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 ->

Mis proyectos de sistemas en la USAC parte VI: Compiladores 1…

Que ironía, se me olvidó colocar el curso que auxilio en la universidad,  Introducción a los lenguajes y Compiladores 1.  Y si lenguajes era introductorio a éste, éste a su vez, es introductorio a la yuca de Compiladores 2 como lo describí anteriormente.  Lamentablemente, como tanto el auxiliar de ese curso, como el ingeniero, no sabian ni rosca, me tocó a mi estudiar por mi cuenta, mas por mi gusto que por ganarlo. y así fue. a continuación publico los únicos 2 proyectos que se realizaron.

1. Strim.

Un proyecto que la verdad, estaba bastante fácil, se trataba de un simple “concatenador” y “repetidor” de cadenas. el cual la mayor complicación era ponerse de acuerdo con el auxiliar para saber qué era lo que querían.  Desarrollado en C usando Flex y Bison, recuerdo cómo los demás compañeros aún no usaban la característica de atributos sintetizados, haciendoles más dificil la elaboración del mismo. El codigo esta en:

svn checkout http://proyectos-kreig-usac.googlecode.com/svn/trunk/c++/COMPI1-proy1-strim/ strim

2. Godzilla.

Bueno, aquí las cosas se empezaron a complicar, me rifaba entre hacer bien éste proyecto y dejar mediocre el de estructuras que estaba haciendo paralelamente… y así fue, me enfoqué más en este proyecto, el que consistía en un mini motor de un subconjunto de PHP, además que debía renderizar el HTML generado.  Desarrollado también en C++ usando QT 3 como framework, y Flex y Bison para el analizador léxico y sintáctico respectivamente, y enfocado desde su concepción a ser compilable y ejecutable tanto en Windows como en Unix.  Recuerdo aún que la mayor complicación de éste era el desarrollo de los ciclos, el cual, con un poco de autoaprendizaje de representaciones intermedias y árboles de sintaxis abstractas,  se simplificó y optimizó bastante la implementación de dicho lenguaje.  El código esta en:

svn checkout http://proyectos-kreig-usac.googlecode.com/svn/trunk/c++/COMPI1-proy2-godzilla/ godzilla

Bueno, eso fue compiladores 1, con un primer proyecto trivial, y el segundo no trivial… bastante parecido al semestre actual (enero-junio 2009) en este sentido. Un curso en el cual conocí la Biblia de los compiladores, el magnífico Libro del Dragón, y una introducción a lo que para muchos se convertiría en su peor pesadilla.

PD. Para poder bajarlos, deben instalar el cliente subversion de consola en gnu/linux y ya instalado ejecutar el comando dado en el directorio donde se vaya a bajar. Tambien recomiendo usar el TortoiseSVN si van a bajarlos en Windows

Mis proyectos de sistemas en la USAC parte V: Compiladores 2…

Y luego de la trabada que fue Compiladores 1, Estructuras de Datos, y Organización Computacional.  se deja venir el 6to semestre con muchas más trabadas, solo que ésta vez exponenciales… y no tanto por los cursos de sistemas, sino tambien por Investigación de Operaciones… un curso en donde el que sepa llevar la subjetividad de Vinicio Monzón, el ingeniero que dá el curso, hasta en su auxiliar se puede convertir (sino vean a Patricio AKA César Rojas), pero bueno, ya mucho hablar de basura, y vamos a lo que me incumbe, publicar los proyectos del que, para muchos, es el curso más difícil de la carrera (aunque a mi me haya costado mas la investigacion de operaciones), no tanto por su contenido teórico, sino por la extensión y dificultad de sus proyectos de programación. Me refiero a Organización de Lenguajes y Compiladores 2.   Se realizaron 2 proyectos en este curso cuando lo lleve ya hace algunos años, los cuales son:

1. VMW:

Un proyecto de supuesta máquina virtual, el nombre haciendo alución al VMWare y a los autos BMW., que consiste en un generador de analizadores léxicos, junto con un generador de analizadores LALR que además debe evaluar código embebido, en un lenguaje parecido a php, el cual a la vez teníamos que interpretar con un parser hecho por nosotros mismos también, todo esto obviamente en el lenguaje JAVA con el cual la escuela de sistemas se matrimonió desde el 2006… la verdad considero que fue el proyecto más trabajoso de la carrera (dado que el que más me costó fue el 2do de estructuras, el de los grafos), y eso que fue trabajado en parejas (con mr. chucho, el cual se dedico solamente al módulo de generación de analizadores léxicos, y la GUI, de los cuales el codigo no esta disponible por sus licencias restrictivas).  Bueno, el proyecto fue publicado previamente en este blog, y está mejor descrito en el siguiente URL, desde donde se puede bajar tambien:

https://objektblog.wordpress.com/2007/07/10/proyecto-generador-de-analizadores-lalr-en-java/

2.  EvilGCC

Supuestamente las siglas significaban Erik’s Visual Intermediate Language Generator and Compiler Collection (todavia me acuerdo), y consistia en un compilador básico de 3 lenguajes de programación (Java, C++, y Pascal) a código de 3 direcciones, aunque en realidad soportaba un subconjunto muy reducido de las construcciones de éstos.  También hecho en Java bajo NetBeans.  De lo que más me acuerdo es lo asustado que estaba respecto a que también debíamos implementar un optimizador del código de 3 direcciones generado, y que al final, era la parte más facil del proyecto, haciendo verdadero el dicho que dice El que se ahueva pierda…  El código esta aquí

svn checkout http://proyectos-kreig-usac.googlecode.com/svn/trunk/java/COMPI2-PROY2-evilgcc/

Bueno, este fue el curso por los que muchos compañeros se han ido de la carrera, otros han intentado olvidar en el alcohol los traumas psicológicos que le ocasionó tanta gramática…  La verdad el mayor problema que vi yo fue el maldito JLex y Cup… habiendo tantos generadores de analizadores… por qué teniamos que usar lo peor?

PD. Para poder bajarlos, deben instalar el cliente subversion de consola en gnu/linux y ya instalado ejecutar el comando dado en el directorio donde se vaya a bajar. Tambien recomiendo usar el TortoiseSVN si van a bajarlos en Windows