25.3.06

Estructura básica de un intérprete SiMPLe (A veces pasan cosas)

Seguro que más de uno le debe la vida a haber sabido hacer un intérprete de una calculadora ampliada. Cuando vaya mejor de tiempo haré las presentaciones oportunas al resto de los mortales, así como introducciones teórico-prácticas acerca de cada aspecto y posibles variantes, pero vayamos al grano.

Queremos que, dada una entrada, el programa reconozca los componentes de la entrada, la estructura sintáctica de la misma, y genere unos resultados. Por ejemplo, queremos que en
a = b + 4
Sepa que hay un identificador llamado "a", un espacio, una operación de asignación, otro espacio, un identificador llamado "b", otro espacio, una operación de suma, otro espacio, un entero con valor cuatro, un salto de línea y un fin de la entrada. Además, queremos que sepa que eso significa que estamos intentando asignarle al identificador "a" el valor resultante de sumar el valor del identificador "b" y 4. Y encima queremos que lo sume y lo asigne.

Bien, de esta forma tan superficial ya tenemos diferenciadas las tres fases del análisis del intérprete: léxico, sintáctico y semántico.
Para facilitar la visualización, a la fase léxica le asignaremos el color verde, a la sintáctica el amarillo, y a la semántica el violeta.
Vamos a empezar, sin embargo, por una "fase 0" (color blanco) que utilizaremos para que almacene la línea de entrada, un contador que nos indique en qué posición de la línea estamos, un método que nos devuelva el carácter que hay en dicha posición y un método que nos permita volver atrás en esa línea (para poder recuperarnos en caso de error, y seguir analizando por donde lo dejamos).
Un ejemplo de esto: Supongamos que queremos asignarle a "a" la cadena "cadena", pero por lo que sea la hemos escrito mal y se nos han olvidado las últimas comillas. El programa recibe lo siguiente:
a="cadena
Para un correcto funcionamiento, debería ir diciendo
a="cadena
^

-Me he encontrado un identificador llamado "a"
a="cadena
-^

-Me he encontrado un operador de asignación
a="cadena
--^

-Me he encontrado unas comillas, así que puede que todo lo que venga a continuación sea una cadena
a="cadena
---^

-Me he encontrado una c, seguramente parte de la cadena
a="cadena
----^

-Me he encontrado una a, seguramente parte de la cadena
...
a="cadena
--------^

-Me he encontrado otra a, seguramente parte de la cadena
a="cadena
---------^

-¡Ojo! Me he encontrado con un salto de línea, pero esto no lo permito en las cadenas, así que daré un error (diré que el causante ha sido las primeras comillas), volveré atrás hasta el punto siguiente al error, y continuaré analizando a partir de ellas.
a="cadena
---^

-Me he encontrado un identificador llamado c
a="cadena
----^

-Me he encontrado una a, seguramente parte del identificador
...
a="cadena
---------^

-Me he encontrado un fin de línea, así que el identificador se llamaba "cadena"
-Me he encontrado con un fin de la entrada

Llamémosle al grupo anterior (el que guarda la entrada, la posición de la línea sobre la que nos movemos y permite mover atrás esa posición) la "caja flujo":


Vamos al siguiente paso: el analizador léxico. El analizador léxico será otra "caja" que albergará en su interior la caja de flujo, y le irá pidiendo el siguiente elemento en la línea para tratar de asociarlo con una serie de categorías predefinidas. Por ejemplo, intentará asociar las letras seguidas de más letras o números a la categoría "identificador", los números a la categoría "entero", etc. Si no puede asociar una parte de la entrada a ninguna categoría, dará un error léxico diciendo qué parte de la entrada no se esperaba. Si sí que asocia correctamente la entrada a una categoría, devolverá esa categoría, con la información suplementaria que sea necesaria (por ejemplo, el nombre del identificador, el valor del entero o de la cadena...)


Recapitulando, con cada llamada al método "Avanza()", el analizador léxico irá pidiendo carácteres al Flujo (invocando a su "Siguiente()") para intentar construir el componente válido más largo posible (la llamada "estrategia avariciosa"). Una vez lo tenga, lo devolverá.

La siguiente fase es el análisis sintáctico. Igual que antes de emprender el análisis léxico necesitamos haber diseñado previamente la serie de categorías que vamos a contemplar, y cuál es su expresión regular (la forma que tendrá: números, letras seguidas de números, cadenas delimitadas por comillas, símbolos matemáticos, carácteres de control...), para el análisis sintáctico necesitamos haber diseñado previamente la gramática: cómo se construirán "frases" correctas.
Por ejemplo, en este lenguaje,
4+4
tiene una estructura correcta, pero
4 4 +
no la tiene (la podría tener si, por ejemplo, el lenguaje interpretara una calculadora de notación polaca, pero no es el caso).
La gramática de SiMPLe no es demasiado complicada; una operación asociativa a derechas se puede transcribir como algo así:
A -> B (( op A ) | lambda )
y el resto son casi todas del tipo:
A -> B ( op B )*

La razón de no hacer en la primera A -> B ( op A )* es que se generaría una ambigüedad (podríamos crear terminal op terminal op terminal a partir de producciones distintas). Sí podríamos hacerlo si, por ejemplo, tuviera la forma
A -> B ( op [ A ] )*
ya que no hay posibilidad de equívoco posible en las producciones seguidas para obtener cadenas como terminal op [ terminal op [ terminal ] op [ terminal ] ]
No profundizo en la gramática por no ser el objeto de esta entrada; quizá en la revisión detalle algunos aspectos de su funcionamiento. De momento, basta con decir que hay que asegurarse que la gramática no sea ambigua (y para esto hay que construir su tabla de análisis). Ojo con la tabla de análisis de una Gramática con Partes Derechas Regulares, que tiene un par de "añadidos" a la forma de hacerlo con una LL1. Hay ejemplos en los apuntes de la asignatura E79-II26 Humor Amarillo.

Retomando el hilo, el análisis sintáctico se limitará a ir pidiéndole al analizador léxico un elemento tras otro, e irá comprobando que los elementos que va recibiendo concuerdan con alguna de las estructuras preestablecidas que espera encontrar (comenzando por el análisis de la estructura-base "línea"). De no ser así, emitirá un error sintáctico.
El método invocado para analizar la línea llamará a su vez a otros métodos (según la serie de componentes que vaya encontrando) para analizar, por ejemplo, declaraciones de variables, impresiones, sumas, multiplicaciones, factores...


Una vez aquí, sabremos si una línea está bien formada o no. Pero, ¿cómo podemos darle sentido a la línea, para poder ejecutarla? Para esto modificaremos ligeramente la "caja sintáctica", ayudándonos de su estructura para crear un esquema de traducción dirigido por la sintaxis.
La idea es que cada rama del árbol correctamente analizada en el sintáctico devuelva una estructura (concretamente un Árbol de Sintaxis Abstracta) que, además de contener la estructura de las ramas-hijo, tenga una serie de métodos que le permitan comprobar su integridad semántica (no se pueden sumar enteros con cadenas, por ejemplo, ni asignar un valor a una variable no declarada; esto serían errores semánticos), ejecutar las operaciones correspondientes a cada rama, e incluso visualizar el árbol representándolo en forma de texto.



Los AST de tipo básico (enteros, cadenas) no tendrán AST hijos; además, no necesitarán comprobación semántica, y su ejecución es tan sencilla como devolver el valor almacenado en su componente (que se lo tendremos que haber hecho llegar a partir de su construcción en el sintáctico, que recordemos que a su vez lo habrá adquirido del léxico). El otro tipo "básico", el identificador, tampoco tendrá AST hijos, su comprobación semántica consistirá en averiguar si el identificador estaba declarado o no, y al ejecutarlo devolverá el valor que tuviera asociado (al ejecutar la declaración de variables, se habrá creado una entrada en un diccionario, con su nombre como clave, y su valor se habrá inicializado a 0 si la declaración era de tipo entero o a la cadena vacía si era de tipo cadena; aparte, también habrá guardado de qué tipo es dicha variable).
El resto de AST comparte básicamente la misma estructura: tienen uno o dos hijos (excepto el nodo de impresión, que puede tener varios), se guardan el tipo resultante de la operación correspondiente (si es entero, cadena o ha dado un error), algunas (asignación y automodificador) se guardan el i-valor del árbol izquierdo, sobre el que efectuarán las operaciones pertinentes durante su ejecución. Las comprobaciones semánticas consistirán, primero, en invocar a las comprobaciones de sus hijos (por si hubiera un error en éstos, que se detectara antes) y después hacer la comprobación de la operación propia. Para las ejecuciones, es similar: primero ejecutaremos los hijos izquierdo y derecho (en ese orden, como en las comprobaciones semánticas, para conseguir una correcta ejecución de izquierda a derecha), guardando los valores resultantes. Después, aplicaremos la operación pertinente a esos valores obtenidos.
En este punto, todavía podemos tener errores de un cuarto tipo: errores en tiempo de ejecución. Por ejemplo, una división por 0, o una replicación de una cadena un número negativo de veces. En este módulo trataremos convenientemente estos casos, según nos indiquen las especificaciones del lenguaje.
El método de declaración sólo tendrá sentido en el AST del Nodo de declaraciones de variables. Lo que se hace en él es lo mismo que habría que hacerse en su ejecución, sólo que lo hemos separado porque la especificación del funcionamiento del lenguaje así lo requiere. Este método no hará nada en el resto de AST, y en este AST el método ejecutar será el que no haga nada.

Así pues, el programa al completo tendrá esta estructura:


El resultado de crear este esquema de traducción dirigido por la sintaxis será algo similar a esto:


De forma que ya sólo nos queda utilizar toda esta estructura desde nuestro programa principal. Éste consistirá en un bucle que leerá líneas de la entrada; para cada línea, creará un analizador sintáctico que la analice, y guardará su AST resultante. Después, ejecutará los métodos pertinentes de este AST.
En el caso de que haya un error de cualquier tipo (léxico, sintáctico o semántico), las órdenes posteriores a donde haya saltado el error no se ejecutarán, pasando directamente a la siguiente iteración del bucle, con la siguiente línea (es decir, ante un error léxico o sintáctico no se construirá el AST, y ante un error semántico no se llegará a declarar variables ni ejecutar). A la hora de implementarlo, podemos conseguir este funcionamiento en Python encerrando el bucle anterior en un try-except, y elevando errores desde las funciones de error. Por supuesto, sólo es una de las muchas posibilidades.


Para cualquier aclaración, corrección, o lo que se tercie, aplicad comentarios ;)
Recuerdo que tengo intención de ampliar las explicaciones de cada fase, haciendo un pequeño resumen de lo que podemos encontrar, de forma mucho más profunda, en los apuntes de clase.

22.3.06

Un nuevo inquilino (Esta mañana me he levantado...)

¿Qué dice un cazador de pingüinos cuando llega al Polo Norte y lo encuentra desierto?
¡Ningüino!

Con esta parida mala, una servidora me traumatizó en aquél lejano primer año de carrera. Esta tarde, aprovechando un paseito por "los hippies" de Castellón, he adoptado a un pequeñín que ha usado la Fuerza para atraer mi atención. Como cualquier linuxero que se precie, me hacía falta un pingüino. Y como homenaje (la idea ha sido de cierta incontinente verbal, todo hay que decirlo), se llama Ningüino (Ningüi para los amigos).


El pequeño Ningüi

Ya tengo algo más que llevarme a la próxima iParty, aparte de a mi querida Python.

Los del "piso de arriba" han visto con algo de recelo al recién llegado. Con esa bufandita y esas pintas, sospechan que pierde aceite.


Algunos de los del piso de arriba
(de izquierda a derecha): Kthulito, Rigoberto y Eusebio

Pero bueno, por una parte tampoco importa tanto lo que digan dos godzillas semifosforescentes (Eneumesio y Eusebio), un alien (Rigoberto), un pulpo fosforescente (Kthulito) y un pterodáctilo de madera (que no tiene nombre porque como es de madera, no habla y no me lo ha comunicado); y por otra, siendo tan frikis, seguro que acabará cayéndoles bien, y lo protegerán como es debido. Al fin y al cabo, ¡es el peque de la familia!

21.3.06

Cómo destruir la Tierra (Esta mañana me he levantado...)

Un divertido repaso (en inglés) a las mejores formas de cargarse, de una vez por todas y definitivamente, este pedazo de roca en el que nos movemos. ¡Con explicaciones científicas y todo! Sólo apto para supervillanos y mentes enfermas:

http://qntm.org/destroy

Edito: No me he olvidado de ti, Annie:

Traducción en castellano

Portazo a la SGAE (Esta mañana me he levantado...)

Sacado de la web de Informativos Telecinco.

Nace "Extremadura Creativa" una plataforma que gestiona derechos de autor

AGENCIAS
20 de marzo de 2006

La plataforma Extremadura Creativa ha sido presentada en Badajoz. Esta organización pretende prestar asesoramiento a los artistas, creadores y científicos que quieran gestionar sus derechos de autor al margen de las condiciones impuestas por la Sociedad General de Autores (SGAE). Para esta actividad, utilizarán las licencias Creative Commons” que se ofrecen a través de Internet.

Ricardo Utrera es uno de los promotores de esta plataforma. Además, es propietario del bar Metropol de Badajoz, que obtuvo una sentencia favorable frente a la SGAE el pasado 8 de febrero, en el Juzgado de Primera Instancia número 6 de Badajoz.

Utrera explicó que la iniciativa surgió tras el interés que provocó esta sentencia, pionera en España, que de ratificarse en la Audiencia Provincial sentaría jurisprudencia.

Añadió que la SGAE utiliza prácticas "deplorables" para garantizar sus ingresos por derechos de autor, como "detectives" que recorren desde bares a festejos familiares para comprobar si se utiliza música que ellos consideren de su propiedad.

Ricardo Utrera declaró que a pesar de contar con sólo 80.000 socios, la SGAE, se considera "representante de la música universal" y, además, pide cánones en los PC portátiles, los CD e incluso por las líneas ADSL.

La plataforma "Extremadura Creativa" es la única en España, y nace con el objetivo de que músicos, escritores y científicos pongan su obra a disposición del público en general. También pretenden que los autores cedan sus derechos a quien ellos consideren más oportuno a través de las licencias "Creative Commons".

Otro de los promotores, Santiago Cambero, explicó que se trata de una iniciativa surgida en EEUU en el año 2001 y que está extendida por todo el mundo. Esta forma de actuar respecto a los derechos de autor, cuenta, según Cambero, con seguidores como los "Talking Heads", el ministro de Cultura brasileño o el cantante y compositor Gilberto Gil.

Extremadura Creativa presta asesoramiento jurídico desde su web sobre cómo ceder los derechos y es el propio creador el que elige el gestor de sus derechos de autor. Aunque todavía se encuentra en fase de iniciación, la web ofrece contactar con esta plataforma para cualquier consulta.

El autor tendrá así, dijo, pleno derecho sobre la copia y reproducción de su obra, la distribución, la comunicación pública y la realización de versiones o obras transformadas sobre la original.

Los promotores de la plataforma hicieron una llamamiento a la Junta de Extremadura para que, igual que actúa de abanderando del software libre, muestre su apoyo institucional a todos aquellos que se quieran unir a las "Creative Commons".

18.3.06

Luces en el cielo (Esta mañana me he levantado...)

Hay noches en los que da verdadero asco mirar al cielo en busca de las estrellas y encontrarse con que hay más luz en el ambiente que en tu pueblo al amanecer. Recuerdo de una visita a Valencia que allí la cosa era bastante más grave, con un eterno tono rojizo-amarillento en el cielo nublado. No sé si la fauna de la zona (animales y humanos) tendrá algún tipo de problema biorrítmico por eso, pero no me extrañaría. Aquí quizá no llame tanto la atención, excepto si eres aficionado a mirar al cielo o cuando hay partidos de fútbol.
En esos días, en los que seis enormes baterías de focos resplandecen con toda su potencia, las estrellas enmudecen en una especie de nube radiactiva de luz que rodea como un hongo atómico todo el perímetro de varios kilómetros a la redonda.
¿No hay forma de tapar esos focos para que sólo iluminen a donde tengan que iluminar? ¿No están haciendo nada por modificar los alumbrados de la ciudad?
Quiero que me devuelvan mis estrellas :(

17.3.06

El Día del Juicio Final Revisited (Esta mañana me he levantado...)

Pues en fin, parece un calco del último intento de Día del Juicio Final. Al volver edito esto y cuento cómo ha ido. De momento, después de ver cómo abrieron en canal hace poco a mi perra para una operación, creo que un par de centímetros de puntos en la boca no serán para tanto...
Más información luego. ¡Y tal vez con fotos!

Eeeeeedito. Ya estoy de vuelta, y aunque las malditas muelas se han resistido muchísimo a salir, al menos el proceso (aunque tedioso) ha resultado indoloro (por el momento). Han tenido que fresar aquí y allá la muela, espero que no se haya quedado ningún cachodiente por ahí dentro :S
En cuanto pueda abrir la boca, fotos del antes y después del interior. De momento, cómo ha quedado el chasis:



11.3.06

Cuanto más grande es el caos (Esta mañana me he levantado...)

Mao-Tse-Tung dejó dicho «Cuanto más grande es el caos, más próxima está la solución». Las cosas se han ido torciendo más y más en mi vida en los últimos días, y las expectativas indican que aún va a ser peor.
Como diría un esotérico, la vida se compone de "salud, trabajo y amor". En cuanto a salud, las cosas no andan muy finas en mi familia (y este viernes me toca el Día del Juicio Final). En el "trabajo", se acerca una suerte de suicidio académico por presentar una queja formal en una asignatura con requisitos de evaluación excesivos. "E79-II26: Humor Amarillo", la llaman algunos. En cuanto al amor... nada que no sepáis ya. Atrapado en el tiempo.
Es curioso, acaba de empezar a sonar "Teenage wasteland", el tema de The Who que abre las cortinas de CSI: NY. Un escalofrío recorre mi cuerpo, y se me olvida todo lo que pensaba decir. Los potentes y graves acordes de sus guitarras y bajos, con el teclado haciendo virguerías por lo alto, me dejan en un estado parecido al que escucha un koan zen. ¿Son unos genios o están locos? Sus canciones también parecen puro caos, experimentos que acaban teniendo un orden, un sentido. Tengo entendido que vienen a tocar a España dentro de poco, una lástima no poder disfrutar de estos sonidos en primera persona. Siempre me quedará poner el reproductor a todo volumen, cerrar los ojos y soñar con que no hay nada en el mundo que pueda hacerme daño. Que todo está bien. Que, cuanto más grande sea el caos, más cerca estará la solución.
Como dijo alguien en una tira cómica: "No digas que hemos fracasado; di mejor que hemos decidido postponer nuestro éxito."

9.3.06

Reglas no escritas I (A veces pasan cosas)

Constante Universal de Cariño: La suma de cariño de dos personas es constante; si una de los dos da de menos, y la otra da de más esperando recibir la misma respuesta, la otra persona dará aún menos y se sentirá agobiada.
Corolario de Equilibrio: En el mejor de los casos, como excepción a la regla, ambas personas darán de menos.

Principio de Falta de Confidente: Justo el día en que necesites tener cinco minutos para contarle tus penas por primera vez en diez años a alguien con quien pasas casi todo el tiempo, esa persona no aparecerá o se tendrá que ir.
Corolario de Servidora: Si esa persona está disponible, te contará algo tantas veces peor que lo tuyo, que te sentirás una colillita.