Consejos a seguir al escribir un programa yapp

Ejemplo 7.17.1 Consideremos de nuevo el programa yapp para producir árboles para las expresiones en infijo. Supongamos que olvidamos introducir una prioridad explícita al terminal '=':

$ cat -n Infixtree_conflict.yp
 1  #
 2  # Infixtree.yp
 3  #
 4
 5  %{
 6  use Data::Dumper;
 7  %}
 8  %left   '-' '+'
 9  %left   '*' '/'
10  %left   NEG
11
12  %%
13  input:  #empty
14          |   input line
15  ;
16
17  line:     '\n'         { $_[1] }
18          | exp '\n'     { print Dumper($_[1]); }
19          | error '\n'   { $_[0]->YYErrok }
20  ;
21
22  exp:        NUM
23          |   VAR                 { $_[1] }
24          |   VAR '=' exp         { bless [$_[1], $_[3]], 'ASSIGN' }
25          |   exp '+' exp         { bless [$_[1], $_[3] ], 'PLUS'}
26          |   exp '-' exp         { bless [$_[1], $_[3] ], 'MINUS'}
27          |   exp '*' exp         { bless [$_[1], $_[3]], 'TIMES' }
28          |   exp '/' exp         { bless [$_[1], $_[3]], 'DIVIDE' }
   ....

en este caso al compilar encontraremos conflictos:

$ yapp -v -m Infixtree Infixtree_conflict.yp
4 shift/reduce conflicts

En tal caso lo que debemos hacer es editar el fichero .output. El comienzo del fichero es como sigue:

$ cat -n Infixtree_conflict.output
1  Warnings:
2  ---------
3  4 shift/reduce conflicts
4
5  Conflicts:
6  ----------
7  Conflict in state 11 between rule 13 and token '-' resolved as reduce.
8  Conflict in state 11 between rule 13 and token '*' resolved as reduce.
  ...

Tal y como indica la expresión ...resolved as ..., las líneas como la 7, la 8 y siguientes se refieren a conflictos resueltos. Mas abajo encontraremos información sobre la causa de nuestros conflictos no resueltos:

    ...
26  Conflict in state 23 between rule 11 and token '/' resolved as reduce.
27  State 25 contains 4 shift/reduce conflicts

Lo que nos informa que los conflictos ocurren en el estado 25 ante 4 terminales distintos. Nos vamos a la parte del fichero en la que aparece la información relativa al estado 25. Para ello, como el fichero es grande, buscamos por la cadena adecuada. En vi buscaríamos por /^State 25. Las líneas correspondientes contienen:

291 State 25:
292
293   exp -> VAR '=' exp .  (Rule 8)
294   exp -> exp . '+' exp  (Rule 9)
295   exp -> exp . '-' exp  (Rule 10)
296   exp -> exp . '*' exp  (Rule 11)
297   exp -> exp . '/' exp  (Rule 12)
298
299   '*' shift, and go to state 16
300   '+' shift, and go to state 13
301   '-' shift, and go to state 12
302   '/' shift, and go to state 15
303
304   '*' [reduce using rule 8 (exp)]
305   '+' [reduce using rule 8 (exp)]
306   '-' [reduce using rule 8 (exp)]
307   '/' [reduce using rule 8 (exp)]
308   $default  reduce using rule 8 (exp)

El comentario en la línea 308 ($default ...) indica que por defecto, ante cualquier otro terminal que no sea uno de los explícitamente listados, la acción a tomar por el analizador será reducir por la regla 8.

Una revisión a la numeración de la gramática, al comienzo del fichero .output nos permite ver cuál es la regla 8:

29 Rules:
30 ------
31 0:  $start -> input $end
32 1:  input -> /* empty */
33 2:  input -> input line
34 3:  line -> '\n'
35 4:  line -> exp '\n'
36 5:  line -> error '\n'
37 6:  exp -> NUM
38 7:  exp -> VAR
39 8:  exp -> VAR '=' exp
40 9:  exp -> exp '+' exp
41 10: exp -> exp '-' exp
42 11: exp -> exp '*' exp
43 12: exp -> exp '/' exp
44 13: exp -> '-' exp
45 14: exp -> '(' exp ')'

Efectivamente, es la regla de asignación exp -> VAR '=' exp. El conflicto aparece por que los terminales * + - / están en el conjunto FOLLOW(exp) y también cabe esperarlos respectivamente en las reglas 9, 10, 11 y 12 ya que el estado 25 contiene:

294   exp -> exp . '+' exp  (Rule 9)
295   exp -> exp . '-' exp  (Rule 10)
296   exp -> exp . '*' exp  (Rule 11)
297   exp -> exp . '/' exp  (Rule 12)

Estamos ante un caso en el que se aplica el consejo número 8. Los items de la forma $B \rightarrow \beta_\uparrow \gamma$ , son los de la forma exp -> exp . '+' exp, etc. El item de la forma $A \rightarrow \alpha_\uparrow$ es en este caso exp -> VAR '=' exp.

En efecto, en una expresión como a = 4 + 3 se produce una ambiguedad. ¿Debe interpretarse como (a = 4) + 3? ¿O bien como a = (4 + 3)?. La primera interpretación corresponde a reducir por la regla 8. La segunda a desplazar al estado 13. En este ejemplo, el conflicto se resuelve haciendo que tenga prioridad el desplazamiento, dando menor prioridad al terminal = que a los terminales * + - /.