Cómo escribir un compilador muy básico

Introducción

Un compilador típico realiza los siguientes pasos:

• Analizando: el el texto de origen se convierte en un árbol de sintaxis abstracta (AST).
• Resolución de referencias a otros módulos (C pospone este paso hasta la vinculación).
• Validación semántica: eliminar declaraciones sintácticamente correctas que no tienen sentido, por ejemplo código inalcanzable o declaraciones duplicadas.
• Transformaciones equivalentes y optimización de alto nivel: el AST se transforma para representar un cálculo más eficiente con la misma semántica. Esto incluye, por ejemplo, cálculo temprano de subexpresiones comunes y expresiones constantes, eliminando asignaciones locales excesivas (ver también SSA ), etc.
• Generación de código: el AST es transformado en código lineal de bajo nivel, con saltos, asignación de registros y similares. Algunas llamadas a funciones pueden insertarse en esta etapa, algunos bucles desenrollados, etc.
• Optimización de mirilla: el código de bajo nivel se escanea en busca de ineficiencias locales simples que se eliminan.

La mayoría de los compiladores modernos (por ejemplo, gcc y clang) repiten los dos últimos pasos una vez más. Utilizan un lenguaje intermedio de bajo nivel pero independiente de la plataforma para la generación inicial de código. Luego, ese lenguaje se convierte en código específico de la plataforma (x86, ARM, etc.) haciendo aproximadamente lo mismo de una manera optimizada para la plataforma. Esto incluye, por ejemplo, el uso de instrucciones vectoriales cuando sea posible, el reordenamiento de las instrucciones para aumentar la eficiencia de predicción de ramas, etc.

Después de eso, el código objeto está listo para ser enlazado. La mayoría de los compiladores de código nativo saben cómo llamar a un enlazador para producir un ejecutable, pero no es un paso de compilación per se. En lenguajes como Java y C #, la vinculación puede ser totalmente dinámica, realizada por la VM en el momento de la carga.

Recuerde los conceptos básicos

• Hágalo funcionar
• Hágalo hermoso
• Hágalo eficiente

Esta secuencia clásica se aplica a todo el desarrollo de software, pero admite repetición.

Concéntrese en el primer paso de la secuencia. Cree lo más simple que pueda funcionar.

¡Lea los libros!

Lea el Dragon Book de Aho y Ullman. Este es un clásico y todavía es bastante aplicable en la actualidad.

Diseño de compilador moderno también es elogiado.

Si estas cosas son demasiado difíciles para ti en este momento, primero lee algunas intros sobre el análisis; generalmente analizando bibliotecas incluya intros y ejemplos.

Asegúrese de sentirse cómodo trabajando con gráficos, especialmente árboles. Estas cosas son de las que están hechos los programas en el nivel lógico.

Defina bien su lenguaje

Use la notación que desee, pero asegúrese de tener una descripción completa y coherente de su idioma. Esto incluye tanto la sintaxis como la semántica.

Es hora de escribir fragmentos de código en su nuevo idioma como casos de prueba para el futuro compilador.

Use su idioma favorito

Está totalmente bien escribir un compilador en Python o Ruby o cualquier lenguaje que le resulte fácil.Utilice algoritmos simples que comprenda bien. La primera versión no tiene que ser rápida, eficiente o completa. Solo necesita ser lo suficientemente correcto y fácil de modificar.

También está bien escribir diferentes etapas de un compilador en diferentes lenguajes, si es necesario.

Prepárese para escribir mucho de pruebas

Todo su lenguaje debe estar cubierto por casos de prueba; de hecho, será definido por ellos. Familiarícese con su marco de prueba preferido. Escriba pruebas desde el primer día. Concéntrese en las pruebas «positivas» que aceptan el código correcto, en contraposición a la detección de código incorrecto.

Ejecute todas las pruebas con regularidad. Arregle las pruebas rotas antes de continuar. Sería una pena terminar con un mal lenguaje definido que no puede aceptar código válido.

Cree un buen analizador

Los generadores de analizadores son muchos . Elija lo que desee También puede escribir su propio analizador desde cero, pero solo vale la pena si la sintaxis de su idioma es muerto simple.

El analizador debe detectar e informar errores de sintaxis. muchos casos de prueba, tanto positivos como negativos ve; reutiliza el código que escribiste al definir el lenguaje.

La salida de tu analizador es un árbol de sintaxis abstracto.

Si tu lenguaje tiene módulos, la salida del analizador puede ser la representación más simple del «código objeto» que genere. Hay muchas formas sencillas de volcar un árbol en un archivo y volver a cargarlo rápidamente.

Cree un validador semántico

Lo más probable es que su lenguaje permita construcciones sintácticamente correctas que pueden hacer no tiene sentido en ciertos contextos. Un ejemplo es una declaración duplicada de la misma variable o pasar un parámetro de un tipo incorrecto. El validador detectará tales errores mirando el árbol.

El validador también resolverá las referencias a otros módulos escritos en su idioma, cargará estos otros módulos y los utilizará en el proceso de validación. Por ejemplo, este paso asegurará que el número de parámetros pasados a una función desde otro módulo sea correcto.

De nuevo, escriba y ejecute muchos casos de prueba. Los casos triviales son tan indispensables para la resolución de problemas como inteligentes y complejos.

Genere código

Utilice las técnicas más simples que conozca. A menudo, está bien traducir directamente una construcción de lenguaje (como una instrucción if) a una plantilla de código ligeramente parametrizada, similar a una plantilla HTML.

De nuevo , ignore la eficiencia y concéntrese en la corrección.

Apunte a una VM de bajo nivel independiente de la plataforma

Supongo que ignorará las cosas de bajo nivel a menos que esté muy interesado en hardware específico detalles. Estos detalles son sangrientos y complejos.

Sus opciones:

• LLVM: permite la generación eficiente de código de máquina, generalmente para x86 y ARM.
• CLR : apunta a .NET, multiplataforma; tiene un buen JIT.
• JVM: apunta al mundo Java, bastante multiplataforma, tiene un buen JIT.

Ignorar la optimización

La optimización es difícil. Casi siempre la optimización es prematura. Genere código ineficiente pero correcto. Implemente todo el lenguaje antes de intentar optimizar el código resultante.

Por supuesto, las optimizaciones triviales están bien para introducir. Pero evite cualquier cosa astuta y peluda antes de que su compilador sea estable.

¿Y qué?

Si todo esto no es demasiado intimidante para usted, ¡continúe! Para un lenguaje simple, cada uno de los pasos puede ser más simple de lo que piensa.

Ver un «Hola mundo» de un programa que creó su compilador puede valer la pena.

Comentarios

• Esta es una de las mejores respuestas que ‘ he visto hasta ahora.
• Creo que se perdió una parte de la pregunta … El OP quería escribir un compilador muy básico . Creo que va más allá de lo básico aquí.
• @ marco-fiset , por el contrario, creo que es ‘ es una respuesta sobresaliente que le dice al OP cómo hacer un compilador muy básico, mientras señala las trampas para evitar y define fases más avanzadas.
• Esta es una de las mejores respuestas Lo he visto en todo el universo de Stack Exchange. ¡Felicitaciones!
• Ver un ‘ Hola mundo ‘ de un programa creado por su compilador puede valer la pena. – EN REALIDAD

Jack Crenshaw «s Vamos a construir un compilador , aunque está inacabado, es una introducción y un tutorial eminentemente legibles.

Nicklaus Wirth «s Construcción del compilador es un muy buen libro de texto sobre los conceptos básicos de la construcción de un compilador simple. Se centra en el descenso recursivo de arriba hacia abajo, que, seamos sinceros, es MUCHO más fácil que lex / yacc o flex / bison. El compilador PASCAL original que escribió su grupo se hizo de esta manera.

Otras personas han mencionado los diversos libros de Dragon.

Comentarios

• Una de las cosas buenas de Pascal es que todo tiene que ser definido o declarado antes de ser utilizado. Por lo tanto, se puede compilar en una sola pasada. Turbo Pascal 3.0 es un ejemplo, y hay mucha documentación sobre los componentes internos aquí .
• PASCAL fue diseñado específicamente con una- pasar la compilación y la vinculación en mente. El libro de compiladores de Wirth ‘ s menciona compiladores de múltiples pasadas y agrega que conocía un compilador PL / I que tomó 70 (sí, setenta) pasadas.
• Declaración obligatoria antes de su uso se remonta a ALGOL. Tony Hoare consiguió que el comité de ALGOL se quedara quieto cuando trató de sugerir agregar reglas de tipo predeterminadas, similar a lo que tenía FORTRAN. Ellos ya sabían acerca de los problemas que esto podría crear, con errores tipográficos en los nombres y reglas predeterminadas que crean errores interesantes.
• Aquí hay una versión más actualizada y terminada del libro del propio autor original: stack.nl/~marcov/compiler.pdf Edite su respuesta y agregue esto 🙂

Si realmente desea escribir código legible por máquina únicamente y no dirigido a una máquina virtual, entonces tendrá que leer los manuales de Intel y comprender

• a. Vinculación y carga de código ejecutable

• b. Formatos COFF y PE (para Windows), también entender el formato ELF (para Linux)

• c. Comprender los formatos de archivo .COM (más fácil que PE)
• d. Entender a los ensambladores
• e. Comprender los compiladores y el motor de generación de código en los compiladores.

Mucho más difícil de hacer de lo que se dice. Le sugiero que lea Compiladores e intérpretes en C ++ como punto de partida (por Ronald Mak). Alternativamente, «vamos a construir un compilador» por Crenshaw está bien.

Si no quiere hacer eso, también podría escribir su propia VM y escribir un generador de código dirigido a esa VM.

• Otro punto de partida: http://gnuu.org/2009/09/18/writing-your-own-toy-compiler/
• Gran libro de Kenneth Louden: http://www.amazon.com/Compiler-Construction-Principles-Kenneth-Louden/dp/0534939724

Consejos: Aprenda a utilizar Flex y Bison PRIMERO. Luego, construya su propio compilador / VM.

¡Buena suerte!

Comentarios

• Creo que apuntar a LLVM y no el código de máquina real es la mejor manera disponible en la actualidad.
• Estoy de acuerdo, he estado siguiendo LLVM por algún tiempo y debo decir que fue una de las mejores cosas que había visto en años en términos de esfuerzo de programador necesario para orientarlo!
• ¿Qué pasa con MIPS y usar spim para ejecutarlo? O MIX ?
• @MichaelT No he usado MIPS pero estoy seguro de que será bueno.
• @PrototypeStark Conjunto de instrucciones RISC, procesador del mundo real que todavía está en uso hoy (entendiendo que será traducible a sistemas integrados). El conjunto de instrucciones completo se encuentra en wikipedia . Mirando en la red, hay muchos ejemplos y se usa en muchas clases académicas como un objetivo para la programación en lenguaje de máquina. Hay un poco de actividad en SO .

En realidad, comenzaría escribiendo un compilador para Brainfuck . Es un lenguaje bastante obtuso para programar, pero solo tiene 8 instrucciones para implementar. Es lo más simple posible y existen instrucciones C equivalentes para los comandos involucrados si encuentra la sintaxis desagradable.

Comentarios

• Pero luego, una vez que tenga listo su compilador BF, debe escribir su código en él 🙁
• @ 500-InternalServerError use el método de subconjunto C

El enfoque de bricolaje para un compilador simple podría verse así (al menos así es como se veía mi proyecto uni):

1. Defina la gramática del idioma. Sin contexto.
2. Si su gramática aún no es LL (1), hágalo ahora. Tenga en cuenta que algunas reglas que se veían bien en CF simple la gramática puede resultar fea. Quizás su lenguaje sea demasiado complejo …
3. Escriba Lexer que corta el flujo de texto en tokens (palabras, números, literales).
4. Escriba de arriba hacia abajo analizador sintáctico descendente recursivo para su gramática, que acepta o rechaza la entrada.
5. Agregue la generación del árbol de sintaxis en su analizador.
6. Escriba ma generador de código chine del árbol de sintaxis.
7. Profit & Cerveza, alternativamente, puede comenzar a pensar en cómo hacer un analizador más inteligente o generar un mejor código.

Debería ser abundante literatura que describa cada paso en detalle.

Comentarios

• El séptimo punto es sobre lo que OP está preguntando.
• 1-5 son irrelevantes y no merecen tal mucha atención. 6 es la parte más interesante.Desafortunadamente, la mayoría de los libros siguen el mismo patrón, después del infame libro del dragón, prestando demasiada atención al análisis y dejando las transformaciones de código fuera de alcance.