Los operadores de listas *
, +
y ?
pueden
usarse en las partes derechas de las reglas de producción para indicar
repeticiones8.1.
La gramática:
pl@nereida:~/LEyapp/examples$ head -12 List3.yp | cat -n 1 # List3.yp 2 %semantic token 'c' 3 %{ 4 use Data::Dumper; 5 %} 6 %% 7 S: 'c'+ 'd'+ 8 { 9 print Dumper($_[1]); 10 print Dumper($_[2]); 11 } 12 ;Es equivalente a:
pl@nereida:~/LEyapp/examples$ eyapp -v List3.yp | head -9 List3.output Rules: ------ 0: $start -> S $end 1: PLUS-1 -> PLUS-1 'c' 2: PLUS-1 -> 'c' 3: PLUS-2 -> PLUS-2 'd' 4: PLUS-2 -> 'd' 5: S -> PLUS-1 PLUS-2La acción semántica asociada con un operador de lista
+
retorna una
lista con los atributos de los factores a los que afecta el +
:
pl@nereida:~/LEyapp/examples$ use_list3.pl ccdd $VAR1 = [ 'c', 'c' ]; $VAR1 = [ 'd', 'd' ];
Si se activado una de las directivas de creación de árbol (%tree
o %metatree
)
o bien se ha hecho uso explícito del método YYBuildingTree
o se pasa la
opción yybuildingtree
de YYParse
la semántica de la acción
asociada cambia.
En tal caso la acción semántica asociada con un operador de lista +
es crear un nodo
con la etiqueta
_PLUS_LIST_#number
cuyos hijos son los elementos
de la lista. El número es el número de orden de la regla tal y como
aparece en el fichero .output
. Como ocurre cuando se trabaja bajo la
directiva %tree
, es necesario que los atributos de los
símbolos sean terminales semánticos
o referencias para que se incluyan en la lista.
Al ejecutar el programa anterior bajo la directiva %tree
se obtiene la salida:
pl@nereida:~/LEyapp/examples$ head -3 List3.yp; eyapp List3.yp # List3.yp %semantic token 'c' %tree pl@nereida:~/LEyapp/examples$ use_list3.pl ccdd $VAR1 = bless( { 'children' => [ bless( { 'children' => [], 'attr' => 'c', 'token' => 'c' }, 'TERMINAL' ), bless( { 'children' => [], 'attr' => 'c', 'token' => 'c' }, 'TERMINAL' ) ] }, '_PLUS_LIST_1' ); $VAR1 = bless( { 'children' => [] }, '_PLUS_LIST_2' );
El nodo asociado con la lista de d
s aparece vacío por que el terminal
'd'
no fué declarado semántico.
Cuando se trabaja con listas bajo la directiva %tree
la acción por defecto es el ''aplanamiento'' de los nodos
a los que se aplica el operador +
en una sóla lista.
En el ejemplo anterior los nodos 'd'
no aparecen pues
'd'
es un token sintáctico. Sin embargo, puede que no
sea suficiente declarar 'd'
como semántico.
Cuando se construye el árbol, el algoritmo de construcción de nodos asociados con las listas omite cualquier atributo que no sea una referencia. Por tanto, es necesario garantizar que el atributo asociado con el símbolo sea una referencia (o un token semántico) para asegurar su presencia en la lista de hijos del nodo.
pl@nereida:~/LEyapp/examples$ head -19 ListWithRefs1.eyp | cat -n 1 # ListWithRefs.eyp 2 %semantic token 'c' 'd' 3 %{ 4 use Data::Dumper; 5 %} 6 %% 7 S: 'c'+ D+ 8 { 9 print Dumper($_[1]); 10 print $_[1]->str."\n"; 11 print Dumper($_[2]); 12 print $_[2]->str."\n"; 13 } 14 ; 15 16 D: 'd' 17 ; 18 19 %%Para activar el modo de construcción de nodos usamos la opción
yybuildingtree
de YYParse
:
pl@nereida:~/LEyapp/examples$ tail -7 ListWithRefs1.eyp | cat -n 1 sub Run { 2 my($self)=shift; 3 $self->YYParse( yylex => \&_Lexer, yyerror => \&_Error, 4 yybuildingtree => 1, 5 #, yydebug => 0x1F 6 ); 7 }Al ejecutar se producirá una salida similar a esta:
pl@nereida:~/LEyapp/examples$ eyapp ListWithRefs1.eyp; use_listwithrefs1.pl ccdd $VAR1 = bless( { 'children' => [ bless( { 'children' => [], 'attr' => 'c', 'token' => 'c' }, 'TERMINAL' ), bless( { 'children' => [], 'attr' => 'c', 'token' => 'c' }, 'TERMINAL' ) ] }, '_PLUS_LIST_1' ); _PLUS_LIST_1(TERMINAL,TERMINAL) $VAR1 = bless( { 'children' => [] }, '_PLUS_LIST_2' ); _PLUS_LIST_2
Aunque 'd'
es declarado semántico la acción por
defecto asociada con la regla D: 'd'
en la línea 16 retornará
$_[1]
(esto es, el escalar 'd'
). Dado que no se trata
de una referencia no es insertado en la lista de hijos del nodo
_PLUS_LIST
.
La solución es hacer que cada uno de los símbolos a los que afecta el operador de lista sea una referencia.
pl@nereida:~/LEyapp/examples$ head -22 ListWithRefs.eyp | cat -n 1 # ListWithRefs.eyp 2 %semantic token 'c' 3 %{ 4 use Data::Dumper; 5 %} 6 %% 7 S: 'c'+ D+ 8 { 9 print Dumper($_[1]); 10 print $_[1]->str."\n"; 11 print Dumper($_[2]); 12 print $_[2]->str."\n"; 13 } 14 ; 15 16 D: 'd' 17 { 18 bless { attr => $_[1], children =>[]}, 'DES'; 19 } 20 ; 21 22 %%
Ahora el atributo asociado con D
es un nodo y aparece en la
lista de hijos del nodo _PLUS_LIST
:
pl@nereida:~/LEyapp/examples$ eyapp ListWithRefs.eyp; use_listwithrefs.pl ccdd $VAR1 = bless( { 'children' => [ bless( { 'children' => [], 'attr' => 'c', 'token' => 'c' }, 'TERMINAL' ), bless( { 'children' => [], 'attr' => 'c', 'token' => 'c' }, 'TERMINAL' ) ] }, '_PLUS_LIST_1' ); _PLUS_LIST_1(TERMINAL,TERMINAL) $VAR1 = bless( { 'children' => [ bless( { 'children' => [], 'attr' => 'd' }, 'DES' ), bless( { 'children' => [], 'attr' => 'd' }, 'DES' ) ] }, '_PLUS_LIST_2' ); _PLUS_LIST_2(DES,DES)
La solución anterior consistente en escribir a mano el código de construcción del nodo
puede ser suficiente cuando se trata de un sólo nodo.
Escribir a mano el código para la construcción de un árbol con varios nodos
puede ser tedioso. Peor aún: aunque el nodo construido en el ejemplo
luce como los nodos Parse::Eyapp
no es realmente un nodo
Parse::Eyapp
. Los nodos Parse::Eyapp
siempre heredan
de la clase Parse::Eyapp::Node
y por tanto tienen
acceso a los métodos definidos en esa clase.
La siguiente ejecución con el depurador ilustra este punto:
pl@nereida:~/LEyapp/examples$ perl -wd use_listwithrefs.pl Loading DB routines from perl5db.pl version 1.28 Editor support available. Enter h or `h h' for help, or `man perldebug' for more help. main::(use_listwithrefs.pl:4): $parser = new ListWithRefs(); DB<1> f ListWithRefs.eyp 1 2 #line 3 "ListWithRefs.eyp" 3 4: use Data::Dumper; 5 6 #line 7 "ListWithRefs.eyp" 7 #line 8 "ListWithRefs.eyp" 8 9: print Dumper($_[1]); 10: print $_[1]->str."\n";Mediante el comando
f ListWithRefs.eyp
le indicamos
al depurador que los subsiguientes comandos harán referencia
a dicho fichero. A continuación ejecutamos el programa hasta alcanzar
la acción semántica asociada con la regla S: 'c'+ D+
(línea 9)
DB<2> c 9 # Continuar hasta la línea 9 de ListWithRefs.eyp ccdd ListWithRefs::CODE(0x84ebe5c)(ListWithRefs.eyp:9): 9: print Dumper($_[1]);Estamos en condiciones ahora de observar los contenidos de los argumentos:
DB<3> x $_[2]->str 0 '_PLUS_LIST_2(DES,DES)' DB<4> x $_[2]->child(0) 0 DES=HASH(0x85c4568) 'attr' => 'd' 'children' => ARRAY(0x85c458c) empty arrayEl método
str
funciona con el objeto $_[2]
pues
los nodos _PLUS_LIST_2
heredan de la clase Parse::Eyapp::Node
.
sin embargo, cuando intentamos usarlo con un nodo DES
obtenemos un
error:
DB<6> x $_[2]->child(0)->str Can't locate object method "str" via package "DES" at \ (eval 11)[/usr/share/perl/5.8/perl5db.pl:628] line 2, <STDIN> line 1. DB<7>Una solución mas robusta que la anterior es usar el constructor
Parse::Eyapp::Node->new
.
El método
Parse::Eyapp::Node->new
se usa para construir un bosque de árboles sintácticos.
Recibe una secuencia de términos describiendo los árboles
y - opcionalmente - una subrutina.
La subrutina se utiliza para iniciar los atributos
de los nodos recién creados. Después de la creación del árbol
la subrutina es llamada por Parse::Eyapp::Node->new
pasándole como argumentos la lista de referencias a los nodos
en el órden en el que aparecen en la secuencia de términos
de izquierda a derecha.
Parse::Eyapp::Node-
new retorna una lista de
referencias a los nodos recién creados,
en el órden en el que aparecen en la secuencia de términos
de izquierda a derecha.
En un contexto escalar devuelve la referencia al primero
de esos árboles.
Por ejemplo:
pl@nereida:~/LEyapp/examples$ perl -MParse::Eyapp -MData::Dumper -wde 0 main::(-e:1): 0 DB<1> @t = Parse::Eyapp::Node->new('A(C,D) E(F)', sub { my $i = 0; $_->{n} = $i++ for @_ }) DB<2> $Data::Dumper::Indent = 0 DB<3> print Dumper($_)."\n" for @t $VAR1 = bless( {'n' => 0,'children' => [bless( {'n' => 1,'children' => []}, 'C' ), bless( {'n' => 2,'children' => []}, 'D' ) ] }, 'A' ); $VAR1 = bless( {'n' => 1,'children' => []}, 'C' ); $VAR1 = bless( {'n' => 2,'children' => []}, 'D' ); $VAR1 = bless( {'n' => 3,'children' => [bless( {'n' => 4,'children' => []}, 'F' )]}, 'E' ); $VAR1 = bless( {'n' => 4,'children' => []}, 'F' );
Véase el siguiente ejemplo en el cual los nodos asociados con las 'd'
se han convertido
en un subárbol:
pl@nereida:~/LEyapp/examples$ head -28 ListWithRefs2.eyp| cat -n 1 # ListWithRefs2.eyp 2 %semantic token 'c' 3 %{ 4 use Data::Dumper; 5 %} 6 %% 7 S: 'c'+ D+ 8 { 9 print Dumper($_[1]); 10 print $_[1]->str."\n"; 11 print Dumper($_[2]); 12 print $_[2]->str."\n"; 13 } 14 ; 15 16 D: 'd'.d 17 { 18 Parse::Eyapp::Node->new( 19 'DES(TERMINAL)', 20 sub { 21 my ($DES, $TERMINAL) = @_; 22 $TERMINAL->{attr} = $d; 23 } 24 ); 25 } 26 ; 27 28 %%
Para saber mas sobre Parse::Eyapp::Node->new
consulte la entrada
Parse::Eyapp::Node->new
de la documentación de Parse::Eyapp
.
pl@nereida:~/LEyapp/examples$ eyapp ListWithRefs2.eyp; use_listwithrefs2.pl ccdd $VAR1 = bless( { 'children' => [ bless( { 'children' => [], 'attr' => 'c', 'token' => 'c' }, 'TERMINAL' ), bless( { 'children' => [], 'attr' => 'c', 'token' => 'c' }, 'TERMINAL' ) ] }, '_PLUS_LIST_1' ); _PLUS_LIST_1(TERMINAL,TERMINAL) $VAR1 = bless( { 'children' => [ bless( { 'children' => [ bless( { 'children' => [], 'attr' => 'd' }, 'TERMINAL' ) ] }, 'DES' ), bless( { 'children' => [ bless( { 'children' => [], 'attr' => 'd' }, 'TERMINAL' ) ] }, 'DES' ) ] }, '_PLUS_LIST_2' ); _PLUS_LIST_2(DES(TERMINAL),DES(TERMINAL))
Un operador de lista afecta al factor a su izquierda. Una lista en la parte derecha de una regla cuenta como un único símbolo.
Los operadores *
y +
pueden ser
usados con el formato X <* Separator>
.
En ese caso lo que se describen son listas separadas por el separador
separator
.
pl@nereida:~/LEyapp/examples$ head -25 CsBetweenCommansAndD.eyp | cat -n 1 # CsBetweenCommansAndD.eyp 2 3 %semantic token 'c' 'd' 4 5 %{ 6 sub TERMINAL::info { 7 $_[0]->attr; 8 } 9 %} 10 %tree 11 %% 12 S: 13 ('c' <* ','> 'd')* 14 { 15 print "\nNode\n"; 16 print $_[1]->str."\n"; 17 print "\nChild 0\n"; 18 print $_[1]->child(0)->str."\n"; 19 print "\nChild 1\n"; 20 print $_[1]->child(1)->str."\n"; 21 $_[1] 22 } 23 ; 24 25 %%La regla
S: ('c' <* ','> 'd')*
tiene dos elementos en su parte derecha: la lista de c
s
separadas por comas y la d
. La regla es equivalente a:
pl@nereida:~/LEyapp/examples$ eyapp -v CsBetweenCommansAndD.eyp pl@nereida:~/LEyapp/examples$ head -11 CsBetweenCommansAndD.output | cat -n 1 Rules: 2 ------ 3 0: $start -> S $end 4 1: STAR-1 -> STAR-1 ',' 'c' 5 2: STAR-1 -> 'c' 6 3: STAR-2 -> STAR-1 7 4: STAR-2 -> /* empty */ 8 5: PAREN-3 -> STAR-2 'd' 9 6: STAR-4 -> STAR-4 PAREN-3 10 7: STAR-4 -> /* empty */ 11 8: S -> STAR-4
La acción semántica asociada con un operador de lista *
es retornar
una referencia a una lista con los atributos de los elementos a
los que se aplica.
Si se trabaja - como en el ejemplo -
bajo una directiva de creación de árbol retorna un nodo
con la etiqueta _STAR_LIST_#number
cuyos hijos son los elementos
de la lista. El número es el número de orden de la regla tal y como
aparece en el fichero .output
. Es necesario que los elementos sean
terminales o referencias para que se incluyan en la lista. Observe como el nodo PAREN-3
ha sido eliminado del árbol. Los nodos paréntesis son -en general - obviados:
pl@nereida:~/LEyapp/examples$ use_csbetweencommansandd.pl c,c,cd Node _STAR_LIST_4(_STAR_LIST_1(TERMINAL[c],TERMINAL[c],TERMINAL[c]),TERMINAL[d]) Child 0 _STAR_LIST_1(TERMINAL[c],TERMINAL[c],TERMINAL[c]) Child 1 TERMINAL[d]Obsérvese también que la coma ha sido eliminada.
Para poner nombre a una lista la directiva %name
debe preceder al operador
tal y como ilustra el siguiente ejemplo:
pl@nereida:~/LEyapp/examples$ sed -ne '1,27p' CsBetweenCommansAndDWithNames.eyp | cat -n 1 # CsBetweenCommansAndDWithNames.eyp 2 3 %semantic token 'c' 'd' 4 5 %{ 6 sub TERMINAL::info { 7 $_[0]->attr; 8 } 9 %} 10 %tree 11 %% 12 Start: S 13 ; 14 S: 15 ('c' <%name Cs * ','> 'd') %name Cs_and_d * 16 { 17 print "\nNode\n"; 18 print $_[1]->str."\n"; 19 print "\nChild 0\n"; 20 print $_[1]->child(0)->str."\n"; 21 print "\nChild 1\n"; 22 print $_[1]->child(1)->str."\n"; 23 $_[1] 24 } 25 ; 26 27 %%La ejecución muestra que los nodos de lista han sido renombrados:
pl@nereida:~/LEyapp/examples$ use_csbetweencommansanddwithnames.pl c,c,c,cd Node Cs_and_d(Cs(TERMINAL[c],TERMINAL[c],TERMINAL[c],TERMINAL[c]),TERMINAL[d]) Child 0 Cs(TERMINAL[c],TERMINAL[c],TERMINAL[c],TERMINAL[c]) Child 1 TERMINAL[d]
La utilización del operador ?
indica la presencia
o ausencia del factor a su izquierda.
La gramática:
pl@nereida:~/LEyapp/examples$ head -11 List5.yp | cat -n 1 %semantic token 'c' 2 %tree 3 %% 4 S: 'c' 'c'? 5 { 6 print $_[2]->str."\n"; 7 print $_[2]->child(0)->attr."\n" if $_[2]->children; 8 } 9 ; 10 11 %%
produce la siguiente gramática:
l@nereida:~/LEyapp/examples$ eyapp -v List5 pl@nereida:~/LEyapp/examples$ head -7 List5.output Rules: ------ 0: $start -> S $end 1: OPTIONAL-1 -> 'c' 2: OPTIONAL-1 -> /* empty */ 3: S -> 'c' OPTIONAL-1
Cuando no se trabaja bajo directivas de creación de árbol
el atributo asociado es una lista (vacía si el opcional no
aparece).
Bajo la directiva %tree
el efecto es crear el nodo:
pl@nereida:~/LEyapp/examples$ use_list5.pl cc _OPTIONAL_1(TERMINAL) c pl@nereida:~/LEyapp/examples$ use_list5.pl c _OPTIONAL_1
Es posible agrupar mediante paréntesis una subcadena de la parte derecha de una regla de producción. La introducción de un paréntesis implica la introducción de una variable adicional cuya única producción es la secuencia de símbolos entre paréntesis. Así la gramática:
pl@nereida:~/LEyapp/examples$ head -6 Parenthesis.eyp | cat -n 1 %% 2 S: 3 ('a' S ) 'b' { shift; [ @_ ] } 4 | 'c' 5 ; 6 %%
genera esta otra gramática:
pl@nereida:~/LEyapp/examples$ eyapp -v Parenthesis.eyp; head -6 Parenthesis.output Rules: ------ 0: $start -> S $end 1: PAREN-1 -> 'a' S 2: S -> PAREN-1 'b' 3: S -> 'c'
Por defecto, la regla semántica asociada con un paréntesis consiste en formar una lista con los atributos de los símbolos entre paréntesis:
pl@nereida:~/LEyapp/examples$ cat -n use_parenthesis.pl 1 #!/usr/bin/perl -w 2 use Parenthesis; 3 use Data::Dumper; 4 5 $Data::Dumper::Indent = 1; 6 $parser = Parenthesis->new(); 7 print Dumper($parser->Run); pl@nereida:~/LEyapp/examples$ use_parenthesis.pl acb $VAR1 = [ [ 'a', 'c' ], 'b' ]; pl@nereida:~/LEyapp/examples$ use_parenthesis.pl aacbb $VAR1 = [ [ 'a', [ [ 'a', 'c' ], 'b' ] ], 'b' ];
Cuando se trabaja bajo una directiva de creación de árbol o se establece el atributo con el método YYBuildingtree la acción semántica es construir un nodo con un hijo por cada atributo de cada símbolo entre paréntesis. Si el atributo no es una referencia no es insertado como hijo del nodo.
Veamos un ejemplo:
pl@nereida:~/LEyapp/examples$ head -23 List2.yp | cat -n 1 %{ 2 use Data::Dumper; 3 %} 4 %semantic token 'a' 'b' 'c' 5 %tree 6 %% 7 S: 8 (%name AS 'a' S )'b' 9 { 10 print "S -> ('a' S )'b'\n"; 11 print "Atributo del Primer Símbolo:\n".Dumper($_[1]); 12 print "Atributo del Segundo símbolo: $_[2]\n"; 13 $_[0]->YYBuildAST(@_[1..$#_]); 14 } 15 | 'c' 16 { 17 print "S -> 'c'\n"; 18 my $r = Parse::Eyapp::Node->new(qw(C(TERMINAL)), sub { $_[1]->attr('c') }) ; 19 print Dumper($r); 20 $r; 21 } 22 ; 23 %%El ejemplo muestra (línea 8) como renombrar un nodo
_PAREN
asociado con un paréntesis.
Se escribe la directiva %name CLASSNAME
despúes del paréntesis de
apertura.
La llamada de la línea 13 al método YYBuildAST
con
argumentos los atributos de los símbolos de la parte derecha se encarga de
retornar el nodo describiendo la regla de producción actual.
Observe que la línea 13 puede ser reescrita como:
goto &Parse::Eyapp::Driver::YYBuildAST;
En la línea 18 se construye explícitamente un nodo para la regla
usando Parse::Eyapp::Node->new
. El manejador pasado
como segundo argumento se encarga de establecer un valor para
el atributo attr
del nodo TERMINAL
que acaba de ser creado.
Veamos una ejecución:
pl@nereida:~/LEyapp/examples$ use_list2.pl aacbb S -> 'c' $VAR1 = bless( { 'children' => [ bless( { 'children' => [], 'attr' => 'c' }, 'TERMINAL' ) ] }, 'C' );La primera reducción ocurre por la regla no recursiva. La ejecución muestra el árbol construido mediante la llamada a
Parse::Eyapp::Node->new
de la línea 18.
La ejecución continúa con una reducción o anti-derivación por la regla
S -> ('a' S )'b'
. La acción de las líneas 9-14
hace que se muestre el atributo asociado con ('a' S)
o lo que es lo mismo con la variable sintáctica adicional
PAREN-1
asi como el atributo de 'b'
:
S -> ('a' S )'b' Atributo del Primer Símbolo: $VAR1 = bless( { 'children' => [ bless( { 'children' => [], 'attr' => 'a', 'token' => 'a' }, 'TERMINAL' ), bless( { 'children' => [ bless( { 'children' => [], 'attr' => 'c' }, 'TERMINAL' ) ] }, 'C' ) ] }, 'AS' ); Atributo del Segundo símbolo: bLa última reducción visible es por la regla
S -> ('a' S )'b'
:
S -> ('a' S )'b' Atributo del Primer Símbolo: $VAR1 = bless( { 'children' => [ bless( { 'children' => [], 'attr' => 'a', 'token' => 'a' }, 'TERMINAL' ), bless( { 'children' => [ bless( { 'children' => [ bless( { 'children' => [], 'attr' => 'a', 'token' => 'a' }, 'TERMINAL' ), bless( { 'children' => [ bless( { 'children' => [], 'attr' => 'c' }, 'TERMINAL' ) ] }, 'C' ) ] }, 'AS' ), bless( { 'children' => [], 'attr' => 'b', 'token' => 'b' }, 'TERMINAL' ) ] }, 'S_2' ) ] }, 'AS' ); Atributo del Segundo símbolo: b
Aunque no es una práctica recomendable es posible introducir acciones en los paréntesis como en este ejemplo:
pl@nereida:~/LEyapp/examples$ head -16 ListAndAction.eyp | cat -n 1 # ListAndAction.eyp 2 %{ 3 my $num = 0; 4 %} 5 6 %% 7 S: 'c' 8 { 9 print "S -> c\n" 10 } 11 | ('a' {$num++; print "Seen <$num> 'a's\n"; $_[1] }) S 'b' 12 { 13 print "S -> (a ) S b\n" 14 } 15 ; 16 %%
Al ejecutar el ejemplo con la entrada aaacbbb
se obtiene la siguiente salida:
pl@nereida:~/LEyapp/examples$ use_listandaction.pl aaacbbb Seen <1> 'a's Seen <2> 'a's Seen <3> 'a's S -> c S -> (a ) S b S -> (a ) S b S -> (a ) S b