next up previous contents index PLPL moodlepserratamodulosperlmonksperldocapuntes LHPgoogleetsiiullpcgull
Sig: La ambiguedad de las Sup: RecDescent Ant: Introducción Err: Si hallas una errata ...

Orden de Recorrido del Árbol de Análisis Sintáctico

RD es un analizador sintáctico descendente recursivo pero no es predictivo. Cuando estamos en la subrutina asociada con una variable sintáctica, va probando las reglas una a una hasta encontrar una que tiene éxito. En ese momento la rutina termina retornando el valor asociado. Consideremos la siguiente gramática (véase el clásico libro de Aho et al. [9], página 182):



S $ \rightarrow$ cAd
A $ \rightarrow$ ab $ \vert$ 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 $ \rightarrow$ 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.

Ejercicio 6.2.1   Dado el siguiente programa Perl
#!/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.


next up previous contents index PLPL moodlepserratamodulosperlmonksperldocapuntes LHPgoogleetsiiullpcgull
Sig: La ambiguedad de las Sup: RecDescent Ant: Introducción Err: Si hallas una errata ...
Casiano Rodríguez León
2012-05-22