Pregunta Aprendiendo a escribir un compilador [cerrado]


Lenguas preferidas: C / C ++, Java y Ruby.

Estoy buscando algunos libros / tutoriales útiles sobre cómo escribir tu propio compilador simplemente con fines educativos. Estoy muy familiarizado con C / C ++, Java y Ruby, por lo que prefiero los recursos que implican uno de esos tres, pero cualquier buen recurso es aceptable.


699


origen


Respuestas:


Gran lista de recursos:

Leyenda:

  • ¶ Enlace a un archivo PDF
  • $ Enlace a un libro impreso

1024



Esta es una pregunta bastante vaga, creo; solo por la profundidad del tema involucrado. Sin embargo, un compilador se puede descomponer en dos partes separadas; una mitad superior y una inferior. La mitad superior generalmente toma el idioma de origen y lo convierte en una representación intermedia, y la mitad inferior se ocupa de la generación de código específico de la plataforma.

Sin embargo, una idea para una manera fácil de abordar este tema (la que usamos en mi clase de compiladores, al menos) es construir el compilador en las dos piezas descritas anteriormente. Específicamente, obtendrá una buena idea de todo el proceso al construir la mitad superior.

Simplemente haciendo la mitad superior le permite obtener la experiencia de escribir el analizador léxico y el analizador e ir a generar algún "código" (esa representación intermedia que mencioné). Por lo tanto, tomará su programa de origen y lo convertirá a otra representación y hará algo de optimización (si lo desea), que es el corazón de un compilador. La mitad inferior tomará esa representación intermedia y generará los bytes necesarios para ejecutar el programa en una arquitectura específica. Por ejemplo, la mitad inferior tomará su representación intermedia y generará un ejecutable PE.

Algunos libros sobre este tema que encontré particularmente útiles fueron Principios y técnicas para compiladores (o el Libro del Dragón, debido al lindo dragón en la portada). Tiene una gran teoría y definitivamente cubre Gramáticas sin contexto de una manera realmente accesible. Además, para construir el analizador léxico y el analizador, probablemente use las herramientas * nix lex y yacc. Y sin interés, el libro llamado "lex y yacc"recogió donde dejó el Libro del Dragón para esta parte.


69



creo Implementación moderna del compilador en ML es el mejor texto de compilación introductorio para compiladores. Hay una Versión de Java y un Versión C también, cualquiera de los cuales podría ser más accesible dado el fondo de tu idioma. El libro contiene una gran cantidad de material básico útil (escaneo y análisis sintáctico, análisis semántico, registros de activación, selección de instrucciones, generación de código nativo RISC y x86) y varios temas "avanzados" (compilación de OO y lenguajes funcionales, polimorfismo, recolección de basura, optimización y una sola forma de asignación estática) en un espacio relativamente pequeño (~ 500 páginas).

Prefiero la Modern Compiler Implementation al libro de Dragon porque la implementación de Modern Compiler abarca menos del campo; en cambio, tiene una cobertura realmente sólida de todos los temas que necesitaría para escribir un compilador serio y decente. Después de trabajar en este libro, estará listo para abordar los artículos de investigación directamente para obtener más detalles si lo necesita.

Debo confesar que tengo un punto débil serio para Niklaus Wirth Construcción del compilador. Es disponible en linea como PDF La estética de programación de Wirth me parece simplemente hermosa, sin embargo, algunas personas consideran que su estilo es demasiado minimalista (por ejemplo, Wirth prefiere los analizadores sintácticos de descenso recursivo, pero la mayoría de los cursos de CS se centran en herramientas de generación de analizadores sintácticos, los diseños de lenguaje de Wirth son bastante conservadores). de las ideas básicas de Wirth, así que si te gusta su estilo o no, te recomiendo leer este libro.


54



Estoy de acuerdo con la referencia del Libro del Dragón; IMO, es la guía definitiva para la construcción de compiladores. Sin embargo, prepárate para una teoría hardcore.

Si quieres un libro que es más ligero en teoría, Juego Scripting Mastery podría ser un mejor libro para ti. Si eres un novato total en teoría de compilación, proporciona una introducción más amable. No cubre métodos de análisis más prácticos (optando por el descenso recursivo no predictivo sin discutir el análisis LL o LR), y según recuerdo, ni siquiera discute ningún tipo de teoría de la optimización. Además, en lugar de compilar código máquina, compila un bytecode que se supone que se ejecuta en una máquina virtual que usted también escribe.

Sigue siendo una lectura decente, especialmente si puedes comprarlo barato en Amazon. Si solo desea una introducción fácil a los compiladores, Game Scripting Mastery no es un mal camino a seguir. Si quieres ir al hardcore por adelantado, entonces deberías conformarte con nada menos que el Dragon Book.


46



"Construyamos un compilador" es increíble, pero está un poco desactualizado. (No estoy diciendo que lo haga un poco menos válido).

O echa un vistazo ARGOT. Esto es similar a "Construyamos un compilador", pero es un recurso mucho mejor, especialmente para principiantes. Esto viene con un tutorial en pdf que toma un enfoque de 7 pasos para enseñarte un compilador. Agregando el enlace quora ya que tiene los enlaces a todos los puertos de SLANG, en C ++, Java y JS, también intérpretes en python y java, originalmente escritos usando C # y la plataforma .NET.


28



Si está buscando utilizar herramientas poderosas de alto nivel en lugar de construir todo usted mismo, pasando por los proyectos y las lecturas de este curso es una muy buena opción. Es un curso de idiomas del autor del motor de análisis ANTLR de Java. Puede obtener el libro del curso en formato PDF desde los programadores pragmáticos.

El curso repasa las cosas del compilador de compilador estándar que verías en otro lugar: análisis sintáctico, tipos y verificación de tipos, polimorfismo, tablas de símbolos y generación de código. Casi todo lo que no está cubierto son las optimizaciones. El proyecto final es un programa que compila un subconjunto de C. Debido a que utiliza herramientas como ANTLR y LLVM, es factible escribir todo el compilador en un solo día (tengo una prueba de existencia de esto, aunque quiero decir ~ 24 horas). Es pesado en la ingeniería práctica utilizando herramientas modernas, un poco más ligero en teoría.

LLVM, por cierto, es simplemente fantástico. En muchas situaciones en las que normalmente puede compilar hasta ensamblar, sería mucho mejor que compilara Representación intermedia de LLVM en lugar. Es de nivel superior, multiplataforma, y ​​LLVM es bastante bueno para generar un ensamblaje optimizado a partir de él.


24



Si tienes poco tiempo, te recomiendo "Compilación Construcción" de Niklaus Wirth (Addison-Wesley. 1996), un pequeño librito que se puede leer en un día, pero explica los conceptos básicos (que incluyen cómo implementar lexers, analizadores sintácticos de descenso recursivo y sus propias máquinas virtuales basadas en pila). Después de eso, si quieres una inmersión profunda, no hay forma de evitar el libro del Dragón como sugieren otros comentaristas.


20



Es posible que desee buscar en Lex / Yacc (o Flex / Bison, como quiera llamarlos). Flex es un analizador léxico, que analizará e identificará los componentes semánticos ("tokens") de su idioma, y ​​Bison se usará para definir qué sucede cuando se analiza cada token. Esto podría ser, pero definitivamente no se limita a, imprimir el código C, para un compilador que compilaría en C, o ejecutar las instrucciones dinámicamente.

Estas preguntas frecuentes debería ayudarte, y este tutorial parece bastante útil.


17



En general, no hay un tutorial de cinco minutos para los compiladores, porque es un tema complicado y escribir un compilador puede llevar meses. Tendrás que hacer tu propia búsqueda.

Python y Ruby suelen interpretarse. Quizás también quieras comenzar con un intérprete. En general es más fácil.

El primer paso es escribir una descripción formal del lenguaje, la gramática de su lenguaje de programación. Luego debe transformar el código fuente que desea compilar o interpretar de acuerdo con la gramática en un árbol de sintaxis abstracta, una forma interna del código fuente que la computadora entiende y en la que puede operar. Este paso se suele denominar análisis y el software que analiza el código fuente se denomina analizador. A menudo, el analizador es generado por un generador de analizador sintáctico que transforma una gramática formal en código fuente o de máquina. Para una buena explicación no matemática del análisis, recomiendo Técnicas de análisis: una guía práctica. Wikipedia tiene una comparación de generadores de analizadores de los que puede elegir aquella que sea adecuada para usted. Dependiendo del generador de analizadores que elija, encontrará tutoriales en Internet y para los generadores de analizadores realmente populares (como el bisonte GNU) también hay libros.

Escribir un analizador sintáctico para su idioma puede ser muy difícil, pero esto depende de su gramática. Así que sugiero mantener su gramática simple (a diferencia de C ++); un buen ejemplo para esto es LISP.

En el segundo paso, el árbol de sintaxis abstracta se transforma de una estructura de árbol a una representación lineal intermedia. Como un buen ejemplo para este bytecode de Lua a menudo se cita. Pero la representación intermedia realmente depende de tu lenguaje.

Si está construyendo un intérprete, simplemente tendrá que interpretar la representación intermedia. También puede compilarlo justo a tiempo. Recomiendo LLVM y libjit para compilación justo a tiempo. Para que el lenguaje sea utilizable, también deberá incluir algunas funciones de entrada y salida, y quizás una pequeña biblioteca estándar.

Si va a compilar el idioma, será más complicado. Deberá escribir backends para diferentes arquitecturas de computadora y generar código de máquina a partir de la representación intermedia en esos backends. Recomiendo LLVM para esta tarea.

Hay algunos libros sobre este tema, pero no puedo recomendar ninguno para uso general. La mayoría de ellos son demasiado académicos o demasiado prácticos. No existe el "Enséñale a ti mismo el compilador escribiendo en 21 días" y, por lo tanto, tendrás que comprar varios libros para comprender bien todo este tema. Si busca en Internet, encontrará algunos libros en línea y notas de conferencias. Tal vez haya una biblioteca universitaria cerca de ti donde puedas tomar prestados libros sobre compiladores.

También recomiendo un buen conocimiento de fondo en teoría informática y teoría de grafos, si va a hacer que su proyecto sea serio. Un título en ciencias de la computación también será útil.


16



Eche un vistazo al libro a continuación. El autor es el creador de ANTLR.

Patrones de implementación del lenguaje: cree sus propios lenguajes específicos de dominio y de programación.

alt text


14



Un libro aún no sugerido pero muy importante es "Enlazadores y cargadores" por John Levine. Si no está utilizando un ensamblador externo, necesitará una forma de generar un archivo de objeto que pueda vincularse con su programa final. Incluso si está utilizando un ensamblador externo, probablemente deba comprender las reubicaciones y cómo funciona todo el proceso de carga del programa para hacer una herramienta de trabajo. Este libro recopila gran cantidad de conocimientos sobre este proceso para varios sistemas, incluidos Win32 y Linux.


11