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

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

Mis proyectos de sistemas en la USAC parte IV: Lenguajes Formales…

Se me olvidaba un curso de 4to semestre, paralelo a IPC2, uno de los que enseñan lo que es desvelarse echando punta, Lenguajes formales, impartido por el mismísimo Satán.  Era un curso introductorio a Compiladores, y por lo tanto, a nivel de éstos en cuanto a extensión y dificultad en sus proyectos, aunque con menor magnitud obviamente…  Aquí se realizaban 3 proyectos, los cuales se enfocaban en usar 3 diferentes lenguajes para comprobar 3 diferentes paradigmas supuestamente.

1. StaticS:

Éste realizaba cálculos de estadística descriptiva, leyendo un archivo de texto en donde estaba los datos, y sacándolos en un bonito HTML Éste proyecto fue desarrollado en otro lenguaje que destesto,  Pascal;  Quérian obligarme tal y como lo hicieron en IPC 1 a usar el Turbo Pascal, pero no pudieron, mi subversión me llevó a programarlo en Linux usando Free Pascal, un compilador libre y gratuito de Pascal, que tenía muchas más características que el raquítico compilador de Borland. El proyecto se encuentra aqui:

svn checkout http://proyectos-kreig-usac.googlecode.com/svn/trunk/pascal/LFP-proy1-StaticS/ statics

2. O-tell-O

Era el primer proyecto de la U que desarrollaba en Java, y como subversivo en cuanto a compiladores, lo desarollé en Netbeans mientras la mayoría prefería usar el Borland JBuilder (Cual era las gana de usar herramientas de Borland me pregunto yo?) ,  Éste proyecto no era más que el jueguito de otello, reversi, o como le quieran llamar, obviamente sin IA ni nada de eso, dado que no daba tiempo para implementarlo.  A continuación el código:

svn checkout http://proyectos-kreig-usac.googlecode.com/svn/trunk/java/LFP-proy2-OTELLO/ otello

3. Conjuntivity:

El primer proyecto en el que tuve contacto con un parser verdadero, que tuve que desarrollar a pata con la poca teoria que tenía de parsers recursivos descendentes.  La verdad fue el que me hizo crecer mi expectación por los compiladores, a pesar de ser desarrollado en otro lenguaje que destesto, el Visual Basic .NET. Obviamente, aqui no pude ser tan subversivo, pues para esa época no me quería arriesgar a desarrollarlo en Mono por cuestion de tiempo. no quedó de otra que echar mano del Visual Studio .NET 2002 (el mas buggy de todos) y desarrollarlo.  La solución se encuentra aquí:

svn checkout http://proyectos-kreig-usac.googlecode.com/svn/trunk/vb.net/LFP-proy3-Conjuntivity/ conjuntivity

Esos fueron los proyectos de Lenguajes, en los próximos posts estaré de regreso en el 5to semestre, publicando los de Compiladores 1…

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