Programación del compilador: ¿Cuáles son los ingredientes más fundamentales?

Question

Estoy interesado en escribir un compilador muy minimalista.

Quiero escribir una pequeña pieza de software (en C/C++) que cumpla con los siguientes criterios:

• salida en formato ELF (* nix)
• de entrada es un solo archivo de texto
• C-como gramática y la sintaxis
• no enlazador
• no preprocesador
• muy pequeña (máx. 1-2 KLOC)

Características del lenguaje:

• tipos de datos nativos: char, int y flota
• matrices (para todos los tipos de datos nativos)
• las variables
• estructuras de control (if-else)
• funciones
• loops (sería bueno)
• simple algebra (div, agregar, sub, mul, las expresiones booleanas, desplazamiento de bit, etc.)
• línea asm (para llamadas al sistema)

¿Puede alguien decirme cómo empezar? No sé en qué partes está compuesto un compilador (al menos no en el sentido de que podría comenzar directamente) y cómo programarlos. Gracias por tus ideas.

Answer 1

En primer lugar, debe decidir si va a hacer un compilador o un intérprete. Un compilador traduce su código en algo que puede ejecutarse directamente en el hardware, en un intérprete o compilarse en otro idioma que luego se interpreta de alguna manera. Ambos tipos de lenguajes están completos, por lo que tienen las mismas capacidades expresivas. Sugiero que cree un compilador que compile su código en .net o bytecode de Java, ya que le ofrece un intérprete muy optimizado para ejecutar, así como muchas bibliotecas estándar.

vez ha tomado una decisión, hay algunos pasos comunes a seguir

1. lenguaje de definición de En primer lugar, hay que definir cómo su lenguaje debe ser sintácticamente.

2. Lexer El segundo paso es crear las palabras clave de su código, conocidas como tokens. Aquí, estamos hablando de elementos muy básicos como números, signos de suma y cadenas.

3. Análisis El siguiente paso es crear una gramática que coincida con su lista de tokens. Puedes definir tu gramática usando, por ejemplo, una gramática libre de contexto. Se pueden alimentar varias herramientas con una de estas gramáticas y crear el analizador para usted. Por lo general, los tokens analizados se organizan en un árbol de análisis sintáctico. Un árbol de análisis es la representación de su gramática como una estructura de datos que puede moverse.

4. compilación o interpretación El último paso es ejecutar alguna lógica en el árbol de análisis sintáctico. Una forma sencilla de crear su propio intérprete es crear una lógica asociada a cada tipo de nodo en su árbol y recorrer el árbol de abajo hacia arriba o de arriba hacia abajo. Si desea compilar en otro idioma, puede insertar la lógica de cómo traducir el código en los nodos.

Wikipedia es ideal para obtener más información, es posible que desee comenzar here.

En cuanto al material de lectura del mundo real, sugeriría "Procesadores de lenguaje de programación en JAVA" por David A Watt & Deryck F Brown. Utilicé ese libro en mi curso de compiladores y aprender con el ejemplo es excelente en este campo.

Answer 2

Estas son las partes absolutamente esencial:

• escáner: Esto rompe el archivo de entrada en tokens
• Analizador: Esto construye un árbol de sintaxis abstracta (AST) a partir de las fichas identificadas por el escáner.
• Generación de código: Esto produce la salida del AST.

Usted también probable que desee:

• La gestión de errores: Esto le dice al analizador qué hacer si encuentra un inesperado símbolo
• Optimización: Esto permitirá que el compilador para producir la máquina más eficiente código

Editar: ¿Ya has diseñado el idioma? Si no, también querrás ver el diseño del lenguaje.

Answer 3

El número uno esencial es un libro sobre compilación de escritura. Mucha gente te dirá que leas el "Libro del Dragón" de Aho y otros, pero el mejor libro que he leído sobre compiladores es "Brinch Hansen en Compiladores Pascal". Sospecho que está agotado (Amazon es tu amiga), pero te lleva a través de todos los pasos de diseñar y escribir un compilador utilizando el descenso recursivo, que es el método más fácil de entender para los novatos compiladores.

Aunque el libro utiliza Pascal como la implementación y los idiomas de destino, las lecciones y técnicas presentadas se aplican igualmente a todos los demás idiomas.

Answer 4

No sé qué espera obtener de esto, pero si se trata de aprender, y ver que el código existente funciona para usted, siempre hay tcc.

Answer 5

Los ejemplos están todos en Perl, pero Exploring Programming Language Architecture in Perl es un buen libro (y gratis).

Answer 6

Con todo lo que espera lograr, el requisito más exigente podría ser "muy pequeño (máximo 1-2 KLOC)". Creo que su primer requisito solo (generación de salida ELF) podría tomar más de mil líneas de código por sí mismo.

Una forma de simplificar el problema, al menos para empezar, es generar código en texto de lenguaje ensamblador que luego alimentar a un ensamblador existente (nasm sería una buena opción).El ensamblador se encargaría de generar el código de máquina real, así como también todo el código específico de ELF requerido para construir un ejecutable ejecutable real. Luego, su trabajo se reduce a análisis de lenguaje y generación de código de ensamblaje. Cuando su proyecto vence hasta el punto en que desea eliminar la dependencia de un ensamblador, puede volver a escribir esta parte usted mismo y conectarla en cualquier momento.

Si yo fuera usted, podría comenzar con un ensamblador y construir piezas encima. El "compilador" simple podría tener un lenguaje con sólo unas pocas declaraciones muy simples posibles:

print "hello" 
a = 5 
print a 

y traducirlo a lenguaje ensamblador. Una vez que lo hagas funcionar, puedes construir un generador de códigos y árbol de sintaxis abstracto y analizador, que son la mayoría de las partes que necesitarás para un lenguaje estructurado de bloque moderno.

¡Buena suerte!

Answer 7

Siempre recomiendo flex y bison para este tipo de trabajo como principiante. Siempre puede aprender los pormenores de escribir su propio escáner y analizador más tarde, aunque pueden aumentar el tamaño del código, al menos serán generados por las herramientas. :)

Answer 8

Un buen conjunto de referencias libres, en mi humilde opinión, son:

general tutorial compilador: Construyamos un compilador por Jack Crenshaw (http://compilers.iecc.com/crenshaw/) Es prolijo, pero me gusta.

Ensamblador: NASM (nasm.us) bueno para Linux y Windows/DOS, y lo más importante, un montón de doco y ejemplos/tutoriales. (FASM también es bueno, pero menos documentación/tutoriales por ahí)

Otras fuentes El libro Asamblea PC (http://www.drpaulcarter.com/pcasm/index.php)

Estoy intentando escribir una LISP, así que estoy usando el Lisp 1.5 Manual. Es posible que desee obtener las especificaciones de idioma para el idioma que está escribiendo.

En cuanto a 1-2KLOC, suponiendo que utilice un lenguaje de alto nivel (como Py o Rb), debe estar cerca si no es demasiado ambicioso.