Cómo escribir un compilador muy básico

214

Los compiladores avanzados tienen gusto de gcccompilar códigos en archivos legibles por máquina según el lenguaje en el que se ha escrito el código (por ejemplo, C, C ++, etc.). De hecho, interpretan el significado de cada código según la biblioteca y las funciones de los idiomas correspondientes. Corrígeme si estoy equivocado.

Deseo comprender mejor los compiladores escribiendo un compilador muy básico (probablemente en C) para compilar un archivo estático (por ejemplo, Hello World en un archivo de texto). Intenté algunos tutoriales y libros, pero todos son para casos prácticos. Se ocupan de compilar códigos dinámicos con significados relacionados con el lenguaje correspondiente.

¿Cómo puedo escribir un compilador básico para convertir un texto estático en un archivo legible por máquina?

El siguiente paso será introducir variables en el compilador; imagine que queremos escribir un compilador que compile solo algunas funciones de un lenguaje.

La introducción de tutoriales y recursos prácticos es muy apreciada :-)

Googlebot
fuente
¿Has probado lex / flex y yacc / bison?
mouviciel
15
@mouviciel: Esa no es una buena manera de aprender a construir un compilador. Esas herramientas hacen una gran cantidad de trabajo duro para usted, por lo que nunca lo hace y aprende cómo se hace.
Mason Wheeler
11
@Mat curiosamente, el primero de sus enlaces da 404, mientras que el segundo ahora está marcado como duplicado de esta pregunta.
Ruslan

Respuestas:

326

Introducción

Un compilador típico realiza los siguientes pasos:

  • Análisis: el texto fuente se convierte en un árbol de sintaxis abstracta (AST).
  • Resolución de referencias a otros módulos (C pospone este paso hasta el enlace).
  • 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 una computación más eficiente con la misma semántica. Esto incluye, por ejemplo, el 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 se transforma en código lineal de bajo nivel, con saltos, asignación de registros y similares. Algunas llamadas de función pueden estar en línea 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 últimos dos 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, la reordenación de instrucciones para aumentar la eficiencia de predicción de ramales, etc.

Después de eso, el código objeto está listo para vincular. 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 máquina virtual en el momento de la carga.

Recuerda lo básico

  • Hazlo funcionar
  • Hazlo hermoso
  • Hazlo eficiente

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

Concéntrese en el primer paso de la secuencia. Crea la cosa más simple que podría funcionar.

¡Lee los libros!

Lea el Libro del Dragón de Aho y Ullman. Esto es clásico y todavía es bastante aplicable hoy.

El diseño moderno del compilador también es alabado.

Si estas cosas son demasiado difíciles para usted en este momento, lea primero algunas introducciones sobre el análisis; Por lo general, las bibliotecas de análisis incluyen introducciones y ejemplos.

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

Define bien tu idioma

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.

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

Usa tu idioma favorito

Está totalmente bien escribir un compilador en Python o Ruby o cualquier idioma que sea fácil para usted. Use algoritmos simples que entienda 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 idiomas, si es necesario.

Prepárate para escribir muchas pruebas

Todo su idioma debe estar cubierto por casos de prueba; efectivamente será definido por ellos. Conozca bien su marco de prueba preferido. Escribe exámenes desde el primer día. Concéntrese en las pruebas 'positivas' que aceptan el código correcto, en lugar de la detección de código incorrecto.

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

Crea un buen analizador

Los generadores de analizadores son muchos . Elige lo que quieras. También puede escribir su propio analizador de cero, pero sólo vale la pena si la sintaxis de la lengua es muerto simple.

El analizador debe detectar e informar errores de sintaxis. Escriba muchos casos de prueba, tanto positivos como negativos; Reutilice el código que escribió al definir el idioma.

La salida de su analizador es un árbol de sintaxis abstracta.

Si su idioma tiene módulos, la salida del analizador puede ser la representación más simple del 'código objeto' que genera. Hay muchas formas simples de volcar un árbol en un archivo y volver a cargarlo rápidamente.

Crear un validador semántico

Lo más probable es que su lenguaje permita construcciones sintácticamente correctas que pueden no tener 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 usará en el proceso de validación. Por ejemplo, este paso se asegurará de que el número de parámetros pasados ​​a una función desde otro módulo sea correcto.

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

Generar codigo

Usa las técnicas más simples que conoces. A menudo está bien traducir directamente una construcción de lenguaje (como una ifdeclaración) a una plantilla de código ligeramente parametrizada, a diferencia de una plantilla HTML.

Nuevamente, ignore la eficiencia y concéntrese en lo correcto.

Apunte a una VM de bajo nivel independiente de la plataforma

Supongo que ignoras las cosas de bajo nivel a menos que estés muy interesado en los detalles específicos del hardware. 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: objetivos .NET, principalmente basados ​​en x86 / Windows; tiene un buen JIT.
  • JVM: apunta al mundo Java, bastante multiplataforma, tiene un buen JIT.

Ignorar optimización

La optimización es difícil. Casi siempre la optimización es prematura. Generar 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 astucia y cosas peludas antes de que su compilador sea estable.

¿Y qué?

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

Ver un 'Hola mundo' de un programa que creó su compilador podría valer la pena.

9000
fuente
45
Esta es una de las mejores respuestas que he visto hasta ahora.
gahooa
11
Creo que te perdiste una parte de la pregunta ... El OP quería escribir un compilador muy básico . Creo que vas más allá de lo básico aquí.
marco-fiset
22
@ marco-fiset , por el contrario, creo que 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.
smci
66
Esta es una de las mejores respuestas que he visto en todo el universo de Stack Exchange. ¡Prestigio!
Andre Terra
3
Ver un 'Hola mundo' de un programa creado por su compilador podría valer la pena. - INDEED
más
27

Let's Build a Compiler de Jack Crenshaw , aunque no está terminado, es una introducción y un tutorial eminentemente legibles.

La construcción del compilador de Nicklaus Wirth es un muy buen libro de texto sobre los conceptos básicos de la construcción del compilador simple. Se enfoca 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 del Dragón.

John R. Strohm
fuente
1
Una de las cosas buenas de Pascal es que todo tiene que definirse o declararse antes de usarse. Por lo tanto, se puede compilar en una sola pasada. Turbo Pascal 3.0 es un ejemplo de ello, y hay una gran cantidad de documentación sobre el funcionamiento interno de aquí .
tcrosley
1
PASCAL fue diseñado específicamente con la compilación de un solo paso y la vinculación en mente. El libro del compilador de Wirth menciona compiladores multipass y agrega que él sabía de un compilador PL / I que tomó 70 (sí, setenta) pases.
John R. Strohm
La declaración obligatoria antes del uso se remonta a ALGOL. Tony Hoare se quedó con los oídos tapados por el comité de ALGOL cuando intentó sugerir agregar reglas de tipo predeterminadas, similares a las que tenía FORTRAN. Ya sabían sobre los problemas que esto podría crear, con errores tipográficos en los nombres y reglas predeterminadas que crean errores interesantes.
John R. Strohm
1
Aquí está una versión más actualizada y terminada del libro por el autor original: stack.nl/~marcov/compiler.pdf Por favor edite su respuesta y agregue esto :)
sonnet
16

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 hay instrucciones C equivalentes para los comandos involucrados si encuentra que la sintaxis es desagradable.

Ingeniero mundial
fuente
77
Pero luego, una vez que tenga listo su compilador BF, debe escribir su código en él :(
500 - Error interno del servidor
@ 500-InternalServerError utiliza el método del subconjunto C
World Engineer
12

Si realmente desea escribir solo un código legible por máquina y no está dirigido a una máquina virtual, entonces deberá leer los manuales de Intel y comprender

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

  • si. Formatos COFF y PE (para Windows), alternativamente entienda el formato ELF (para Linux)

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

Mucho más duro que lo dicho. Le sugiero que lea Compiladores e Intérpretes en C ++ como punto de partida (por Ronald Mak). Alternativamente, "vamos a construir un compilador" de Crenshaw está bien.

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

Consejos: Aprenda Flex y Bison PRIMERO. Luego continúe para construir su propio compilador / VM.

¡Buena suerte!

Aniket Inge
fuente
77
Creo que apuntar a LLVM y no a un código de máquina real es la mejor manera disponible en la actualidad.
9000
Estoy de acuerdo, he estado siguiendo LLVM desde hace 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 del programador necesario para apuntarlo.
Aniket Inge
2
¿Qué pasa con MIPS y usar spim para ejecutarlo? O mezcla ?
@MichaelT No he usado MIPS pero estoy seguro de que será bueno.
Aniket Inge
Conjunto de instrucciones de @PrototypeStark RISC, procesador del mundo real que todavía se usa en la actualidad (entendiendo que será traducible en sistemas integrados). El conjunto completo de instrucciones está 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 SO .
10

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

  1. Definir la gramática del lenguaje. Libre de 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 la gramática CF simple pueden resultar feas. Quizás tu idioma es demasiado complejo ...
  3. Escriba Lexer que corta la secuencia de texto en tokens (palabras, números, literales).
  4. Escriba el analizador de descenso recursivo de arriba hacia abajo para su gramática, que acepta o rechaza la entrada.
  5. Agregue la generación de árbol de sintaxis en su analizador.
  6. Escriba el generador de código de máquina desde el árbol de sintaxis.
  7. Profit & Beer, alternativamente, puede comenzar a pensar cómo hacer un analizador más inteligente o generar un mejor código.

Debe haber mucha literatura que describa cada paso en detalle.

Mar
fuente
El séptimo punto es sobre lo que OP pregunta.
Florian Margaine
77
1-5 son irrelevantes y no merecen tanta 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 fuera del alcance las transformaciones de código.
SK-logic