S
cAd |
A
ab 
a |
Claramente la gramática no es LL(1). Codifiquemos la gramática usando RD:
$ cat -n aho182.pl
1 #!/usr/bin/perl -w
2 use strict;
3 use warnings;
4
5 use Parse::RecDescent;
6
7 $::RD_TRACE = 1;
8 $::RD_AUTOACTION = q{ 1 };
9 my $grammar = q {
10 S : 'c' A 'd' { print "Éxito!\n" }
11 A : 'a' 'b'
12 | 'a'
13 };
14
15 my $parser=Parse::RecDescent->new($grammar);
16 my $input = <>;
17 $parser->S($input);
en este ejemplo usamos dos nuevas variables (líneas 7 y 8)
que gobiernan la conducta
de un analizador generado por RD. Las variables $::RD_TRACE
y $::RD_AUTOACTION. La primera hace que el analizador generado
vuelque en stderr un informe del análisis.
La asignación en la línea 8 de una cadena a $::RD_AUTOACTION
hace que todas las producciones con las cuáles no se asocie una acción
explícitamente, tengan como acción asociada la cadena que figura
en la variable $::RD_AUTOACTION (en este caso, devolver 1).
Así las producciones en las líneas 11 y 12 tienen asociadas la acción
{ 1 }, mientras que la acción asociada con la producción
en la línea 10 es { print "Éxito!\n" }.
Obsérvese que, dado que el analizador se ejecuta dentro de
su propio espacio de nombres, las variables que pertenzcan al
paquete Main como es el caso de RD_AUTOACTION
deben ser explicitadas prefijándolas con el nombre del
paquete.
Veamos el comportamiento del programa con la entrada c a d.
Al ejecutar el programa, lo primero que ocurre, al construir
el objeto analizador en la línea 15 es que RD nos informa de
su interpretación de los diferentes símbolos en la gramática:
$ ./aho182.pl
Parse::RecDescent: Treating "S :" as a rule declaration
Parse::RecDescent: Treating "c" as a literal terminal
Parse::RecDescent: Treating "A" as a subrule match
Parse::RecDescent: Treating "d" as a literal terminal
Parse::RecDescent: Treating "{ print "Éxito!\n" }" as an action
Parse::RecDescent: Treating "A :" as a rule declaration
Parse::RecDescent: Treating "a" as a literal terminal
Parse::RecDescent: Treating "b" as a literal terminal
Parse::RecDescent: Treating "|" as a new production
Parse::RecDescent: Treating "a" as a literal terminal
printing code (12078) to RD_TRACE
Ahora se ejecuta la entrada en la línea 16, tecleamos c a d
y sigue una información detallada de la cosntrucción del árbol
sintáctico concreto:
c a d 1| S |Trying rule: [S] | 1| S | |"c a d\n" 1| S |Trying production: ['c' A 'd'] | 1| S |Trying terminal: ['c'] | 1| S |>>Matched terminal<< (return value: | | |[c]) |La salida aparece en cuatro columnas. El número de línea en el texto de la gramática, la variable sintáctica (que en la jerga RD se denomina regla o subregla), una descripción verbal de lo que se está haciendo y por último, la cadena de entrada que queda por leer. Se acaba de casar
c y por tanto se pasa
a llamar al método asociado con A. en la entrada queda
a d\n:
1| S | |" a d\n" 1| S |Trying subrule: [A] | 2| A |Trying rule: [A] | 2| A |Trying production: ['a' 'b'] | 2| A |Trying terminal: ['a'] | 2| A |>>Matched terminal<< (return value: | | |[a]) | 2| A | |" d\n" 2| A |Trying terminal: ['b'] | 2| A |<<Didn't match terminal>> |RD intenta infructuosamente la primera producción
a b
por tanto va a probar con la segunda producción de A:
2| A | |"d\n" 2| A |Trying production: ['a'] | 2| A | |" a d\n" 2| A |Trying terminal: ['a'] | 2| A |>>Matched terminal<< (return value: | | |[a]) | 2| A | |" d\n" 2| A |Trying action | 2| A |>>Matched action<< (return value: [1])| 2| A |>>Matched production: ['a']<< | 2| A |>>Matched rule<< (return value: [1]) | 2| A |(consumed: [ a]) | 1| S |>>Matched subrule: [A]<< (return | | |value: [1] | 1| S |Trying terminal: ['d'] | 1| S |>>Matched terminal<< (return value: | | |[d]) | 1| S | |"\n" 1| S |Trying action | Éxito! 1| S |>>Matched action<< (return value: [1])| 1| S |>>Matched production: ['c' A 'd']<< | 1| S |>>Matched rule<< (return value: [1]) | 1| S |(consumed: [c a d]) |De este modo la frase es aceptada. Sin embargo, ¿que ocurriría si invertimos el orden de las producciones de
A y damos como entrada la cadena c a b d?
Puesto que RD es ocioso, la ahora primera regla A : a
tendrá éxito y el control retornará al método
asociado con S:
$ ./aho182_reverse.pl c a b d 1| S |Trying rule: [S] | 1| S | |"c a b d\n" 1| S |Trying production: ['c' A 'd'] | 1| S |Trying terminal: ['c'] | 1| S |>>Matched terminal<< (return value: | | |[c]) | 1| S | |" a b d\n" 1| S |Trying subrule: [A] | 2| A |Trying rule: [A] | 2| A |Trying production: ['a'] | 2| A |Trying terminal: ['a'] | 2| A |>>Matched terminal<< (return value: | | |[a]) | 2| A | |" b d\n" 2| A |Trying action | 2| A |>>Matched action<< (return value: [1])| 2| A |>>Matched production: ['a']<< | 2| A |>>Matched rule<< (return value: [1]) | 2| A |(consumed: [ a]) |Ahora RD va a rechazar la cadena. No intenta llamar de nuevo al método asociado con
A para que haga nuevos intentos:
1| S |>>Matched subrule: [A]<< (return | | |value: [1] | 1| S |Trying terminal: ['d'] | 1| S |<<Didn't match terminal>> | 1| S | |"b d\n" 1| S |<<Didn't match rule>> |
Debes, por tanto, ser cuidadoso con el orden en el que escribes las producciones. El orden en que las escribas tiene una importante incidencia en la conducta del analizador. En general el analizador generado por RD no acepta el lenguaje generado por la gramática, en el sentido formal de la expresión lenguaje generado, tal y como fué definida en la definición 8.1.4. En este sentido, hay una separación semántica similar a la que ocurre en las expresiones regulares. El or en las expresiones regulares de Perl también es perezoso, a diferencia de la convención adoptada en el estudio teórico de los lenguajes regulares y los autómatas.
#!/usr/local/bin/perl5.8.0 -w
use strict;
use warnings;
use Parse::RecDescent;
$::RD_TRACE = 1;
my $grammar = q {
start: seq_1 ';'
seq_1 : 'A' 'B' 'C' 'D'
{ print "seq_1: " . join (" ", @item[1..$#item]) . "\n" }
| 'A' 'B' 'C' 'D' 'E' 'F'
{ print "seq_1: " . join (" ", @item[1..$#item]) . "\n" }
};
my $parser=Parse::RecDescent->new($grammar);
my $result = $parser->start("A B C D E F ;");
if (defined($result)) {
print "Valida\n";
} else { print "No reconocida\n"; }
¿Cuál es la salida?
Indica que ocurre si cambiamos el lugar en el que aparece el separador
punto y coma, poniéndolo en las producciones de seq_1
como sigue:
#!/usr/local/bin/perl5.8.0 -w
use strict;
use warnings;
use Parse::RecDescent;
$::RD_TRACE = 1;
my $grammar = q {
start: seq_1
seq_1 : 'A' 'B' 'C' 'D' ';'
{ print "seq_1: " . join (" ", @item[1..$#item]) . "\n" }
| 'A' 'B' 'C' 'D' 'E' 'F' ';'
{ print "seq_1: " . join (" ", @item[1..$#item]) . "\n" }
};
my $parser=Parse::RecDescent->new($grammar);
my $result = $parser->start("A B C D E F ;");
if (defined($result)) {
print "Valida\n";
} else { print "No reconocida\n"; }
¿Podrías resumir en palabras la forma en la que RD explora el árbol de análisis concreto? Intenta escribir un seudocódigo que resuma el comportamiento de RD.