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.