La directiva %tree hace que Parse::Eyapp genere una estructura de datos que representa al árbol sintáctico. Haciendo uso de las directivas adecuadas podemos controlar la forma del árbol.
Los nodos del árbol sintáctico generado por la producción
son objetos (de tipo hash)
bendecidos en una clase
con nombre A_#
, esto es, el de la variable sintáctica en el lado izquierdo
seguida de un número de orden.
Los nodos retornados por el analizador léxico son bendecidos
en la clase especial TERMINAL
.
Los nodos tienen además un atributo children
que referencia
a la lista de nodos hijos
del nodo.
La directiva %name CLASSNAME
permite modificar el nombre
por defecto de la clase del nodo para que sea CLASSNAME
.
Por ejemplo, cuando es aplicada en el siguiente
fragmento de código:
25 exp: .. ............ 32 | %name PLUS 33 exp '+' expHace que el nodo asociado con la regla pertenezca a la clase
PLUS
en vez de a una clase con un nombre
poco significativo como
exp_25
:
pl@nereida:~/LEyapp/examples$ cat -n CalcSyntaxTree.eyp 1 # CalcSyntaxTree.eyp 2 %right '=' 3 %left '-' '+' 4 %left '*' '/' 5 %left NEG 6 %right '^' 7 8 %tree 9 10 %{ 11 sub TERMINAL::info { 12 my $self = shift; 13 14 $self->attr; 15 } 16 17 %} 18 %% 19 20 line: 21 %name EXP 22 exp '\n' 23 ; 24 25 exp: 26 %name NUM 27 NUM 28 | %name VAR 29 VAR 30 | %name ASSIGN 31 VAR '=' exp 32 | %name PLUS 33 exp '+' exp 34 | %name MINUS 35 exp '-' exp 36 | %name TIMES 37 exp '*' exp 38 | %name DIV 39 exp '/' exp 40 | %name UMINUS 41 '-' exp %prec NEG 42 | %name EXP 43 exp '^' exp 44 | %name PAREN 45 '(' exp ')' 46 ; 47 48 %% .. # Exactamente igual que en el ejemplo anterior
La forma que tiene el árbol construido mediante la directiva %tree
puede ser modificada. Por defecto, todos aquellos terminales
que aparecen en
definidos en el programa eyapp
mediante el uso de apóstrofes
son eliminados del árbol. En la jerga ''Eyapp'' un
token sintáctico es uno que será eliminado (podado)
del árbol sintáctico. Por contra, un token semántico es uno que
aparecerá en el árbol. Por defecto los tokens definidos simbólicamente
como NUM
o VAR
son ''semanticos'' y aparecerán como un nodo de
tipo TERMINAL
en el
árbol de análisis sintáctico. Estos estatus por defecto
pueden ser modificados mediante las directivas %semantic token
y %syntactic token
.
Los token sintácticos no forman parte del árbol construido.
Asi pues, en el ejemplo que nos ocupa, los terminales '='
,
'-'
,
'+'
,
'*'
y
'/'
serán, por defecto, eliminados del árbol sintáctico.
pl@nereida:~/LEyapp/examples$ cat -n usecalcsyntaxtree.pl 1 #!/usr/bin/perl -w 2 # usecalcsyntaxtree.pl prueba2.exp 3 use strict; 4 use CalcSyntaxTree; 5 6 sub slurp_file { 7 my $fn = shift; 8 my $f; 9 10 local $/ = undef; 11 if (defined($fn)) { 12 open $f, $fn 13 } 14 else { 15 $f = \*STDIN; 16 } 17 my $input = <$f>; 18 return $input; 19 } 20 21 my $parser = CalcSyntaxTree->new(); 22 23 my $input = slurp_file( shift() ); 24 my $tree = $parser->Run($input); 25 26 $Parse::Eyapp::Node::INDENT = 2; 27 print $tree->str."\n";
El método str de Parse::Eyapp::Node
devuelve una cadena describiendo el árbol de análisis
sintáctico enraizado en el nodo
que se ha pasado como argumento.
El método str cuando visita un nodo comprueba la existencia de
un método info para la clase del nodo. Si es así el método
será llamado. Obsérvese como en la cabecera del programa
Eyapp
proveemos un método
info
para los nodos TERMINAL
.
8 %tree 9 10 %{ 11 sub TERMINAL::info { 12 my $self = shift; 13 14 $self->attr; 15 } 16 17 %} 18 %%
Los nodos TERMINAL
del árbol sintáctico
tienen un atributo attr
que guarda
el valor pasado para ese terminal por el analizador
léxico.
La variable de paquete $Parse::Eyapp::Node::INDENT controla el formato de presentación usado por Parse::Eyapp::Node::str : Si es 2 cada paréntesis cerrar que este a una distancia mayor de $Parse::Eyapp::Node::LINESEP líneas será comentado con el tipo del nodo.
pl@nereida:~/LEyapp/examples$ cat prueba2.exp a=(2+b)*3 pl@nereida:~/LEyapp/examples$ usecalcsyntaxtree.pl prueba2.exp | cat -n 1 2 EXP( 3 ASSIGN( 4 TERMINAL[a], 5 TIMES( 6 PAREN( 7 PLUS( 8 NUM( 9 TERMINAL[2] 10 ), 11 VAR( 12 TERMINAL[b] 13 ) 14 ) # PLUS 15 ) # PAREN, 16 NUM( 17 TERMINAL[3] 18 ) 19 ) # TIMES 20 ) # ASSIGN 21 ) # EXP
Para entender mejor la representación interna que Parse::Eyapp
hace del
árbol ejecutemos de nuevo el programa con la ayuda del depurador:
pl@nereida:~/LEyapp/examples$ perl -wd usecalcsyntaxtree.pl prueba2.exp main::(usecalcsyntaxtree.pl:21): my $parser = CalcSyntaxTree->new(); DB<1> l 21-27 # Listamos las líneas de la 1 a la 27 21==> my $parser = CalcSyntaxTree->new(); 22 23: my $input = slurp_file( shift() ); 24: my $tree = $parser->Run($input); 25 26: $Parse::Eyapp::Node::INDENT = 2; 27: print $tree->str."\n"; DB<2> c 27 # Continuamos la ejecución hasta alcanzar la línea 27 main::(usecalcsyntaxtree.pl:27): print $tree->str."\n"; DB<3> x $tree 0 EXP=HASH(0x83dec7c) # El nodo raíz pertenece a la clase EXP 'children' => ARRAY(0x83df12c) # El atributo 'children' es una referencia a un array 0 ASSIGN=HASH(0x83decdc) 'children' => ARRAY(0x83df114) 0 TERMINAL=HASH(0x83dec40) # Nodo construido para un terminal 'attr' => 'a' # Atributo del terminal 'children' => ARRAY(0x83dee38) # Para un terminal debera ser una lista empty array # vacía 'token' => 'VAR' 1 TIMES=HASH(0x83df084) 'children' => ARRAY(0x83df078) 0 PAREN=HASH(0x83ded9c) 'children' => ARRAY(0x83defac) 0 PLUS=HASH(0x83dee74) 'children' => ARRAY(0x83deef8) 0 NUM=HASH(0x83dedc0) 'children' => ARRAY(0x832df14) 0 TERMINAL=HASH(0x83dedfc) 'attr' => 2 'children' => ARRAY(0x83dedd8) empty array 'token' => 'NUM' 1 VAR=HASH(0x83decd0) 'children' => ARRAY(0x83dee2c) 0 TERMINAL=HASH(0x83deec8) 'attr' => 'b' 'children' => ARRAY(0x83dee98) empty array 'token' => 'VAR' 1 NUM=HASH(0x83dee44) 'children' => ARRAY(0x83df054) 0 TERMINAL=HASH(0x83df048) 'attr' => 3 'children' => ARRAY(0x83dece8) empty array 'token' => 'NUM'Observe que un nodo es un objeto implantado mediante un hash. El objeto es bendecido en la clase/paquete que se especifico mediante la directiva
%name
. Todas estas clases
heredan de la clase Parse::Eyapp::Node
y por tanto disponen de los métodos
proveídos por esta clase (en particular el método str
usado en el ejemplo).
Los nodos disponen de un atributo children
que es una referencia a la lista de
nodos hijo. Los nodos de la clase TERMINAL
son construidos a partir
de la pareja (token, atributo)
proveída por el analizador léxico. Estos nodos
disponen además del atributo attr
que encapsula el atributo del terminal.
Observe como en el árbol anterior no existen nodos TERMINAL[+]
ni TERMINAL[*]
ya que estos terminales fueron definidos mediante apóstrofes y son
- por defecto - terminales sintácticos.
pl@nereida:~/LEyapp/examples$ head -9 CalcSyntaxTree3.eyp | cat -n 1 # CalcSyntaxTree.eyp 2 %semantic token '=' '-' '+' '*' '/' '^' 3 %right '=' 4 %left '-' '+' 5 %left '*' '/' 6 %left NEG 7 %right '^' 8 9 %treeEscriba un programa cliente y explique el árbol que resulta para la entrada
a=(2+b)*3
:
pl@nereida:~/LEyapp/examples$ cat prueba2.exp a=(2+b)*3 pl@nereida:~/LEyapp/examples$ usecalcsyntaxtree3.pl prueba2.exp | cat -n 1 2 EXP( 3 ASSIGN( 4 TERMINAL[a], 5 TERMINAL[=], 6 TIMES( 7 PAREN( 8 PLUS( 9 NUM( 10 TERMINAL[2] 11 ), 12 TERMINAL[+], 13 VAR( 14 TERMINAL[b] 15 ) 16 ) # PLUS 17 ) # PAREN, 18 TERMINAL[*], 19 NUM( 20 TERMINAL[3] 21 ) 22 ) # TIMES 23 ) # ASSIGN 24 ) # EXP
Modifiquemos la precedencia de operadores utilizada en el ejemplo anterior:
pl@nereida:~/LEyapp/examples$ head -6 CalcSyntaxTree2.eyp | cat -n 1 # CalcSyntaxTree.eyp 2 %right '=' 3 %left '+' 4 %left '-' '*' '/' 5 %left NEG 6 %right '^'Compilamos la gramática y la ejecutamos con entrada
a=2-b*3
:
pl@nereida:~/LEyapp/examples$ cat prueba3.exp a=2-b*3 pl@nereida:~/LEyapp/examples$ usecalcsyntaxtree2.pl prueba3.exp EXP( ASSIGN( TERMINAL[a], TIMES( MINUS( NUM( TERMINAL[2] ), VAR( TERMINAL[b] ) ) # MINUS, NUM( TERMINAL[3] ) ) # TIMES ) # ASSIGN ) # EXP
-
asociativo a derechas
<
, >
, etc.).
¿Cual es la prioridad adecuada para estos operadores?
¿Que asociatividad es correcta para los mismos?
Observe los árboles formados para frases como
a = b < c * 2
. Contraste como interpreta un lenguaje típico (Java, C, Perl)
una expresión como esta.
Es posible consultar o cambiar dinámicamente el estatus de un terminal usando el método YYIssemantic :
pl@nereida:~/LEyapp/examples$ sed -ne '/sub Run/,$p' CalcSyntaxTreeDynamicSemantic.eyp | cat -n 1 sub Run { 2 my($self)=shift; 3 4 $input = shift; 5 $self->YYIssemantic('+', 1); 6 return $self->YYParse( yylex => \&_Lexer, yyerror => \&_Error ); 7 }
Los árboles generados al ejecutar el programa
contienen nodos TERMINAL[+]
):
pl@nereida:~/LEyapp/examples$ usecalcsyntaxtreedynamicsemantic.pl 2+3+4 EXP( PLUS( PLUS( NUM( TERMINAL[2] ), TERMINAL[+], NUM( TERMINAL[3] ) ) # PLUS, TERMINAL[+], NUM( TERMINAL[4] ) ) # PLUS ) # EXP