next up previous contents index PLPL moodlepserratamodulosperlmonksperldocapuntes LHPgoogleetsiiullpcgull
Sig: La opción SEVERITY Sup: Transformaciones Árbol con Parse::Eyapp Ant: Transformaciones Arbol con treereg Err: Si hallas una errata ...

Transformaciones de Árboles con Parse::Eyapp::Treeregexp

El módulo 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.

Optimización del Traductor de Infijo a Postfijo

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

  1. Compactar los árboles UMINUS a un número negativo
  2. Realizar plegado de constantes: sustituir los árboles de constantes por su evaluación
  3. Sustituir los árboles producto en los que uno de los factores es cero por el número cero.

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

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 
  | '*'

Las Reglas Treeregexp

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.

Escalares

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 =>).

El Punto

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.

Condiciones Semánticas

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.

Referenciado de los Nodos del Arbol

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.

Código de Transformación

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.

Expresiones Regulares

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.

Familias de Transformaciones

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).

Codigo de Apoyo

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() }

El método delete de los objetos YATW

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.

Fases en la Ejecución de un Programa Treeregexp

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 code
se 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' );

Ejecución del Ejemplo

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.

Expresiones Regulares Arbol Array

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' );

Expresión regular árbol estrella

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.

Parámetros Pasados a una Subrutina de Transformación Árbol

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:

  1. El nódo del árbol que esta siendo visitado
  2. El padre de dicho nodo
  3. El índice del nodo ($_[0]) en la lista de nodos del padre
  4. Una referencia al objeto YATW

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.



Subsecciones
next up previous contents index PLPL moodlepserratamodulosperlmonksperldocapuntes LHPgoogleetsiiullpcgull
Sig: La opción SEVERITY Sup: Transformaciones Árbol con Parse::Eyapp Ant: Transformaciones Arbol con treereg Err: Si hallas una errata ...
Casiano Rodríguez León
2012-05-22