Parse::Eyapp::Treeregexp permite la transformación de
árboles mediante el uso de Expresiones Regulares Arbol.
Las expresiones regulares árbol serán introducidas en mas detalle en la
sección
4.9.
El siguiente ejemplo modifica el anterior esquema de traducción de infijo a postfijo para producir un código de postfijo mas eficiente. Para ello se transforma el árbol generado durante la fase Tree Construction Time y antes de la fase Execution Time. El código Treeregexp que define el conjunto de transformaciones se encuentra en las líneas 74-103.
Las transformaciones consisten en
UMINUS a un número negativo
Después de ello se realiza la traducción quedando la misma
como el atributo t del
nodo raíz (línea 120).
A partir de este momento,
si el traductor tuviera un mayor número de fases
de posterior tratamiento del árbol,
los nodos de tipo código y los nodos hoja cuya funcionalidad es
puramente sintáctica como los terminales =, * etc.
pueden ser eliminados. Es por eso que los suprimimos en las
líneas 122-123.
Veamos primero el código y luego lo discutiremos en mas detalle:
nereida:~/src/perl/YappWithDefaultAction/examples> cat -n TSwithtreetransformations.eyp
1 # File TSwithtreetransformations.eyp
2 %right '='
3 %left '-' '+'
4 %left '*' '/'
5 %left NEG
6
7 %{
8 # Treeregexp is the engine for tree transformations
9 use Parse::Eyapp::Treeregexp;
10 use Data::Dumper;
11 $Data::Dumper::Indent = 1;
12 $Data::Dumper::Deepcopy = 1;
13 $Data::Dumper::Deparse = 1;
14 %}
15
16 %metatree
17
18 %defaultaction {
19 if (@_==4) { # binary operations: 4 = lhs, left, operand, right
20 $lhs->{t} = "$_[1]->{t} $_[3]->{t} $_[2]->{attr}";
21 return
22 }
23 die "Fatal Error. Unexpected input\n".Dumper(@_);
24 }
25
26 %%
27 line: %name PROG
28 exp <%name EXP + ';'>
29 { @{$lhs->{t}} = map { $_->{t}} ($lhs->child(0)->Children()); }
30
31 ;
32
33 exp: %name NUM NUM { $lhs->{t} = $_[1]->{attr}; }
34 | %name VAR VAR { $lhs->{t} = $_[1]->{attr}; }
35 | %name ASSIGN VAR '=' exp { $lhs->{t} = "$_[1]->{attr} $_[3]->{t} =" }
36 | %name PLUS exp '+' exp
37 | %name MINUS exp '-' exp
38 | %name TIMES exp '*' exp
39 | %name DIV exp '/' exp
40 | %name UMINUS '-' exp %prec NEG { $_[0]->{t} = "$_[2]->{t} NEG" }
41 | '(' exp ')' %begin { $_[2] } /* skip parenthesis */
42 ;
43
44 %%
45
46 # subroutines _Error and _Lexer
.. ................................
66
67 sub Run {
68 my($self)=shift;
69 print "input: "; $x = <>;
70 my $tree = $self->YYParse( yylex => \&_Lexer, yyerror => \&_Error,
71 #yydebug => 0xFF
72 );
73
74 my $transform = Parse::Eyapp::Treeregexp->new( STRING => q{
75
76 delete_code : CODE => { $delete_code->delete() }
77
78 {
79 sub not_semantic {
80 my $self = shift;
81 return 1 if $self->{token} eq $self->{attr};
82 return 0;
83 }
84 }
85
86 delete_tokens : TERMINAL and { not_semantic($TERMINAL) } => { $delete_tokens->delete() }
87
88 delete = delete_code delete_tokens;
89
90 uminus: UMINUS(., NUM($x), .) => { $x->{attr} = -$x->{attr}; $_[0] = $NUM }
91
92 constantfold: /TIMES|PLUS|DIV|MINUS/(NUM($x), ., NUM($y))
93 => {
94 $x->{attr} = eval "$x->{attr} $W->{attr} $y->{attr}";
95 $_[0] = $NUM[0];
96 }
97
98 zero_times: TIMES(NUM($x), ., .) and { $x->{attr} == 0 } => { $_[0] = $NUM }
99 times_zero: TIMES(., ., NUM($x)) and { $x->{attr} == 0 } => { $_[0] = $NUM }
100
101 algebraic_transformations = constantfold zero_times times_zero;
102
103 },
104 PACKAGE => 'TSwithtreetransformations',
105 OUTPUTFILE => 'main.pm',
106 SEVERITY => 0,
107 NUMBERS => 0,
108 );
109
110 # Create the transformer
111 $transform->generate();
112 # Get the AST
113
114 our ($uminus);
115 $uminus->s($tree);
116
117 our (@algebraic_transformations);
118 $tree->s(@algebraic_transformations);
119
120 $tree->translation_scheme();
121
122 our (@delete);
123 $tree->s(@delete);
124 print Dumper($tree);
125 }
La estructura de un programa Treeregexp es sencilla. Consiste en la repetición de tres tipos de expresiones regulares árbol: las treeregexp propiamente dichas, código auxiliar para las transformaciones y definiciones de familias de transformaciones.
treeregexplist:
treeregexp*
;
treeregexp:
IDENT ':' treereg ('=>' CODE)? # Treeregexp
| CODE # Código auxiliar
| IDENT '=' IDENT + ';' # Familia de transformaciones
;
Las expresiones regulares árbol propiamente dichas siguen la regla
IDENT ':' treereg ('=>' CODE)?
Podemos ver ejemplos de instancias de esta regla en las líneas
76, 86, 90, 92-96, 98 y 99. El identificador IDENT da el nombre
a la regla. Actualmente (2006) existen estos tipos de treereg :
treereg:
/* patrones con hijos */
IDENT '(' childlist ')' ('and' CODE)?
| REGEXP (':' IDENT)? '(' childlist ')' ('and' CODE)?
| SCALAR '(' childlist ')' ('and' CODE)?
| '.' '(' childlist ')' ('and' CODE)?
/* hojas */
| IDENT ('and' CODE)?
| REGEXP (':' IDENT)? ('and' CODE)?
| '.' ('and' CODE)?
| SCALAR ('and' CODE)?
| ARRAY
| '*'
Una regla como
zero_times: TIMES(NUM($x), ., .) and { $x->{attr} == 0 } => { $_[0] = $NUM }
crea un objeto transformación (concretamente un objeto de la clase Parse::Eyapp:YATW )
que puede ser referido a través de la variable escalar $zero_times.
La primera parte de la regla zero_times indica que
para que se produzca el emparejamiento es necesario que el nodo visitado sea
del tipo TIMES y su primer
hijo es de tipo NUM. Una referencia al nodo hijo de NUM será automáticamente
guardada en la variable léxica $x.
El efecto de un escalar en una treeregexp es casar con cualquier nodo y almacenar su referencia en la variable.
La aparición de $x en la treeregexp anterior
casará con cualquier nodo. La referencia al nodo que ha casado queda en $x.
Asi $x podrá ser usado en el patrón árbol semántico
o condición semántica(esto es,
en el código opcional que va precedido de la palabra reservada and)
y en la acción de transformación árbol (el código opcional que va precedido de la
flecha gorda =>).
Un punto también casa con cualquier nodo. Puede verse como una abreviación de
la expresión regular árbol escalar. Una referencia al nodo que casa
queda almacenada en la variable
léxica especial $W . Si la expresión regular árbol tiene
varios puntos sus referencias quedan almacenadas en la variable array @W.
Es un error usar el identificador W en una expresión regular escalar
escalar. Por ejemplo, una treeregexp como:
constantfold: /TIMES|PLUS|DIV|MINUS/(NUM($W), ., NUM($y))
da lugar al error:
*Error* Can't use $W to identify an scalar treeregexp at line 100.
La segunda parte de la regla es opcional y comienza con la palabra reservada and
seguida de un código que explicita las condiciones semánticas que debe cumplir el nodo
para que se produzca el casamiento. En el ejemplo se explicita que el attributo del nodo
(forzosamente del tipo TERMINAL en este caso) referenciado por $x debe ser cero.
Es posible dentro de las partes de código referirse a los nodos del árbol.
Cuando la rutina de transformación generada por el compilador para una
treeregexp es llamada, el primer argumento $_[0] contiene la referencia al nodo
que esta siendo visitado.
Parse::Eyapp::Treeregexp crea variables léxicas con nombres
los tipos de los nodos a los que referencian.
Así la subrutina generada para la transformación zero_times
zero_times: TIMES(NUM($x), ., .) and { $x->{attr} == 0 } => { $_[0] = $NUM }
guarda en la variable lexica $TIMES una copia de $_[0] y en
la variable léxica $NUM una referencia al nodo $TIMES->child(0) .
Si un tipo de nodo se repite en la treeregexp la variable léxica
asociada con dicho tipo se autodeclara como un array. Este es el caso de
la transformación constantfold
en la cual aparecen dos nodos de tipo NUM:
92 constantfold: /TIMES|PLUS|DIV|MINUS/(NUM($x), ., NUM($y))
93 => {
94 $x->{attr} = eval "$x->{attr} $W->{attr} $y->{attr}";
95 $_[0] = $NUM[0];
96 }
La variable @NUM es automáticamente declarada: $NUM[0] es una
referencia al primer nodo NUM y $NUM[1] es una referencia
al segundo.
La tercera parte de la regla es también opcional y viene precedida de la flecha gorda.
Habitualmente contiene el código que transforma el árbol.
Para lograr la modificación del nodo del árbol visitado el programador
Treeregexp deberá usar $_[0]. Recuerde que
los elementos en @_ son alias de los argumentos. Si el código
de la tercera parte fuera reescrito como:
{ $TIMES = $NUM }
no funcionaría ya que estaríamos modificando la variable léxica que referencia al
nodo raíz del subarbol que ha casado.
Es posible usar una expresión regular lineal alias expresión regular clásica alias regexp para explicitar el tipo de un nodo como indica la regla de producción:
treereg: REGEXP (':' IDENT)? '(' childlist ')' ('and' CODE)?
La treeregexp para el plegado de constantes constituye un ejemplo:
92 constantfold: /TIMES|PLUS|DIV|MINUS/(NUM($x), ., NUM($y))
93 => {
94 $x->{attr} = eval "$x->{attr} $W->{attr} $y->{attr}";
95 $_[0] = $NUM[0];
96 }
La expresión regular deberá especificarse entre barras de división (/)
y es posible especificar opciones después del segundo slash (e, i, etc.).
El identificador opcional después de la regexp indica el nombre para la
variable léxica que almacenará una copia de la referencia al nodo del árbol.
En el ejemplo $bin podría usarse para referenciar al nodo apuntado por $_[0].
Si no se especifica identificador quedará almacenado en la variable léxica
especial $W. Si la expresión regular árbol tiene
varias regexp (y/o puntos) sus referencias quedan almacenadas en la variable array @W.
La semántica de las expresiones regulares lineales
es modificada ligéramente por Parse::Eyapp::Treeregexp.
Por defecto se asume la opción x . El compilador de expresiones regulares árbol
procede a la inserción automática de la opción x.
Use la nueva opción X ((X mayúscula)
para evitar esta conducta.
Tampoco es necesario añadir anclas de frontera
de palabra \b a los identificadores que aparecen en la expresión
regular lineal: el compilador de expresiones regulares árbol
las insertará. Use la nueva opción B (B mayúscula) para negar esta conducta.
El siguiente ejemplo tomado del análisis de tipos en el compilador
de Simple C muestra como no es encesario usar x:
67 # Binary Operations
68 bin: / PLUS
69 |MINUS
70 |TIMES
71 |DIV
72 |MOD
73 |GT
74 |GE
75 |LE
76 |EQ
77 |NE
78 |LT
79 |AND
80 |EXP
81 |OR
82 /($x, $y)
83 => {
84 $x = char2int($_[0], 0);
85 $y = char2int($_[0], 1);
86
87 if (($x->{t} == $INT) and ( $y->{t} == $INT)) {
88 $_[0]->{t} = $INT;
89 return 1;
90 }
91 type_error("Incompatible types with operator '".($_[0]->lexeme)."'", $_[0]->line);
92 }
Con la semántica habitual de las regexp la palabra reservada
WHILE casaría con la subexpresión LE en la línea 76
provocando un análisis de tipos erróneo para esta clase de nodos.
La inserción automática de anclas por parte de Parse::Eyapp::Treeregexp
evita este - normalmente indeseable - efecto.
Las transformaciones creadas por Parse::Eyapp::Treeregexp pueden agruparse por familias.
Esta es la función de la regla de producción:
treeregexp: IDENT '=' IDENT + ';'
En el ejemplo creamos una nueva familia denominada algebraic_transformations
mediante la asignación de la línea 101:
algebraic_transformations = constantfold zero_times times_zero;Las transformaciones en esa familia pueden ser accedidas posteriormente para su aplicación mediante la variable de paquete
@algebraic_transformations (véanse las líneas
117-118).
En medio de la definición de cualquier regla treeregexp es posible insertar código de apoyo siempre que se sitúe entre llaves:
78 {
79 sub not_semantic {
80 my $self = shift;
81 return 1 if $self->{token} eq $self->{attr};
82 return 0;
83 }
84 }
85
86 delete_tokens : TERMINAL and { not_semantic($TERMINAL) } => { $delete_tokens->delete() }
Los objetos de la clase Parse::Eyapp::YATW como $delete_tokens disponen
de un método delete que permite eliminar con seguridad un hijo de la raíz del
subárbol que ha casado. En este caso los nodos que casan son los de la clase TERMINAL
en los que el valor de la clave token coincide con el valor de la clave attr.
Un programa Treeregexp puede - como en el ejemplo - proporcionarse como una
cadena de entrada al método new de la clase Parse::Eyapp::Treeregexp
o bien escribirse en un fichero separado (la extensión .trg es usada por
defecto) y compilado con el script treereg que acompaña a la distribución de
Parse::Eyapp.
La primera fase en la ejecución de un programa Treeregexp
es la fase de creación del paquete Treeregexp
que contendrá las subrutinas
de reconocimiento de los patrones árbol definidos en el programa Treeregexp.
En el ejemplo esta fase tiene lugar en las líneas
74-111 con las llamadas a new (que crea el objeto programa Treeregexp)
y generate (que crea el paquete conteniendo las subrutinas reconocedoras).
74 my $transform = Parse::Eyapp::Treeregexp->new( STRING => q{
75
76 delete_code : CODE => { $delete_code->delete() }
... ................................................
103 },
104 PACKAGE => 'TSwithtreetransformations',
105 OUTPUTFILE => 'main.pm',
106 SEVERITY => 0,
107 NUMBERS => 0,
108 );
109
110 # Create the transformer
111 $transform->generate();
Durante esta fase se crea un objeto transformación i(perteneciente a la clase Parse::Eyapp::YATW )
por cada expresión regular árbol que aparece en el programa Treeregexp.
Las variables contenedor de cada uno de esos objetos tienen por nombre el que se
les dió a las correspondientes expresiones regulares árbol. En nuestro ejemplo, y después
de esta fase habrán sido creadas variables escalares de paquete
$delete_tokens, $delete, $uminus, $constantfold, $zero_times
y $times_zero
asociadas con cada una de las expresiones regulares árbol definidas.
También se crearán variables array para cada una de las
familias de transformaciones especificadas: Asi la variable
@delete contiene ($delete_tokens, $delete) y la variable
@algebraic_transformations
es igual a ($constantfold, $zero_times, $times_zero). La variable de paquete especial
@all es un array que contiene todas las transformaciones definidas en el programa.
Una vez creados los objetos transformación y las familias de transformaciones
Parse::Eyapp::YATW podemos proceder a transformar el árbol
mediante su uso.
Esto puede hacerse mediante el método s el cual procede
a modificar el árbol pasado como parámetro.
114 our ($uminus); 115 $uminus->s($tree);En el ejemplo la llamada
$uminus->s($tree) da lugar al
recorrido primero-profundo de $tree. Cada vez que un nodo
casa con la regla:
UMINUS(., NUM($x), .) # first child is '-', second the number and third the codese le aplica la transformación:
{ $x->{attr} = -$x->{attr}; $_[0] = $NUM }
Esta transformación hace que el nodo UMINUS visitado sea sustituido
por un nodo de tipo NUM cuyo atributo sea el número de su hijo
NUM cambiado de signo.
Las líneas 117-118 nos muestran como someter un árbol a un conjunto de transformaciones:
117 our (@algebraic_transformations); 118 $tree->s(@algebraic_transformations);Los objetos nodo (esto es, los que pertenecen a la clase Parse::Eyapp::Node ) disponen del método s que recibe como argumentos una familia de transformaciones. La familia de transformaciones es aplicada iterativamente al árbol hasta que este no cambia.
Nótese que consecuencia de esta definición es que es posible escribir transformaciones
que dan lugar a bucles infinitos. Por ejemplo si en @algebraic_transformations
incluimos una transformación que aplique las propiedades conmutativas de la
suma:
commutative_add: PLUS($x, ., $y, .)
=> { my $t = $x; $_[0]->child(0, $y); $_[0]->child(2, $t)}
el programa podría caer en un bucle infinito ya que la transformación es
susceptible de ser aplicada indefinidamente. Sin embargo no se produce bucle infinito
si llamamos al código asociado a la transformación:
$commutative_add->($tree);
ya que en este caso se produce un sólo recursivo descendente aplicando la transformación
$commutative_add.
El uso de transformaciones conmutativas no tiene porque dar lugar a
la no finalización del programa. La parada del programa se puede
garantizar si podemos asegurar que la aplicación reiterada
del patrón implica la desaparición del mismo. Por ejemplo,
la transformación comasocfold puede ser añadida
a la familia algebraic_transformations sin introducir
problemas de parada:
comasocfold: TIMES(DIV(NUM($x), ., $b), ., NUM($y))
=> {
$x->{attr} = $x->{attr} * $y->{attr};
$_[0] = $DIV;
}
algebraic_transformations = constantfold zero_times times_zero comasocfold;
La introducción de esta transformación permite el plegado de entradas como a=2;b=2/a*3:
nereida:~/src/perl/YappWithDefaultAction/examples> usetswithtreetransformations3.pl
a=2;b=2/a*3
$VAR1 = bless( { 'children' => [
bless( { 'children' => [
bless( { 'children' => [
bless( { 'children' => [], 'attr' => 'a', 'token' => 'VAR' }, 'TERMINAL' ),
bless( { 'children' => [
bless( { 'children' => [], 'attr' => 2, 'token' => 'NUM' }, 'TERMINAL' ) ],
't' => 2
}, 'NUM' )
],
't' => 'a 2 ='
}, 'ASSIGN' ),
bless( { 'children' => [
bless( { 'children' => [], 'attr' => 'b', 'token' => 'VAR' }, 'TERMINAL' ),
bless( { 'children' => [
bless( { 'children' => [
bless( { 'children' => [], 'attr' => 6, 'token' => 'NUM' }, 'TERMINAL' )
],
't' => 6
}, 'NUM' ),
bless( { 'children' => [
bless( { 'children' => [], 'attr' => 'a', 'token' => 'VAR' }, 'TERMINAL' )
],
't' => 'a'
}, 'VAR' )
],
't' => '6 a /'
}, 'DIV' )
],
't' => 'b 6 a / ='
}, 'ASSIGN' )
]
}, 'EXP' )
],
't' => [ 'a 2 =', 'b 6 a / =' ]
}, 'PROG' );
Una vez compilado el analizador, escribimos el programa que usa el módulo generado:
nereida:~/src/perl/YappWithDefaultAction/examples> cat -n usetswithtreetransformations.pl
1 #!/usr/bin/perl -w
2 use strict;
3 use TSwithtreetransformations;
4 use Parse::Eyapp::Treeregexp;
5
6 my $parser = TSwithtreetransformations->new();
7 $parser->Run;
Al ejecutarlo obtenemos la siguiente salida:
nereida:~/src/perl/YappWithDefaultAction/examples> eyapp TSwithtreetransformations.eyp ; \\
usetswithtreetransformations.pl
input: a=2*-3;b=a*(2-1-1);c=a+b
$VAR1 = bless( { 'children' => [
bless( { 'children' => [
| bless( { 'children' => [
| | bless( { 'children' => [], 'attr' => 'a', 'token' => 'VAR' }, 'TERMINAL' ),
| | bless( { 'children' => [
| | | bless( { 'children' => [], 'attr' => -6, 'token' => 'NUM' }, 'TERMINAL' )
| | | ],
| | | 't' => -6
| | }, 'NUM' )
| | ],
| | 't' => 'a -6 ='
| }, 'ASSIGN' ),
| bless( { 'children' => [
| | bless( { 'children' => [], 'attr' => 'b', 'token' => 'VAR' }, 'TERMINAL' ),
| | bless( { 'children' => [
| | | bless( { 'children' => [], 'attr' => 0, 'token' => 'NUM' }, 'TERMINAL' )
| | | ],
| | | 't' => 0
| | }, 'NUM' )
| | ],
| | 't' => 'b 0 ='
| }, 'ASSIGN' ),
| bless( { 'children' => [
| | bless( { 'children' => [], 'attr' => 'c', 'token' => 'VAR' }, 'TERMINAL' ),
| | bless( { 'children' => [
| | | bless( { 'children' => [
| | | bless( { 'children' => [], 'attr' => 'a', 'token' => 'VAR' }, 'TERMINAL' )
| | | ],
| | | 't' => 'a'
| | | }, 'VAR' ),
| | | bless( { 'children' => [
| | | bless( { 'children' => [], 'attr' => 'b', 'token' => 'VAR' }, 'TERMINAL' )
| | | ],
| | | 't' => 'b'
| | | }, 'VAR' )
| | | ],
| | | 't' => 'a b +'
| | }, 'PLUS' )
| | ],
| | 't' => 'c a b + ='
| }, 'ASSIGN' )
| ]
}, 'EXP' )
],
't' => [ 'a -6 =', 'b 0 =', 'c a b + =' ]
}, 'PROG' );
Como puede verse la traducción de la frase de
entrada a=2*-3;b=a*(2-1-1);c=a+b
queda como atributo t del nodo raíz PROG.
Una expresión regular árbol array se escribe insertando un array Perl
en la expresión regular árbol, por ejemplo @a.
Una expresión regular árbol array @a casa con la secuencia mas corta de hijos del nodo
tal que la siguiente expresión regular árbol (no array) casa.
La lista de nodos
que han casado con la expresión regular árbol array quedará en la variable
léxica @a.
Por ejemplo, despúes de un casamiento de un árbol $t con la expresión regular árbol
BLOCK(@a, ASSIGN($x, $e), @b), la variable léxica
@a contendrá la lista de nodos hijos de $t
que precede a la primera aparición de ASSIGN($x, $e).
Si no
existe expresión regular árbol siguiente - el caso de @b en el ejemplo -
la expresión regular
array casará con todos los nodos hijo a partir del último casamiento (no array).
Asi @b contendrá la lista de referencias a los nodos hijos
de $t posteriores al nodo ASSIGN($x, $e).
Es ilegal escribir dos expresiones regulares arbol array
seguidas (por ejemplo A(@a, @b)).
El siguiente ejemplo muestra como usar las expresiones árbol array para mover las asignaciones invariantes de un bucle fuera del mismo (líneas 104-116):
nereida:~/src/perl/YappWithDefaultAction/t> cat -n 34moveinvariantoutofloopcomplexformula.t
1 #!/usr/bin/perl -w
2 use strict;
5 use Parse::Eyapp;
6 use Data::Dumper;
7 use Parse::Eyapp::Treeregexp;
8
9 my $grammar = q{
10 %{
11 use Data::Dumper;
12 %}
13 %right '='
14 %left '-' '+'
15 %left '*' '/'
16 %left NEG
17 %tree
18
19 %%
20 block: exp <%name BLOCK + ';'> { $_[1] }
21 ;
22
23 exp: %name NUM
24 NUM
25 | %name WHILE
26 'while' exp '{' block '}'
27 | %name VAR
28 VAR
29 | %name ASSIGN
30 VAR '=' exp
31 | %name PLUS
32 exp '+' exp
33 | %name MINUS
34 exp '-' exp
35 | %name TIMES
36 exp '*' exp
37 | %name DIV
38 exp '/' exp
39 | %name UMINUS
40 '-' exp %prec NEG
41 | '(' exp ')' { $_[2] } /* Let us simplify a bit the tree */
42 ;
43
44 %%
.. .......................................................................
87 }; # end grammar
88
.. ..................
99 $parser->YYData->{INPUT} = "a =1000; c = 1; while (a) { c = c*a; b = 5; a = a-1 }\n";
100 my $t = $parser->Run;
101 print "\n***** Before ******\n";
102 print Dumper($t);
104 my $p = Parse::Eyapp::Treeregexp->new( STRING => q{
105 moveinvariant:
106 BLOCK(@prests, WHILE(VAR($b), BLOCK(@a, ASSIGN($x, $e), @c)), @possts )
107 and { is_invariant($ASSIGN, $WHILE) } /* Check if ASSIGN is invariant relative */
108 => { /* to the while loop */
109 my $assign = $ASSIGN;
110 $BLOCK[1]->delete($ASSIGN);
111 $BLOCK[0]->insert_before($WHILE, $assign);
112 }
113 },
114 #outputfile => 'main.pm',
115 firstline => 104,
116 );
Al ejecutar el programa con la entrada
"a =1000; c = 1; while (a) { c = c*a; b = 5; a = a-1 }\n"
obtenemos el árbol modificado:
bless( { 'children' => [
bless( { 'children' => [ # a = 1000
| bless( { 'children' => [], 'attr' => 'a', 'token' => 'VAR' }, 'TERMINAL' ),
| bless( { 'children' => [
| bless( { 'children' => [], 'attr' => '1000', 'token' => 'NUM' }, 'TERMINAL' )
| ]
| }, 'NUM' )
| ]
}, 'ASSIGN' ),
bless( { 'children' => [ # c = 1
| bless( { 'children' => [], 'attr' => 'c', 'token' => 'VAR' }, 'TERMINAL' ),
| bless( { 'children' => [ bless( { 'children' => [], 'attr' => '1', 'token' => 'NUM' }, 'TERMINAL' )
| ]
| }, 'NUM' )
| ]
}, 'ASSIGN' ),
bless( { 'children' => [ # b = 5 moved out of loop
| bless( { 'children' => [], 'attr' => 'b', 'token' => 'VAR' }, 'TERMINAL' ),
| bless( { 'children' => [ bless( { 'children' => [], 'attr' => '5', 'token' => 'NUM' }, 'TERMINAL' )
| ]
| }, 'NUM' )
| ]
}, 'ASSIGN' ),
bless( { 'children' => [ # while
| bless( { 'children' => [ # ( a )
| bless( { 'children' => [], 'attr' => 'a', 'token' => 'VAR' }, 'TERMINAL' )
| ]
| }, 'VAR' ),
| bless( { 'children' => [ # BLOCK {}
| | bless( { 'children' => [ # c = c * a
| | | bless( { 'children' => [], 'attr' => 'c', 'token' => 'VAR' }, 'TERMINAL' ),
| | | bless( { 'children' => [
| | | bless( { 'children' => [
| | | bless( { 'children' => [], 'attr' => 'c', 'token' => 'VAR' }, 'TERMINAL' )
| | | ]
| | | }, 'VAR' ),
| | | bless( { 'children' => [
| | | bless( { 'children' => [], 'attr' => 'a', 'token' => 'VAR' }, 'TERMINAL' )
| | | ]
| | | }, 'VAR' )
| | | ]
| | | }, 'TIMES' )
| | | ]
| | }, 'ASSIGN' ),
| | bless( { 'children' => [ # a = a - 1
| | | bless( { 'children' => [], 'attr' => 'a', 'token' => 'VAR' }, 'TERMINAL' ),
| | | bless( { 'children' => [
| | | bless( { 'children' => [
| | | bless( { 'children' => [], 'attr' => 'a', 'token' => 'VAR' }, 'TERMINAL' )
| | | ]
| | | }, 'VAR' ),
| | | bless( { 'children' => [
| | | bless( { 'children' => [], 'attr' => '1', 'token' => 'NUM' }, 'TERMINAL' )
| | | ]
| | | }, 'NUM' )
| | | ]
| | | }, 'MINUS' )
| | | ]
| | }, 'ASSIGN' )
| | ]
| }, 'BLOCK' )
| ]
}, 'WHILE' )
]
}, 'BLOCK' );
Una expresión regular árbol estrella casa con la secuencia mas corta de hijos del nodos
tal que la siguiente expresión regular árbol casa. Si no
existe expresión regular árbol siguiente - esto es, la expresión regular
estrella es la última de la lista como en A(B(C,.), *)- la expresión regular
estrella casará con todos los nodos hijo a partir del último casamiento.
Una expresión regular árbol array se escribe insertando el símbolo *
en la expresión regular árbol. Las listas de nodos
que han casado con la expresiones regulares árbol estrella quedaran en las variables
léxicas @W_0, @W_1, @W_2, etc.
En este sentido una expresión regular árbol estrella no es mas que
una abreviación para la expresión regular árbol @W_#
siendo # el número de orden de aparición.
Como se ha mencionado anteriormente el compilador de expresiones
regulares árbol traduce cada transformación árbol en una subrutina Perl.
Con mayor precisión: se crea un objeto Parse::Eyapp:YATW que es el
encargado de gestionar la transformación. Para que una subrutina pueda
ser convertida en un objeto YATW deben ajustarse al Protocolo YATW de LLamada.
Actualmente (2006) la subrutina asociada con un objeto YATW es llamada como sigue:
pattern_sub(
$_[0], # Node being visited
$_[1], # Father of this node
$index, # Index of this node in @Father->children
$self, # The YATW pattern object
);
Los cuatro argumentos tienen el siguiente significado:
$_[0]) en la lista de nodos del padre
La subrutina debe devolver cierto (TRUE) si se produce matching
y falso en otro caso. Recuerde que el método s de los nodos (no así
el de los objetos YATW) permancerá aplicando las transformaciones
hasta que no se produzcan emparejamientos. Por tanto es importante
asegurarse cuando se usa la forma $node->s(@transformations)
que la aplicación reiterada de las transformaciones conduce
a situaciones en las que eventualmente las subrutinas retornan
el valor falso.
Es posible que el protocolo de llamada YATW cambie en un futuro próximo.