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

…viene de https://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

17 comentarios

  1. […] ) Tutorial ANTLR y Pyt… en Tutorial ANTLR y Python II. C…Erik Giron en Mi TOP 10 del 2007 para el […]

  2. […] ) Tutorial ANTLR y Pyt… en Tutorial ANTLR y Python III. C…Tutorial ANTLR y Pyt… en Tutorial ANTLR y Python II. C…Erik Giron en Mi TOP 10 del […]

  3. Ahhhhhhhhhhhh

  4. Excelente!!!!!! solo me queda una pregunta en el metodo calcular, a mi jamas me da el caso que solo tenga un hijo cada nodo, de hecho siempre me sale que tiene dos y pongo expresiones sencillas tales como 2+3*4==(1+4), por supuesto que respeta las precedencias, podrias explicar un poco más cuando se da solo un hijo por nodo, porque es que se da y porque crees que me salen dos siempre si yo lo hice siguiendo tu procedimiento. muchas Gracias Erick, es un excelente material!!!!!

    • Si consideras que no es necesario el caso de un solo nodo lo podes obviar, yo lo coloque en el caso que ANTLR me generara nodo para la produccion “sentencia”, la cual tiene un unico descendiente como lo muestra la gramatica. Lo importante es que al debugear te des cuenta si lo saca o no.

      Saludos.

      • muy buenas vibras amigos qisiera saber si me pueden colaborar con ua taller que tengo en antlr la verdd no soy muy experto
        el taller es el siguiente:
        *crear la gramatica para las operaciones logicas and, or. etc
        * crear las funciones para que el lenguaje tome funciones
        *crear las gramatika para tomar el break.

        muchas gracias por su atencion

  5. EL numero de simbolos de preanalisis de una gramatica LL(K) no afecta al AST verdad?

  6. Disculpa no se si mi pregunta es algo basico pero como reacciona un AST ante una produccion epsilon, suponte que en tu ejemplo:

    ‘*’
    |-> nume //(expresion del lado izquierdo)
    |-> nume //(expresion del lado derecho)

    el * tiene como hijos a nume pero que pasa si nume produce

    nume : ENTERO | ‘(‘! expresion ‘)’! | ;

    nume produce entero, (expresion) o epsilon

    que sucede con el ast en este caso? o simplemente debo hacer que el ast ignore la posibilidad epsilon?

  7. que diferencia hay entre la seccion 2 y la seccion 8?

  8. El ANTLR utiliza el patrón Visitor para la implementación de los AST? en caso de que no lo utilize existe alguna forma de especificarle que lo haga?

    • Si lo implementa, media vez se desee utilizar una gramatica de arbol (tree gramar) la cual tambien es una opcion para la segunda pasada, sin embargo, al menos para python, es mas comodo implementar una funcion recursiva para recorrer el arbol, para evitarnos problemas con eso de las sangrias obligatorias que a veces nos fallan dentro de las gramaticas de ANTLR. saludos.

  9. Genial, ahora me asalta otra duda, y es si es posible mediante la implementación de determinadas funciones y/o clases independizar un código generado con el ANTLR3 de los módulos del python-runtime ?

  10. El código fuente no se puede bajar😦 el link esta roto

    gracias por el aporte

Responder

Introduce tus datos o haz clic en un icono para iniciar sesión:

Logo de WordPress.com

Estás comentando usando tu cuenta de WordPress.com. Cerrar sesión / Cambiar )

Imagen de Twitter

Estás comentando usando tu cuenta de Twitter. Cerrar sesión / Cambiar )

Foto de Facebook

Estás comentando usando tu cuenta de Facebook. Cerrar sesión / Cambiar )

Google+ photo

Estás comentando usando tu cuenta de Google+. Cerrar sesión / Cambiar )

Conectando a %s

A %d blogueros les gusta esto: