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 .
* tiene
mayor precedencia que + pero la misma que /.
se
define como la del terminal mas a la derecha que aparece en
. En el ejemplo, la producción
expr : expr '+' expr
tiene la precedencia del token +.
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 8.3 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.
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 1A 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.