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 7.4).
Como se ve en la figura 7.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 7.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.
(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 8.25.
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 8.25.