sidelab: de BNF a la Depuración Estructural

Me gustaría volver sobre el tema de mi último post. Porque en sidelab éste ha sido un tema recurrente. Micael realizó un modelo orientado a objetos de Pascal como parte de su trabajo fin de carrera de la ingeniería técnica, y un modelo de Java 5 como parte de su proyecto fin de carrera de la ingeniería superior. Ambos trabajos dieron lugar a sendos parsers (definidos en JavaCC) que, dado un fichero escrito en Pascal (en el primer caso) o en Java (en el segundo) construía la representación orientada a objetos de dicho fichero.

En el caso del proyecto fin de carrera de la ingeniería superior el modelo de Java 5 representaba la parte estática del lenguaje (la representación en memoria de las clases, métodos, etc de un fichero Java), pero tenía la particularidad de representar también la parte dinámica: pila de ejecución de métodos, variables, llamadas a métodos, etc. El proyecto se denominó inicialmente JavaMod, pero después decidimos cambiarle el nombre por JavaCET (Java Código, Ejecución y Traza, o también Java Code, Execution, and Trace).

Utilizando JavaCET (y después de mucho penar construyendo un editor de Java con características similares a las que tenía JIdea [¿por qué nos metimos a esto, Mica?] que será objeto de otro post aquí) construimos un depurador estructural. Comentaré lo que significa depuración estructural, comentando primero cómo funcionan los depuradores «al uso». Un depurador generalmente muestra resaltada la próxima línea que se va a ejecutar. Si avanzamos (con un «step» o «step over») el depurador nos sitúa ahora en la siguiente línea. Sin embargo, la línea que se acaba de ejecutar puede contener potencialmente decenas de instrucciones Java que ha habido que ejecutar una a una hasta llegar a la línea siguiente. Cuando se enseña programación, esto no es deseable, porque puede confundir al pensar que varias operaciones son realmente una sola. Para facilitar el aprendizaje de los conceptos «dinámicos» del lenguaje Java, desarrollamos un depurador estructural que tenía la capacidad de mostrar la siguiente expresión a evaluar. No era un depurador línea a línea, sino que si en una línea había varias expresiones, iba evaluándolas todas ellas paso a paso (y resaltando exclusivamente la siguiente a evaluar). Sobre esto de la depuración estructural escribimos un paper titulado Depuración Estructural: Acercando la Práctica a la Teoría de la Programación.

Posteriormente, la idea era hacer crecer JavaCET incluyéndole una parte de traza que permitiera guardar la traza de la ejecución del programa (o al menos parte de ella) para poder reproducir posteriormente fácilmente los errores. Esta parte nunca llegamos a implementarla, aunque sí que indagamos herramientas como Omniscient Debugger (recuerdo que lo vendían como Debugging backwards in time, ya que el disponer de la traza de ejecución permitía ir hacia atrás desde una condición de error hasta su causa a través de todas las ejecuciones de métodos y expresiones evaluadas) para estudiar cuál era el estado de la cuestión. Pero de esto hablaremos también en otro post, que este ya está yendo demasiado lejos.

Estábamos con BNF. Pues bien, este lenguaje estuvo presente también durante toda mi tesis doctoral, centrada en la Ingeniería de Lenguajes (Language Engineering o Grammarware), término muy cool que se acuñó para simular formalismo y enfoques ingenieriles en algo que carecía completamente de ello, como era el diseño de lenguajes y la implementación de herramientas de soporte para los mismos. Y digo que carecía totalmente de ello porque el parser se hacía (y se hace) a mano (y en el lenguaje del generador de parsers de turno), el modelo no podía generarse directamente desde la gramática, siempre había que retocarlo en mil sitios diferentes, y la depuración vivía en un mundo aparte, como si el código en ejecución no tuviera derecho también a tener un modelo.

Así que durante mi tesis conviví estrechamente con BNF (o el lenguaje de especificación de turno). Posteriormente volví a este tema al implementar Pascaline, el conjunto de plug-ins de Eclipse para el lenguaje Pascal.

Y por último, Micael ha estado trabajando codo con codo con gente de CAPO para hacer un binding Java basado en JNI de OpenCL. Así que parece que retomaré el tema para dotar de un parser a los kernels de este lenguaje y disponer de un plug-in OpenCL (y JavaOpenCL) para Eclipse… si es que tengo tiempo.

¿Te apetece hacer un Proyecto Fin de Carrera con nosotros?

La primera línea en BNF

A través de Barrapunto he dado con una página que contiene el documento original donde se describe ALGOL60.

Este documento, firmado entre otros por John Warner Backus y Peter Naur, tiene la particularidad de haber sido el primer documento en contener la definición de un lenguaje de programación en notación BNF. Peter Naur y John Backus definieron BNF (Backus-Naur Form) con el objeto de dar una descripción formal de los lenguajes de programación, frente a las descripciones informales en lenguaje natural habituales en la época. Esto permitió escribir compiladores fieles a la especificación del lenguaje, al reducir el grado de ambigüedad de los mismos. La línea en cuestión (un ejemplo de la notación, que se describe en lenguaje informal) la dejo aquí:

Si le echáis un vistazo al documento… ¿es la gramática ambigua?

La página contiene documentos donde se definen algunos de los lenguajes de programación más carismáticos, como FORTRAN o Pascal.

Por supuesto en BNF:

Para los más intrépidos, es interesante echar un vistazo al código del compilador de Pascal-S.