compiler-construction - tutorial - lexical analyzer with lex

Escribir compiladores... ¿Qué está bien y qué está mal? (8)

¿Alguien preguntó seriamente si el libro del dragón podría estar desactualizado? Es el trabajo seminal del hombre. No puedo decirte cuánto aprendí solo de los primeros dos capítulos (porque desde entonces lo he olvidado ... ba-dum-bum).

Cada tecnología (excepto tal vez la declaración goto) tiene detractores y partidarios. No se preocupe por "hacer la elección correcta de herramientas", e intente aprender los conceptos e implementarlos de una manera que tenga sentido. Quiero decir, hombre, incluso si eligieras las mejores herramientas perfectas en el mundo, ¿crees que construirías algo tan amado, adorado y respetado tanto como lo es FORTRAN en estos días ... quiero decir, nos encanta ... verdad?

Por supuesto que no el hombre ... tanto de aprender proviene de cometer errores. Ahí es donde aprendes más.

¡PUEDES HACERLO!

De acuerdo, en mi búsqueda para descubrir las cosas necesarias para escribir un compilador, he llegado a un pequeño obstáculo. Parece que cada tecnología o herramienta que encuentro tiene alguna oposición en alguna parte.

Utilizo Bison y Flex en este momento, pero tengo la sensación de que este método no está actualizado. ¿Es esto cierto? ¿Es esta una buena manera de avanzar en la escritura de un lenguaje de programación completo?

En un mar de diferentes conceptos y herramientas (ANTLR, LL (k), GLR, LALR, LLVM, Flex, Bison) ¿Cuál es la tendencia actual y las mejores prácticas para escribir compiladores? ¿Está el libro del dragón desactualizado?

¿Es esto para 1) un gran lenguaje existente como Java o C ++ en un extremo, o 2) un pequeño lenguaje sin tipos de datos sofisticados en el otro?

Si es 1, es mejor que te pongas al día con todas las tecnologías que Ira mencionó.

Si es 2, puede hacerlo rápidamente si solo escribe un analizador de descenso recursivo, y ya sea a) lo traduce a su idioma favorito (YFL) mientras analiza, o b) construye una tabla de símbolos y un árbol de análisis, y luego caminar eso para generar YFL. Si no desea generar YFL, simplemente escriba un intérprete que recorra el árbol de análisis.

Si su objetivo es aprender todas las tecnologías difíciles, entonces hágalo. Si no, rápido y sucio es el camino a seguir. Si esto último, ¡NO te preocupes por la optimización!

Por cierto, si quieres ir realmente rápido y sucio, y tienes C o C ++, y no estás demasiado orgulloso de escribir macros, una forma sencilla de crear un lenguaje es simplemente escribir un conjunto de macros. De esa manera, puede crear sus propias declaraciones, mientras aprovecha los tipos de datos, la sintaxis de expresión, la eficiencia y las bibliotecas de tiempo de ejecución del lenguaje subyacente.

A menos que desee escribir un compilador realmente simple, su enfoque es incorrecto.

Escribir compiladores es solo un poquito sobre escribir analizadores. Tener un analizador es como escalar las estribaciones de los Himalayas cuando el problema es escalar el Everest. Llegas a la cima de la colina y miras hacia arriba ... solo quedan 20,000 pies y solo has hecho la parte realmente fácil. Y notará que la tecnología requerida para llegar a la cima de las colinas es radicalmente más fácil que la tecnología que necesita para recorrer el resto del camino.

(Para su información: la mejor tecnología de análisis actual es GLR , que acepta fácilmente gramáticas ambiguas sin piratear la gramática. GLR incluso analiza fácilmente C ++, que viola el teorema popular de que C ++ es difícil de analizar. El teorema popular proviene de personas que intentan usar YACC y ANTLR para analizarlo).

Para construir un compilador necesitas mucha maquinaria:

Edificio de AST
Mesa de simbolos de construccion
Análisis de flujo de control
Análisis de flujo de datos
Representación del código de programa esencialmente como un cálculo de flujo de datos (SSA o triples)
Un modelo de la máquina objetivo.
Un medio para asignar el código del programa a las instrucciones de la máquina
Asignación de registro
Optimizaciones: propagación constante, desenrollado de bucles, ...

Ni siquiera nos hemos acercado al análisis de flujo global, a las optimizaciones globales o al manejo especial de los conjuntos de instrucciones de hoy en día que incluyen instrucciones SIMD u optimizaciones de caché. ... La lista sigue y sigue. El libro del Dragón ofrece una buena introducción a los temas básicos, pero no aborda ninguno de los avanzados. Querrá que Cooper''s "Engineering a Compiler" y Muchnick''s "Advanced Compiler Design" sean referencias, y sería bueno si los hubiera analizado bien antes de comenzar.

Construir un compilador moderno es toda una hazaña de ingeniería.

El análisis sintáctico, aunque muy estudiado, es la parte menos importante de la compilación. (Excepción: estás diseñando tu propia sintaxis concreta y estás continuamente refinando y cambiando el idioma).

Yacc, Bison y sus amigos fueron diseñados para una era de máquinas con 64K de memoria. Son excelentes para correr rápido en máquinas con memoria limitada. Pero la cantidad de ingeniería humana requerida para forzar una gramática en la forma LALR (1) es ridícula hoy en día. Ira Baxter tiene razón en que GLR es probablemente la mejor y más flexible tecnología de análisis, pero PEG (Gramática de expresión de análisis) también es bueno. En ambos casos, la ingeniería humana está a años luz de las herramientas más antiguas.

Habiendo descartado el análisis, ahora comenzaré otra pelea por la tecnología de los alimentos :-) La compilación consiste principalmente en reescribir un programa una y otra vez de una forma a otra, hasta que finalmente llegue al código de ensamblaje o al código de la máquina. Para este tipo de problema, realmente no desea utilizar C o C ++:

P: (Le preguntaron a Dave Hanson cuando publicó su increíble libro sobre lcc con Chris Fraser) "Usted y Chris han pasado diez años construyendo lo que puede ser uno de los compiladores más cuidadosamente diseñados que se hayan hecho. ¿Qué aprendió de la experiencia?"
R: "Bueno, C es un lenguaje pésimo para escribir un compilador".

Le insto a que pruebe uno de los lenguajes funcionales populares, como Haskell o Standard ML. Las personas que trabajan en este campo creen que los compiladores son la "aplicación asesina" para los lenguajes funcionales. Los tipos de datos algebraicos y la coincidencia de patrones están hechos a medida para escribir sintaxis abstracta en código intermedio en código de máquina. Un buen lugar para ver el poder de estas técnicas es el libro Compilación con continuaciones de Andrew Appel. (El libro de texto del compilador de Appel también es una buena lectura y un diseño muy elegante, pero no siempre explica por qué el diseño es como es).

No puedo dar una comparación de los diversos enfoques, pero el grupo ANTLR ha cubierto una amplia gama de idiomas de destino ricos :

que incluyen la mayoría de las actuales comunes. ANTLR también soporta una variedad de lenguajes de salida. Planeamos abordar un lenguaje similar a CSS

Para construir un compilador, recomiendo encarecidamente pararse sobre los hombros de gigantes. Hay muchas cosas buenas que se pueden juntar para hacer compiladores. He estado trabajando en un compilador a tiempo parcial para C / C ++. Utiliza GLR para el análisis, crea un AST, utiliza SSA como su forma intermedia, realiza optimizaciones entre procedimientos y genera código para X86, ARM, MIPS, PowerPC, Sparc y otros.

¿El secreto? Tomé prestado el código de varias fuentes.

El preprocesador y el informe de errores de clang
El generador de compiladores Elkhound y Elsa y compilador C / C ++
El sistema LLVM para optimización y generación de código.

Trabajando a tiempo parcial, he podido armar un sistema de herramientas bastante útil. Si hubiera intentado empezar de cero, apenas habría terminado el analizador. ;-)

http://ellcc.org

Realmente no hay nada malo con Flex y Bison, pero si buscas algo un poco más actualizado (y orientado a objetos) puedes considerar la biblioteca Spirit de boost .

Asumiré que estás en la misma posición que yo: quieres escribir un compilador para divertirte y aprender al menos un poco sobre cada etapa de la misma. Por lo tanto, no desea simplemente escribir un complemento para un compilador existente. Y desea evitar el uso de demasiados módulos de compilación existentes, excepto donde puede entender exactamente lo que están haciendo. En mi caso, estoy usando bison , que es una ligera excepción porque está haciendo al menos algunas cosas que doy por sentado (estudié gramáticas, etc. en la universidad, pero eso fue hace mucho tiempo). Por otro lado, los generadores de analizadores son lo suficientemente comunes como para que sea una etapa de compilación digna de interés: bison puede impedir que escriba mucho código de análisis, pero me está dando un cambio para escribir código de acción de analizador.

Contrariamente a algunos consejos, yo diría que puede comenzar sin saber todo sobre su entrada y los idiomas de destino. Con algunas excepciones, las características del idioma no son difíciles de agregar posteriormente. Una excepción que he descubierto es el flujo de control: si escribe la mayoría de las manipulaciones posteriores para trabajar en una forma de árbol, puede ser difícil atender declaraciones como break , continue y goto (incluso la forma estructurada). Así que recomiendo traducir de árbol a CFG antes de hacer demasiado de eso.

Escriba un analizador para un subconjunto razonablemente estable de la entrada.
Agregue acciones que generen una representación útil en la memoria (normalmente un árbol) y consiga que imprima eso.
Consíguelo para imprimirlo en una forma que se parezca un poco al idioma de destino. En mi caso, imprimo el nodo del árbol para "x = y + z;" nodos como "ADD x, y, z"; "if (c) {...}" se convierte en "bz c label1", luego la traducción de "..." luego "label1:".
Añadir etapas opcionales en el medio. Estas pueden ser etapas de optimización y / o verificación. Es posible que necesite uno que prepare la representación para la generación fácil de código: Tengo una etapa que reduce expresiones demasiado complejas al agregar variables temporales. (Esto es realmente necesario para la salida, porque la instrucción "AGREGAR" solo puede funcionar en entradas simples).
Regresa y mejora cualquier parte de ella. Por ejemplo, ponga algunas comprobaciones en las acciones del analizador para que se puedan detectar errores en esa etapa (uso de variables no declaradas, por ejemplo).

Es sorprendentemente fácil obtener la mayor parte de esto, si adopta un enfoque iterativo.