Precedencia y Asociatividad

Recordemos que si al construir la tabla LALR, alguna de las entradas de la tabla resulta multievaluada, decimos que existe un conflicto. Si una de las acciones es de `reducción'' y la otra es de `desplazamiento'', se dice que hay un conflicto shift-reduce o conflicto de desplazamiento-reducción. Si las dos reglas indican una acción de reducción, decimos que tenemos un conflicto reduce-reduce o de reducción-reducción. En caso de que no existan indicaciones específicas yapp resuelve los conflictos que aparecen en la construcción de la tabla utilizando las siguientes reglas:

1. Un conflicto reduce-reduce se resuelve eligiendo la producción que se listó primero en la especificación de la gramática.
2. Un conflicto shift-reduce se resuelve siempre en favor del shift

Las declaraciones de precedencia y asociatividad mediante las palabras reservadas %left , %right , %nonassoc se utilizan para modificar estos criterios por defecto. La declaración de token s mediante la palabra reservada %token no modifica la precedencia. Si lo hacen las declaraciones realizadas usando las palabras left , right y nonassoc .

1. Los tokens declarados en la misma línea tienen igual precedencia e igual asociatividad. La precedencia es mayor cuanto mas abajo su posición en el texto. Así, en el ejemplo de la calculadora en la sección 35.1, el token * tiene mayor precedencia que + pero la misma que /.
2. La precedencia de una regla $A \rightarrow \alpha$ se define como la del terminal mas a la derecha que aparece en $\alpha$. En el ejemplo, la producción
   expr : expr '+' expr

   tiene la precedencia del token +.

3. Para decidir en un conflicto shift-reduce se comparan la precedencia de la regla con la del terminal que va a ser desplazado. Si la de la regla es mayor se reduce si la del token es mayor, se desplaza.
4. Si en un conflicto shift-reduce ambos la regla y el terminal que va a ser desplazado tiene la misma precedencia yapp considera la asociatividad, si es asociativa a izquierdas, reduce y si es asociativa a derechas desplaza. Si no es asociativa, genera un mensaje de error.
   Obsérvese que, en esta situación, la asociatividad de la regla y la del token han de ser por fuerza, las mismas. Ello es así, porque en yapp los tokens con la misma precedencia se declaran en la misma línea y sólo se permite una declaración por línea.

5. Por tanto es imposible declarar dos tokens con diferente asociatividad y la misma precedencia.
6. Es posible modificar la precedencia ``natural'' de una regla, calificándola con un token específico. para ello se escribe a la derecha de la regla prec token, donde token es un token con la precedencia que deseamos. Vea el uso del token dummy en el siguiente ejercicio.

Para ilustrar las reglas anteriores usaremos el siguiente programa yapp:

$ cat -n Precedencia.yp
     1  %token NUMBER
     2  %left '@'
     3  %right '&'  dummy
     4  %%
     5  list
     6      :
     7      | list '\n'
     8      | list e
     9      ;
    10
    11  e : NUMBER
    12    | e '&' e
    13    | e '@' e %prec dummy
    14    ;
    15
    16  %%

El código del programa cliente es el siguiente:

$ cat -n useprecedencia.pl
cat -n useprecedencia.pl
     1  #!/usr/bin/perl -w
     2  use strict;
     3  use Precedencia;
     4
     5  sub Error {
     6    exists $_[0]->YYData->{ERRMSG}
     7    and do {
     8      print $_[0]->YYData->{ERRMSG};
     9      delete $_[0]->YYData->{ERRMSG};
    10      return;
    11    };
    12    print "Syntax error.\n";
    13  }
    14
    15  sub Lexer {
    16    my($parser)=shift;
    17
    18    defined($parser->YYData->{INPUT})
    19    or  $parser->YYData->{INPUT} = <STDIN>
    20    or  return('',undef);
    21
    22    $parser->YYData->{INPUT}=~s/^[ \t]//;
    23
    24    for ($parser->YYData->{INPUT}) {
    25        s/^([0-9]+(?:\.[0-9]+)?)//
    26                and return('NUMBER',$1);
    27        s/^(.)//s
    28                and return($1,$1);
    29    }
    30  }
    31
    32  my $debug_level = (@ARGV)? oct(shift @ARGV): 0x1F;
    33  my $parser = Precedencia->new();
    34  $parser->YYParse( yylex => \&Lexer, yyerror => \&Error, yydebug => $debug_level );

Observe la llamada al analizador en la línea 34. Hemos añadido el parámetro con nombre yydebug con argumento yydebug => $debug_level (véase la sección 35.6 para ver los posibles valores de depuración).

Compilamos a continuación el módulo usando la opción -v para producir información sobre los conflictos y las tablas de salto y de acciones:

yapp -v -m Precedencia Precedencia.yp
$ ls -ltr |tail -2
-rw-r--r--  1 lhp lhp   1628 2004-12-07 13:21 Precedencia.pm
-rw-r--r--  1 lhp lhp   1785 2004-12-07 13:21 Precedencia.output

La opción -v genera el fichero Precedencia.output el cual contiene información detallada sobre el autómata:

$ cat -n Precedencia.output
     1  Conflicts:
     2  ----------
     3  Conflict in state 8 between rule 6 and token '@' resolved as reduce.
     4  Conflict in state 8 between rule 6 and token '&' resolved as shift.
     5  Conflict in state 9 between rule 5 and token '@' resolved as reduce.
     6  Conflict in state 9 between rule 5 and token '&' resolved as shift.
     7
     8  Rules:
     9  ------
    10  0:      $start -> list $end
    11  1:      list -> /* empty */
    12  2:      list -> list '\n'
    13  3:      list -> list e
    14  4:      e -> NUMBER
    15  5:      e -> e '&' e
    16  6:      e -> e '@' e
    17  ...

¿Porqué se produce un conflicto en el estado 8 entre la regla 6 (e -> e '@' e) y el terminal '@'?. Editando el fichero Precedencia.output podemos ver los contenidos del estado 8:

85  State 8:
86
87          e -> e . '&' e  (Rule 5)
88          e -> e . '@' e  (Rule 6)
89          e -> e '@' e .  (Rule 6)
90
91          '&'     shift, and go to state 7
92
93          $default        reduce using rule 6 (e)

El item de la línea 88 indica que debemos desplazar, el de la línea 89 que debemos reducir por la regla 6. ¿Porqué yapp resuelve el conflicto optando por reducir? ¿Que prioridad tiene la regla 6? ¿Que asociatividad tiene la regla 6? La declaración en la línea 13 modifica la precedencia y asociatividad de la regla:

    13    | e '@' e %prec dummy

de manera que la regla pasa a tener la precedencia y asociatividad de dummy. Recuerde que habíamos declarado dummy como asociativo a derechas:

     2  %left '@'
     3  %right '&'  dummy

¿Que ocurre? Que dummy tiene mayor prioridad que '@' y por tanto la regla tiene mayor prioridad que el terminal: por tanto se reduce.

¿Que ocurre cuando el terminal en conflicto es '&'? En ese caso la regla y el terminal tienen la misma prioridad. Se hace uso de la asociatividad a derechas que indica que el conflicto debe resolverse desplazando.

Ejercicio 35.7.1   Explique la forma en que yapp resuelve los conflictos que aparecen en el estado 9. Esta es la información sobre el estado 9:

State 9:

	e -> e . '&' e	(Rule 5)
	e -> e '&' e .	(Rule 5)
	e -> e . '@' e	(Rule 6)
	'&'	shift, and go to state 7
	$default	reduce using rule 5 (e)

Veamos un ejemplo de ejecución:

$ ./useprecedencia.pl
----------------------------------------
In state 0:
Stack:[0]
Don't need token.
Reduce using rule 1 (list,0): Back to state 0, then go to state 1.

Lo primero que ocurre es una reducción por la regla en la que list produce vacío. Si miramos el estado 0 del autómata vemos que contiene:

20 State 0:
21
22   $start -> . list $end (Rule 0)
23
24   $default  reduce using rule 1 (list)
25
26   list  go to state 1

A continuación se transita desde 0 con list y se consume el primer terminal:

----------------------------------------
In state 1:
Stack:[0,1]
2@3@4
Need token. Got >NUMBER<
Shift and go to state 5.
----------------------------------------
In state 5:
Stack:[0,1,5]
Don't need token.
Reduce using rule 4 (e,1): Back to state 1, then go to state 2.
----------------------------------------

En el estado 5 se reduce por la regla e -> NUMBER. Esto hace que se retire el estado 5 de la pila y se transite desde el estado 1 viendo el símbolo e:

In state 2:
Stack:[0,1,2]
Need token. Got >@<
Shift and go to state 6.
----------------------------------------
In state 6:
Stack:[0,1,2,6]
Need token. Got >NUMBER<
Shift and go to state 5.
----------------------------------------
In state 5:
Stack:[0,1,2,6,5]
Don't need token.
Reduce using rule 4 (e,1): Back to state 6, then go to state 8.
----------------------------------------
In state 8:
Stack:[0,1,2,6,8]
Need token. Got >@<
Reduce using rule 6 (e,3): Back to state 1, then go to state 2.
----------------------------------------
...
Accept.

Obsérvese la resolución del conflicto en el estado 8

La presencia de conflictos, aunque no siempre, en muchos casos es debida a la introducción de ambiguedad en la gramática. Si el conflicto es de desplazamiento-reducción se puede resolver explicitando alguna regla que rompa la ambiguedad. Los conflictos de reducción-reducción suelen producirse por un diseño erróneo de la gramática. En tales casos, suele ser mas adecuado modificar la gramática.