El Analizador Ascendente Parse::Yapp

El program yapp es un traductor y, por tanto, constituye un ejemplo de como escribir un traductor. El lenguaje fuente es el lenguaje yacc y el lenguaje objeto es Perl. Como es habitual en muchos lenguajes, el lenguaje objeto se ve "expandido" con un conjunto de funciones de soporte. En el caso de yapp estas funciones de soporte, son en realidad métodos y están en el módulo Parse::Yapp::Driver. Cualquier módulo generado por yapp hereda de dicho módulo (véase por ejemplo, el módulo generado para nuestro ejemplo de la calculadora, en la sección 35.4).

Como se ve en la figura 35.3, los módulos generados por yapp heredan y usan la clase Parse::Yapp::Driver la cual contiene el analizador sintáctico LR genérico. Este módulo contiene los métodos de soporte visibles al usuario YYParse, YYData, YYErrok, YYSemval, etc.

La figura 35.3 muestra además el resto de los módulos que conforman el ``compilador'' Parse::Yapp. La herencia se ha representado mediante flechas contínuas. Las flechas punteadas indican una relación de uso entre los módulos. El guión yapp es un programa aparte que es usado para producir el correspondiente módulo desde el fichero conteniendo la gramática.

Figura: Esquema de herencia de Parse::Yapp. Las flechas contínuas indican herencia, las punteadas uso. La clase Calc es implementada en el módulo generado por yapp

(Para ver el contenido de los módulos, descarge yapp desde CPAN: http://search.cpan.org/~fdesar/Parse-Yapp-1.05/lib/Parse/Yapp.pm o bien desde uno de nuestros servidores locales; en el mismo directorio en que se guarda la versión HTML de estos apuntes encontrará una copia de Parse-Yapp-1.05.tar.gz). La versión a la que se refiere este capítulo es la 1.05.

El módulo Parse/Yapp/Yapp.pm se limita a contener la documentación y descansa toda la tarea de análisis en los otros módulos. El módulo Parse/Yapp/Output.pm contiene los métodos _CopyDriver y Output los cuales se encargan de escribir el analizador: partiendo de un esqueleto genérico rellenan las partes específicas a partir de la información computada por los otros módulos.

El módulo Parse/Yapp/Options.pm analiza las opciones de entrada. El módulo Parse/Yapp/Lalr.pm calcula las tablas de análisis LALR. Por último el módulo Parse/Yapp/Grammar contiene varios métodos de soporte para el tratamiento de la gramática.

El modulo Parse::Yapp::Driver contiene el método YYparse encargado del análisis. En realidad, el método YYparse delega en el método privado _Parse la tarea de análisis. Esta es la estructura del analizador genérico usado por yapp. Léalo con cuidado y compare con la estructura explicada en la sección 35.5.

 1 sub _Parse {
 2   my($self)=shift;
 3 
 4   my($rules,$states,$lex,$error)
 5      = @$self{ 'RULES', 'STATES', 'LEX', 'ERROR' };
 6   my($errstatus,$nberror,$token,$value,$stack,$check,$dotpos)
 7      = @$self{ 'ERRST', 'NBERR', 'TOKEN', 'VALUE', 'STACK', 'CHECK', 'DOTPOS' };
 8 
 9   $$errstatus=0;
10   $$nberror=0;
11   ($$token,$$value)=(undef,undef);
12   @$stack=( [ 0, undef ] ); # push estado 0
13   $$check='';

La componente 0 de @$stack es el estado, la componente 1 es el atributo.

14 
15   while(1) { 
16     my($actions,$act,$stateno);
17 
18     $stateno=$$stack[-1][0];     # sacar el estado en el top de 
19     $actions=$$states[$stateno]; # la pila

$states es una referencia a un vector. Cada entrada $$states[$stateno] es una referencia a un hash que contiene dos claves. La clave ACTIONS contiene las acciones para ese estado. La clave GOTOS contiene los saltos correspondientes a ese estado.

20 
21     if  (exists($$actions{ACTIONS})) {
22       defined($$token) or do {
23         ($$token,$$value)=&$lex($self); # leer siguiente token
24       };
25 
26       # guardar en $act la acción asociada con el estado y el token
27       $act = exists($$actions{ACTIONS}{$$token})?   
28          $$actions{ACTIONS}{$$token} : 
29          exists($$actions{DEFAULT})? $$actions{DEFAULT} : undef;
30     }
31     else { $act=$$actions{DEFAULT}; }

La entrada DEFAULT de una acción contiene la acción a ejecutar por defecto.

32 
33     defined($act) and do {
34       $act > 0 and do { # $act >0 indica shift
35          $$errstatus and do { --$$errstatus; };

La línea 35 esta relacionada con la recuperación de errores. Cuando yapp ha podido desplazar varios terminales sin que se produzca error considerará que se ha recuperado con éxito del último error.

36          # Transitar: guardar (estado, valor)
37          push(@$stack,[ $act, $$value ]);
38          $$token ne ''   #Don't eat the eof
39          and $$token=$$value=undef;
40          next; # siguiente iteración
41       };

A menos que se trate del final de fichero, se reinicializa la pareja ($$token, $$value) y se repite el bucle de análisis. Si $act es negativo se trata de una reducción y la entrada $$rules[-$act] es una referencia a un vector con tres elementos: la variable sintáctica, la longitud de la parte derecha y el código asociado:

43       # $act < 0, indica reduce
44       my($lhs,$len,$code,@sempar,$semval);
45 
46       #obtenemos una referencia a la variable,
47       #longitud de la parte derecha, referencia
48       #a la acción
49       ($lhs,$len,$code)=@{$$rules[-$act]};
50       $act or $self->YYAccept();

Si $act es cero indica una acción de aceptación. El método YYAccept se encuentra en Driver.pm. Simplemente contiene:

              sub YYAccept {
                my($self)=shift;

                ${$$self{CHECK}}='ACCEPT';
                  undef;
              }

Esta entrada será comprobada al final de la iteración para comprobar la condición de aceptación (a través de la variable $check, la cuál es una referencia).

51       $$dotpos=$len; # dotpos es la longitud de la regla
52       unpack('A1',$lhs) eq '@'    #In line rule
53       and do {
54         $lhs =~ /^\@[0-9]+\-([0-9]+)$/
55           or  die "In line rule name '$lhs' ill formed: ".
56                   "report it as a BUG.\n";
57         $$dotpos = $1;
58       };

En la línea 52 obtenemos el primer carácter en el nombre de la variable. Las acciones intermedias en yapp producen una variable auxiliar que comienza por @ y casa con el patrón especificado en la línea 54. Obsérvese que el número después del guión contiene la posición relativa en la regla de la acción intermedia.

60       @sempar = $$dotpos ?   
61          map { $$_[1] } @$stack[ -$$dotpos .. -1 ] : ();

El array @sempar se inicia a la lista vacía si $len es nulo. En caso contrario contiene la lista de los atributos de los últimos $$dotpos elementos referenciados en la pila. Si la regla es intermedia estamos haciendo referencia a los atributos de los símbolos a su izquierda.

62       $semval = $code ? &$code( $self, @sempar ) : 
63                         @sempar ? $sempar[0] : undef;

Es en este punto que ocurre la ejecución de la acción. La subrutina referenciada por $code es llamada con primer argumento la referencia al objeto analizador $self y como argumentos los atributos que se han computado previamente en @sempar. Si no existe tal código se devuelve el atributo del primer elemento, si es que existe un tal primer elemento.

El valor retornado por la subrutina/acción asociada es guardado en $semval.

65       splice(@$stack,-$len,$len);

La función splice toma en general cuatro argumentos: el array a modificar, el ındice en el cual es modificado, el número de elementos a suprimir y la lista de elementos extra a insertar. Aquí, la llamada a splice cambia los elementos de @$stack a partir del índice -$len. El número de elementos a suprimir es $len. A continuación se comprueba si hay que terminar, bien porque se ha llegado al estado de aceptación ($$check eq 'ACCEPT') o porque ha habido un error fatal:

      $$check eq 'ACCEPT' and do { return($semval); };
      $$check eq 'ABORT' and  do { return(undef); };

Si las cosas van bien, se empuja en la cima de la pila el estado resultante de transitar desde el estado en la cima con la variable sintáctica en el lado izquierdo:

      $$check eq 'ERROR' or  do { 
          push(@$stack, [ $$states[$$stack[-1][0]]{GOTOS}{$lhs}, $semval ]);
          $$check='';
          next;
      };

La expresión $$states[$$stack[-1][0]] es una referencia a un hash cuya clave GOTOS contiene una referencia a un hash conteniendo la tabla de transiciones del éstado en la cima de la pila ($stack[-1][0]). La entrada de clave $lhs contiene el estado al que se transita al ver la variable sintáctica de la izquierda de la regla de producción. El atributo asociado es el devuelto por la acción: $semval.

      $$check='';

    }; # fin de defined($act)

    # Manejo de errores: código suprimido
    ... 

  }
}#_Parse

... y el bucle while(1) de la línea 15 continúa. Compare este código con el seudo-código introducido en la sección 35.5.