Árbol de Análisis Abstracto

Lenguajes Árbol y Gramáticas Árbol

Un árbol de análisis abstracto (denotado AAA, en inglés abstract syntax tree o AST) porta la misma información que el árbol de análisis sintáctico pero de forma mas condensada, eliminándose terminales y producciones que no aportan información.

Definición 33.9.1   Un alfabeto con función de aridad es un par $(\Sigma, \rho)$ donde $\Sigma$ es un conjunto finito y $\rho$ es una función $\rho: \Sigma \rightarrow \mathds{N}_0$, denominada función de aridad. Denotamos por $\Sigma_k = \{ a \in \Sigma : \rho(a) = k \}$.

Definimos el lenguaje árbol homogéneo $B(\Sigma)$ sobre $\Sigma$ inductivamente:

• Todos los elementos de aridad 0 están en $B(\Sigma)$: $a \in \Sigma_0$ implica $a \in B(\Sigma)$
• Si $b_1, \ldots , b_k \in B(\Sigma)$ y $f \in \Sigma_k$ es un elemento $k$-ario, entonces $f(b_1, \ldots , b_k) \in B(\Sigma)$

Los elementos de $B(\Sigma)$ se llaman árboles o términos.

Ejemplo 33.9.1   Sea $\Sigma = \{A, CONS, NIL \}$ con $\rho(A) = \rho(NIL) = 0, \rho(CONS) = 2$. Entonces

$B(\Sigma) = \{ A, NIL, CONS(A,NIL), CONS(NIL, A), CONS(A, A), CONS(NIL,NIL), \ldots \}$

Ejemplo 33.9.2   Una versión simplificada del alfabeto con aridad en el que estan basados los árboles construidos por el compilador de Tutu es:

$\Sigma = \{ID, NUM, LEFTVALUE, STR, PLUS, TIMES, ASSIGN, PRINT \}$

$\rho(ID) = \rho(NUM) = \rho(LEFTVALUE) = \rho(STR) = 0$

$\rho(PRINT) = 1$

$\rho(PLUS) = \rho(TIMES) = \rho(ASSIGN) = 2$.

Observe que los elementos en $B(\Sigma)$ no necesariamente son árboles ``correctos''. Por ejemplo, el árbol $ASSIGN(NUM, PRINT(ID))$ es un elemento de $B(\Sigma)$.

Definición 33.9.2   Una gramática árbol regular es una cuadrupla $((\Sigma, \rho), N, P, S)$, donde:

• $(\Sigma, \rho)$ es un alfabeto con aricidad $\rho: \Sigma \rightarrow \mathds{N}$
• $N$ es un conjunto finito de variables sintácticas o no terminales
• $P$ es un conjunto finito de reglas de producción de la forma $X \rightarrow s$ con $X \in N$ y $s \in B(\Sigma \cup N)$
• $S \in N$ es la variable o símbolo de arranque

Definición 33.9.3   Dada una gramática $(\Sigma, N, P, S)$, se dice que un árbol $t \in B(\Sigma \cup N)$ es del tipo $(X_1, \ldots X_k)$ si el $j$-ésimo noterminal, contando desde la izquierda, que aparece en $t$ es $X_j \in N$.

Si $p = X \rightarrow s$ es una producción y $s$ es de tipo $(X_1, \ldots X_n)$, diremos que la producción $p$ es de tipo $(X_1, \ldots X_n) \rightarrow X$.

Definición 33.9.4   Consideremos un árbol $t \in B(\Sigma \cup N)$ que sea del tipo $(X_1, \ldots X_n)$, esto es las variables sintácticas en el árbol leídas de izquierda a derecha son $(X_1, \ldots X_n)$.

• Si $X_i \rightarrow s_i \in P$ para algún $i$, entonces decimos que el árbol $t$ deriva en un paso en el árbol $t'$ resultante de sustituir el nodo $X_i$ por el árbol $s_i$ y escribiremos $t \Longrightarrow t'$. Esto es, $t' = t\{X_i/s_i\}$
• Todo árbol deriva en cero pasos en si mismo $t \stackrel{0}{\Longrightarrow} t$.
• Decimos que un árbol $t$ deriva en $n$ pasos en el árbol $t'$ y escribimos $t \stackrel{n}{\Longrightarrow} t'$ si $t$ deriva en un paso en un árbol $t''$ el cuál deriva en $n-1$ pasos en $t'$. En general, si $t$ deriva en un cierto número de pasos en $t'$ escribiremos $t \stackrel{*}{\Longrightarrow} t'$.

Definición 33.9.5   Se define el lenguaje árbol generado por una gramática $G = (\Sigma, N, P, S)$ como el lenguaje $L(G) = \{ t \in B(\Sigma): \exists S \stackrel{*}{\Longrightarrow} t \}$.

Ejemplo 33.9.3   Sea $G =(\Sigma,V,P,S)$ con $\Sigma = \{A, CONS, NIL \}$ y $\rho(A) = \rho(NIL) = 0, \rho(CONS) = 2$ y sea $V = \{ E, L \}$. El conjunto de producciones $P$ es:

$P_1 = \{ L \rightarrow NIL, L \rightarrow CONS(E,L),E \rightarrow a \}$

La producción $L \rightarrow CONS(E,L)$ es del tipo $(E,L) \rightarrow L$.

Informalmente, el lenguaje generado por $G$ se obtiene realizando sustituciones sucesivas (derivando) desde el símbolo de arranque hasta producir un árbol cuyos nodos estén etiquetados con elementos de $\Sigma$. Debería ser claro que, en este ejemplo, $L(G)$ es el conjunto de las listas en $A$, incluyendo la lista vacía:

$L(G) = \{ NIL, CONS(A, NIL), CONS(A, CONS(A,NIL)), \ldots \}$

Ejercicio 33.9.1   Construya una derivación para el árbol $CONS(A, CONS(A,NIL))$. ¿De que tipo es el árbol $CONS(E, CONS(A, CONS(E,L)))$?.

Cuando hablamos del AAA producido por un analizador sintáctico, estamos en realidad hablando de un lenguaje árbol cuya definición precisa debe hacerse a través de una gramática árbol regular. Mediante las gramáticas árbol regulares disponemos de un mecanismo para describir formalmente el lenguaje de los AAA que producirá el analizador sintáctico para las sentencias Tutu.

Ejemplo 33.9.4   Sea $G =(\Sigma,V,P,S)$ con

$\Sigma = \{ID, NUM, LEFTVALUE, STR, PLUS, TIMES, ASSIGN, PRINT \}$

$\rho(ID) = \rho(NUM) = \rho(LEFTVALUE) = \rho(STR) = 0$

$\rho(PRINT) = 1$

$\rho(PLUS) = \rho(TIMES) = \rho(ASSIGN) = 2$

$V = \{ st, expr \}$

y las producciones:

$P =$	$\{$
	$st$	$\rightarrow ASSIGN(LEFTVALUE, expr)$
	$st$	$\rightarrow PRINT(expr)$
	$expr$	$\rightarrow PLUS(expr, expr)$
	$expr$	$\rightarrow TIMES(expr, expr)$
	$expr$	$\rightarrow NUM$
	$expr$	$\rightarrow ID$
	$expr$	$\rightarrow STR$
	$\}$

Entonces el lenguaje $L(G)$ contiene árboles como el siguiente:

$ASSIGN$	$($
	$LEFTVALUE$,
	$PLUS$	$($
		$ID$,
		$TIMES$	$($
			$NUM$,
			$ID$
			$)$
		$)$
	$)$

El cual podría corresponderse con una sentencia como a = b + 4 * c.

El lenguaje de árboles descrito por esta gramática árbol es el lenguaje de los AAA de las sentencias de Tutu.

Ejercicio 33.9.2   Redefina el concepto de árbol de análisis concreto dado en la definición 34.1.7 utilizando el concepto de gramática árbol. Con mas precisión, dada una gramática $G =(\Sigma,V,P,S)$ defina una gramática árbol $T = (\Omega, N, R, U)$ tal que $L(T)$ sea el lenguaje de los árboles concretos de $G$. Puesto que las partes derechas de las reglas de producción de $P$ pueden ser de distinta longitud, existe un problema con la aricidad de los elementos de $\Omega$. Discuta posibles soluciones.

Ejercicio 33.9.3   ¿Cómo son los árboles sintácticos en las derivaciones árbol? Dibuje varios árboles sintácticos para las gramáticas introducidas en los ejemplos 33.9.3 y 33.9.4.

Intente dar una definición formal del concepto de árbol de análisis sintáctico asociado con una derivación en una gramática árbol

Definición 33.9.6   La notación de Dewey es una forma de especificar los subárboles de un árbol $t \in B(\Sigma)$. La notación sigue el mismo esquema que la numeración de secciones en un texto: es una palabra formada por números separados por puntos. Así t/2.1.3 denota al tercer hijo del primer hijo del segundo hijo del árbol $t$. La definición formal sería:

• $t/\epsilon = t$
• Si $t = a(t_1, \ldots t_k)$ y $j \in \{ 1 \ldots k \}$ y $n$ es una cadena de números y puntos, se define inductivamente el subárbol $t/j.n$ como el subárbol $n$-ésimo del $j$-ésimo subárbol de $t$. Esto es: $t/j.n = t_j/n$

Ejercicio 33.9.4   Sea el árbol:

$t = ASSIGN$	$($
	$LEFTVALUE$,
	$PLUS$	$($
		$ID$,
		$TIMES$	$($
			$NUM$,
			$ID$
			$)$
		$)$
	$)$

Calcule los subárboles $t/\epsilon$, $t/2\ldotp2\ldotp1$, $t/2\ldotp1$ y $t/2\ldotp1\ldotp2$.

Realización del AAA para Tutu en Perl

En la sección 33.6.1 nos limitamos a realizar un recorrido del árbol de análisis sintáctico concreto. En esta sección construimos un árbol de análisis sintáctico abstracto. Este proceso puede verse como la traducción desde el lenguaje de árboles concretos hasta el lenguaje de árboles abstractos.

Definición 33.9.7   La gramática árbol extendida que especifica los árboles AAA para el compilador de Tutu es esta:

1	$prog$	$\rightarrow PROGRAM(decls, sts)$
2	$decls$	$\rightarrow$ list $decl$
3	$sts$	$\rightarrow$ list $st$
4	$decl$	$\rightarrow INT(idlist)$
5	$decl$	$\rightarrow STRING(idlist)$
6	$idlist$	$\rightarrow$ list $SIMPLEID$
7	$st$	$\rightarrow ASSIGN(LEFTVALUE, expr)$
8	$st$	$\rightarrow PRINT(expr)$
9	$expr$	$\rightarrow PLUS(expr, expr)$
10	$expr$	$\rightarrow TIMES(expr, expr)$
11	$expr$	$\rightarrow NUM$
12	$expr$	$\rightarrow ID$
13	$expr$	$\rightarrow STR$

Hemos extendido el concepto de gramática árbol con el concepto de lista de no terminales. A la hora de construir las estructuras de datos las listas de variables se van a traducir por listas de árboles.

Por ejemplo, un árbol abstracto para el programa

int a,b;
string c, d;
a = 4;
p a

Sería de la forma:

PROGRAM(
         DECLS[INT[ID, ID], STRING[ID, ID]], 
         STS[ASSIGN(LEFTVALUE, NUM), PRINT(ID)]
       )

Donde los corchetes indican listas y los paréntesis tuplas.

Para llevar a cabo la traducción deberemos tomar decisiones sobre que forma de representación nos conviene. Cada nodo del AAA va a ser un objeto y la clase indicará si es un nodo suma, producto, una declaración, una asignación, etc.

Cada nodo del árbol AAA va a ser un objeto. De este modo el acceso a los atributos del nodo se hará a través de los métodos asociados. Además, el procedimiento de traducción al lenguaje objetivo depende del tipo de nodo. Así por ejemplo, el método traducción es diferente para un nodo de tipo $PLUS$ que para otro de tipo $ASSIGN$.

Resumamos antes de entrar en detalle, la forma de manejar los objetos en Perl:

• Para crear una clase se construye un ``package'':

  package NUM;
  

• Para crea un método se escribe una subrutina:

  package NUM;
  sub incr { my $self = shift; $self->{VAL}++ }
  

  el primer argumento de un método suele ser la referencia al objeto en cuestión.
• Para crear un objeto, se bendice (``bless'') una referencia. Los objetos Perl son datos normales como hashes y arrays que han sido ``bendecidos'' en un paquete. Por ejemplo:

  my $a = bless {VAL => 4}, 'NUM';
  

  crea un objeto referenciado por $a que pertenece a la clase NUM. Los métodos del objeto son las subrutinas que aparecen en el package NUM.
• Para referirse a un método de un objeto se usa la sintáxis ``flecha'':

  $a->incr;
  

  Cuando se usa la sintáxis flecha, el primer argumento de la rutina es la referencia al objeto, esto es, la llamada anterior es equivalente a NUM::incr($a)
• Constructores: En Perl son rutinas que retornan una referencia a un objeto recién creado e inicializado

  sub new { my ($class, $value) = @_; return bless {VAL => $value}, $class; }
  

  Normalmente se llaman usando la sintáxis flecha, pero a la izquierda de la flecha va el nombre de la clase. Por ejemplo:

  my $a = NUM->new(4)

  En este caso, el primer argumento es el nombre de la clase. La llamada anterior es equivalente a

  NUM::new('NUM', 4)

Volviendo a nuestro problema de crear el AAA, para crear los objetos de las diferentes clases de nodos usaremos el módulo Class::MakeMethods::Emulator::MethodMaker (véase la línea 9):

 1 package PL::Syntax::Analysis;
 2
 3 use 5.006;
 4 use strict;
 5 use warnings;
 6 use Data::Dumper;
 7 use IO::File;
 8 use Class::MakeMethods::Emulator::MethodMaker '-sugar';
 9
10 require Exporter;
11 our @ISA = qw(Exporter);
12 our @EXPORT = qw( );
13 our $VERSION = '0.02';
14
15 #######################################################
16
17 # Grammar:
18 # P : DD L      | L
19 # DD: D ';' DD  | D ';'
20 # D : int I     | string I
21 # L : S         | S ; L
22 # S : ID '=' E  | p E  | epsilon
23 # E : T '+' E   | T
24 # T : F '*' T   | F
25 # F : '(' E ')' | id | num | str
26 # I : id ',' I  | id

Hemos aislado la fase de análisis sintáctica en un módulo aparte denominado PL::Syntax::Analysis. La dependencia se actualiza en Makefile.PL:

PL0506/04sintactico/PL-Tutu$ cat -n Makefile.PL
  1  use 5.008004;
  2  use ExtUtils::MakeMaker;
  3  WriteMakefile(
  4      NAME              => 'PL::Tutu',
  5      VERSION_FROM      => 'lib/PL/Tutu.pm', # finds $VERSION
  6      PREREQ_PM         => {Class::MakeMethods::Emulator::MethodMaker => 0},1
  7      EXE_FILES         => [ 'scripts/tutu.pl', 'scripts/tutu' ],
  8      ($] >= 5.005 ?     ## Add these new keywords supported since 5.005
  9        (ABSTRACT_FROM  => 'lib/PL/Tutu.pm', # retrieve abstract from module
 10         AUTHOR         => 'Casiano Rodriguez Leon <casiano@ull.es>') : ()),
 11  );

Se actualiza también MANIFEST:

$ cat -n MANIFEST
 1  Changes
 2  lib/PL/Error.pm
 3  lib/PL/Lexical/Analysis.pm
 4  lib/PL/Syntax/Analysis.pm
 5  lib/PL/Tutu.pm
 6  Makefile.PL
 7  MANIFEST
 8  MANIFEST.SKIP
 9  README
10  scripts/test01.tutu
11  scripts/tutu
12  scripts/tutu.pl
13  t/01Lexical.t

Ahora compile llama a Syntax::Analysis::parser pasándole como argumento la lista de terminales @tokens. La función parser devuelve el AAA:

04sintactico/PL-Tutu/lib/PL$ sed -ne '/sub compile\>/,/^}/p' Tutu.pm | cat -n
  1  sub compile {
  2    my ($input) = @_;
  3    #my %symbol_table = ();
  4    #my $data = ""; # Contiene todas las cadenas en el programa fuente
  5    my $target = ""; # target code
  6    my @tokens = ();
  7    my $tree = undef; # abstract syntax tree
  8    #my $global_address = 0;
  9
 10
 11    ########lexical analysis
 12    @tokens = scanner($input);
 13    #print "@tokens\n";
 14
 15    ########syntax (and semantic) analysis
 16    $tree = &Syntax::Analysis::parser(@tokens);
 17    print Dumper($tree);
 18
 19    ########machine independent optimizations
 20    &Machine::Independent::Optimization::Optimize;
 21
 22    ########code generation
 23    &Code::Generation::code_generator;
 24
 25    ########peephole optimization
 26    &Peephole::Optimization::transform($target);
 27
 28    return \$target;
 29  }

El módulo Class::MakeMethods::Emulator::MethodMaker permite crear constructores y métodos de acceso. El módulo no viene con la distribución de Perl, así que, en general, deberá descargarlo desde CPAN e instalarlo. Así definimos que existe una clase de nodos TYPE que nuestro AAA va a tener:

package TYPE;
make methods
  get_set       => [ 'NAME', 'LENGTH' ],
  new_hash_init => 'new';

El uso de los argumentos get_set => [ 'NAME', 'LENGTH' ] hace que se cree un objeto de tipo hash con claves 'NAME' y 'LENGTH' así como métodos NAME y LENGTH que cuando se llaman con un argumento devuelven el valor y cuando se llaman con dos argumentos modifican el valor correspondiente. La clave get_set produce métodos de acceso y modificación de los atributos del objeto que tienen la forma:

sub TYPE::NAME {
  my ($self, $new) = @_;
  defined($new) and $self->{NAME} = $new;
  return $self->{NAME};
}

Asi mismo el uso de new_hash_init => 'new' genera un constructor cuyo nombre será 'new' y que cuando es llamado inicializará el objeto con los argumentos con nombre especificados en la llamada. El constructor construído (vaya retruécano) cuando se usa la clave new_hash_init tiene el siguiente aspecto:

sub TYPE::new {
  my ($class, %args) = @_;
  my $self = {};

  bless $self, $class;
  foreach my $attribute (keys %args) {
    $self->$attribute($args{$attribute});
  }
  return $self;
}

Ahora podemos crear objetos de la clase TYPE haciendo:

my $int_type = TYPE->new(NAME => 'INTEGER', LENGTH => 1); 
my $string_type = TYPE->new(NAME => 'STRING', LENGTH => 2);
my $err_type = TYPE->new(NAME => 'ERROR', LENGTH => 0);

Cada uno de estos objetos es un hash con las correspondientes claves para el nombre y el tipo.

Otros tipos de nodos del AAA son:

package PROGRAM; # raíz del AAA
make methods
  get_set       => [ 'DECLS', 'STS' ],
  new_hash_init => 'new';

package STRING; # tipo
make methods
  get_set       => [ 'TYPE', 'IDLIST' ],
  new_hash_init => 'new';

package INT; # tipo
make methods
  get_set       => [ 'TYPE', 'IDLIST' ],
  new_hash_init => 'new';

package ASSIGN; #sentencia
make methods
  get_set       => [ 'LEFT', 'RIGHT' ],
  new_hash_init => 'new';

package PRINT; #sentencia
make methods
  get_set       => [ 'EXPRESSION' ],
  new_hash_init => 'new';

package NUM; # para los números
make methods
  get_set       => [ 'VAL', 'TYPE' ],
  new_hash_init => 'new';

package ID; # Nodos identificador. Parte derecha
make methods
  get_set       => [ 'VAL', 'TYPE' ],
  new_hash_init => 'new';

package STR; # Clase para las constantes cadena
make methods
  get_set       => [ 'OFFSET', 'LENGTH', 'TYPE' ],
  new_hash_init => 'new';

package PLUS; # Nodo suma
make methods
  get_set       => [ 'LEFT', 'RIGHT', 'TYPE' ],
  new_hash_init => 'new';

package TIMES;
make methods
  get_set       => [ 'LEFT', 'RIGHT', 'TYPE' ],
  new_hash_init => 'new';

package LEFTVALUE; # Identificador en la parte izquierda
make methods       # de una asignación
  get_set       => [ 'VAL', 'TYPE' ],
  new_hash_init => 'new';

Hemos extendido el concepto de gramática árbol con el concepto de lista de no terminales. A la hora de construir las estructuras de datos las listas de variables se van a traducir por listas de árboles. Los tipos de nodos ($ASSIGN$, $PRINT$, ...) se traducen en nombres de clases. Hemos hecho una excepción con $SIMPLEID$ el cual es simplemente una variable cadena conteniendo el identificador correspondiente.

El siguiente esquema de traducción resume la idea para una gramática simplificada: cada vez que encontremos un nodo en el árbol sintáctico concreto con una operación crearemos un nodo en el AAA cuya clase viene definida por el tipo de operación. Para los terminales creamos igualmente nodos indicando de que clase de terminal se trata. El atributo nodo lo denotaremos por n:

$e \rightarrow e_1 + f$	{ $e{n} = PLUS->new(LEFT=>$e_1{n}, RIGHT=>$f{n}) }
$f \rightarrow NUM$	{ $f{n} = NUM->new(VAL => $NUM{VAL}) }
$f \rightarrow ID$	{ $f{n} = ID->new(VAL => $ID{VAL}) }

La estructura de cada rutina sigue siendo la misma, sólo que ampliada con las acciones para la construcción de los correspondientes nodos. Veamos por ejemplo, como modificamos la subrutina factor:

sub factor() {
  my ($e, $id, $str, $num);

  if ($lookahead eq 'NUM') {
    $num = $value;
    match('NUM');
    return NUM->new(VAL => $num, TYPE => $int_type);
  }
  elsif ($lookahead eq 'ID') {
    $id = $value;
    match('ID');
    return ID->new( VAL => $id, TYPE => undef);
  }
  elsif ($lookahead eq 'STR') {
    $str = $value;
    match('STR');
    return STR->new(OFFSET => undef, LENGTH => undef, TYPE => $string_type);
  }
  elsif ($lookahead eq '(') {
    match('(');
    $e = expression;
    match(')');
    return $e;
  }
  else {
    Error::fatal("Se esperaba (, NUM o ID");
  }
}

AAA: Otros tipos de nodos

Hemos optado por que las rutinas asociadas a variables sintácticas que describen listas de subcategorías devuelvan las correspondientes listas de nodos. Teníamos tres variables tipo lista. Las reglas para las listas eran:

Gramática de los Árboles de Tutu	Gramática del lenguaje Tutu
$decls$ $\rightarrow list decl$	declarations $\rightarrow$ declaration ';' declarations $\vert$ declaration ';'
$sts$ $\rightarrow list st$	statements $\rightarrow$ statement ';' statements $\vert$ statement
$idlist$ $\rightarrow list SIMPLEID$	idlist $\rightarrow$ ID ',' idlist $\vert$ ID

En este caso las subrutinas asociadas no devuelven objetos sino listas de objetos. Esto da lugar a una compactación del AAA. Veánse los códigos de statements y idlist:

sub statements() {
  my @s;

  @s = (statement());
  if ($lookahead eq ';') {
    match(';');
    push @s, statements();
  }
  return @s;
}

sub idlist() {
  my @id;

  if ($lookahead eq 'ID') {
    @id = ($value); # no es un objeto 
    match('ID');
    if ($lookahead eq ',') {
      match(',');
      push @id, idlist();
    }
  }
  else {
    Error::fatal('Se esperaba un identificador');
    @id = ('ERROR');
  }
  return @id;
}

Declaraciones

Los nodos del tipo declaration no existen propiamente, son nodos de la clase $INT$ o de la clase $STRING$. La parte de la gramática árbol de la que hablamos es:

2	$decls$	$\rightarrow$ list $decl$
4	$decl$	$\rightarrow INT(idlist)$
5	$decl$	$\rightarrow STRING(idlist)$
6	$idlist$	$\rightarrow$ list $SIMPLEID$

Los nodos declaration son un hash con una clave TYPE la cual apunta a la estructura de datos/objeto describiendo el tipo. La otra clave del hash IDLIST apunta a una lista de identificadores. Los elementos de esta lista son simples identificadores (identificados en la gramática árbol anterior como $SIMPLEID$ y no como objetos $ID$). La parte de la gramática implicada en las declaraciones es:

declaration $\rightarrow$ INT idlist $\vert$ STRING idlist

idlist $\rightarrow$ ID ',' idlist $\vert$ ID

Así pues, el código construye un nodo de la clase INT o STRING según sea el caso.

sub declaration() {
  my ($t, $class, @il);

  if (($lookahead eq 'INT') or ($lookahead eq 'STRING')) {
    $class = $lookahead;
    $t = &type();
    @il = &idlist();
    return $class->new(TYPE => $t, IDLIST => \@il);
  }
  else {
    Error::fatal('Se esperaba un tipo');
  }
}

Observe la llamada $class->new(TYPE => $t, IDLIST => \@il) en la cual la clase se usa a través de una referencia simbólica.

Práctica: Arbol de Análisis Abstracto

Complete la fase de análisis sintáctico para la gramática de Tutu extendida con sentencias de bloque (vea las reglas 1,2,3 y 11) construyendo el AAA según el lenguaje árbol especificado por una gramática árbol que extienda la dada en la definición 33.9.7. Genere pruebas, usando make test para comprobar el correcto funcionamiento de su analizador sobre las mismas. Utilize el módulo Data::Dumper para volcar las estructuras de datos resultantes.

1	p $\rightarrow$ b
2	b $\rightarrow$ ds ss
3	b $\rightarrow$ ss
4	ds $\rightarrow$ d ';' ds
5	ds $\rightarrow$ d ';'
6	d $\rightarrow$ INT il
7	d $\rightarrow$ STRING il
8	ss $\rightarrow$ s ';' ss
9	ss $\rightarrow$ s
10	s $\rightarrow$ ID = e
11	s $\rightarrow$ '{' b '}'
12	s $\rightarrow$ P e
13	s $\rightarrow \epsilon$
14	e $\rightarrow$ e1 '+' t
15	e $\rightarrow$ e1 '-' t
16	e $\rightarrow$ t
17	t $\rightarrow$ t1 '*' f
18	t $\rightarrow$ t '/' f
19	t $\rightarrow$ f
20	f $\rightarrow$ '(' e ')'
21	f $\rightarrow$ ID
22	f $\rightarrow$ NUM
23	f $\rightarrow$ STR
24	il $\rightarrow$ ID ',' il
25	il $\rightarrow$ ID