Tutorial ANTLR y Python III. Creando e implementando un intérprete de dos o más pasadas usando árboles de sintaxis abstracta...

Posted on 6 abr 2009

…viene de http://objektblog.wordpress.com/2009/03/30/tutorial-antlr-y-python-ii-creando-una-gramatica-sencilla/

Tutorial ANTLR y Python:

Parte I: Introducción e Instalación.

Parte II: Creacion de una gramática sencilla.

Parte III: Creacion e implementación de un AST.

Antes de empezar pueden bajar el código que se estará utilizando del siguiente URL http://rapidshare.com/files/218352788/ejemploAST.tar.bz2 Bueno, anteriormente habiamos visto como Instalar Python y ANTLR, luego colocamos un ejemplo sencillo para un intérprete de una sola pasada usando ANTLR y Python,  esta vez toca ver una de las características que hacen de ANTLR una herramienta poderosa, los AST o Árboles de sintaxis abstractas por sus siglas en inglés.

Definición AST

Pero.. ¿y qué es un AST?. Un AST es simplemente una estructura de datos en forma de arbol, que permite “abstraer” como su nombre lo dice, el árbol de sintaxis que el parser está utilizando, de tal manera que sea generado durante la etapa de análisis sintáctico, y posteriormente, sera recorrido y ejecutado independientemente luego que la etapa de análisis sintactico haya finalizado, Es decir, se crea mientras se va leyendo la entrada, para una posterior ejecucion luego de terminar la lectura de la entrada. Éste es una Representación Intermedia (IR por sus siglas en inglés).

¿Y de qué nos va a servir todo esto?

El AST es una técnica poderosa que permite:

  • Ejecutar sentencias complejas (como ciclos iterativos for, while, etc, anidados en los lenguajes de programación) que de otra manera con una sola pasada sería imposible realizarla directamente con las acciones semánticas del parser.
  • Realizar optimizaciones, de ser necesarias, al código leído.
  • Separar el análisis y el analizador sintáctico del análisis semántico, haciendo mas ordenada y limpio nuestro archivo de gramática.
  • etc, etc.

¿Qué se necesita para implementarlo?

Primero muchas ganas de hacerlo, pues el crearlo siempre implica el “fumarse” un AST adecuado a nuestras necesidades y despues adaptarlo en los analizadores sintácticos convencionales como Bison,  Sin embargo, ANTLR nos resuelve el problema de tener que realizar que inventar y llenar una estructura de datos para ello, pues ya incluye por su diseño la capacidad de generarnos un AST desde la misma gramática,  usando simples operadores para ello, el cual se adaptará a la mayoria de problemas comunes como se vera a continuacion.
Por convención, aqui se toma un arbol y un nodo como lo mismo, tal y como lo expresa la teoría (donde nos dice que un arbol puede ser un nodo con 0 o mas nodos hijos), por lo que hay que tomarlo en cuenta para evitar confusiones.
Iniciamos con reescribir nuestra gramática de la siguiente manera
abrimos ANTLRWorks
creando un nuevo archivo (File-:New), para despues pegar lo siguiente:
`//Seccion de codigo 1
grammar ejemploAST;
options{
language=Python;
output=AST;
}
//Seccion de codigo 2
tokens {
SENTENCIA;
OPMUL;
OPSUM;
}
program : sentencias
;//fin program
//Seccion de codigo 3
sentencias
(expresion NEWLINE)+ -> ^(SENTENCIA expresion+) | NEWLINE ;//fin sentencias //Seccion de codigo 4 expresion
suma // suma ;//fin expresion //Seccion de codigo 5 suma
mult ( OPSUM^ mult)* ;//fin suma //Seccion de codigo 6 mult
nume ( OPMUL^ nume)* ;//fin mult //Seccion de codigo 7 nume : ENTERO | ‘(’! expresion ‘)’! ;//fin nume //Seccion de codigo 8 ENTERO : (‘0’..‘9’)+ ; // Lee enteros postivos NEWLINE: ‘\r’? ‘\n’ ; // lee cambios de linea OPSUM : ‘+’ | ‘-’; // operadores aditivos OPMUL : ‘/’ | ‘*’; // operadores multiplicativos ESPACIO : (’ ’ | ‘\t’)+ { $channel=HIDDEN; }; // ignora espacios en blanco` Pero… ¿y qué es todo esto?, comencemos desde el inicio

Seccion de codigo 1

1 grammar ejemploAST; 2 options{ 3 language=Python; 4 output=AST; 5 } Bastante parecido a nuestra anterior gramática: le colocamos nombre a nuestra clase de gramatica como lo dice la primer linea, generamos codigo para python como dice la tercer linea, con la excepcion de la 4ta linea, en donde le especificamos al ANTLR que la generación de código vaya orientada a generar un AST cuando se implemente el analizador sintáctico.

Seccion de codigo 2

1 tokens { 2 SENTENCIA; 3 OPMUL; 4 OPSUM; 5 } Ésta es simplemente una lista de tokens que identificará cada uno de los nodos del AST como se verá mas adelante.

Seccion de codigo 3

1 sentencias 2 : (expresion NEWLINE)+ -> ^(SENTENCIA expresion+) 3 | NEWLINE Aqui vemos donde empieza a variar nuestra gramática. en la linea 2 podemos ver que ya no usamos más acciones semánticas asociadas a cada producción, en vez de eso usamos el operador “->” el cual nos traduce nuestra gramática a su forma de árbol de sintaxis abstracta. Es decir. que cada vez que se pase por esta producción, el parser automáticamente generará un nuevo nodo (especificado por el operador ^) el cual se identificará con el toquen SENTENCIA, y podrá tener uno o más expresiones como nodos hijos, de la siguiente manera.SENTENCIA | |-> expresion1 |-> expresion2 | . | . | . |-> expresionN Como podemos ver con éste ejemplo, los árboles AST de ANTLR son árboles N-narios, es decir, un nodo pueden tener de 0 a n cantidad de nodos hijos, lo que le dá bastante flexibilidad a la hora de implementarlos.

Seccion de codigo 4

1 expresion 2 : suma // suma 3 ;//fin expresion ¿y que paso aqui?, como podemos ver en la linea 2 no tenemos ni una sola accion asociada a crear nodos en esta produccion, Bueno, al hacer esto, ANTLR automáticamente traslada el nodo inferior (hijo) al nodo padre, es decir, el nodo “suma” pasará a ser nodo “expresión” automáticamente para ser directamente nodo hijo de SENTENCIA.

Seccion de codigo 5

1 suma 2 : mult ( OPSUM^ mult)* 3 ;//fin suma Aqui tenemos otro ejemplo de creación de nodo, en este caso mezcla el caso anterior (en donde se traslada el nodo inferior “mult” al nodo padre “suma”), y de creacion de nuevo nodo (como en SENTENCIA), solo que esta vez es con otra nomenclatura para crearlos, adjuntando el operador “^” al token con el cual queremos que se identifique el nodo cuando se llegue a leer “( OPSUM^ mult)*”, en donde OPSUM podría ser el “+” o el “-” que es definido en donde definimos expresiones regulares para los terminales: de tal manera que se crearia el nodo con las siguientes alternativas como lo indica la sig. figura '+' |-> mult //(expresion del lado izquierdo) |-> mult //(expresion del lado derecho) (o tambien) '-' |-> mult //(expresion del lado izquierdo) |-> mult //(expresion del lado derecho)

Seccion de codigo 6

0 mult 1 : nume ( OPMUL^ nume)* 2 ;//fin mult Lo mismo que en el caso anterior, se copia el nodo hijo nume de la izquierda si es expresion de un solo simbolo, o se crea nodo identificado ya sea por el operador de multiplicacion ‘*’ o el de division ‘*’, con los dos nodos nume izquierdo y derecho como hijos. '*' |-> nume //(expresion del lado izquierdo) |-> nume //(expresion del lado derecho) (o tambien) '/' |-> nume //(expresion del lado izquierdo) |-> nume //(expresion del lado derecho)

Seccion de codigo 7

nume : ENTERO | '('! expresion ')'! ;//fin nume Aqui es casi el mismo caso que cuando copiamos directamente el nodo inferior al nodo padre, con excepcion que esta vez tenemos un par de “estorbos”, estos son los símbolos ‘(’ y ‘)’ los cuales debemos de obviar antes de queres copiar el nodo hijo al nodo padre. Para ello se les adjunta el simbolo ’ ! ’ (admiracion) el cual permite que no sean tomados en cuenta a la hora de copiar el nodo, y asi ANTLR no genere errores extraños al momento de generar nuestras clases en python.

Seccion de codigo 8

ENTERO : ('0'..'9')+ ; // Lee enteros postivos NEWLINE: '\r'? '\n' ; // lee cambios de linea OPSUM : '+' | '-'; // operadores aditivos OPMUL : '/' | '*'; // operadores multiplicativos ESPACIO : (' ' | '\t')+ { $channel=HIDDEN; }; // ignora espacios en blanco Bueno, el lexer, el cual no tiene gran cambio, como podemos ver no hay necesidad de colocarles acciones por que automáticamente al ser éstos los terminales, quedarán como “hojas” del arbol, es decir nodos que no tienen nodos hijos. Luego ya estaremos listos para generar el código desde el menu GENERATE-: GENERATE CODE. para generar salida a nuestro directorio output por defecto.

Y después de escribir la gramática ¿que viene?

De aquí se pueden tomar dos caminos:

  1. Crear una gramática de árbol: Es decir, ANTLR nos permite escribir otra gramática más llamada TreeGrammar, la cual deja mezclar las acciones semánticas con nuestra gramática que únicamente tendrá que parsear nuestro arbol ya generado. Una opción bastante sencilla, sin embargo es la menos poderosa, ya que aparte de estar limitados a seguir la estructura de dicha gramática, mezclaremos el código de implementación de nuestro intérprete dentro de la misma, lo cual resulta un dolor de cabeza para lenguajes como Python, que son sensibles a las tabulaciones.
  2. Heredar e implementar nuestro propio recorredor de árbol: Éste sera el camino que se tomará y es definitivamente la opción más flexible, pues permite de poder manipular el arbol que ANTLR nos genera como nos dé la gana, sin necesidad de aprender nueva sintaxis para usarlo, también permite una mayor personalización de los mismos árboles al poder implementar un “Adaptador” personalizado para crear nodos a nuestro gusto. Además de permitirnos separar el código de las acciones semánticas en Python del código de ANTLR, lo que resulta más legible y modularizable.

Implementando el “Walker” en Python

Luego de realizar nuestra gramática estamos listos para el siguiente gran paso, implementarlo en Python.  Para ello abrimos nuestro IDE de python preferido (en mi caso uso SPE) y creamos un nuevo archivo. en éste escribimos lo siguiente para luego guardarlo como EjemploAST.py en nuestro directorio output. NOTA: Lamentablemente Wordpress se come las sangrias, por lo que para tener un panorama mas claro del codigo, y tambien para que se ejecute pues python es sensible a las sangrias, recomiendo bajar primero el codigo fuente. Como el ejemplo es algo largo solo hare énfasis en lo importante:

Segmento de Codigo 1, Imports:

#---SEGMENTO DE CODIGO 1 import sys import antlr3 from antlr3 import ANTLRFileStream; from antlr3 import TokenRewriteStream; from ejemploASTLexer import ejemploASTLexer # importamos nuestro lexer generado por ANTLRWorks from ejemploASTParser import ejemploASTParser # Importamos nuestro parser generado por ANTLRWorks Podemos ver que ahora importamos una nueva clase, TokenRewriteStream, necesaria para la implementacion del AST.

Segmento de Codigo 2; Clase Adaptor:

`#Implementacion de la interfaz treeadaptor que permite adaptar el arbol AST

para cualquier implementacino derivada de CommonTree que quisieramos usar

class adaptor(antlr3.tree.CommonTreeAdaptor): def createWithPayload(self,payload): return antlr3.tree.CommonTree(payload)` Una característica importante de ANTLR es su capacidad de extender los árboles que ya trae en sus librerías a nuestro gusto, para ello la implementación de la interfaz CommonTreeAdaptor nos sirve para personalizar el método que usará nuestro analizador sintáctico cada vez que vaya a crear un nodo con el método CreateWithPayload. Ésta vez haremos que simplemente devuelva un nodo de tipo CommonTree que es el que se usa en ANTLR.  Pero es muy probable que en la realidad querramos cambiarlo ya con lenguajes más serios.

Segmento de Codigo 3; recorredorAST:

class recorredorAst: #Recorre todas las expresiones linea por linea Aqui definimos la clase que nos servira como Walker o recorredor del arbol que genere el parser cuando termine de leer  el archivo de entrada.

Segmento de Codigo 3.1; Metodo recorrer() del recorredorAST:

`def recorrer(self, arbol): #nos aseguramos que el arbol no sea nulo if (arbol None): #recorremos todas las sentencias de expresiones dada en la gramatica por

^(SENTENCIA expresion+)

for i in xrange(0,arbol.getChildCount()): valor = self.calcular(arbol.getChild(i)) print ‘Sentencia %d: %f \n’ % (i,valor) #–fin recorrer` Este será nuestro punto de entrada cuando leámos el AST que le pasemos como parámetro, como vemos éste iniciará el el nodo Sentencia, por lo que al llamar al parser, debemos llamarlo desde el nodo “sentencia” para que el arbol inicie desde allí. Podemos ver que llama a un método calcular de la misma clase el cual se describe a continuación.

Segmento de código 3.2; Método calcular() del recorredorAST:

`#calcula recursivametne el valor de la expresion definida en arbol def calcular(self,arbol):

hacemos recorrido post-orden del AST evaluando primero la cantidad

de nodos hijos

si el nodo no tiene hijos, es nodo de un terminal, por lo que

devolvemos su valor

if arbol.getChildCount() == 0: return float(arbol.text)

si el nodo tiene 1 hijo, es nodo transitorio, por lo que

recursivamente volvemos a llamar a recorrer dentro del nodo hijo

elif arbol.getChildCount() == 1: return self.calcular(arbol.getChild(0))

si el nodo tiene 2 hijos, el nodo es de operacion

^(operador, (valor izquierdo, valor derecho) )

elif arbol.getChildCount() == 2: #obtenemos el valor de los nodos hijos valor1 = self.calcular(arbol.getChild(0)) #obtenemos valor del nodo izq valor2 = self.calcular(arbol.getChild(1)) #obtenemos valor del nodo der

si la operacion definida en el nodo es * se multiplican

los valores devueltos por el recorrido de los nodos hijos

if(arbol.text == ‘*’): return valor1 * valor2

si la operacion definida en el nodo es / se dividen

los valores devueltos por el recorrido de los nodos hijos

elif(arbol.text == ‘/’): if valor2 0: return valor1 / valor2 else: raise “division entre 0”

si la operacion definida en el nodo es + se suman

los valores devueltos por el recorrido de los nodos hijos

elif(arbol.text == ‘+’): return valor1 + valor2

si la operacion definida en el nodo es - se restan

los valores devueltos por el recorrido de los nodos hijos

elif(arbol.text == ‘-’): return valor1 - valor2 else: #calculamos siempre para el primer hijo en caso que no se especific return self.calcular(arbol.getChild(0)) #–fin calcular` La función principal del método recursivo “calcular” es obtener los valores de los nodos hojas o Terminales cuando el número de nodos hijos del nodo que se este calculando actualmente sea 0, tambien realizará la transición de nodos cuando el numero de nodos hijos sea 1, y operará cuando la cantidad de nodos hijos sea 2, según el valor del atributo “text” del nodo actual, pues este es el que trae el valor semántico del nodo que se este ejecutando actualmente.

Segmento de Código 4, Punto de entrada de la aplicación

`# MAIN

asignamos archivo

inputf = antlr3.ANTLRFileStream(“input.txt”) #asignamos archivo de entrada a ANTLR #instanciamos parser lex = ejemploASTLexer(inputf); #asignamos flujo de entrada a lexer tokens = TokenRewriteStream(lex); # creamos flujo de tokens en base al lexer parser = ejemploASTParser(tokens); # creamos la gramatica en base al flujo #asignamos adaptador de arbol al parser ta = adaptor() #instanciamos adaptor parser.setTreeAdaptor(ta) #asignamos adaptor al parser ret = parser.sentencias() # Ejecutamos primer pasada desde la produccion sentencias arbolAst = ret.tree # obtenemos resultante de la etapa de parser recorredor = recorredorAst() #instanciamos nuestro recorredor operacion = recorredor.recorrer(arbolAst) #recorremos el arbol` Este sera el punto de entrada del script, en donde abrimos el archivo de entrada, instanciamos el parser, instanciamos un flujo de tokens para ser usandos por el parser, el cual tambien se instancía. Luego creamos un objeto Adaptor para asignarle el adaptador de arbol al parser, el cual llamará al metodo CreateWithPayback cada vez que cree un nodo al leer el archivo de entrada. Finalmente obtenemos en el objeto ret el arbol de sintaxis abstracta iniciando por la produccion “sentencias” al llamar al metodo “sentencias()” del parser. Si el archivo de entrada se lee exitosamente, sin errores léxicos ni sintácticos, el árbol estará listo para ser recorrido, para ello instanciamos nuestro Recorredor y lo recorremos con el método “recorrer()” del mismo, el cual tomaŕa como parámetro el arbol devuelto por nuestro parser.

Segmento de Código 5, Serialización del AST:

#---SEGMENTO DE CODIGO 5 #----------------------- #persistencia del AST #libreria para serializacion import pickle #guardamos AST f1 = file("/tmp/salida.ast","w") pickle.dump(arbolAst, f1,2) f1.close() #leemos ast de nuevo f2 = file("/tmp/salida.ast","r") nuevoAst = pickle.load(f2) operacion = recorredor.recorrer(nuevoAst) #recorremos el arbol Ésto es optativo si deseamos serializar y persistir nuestro árbol de sintaxis abstracta a un archivo, para ello se utilizará la libreria “pickle” de python, la cual permite serializar y deserializar objetos hacia y desde archivos. Para ello definimos un archivo de salida como f1, y llamamos al método “Dump” de pickle, el cual almacenará nuestro AST al archivo, asimismo si lo deseamos leer, abrimos un archivo f2 que apunte al archivo previamente serializado, y utilizamos el método “load” de pickle sobre un objeto AST destino, el cual ya restaurado podemos recorrerlo nuevamente. Lo ejecutamos con $ python EjemploAST.py y listo. Todo esto es lo básico para generar intérpretes de N Pasadas, y aunque por cuestiones de espacio y tiempo nos dedicamos a crear una gramática sencilla de operaciones aritméticas, en la realidad los AST permiten reducir la complejidad en el análisis sintáctico, al delegar la función semántica a ésta representación intermedia que nos permite una gran flexibilidad sobre la entrada previamente leída. El código para los ejemplos incluidos aquí podrán ser bajados desde el siguiente URL: http://rapidshare.com/files/218352788/ejemploAST.tar.bz2 Para mayor información del API de ANTLR en Python y los AST http://www.antlr.org/api/Python/index.html http://www.antlr.org/wiki/display/ANTLR3/Tree+construction