Para calcular la relación entre una instancia de un identificador y su declaración usaremos el módulo Parse::Eyapp::Scope :
l@nereida:~/Lbook/code/Simple-Scope/lib/Simple$ sed -ne '1,/^ *$/p' Scope.eyp | cat -n 1 /* 2 File: lib/Simple/Scope.eyp 3 Full Scope Analysis 4 Test it with: 5 lib/Simple/ 6 eyapp -m Simple::Scope Scope.eyp 7 treereg -nonumbers -m Simple::Scope Trans 8 script/ 9 usescope.pl prueba12.c 10 */ 11 %{ 12 use strict; 13 use Data::Dumper; 14 use List::MoreUtils qw(firstval lastval); 15 use Simple::Trans; 16 use Parse::Eyapp::Scope qw(:all);
Véamos el
manejo de las reglas de program
:
pl@nereida:~/Lbook/code/Simple-Scope/lib/Simple$ sed -ne '/^program:/,/^;$/p' Scope.eyp | cat -n 1 program: 2 { 3 reset_file_scope_vars(); 4 } 5 definition<%name PROGRAM +>.program 6 { 7 $program->{symboltable} = { %st }; # creates a copy of the s.t. 8 for (keys %type) { 9 $type{$_} = Parse::Eyapp::Node->hnew($_); 10 } 11 $program->{depth} = 0; 12 $program->{line} = 1; 13 $program->{types} = { %type }; 14 $program->{lines} = $tokenend; 15 16 my ($nondec, $declared) = $ids->end_scope($program->{symboltable}, $program, 'type'); 17 18 if (@$nondec) { 19 warn "Identifier ".$_->key." not declared at line ".$_->line."\n" for @$nondec; 20 die "\n"; 21 } 22 23 # Type checking: add a direct pointer to the data-structure 24 # describing the type 25 $_->{t} = $type{$_->{type}} for @$declared; 26 27 my $out_of_loops = $loops->end_scope($program); 28 if (@$out_of_loops) { 29 warn "Error: ".ref($_)." outside of loop at line $_->{line}\n" for @$out_of_loops; 30 die "\n"; 31 } 32 33 # Check that are not dangling breaks 34 reset_file_scope_vars(); 35 36 $program; 37 } 38 ;
Antes de comenzar la construcción del AST se inicializan las variables visibles en todo el fichero:
pl@nereida:~/Lbook/code/Simple-Scope/lib/Simple$ sed -ne '/^sub reset_file_scope_vars/,/^}$/p' Scope.eyp | cat -n 1 sub reset_file_scope_vars { 2 %st = (); # reset symbol table 3 ($tokenbegin, $tokenend) = (1, 1); 4 %type = ( INT => 1, 5 CHAR => 1, 6 VOID => 1, 7 ); 8 $depth = 0; 9 $ids = Parse::Eyapp::Scope->new( 10 SCOPE_NAME => 'block', 11 ENTRY_NAME => 'info', 12 SCOPE_DEPTH => 'depth', 13 ); 14 $loops = Parse::Eyapp::Scope->new( 15 SCOPE_NAME => 'exits', 16 ); 17 $ids->begin_scope(); 18 $loops->begin_scope(); # just for checking 19 }
El método Parse::Eyapp::Scope->new crea un objeto del tipo manejador de ámbito.
Un manejador de ámbito es un objeto que ayuda en el cómputo de la función que asigna a cada nodo instancia de un nombre (variable, función, etiqueta, constante, identificador de tipo, etc.) su declaración, esto es su entrada en su tabla de símbolos.
En la línea 9 creamos el manejador de ámbito
de los objetos identificadores $ids
(ámbito de variables, funciones, etc.).
En la línea 14 creamos un manejador de ámbito para los bucles (sentencias CONTINUE
, break
, etc.).
El manejo de ámbito de los bucles consiste en asignar cada ocurrencia de una
sentencia BREAK
o CONTINUE
con el bucle en el que ocurre. Por ejemplo:
pl@nereida:~/Lbook/code/Simple-Scope/script$ usescope.pl outbreak.c 2 1 test (int n, int m) 2 { 3 break; 4 while (n > 0) { 5 if (n>m) { 6 break; 7 } 8 else if (m>n){ 9 continue; 10 } 11 n = n-1; 12 } 13 } Error: BREAK outside of loop at line 3En esta sección mostraremos como usar Parse::Eyapp::Scope cuando trabajemos en el análisis de condiciones dependientes del contexto.
La filosofía de Parse::Eyapp::Scope es que existen tres tipos de nodos en el AST:
La asignación de ámbito se implanta a través de atributos que se añaden a las nodos de uso y a los nodos ámbito.
Algunos de los nombres de dichos atributos pueden ser especificados mediante los parámetros
de new
. En concreto:
scope
.
En el ejemplo:
9 $ids = Parse::Eyapp::Scope->new( 10 SCOPE_NAME => 'block', 11 ENTRY_NAME => 'info', 12 SCOPE_DEPTH => 'depth', 13 );
cada nodo asociado con una instancia de uso tendrá un atributo con clave block
que será una referencia al nodo BLOCK
en el que fué declarado el identificador.
entry
.
En el ejemplo que estamos trabajando cada nodo BLOCK
tendrá un atributo
symboltable
que será una referencia a la tabla de símbolos asociada con el bloque.
Dado que el atributo block
de un nodo $n
asociado
con una instancia de un identificador $id
apunta
al nodo BLOCK
en el que se define, siempre sería posible
acceder a la entrada de la tabla de símbolos mediante el código:
$n->{block}{symboltable}{$id}El atributo
entry
crea una referencia directa en el nodo:
$n->{entry} = $n->{block}{symboltable}{$id}de esta forma es mas directo acceder a la entrada de símbolos de una instancia de uso de un identificador.
Obviamente el atributo entry
no tiene sentido
en aquellos casos en que el análisis de ámbito no requiere
de la presencia de tablas de símbolos, como es el caso del
análisis de ámbito de las sentencias de cambio de flujo en
bucles:
14 $loops = Parse::Eyapp::Scope->new( 15 SCOPE_NAME => 'exits', 16 );
Este método debe ser llamado cada vez que se entra en una nueva región de ámbito.
Parse::Eyapp::Scope
asume un esquema de ámbitos léxicos anidados como ocurre en la mayoría
de los lenguajes de programación: se supone que
todos los nodos declarados mediante llamadas al método scope_instance
entre dos llamadas consecutivas a begin_scope
y end_scope
definen la región del ámbito.
Por ejemplo, en el analisis de ámbito de SimpleC llamamos a
begin_scope
cada vez que se entra en una definición de función:
pl@nereida:~/Lbook/code/Simple-Scope/lib/Simple$ sed -ne '/^funcDef:/,/^;$/p' Scope.eyp | cat -n 1 funcDef: 2 $ID 3 { 4 $ids->begin_scope(); 5 } 6 '(' $params ')' 7 $block 8 { .. ........................................ 35 } 36 ;y cada vez que se entra en un bloque:
pl@nereida:~/Lbook/code/Simple-Scope/lib/Simple$ sed -ne '/^block:/,/^;$/p' Scope.eyp | cat -n 1 block: 2 '{'.bracket 3 { $ids->begin_scope(); } 4 declaration<%name DECLARATIONS *>.decs statement<%name STATEMENTS *>.sts '}' 5 { 25 ................ 26 } 27 28 ;
En el caso del análisis de ámbito de bucles la entrada en un bucle crea una nueva región de ámbito:
pl@nereida:~/Lbook/code/Simple-Scope/lib/Simple$ sed -ne '/^loopPrefix:/,/^;$/p' Scope.eyp | cat -n 1 loopPrefix: 2 $WHILE '(' expression ')' 3 { 4 $loops->begin_scope; 5 $_[3]->{line} = $WHILE->[1]; 6 $_[3] 7 } 8 ;
En el código que sigue
el método end_scope
es llamado con tres argumentos:
my ($nodec, $dec) = $ids->end_scope($st, $block, 'type');El significado de estos argumentos es el siguiente:
$st
.
Este hash es la tabla de símbolos asociada con el bloque actual.
Se asume que la clave de entrada de un nodo $n
del árbol
se obtiene mediante una llamada al método del nodo key
definido
por el programador: $st->{$n->key}
. Se asume también que los
valores del hash son una referencia a un hash conteniendo los atributos
asociados con la clave $n->key
.
$block
o nodo de ámbito asociado con el hash.
En nuestro ejemplo del análisis de ámbito de los identificadores
las instancias de identificadores declarados en el presente bloque
seran decorados con un atributo block
que apunta a dicho nodo.
El nombre es block
porque así se específico en la llamada a new
:
9 $ids = Parse::Eyapp::Scope->new( 10 SCOPE_NAME => 'block', 11 ENTRY_NAME => 'info', 12 SCOPE_DEPTH => 'depth', 13 );
'type'
que sean pasados a end_scope
son interpretados como claves del hash
apuntado por su entrada en la tabla de símbolos $n->key
.
Para cada uno de esos argumentos se crean referencias directas en el nodo $n
a los mismos:
$n->{type} = $st->{$n->key}{type}
$ids->end_scope($st, $block, 'type')
ocurre después del
análisis de todo el bloque de la función:
pl@nereida:~/Lbook/code/Simple-Scope/lib/Simple$ sed -ne '/^funcDef:/,/^;$/p' Scope.eyp | cat -n 1 funcDef: 2 $ID 3 { 4 $ids->begin_scope(); 5 } 6 '(' $params ')' 7 $block 8 { 9 my $st = $block->{symboltable}; 10 my @decs = $params->children(); 11 $block->{parameters} = []; 12 while (my ($bt, $id, $arrspec) = splice(@decs, 0, 3)) { .. .................................................. 24 } 25 $block->{function_name} = $ID; 26 $block->type("FUNCTION"); 27 28 my ($nodec, $dec) = $ids->end_scope($st, $block, 'type'); 29 30 # Type checking: add a direct pointer to the data-structure 31 # describing the type 32 $_->{t} = $type{$_->{type}} for @$dec; 33 34 return $block; 35 } 36 ;Todos los nodos
$n
del árbol que fueron
declarados como instancias mediante llamadas al método
scope_instance
desde la última llamada a begin_scope
son buscados en el hash referenciado por $st
.
Si la clave $n->key
asociada con el nodo $n
se encuentra entre las claves del hash (esto es,
exists $st->{$n->key}
) el nodo se
anota como declarado. Los nodos-instancia para los cuales
no existe una entrada en la tabla de símbolos se consideran
no declarados.
Cuando un nodo se determina como declarado se establecen los atributos de declaración:
ENTRY_NAME
de new
)
$n->{$ids->{ENTRY_NAME}} = $st->{$n->key}Si por ejemplo el nodo siendo usado se corresponde con el uso de una variable de nombre
a
,
entonces $n->key
deberá retornar a
y la asignación anterior, asumiendo la declaración
previa del manejador de ámbito $ids
, sería:
$n->{info} = $st->{a}
SCOPE_NAME
).
$n->{$ids->{SCOPE_NAME}} = $blockSi por ejemplo el nodo siendo usado se corresponde con el uso de una variable de nombre
a
,
la asignación anterior, asumiendo la declaración
previa del manejador de ámbito $ids
, sería:
$n->{block} = $blockdonde
$block
es el nodo asociado con el bloque en el que fue declarado
$a
.
'type'
en el ejemplo -
que sean pasados a end_scope
son interpretados
como claves del hash apuntado por su entrada en la tabla de
símbolos $st->{$n->key}
. Para cada uno de esos argumentos
se crean referencias directas en el nodo $n
a los mismos.
$n->{type} = $st->{$n->key}{type}esto es:
$n->{type} = $st->{a}{type}
Se supone que antes de la llamada a end_scope las declaraciones de los diferentes objetos han sido procesadas y la tabla hash ha sido rellenada con las mismas.
Los nodos $n
que no aparezcan entre los
declarados en este ámbito son apilados en la esperanza de que
hayan sido declarados en un ámbito superior.
Para un ejemplo de uso véase la línea 28 en el código anterior.
El tercer argumento type
indica que para cada instancia
de variable global que ocurre en el ámbito de program
queremos que se cree una referencia desde el nodo a su entrada
type
en la tabla de símbolos. De este modo se puede
conseguir un acceso mas rápido al tipo de la instancia si bien a costa
de aumentar el consumo de memoria.
En un contexto de lista end_scope
devuelve un par de referencias.
La primera es una referencia a la lista de instancias/nodos
del ámbito actual que no aparecen como claves
del hash. La segunda a los que aparecen.
En un contexto escalar devuelve la lista de instancias/nodos no declarados.
El programador deberá proveer a cada clase de nodo (subclases de Parse::Eyapp::Node
)
que pueda ser instanciado/usado en un ámbito o bloque de un método key .
En nuestro caso los nodos
del tipo VAR
, VARARRAY
y FUNCTIONCALL
son los que
pueden
ser usados dentro de expresiones y sentencias.
El método key se usa para computar el valor de la clave de entrada en el hash para esa clase de nodo.
Para la tabla de símbolos de los identificadores
en SimpleC necesitamos definir el método key
para los nodos VAR
,
VARARRAY
y FUNCTIONCALL
:
827 sub VAR::key { 828 my $self = shift; 829 830 return $self->child(0)->{attr}[0]; 831 } 832 833 *VARARRAY::key = *FUNCTIONCALL::key = \&VAR::key;
Si tiene dudas repase la definición de Variable
en la descripción de la gramática en la página :
Variable: %name VAR ID | %name VARARRAY $ID ('[' binary ']') <%name INDEXSPEC +> ;y el subárbol para la asignación de
a = 2
en la página .
ASSIGN( VAR( TERMINAL[a:5] ), INUM( TERMINAL[2:5] ) ) # ASSIGN,
En el caso de un análisis de ámbito simple como es el análisis de ámbito
de los bucles no se requiere de la presencia de una tabla de símbolos.
El único argumento de end_scope
es la referencia al nodo que define
el ámbito.
pl@nereida:~/Lbook/code/Simple-Scope/lib/Simple$ sed -ne '/^statement:/,/^;$/p' Scope.eyp | cat -n 1 statement: 2 expression ';' { $_[1] } 3 | ';' 4 | %name BREAK 5 $BREAK ';' 6 { 7 my $self = shift; 8 my $node = $self->YYBuildAST(@_); 9 $node->{line} = $BREAK->[1]; 10 $loops->scope_instance($node); 11 return $node; 12 } 13 | %name CONTINUE 14 $CONTINUE ';' 15 { 19 ............................... 21 } .. ..................................... 34 | %name WHILE 35 $loopPrefix statement 36 { 37 my $self = shift; 38 my $wnode = $self->YYBuildAST(@_); 39 $wnode->{line} = $loopPrefix->{line}; 40 my $breaks = $loops->end_scope($wnode); 41 return $wnode; 42 } 43 ;
Este método del objeto Parse::Eyapp::Scope
empuja el nodo
que se le pasa como argumento en la cola de instancias del
manejador de ámbito.
El nodo se considerará una ocurrencia de un objeto dentro
del ámbito actual (el que comienza en la última ejecución
de begin_scope
). En el compilador de SimpleC
debemos hacer:
pl@nereida:~/Lbook/code/Simple-Scope/lib/Simple$ sed -ne '/^Primary:/,/^;$/p' Scope.eyp | cat -n 1 Primary: 2 %name INUM 3 INUM 4 | %name CHARCONSTANT 5 CHARCONSTANT 6 | $Variable 7 { 8 $ids->scope_instance($Variable); 9 return $Variable 10 } 11 | '(' expression ')' { $_[2] } 12 | $function_call 13 { 14 $ids->scope_instance($function_call); 15 return $function_call # bypass 16 } 17 ;
Otros lugares en los que ocurren instancias de identificadores son las asignaciones:
pl@nereida:~/Lbook/code/Simple-Scope/lib/Simple$ sed -ne '/^binary:/,/^;$/p' Scope.eyp | cat -n 1 binary: 2 Unary { $_[1] } 3 | %name PLUS 4 binary '+' binary .. ................... 23 | %name ASSIGN 24 $Variable '=' binary 25 { 26 goto &declare_instance_and_build_node; 27 } 28 | %name PLUSASSIGN 29 $Variable '+=' binary 30 { 31 goto &declare_instance_and_build_node; 32 } 33 | %name MINUSASSIGN 34 $Variable '-=' binary 35 { 36 goto &declare_instance_and_build_node; 37 } 38 | %name TIMESASSIGN 39 $Variable '*=' binary 40 { 41 goto &declare_instance_and_build_node; 42 } 43 | %name DIVASSIGN 44 $Variable '/=' binary 45 { 46 goto &declare_instance_and_build_node; 47 } 48 | %name MODASSIGN 49 $Variable '%=' binary 50 { 51 goto &declare_instance_and_build_node; 52 } 53 ;Como indica su nombre, la función
declare_instance_and_build_node
declara la instancia y crea el nodo del AST:
116 sub declare_instance_and_build_node { 117 my ($parser, $Variable) = @_[0,1]; 118 119 $ids->scope_instance($Variable); 120 goto &Parse::Eyapp::Driver::YYBuildAST; 121 }
En el caso del análisis de ámbito en bucles las instancias ocurren en las
sentencias de break
y continue
:
pl@nereida:~/Lbook/code/Simple-Scope/lib/Simple$ sed -ne '/^statement:/,/^;$/p' Scope.eyp | cat -n 1 statement: 2 expression ';' { $_[1] } 3 | ';' 4 | %name BREAK 5 $BREAK ';' 6 { 7 my $self = shift; 8 my $node = $self->YYBuildAST(@_); 9 $node->{line} = $BREAK->[1]; 10 $loops->scope_instance($node); 11 return $node; 12 } 13 | %name CONTINUE 14 $CONTINUE ';' 15 { 16 my $self = shift; 17 my $node = $self->YYBuildAST(@_); 18 $node->{line} = $CONTINUE->[1]; 19 $loops->scope_instance($node); 20 return $node; 21 } .. ..................................... 34 | %name WHILE 35 $loopPrefix statement 36 { 37 my $self = shift; 38 my $wnode = $self->YYBuildAST(@_); 39 $wnode->{line} = $loopPrefix->{line}; 40 my $breaks = $loops->end_scope($wnode); 41 return $wnode; 42 } 43 ;
El modo de uso se ilustra en el manejo de los bloques
block: '{' declaration * statement * '}'
La computación del ámbito requiere las siguientes etapas:
Durante las sucesivas visitas a declaration
construímos
tablas de símbolos que son mezcladas en las líneas 8-15.
Todas
las instancias de nodos-nombre que ocurren cuando se
visitan los hijos de statements
son declaradas como
instanciaciones con scope_instance
(véanse los acciones
semánticas para Primary
en la página ).
La llamada a end_scope
de la línea 19
produce la computación parcial de la función de asignación de ámbito
para los nodos/nombre que fueron instanciados en este bloque.
pl@nereida:~/Lbook/code/Simple-Scope/lib/Simple$ sed -ne '/^block:/,/^;$/p' Scope.eyp | cat -n 1 block: 2 '{'.bracket 3 { $ids->begin_scope(); } 4 declaration<%name DECLARATIONS *>.decs statement<%name STATEMENTS *>.sts '}' 5 { 6 my %st; 7 8 for my $lst ($decs->children) { 9 10 # control duplicated declarations 11 my $message; 12 die $message if $message = is_duplicated(\%st, $lst); 13 14 %st = (%st, %$lst); 15 } 16 $sts->{symboltable} = \%st; 17 $sts->{line} = $bracket->[1]; 18 $sts->type("BLOCK") if (%st); 19 my ($nondec, $dec) = $ids->end_scope(\%st, $sts, 'type'); 20 21 # Type checking: add a direct pointer to the data-structure 22 # describing the type 23 $_->{t} = $type{$_->{type}} for @$dec; 24 25 return $sts; 26 } 27 28 ;
Actualmente las acciones intermedias tal y como la que se ven en el código anterior se usan habitualmente para producir efectos laterales en la construcción del árbol. No dan lugar a la inserción de un nodo. Esto es, la variable auxiliar/temporal generada para dar lugar a la acción intermedia no es introducida en el árbol generado.
Para completar el análisis de ámbito queremos decorar cada nodo BLOCK
con un atributo fatherblock
que referencia al nodo bloque
que lo contiene. Para esta fase usaremos el lenguaje Treeregexp .
Las frases de este lenguaje permiten definir conjuntos de árboles. Cuando van en un fichero aparte los programas
Treeregexp
suelen tener la extensión trg
. Por ejemplo,
el siguiente programa
pl@nereida:~/Lbook/code/Simple-Scope/lib/Simple$ cat -n Trans.trg 1 /* Scope Analysis */ 2 blocks: /BLOCK|FUNCTION|PROGRAM/ 3 4 retscope: /FUNCTION|RETURN/ 5 6 loop_control: /BREAK|CONTINUE|WHILE/define tres expresiones árbol a las que nos podremos referir en el cliente mediante las variables
$blocks
, $retscope
y
loops_control
. La primera expresión árbol tiene por nombre blocks
y casará con cualesquiera árboles de las clases BLOCK
, FUNCTION
o PROGRAM
.
Es necesario compilar el programa Treeregexp
:
l@nereida:~/Lbook/code/Simple-Scope/lib/Simple$ treereg -m Simple::Scope Trans pl@nereida:~/Lbook/code/Simple-Scope/lib/Simple$ ls -ltr | tail -2 -rw-r--r-- 1 pl users 122 2007-12-10 11:49 Trans.trg -rw-r--r-- 1 pl users 1544 2007-12-10 11:49 Trans.pmEl módulo generado
Trans.pm
contendrá una subrutina por cada expresión
regular árbol en el programa Treeregexp
.
La subrutina devuelve cierto si el nodo que se le pasa como primer argumento
casa con la expresión árbol. La subrutina espera como primer argumento el nodo, como
segundo argumento el padre del nodo y como tercero el objeto Parse::Eyapp::YATW
que encapsula
la transformación:
pl@nereida:~/Lbook/code/Simple-Scope/lib/Simple$ sed -ne '19,31p' Trans.pm sub blocks { my $blocks = $_[3]; # reference to the YATW pattern object my $W; { my $child_index = 0; return 0 unless ref($W = $_[$child_index]) =~ m{\bBLOCK\b|\bFUNCTION\b|\bPROGRAM\b}x; } # end block of child_index 1; } # end of blocksNo solo se construye una subrutina
blocks
sino que en el espacio de nombres
correspondiente se crean objetos Parse::Eyapp::YATW
por cada una de las
transformaciones especificadas en el programa trg
, como muestra el siguiente
fragmento del módulo conteniendo el código generado por treeregexp
:
pl@nereida:~/Lbook/code/Simple-Scope/lib/Simple$ sed -ne '16p' Trans.pm our @all = ( our $blocks, our $retscope, our $loop_control, ) = Parse::Eyapp::YATW->buildpatterns( blocks => \&blocks, retscope => \&retscope, loop_control => \&loop_control, );
Estos objetos Parse::Eyapp::YATW
estan disponibles
en el programa eyapp ya que hemos importado el módulo:
l@nereida:~/Lbook/code/Simple-Scope/lib/Simple$ sed -ne '1,/^ *$/p' Scope.eyp | cat -n 1 /* 2 File: lib/Simple/Scope.eyp 3 Full Scope Analysis 4 Test it with: 5 lib/Simple/ 6 eyapp -m Simple::Scope Scope.eyp 7 treereg -nonumbers -m Simple::Scope Trans 8 script/ 9 usescope.pl prueba12.c 10 */ 11 %{ 12 use strict; 13 use Data::Dumper; 14 use List::MoreUtils qw(firstval lastval); 15 use Simple::Trans; 16 use Parse::Eyapp::Scope qw(:all);
Es por eso que, una vez realizadas las fases de análisis léxico,
sintáctico y de ámbito podemos usar el objeto $blocks
y el método m
(por matching
) de dicho objeto
(véase la línea 14 en el código de compile
):
pl@nereida:~/Lbook/code/Simple-Scope/lib/Simple$ sed -ne '/sub comp/,/^}/p' Scope.eyp | cat -n 1 sub compile { 2 my($self)=shift; 3 4 my ($t); 5 6 $self->YYData->{INPUT} = shift; 7 8 $t = $self->YYParse( yylex => \&_Lexer, yyerror => \&_Error, 9 #yydebug => 0x1F 10 ); 11 12 # Scope Analysis: Block Hierarchy 13 our $blocks; 14 my @blocks = $blocks->m($t); 15 $_->node->{fatherblock} = $_->father->{node} for (@blocks[1..$#blocks]); 16 .. ................................. 28 29 return $t; 30 }
El método m
para árboles y expresiones regulares árbol
YATW
funciona de manera parecida
al método m
para cadenas y expresiones regulares convencionales.
El resultado de un matching en árboles es un árbol. Si se trabaja en un contexto
de lista es una lista de árboles.
La llamada $blocks->m($t)
permite la búsqueda
de los nodos de $t
que casan con la expresión regular árbol para blocks
.
En un contexto de lista m
devuelve una
lista con nodos del
tipo Parse::Eyapp::Node::Match que referencian
a los nodos que han casado.
Los nodos Parse::Eyapp::Node::Match
son a su vez nodos (heredan de)
Parse::Eyapp::Node
.
Los nodos
aparecen en la lista retornada en orden primero profundo de
recorrido del árbol $t
.
Los nodos en la lista
se estructuran según un árbol (atributos children
y father
)
de manera que el padre
de un nodo $n
del tipo Parse::Eyapp::Node::Match
es el
nodo $f
que referencia al inmediato antecesor
en el árbol que ha casado.
Un nodo $r
de la clase
Parse::Eyapp::Node::Match
dispone de varios atributos
y métodos:
$r->node
retorna el nódo del árbol $t
que ha casado
$r->father
retorna el nodo padre en el árbol the matching.
Se cumple que $r->father->node
es
una referencia al antepasado mas cercano en $t
de $r->node
que casa con el patrón árbol.
$r->coord
retorna las coordenadas del nódo del árbol que ha casado
usando una notación con puntos. Por ejemplo la coordenada
".1.3.2"
denota al nodo $t->child(1)->child(3)->child(2)
, siendo $t
la raíz del árbol de búsqueda.
$r->depth
retorna la profundidad del nódo del árbol que ha casado
En un contexto escalar m
devuelve el primer
elemento de la lista de nodos Parse::Eyapp::Node::Match
.
pl@nereida:~/Lbook/code/Simple-Scope/script$ perl -wd usescope.pl blocks.c 2 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::(usescope.pl:6): my $filename = shift || die "Usage:\n$0 file.c\n"; DB<1> c Simple::Scope::compile 1 test (int n) 2 { 3 int a; 4 5 while (1) { 6 if (1>0) { 7 int a; 8 break; 9 } 10 else if (2>0){ 11 char b; 12 continue; 13 } 14 } 15 } Simple::Scope::compile(Scope.eyp:784): 784: my($self)=shift; DB<2> l 783,797 783 sub compile { 784==> my($self)=shift; 785 786: my ($t); 787 788: $self->YYData->{INPUT} = shift; 789 790: $t = $self->YYParse( yylex => \&_Lexer, yyerror => \&_Error, 791 #yydebug => 0x1F 792 ); 793 794 # Scope Analysis: Block Hierarchy 795: our $blocks; 796: my @blocks = $blocks->m($t); 797: $_->node->{fatherblock} = $_->father->{node} for (@blocks[1..$#blocks]); DB<3> c 797 Simple::Scope::compile(Scope.eyp:797): 797: $_->node->{fatherblock} = $_->father->{node} for (@blocks[1..$#blocks]); DB<4> x Parse::Eyapp::Node->str(@blocks) 0 ' Match[[PROGRAM:0:blocks]]( Match[[FUNCTION:1:blocks:test]]( Match[[BLOCK:6:blocks:10:4]], Match[[BLOCK:5:blocks:6:4]] ) )' 1 ' Match[[FUNCTION:1:blocks:test]]( Match[[BLOCK:6:blocks:10:4]], Match[[BLOCK:5:blocks:6:4]] )' 2 ' Match[[BLOCK:5:blocks:6:4]]' 3 ' Match[[BLOCK:6:blocks:10:4]]'La información que aparece en los nodos
Match
es como sigue:
PROGRAM
, FUNCTION
, etc.
$t
info
la información asociada.
En este caso la línea y la profundidad en los bloques.
DB<5> p $t->str PROGRAM^{0}( FUNCTION[test]^{1}( # test (int n) { WHILE( # while (1) { INUM(TERMINAL[1:5]), STATEMENTS( IFELSE( # if (1>0) { GT(INUM( TERMINAL[1:6]), INUM(TERMINAL[0:6])), BLOCK[6:4]^{2}( BREAK # break; ), # } IF( # else if (2>0){ GT(INUM(TERMINAL[2:10]), INUM(TERMINAL[0:10])), BLOCK[10:4]^{3}( CONTINUE # continue ) # } ) ) ) ) ) ) .... DB<6> x map {$_->coord} @blocks 0 '' 1 '.0' 2 '.0.0.1.0.1' 3 '.0.0.1.0.2.1' DB<7> p $t->descendant('.0.0.1.0.2.1')->str BLOCK[10:4]^{0}( CONTINUE ) --------------------------- 0) Symbol Table of block at line 10 $VAR1 = { 'b' => { 'type' => 'CHAR', 'line' => 11 } }; DB<8> x map {$_->depth} @blocks 0 0 1 1 2 5 3 6 DB<9> x map {ref($_->node) } @blocks 0 'PROGRAM' 1 'FUNCTION' 2 'BLOCK' 3 'BLOCK' DB<10> x map {ref($_->father) } @blocks 0 '' 1 'Parse::Eyapp::Node::Match' 2 'Parse::Eyapp::Node::Match' 3 'Parse::Eyapp::Node::Match' DB<11> x map {ref($_->father->node) } @blocks[1..3] 0 'PROGRAM' 1 'FUNCTION' 2 'FUNCTION' DB<12> x $blocks[2]->father->node->{function_name} 0 ARRAY(0x86ed84c) 0 'test' 1 1
La clase Parse::Eyapp::Node::Match
dispone además de otros métodos
para el caso en que se usan varios patrones en la misma búsqueda.
Por ejemplo, el método $r->names
retorna una referencia a los nombres de los patrones
que han casado con el nodo.
En el ejemplo que sigue aparecen tres transformaciones
fold
, zxw
y wxz
. La llamada a
m
de la línea 19 toma una forma diferente. ahora
m
es usado como método del árbol $t
y recibe como argumentos
la lista con los objetos expresiones regulares árbol (Parse::Eyapp::YATW
).
pl@nereida:~/LEyapp/examples$ cat -n m2.pl 1 #!/usr/bin/perl -w 2 use strict; 3 use Rule6; 4 use Parse::Eyapp::Treeregexp; 5 6 Parse::Eyapp::Treeregexp->new( STRING => q{ 7 fold: /TIMES|PLUS|DIV|MINUS/(NUM, NUM) 8 zxw: TIMES(NUM($x), .) and { $x->{attr} == 0 } 9 wxz: TIMES(., NUM($x)) and { $x->{attr} == 0 } 10 })->generate(); 11 12 # Syntax analysis 13 my $parser = new Rule6(); 14 my $input = "0*0*0"; 15 my $t = $parser->Run(\$input); 16 print "Tree:",$t->str,"\n"; 17 18 # Search 19 my $m = $t->m(our ($fold, $zxw, $wxz)); 20 print "Match Node:\n",$m->str,"\n";La primera expresión regular árbol
fold
casa con cualquier árbol tal
que la clase del nodo raíz case con la expresión regular (clásica)
/TIMES|PLUS|DIV|MINUS/
y tenga dos hijos de clase NUM
.
La segunda expresión regular zxw
(por zero
times whatever) casa con cualquier árbol tal que la clase del
nodo raíz es TIMES
y cuyo primer hijo pertenece a la clase
NUM
. Se debe cumplir además que el hijo del nodo NUM
(el nodo TERMINAL
proveído por el analizador léxico)
debe tener su atributo attr
a cero. La notación
NUM($x)
hace que en $x
se almacene una referencia al nodo
hijo de NUM
.
La expresión regular árbol wxz
es la simétrica de zxw
.
Cuando se ejecuta, el programa produce la salida:
pl@nereida:~/LEyapp/examples$ m2.pl Tree:TIMES(TIMES(NUM(TERMINAL),NUM(TERMINAL)),NUM(TERMINAL)) Match Node: Match[[TIMES:0:wxz]](Match[[TIMES:1:fold,zxw,wxz]])