Libro Gratuito ANTLR 3 – Proyecto FKScript

Esta entrada forma parte de una serie de artículos dedicados al proyecto FKScript, construcción de un compilador y una máquina virtual para un lenguaje de script con C# y ANTLR, entre los cuales podrás encontrar una descripción detallada de cada módulo, documentación técnica, ejemplos y tutoriales de uso que pueden ser de tu interés. No olvides consultar la página principal de FKScript para más información.

Información Proyecto FKScript

Esta página contiene información sobre el documento “Proyecto FKScript – Implementación mediante ANTLR y C# de un compilador y una máquina virtual para un lenguaje de script sencillo“. Puede visitar la página del proyecto para más información.

Introducción al documento

Mis primeros pasos en el mundo de las herramientas de generación de compiladores fueron con Flex y Bison (versiones GNU de Lex y Yacc). Estas herramientas, aunque potentes, resultaban algo tediosas de utilizar tanto por sus características intrínsecas como por el código generado, en lenguaje C. A pesar de todo, mis primeros trabajos con estas herramientas me proporcionaron enormes conocimientos sobre este bonito campo del desarrollo de software, aunque eso sí, pasando por muchas dificultades durante el aprendizaje debido a la falta de documentación en español sobre la generación de procesadores de lenguaje y sobre las herramientas concretas utilizadas en el proceso.

Más tarde, mis comienzos con ANTLR (allá por la versión 2.7) no fueron mejores. Me fascinaba un artilugio que unificara en una sola herramienta todos los procesos de generación de un compilador: el análisis léxico y análisis sintáctico mediante autómatas LL, la generación y recorrido de árboles de sintaxis abstracta (AST) para el análisis semántico, y la generación de código tradicional o mediante plantillas (templates), todo con una sintaxis común y con una integración total entre todos los módulos sin tener que recurrir a herramientas de terceros o desarrolladas ad hoc. Sin embargo, la curva de aprendizaje para ANTLR resultó más pronunciada de lo esperado, ya no por la falta de documentación técnica de referencia (extensa pero en inglés) sino por la falta de documentación práctica, es decir, documentación sobre cómo enfocar el desarrollo de un traductor o compilador con esta nueva herramienta.

Por aquel entonces un compañero de promoción realizó como proyecto fin de carrera un fantástico estudio de la versión 2.7.2 de ANTLR (ANTLR v2), abordando el tema desde un punto de vista completamente práctico, es decir, desarrollando desde cero un compilador para un lenguaje relativamente sencillo aunque bastante completo. Este trabajo resultó ser un recurso inmejorable de información útil sobre ANTLR 2.

Sin embargo, con la llegada de ANTLR v3 todo volvió a cambiar. La documentación de la versión anterior había quedado obsoleta ya que los cambios entre una versión y otra son notables, la documentación pública y gratuita de la versión 3 brillaba por su ausencia (aunque poco a poco se va incrementando en forma de wiki, por supuesto en inglés) y el único documento estructurado con información sobre la herramienta era el libro “The Definitive ANTLR Reference: Building Domain-Specific Languages” del propio autor de ANTLR, Terence Parr. Y por supuesto que recomiendo adquirir el libro a todo aquel que esté realmente interesado en conocer a fondo ANTLR, pero no deja de ser una fuente de información que no está al alcance de todos de forma gratuita como cabría esperar de una herramienta de código libre como es ANTLR (licencia BSD).

Y aquí es precisamente donde pensé que podría aportar mi granito de arena a todo este asunto. Aprovechando un proyecto personal en el que hacía uso de ANTLR v3 para generar el procesador de un pequeño lenguaje de script decidí escribir un pequeño documento sobre el desarrollo de un compilador para un lenguaje aún más pequeño. Un lenguaje sin complicaciones innecesarias, lo más básico posible para no perdernos en explicaciones. Un documento para comenzar a conocer ANTLR 3 y saber cómo empezar a aplicarlo al desarrollo de un compilador y una máquina virtual sencillos utilizando como lenguaje base C#. En definitiva, algo que asiente las bases necesarias para, a partir de ahí, poder seguir profundizando en el tema todo lo que se desee.

Y así nace este documento que aún no sé cómo llamar: libro de ANTLR 3, manual de ANTLR 3, tutorial de ANTLR 3, guía práctica de ANTLR 3… quizá documentación práctica de iniciación a ANTLR 3 con C#.

¿A quiénes está dirigido este tutorial? Pues en principio a cualquiera que quiera conocer los entresijos básicos de un sistema como el que se pretende construir, y que desee utilizar como herramientas de apoyo ANTLR 3 y C#. Sin embargo, aunque al principio del documento se intenta describir una foto del proceso general que siguen estos sistemas, ayudará mucho conocer al menos unos principios básicos de construcción de compiladores y máquinas virtuales. En cuanto a ANTLR v3, en este manual no se describen sus características generales por lo que se recomienda consultar documentación adicional si aún no se ha tenido ningún contacto con la herramienta. Serán de mucha utilidad conocimientos previos sobre otras herramientas de generación de compiladores (como Flex/Bison, Lex/Yacc, JavaCC…), ya que aunque sus principios no coincidan con los de ANTLR, sí que compartirán muchos conceptos comunes.

¿Qué pretendemos construir? Los requerimientos a grandes rasgos del lenguaje de script y la máquina virtual que pretendemos implementar durante esta guía son los siguientes:

  • El programa principal se escribirá en un solo fichero y estará formado por una sola función principal, es decir, no será necesario la implementación de llamadas a funciones internas (aunque no se descarta su inclusión en futuras versiones).
  • Las variables del lenguaje tendrán un tipo declarado de forma explícita y se deberá comprobar en tiempo de compilación que han sido declaradas y que sus tipos concuerdan dentro de una expresión o una asignación. •
  • Deberán existir los siguientes tipos de datos: entero, real, lógico y cadena.
  • El lenguaje deberá proporcionar las instrucciones clásicas: asignaciones, condicionales y bucles.
  • El lenguaje deberá proporcionar las expresiones aritméticas y lógicas básicas.
  • La máquina virtual se debe poder integrar fácilmente con cualquier aplicación que exponga una API, y desde el programa script se podrá interactuar con esta aplicación mediante llamadas a las funciones de esta API.

El sistema se escribirá completamente en C# y estará formado por los siguientes módulos:

  1. Un compilador que transformará el código script a un lenguaje intermedio.
  2. Un ensamblador que generará el fichero binario ejecutable a partir del código intermedio.
  3. Una máquina virtual capaz de ejecutar el fichero generado por el ensamblador.

ANTLR será usado para construir el compilador, que estará formado a su vez por los analizadores léxico y sintáctico, un analizador semántico para el cálculo y comprobación de tipos, y un generador de código a partir del árbol de sintaxis abstracta (AST) construido durante las fases anteriores. Por su parte, tanto el ensamblador como la máquina virtual se escribirán sin utilizar ninguna herramienta de apoyo, dado que son relativamente sencillos de implementar.

Descarga

El documento puede ser libremente descargado y distribuido bajo los términos de la licencia Creative Commons que se expone en el siguiente apartado.

Enlace de descarga: Libro Proyecto FKScript (v0.1) (Formato PDF – 285 Kb)


¿Te ha sido de utilidad este libro? ¿Quieres colaborar de forma económica con el proyecto? Puedes contribuir con cualquier cantidad, unos céntimos, unos euros, cualquier donación será bienvenida. Muchas gracias.

Licencia

Este trabajo y su código fuente asociado se distribuyen bajo una licencia de Creative Commons.

Tabla de Contenidos

  1. Introducción al Proyecto
  2. Introducción ANTLR
  3. Proceso General FKScript
  4. Análisis Léxico y Sintáctico de FKScript
    1. Análisis léxico
    2. Análisis sintáctico
    3. Recuento y reporte de errores
    4. Construcción del AST
    5. Construcción de la tabla de símbolos
    6. Finalizando el analizador léxico-sintáctico
  5. Análisis Semántico de FKScript
    1. Tareas del análisis semántico
    2. Enriqueciendo los nodos del árbol AST
    3. Implementación del analizador en ANTLR v3
    4. Cálculo y chequeo de tipos
    5. Programa principal
  6. Generación de Código de FKScript
    1. Máquina virtual FKVM
    2. Primeros pasos
    3. Generación de código para literales e identificadores
    4. Generación de código para expresiones aritméticas
    5. Generación de código para expresiones lógicas
    6. Generación de código para asignaciones
    7. Generación de código para instrucciones condicionales y bucles
    8. Generación de código para el programa principal FKIL
    9. Programa principal
  7. Ensamblador de código FKIL (FKASM)
    1. Tareas del ensamblador
    2. Estructuras de datos
    3. Inicialización del ensamblador
    4. Primera pasada del ensamblador
      1. Procesamiento de directivas
      2. Procesamiento de etiquetas
      3. Procesamiento de instrucciones
    5. Segunda pasada del ensamblador
  8. Máquina Virtual de FKScript (FKVM)
    1. Estructura de la máquina virtual
      1. Segmento de código
      2. Registro contador de programa
      3. Pila
      4. Memoria dinámica
      5. Tabla de funciones API
    2. Carga de un programa
    3. Ejecución de un programa
    4. Ejecución de instrucciones
      1. Instrucciones PUSH
      2. Instrucciones LOAD
      3. Instrucciones STORE
      4. Instrucciones aritméticas
      5. Instrucciones de comparación
      6. Instrucciones de salto condicional
      7. Instrucciones de llamada a función externa
    5. Integración con otras aplicaciones
      1. Registro de funciones API
      2. Definición de la API de la aplicación externa
  9. ANEXO I: Especificación del lenguaje FKScript
  10. ANEXO II: Especificación del lenguaje FKIL

¿Te ha sido de utilidad este libro? ¿Quieres colaborar de forma económica con el proyecto? Puedes contribuir con cualquier cantidad, unos céntimos, unos euros, cualquier donación será bienvenida. Muchas gracias.