Precedencia y Asociatividad

En caso de que no existan indicaciones específicas yacc 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

La precedencia se utiliza para modificar estos criterios. Para ello se define:

1. La precedencia de los tokens es determinada según el orden de declaración. La declaración de tokens mediante la palabra reservada token no modifica la precedencia. Si lo hacen las declaraciones realizadas usando las palabras left, right y nonassoc. Los tokens declarados en la misma línea tienen igual precedencia. La precedencia es mayor cuanto mas abajo en el texto. Así, en el ejemplo que sigue, 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 yacc 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 yacc los tokens con la misma precedencia se declaran en la misma línea.

   Por tanto es imposible declarar dos tokens con diferente asociatividad y la misma precedencia.

5. 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.

Programa 36.2.1   Este programa muestra el manejo de las reglas de precedencia.

%{
#define YYSTYPE double
#include <stdio.h>
%}
%token NUMBER
%left '@' 
%right '&'  dummy
%%
list 
    :
    | list '\n'  
    | list e 
    ;

e : NUMBER  
  | e '&' e 
  | e '@' e %prec dummy
    ;

%%
extern FILE * yyin;
 
main(int argc, char **argv) {
  if (argc > 1) yyin = fopen(argv[1],"r");
  yydebug = 1;
  yyparse();
}
 
yyerror(char *s) {
  printf("%s\n",s);
}

Ejercicio 36.2.1   Dado el programa yacc 36.2.1 Responda a las siguientes cuestiones:

1. Construya las tablas SLR de acciones y gotos.
2. Determine el árbol construido para las frases: 4@3@5, 4&3&5, 4@3&5, 4&3@5.
3. ¿Cuál es la asociatividad final de la regla e : e '@' e?

Listado 36.2.1   Fichero y.output:

   0  $accept : list $end

   1  list :
   2       | list '\n'
   3       | list e

   4  e : NUMBER
   5    | e '&' e
   6    | e '@' e

state 0 $accept : . list $end (0) list : . (1) . reduce 1 list goto 1 state 1 $accept : list . $end (0) list : list . '\n' (2) list : list . e (3) $end accept NUMBER shift 2 '\n' shift 3 . error e goto 4 state 2 e : NUMBER . (4) . reduce 4 state 3 list : list '\n' . (2) . reduce 2 state 4 list : list e . (3) e : e . '&' e (5) e : e . '@' e (6) '@' shift 5 '&' shift 6 $end reduce 3 NUMBER reduce 3 '\n' reduce 3

state 5 e : e '@' . e (6) NUMBER shift 2 . error e goto 7 state 6 e : e '&' . e (5) NUMBER shift 2 . error e goto 8 state 7 e : e . '&' e (5) e : e . '@' e (6) e : e '@' e . (6) '&' shift 6 $end reduce 6 NUMBER reduce 6 '@' reduce 6 '\n' reduce 6 state 8 e : e . '&' e (5) e : e '&' e . (5) e : e . '@' e (6) '&' shift 6 $end reduce 5 NUMBER reduce 5 '@' reduce 5 '\n' reduce 5

7 terminals, 3 nonterminals
7 grammar rules, 9 states

Ejemplo 36.2.1   Contrasta tu respuesta con la traza seguida por el programa anterior ante la entrada 1@2&3, al establecer la variable yydebug = 1 y definir la macro YYDEBUG:

Ejecución 36.2.1  

$ hocprec
yydebug: state 0, reducing by rule 1 (list :)
yydebug: after reduction, shifting from state 0 to state 1
1@2&3
yydebug: state 1, reading 257 (NUMBER)
yydebug: state 1, shifting to state 2
yydebug: state 2, reducing by rule 4 (e : NUMBER)
yydebug: after reduction, shifting from state 1 to state 4
yydebug: state 4, reading 64 ('@')
yydebug: state 4, shifting to state 5
yydebug: state 5, reading 257 (NUMBER)
yydebug: state 5, shifting to state 2
yydebug: state 2, reducing by rule 4 (e : NUMBER)
yydebug: after reduction, shifting from state 5 to state 7
yydebug: state 7, reading 38 ('&')
yydebug: state 7, shifting to state 6

¿Por que se desplaza? ¿No va eso en contra de la declaración %left '@'?. ¿O quizá es porque la precedencia de @ es menor que la de &? La respuesta es que la precedencia asignada por la declaración

e : e '@' e %prec dummy

cambio la asociatividad de la regla. Ahora la regla se ``enfrenta'' a un token, & con su misma precedencia. Al pasar a ser asociativa a derechas (debido a que dummy lo es), se debe desplazar y no reducir.

Ejemplo 36.2.2   Otra ejecución, esta vez con entrada 1&2@3. Compara tus predicciones con los resultados.

Ejecución 36.2.2  

$ hocprec
yydebug: state 0, reducing by rule 1 (list :)
yydebug: after reduction, shifting from state 0 to state 1
1&2@3
yydebug: state 1, reading 257 (NUMBER)
yydebug: state 1, shifting to state 2
yydebug: state 2, reducing by rule 4 (e : NUMBER)
yydebug: after reduction, shifting from state 1 to state 4
yydebug: state 4, reading 38 ('&')
yydebug: state 4, shifting to state 6
yydebug: state 6, reading 257 (NUMBER)
yydebug: state 6, shifting to state 2
yydebug: state 2, reducing by rule 4 (e : NUMBER)
yydebug: after reduction, shifting from state 6 to state 8
yydebug: state 8, reading 64 ('@')
yydebug: state 8, reducing by rule 5 (e : e '&' e)

En este caso se comparan la producción :

e $\rightarrow$ e & e

con el token @. La regla tiene mayor precedencia que el token,dado que la precedencia de la regla es la de &.