El cierre de un círculo

Si bien han estado ausentes los post del blog en estos dos últimos meses, no ha sido porque piense que ya no es “cool” bloguear (como ha sucedido con muchos compañeros que lo tomaron como una moda), mas bien que en estos últimos meses me enfoqué en terminar un pendiente, terminar mi carrera de ingeniería. algo que inicié por tomarlo relajado desde hace tres años, pero que comenzó a atormentarme en este último año.

Todo empezó como una ilusión de primeros años de secundaria, convirtiendose en meta al al final. Era bonito todo eso de los videojuegos, saber que al final una consola es una computadora, entre otras ilusiones son las que llevan a uno a pensar estudiar una carrera relacionada con estos aparatejos digitales.  No lo vi tanto como una alternativa lucrativa ante la difícil situación del país, sino mas bien como desarrollar mis vagos y casi virginales conocimientos en este interesante campo.  El principal motivador: aquella exquisita sensación de sentirse dios frente a un computador, programarla, darle algo de vida a algo inanimado. crear reglas y deshacerlas, crear mi mundo e interactuar con este.

Finalizando secundaria estaba decidido, la USAC, una universidad pública, no por que fuera la mejor (aunque hay mucho alarde al respecto), sino por ser “libre” y gratuita, entrecomillando lo libre por los exámenes de admisión.  Ingeniería era la facultad, Ciencias y Sistemas era la carrera.   Ganar bien los exámenes de ubicación me exoneró de ciertos exámenes de admisión, lo que contrastó con mis primeros dos semestres (o primer año), los cuales fueron un total fiasco, ganando en el primer año tan solo 3 cursos (de aprox 10), la mayoría del área social, y ninguno de ciencias puras y sabrosas.  A esto quisiera culpar un poco a mi irresponsabilidad  debido al consumo excesivo de videojuegos durante el primer año (te veo de reojo Chrono Cross), y a otras situaciones interpersonales al ocasionados por el choque entre un reciensalido-de-la-pubertad estudiante de Ingeniería y una virginal adolescente de 15 años del instituto colindante.  Paralelo a esto, también tuve mi primer encuentro con EL METAL.

El segundo año ya fue mejor, logre aprobar mis primeras matemáticas, un curso de física, otro de química y algunas otras asignaturas que no les tomé mucho interés. Mi consumo de videojuegos, y Metal lograban balancear perfectamente la situación “del corazón/genitales” y el estudio.  Las matemáticas ya cobraban sentido, aquel ganchito raro ya sabia que se llamaba integral, y la ciencia pura comenzaba a producirme cierta obsesión placentera. y sobre todo, logré mantener mi acostumbrado bajo perfil.

La aventura comenzaba a hacerse divertida durante el tercer año, pues, con un año académico desfasado de los de mi “promocion” ( o al menos del ideal), comenzó mi camino por cursos de ciencia computacional y monkey coding.   Supe por primera vez lo que era programar miles de lineas de código, contra el reloj.  el placer de sacrificar features por bugfixes, y  contínuo debugging en un lenguaje C bastante fuera del estándar del que me había preparado, todo era alegria y gozo, hacia lo que me gustaba, y creo que lo hacía bien. Mi rebeldía contra el “establishment” comenzaba a salir, sobre todo al respecto de editores, IDES, compiladores, y paradigmas.  sobreutilicé técnicas orientadas a objetos en código que no necesitaba tales cosas, con tal de simplificarme la abstracción. Esto contribuyó a que me bautizaran con mi apodo y el apodo de este blog, y que la gente me conociera más con ese que con mi nombre real.

Cuarto año de universidad, 2006, quizás fue la de mayor aprendizaje, no solo a nivel academico, en donde resaltaría el placer exquisito por los compiladores, los circuitos digitales y el lenguaje ensamblador, sino también a nivel personal, el desamor me invade, y mi mente comienza a encontrar refugio en el alcohol, y como consecuencia, la necesidad imperante de tener más dinero de los dos quetzales diarios de mi pasaje.  Sin embargo todavía sobreviví como méndigo de cerveza durante ese tiempo con los compañeros, y aun logre ganar los cursos en el que muchos dicen que es el segmento más complicado de la carrera… uff que alivio.

Durante el quinto año que estuve en la universidad, llevando cursos de 6to, 7mo y quizas alguno de octavo, intentando matar demonios mentales comienza mi decadencia academica.  Los cursos que me interesan se terminan uno a uno… y en cambio comienzan cursos más aburridos, tal contraste como cambiar Compiladores por Investigación de Operaciones o Estructuras de Datos por Analisis y Diseño… un total asco, todo se tornaba para peor, llegaba a aburrirme y a burlarme de los ingenieros mediocres casi siempre, pero en fin, tenia que salir y ganar todos esos cursos feos.   Lo mejor que podría resaltar fue mi primer encuentro con una comunidad de locos como yo, que gustaban de usar el software libre… Contrastando con lo peor, que fue la pérdida de mis dos incisivos superiores a causa del excesivo uso del alcohol y de la delincuencia en mi amado país…  Afortunadamente fue durante los diez días de empezar mi primer trabajo como desarrollador.  Casi no disfrute mis primeros sueldos pagando mis dientecitos.  Lección aprendida, me sigo embriagando pero con mas cautela.

Sexto año,  Las sombras del pasado continuan taladrando la mente, en donde el único refugio es la cerveza y el Heavy Metal.  Ya con trabajo ya no dedicaba tiempo para estudiar, y el interés por seguir la carrera estaba en su mínimo, pero ya faltaba poco para terminar la carrera, llevando cursos de 7mo y 8vo semestre, debía terminarla o morir en el intento.  Año difícil académicamente pero salió adelante, ya no me importaba salir a tiempo, lo que queria era salir, aunquesea a paso de tortuga.

Durante el séptimo año, al fin pude decir adiós a todos esos cursos feos de administracion gerencial e ingenieria de software.  Mayor decepción fue ver que el último curso de ciencia computacional que pensé disfrutaría, terminaría siendo más curso de superación personal que de inteligencia artificial… El Metal me seguía dando la paz mental necesaria como fue desde el inicio de la carrera,  hasta que al fin! se acabó.  Había terminado todos los cursos… excepto uno Maldición y Simulación 2.

Durante el octavo año en mi estancia por el sagrado edificio T3.  ya ni lo conte, no me interesó meterme a llevar un curso que detesto una vez mas durante todo un semestre, mejor decidi esperar a que la aleatoriedad me favoreciera y abrieran el curso en los muy convenientes cursos de vacaciones de junio (o interciclos como le dicen en algunas universidades mariconas)… Esa era la oportunidad y fue un sacrificio soportar al mediocre ingeniero durante ese mes. pero al finalizarlo exitosamente dije:  mision cumplida. pero aun no completada… faltaba el examen privado y la tesis que ya llevaba un año de postergada debido a mi dejadez y falta de asesor.  Fue buen año de reiniciar cuestiones personales ademas, saliendo exitoso de mis conflictos mentales y encontrando la paz mental en la que hasta la fecha es la perfecta compañía.

Durante el noveno año, decían que había que prepararse para el examen privado, estudiar durante 3 meses dia y noche como si nunca hubiera llevado la carrera.  Decidi ignorar ese “approach” y no estudie NADA, tomé la filosofía de “Si gano, es por que aprendí algo, sino aprendi nada, merezco perder y ser un mediocre”. Todo salió bien, aunque el examen no fue como lo describían los paranóicos, siempre tuvo su dificultad y requirió su esfuerzo durante el tiempo que se realizó. Exámen aprobado exitosamente y de premio me regalé un viaje al Wacken Open Air, a agradecer a los dioses del Metal la existencia de ese Heavy Metal que me acompañó durante la carrera, con miras  para terminar el siguiente año la tesis pendiente ya con dos años de atraso.

Décimo año, tocaría conseguir asesor, terminar la tesis y graduarme. Fue algo tormentoso ver como todos se graduaban y yo seguía en las mismas, pero me tranquilizaba que ya tenia mi plan hecho.   Fue fatídico que me aceptaran mi tema de tesis nuevamente, dado que llevaba tres años de antigüedad, afortunadamente el revisor de tesis se porto bien, me la acepto, terminé el capítulo faltante, afiné detalles junto con mi flamante asesor (al cual le agradezco su tiempo), y despues de un montón de odiosos trámites, la graduación, y el alivio…  Un viernes cualquiera ya era ingeniero, aunque al final me sentía igual que cuando no lo era.  quizás alargué mucho la carrera como para sentir algo especial al terminarla.

En fin aunque la carrera ya esta muy desgastada (y lamentablemente sigue desgastándose) siempre es bonito lograr metas, estoy contento de haber logrado esta, con un esfuerzo moderado y sin estresarme mucho. Aprendí, me divertí, y sobre todo conocí y compartí con mucha gente, que no solo me ayudaron en muchos casos, sino ademas forjaron la profesionalización de manera positiva (y con algunos otros contraejemplos).  Gracias Universidad de San Carlos de Guatemala, buenos catedráticos y Pueblo de Guatemala por mantenerme estos 9 años y fracción… ahora tocará devolverles lo que me dieron.

Id y enseñad a todos.

Cantinfleando…

Erase una vez una tarde de Sábado, en la cual la energia eléctrica dejó de fluir por un momento a travez de los circuitos de mi ordenador, efectivamente se habia ido la luz como se le dice vulgarmente, y, dado que las circunstancias me han convertido en un ser dependiente del flujo de electrones, me quede sin algo productivo que hacer, en las penumbras recorde que aún tenía carga en mi reproductor Titan (coloquialmente llamado iTan, barato y fiel amigo por año y medio) de quinta categoria, Lo encendí a ver que escuchaba… y dado que todo el dia la habia pasado escuchando heavy, tal como lo hago todos los dias, queria escuchar algo diferente… mis opciones era o sintonizar las radios reguetoneras, que invaden el espectro de radiofrecuencias del país, lo cual obviamente no era opcion, o revisar si habia algo mejor en ese pequeño aparato…

Cual fue mi sorpresa de encontrarme de nuevo con unas grabaciones de voz que habia realizado hace ya mas de un año y que daba por perdidas, dichas grabaciones testificaban de una manera elocuente la frustración de un alumno desesperado quien por recibir una buena charla acerca de tecnologías de telecomunicación en un curso relacionado con el tema,  recibió en cambio, una charla graciosa en los primeros 5 minutos por su contenido “Sientifico”, y bastante desesperante por lo mismo, luego de ese lapso de tiempo. Dicho todo esto, al regresar el flujo eléctrico por la circuiteria de su ordenador, decidió dar a conocer a la humanidad el nivel de cátedra de curso por medio de la grabacion anteriormente mencionada… y esto fue lo que escucho…

NOTA: Favor escuchar el sig, video si y sólo si se esta preparado para recibir un bombardeo de informacion en 10 minutos magistrales…

PD. El autor se reserva el nombre del curso (aunque es obvio por el contexto del sig video), el período en el que fue dado, y el catedrático (¿?), pero seguro quienes han recibido clases con él sabran de quien se trata.

Los ánimos sistemicos…

Sin afán de hacerle competencia al Failblog.org, y sin tener ganas de escribir mucho, revisando fotos viejas en mi celular, recorde que habia tomado una a los famosos “ranchitos” de la facultad de Ingenieria USAC, el cual tiene el siguiente mensaje de optimismo que dice asi:

Mensaje optimista en los ranchitos

Mensaje optimista en los ranchitoss

– Vamos a Pizar

– Semana (22-28) 220809 Maldita!! [tridente]

Seguramente quien escribio ese mensaje le estaban calificando Compiladores 2 …

Festival Latinoamericano de Instalación de Software Libre 2009…

Se informa que  el sábado 25 se estará realizando el festival latinoamericano de instalación de Software Libre FLISOL 2009 en la USAC, por lo que todos aquellos que quieran desinfectar sus máquinas de software privativo y sus virus(Entiendase windows) estan cordialmente invitados.

Lugar: Área de Columnas en Facultad de Ingeniería (Edificio T4), Universidad de San Carlos de Guatemala, Campus Central.

Fecha:  25 de Abril de 2009

Horario: De 9 AM a 5 PM

Entrada: Libre

Afiche Flisol

Afiche Flisol

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

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