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

Tutorial ANTLR y Python II. Creando una gramatica sencilla

Viene de https://objektblog.wordpress.com/2009/03/29/tutorial-antlr-y-python-i-introduccion-e-instalacion/

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, el codigo que se usara en los ejemplos esta publicado en el sig. URL:

http://rapidshare.com/files/215758595/ejemplos.tar.bz2

Ahh las gramaticas, tan odiadas por muchos. Y no es para asombrarse, ya que tantos problemas que dan, más aún si la herramienta no es nada amigable (como la tan odiada combinacion JLex/CUP), ANTLR es lo suficientemente amigable como para que desarrollemos gramáticas de la manera menos dolorosa posible, teniendo como valor agregado el ANTLRWorks, un IDE que de verdad permite aumentar nuestra eficiencia a la hora de hacer gramáticas para ANTLR. Esta parte se enfocará en generar una gramática simple con la cual se aprenderá de manera básica la estructura y sintaxis de ANTLR.

Pero… Y donde esta el analizador Léxico???

Como dije antes ANTLR simplifica las cosas, con ello, unifica tanto el analizador léxico como el sintáctico, por lo que para ambas tareas usaremos la misma herramienta, evitando los dolores de cabeza al intentar integrar ambos mundos.

Empezando…

Abrimos el ANTLRWorks que instalamos previamente en nuestro DIRECTORIO DEL IDE. y desde consola ejecutamos


$ cd [DIRECTORIO DEL IDE]
$ java -jar antlrworks-1.2.3.jar &

Abriremos de esta manera el entorno de trabajo de ANTLR, desde donde podemos hacer clic en el menu File -> New… para crear una nueva gramatica

ANTLRWorks.

ANTLRWorks.

Luego de esto, ya podemos empezar a escribir… Empezaremos definiendo lo primero, el nombre que queremos para nuestra gramatica, para ello escribimos els siguiente texto en el editor:
grammar ejemplo;

Luego de esto se puede definir diversas opciones para el ANTLR en la directiva Options que ofrece, en este caso especificamos que se generara codigo para python.
options{
language=Python;
}

Y luego viene la gramática…

Especificacion de la gramatica:

Ya especificado el lenguaje, podemos empezar a hacer ya nuestra gramatica. Nuestro objetivo es crear un lenguaje que pueda leer expresiones aritméticas simples de suma, resta y multiplicación. Debo aclarar que el método de análisis de ANTLR es LL(k) descendente, por lo que debemos previamente hacer las transformaciones necesarias a nuestra gramática (quitar recursividad por la izquierda, factorizar, etc).A continuación la gramática que se utilizará …

grammar ejemplo;
options{
language=Python;
}
program : sentencias
;
sentencias
: (expresion NEWLINE )+
| NEWLINE
;
expresion
: suma
;
suma
: mult (OPSUM mult)*
;
mult
: nume (OPMUL nume)*
;
nume : ENTERO
| '(' expresion ')'
;
ENTERO : ('0'..'9')+ ; // Lee enteros postivos
NEWLINE: '\r'? '\n' ; // lee cambios de linea
OPSUM : '+' | '-'; // operadores aditivos
OPMUL : '/' | '*'; // operadores multiplicativos

Debemos tomar en cuenta que LOS SIMBOLOS TERMINALES VAN EN MAYUSCULAS, asi tambien la gramatica tiene que estar factorizada y sin recursividad por la izquierda. la recursividad se puede quitar desde el mismo ANTLRWorks que tiene la opcion “Remove All Left Recursion” en el menú “Refactor”(forma sencilla), o también, escribiéndolos como Gramáticas Regulares es decir es decir transformar la forma recursiva por la derecha (forma avanzada)…

e : ep
;

ep : OP ep
| null
;

equivalente a a la expresion regular en la gramatica.

e : ep (OP ep)*
;

…como se hizo en el ejemplo, pues ANTLR permite la escritura de expresiones regulares desde la misma gramatica, además de hacerla más legible, se vuelve más intuitiva la forma de gramatica regular.

Pero bueno, en si lo único que hace esta gramática es revisar si la entrada va bien escrita… todavia faltan las acciones.

Agregando acciones semánticas en la gramatica:

Gracias a que ANTLR usa método descendente, se puede utilizar Atributos Heredados. Trabajaremos en base a atributos heredados, pues es como normalmente se trabaja en ANTLR. Tambien hay que tomar en cuenta que debido a que se estará generando código para Python, obviamente las acciones deberán ir en ese lenguaje.

Agregando acciones, la gramática nos quedaría de la siguiente manera:


grammar ejemplo;
options{
language=Python;
}
program : sentencias
;//fin program
sentencias
: (expresion NEWLINE {print $expresion.valor} )+
| NEWLINE
;//fin sentencias
expresion returns [valor]
: mult { $expresion.valor = $mult.valor }// suma
;//fin expresion
suma returns [valor]
: e1=mult {$valor = $e1.valor }
(OPSUM e2=mult
{ if ($OPSUM.getText() == '+') :
$valor = $valor + $e2.valor
if ($OPSUM.getText() == '-') :
$valor = $valor - $e2.valor
} //cerramos atributo

)*
;//fin suma
mult returns [valor] // nume ( OPMUL nume)*
: e1=nume {$valor = $e1.valor }
( OPMUL e2=nume
{ if ($OPMUL.getText() == '*') :
$valor = $valor * $e2.valor
if ($OPMUL.getText() == '/') :
if ($e2.valor 0) :
$valor = $valor / $e2.valor
else:
print "Division entre 0\n"
} //cerramos atributo
)* //cerramos expresion
;//fin mult
nume returns [valor] : ENTERO { $valor = int($ENTERO.getText()) }
| '(' expresion ')' { $valor = $expresion.valor }
;//fin nume
ENTERO : ('0'..'9')+ ; // Lee enteros postivos
NEWLINE: '\r'? '\n' ; // lee cambios de linea
OPSUM : '+' | '-'; // operadores aditivos
OPMUL : '/' | '*'; // operadores multiplicativos

Revisando la gramática tenemos cosas nuevas:

* suma returns [valor] nos indica que el dato regresado por la regla expresión devolverá un atributo llamado valor. ésto es también para las demás reglas que tengan la sentencia returns.

* e1=mult {$valor = $e1.valor } , Al mismo tiempo, también podemos colocar “alias” a los nombres de los terminales y no terminales que estemos utilizando en la producción, en este caso el e1=mult indica que el símbolo mult, estará identificado dentro de las acciones como e1 para la accion que tenga más próxima, en este caso es {$valor = $e1.valor } , En esta acción también podemos ver que $valor nos representa el atributo del símbolo no terminal que identifica la produccción al cual queremos “pasar” la información. en este caso estaremos pasando el valor de e1, al atributo valor del símbolo suma .

(OPSUM e2=mult
{ if ($OPSUM.getText() == '+') :
$valor = $valor + $e2.valor
if ($OPSUM.getText() == '-') :
$valor = $valor - $e2.valor
} //cerramos atributo

)*

Lo mismo que el anterior, le asignamos e2 al simbolo mult , Y como pueden darse cuenta ANTLR permite más de un segmento de codigo dentro de una regla gramatical, gracias a esto podemos evaluar cada repeticion que se encuentra en la sentencia mult (OPSUM mult)* , quedando como mult {} (OPSUM mult {})* en donde codigo2 se ejecutara cada vez que se lea OPSUM mult, pues esta dentro del operador de repeticion *.

La producción mult es similar a la suma, con excepcion de que agrega una validación adicional dentro del código para divisiones entre cero. Debemos tener las siguientes consideraciones cuando creamos codigo en python.

Podemos ver tambien que accedemos al valor del terminal OPSUM, con su atributo getText(), el cual devuelve el lexema leído actualmente por la regla OPSUM. con lo cual nos evitamos agregarles acciones semánticas a todos los terminales (ENTERO, NEWLINE, OPSUM, OPMUL).

Notas:

  • En las acciones, el codigo python, las sangrias deberan estar hechas por ESPACIOS, no por TABS.
  • Cuando se vaya a usar el operador % de python en las acciones, se debera anteceder con una backslash “\” de esta manera a % b se convertiria en a \% b

Ya lista la gramática, generamos código de la siguiente manera:

Seleccionamos la opcion “generate code” del menu “Generate”, y si todo sale bien no dara ningun error, de otra manera ANTLRWorks avisara cualquier falta que se este cometiendo. El código será generado en un nuevo directorio llamado “output” dentro de nuestro DIRECTORIO DEL IDE.

Pero bueno… y como conecto lo generado con un script python?

Creamos el siguiente script que servirá como punto de entrada, para ello, estando en nuestro DIRECTORIO DEL IDE, nos metemos al directorio output generado por ANTLR al generar código, y abrimos el editor nano con

$ cd output && nano ejemplo.py

y escribimos lo siguiente

import sys
import antlr3 # importamos librerias de antlr3
from ejemploLexer import ejemploLexer # importamos nuestro lexer generado por ANTLRWorks
from ejemploParser import ejemploParser # Importamos nuestro parser generado por ANTLRWorks

inputf = file(“input.txt”) # leemos archivo de entrada
char_stream = antlr3.ANTLRInputStream(inputf) #asignamos archivo de entrada a ANTLR

lexer = ejemploLexer(char_stream) # Asignamos strean devuelto por ANTLR al lexer
tokens = antlr3.CommonTokenStream(lexer) # Creamos stream de dokens con el lexer
parser = ejemploParser(tokens) # Creamos nuevo parser y le pasamos el lexer de parametro
parser.program() # Ejecutamos la produccion program del parser.
inputf.close() # Cerramos archivo ya que todo se haya leido

Nos salimos con CTRL+X y guardamos el script cuando nos lo pregunten.

Luego creamos el archivo de entrada

$ nano input.txt

y escribimos en él

1*1
2*2
3*3
2*2/3
2*2/2

Nos salimos con CTRL+X y guardamos el archivo de entrada cuando nos lo pregunten.

Corriendo el código:

Lo ejecutamos con el siguiente comando

python ejemplo.py

y en la pantalla veremos los resultados.

Los ejemplos pueden ser bajados directamente del siguiente URL:

http://rapidshare.com/files/215758595/ejemplos.tar.bz2

Siguiente –>

Tutorial ANTLR y Python I. Introducción e Instalación

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.

Dada la poca información que hay respecto al tema en Internet en español, me imagino que quizás por la poca apreciación que tiene la Teoría de Compiladores no sólo en mi país (Guatemala) sino en quiza toda latinoamérica. he decidido hacer un tutorial para intentar llenar ese vacio, y demostrar que existen herramientas más amistosas para generar analizadores léxico y sintácticos que la monolítica combinación FLEX/Bison, y que además, se pueden hacer en otros lenguajes que no sea el legendario C/C++.

Pero antes de esto, una introducción (rapida para no aburrir) a las herramientas.

El lenguaje Python:

Lenguaje dinámico y de scripts completamente orientado a objetos, su simplicidad se basa en las pocas construcciones de lenguaje que posee, y su poder en la capacidad de enlazarse a muchísimas librerías hechas en C, lo cual garantiza la eficiencia, además de tener una sintaxis simple, sensible a las sangrías. . Existen varias implementaciones, aunque las más populares son CPyhton (la version normal) y JPython (la que corre sobre la VM de java).

Se estará utilizando la version 2.5 de python en los ejemplos que se hagan, y para los que no esten familiarizados con el lenguaje se les recomienda el siguiente tutorial (en inglés pero muy bueno)

ANTLR:

Herramienta de generación de compiladores, es multiplataforma por estar desarrollado en Java, y es multilenguaje por tener la capacidad de generar código para la mayoría de lenguajes orientados a objetos populares actualmente, incluyendo, pero no limitándose a Java, C#, C++, Python, Ruby, Javascript, entre otros. Su método de análisis se basa en el LL(k) por lo que soporta el uso de atributos heredados. Otra característica es la facilidad para generar AST, es decir representaciones intermedias que permiten crear compiladores o intérpretes de más de una pasada. y la integración con StringTemplates para transformaciones complejas.

Se estará usando la versión 3 de ANTLR para los ejemplos que se incluyan. para más información visitar la wiki de ANTLR

Dado que este tutorial se enfocará únicamente en la combinación ANTLR/Python, para comprender mejor lo descrito a continuación, el lector deberá tener alguna familiaridad con Teoría de Compiladores (Véase el libro del Dragon), esto incluye Expresiones regulares, métodos de análisis descendente LL(k) y descendente (LA|G|S)?LR(x), también de tener experiencia en alguna otra herramienta de generación de compiladores, como YACC, y, pues un poco de conocimiento en lenguajes como c/c++, y obviamente Python no vendrían nada mal.

I. Instalación:

Prerrequisitos.

– Ubuntu GNU/Linux (en este tutorial se estará utilizando esta versión por simplicidad, aunque si se desea se puede usar cualquier otra distribución), y los repositorios adicionales (universe, multiverse, etc) correctamente configurados en el APT.

1. Instalando Java Runtime Environment 1.5 y Python de un tirón.

En este paso se instalará la plataforma Python (que por default ya viene instalada) y el JRE de Java, ya que para el funcionamiento del IDE ANTLRWorks se requiere la JRE 1.5 o mayor,
por lo que si tenemos bien configurados los repositorios, desde consola (alt+f2 gnome-terminal) escribimos…

$ sudo apt-get install python openjdk-6-jre

fig 1. Instalacoin por APT

fig 1. Instalacoin por APT

…y le decimos que SI cuando nos pregunte si en realidad se desea instalar el paquete.

2. Bajando e instalando ANTLRWorks

ANTLRWorks es un IDE multiplataforma hecho en Java para que desde ahí podamos desarrollar las gramáticas de ANTLR en una interfaz gráfica amistosa, teniendo el típico resaltado de código, visualización de la gramática de manera gráfica, generación de código, e incluso hasta debugging de la gramatica que desarrollamos. No es necesario bajar otra cosa, el ANTLRWorks trae tanto el IDE como el generador ANTLR.

Para descargar ANTLRWorks damos clic en http://www.antlr.org/download/antlrworks-1.2.3.jar. y lo colocamos en cualquier directorio (le llamare DIRECTORIO DEL IDE de aqui en adelante) (en mi caso lo guardaré en mi directorio de inicio “home” [/home/kreig/antlr] ) y ya desde ahi podemos ejecutarlo.

Descarga de ANTLRWorks

Descarga de ANTLRWorks

3. Bajando e instalando el runtime de Python para ANTLR

El runtime de ANTLR es el conjunto de clases necesarias para que nuestro código python generado por ANTLR funcione, y pueda ser incluido dentro de nuestro script.

Para esto, bajamos el Runtime

http://www.antlr.org/download/Python/antlr_python_runtime-3.1.2.tar.gz

y lo colocamos en el DIRECTORIO DEL IDE

Descomprimimos el paquete


$ cd [DIRECTORIO DEL IDE]
$ tar -xvzf antlr_python_runtime-3.1.2.tar.gz

Instalacion de runtime

Desempaquetado del runtime

y ejecutamos el instalador


$ sudo python antlr_python_runtime-3.1.2/setup.py install

Instalación del runtime de ANTLR para python

Instalación del runtime de ANTLR para python

y listo, los runtimes de ANTLR fueron instalados con exito, con estos 3 sencillos pasos tendremos ya instalado nuestro entorno de desarrollo de gramáticas con ANTLR y Python.

(Nota: En caso de que nos de errores de referencia en el codigo de que no se encuentra antlr3, sera necesario copiar el directorio antlr3 del paquete de runtime, hacia el directorio de las librerias de python. en mi caso /usr/lib/python-2.5)

En la siguiente entrega elaboraremos nuestra primer gramática con ANTLR…

Siguiente ->

Y Compiladores, para que p****?…

… Esto es lo que dice mucha gente en informatica, que estudia o estudió Ingeniería en Sistemas o Informática, o Ciencias de la Computacion, o como quiera llamarle, tiene cierto odio/resentimiento/ahuevamiento con ciertos cursos como Estructuras de Datos, Administracion de Archivos, y en general aquellos que están directamente relacionados con la ciencia computacional.

Sin embargo, de todos estos cursos, los que están a la cabeza son definitavemente los cursos relacionados Teoría de Compiladores, al cual mucha gente califica como  “Inaplicables”, “Inservibles”, “basura”, “m**rda” y va en descenso… Sobre todo en países como los nuestros, con sus problemas económicos, que no  invierten casi nada en Investigación y Desarrollo, haciendo que los cursos de Compiladores queden siempre a la cabeza de los listados de las encuestas de “cursos que se deberían eliminar de la carrera”.

Desafortunadamente, yo soy uno de esos pocos freaks a los que si les gusta esos temas, mi pasíon por ésta teoria de compiladores nació desde que conocí el curso de Lenguajes Formales y Autómatas (en realidad no le pongo el nombre actual que le dan en mi universidad por que suena muy estúpido), el cual se puede decir que es un curso introductorio a compiladores (Compiladores 0 como le suelo decir), y desde ahí me gusto la idea de transformar algo tan natural como el lenguaje humano a una serie de instrucciones capaces de ser interpretadas por el ordenador.

Me pareció bastante interesante,  que en el lugar donde laboro actualmente, se me asignó un proyecto ya hace algunos meses, en donde, se requiere el manejo de ciertas fórmulas para calcular el precio de energía de ciertas cosas segun cierta condicion.  Lo interesante es que estas fórmulas, obviamente, estarán persistidas en una base de datos de dudosa estabilidad (no digo la marca pero ya se imaginarán cual és, y lamentablemente sobre esa trabajamos), en formato varchar, o sea puro texto.

Ahí es donde viene lo bueno, toca crear algún tipo “intérprete” para las mismas, ya que, aunque va a tener un conjunto de sentencias y expresiones bastante sencillas, me niego a hacerlas “a pie” por tres puntos:

  1. Suponiendo que las tenga que hacer a pié, tendría que hacer un analizador tanto léxico como sintáctico “a pié”. algo no factible tanto por cuestion de tiempo como por cuestion de numero de “bugs” lo cual seguramente muchos que estudien en otras universades hubieran hecho “a pie”.
  2. A lo anterior, se agrega que existen muchas herramientas de análisis léxico y sintáctico bastante buenas (no solo la basura de “jlex” y “cup” que tanto alardean actualmente en mi universidad). los cuales con simplemente escribir una gramática y un conjunto de expresiones regulares, así como sus respectivas acciones semánticas para cada una de éstas, se puede desarrollar intérpretes de una manera bastante sencilla y rápida.
  3. Y la mas importante… Si recibí 2 benditos cursos de compiladores en la universidad. por que no poner en práctica lo aprendido?  Seria una gran estupidez no aprovechar la oportunidad de aplicar lo aprendido en los que quizá sean los cursos más dificultosos de la carrera (aunque desde mi punto de vista hay otros cursos peores, pero por culpa de la falta de profesionalismo de quienes las imparten).

La tarea no iba a ser facil, pues la plataforma sobre la que debería correr era .NET, y aunque existen diversas opciones para generación de compiladores bajo esta plataforma, en mi evaluación me dí cuenta que ninguna se ajustaba mejor que ANTLR.  Por qué tome esta decisión?

  1. Es software libre, con lo cual estoy seguro, que gracias a su licencia, lo generado lo voy a poder redistribuir en la implementación de mi intérprete para el producto que se va a vender.
  2. Es portable, el generador está desarrollado en Java, por lo cual se puede generar código desde cualquier plataforma compatible con la JVM.
  3. Es multilenguaje y orientado a objetos. Es decir, puede generar código para una gran cantidad de lenguajes orientados a objetos (Java, Python, Ruby, C++, C#, etc) y como la plataforma “destino” iba a ser .net, era necesario una herramienta que respetase este paradigma.
  4. es sencillo. Pues en el mismo archivo se define tanto el lexer como el parser, enlazándolos de una manera transparente. Eliminando aquella necesidad que con herramientas como Yacc y Lex de tener que interfazar ambos analizadores.
  5. Es eficiente. Gracias a que las gramáticas que escribimos en éste deben ser LLk compatibles, permite generar codigo bastante eficiente por su naturaleza descendente.
  6. Incluye un IDE para el desarrollo de gramáticas bastante bueno.
  7. Y algo mas avanzado, Genera Arboles de Sintaxis Abstracta (AST por sus siglas en ingles) on the fly.

En conclusión este post es para demostrar que, quien haya pensado que toda la teoría de compiladores que le fue impartida en la Universidad no iba a tener aplicación, esta equivocado, eventualmente pueden venir proyectos en donde se requiera el uso de lo aprendido en éstos. Esto es uno de los detalles que nos aventajan de los demás.