Sig: Resultado del Análisis de Sup: Análisis de Ámbito Ant: La Dificultad de Elaboración Err: Si hallas una errata ...
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 3
En 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}} = $block
Si 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} = $block
donde $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 ![[*]](crossref.png)
:
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 blocks
No 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]])