Antlr Arboles Sintacticos

Árboles de Sintaxis Abstracta en ANTLR
Antlr permite construir árboles de sintaxis abstracta (ASA) mediante anotaciones en la gramática indicando qué tokens deben tratarse como raíces de subárboles, cuáles son tokens hojas y cuáles deben ignorarse. Notación para describir Árboles de Sintaxis Abstracta. La notación usada para representar un ASA es #(A B C) donde A es la raíz y B y C son loshijos. Esta notación puede ser anidada permitiendo construir árboles con una estructura más compleja. Por ejemplo: #(A B #(C D E)) es un árbol con A de ráiz y B y el subárbol #(C D E) como sus hijos. La opción buildAST de Antlr habilita la construcción automática de ASAs. El siguiente ejemplo nos muestra una gramática con la opción de construir ASAs: class Anasint extends Parser; options{ buildAST =true; //construcción automática de ASA } instrucciones : (expresion ";")*; expresion : exp_mult (("+"|"-") exp_mult)*; exp_mult : exp_base (("*"|"/") exp_base)*; exp_base : NUMERO | "(" expresion ")" ; Las anotaciones para construir ASAs son: • • • • • Cualquier token con sufijo ^ se considera raiz del árbol. Por ejemplo, A B^C^ construye el árbol #(C #(B A)). Un token con sufijo ! no se incorporaal árbol. Una referencia a regla (símbolo no terminal) con sufijo ! indica que el árbol de dicha regla no se incorpora al árbol que se está construyendo. Una definición de regla con ! indica que no se construye árbol para dicha regla. Por ejemplo begin !: INT PLUS i:INT {#begin = #(PLUS INT i);} ; Una alternativa prefijada con ! inhabilita la construcción del árbol para dicha alternativa.

•Hay varias formas (no automáticas) de construir un nodo: #[TYPE] y #[TYPE, “text”]

Ejemplos de construcción de árboles: (Construcción manual de árbol) r! : a:A {#r = #a;} ; (Adición de nodos imaginarios) decl : (TYPE ID)+ {#decl = #(#[DECL, “decl”],#decl); } ; El siguiente ejemplo muestra una construcción híbrida (manual y automática) del ASA: class Anasint extends Parser; options{ buildAST =true; //construcción automática de AST } tokens { LISTA_INST; } instrucciones : (expresion ";"!)* {#instrucciones = #(#[LISTA_INST,"LISTA_INST"],#instrucciones);} //manual ; expresion : exp_mult (("+"^|"-"^) exp_mult)*; //automática exp_mult : exp_base (("*"^|"/"^) exp_base)*; //automática exp_base : NUMERO //automática | "("! expresion ")"! //automática ; Interfaz AST e Implementaciones Antlrpredefine una interfaz llamada AST (abstract sintax tree) para representar el tipo abstracto de datos árbol de sintáxis abstracta. La interfaz AST consta de las siguientes operaciones: public interface AST { /** añadir un hijo a la derecha del nodo ‘this’*/ public void addChild(AST c); /** igualdad entre dos nodos (mismo token, mismo texto)*/ public boolean equals(AST t);

/** dos listas de nodos osubárboles iguales en estructura y contenido*/ public boolean equalsList(AST t); /** dos listas de nodos o subárboles parcialmente iguales. ‘this’ contiene a ‘t’*/ public boolean equalsListPartial(AST t); /** dos nodos o subárboles iguales*/ public boolean equalsTree(AST t); /** dos nodos o subárboles parcialmente iguales. ‘this’ contiene a ‘t’*/ public boolean equalsTreePartial(AST t);/**enumeración de todos los emparejamientos de ‘tree’ en ‘this’*/ public ASTEnumeration findAll(AST tree); /** enumeración de todos los emparejamientos parciales de ‘tree’ en ‘this’*/ public ASTEnumeration findAllPartial(AST subtree); /** primer hijo de ‘this’. Null si no existiese */ public AST getFirstChild(); /** siguiente hermano de ‘this’ */ public AST getNextSibling(); /** texto asociado el token delnodo ‘this’ */ public String getText(); /** token asociado al nodo ‘this’ */ public int getType(); /** Número de hijos del nodo ‘this’*/ public int getNumberOfChildren(); /** inicializar el nodo ‘this’ con token ‘t’ y texto ‘txt’ */ public void initialize(int t, String txt); /** inicializar el nodo ‘this’ con el contenido del árbol ‘t’ */ public void initialize(AST t); /** inicializar el nodo...