next up previous contents index PLPL moodlepserratamodulosperlmonksperldocapuntes LHPgoogleetsiiullpcgull
Sig: Definición Dirigida por la Sup: Análisis Semántico con Parse::Eyapp Ant: Esquemas de Traducción: Conceptos Err: Si hallas una errata ...


Esquemas de Traducción con Parse::Eyapp

La distribución Parse::Eyapp debida al autor de estos apuntes (i.e. Casiano Rodriguez-Leon) permite la escritura de esquemas de traducción. El módulo no esta aún disponible en CPAN: estoy a la espera de completar las pruebas y la documentación.

El ejemplo simple que sigue ilustra como construir un esquema de traducción. El código completo puede encontrarlo en la página [*]. Un ejemplo de ejecución del programa se encuentra en la página [*].

Comencemos por el principio:

nereida:~/doc/casiano/PLBOOK/PLBOOK/code> head -n79 trans_scheme_simple2.pl | cat -n
 1  #!/usr/bin/perl -w
 2  use strict;
 3  use Data::Dumper;
 4  use Parse::Eyapp;
 5  use IO::Interactive qw(is_interactive);
 6
 7  my $translationscheme = q{
 8  %{
 9  # head code is available at tree construction time
10  use Data::Dumper;
11
12  our %sym; # symbol table
13  %}
14
15  %metatree
16
17  %right   '='
18  %left   '-' '+'
19  %left   '*' '/'
20
21  %%
22  line:       %name EXP
23                exp <+ ';'> /* Expressions separated by semicolons */
24                  { $lhs->{n} = [ map { $_->{n}} $_[1]->Children() ]; }
25  ;
26
27  exp:
28              %name PLUS
29                exp.left '+'  exp.right
30                  { $lhs->{n} = $left->{n} + $right->{n} }
31          |   %name MINUS
32                exp.left '-' exp.right
33                  { $lhs->{n} = $left->{n} - $right->{n} }
34          |   %name TIMES
35                exp.left '*' exp.right
36                  { $lhs->{n} = $left->{n} * $right->{n} }
37          |   %name DIV
38                exp.left '/' exp.right
39                  { $lhs->{n} = $left->{n} / $right->{n} }
40          |   %name NUM   $NUM
41                  { $lhs->{n} = $NUM->{attr} }
42          |   '(' $exp ')'  %begin { $exp }
43          |   %name VAR
44                $VAR
45                  { $lhs->{n} = $sym{$VAR->{attr}}->{n} }
46          |   %name ASSIGN
47                $VAR '=' $exp
48                  { $lhs->{n} = $sym{$VAR->{attr}}->{n} = $exp->{n} }
49
50  ;
51
52  %%
53  # tail code is available at tree construction time
54  sub _Error {
55    my($token)=$_[0]->YYCurval;
56    my($what)= $token ? "input: '$token'" : "end of input";
57
58    die "Syntax error near $what.\n";
59  }
60
61  sub _Lexer {
62      my($parser)=shift;
63
64      for ($parser->YYData->{INPUT}) {
65          $_ or  return('',undef);
66
67          s/^\s*//;
68          s/^([0-9]+(?:\.[0-9]+)?)// and return('NUM',$1);
69          s/^([A-Za-z][A-Za-z0-9_]*)// and return('VAR',$1);
70          s/^(.)// and return($1,$1);
71          s/^\s*//;
72      }
73  }
74
75  sub Run {
76      my($self)=shift;
77      return $self->YYParse( yylex => \&_Lexer, yyerror => \&_Error );
78  }
79  }; # end translation scheme

Las líneas 7-79 no hacen otra cosa que iniciar una cadena conteniendo el esquema de traducción. También podríamos haberlo escrito en un fichero y compilarlo con eyapp .

Partes de un programa eyapp

Un programa eyapp es similar en muchos aspectos a un programa eyapp / yacc y se divide en tres partes: la cabeza, el cuerpo y la cola. Cada una de las partes va separada de las otras por el símbolo %% en una línea aparte. Así, el %% de la línea 21 separa la cabeza del cuerpo. En la cabecera se colocan el código de inicialización, las declaraciones de terminales, las reglas de precedencia, etc. El cuerpo contiene las reglas de la gramática y las acciones asociadas. Por último, la cola de un program eyapp se separa del cuerpo por otro %% en una línea aparte. La cola contiene las rutinas de soporte al código que aparece en las acciones asi como, posiblemente, rutinas para el análisis léxico (subrutina _Lexer en la línea 58) y el tratamiento de errores (subrutina _Error en la línea 54). Puede encontrar una descripción de la gramática de eyapp usando su propia notación en la página [*].

Esquemas de Traducción con %metatree

Por defecto Parse::Eyapp se comporta de manera similar a eyapp y yacc generando un analizador sintáctico LALR(1) y ejecutando las acciones empotradas según una antiderivación a derechas, esto es en un recorrido del árbol de análisis sintáctico de abajo hacia arriba y de izquierda a derecha.

Mediante la directiva %metatree en la línea 15 le indicamos a Parse::Eyapp que debe generar un esquema de traducción. En tal caso, al llamar al analizador el código empotrado no es ejecutado sino que se genera un árbol de análisis sintáctico con los correspondientes nodos de código colgando del árbol en las posiciones que les corresponden.

Las reglas

Las reglas de producción de la gramática están entre las líneas 21 y 52. Cada entrada comienza con el nombre de la variable sintáctica y va seguida de las partes derechas de sus reglas de producción separadas por barras verticales. Opcionalmente se le puede dar un nombre a la regla de producción usando la directiva %name . El efecto que tiene esta directiva es bendecir - durante la fase tree construction time - el nodo del árbol sintáctico en una clase con nombre el argumento de %name (los nodos del árbol sintáctico son objetos). El código - entre llaves - puede ocupar cualquier lugar en el lado derecho.

Nombres de los atributos

En las acciones los atributos de los nodos pueden ser accedidos usando el array mágico @_. De hecho, los códigos insertados en el árbol sintáctico son convertidos en subrutinas anónimas. Así $_[0] es una referencia al nodo padre asociado con el lado izquierdo, $_[1] el asociado con el primer símbolo de la parte derecha, etc. Esta notación posicional es confusa e induce a error: si el programador cambia la regla posteriormente insertando acciones o símbolos en la parte derecha, ¡todas las apariciones de índices en el código que se refieran a nodos a la derecha del insertado deben ser modificadas!. Algo similar ocurre si decide suprimir una acción o un símbolo. Por ello Parse::Eyapp proporciona mediante la notación punto la posibilidad de hacer una copia automática con nombre del atributo: la notación exp.left indica que la variable léxica $left guardará una referencia al nodo que corresponde a esta instanciación de la variable sintáctica exp. Además Parse::Eyapp provee la variable léxica especial $ lhs donde se guarda una referencia al nodo padre. Así la regla:

                exp.left '-' exp.right
                  { $lhs->{n} = $left->{n} - $right->{n} }
equivale al siguiente código:
                 exp '-' exp
                  { 
                    my $lhs = shift; 
                    my ($left, $right) = @_[1, 3];
                    $lhs->{n} = $left->{n} - $right->{n} 
                  }
Si se desea usar el propio nombre de la variable sintáctica como nombre del atributo se usa la notación dolar. Asi la notación $exp puede considerarse una abreviación a la notación exp.exp. El código:
                $VAR '=' $exp
                  { $lhs->{n} = $sym{$VAR->{attr}}->{n} = $exp->{n} }
equivale a este otro:
                  VAR '=' exp
                  { 
                    my $lhs = shift;
                    my ($VAR, $exp) = @_[1, 3];
                    $lhs->{n} = $sym{$VAR->{attr}}->{n} = $exp->{n} 
                  }

Nombres de atributos de expresiones complejas Eyapp

Consideremos la parte derecha de la regla de producción:

program: definition<%name PROGRAM +>.program

observe los siguientes detalles:

  1. Es posible usar los símbolos menor/mayor para incidir en el hecho de que la especificación del tipo del nodo construido como nodo PROGRAM se le da a la lista no vacía de repeticiones de definition. Funciona como un paréntesis de agrupamiento y es opcional. Podríamos haber escrito:

    program: definition %name PROGRAM +.program

    pero es, sin duda, mas confuso para el lector.

  2. Si queremos darle nombre al nodo asociado con el único elemento en la parte derecha de la regla:

    program: definition %name PROGRAM +.program

    no podemos usar la notación dolar. Este código que pretende ser equivalente al anterior:

    program:
        $definition<%name PROGRAM +>
    
    produce un mensaje de error:
    nereida:~/doc/casiano/PLBOOK/PLBOOK/code> eyapp Simple4
    *Fatal* $ is allowed for identifiers only (Use dot notation instead), at line 149 at file Simple4.eyp
    
    La razón del mensaje es doble:

    La solucion: En vez del dolar deberemos usar la notación punto para darle nombre al atributo, como se ha hecho en el ejemplo.

Fases de un Esquema de Traducción

La ejecución de un esquema de traducción por Parse::Eyapp ocurre en tres tiempos.

Class Construction Time

En una primera parte - que denominaremos Class Construction Time - se analiza la gramática y se crea la clase que contendrá el analizador sintáctico. Esto se hace llamando al método de clase new_grammar el cual devuelve una cadena conteniendo información sobre las ambiguedades, conflictos y errores que pueda tener la gramática:

84  my $warnings = Parse::Eyapp->new_grammar(
85    input=>$translationscheme,
86    classname=>'main',
87    firstline => 6,
88    outputfile => 'main.pm');
89  die "$warnings\nSolve Ambiguities. See file main.output\n"  if $warnings;

El nombre de la clase o package en el que se crea el analizador se especifica mediante el argumento classname .

El argumento firstline facilita la emisión de errores y warnings indicando la línea en que comienza la cadena que contiene el esquema de traducción.

Si se especifica el argumento outputfile => filename los resultados del análisis se volcarán en los ficheros filename.pm y filename.output los cuales contienen respectivamente el código del analizador e información pormenorizada sobre las tablas usadas por el analizador y los conflictos y ambiguedades encontradas durante el estudio de la gramática.

Una vez creada la clase es posible instanciar objetos del tipo analizador llamando al constructor new de la clase creada:

90  my $parser = main->new();

Tree Construction Time

En una segunda parte - que denominaremos Tree Construction Time - se toma la entrada (usando para ello el analizador léxico y las rutinas de error proveídas por el programador) y se procede a la construcción del árbol. Las acciones especificadas por el programador en el esquema no son ejecutadas sino que se añaden al árbol como referencias a subrutinas (nodos de tipo CODE).

El programador puede influir en la construcción del árbol por medio de diversas directivas. De estas explicaremos tres:

La directiva %name class

Como se ha dicho, la directiva %name class hace que el nodo asociado con la instanciación de la regla de producción se bendiga en la clase dada por la cadena class.

La directiva %begin

La directiva %begin { ... code ...} usada en la línea 42 hace que el código usado como argumento { ... code ...} se ejecute en Tree Construction Time.

27  exp:
28              %name PLUS
29                exp.left '+'  exp.right
30                  { $lhs->{n} = $left->{n} + $right->{n} }
31          |   %name MINUS
..          .   ............................................
42          |   '(' $exp ')'  %begin { $exp }

En el ejemplo la directiva %begin { $exp } hace que nos saltemos el nodo asociado con el paréntesis enlazando directamente la raíz del árbol referenciado por $exp con el padre de la regla actual. Si no se hubiera insertado esta directiva el árbol construido para la entrada 2*(3+4) sería similar a este:

TIMES
  |-- NUM -- TERMINAL( attr => 2 )
  |-- '*'
  `-- E_7
       |-- '('
       |-- PLUS
       |    |-- NUM -- TERMINAL( attr => 3 )
       |    |-- '+'
       |    `-- NUM -- TERMINAL( attr => 4 )
       `--  ')'
El efecto de la directiva %begin { $exp } es retornar la referencia a la expresión parentizada dando lugar al siguiente árbol:
TIMES
  |-- NUM -- TERMINAL( attr => 2 )
  |-- '*'
  `-- PLUS
       |-- NUM -- TERMINAL( attr => 3 )
       |-- '+'
       `-- NUM -- TERMINAL( attr => 4 )

En general, las acciones asociadas con directivas %begin modifican la construcción del árbol sintáctico concreto para dar lugar a un árbol de análisis sintáctico abstracto adecuado a los requerimientos de las fases posteriores.

Las acciones en Tree Construction Time insertadas mediante %begin se ejecutan colaborativamente con las acciones de construcción del árbol en el orden usual de los analizadores LR: según una antiderivación a derechas, esto es, en un recorrido del árbol de análisis sintáctico de abajo hacia arriba (de las hojas hacia la raíz) y de izquierda a derecha.

Las acciones en Tree Construction Time reciben como argumentos en $_[1], $_[2], etc. las referencias a los nodos del árbol asociadas con los elementos de la parte derecha. En Tree Construction Time el argumento $_[0] es una referencia al objeto analizador sintáctico.

La segunda fase en nuestro ejemplo ocurre en las líneas 90-92 en las que leemos la entrada y llamamos al método Run el cual construye el árbol:

90  print "Write a sequence of arithmetic expressions: " if is_interactive();
91  $parser->YYData->{INPUT} = <>;
92  my $t = $parser->Run() or die "Syntax Error analyzing input";

El método Run se limita a llamar al método YYParse que es quien realiza el análisis:

74  sub Run {
75      my($self)=shift;
76      return $self->YYParse( yylex => \&_Lexer, yyerror => \&_Error );
77  }

Cuando el método YYParse proveido por Parse::Eyapp es llamado es necesario que hayan sido especificadas las correspondientes referencias a las rutinas de análisis léxico (argumento con clave yylex) y de tratamiento de errores (argumento con clave yyerror).

Despues de esta fase tenemos el árbol de análisis extendido con los nodos de tipo CODE.

Execution Time

En una tercera parte - que denominaremos Execution Time - el árbol es recorrido en orden primero-profundo y los nodos de la clase CODE son ejecutados. El árbol será modificado y decorado como consecuencia de las acciones y podremos examinar los resultados:

93  $t->translation_scheme;
94  my $treestring = Dumper($t);
95  our %sym;
96  my $symboltable = Dumper(\%sym);
97  print <<"EOR";
98  ***********Tree*************
99  $treestring
100  ******Symbol table**********
101  $symboltable
102  ************Result**********
103  $t->{n}
104
105  EOR

El método translation_scheme tiene una estructura simple y tiene un código similar a este:

sub translation_scheme {
  my $self = shift; # root of the subtree
  my @children = $self->children();
  for (@children) {
    if (ref($_) eq 'CODE') {
      $_->($self, @children);
    }
    elsif (defined($_)) {
      translation_scheme($_);
    }
  }
}
Como se ve en el código de translation_scheme la subrutina asociada se le pasan como argumentos referencias al nodo y a los hijos del nodo.

Los Terminales

Durante la fase de construcción del árbol sintáctico los nodos que corresponden a terminales o tokens de la gramática son -por defecto - bendecidos en la clase "${PREFIX} TERMINAL ". Si el programador no ha indicado lo contrario en la llamada al analizador, $PREFIX es la cadena vacía. (Véase el párrafo en la página [*] sobre el argumento yyprefix del método constructor del analizador).

Los nodos de la clase TERMINAL poseen al menos dos atributos token y attr. El atributo token indica que clase de terminal es (NUM, IDENTIFIER, etc.). El atributo attr nos da el valor semántico del terminal tal y como fué recibido del analizador léxico.

Listas y Opcionales

El fragmento del esquema de traducción entre las líneas 26 y 30:

26  line: %name PROG
27         exp <%name EXP + ';'>
28           { @{$lhs->{t}} = map { $_->{t}} ($lhs->child(0)->Children()); }
29
30  ;

expresa que el lenguaje generado por el no terminal line esta formado por secuencias no vacías de frases generadas a partir de exp separadas por puntos y comas. En concreto, el analizador generado por eyapp transforma la regla line: exp <%name EXP + ';'> en:

line:       %name EXP
              PLUS-1
;
PLUS-1:     %name _PLUS_LIST
              PLUS-1 ';'  exp
        |     exp      
;

La expresión exp <+ ';'> es tratada como un único elemento de la parte derecha y su atributo es un nodo de la clase _PLUS_LIST cuyos hijos son los elementos de la lista. Por ejemplo, para la entrada a=2; b = 2*a el analizador construye un árbol similar a este:

bless( {
  'children' => [
    bless( {              # _PLUS_LIST
    | 'children' => [
    |   bless( {          # ASSIGN a = 2
    |   | 'children' => [
    |   |   bless( { 'attr' => 'a', 'token' => 'VAR' }, 'TERMINAL' ),
    |   |   bless( { 'attr' => '=', 'token' => '=' }, 'TERMINAL' ),
    |   |   bless( {      # NUM 2
    |   |     'children' => [
    |   |       bless( { 'attr' => '2', 'token' => 'NUM' }, 'TERMINAL' ),
    |   |       sub { my $lhs = $_[0]; my $NUM = $_[1];  $lhs->{n} = $NUM->{attr}  }
    |   |     ]
    |   |   }, 'NUM' ),
    |   |   sub { my ($lhs, $exp, $VAR) = ($_[0], $_[3], $_[1]);  
    |   |         $lhs->{n} = $sym{$VAR->{attr}}->{n} = $exp->{n}  }
    |   | ]
    |   }, 'ASSIGN' ),
    |   bless( {         # ASSIGN b = 2*a
    |   | 'children' => [
    |   |   bless( { 'attr' => 'b', 'token' => 'VAR' }, 'TERMINAL' ),
    |   |   bless( { 'attr' => '=', 'token' => '=' }, 'TERMINAL' ),
    |   |   bless( {     # TIMES 2*a
    |   |     'children' => [
    |   |       bless( { .... }, 'NUM' ),
    |   |       bless( { 'attr' => '*', 'token' => '*' }, 'TERMINAL' ),
    |   |       bless( { .... }, 'VAR' ),
    |   |       sub { ... }
    |   |     ]
    |   |   }, 'TIMES' ),
    |   |   sub { ... }
    |   | ]
    |   }, 'ASSIGN' )
    | ]
    }, '_PLUS_LIST' ),
    sub { ... }
  ]
}, 'EXP' )

Observe que, por defecto, los nodos punto y coma (;) son eliminados del nodo lista de hijos del nodo _PLUS_LIST. Por defecto, en los nodos creados por Parse::Eyapp desde listas declaradas mediante operadores de brackets (por ejemplo St <+ ';'> o ID <* ','>) se elimina el separador si este fué definido mediante una cadena (uso de apostrofes).

Diremos que un terminal es un terminal sintáctico o syntax token si fue definido en el programa eyapp mediante una cadena delimitada por apóstrofes.

Si queremos cambiar el estatus de un syntax token, por ejemplo si queremos que el separador ';' del ejemplo forme parte de la lista deberemos añadir a la cabecera la declaración %semantic token ';'.

Si creamos una nueva versión de nuestro programa trans_scheme_simple3.pl añadiendo esta declaración:

%semantic token ';'
%right   '='
....
Las listas contendran los puntos y comas. En tal caso, la línea 24 dará lugar a un error9.1ya que los nodos punto y coma carecen del atributo n:
24                  { $lhs->{n} = [ map { $_->{n}} $_[1]->Children() ]; }

En efecto:

nereida:~/src/perl/YappWithDefaultAction/examples> trans_scheme_simple3.pl > salida
a=2*3; b = a+1; c = a-b
Use of uninitialized value in join or string at trans_scheme_simple3.pl line 99, <> line 1.
Use of uninitialized value in join or string at trans_scheme_simple3.pl line 99, <> line 1.
Al usar la declaración %semantic token la nueva estructura del árbol es:
bless( {
  'n' => [ 6, undef, 7, undef, -1 ],
  'children' => [
    bless( {
      'children' => [
        bless( { 'n' => 6, ................  ] }, 'ASSIGN' ),
        bless( { 'children' => [], 'attr' => ';', 'token' => ';' }, 'TERMINAL' ),
        bless( { 'n' => 7, ................  }, 'ASSIGN' ),
        bless( { 'children' => [], 'attr' => ';', 'token' => ';' }, 'TERMINAL' ),
        bless( { 'n' => -1, ................  }, 'ASSIGN' )
      ]
    }, '_PLUS_LIST' ),
    sub { "DUMMY" }
  ]
}, 'EXP' )
Parse::Eyapp extiende Parse::Yapp con listas vacías y no vacías usando los operadores *, +:

La regla:

                          A : B C * 'd'
es equivalente a:

                          A : B L 'd' 
                          L : /* vacío */
                            | P
                          P : C P
                            | C

Es posible especificar la presencia de símbolos opcionales usando ?.

Observe que el operador de concatenación tiene menor prioridad que los operadores de listas, esto es la expresión AB* es interpretada como A(B*).

Una secuencia de símbolos en la parte derecha de una regla de producción puede ser agrupada mediante el uso de paréntesis. Al agrupar una secuencia se crea una variable sintáctica intermedia que produce dicha secuencia. Por ejemplo, la regla:

                    A : B (C { dosomething(@_) })? D

es equivalente a:

                    A  : B T1 D 
                    T1 :  /* vacío */
                       | T2
                    T2 : C { dosomething(@_) }

Ambiguedades

Hay numerosas ambiguedades en la gramática asociada con el esquema de traducción presentado en la página [*]. Las ambiguedades se resuelven exactamente igual que en yacc usando directivas en la cabecera o primera parte que indiquen como resolverlas.

Entre las ambiguedades presentes en la gramática del ejemplo estan las siguientes:

La rutina de Tratamiento de Errores

Recuerde que la fase de análisis sintáctico y léxico de la entrada ocurre en Tree Construction Time. En consecuencia el primer argumento que recibe el método _Error (líneas 53-59) cuando es llamado por el analizador sintáctico es una referencia al objeto analizador sintáctico. Dicho objeto dispone de un conjunto de métodos, muchos de los cuales ya existían en Parse::Yapp. Entre estos últimos se encuentra el método YYCurval que es llamado en la línea 55 y que devuelve el terminal/token que estaba siendo analizado en el momento en el que se produjo el error. Si dicho token no está definido es que hemos alcanzado el final del fichero (línea 56).

54  sub _Error {
55    my($token)=$_[0]->YYCurval;
56    my($what)= $token ? "input: '$token'" : "end of input";
57
58    die "Syntax error near $what.\n";
59  }

Otros métodos que pueden ser de ayuda en el diagnóstico de errores son YYCurval que devuelve el atributo del token actual y YYExpect que devuelve una lista con los terminales esperados en el momento en el que se produjo el error.

El Analizador Léxico

El analizador léxico esta tomado de los ejemplos que acompañan a Parse::Yapp. Se supone que la entrada se ha dejado dentro del objeto analizador en $parser->YYData->{INPUT}. Recuerde que el análisis léxico de la entrada ocurre en Tree Construction Time. En consecuencia el primer argumento que recibe _Lexer cuando es llamado por el analizador sintáctico es la referencia al objeto analizador sintáctico. De ahí que lo primero que se hace, en la línea 59, sea crear en $parser una variable léxica que referencia dicho objeto.

58  sub _Lexer {
59      my($parser)=shift;
60
61          $parser->YYData->{INPUT}
62      or  return('',undef);
63
64      $parser->YYData->{INPUT}=~s/^\s*//;
65
66      for ($parser->YYData->{INPUT}) {
67          s/^([0-9]+(?:\.[0-9]+)?)// and return('NUM',$1);
68          s/^([A-Za-z][A-Za-z0-9_]*)// and return('VAR',$1);
69          s/^(.)// and return($1,$1);
70          s/^\s*//;
71      }
72  }

Ejercicio 9.2.3   ¿Cuantos elementos tiene la lista sobre la que se hace el bucle for de la línea 66?

Obsérvese el falso bucle for en la línea 66. Es un truco que constituye una de esas frases hechas o idioms que aunque la primera vez resultan extrañas, a fuerza de verlas repetidas se convierten en familiares.

El bucle de hecho se ejecutará una sóla vez en cada llamada a _Lexer. El objetivo es evitar las costosas indirecciones a las que obliga almacenar la entrada en $parser->YYData->{INPUT}. Para ello se aprovecha la capacidad del bucle for sin índice de crear en $_ un alias del elemento visitado en la iteración.

Ejercicio 9.2.4  
  1. ¿Puedo cambiar el binding de la línea 64 por uno sobre $_ dentro del falso for? ¿Ganamos algo con ello?

  2. ¿Puedo cambiar la comprobación en las líneas 61-62 por una primera línea dentro del falso for que diga $_ or return('',undef);?

  3. ¿Cuántas veces se ejecuta el falso bucle si $parser->YYData->{INPUT} contiene la cadena vacía?

  4. ¿Que ocurrirá en las líneas 61-62 si $parser->YYData->{INPUT} contiene sólamente la cadena '0'?

Acciones por Defecto

En el ejemplo anterior la acción es asociada con los nodos PLUS, MINUS, TIMES y DIV es similar. Parse::Eyapp proporciona una directiva % defaultaction la cual permite especificar la acción por defecto. Esta acción es asociada con las reglas que no tienen una acción asociada explícita. El siguiente ejemplo muestra su uso:

nereida:~/doc/casiano/PLBOOK/PLBOOK/code> cat -n trans_scheme_default_action.pl
 1  #!/usr/bin/perl
 2  use strict;
 3  use warnings;
 4  use Data::Dumper;
 5  use Parse::Eyapp;
 6  use IO::Interactive qw(interactive);
 7
 8  my $translationscheme = q{
 9    %{
10    # head code is available at tree construction time
11    use Data::Dumper;
12
13    our %sym; # symbol table
14    %}
15
16    %defaultaction { $lhs->{n} = eval " $left->{n} $_[2]->{attr} $right->{n} " }
17
18    %metatree
19
20    %right   '='
21    %left   '-' '+'
22    %left   '*' '/'
23
24    %%
25    line:       %name EXP
26                  exp <+ ';'> /* Expressions separated by semicolons */
27                    { $lhs->{n} = $_[1]->Last_child->{n} }
28    ;
29
30    exp:
31                %name PLUS
32                  exp.left '+' exp.right
33            |   %name MINUS
34                  exp.left '-' exp.right
35            |   %name TIMES
36                  exp.left '*' exp.right
37            |   %name DIV
38                  exp.left '/' exp.right
39            |   %name NUM   $NUM
40                    { $lhs->{n} = $NUM->{attr} }
41            |   '(' $exp ')'  %begin { $exp }
42            |   %name VAR
43                  $VAR
44                    { $lhs->{n} = $sym{$VAR->{attr}}->{n} }
45            |   %name ASSIGN
46                  $VAR '=' $exp
47                    { $lhs->{n} = $sym{$VAR->{attr}}->{n} = $exp->{n} }
48
49    ;
50
51    %%
52    sub Error {
53      die "Syntax error near ".($_[0]->YYCurval?$_[0]->YYCurval:"end of file")."\n";
54    }
55
56    sub Lexer {
57      my($parser)=shift;
58
59      for ($parser->YYData->{INPUT}) {
60        s/^\s*//;
61        $_ eq '' and  return('',undef);
62        s/^([0-9]+(?:\.[0-9]+)?)// and return('NUM',$1);
63        s/^([A-Za-z][A-Za-z0-9_]*)// and return('VAR',$1);
64        s/^(.)// and return($1,$1);
65      }
66    }
67  }; # end translation scheme
68
69  $Data::Dumper::Indent = 1;
70  $Data::Dumper::Terse = 1;
71  $Data::Dumper::Deepcopy  = 1;
72  my $warnings = Parse::Eyapp->new_grammar(
73    input=>$translationscheme,
74    classname=>'Calc',
75    firstline => 6,
76    outputfile => 'Calc.pm');
77  die "$warnings\nSolve Ambiguities. See file main.output\n"  if $warnings;
78  my $parser = Calc->new();
79  print {interactive} "Write a sequence of arithmetic expressions: ";
80  $parser->YYData->{INPUT} = <>;
81  my $t = $parser->YYParse( yylex => \&Calc::Lexer, yyerror => \&Calc::Error );
82  $t->translation_scheme;
83  my $treestring = Dumper($t);
84  my $symboltable;
85  {
86    no warnings;
87    $symboltable = Dumper(\%Calc::sym);
88  }
89  print <<"EOR";
90  ***********Tree*************
91  $treestring
92  ******Symbol table**********
93  $symboltable
94  ************Result**********
95  $t->{n}
96
97  EOR

El método Last_child usado en la línea 27 devuelve una referencia al último hijo no código del nodo. Al ser $_[1] un nodo de tipo '_PLUS_LIST' queda garantizado que el último hijo no es una referencia a una subrutina asi que podría haberse usado el método last_child el cual devuelve el último hijo del nodo, sea este código o no.

La línea 86 tiene por efecto desactivar los avisos. De otra manera se produciría un warning con respecto al uso único de la variable %Calc::sym:

nereida:~/doc/casiano/PLBOOK/PLBOOK/code> echo "a=2*3; b=a+1" | trans_scheme_default_action.pl
Name "Calc::sym" used only once: possible typo at trans_scheme_default_action.pl line 85.
***********Tree*************
bless( {
  'n' => 7,
  'children' => [
    ............
  ]
}, 'EXP' )

******Symbol table**********
{
  'a' => { 'n' => 6 },
  'b' => { 'n' => 7 }
}

************Result**********
7

Un Esquema de Traducción para las Declaraciones de Variables

En el siguiente ejemplo se muestra la implementación en eyapp del ejemplo 4.7.1. El código es similar salvo por la presencia de flechas de referenciado:

nereida:~/src/perl/YappWithDefaultAction/examples> cat -n trans_scheme_simple_decls2.pl
 1  #!/usr/bin/perl -w
 2  use strict;
 3  use Data::Dumper;
 4  use Parse::Eyapp;
 5  our %s; # symbol table
 6
 7  my $ts = q{
 8    %token FLOAT INTEGER NAME
 9
10    %{
11    our %s;
12    %}
13
14    %metatree
15
16    %%
17    Dl:  D <* ';'>
18    ;
19
20    D : $T { $L->{t} = $T->{t} } $L
21    ;
22
23    T : FLOAT    { $lhs->{t} = "FLOAT" }
24      | INTEGER  { $lhs->{t} = "INTEGER" }
25    ;
26
27    L : $NAME
28          { $NAME->{t} = $lhs->{t}; $s{$NAME->{attr}} = $NAME }
29      | $NAME { $NAME->{t} = $lhs->{t}; $L->{t} = $lhs->{t} } ',' $L
30          { $s{$NAME->{attr}} = $NAME }
31    ;
32    %%
33  };
34
35  sub Error { die "Error sintáctico\n"; }
36
37  { # Closure of $input, %reserved_words and $validchars
38    my $input = "";
39    my %reserved_words = ();
40    my $validchars = "";
41
42    sub parametrize__scanner {
43      $input = shift;
44      %reserved_words = %{shift()};
45      $validchars = shift;
46    }
47
48    sub scanner {
49      $input =~ m{\G\s+}gc;                     # skip whites
50      if ($input =~ m{\G([a-z_A_Z]\w*)\b}gc) {
51        my $w = uc($1);                 # upper case the word
52        return ($w, $w) if exists $reserved_words{$w};
53        return ('NAME', $1);            # not a reserved word
54      }
55      return ($1, $1) if ($input =~ m/\G([$validchars])/gc);
56      die "Caracter invalido: $1\n" if ($input =~ m/\G(\S)/gc);
57      return ('', undef); # end of file
58    }
59  } # end closure
60
61  Parse::Eyapp->new_grammar(input=>$ts, classname=>'main', outputfile=>'Types.pm');
62  my $parser = main->new(yylex => \&scanner, yyerror => \&Error); # Create the parser
63
64  parametrize__scanner(
65    "float x,y;\ninteger a,b\n",
66    { INTEGER => 'INTEGER', FLOAT => 'FLOAT'},
67    ",;"
68  );
69
70  my $t = $parser->YYParse() or die "Syntax Error analyzing input";
71
72  $t->translation_scheme;
73
74  $Data::Dumper::Indent = 1;
75  $Data::Dumper::Terse = 1;
76  $Data::Dumper::Deepcopy  = 1;
77  $Data::Dumper::Deparse = 1;
78  print Dumper($t);
79  print Dumper(\%s);
Al ejecutarlo con la entrada "float x,y;\ninteger a,b\n" los contenidos finales del arbol son:
nereida:~/src/perl/YappWithDefaultAction/examples> trans_scheme_simple_decls2.pl
bless({'children'=>[
   bless({'children'=>[
   |   bless({'children'=>[
   |   |   bless({'children'=>[
   |   |   |   bless({'children'=>[],'attr'=>'FLOAT','token'=>'FLOAT'},'TERMINAL'),
   |   |   |   sub {use strict 'refs'; my $lhs=$_[0]; $$lhs{'t'}='FLOAT'; }
   |   |   | ],
   |   |   | 't'=>'FLOAT'
   |   |   },'T_8'),       # T -> FLOAT
   |   |   sub { ... },
   |   |   bless({'children'=>[
   |   |   |   bless({'children'=>[],'attr'=>'x','token'=>'NAME','t'=>'FLOAT'},'TERMINAL'),
   |   |   |   sub{ ... },
   |   |   |   bless({'children'=>[],'attr'=>',','token'=>','},'TERMINAL'),
   |   |   |   bless({'children'=>[
   |   |   |   |   bless({'children'=>[],'attr'=>'y','token'=>'NAME','t'=>'FLOAT'},
   |   |   |   |         'TERMINAL'),
   |   |   |   |   sub{ ... }
   |   |   |   | ],
   |   |   |   | 't'=>'FLOAT'
   |   |   |   },'L_10'), # L -> NAME
   |   |   |   sub{ ... }
   |   |   | ],
   |   |   | 't'=>'FLOAT'
   |   |   },'L_11'),     # L -> NAME ',' L 
   |   |   undef
   |   | ]
   |   },'D_6'),          # D -> T L
   |   bless({ 
   |    ... # tree for integer a, b
   |   },'D_6')           # D -> T L
   | ]
   },'_STAR_LIST_1'),
 ]
},'Dl_5')   # Dl : D <* ';'> equivale a: Dl : /* empty */ | S_2; S_2: S_1; S_1: S_1 ';' D | D
Los contenidos de la tabla de símbolos %s quedan como sigue:
{
 'y'=>bless({'children'=>[],'attr'=>'y','token'=>'NAME','t'=>'FLOAT'},'TERMINAL'),
 'a'=>bless({'children'=>[],'attr'=>'a','token'=>'NAME','t'=>'INTEGER'},'TERMINAL'),
 'b'=>bless({'children'=>[],'attr'=>'b','token'=>'NAME','t'=>'INTEGER'},'TERMINAL'),
 'x'=>bless({'children'=>[],'attr'=>'x','token'=>'NAME','t'=>'FLOAT'},'TERMINAL')
}

Prefijos

Como se ha mencionado, durante la fase Tree Construction los nodos son bendecidos en el nombre de la regla de producción. El nombre de una regla de producción es, por defecto, la concatenación de la variable en el lado izquierdo (LHS) con el número de orden de la regla. Es posible modificar el nombre por defecto usando la directiva %name .

Si se desean evitar posibles colisiones con clases existentes es posible prefijar todos los nombres de las clases con un prefijo dado usando el parámetro yyprefix en la llamada al constructor del analizador:

my $warnings = Parse::Eyapp->new_grammar(
  input=>$translationscheme,
  classname=>'main',
  firstline => 6,
  outputfile => 'main.pm');
die "$warnings\nSolve Ambiguities. See file main.output\n"  if $warnings;

# Prefix all the classes with 'Calc::'
my $parser = main->new(yyprefix => 'Calc::');
El resultado de esta llamada a new es que las clases de los nodos quedan prefijadas con Calc::. Por ejemplo el árbol creado para la frase a=1 será:
bless( { 'children' => [
    bless( { 'children' => [
        bless( { 'children' => [
            bless( { 'children' => [], 'attr' => 'a', 'token' => 'VAR' }, 'Calc::TERMINAL' ),
            bless( { 'children' => [], 'attr' => '=', 'token' => '=' }, 'Calc::TERMINAL' ),
            bless( { 'children' => [
                bless( { 'children' => [], 'attr' => '1', 'token' => 'NUM' }, 'Calc::TERMINAL' ),
              ]
            }, 'Calc::NUM' ),
          ]
        }, 'Calc::ASSIGN' )
      ]
    }, 'Calc::_PLUS_LIST' ),
  ]
}, 'Calc::EXP' )

Modo Standalone

Es mas eficiente aislar el código del esquema de traducción en un fichero (se asume por defecto el tipo .eyp) y generar el módulo que contiene el código del analizador usando el guión eyapp .

El siguiente ejemplo muestra un ejemplo de compilación separada. El esquema de traducción convierte expresiones en infijo a postfijo. De un lado tenemos el fichero TSPostfix2.eyp conteniendo el esquema:

nereida:~/src/perl/YappWithDefaultAction/examples> cat -n TSPostfix2.eyp
 1  # File TSPostfix2.eyp
 2  %right  '='
 3  %left   '-' '+'
 4  %left   '*' '/'
 5  %left   NEG
 6
 7  %{
 8    use Data::Dumper;
 9    $Data::Dumper::Indent = 1;
10    $Data::Dumper::Deepcopy = 1;
11    #$Data::Dumper::Deparse = 1;
12    use IO::Interactive qw(interactive);
13  %}
14
15  %metatree
16
17  %defaultaction {
18    if (@_==4) { # binary operations: 4 = lhs, left, operand, right
19      $lhs->{t} = "$_[1]->{t} $_[3]->{t} $_[2]->{attr}";
20      return
21    }
22    die "Fatal Error. Unexpected input\n".Dumper(@_);
23  }
24
25  %%
26  line: %name PROG
27         exp <%name EXP + ';'>
28           { @{$lhs->{t}} = map { $_->{t}} ($lhs->child(0)->Children()); }
29
30  ;
31
32  exp:        NUM         { $lhs->{t} = $_[1]->{attr}; }
33          |   VAR         { $lhs->{t} = $_[1]->{attr}; }
34          |   VAR '=' exp { $lhs->{t} = "$_[1]->{attr} $_[3]->{t} =" }
35          |   exp '+' exp
36          |   exp '-' exp
37          |   exp '*' exp
38          |   exp '/' exp
39          |   '-' exp %prec NEG { $_[0]->{t} = "$_[2]->{t} NEG" }
40          |   '(' exp ')' %begin { $_[2] }
41  ;
42
43  %%
44
45  sub _Error {
46      my($token)=$_[0]->YYCurval;
47
48      my($what)= $token ? "input: '$token'" : "end of input";
49      die "Syntax error near $what.\n";
50  }
51
52  my $x; # Used for input
53
54  sub _Lexer {
55      my($parser)=shift;
56
57      $x =~ s/^\s+//;
58      return('',undef) if $x eq '';
59
60
61      $x =~ s/^([0-9]+(?:\.[0-9]+)?)//   and return('NUM',$1);
62      $x =~ s/^([A-Za-z][A-Za-z0-9_]*)// and return('VAR',$1);
63      $x =~ s/^(.)//s                    and return($1,$1);
64  }
65
66  sub Run {
67      my($self)=shift;
68      $x = <>;
69      my $tree = $self->YYParse( yylex => \&_Lexer, yyerror => \&_Error,
70        #yydebug => 0xFF
71      );
72
73      print Dumper($tree);
74      $tree->translation_scheme();
75      print Dumper($tree);
76      {
77        local $" = ";";
78        print "Translation:\n@{$tree->{t}}\n";
79      }
80  }
Observe el uso del método Children - con C mayúscula - en la línea 28: devuelve los hijos del nodo no incluyendo las referencias a subrutinas. A diferencia de su homólogo con c minúscula children el cual devuelve todos los hijos del nodo, incluyendo las referencias al código empotrado.

Compilamos con eyapp:

nereida:~/src/perl/YappWithDefaultAction/examples> eyapp TSPostfix2
nereida:~/src/perl/YappWithDefaultAction/examples> ls -ltr | tail -2
-rw-r-----  1 pl users   1781 2006-10-30 13:08 TSPostfix2.eyp
-rw-r--r--  1 pl users   7611 2006-10-30 13:12 TSPostfix2.pm

De otro lado tenemos el programa cliente el cual se limita a cargar el módulo y llamar al método Run:

nereida:~/src/perl/YappWithDefaultAction/examples> cat -n usetspostfix2.pl
     1  #!/usr/bin/perl -w
     2  use strict;
     3  use TSPostfix2;
     4
     5  my $parser = new TSPostfix2();
     6  $parser->Run;
Al ejecutar el programa se produce una salida similar a esta (la salida ha sido editada para darle mayor claridad):

nereida:~/src/perl/YappWithDefaultAction/examples> usetspostfix2.pl
 1  a=2
 2  ...
 3  $VAR1 = bless( { 'children' => [
 4      bless( { 'children' => [
 5      |   bless( { 'children' => [
 6      |   |   bless( { 'children' => [], 'attr' => 'a', 'token' => 'VAR' }, 'TERMINAL' ),
 7      |   |   bless( { 'children' => [], 'attr' => '=', 'token' => '=' }, 'TERMINAL' ),
 8      |   |   bless( { 'children' => [
 9      |   |       bless( { 'children' => [], 'attr' => '2', 'token' => 'NUM' }, 'TERMINAL' ),
10      |   |       sub { "DUMMY" }
11      |   |     ],
12      |   |     't' => '2'
13      |   |   }, 'exp_4' ),
14      |   |   sub { "DUMMY" }
15      |   | ],
16      |   | 't' => 'a 2 ='
17      |   }, 'exp_6' )
18      | ]
19      }, 'EXP' ),
20      sub { "DUMMY" }
21    ],
22    't' => [ 'a 2 =' ]
23  }, 'PROG' );
24  Translation:
25  a 2 =

Como puede verse en la salida, cuando no se especifica el nombre del nodo asociado con la regla de producción se genera un nombre por defecto que consiste en la concatenación del nombre de la variable sintáctica en el lado izquierdo y el número de orden de la regla de producción. Así el nodo descrito en las líneas 5-17 tiene por nombre exp_6 indicando que corresponde a la sexta regla de producción de exp.

El nodo en las líneas 4-19 tiene por nombre EXP. Su nombre le fué dado mediante la directiva %name en la línea

27         exp <%name EXP + ';'>
Es posible insertar una directiva %name en una lista usando esta sintáxis.

Nótese también que si hubieramos usado la opción Data::Dumper::Deparse (línea 11) podríamos hacer que Data::Dumper nos informe no sólo de la presencia de código sino que nos muestre el código fuente que ocupa esa posición.



Subsecciones
next up previous contents index PLPL moodlepserratamodulosperlmonksperldocapuntes LHPgoogleetsiiullpcgull
Sig: Definición Dirigida por la Sup: Análisis Semántico con Parse::Eyapp Ant: Esquemas de Traducción: Conceptos Err: Si hallas una errata ...
Casiano Rodríguez León
2012-05-22