Existe una ambiguedad en la parte de las sentencias condicionales de un lenguaje. Por ejemplo, consideremos la gramática:
SENTENCIA
if EXPRESION then SENTENCIA |
| SENTENCIA
if EXPRESION then SENTENCIA else SENTENCIA |
| SENTENCIA
OTRASSENTENCIAS |
Aqui OTRASSENTENCIAS es un terminal/comodín para aludir a cualesquiera otras sentencias que el lenguaje peuda tener (bucles, asignaciones, llamadas a subrutinas, etc.)
La gramática es ambigua, ya que para una sentencia como
then if 
then 
else 
existen dos árboles posibles: uno que asocia el ``else'' con el primer ``if'' y otra que lo asocia con el segundo. Los dos árboles corresponden a las dos posibles parentizaciones:
then (if
then
else
)
Esta es la regla de prioridad usada en la mayor parte de los lenguajes: un ``else'' casa con el ``if' mas cercano. la otra posible parentización es:
then (if
then
) else
El siguiente ejemplo considera una aproximación a la resolución del problema usando
Parse::RecDescent. Para simplificar, la única variable sintáctica que permanece
del ejemplo anterior es SENTENCIA (que ha sido renombrada st).
Las demás han sido convertidas en terminales y se han abreviado.
En esta gramática colocamos primero la regla mas larga st : 'iEt' st 'e' st.
1 #!/usr/local/bin/perl5.8.0 -w
2 use strict;
3 use Parse::RecDescent;
4 use Data::Dumper;
5
6 $::RD_TRACE = 1;
7 $::RD_AUTOACTION = q{ [@item] };
8 my $grammar = q{
9 prog : st ';'
10 st : 'iEt' st 'e' st
11 | 'iEt' st
12 | 'o' { 'o' }
13 };
14
15 my $parse = Parse::RecDescent->new($grammar);
16
17 my $line;
18 while ($line = <>) {
19 print "$line\n";
20 my $result = $parse->prog($line);
21 if (defined($result)) { print Dumper($result); }
22 else { print "Cadena no válida\n"; }
23 }
En este caso, la variable $::RD_AUTOACTION
ha sido establecida a q{ [@item] }. Esto significa
que cada vez que una producción tenga éxito se
devolverá una referencia al array conteniendo los atributos
de los símbolos en la producción.
El contenido de esta variable es evaluado siempre que la producción
en cuestión no tenga una acción asociada explícitamente:
Por tanto, se aplica para todas las reglas
salvo para la regla en la línea 12, en la que se devuelve el
carácter 'o'.
El programa anterior da lugar a la siguiente ejecución:
bash-2.05b$ ./ifthenelse.pl file4.txtEl fichero
file4.txt contiene una sóla línea:
$ cat file4.txt iEt iEt o e o ;que es una frase con dos posibles árboles. RD intentará primero reiteradamente la primera de las producciones de
st:
1| prog |Trying rule: [prog] | 1| prog | |"iEt iEt o e o ;\n" 1| prog |Trying production: [st ';'] | 1| prog |Trying subrule: [st] | 2| st |Trying rule: [st] | 2| st |Trying production: ['iEt' st 'e' st] | 2| st |Trying terminal: ['iEt'] | 2| st |>>Matched terminal<< (return value: | | |[iEt]) | 2| st | |" iEt o e o ;\n" 2| st |Trying subrule: [st] | 3| st |Trying rule: [st] | 3| st |Trying production: ['iEt' st 'e' st] | 3| st |Trying terminal: ['iEt'] | 3| st |>>Matched terminal<< (return value: | | |[iEt]) | 3| st | |" o e o ;\n"Esta opción acabará fracasando, ya que sólo hay un
else.
3| st |Trying subrule: [st] | 4| st |Trying rule: [st] | 4| st |Trying production: ['iEt' st 'e' st] | 4| st |Trying terminal: ['iEt'] | 4| st |<<Didn't match terminal>> |Estamos delante del terminal
o y obviamente la primera producción de st
no casa, se intenta con la segunda, la cual naturalmente fracasrá:
4| st | |"o e o ;\n" 4| st |Trying production: ['iEt' st] | 4| st | |" o e o ;\n" 4| st |Trying terminal: ['iEt'] | 4| st |<<Didn't match terminal>> | 4| st | |"o e o ;\n" 4| st |Trying production: ['o'] |Seguimos delante del terminal
o y la segunda producción de st
tampoco casa, se intenta con la tercera producción:
4| st | |" o e o ;\n" 4| st |Trying terminal: ['o'] | 4| st |>>Matched terminal<< (return value: | | |[o]) | 4| st | |" e o ;\n" 4| st |Trying action | 4| st |>>Matched action<< (return value: [o])|La
o por fin ha sido emparejada.
Se ha ejecutado la acción no automática.
4| st |>>Matched production: ['o']<< | 4| st |>>Matched rule<< (return value: [o]) | 4| st |(consumed: [ o]) | 3| st |>>Matched subrule: [st]<< (return | | |value: [o] |Recuérdese por donde íbamos conjeturando. Se ha construido el árbol (erróneo):
st
|
` 'iEt' st 'e' st
|
` 'iEt' st 'e' st
| ^
` 'o'
Por ello, el e va a ser consumido sin problema:
3| st |Trying terminal: ['e'] | 3| st |>>Matched terminal<< (return value: | | |[e]) | 3| st | |" o ;\n" 3| st |Trying subrule: [st] | 4| st |Trying rule: [st] | 4| st |Trying production: ['iEt' st 'e' st] | 4| st |Trying terminal: ['iEt'] | 4| st |<<Didn't match terminal>> | 4| st | |"o ;\n" 4| st |Trying production: ['iEt' st] | 4| st | |" o ;\n" 4| st |Trying terminal: ['iEt'] | 4| st |<<Didn't match terminal>> | 4| st | |"o ;\n" 4| st |Trying production: ['o'] | 4| st | |" o ;\n" 4| st |Trying terminal: ['o'] | 4| st |>>Matched terminal<< (return value: | | |[o]) | 4| st | |" ;\n" 4| st |Trying action | 4| st |>>Matched action<< (return value: [o])| 4| st |>>Matched production: ['o']<< | 4| st |>>Matched rule<< (return value: [o]) | 4| st |(consumed: [ o]) | 3| st |>>Matched subrule: [st]<< (return | | |value: [o] | 3| st |Trying action | 3| st |>>Matched action<< (return value: | | |[ARRAY(0x830cc04)]) |Hemos construido el árbol:
st
|
` 'iEt' st 'e' st
| ^
` 'iEt' st 'e' st
| |
` 'o' `o
Asi pues la segunda regla conjeturada st : 'iEt' st 'e' st ha tenido
éxito. Después de esto esperamos ver e, pero lo que hay en la entrada
es un punto y coma.
3| st |>>Matched production: ['iEt' st 'e' | | |st]<< | 3| st |>>Matched rule<< (return value: | | |[ARRAY(0x830cc04)]) | 3| st |(consumed: [ iEt o e o]) | 2| st |>>Matched subrule: [st]<< (return | | |value: [ARRAY(0x830cc04)] | 2| st |Trying terminal: ['e'] | 2| st |<<Didn't match terminal>> | 2| st | |";\n"Se ha fracasado. Se probará a este nivel con la siguiente regla
st : 'iEt' st (que acabará produciendo un árbol de acuerdo
con la regla del ``if'' mas cercano).
Mágicamente, la entrada consumida es devuelta
para ser procesada de nuevo (obsérvese la tercera columna).
Sin embargo, los efectos laterales que
las acciones ejecutadas por las acciones asociadas con los falsos
éxitos permanecen. En este caso, por la forma en la que
hemos escrito las acciones, no hay ningún efecto lateral.
2| st |Trying production: ['iEt' st] | 2| st | |"iEt iEt o e o ;\n" 2| st |Trying terminal: ['iEt'] | 2| st |>>Matched terminal<< (return value: | | |[iEt]) | 2| st | |" iEt o e o ;\n" 2| st |Trying subrule: [st] | 3| st |Trying rule: [st] | 3| st |Trying production: ['iEt' st 'e' st] |Ahora el analizador va a intentar el árbol:
st
|
` 'iEt' st
|
` 'iEt' st 'e' st
que se corresponde con la interpretación clásica:
El else casa con el if mas cercano.
3| st |Trying terminal: ['iEt'] | 3| st |>>Matched terminal<< (return value: | | |[iEt]) | 3| st | |" o e o ;\n" 3| st |Trying subrule: [st] |La ineficiencia de RD es clara aqui. Va a intentar de nuevo las diferentes reglas hasta dar con la del
'o'
4| st |Trying rule: [st] | 4| st |Trying production: ['iEt' st 'e' st] | 4| st |Trying terminal: ['iEt'] | 4| st |<<Didn't match terminal>> | 4| st | |"o e o ;\n" 4| st |Trying production: ['iEt' st] | 4| st | |" o e o ;\n" 4| st |Trying terminal: ['iEt'] | 4| st |<<Didn't match terminal>> | 4| st | |"o e o ;\n" 4| st |Trying production: ['o'] | 4| st | |" o e o ;\n" 4| st |Trying terminal: ['o'] | 4| st |>>Matched terminal<< (return value: | | |[o]) | 4| st | |" e o ;\n" 4| st |Trying action | 4| st |>>Matched action<< (return value: [o])| 4| st |>>Matched production: ['o']<< | 4| st |>>Matched rule<< (return value: [o]) | 4| st |(consumed: [ o]) | 3| st |>>Matched subrule: [st]<< (return | | |value: [o] |Ahora el ``else'' será consumido por la sentencia condicional anidada:
3| st |Trying terminal: ['e'] | 3| st |>>Matched terminal<< (return value: | | |[e]) | 3| st | |" o ;\n"y de nuevo debemos pasar por el calvario de todas las reglas, ya que la
'o' es la última
de las reglas:
3| st |Trying subrule: [st] | 4| st |Trying rule: [st] | 4| st |Trying production: ['iEt' st 'e' st] | 4| st |Trying terminal: ['iEt'] | 4| st |<<Didn't match terminal>> | 4| st | |"o ;\n" 4| st |Trying production: ['iEt' st] | 4| st | |" o ;\n" 4| st |Trying terminal: ['iEt'] | 4| st |<<Didn't match terminal>> | 4| st | |"o ;\n" 4| st |Trying production: ['o'] | 4| st | |" o ;\n" 4| st |Trying terminal: ['o'] | 4| st |>>Matched terminal<< (return value: | | |[o]) | 4| st | |" ;\n" 4| st |Trying action | 4| st |>>Matched action<< (return value: [o])| 4| st |>>Matched production: ['o']<< | 4| st |>>Matched rule<< (return value: [o]) | 4| st |(consumed: [ o]) |A partir de aqui todo encaja. Nótese la ejecución de la acción automática:
3| st |>>Matched subrule: [st]<< (return | | |value: [o] | 3| st |Trying action | 3| st |>>Matched action<< (return value: | | |[ARRAY(0x82f2774)]) | 3| st |>>Matched production: ['iEt' st 'e' | | |st]<< | 3| st |>>Matched rule<< (return value: | | |[ARRAY(0x82f2774)]) | 3| st |(consumed: [ iEt o e o]) | 2| st |>>Matched subrule: [st]<< (return | | |value: [ARRAY(0x82f2774)] | 2| st |Trying action | 2| st |>>Matched action<< (return value: | | |[ARRAY(0x830c41c)]) | 2| st |>>Matched production: ['iEt' st]<< | 2| st |>>Matched rule<< (return value: | | |[ARRAY(0x830c41c)]) | 2| st |(consumed: [iEt iEt o e o]) | 1| prog |>>Matched subrule: [st]<< (return | | |value: [ARRAY(0x830c41c)] |A estas alturas hemos construido el árbol:
st
|
` 'iEt' st
|
` 'iEt' st 'e' st
| |
` 'o' `o
y el punto y coma nos espera en la entrada:
1| prog |Trying terminal: [';'] | 1| prog |>>Matched terminal<< (return value: | | |[;]) | 1| prog | |"\n" 1| prog |Trying action | 1| prog |>>Matched action<< (return value: | | |[ARRAY(0x830c314)]) | 1| prog |>>Matched production: [st ';']<< | 1| prog |>>Matched rule<< (return value: | | |[ARRAY(0x830c314)]) | 1| prog |(consumed: [iEt iEt o e o ;]) |Ahora ya se ejecuta la línea
print Dumper($result)
en el programa principal, volcando la estructura de datos
construida durante el análisis:
$VAR1 = [ 'prog',
[ 'st',
'iEt',
[ 'st',
'iEt', 'o', 'e', 'o'
]
],
';'
];
my $grammar = q{
st : 'iEt' st { [ @item ] }
| 'iEt' st 'e' st { [ @item ] }
| 'o'
};
¿Que árbol se obtendrá al darle la entrada iEt iEt o e o ;?
¿Que ocurre si, manteniendo este orden, forzamos a que el programa termine en
punto y coma?
my $grammar = q{
prog : st ';'
st : 'iEt' st { [ @item ] }
| 'iEt' st 'e' st { [ @item ] }
| 'o'
};
¿Es aceptada la cadena?
| SENTENCIA |
|
EQUI | 
NOEQUI |
| EQUI |
|
if EXPRESION then EQUI else EQUI |
OTRASSENTENCIAS |
| NOEQUI |
|
if EXPRESION then SENTENCIA |
|
| if EXPRESION then EQUI else NOEQUI |
Escriba un analizador sintáctico para la gramática usando RD y analice su comportamiento.