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 jison 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 jison 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 jison 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 jison:

[~/jison/jison-prec(ast)]$ cat -n precedencia.jison 
 1  %token NUMBER
 2  %left '@'
 3  %right '&'  dummy
 4  %%
 5  s 
 6      : list      { console.log($list); }
 7      ;
 8  
 9  list
10      :
11                  {
12                    $$ = [];
13                  }
14      | list '\n'
15                  {
16                    $$ = $1;
17                  }
18      | list e
19                  {
20                    $$ = $1;
21                    $$.push($e);
22                  }
23      ;
24  
25  e : NUMBER
26                  {
27                    $$ = "NUMBER ("+yytext+")";
28                  }
29    | e '&' e
30                  {
31                    $$ = [ "&", $e1, $e2];
32                  }
33    | e '@' e %prec dummy
34                  {
35                    $$ = ["@", $e1, $e2];
36                  }
37    ;
38  
39  %%

Obsérvese la siguiente ejecución:

[~/jison/jison-prec(ast)]$ cat input.txt 
2@3@4
2&3&4
[~/jison/jison-prec(ast)]$ node precedencia.js input.txt 
[ [ '@', [ '@', 'NUMBER (2)', 'NUMBER (3)' ], 'NUMBER (4)' ],
  [ '&', 'NUMBER (2)', [ '&', 'NUMBER (3)', 'NUMBER (4)' ] ] ]

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

[~/jison/jison-prec(ast)]$ bison -v precedencia.jison 
precedencia.jison:6.31: warning: stray `$'
precedencia.jison:21.27: warning: stray `$'
precedencia.jison:31.31: warning: stray `$'
precedencia.jison:31.36: warning: stray `$'
precedencia.jison:35.30: warning: stray `$'
precedencia.jison:35.35: warning: stray `$'

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

[~/jison/jison-prec(ast)]$ cat precedencia.output 
Grammar

    0 $accept: s $end

    1 s: list

    2 list: /* empty */
    3     | list '\n'
    4     | list e

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


Terminals, with rules where they appear

$end (0) 0
'\n' (10) 3
'&' (38) 6
'@' (64) 7
error (256)
NUMBER (258) 5
dummy (259)


Nonterminals, with rules where they appear

$accept (8)
    on left: 0
s (9)
    on left: 1, on right: 0
list (10)
    on left: 2 3 4, on right: 1 3 4
e (11)
    on left: 5 6 7, on right: 4 6 7


state 0

    0 $accept: . s $end

    $default  reduce using rule 2 (list)

    s     go to state 1
    list  go to state 2


state 1

    0 $accept: s . $end

    $end  shift, and go to state 3


state 2

    1 s: list .
    3 list: list . '\n'
    4     | list . e

    NUMBER  shift, and go to state 4
    '\n'    shift, and go to state 5

    $default  reduce using rule 1 (s)

    e  go to state 6


state 3

    0 $accept: s $end .

    $default  accept


state 4

    5 e: NUMBER .

    $default  reduce using rule 5 (e)


state 5

    3 list: list '\n' .

    $default  reduce using rule 3 (list)


state 6

    4 list: list e .
    6 e: e . '&' e
    7  | e . '@' e

    '@'  shift, and go to state 7
    '&'  shift, and go to state 8

    $default  reduce using rule 4 (list)


state 7

    7 e: e '@' . e

    NUMBER  shift, and go to state 4

    e  go to state 9


state 8

    6 e: e '&' . e

    NUMBER  shift, and go to state 4

    e  go to state 10


state 9

    6 e: e . '&' e
    7  | e . '@' e
    7  | e '@' e .

    '&'  shift, and go to state 8

    $default  reduce using rule 7 (e)


state 10

    6 e: e . '&' e
    6  | e '&' e .
    7  | e . '@' e

    '&'  shift, and go to state 8

    $default  reduce using rule 6 (e)

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.