¿Quieres crear un compilador? Basta con leer estos dos artículos (2008)

• La mayoría de los manuales de compiladores son extensos y están centrados en la teoría, por lo que a los principiantes les resulta difícil implementar un compilador que realmente funcione
• Como material práctico para superar esto, se presenta la serie “Let’s Build a Compiler!” de Jack Crenshaw, que trata sobre un compilador Pascal conciso con estructura de una sola pasada
• Este tutorial apoya el aprendizaje experimental mediante la combinación de análisis sintáctico y generación de código, una optimización mínima y versiones en C y Forth
• El segundo material, el artículo “A Nanopass Framework for Compiler Education”, propone una arquitectura modular de compilador compuesta por numerosas transformaciones simples (passes)
• Después de adquirir experiencia real de implementación con estos dos materiales, si hace falta se puede profundizar consultando textos tradicionales (Dragon Book)

---

La realidad de aprender compiladores y dos artículos clave

• Se señala que los libros de compiladores existentes son demasiado extensos y difíciles, por lo que a los principiantes les cuesta escribir un compilador que realmente funcione
  • La mayoría de los libros cubren temas muy amplios, como la transformación de expresiones regulares y la teoría gramatical, sin ofrecer un punto de partida práctico
  • Esto ha llevado a la formación de malentendidos y mitos como que “los compiladores son difíciles”
• Como material representativo que rompe con esa percepción, se presenta la serie “Let’s Build a Compiler!” de Jack Crenshaw
  • Este tutorial, iniciado en 1988, trata un compilador de una sola pasada al nivel de Turbo Pascal
  • Tiene una estructura que combina el análisis sintáctico y la generación de código, y realiza solo una optimización mínima
  • Originalmente fue escrito en Pascal, y después aparecieron también una versión en C y una traducción a Forth
  • La versión en Forth facilita la experimentación y la comprensión gracias a las características interactivas del lenguaje
• Una limitación de la serie de Crenshaw es que no incluye una representación interna del programa (árbol de sintaxis abstracta, AST)
  • En Pascal, manipular árboles era complicado y por eso se omitió, pero en lenguajes de alto nivel como Python, Ruby, Erlang, Haskell y Lisp puede implementarse fácilmente
  • Estos lenguajes fueron diseñados originalmente para la manipulación de datos con estructura de árbol
• El segundo material recomendado es el artículo de Sarkar, Waddell y Dybvig, “A Nanopass Framework for Compiler Education”
  • La idea central es que “un compilador es una serie de procesos que transforma gradualmente la representación interna de un programa”
  • Propone una estructura compuesta por decenas o cientos de transformaciones simples (passes)
  • Cada transformación se mantiene lo más simple posible y evita el acoplamiento entre transformaciones
  • El framework define de forma explícita la entrada y la salida de cada pass
  • El lenguaje de implementación es Scheme, y realiza validación en tiempo de ejecución basada en tipado dinámico
• Después de escribir un compilador real con estos dos materiales, si hace falta se puede continuar con un estudio más profundo usando textos tradicionales como el Dragon Book
  • Sin embargo, incluso solo con estos dos materiales es posible obtener suficiente experiencia práctica en la construcción de compiladores

[GN⁺]

Opiniones de Hacker News

• 『The Art of Computer Programming』 de Donald Knuth sigue en proceso de escritura, y ahora parece poco probable que llegue a tratar el tema de los compiladores
  No estoy de acuerdo con la afirmación del autor. El capítulo 2 del 『Dragon Book』 (de Aho y otros) es suficientemente completo por sí solo como introducción a los compiladores
  Otra excelente introducción es 『Compilers』 de Niklaus Wirth, que en menos de 100 páginas incluye el código fuente de un compilador completo junto con explicaciones claras
  Con esos dos libros aprendí lo suficiente como para crear mi propio compilador cuando estaba en la preparatoria

  • El 『Dragon Book』 es excelente, pero no es adecuado como libro introductorio. Yo también estuve a punto de abandonar los compiladores por culpa de ese libro
    Creo que es mucho mejor un libro práctico que siga paso a paso el proceso real de construir un compilador
    Hay material de referencia resumido en este enlace
  • El 『Dragon Book』 está centrado en parsing, así que no lo recomendaría si te interesan el backend o la optimización
    La segunda edición añadió análisis de flujo de datos, pero el formato SSA (Static Single Assignment), clave en compiladores modernos como GCC y LLVM, apenas ocupa una sola página
    Si quieres construir un backend moderno, necesitas estudiar la teoría de SSA por separado
  • 『Compilers』 de Niklaus Wirth puede consultarse aquí
  • Según el sitio de Knuth, todavía existe el plan de tratar técnicas de compiladores en el Volumen 7
    Ver la página oficial de TAOCP
  • No sabía que Knuth tenía segundo nombre, pero en el artículo probablemente no hace falta incluirlo

• El artículo de Abdulaziz Ghuloum An Incremental Approach to Compiler Construction
  rompe la idea de que “los compiladores son algo mágico” y muestra que se puede construir un compilador tan fácilmente como un intérprete
  Explica con mucho detalle el proceso de construir paso a paso un compilador que soporta gran parte del lenguaje Scheme y genera ensamblador para Intel x86

  • 『Writing a C Compiler』 de Nora Sandler, inspirado por ese artículo, también es un libro muy bueno
  • También existe una versión con pruebas donde Nada Amin implementó el enfoque de Aziz

• Últimamente la tecnología de compiladores ha avanzado mucho con los metacompiladores, la compilación adaptativa (Adaptive Compilation) y los compiladores JIT, entre otros
  El grupo de investigación VPRI de Alan Kay aborda los problemas de complejidad
  Material relacionado: artículo sobre Ometa, video sobre Adaptive Compilation, charla de Alan Kay

• Escuché un buen consejo para leer libros: un libro permite acceso aleatorio (random access), como la RAM
  Si lees solo las partes que necesitas, hasta un libro grueso se vuelve menos pesado
  Aun así, este método no funciona cuando ni siquiera sabes qué es lo que no sabes. Por eso son tan importantes las introducciones ligeras

  • La mayoría de los libros tienen demasiados detalles innecesarios y termino saltándomelos. En cambio, los libros técnicos son tan difíciles que para entender una sola parte hay que estudiar durante horas
  • Siento que si no leo un libro hasta el final, me cuesta sacar verdadero provecho. Hoy en día muchos materiales que cumplen bien el papel de obra de consulta se han trasladado a internet
  • Una parte considerable de mis libros técnicos la uso como referencia para preguntas específicas

• En estos días se recomienda mucho 『Crafting Interpreters』
  El enlace al artículo de Nanopass está roto

  • Incluso entre los “libros de compiladores” el alcance varía muchísimo, y muchas veces no coincide con la parte que yo quiero aprender
    Por eso hice una chuleta que resume lo esencial de 『Crafting Interpreters』
    El libro no es solo un manual simple, sino un texto de aprendizaje centrado en la experiencia, donde se nota el gusto del autor por cosas como el patrón visitor
  • 『Crafting Interpreters』 es excelente, pero sería perfecto si tuviera un volumen complementario sobre sistemas de tipos, optimización y linking
  • Es un libro realmente bueno para estudiar por cuenta propia
  • Lo terminé completo en la universidad mientras esperaba entre clases. Todavía no he usado Nanopass, pero pienso probar con otro enlace
  • El artículo de Nanopass está preservado en este repositorio de GitHub

• Últimamente estoy haciendo un compilador de juguete por diversión
  En vez de teoría compleja de parsing o DSL, estoy usando combinadores de parser de Megaparsec
  La lógica de parsing queda clara, es fácil de reutilizar y evita las molestias de la separación tradicional entre lexer y parser

  • Yo creo que los parsers descendentes recursivos son más prácticos que los generadores de parser LL/LR
    Tienen menos bugs, mejores diagnósticos de errores y la mayoría de los lenguajes (C#, Rust, etc.) también usan este enfoque
    tree-sitter también es excelente, pero trae muchas dependencias. En cambio, el descenso recursivo permite una implementación concisa sin dependencias
  • Aun así, creo que es mejor mantener la separación entre lexer y parser
    La ventaja del enfoque con combinadores de parser es que tanto el lexer como el parser pueden tratarse con el mismo tipo de parser
    Eso permite resolver de forma limpia el manejo de espacios en blanco y los problemas de tokenización

• El artículo de Nanopass, cuyo enlace estaba muerto, puede verse aquí

  • También hay un artículo relacionado en el Cambridge Journal of Functional Programming
  • El sitio oficial es nanopass.org

• Lo que me enseñó compiladores fue el artículo sobre el compilador Tiny Pascal en BYTE magazine de 1978
  Aprendí optimización en un curso de verano impartido en Stanford por Ullman y Hennessy
  El generador de código era un método original hecho por mí
  Tengo el 『Dragon Book』, pero en realidad nunca lo he leído

  • Ese número de BYTE magazine puede verse en archive.org

• La clave del enfoque Nanopass no es la cantidad de passes, sino definir un lenguaje de entrada y salida explícito para cada pass
  Gracias a esta forma estructurada de pensar, se pueden detectar muchos bugs antes de ejecutar
  El tutorial de Crenshaw también es excelente, pero esta gestión de invariantes del lenguaje es la diferencia que realmente permite construir compiladores escalables

• En mi época en UC Irvine, recuerdo haber implementado un compilador optimizante en el curso CS241 del profesor Michael Franz, alumno de Niklaus Wirth
  Era una tarea para generar bytecode para una máquina virtual llamada DLX
  El material relacionado puede verse en la explicación de la arquitectura DLX y en esta imagen de referencia sobre el algoritmo de asignación de registros