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.