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

Mis proyectos de sistemas en la USAC parte III: Estructuras de Datos…

Uno de los cursos más difíciles en la vieja escuela, continuación de IPC 2 en un semestre que no tenía nada de trivialidad al llevar cursos de Circuitos Digitales, y Compiladores simultáneamente con éste… y un curso que tuve que repetir en vacaciones con los proyectos ya ganados, (eso era lo bueno), y que, en la actualidad, esta mas orientado a web services y J2EE que a estructuras de datos puras. como cuando la llevé. pero bueno, hace tres años todavía teníamos que hacer Matrices Ortogonales, Árboles AVL, Hash tables, y todo tipo de estructuras desde cero, pues usar librerías como las collection de Java y las STL de C++ era un pecado para los auxiliares. En fin, de éste curso incluiré solamente 1 proyecto, el de un dizque Excel hecho en Java que utilizaria Matrices Ortogonales para manejar las celdas. y 1 práctica ratosa.

1. Proyecto ElectricSheet

Nombre basado en la canción electric Eye de Judas priest,  la verdad se trataba de una aplicación de Hojas electrónicas hechos en Java. que hace uso de la estructura de datos Matriz ortogonal, para representar las celdas del dizque excel.  Programado bajo Netbeans, y que además, ponía en práctica lo que llevaba en compiladores, al tener que implementar un mini parser hecho en JLex y Cup para interpretar las fórmulas, no era algo obligatorio, pero aproveche de una vez para aprenderlo, ya que me iba a servir en compiladores 2.  El código se encuentra hospedado en:

svn checkout http://proyectos-kreig-usac.googlecode.com/svn/trunk/java/EDD-proy1-ElectricSheet/ electricsheet

UPDATE: descargar de aqui usando git clone descrito abajo:

https://github.com/kreigiron/proy-usac/tree/master/java/EDD-proy1-ElectricSheet

2. Practica de Mapeo lexicográfico.

La verdad no es la gran cosa, solo calculaba la posición lineal de un elmento en una matriz de n x m… no me recuerdo como se usa, por lo que dejo el código hecho en C++.

svn checkout http://proyectos-kreig-usac.googlecode.com/svn/trunk/c++/EDD-mapeolex/ mapeolex

UPDATE: descargar de aqui usando git clone descrito abajo:

https://github.com/kreigiron/proy-usac/tree/master/c%2B%2B/EDD-mapeolex

Los Otros proyectos no los incluyo, pues el 2do me quedo bastante feo, y el 3ro, era un website que en realidad no era la gran cosa y dejo de existir para el bien de la humanidad.

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

UPDATE: Codigo disponible en github. para descargar utilizar el siguiente comando:

git clone https://github.com/kreigiron/proy-usac.git

 

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.