compiler-construction - jdoodle - netbeans online




Aprendiendo a escribir un compilador (20)

"... Vamos a construir un compilador ..."

Me gustaría segundo http://compilers.iecc.com/crenshaw/ por @sasb . Olvídate de comprar más libros por el momento.

¿Por qué? Herramientas y lenguaje.

El lenguaje requerido es Pascal y si recuerdo correctamente está basado en Turbo-Pascal. Sucede que si visita http://www.freepascal.org/ y descarga el compilador de Pascal, todos los ejemplos funcionan directamente de la página ~ http://www.freepascal.org/download.var Lo bello de Free Pascal es que puedes usarlo casi en cualquier procesador o sistema operativo que puedas cuidar.

Una vez que haya dominado las lecciones, pruebe el " Libro del Dragón " más avanzado ~ http://en.wikipedia.org/wiki/Dragon_book

Idiomas preferidos : C / C ++, Java y Ruby.

Estoy buscando algunos libros / tutoriales útiles sobre cómo escribir su propio compilador simplemente con fines educativos. Estoy más familiarizado con C / C ++, Java y Ruby, así que prefiero los recursos que involucran a uno de esos tres, pero cualquier buen recurso es aceptable.


Gran lista de recursos:

Leyenda:

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

No incluido en la lista hasta ahora es este libro:

Conceptos básicos del diseño de compiladores (Torben Mogensen) (del departamento de informática, Universidad de Copenhague)

También estoy interesado en aprender sobre compiladores y planear ingresar a esa industria en los próximos dos años. Este libro es el libro de teoría ideal para comenzar a aprender compiladores hasta donde puedo ver. Es GRATUITO para copiar y reproducir, escrito de forma limpia y cuidadosa, y se lo entrega en inglés sencillo sin ningún código, pero aún así presenta la mecánica a través de instrucciones y diagramas, etc. Vale la pena echarle un vistazo.


Puedes usar BCEL por la Apache Software Foundation. Con esta herramienta puede generar código similar a un ensamblador, pero es Java con la API de BCEL. Puede aprender cómo generar código de idioma intermedio (en este caso, código de byte).

Ejemplo simple

  1. Crea una clase de Java con esta función:

    public String maxAsString(int a, int b) {
        if (a > b) {
            return Integer.valueOf(a).toString();
        } else if (a < b) {
            return Integer.valueOf(b).toString();
        } else {
            return "equals";
        }
    }
    

Ahora ejecuta BCELifier con esta clase

BCELifier bcelifier = new BCELifier("MyClass", System.out);
bcelifier.start();

Puede ver el resultado en la consola para toda la clase (cómo crear el código de byte MyClass.java). El código para la función es este:

private void createMethod_1() {
  InstructionList il = new InstructionList();
  MethodGen method = new MethodGen(ACC_PUBLIC, Type.STRING, new Type[] { Type.INT, Type.INT }, new String[] { "arg0", "arg1" }, "maxAsString", "MyClass", il, _cp);

  il.append(InstructionFactory.createLoad(Type.INT, 1)); // Load first parameter to address 1
  il.append(InstructionFactory.createLoad(Type.INT, 2)); // Load second parameter to adress 2
    BranchInstruction if_icmple_2 = InstructionFactory.createBranchInstruction(Constants.IF_ICMPLE, null); // Do if condition (compare a > b)
  il.append(if_icmple_2);
  il.append(InstructionFactory.createLoad(Type.INT, 1)); // Load value from address 1 into the stack
  il.append(_factory.createInvoke("java.lang.Integer", "valueOf", new ObjectType("java.lang.Integer"), new Type[] { Type.INT }, Constants.INVOKESTATIC));
  il.append(_factory.createInvoke("java.lang.Integer", "toString", Type.STRING, Type.NO_ARGS, Constants.INVOKEVIRTUAL));
  il.append(InstructionFactory.createReturn(Type.OBJECT));
  InstructionHandle ih_13 = il.append(InstructionFactory.createLoad(Type.INT, 1));
  il.append(InstructionFactory.createLoad(Type.INT, 2));
    BranchInstruction if_icmpge_15 = InstructionFactory.createBranchInstruction(Constants.IF_ICMPGE, null); // Do if condition (compare a < b)
  il.append(if_icmpge_15);
  il.append(InstructionFactory.createLoad(Type.INT, 2));
  il.append(_factory.createInvoke("java.lang.Integer", "valueOf", new ObjectType("java.lang.Integer"), new Type[] { Type.INT }, Constants.INVOKESTATIC));
  il.append(_factory.createInvoke("java.lang.Integer", "toString", Type.STRING, Type.NO_ARGS, Constants.INVOKEVIRTUAL));
  il.append(InstructionFactory.createReturn(Type.OBJECT));
  InstructionHandle ih_26 = il.append(new PUSH(_cp, "equals")); // Return "equals" string
  il.append(InstructionFactory.createReturn(Type.OBJECT));
  if_icmple_2.setTarget(ih_13);
  if_icmpge_15.setTarget(ih_26);
  method.setMaxStack();
  method.setMaxLocals();
  _cg.addMethod(method.getMethod());
  il.dispose();
}

Aquí hay muchas respuestas buenas, así que pensé que solo agregaría una más a la lista:

Recibí un libro llamado Proyecto Oberon hace más de una década, que tiene un texto muy bien escrito en el compilador. El libro realmente se destaca en el sentido de que la fuente y las explicaciones son muy prácticas y legibles. El texto completo (la edición de 2005) está disponible en pdf, por lo que puede descargarlo ahora mismo. El compilador se discute en el capítulo 12:

http://www-old.oberon.ethz.ch/WirthPubl/ProjectOberon.pdf

Niklaus Wirth, Jürg Gutknecht

(El tratamiento no es tan extenso como su libro sobre compiladores).

He leído varios libros sobre compiladores, y puedo secundar el libro del dragón, el tiempo dedicado a este libro es muy valioso.


Creo que la implementación del compilador moderno en ML es el mejor texto de escritura de compilación introductorio. También hay una Java y una C , cualquiera de las cuales podría ser más accesible dado el fondo de su idioma. El libro contiene una gran cantidad de material básico útil (escaneo y análisis, 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 formulario de asignación estática individual) en relativamente poco espacio (~ 500 páginas).

Prefiero la implementación del compilador moderno al libro de Dragon porque la implementación del compilador moderno estudia 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 leer este libro, estará listo para abordar los trabajos de investigación directamente para obtener más información si lo necesita.

Debo confesar que tengo una debilidad por la construcción del compilador de Niklaus Wirth . Está disponible en línea como un PDF. Me parece que la programación de Wirth es simplemente hermosa, sin embargo, algunas personas encuentran que su estilo es demasiado mínimo (por ejemplo, Wirth favorece los analizadores de descendencia recursivos, pero la mayoría de los cursos de CS se centran en las herramientas del generador de parser; los diseños de lenguaje de Wirth son bastante conservadores). La construcción del compilador es una destilación muy sucinta De las ideas básicas de Wirth, así que le guste o no su estilo, le recomiendo que lea este libro.


Debería revisar los " ichbins " de Darius Bacon, que es un compilador para un pequeño dialecto Lisp, que apunta a C, en poco más de 6 páginas de código. La ventaja que tiene sobre la mayoría de los compiladores de juguetes es que el lenguaje está lo suficientemente completo como para que el compilador esté escrito en él. (El tarball también incluye un intérprete para arrancar la cosa).

Hay más información sobre lo que me pareció útil para aprender a escribir un compilador en mi página web Ur-Scheme .



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

Python y Ruby son usualmente interpretados. Tal vez usted también quiera 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 generalmente se denomina 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 que transforma una gramática formal en código fuente o 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 desde los que puede elegir el que más le convenga. Dependiendo del generador de analizador que haya elegido, encontrará tutoriales en Internet y para los generadores de analizador realmente populares (como GNU bison) también hay libros.

Escribir un analizador para tu idioma puede ser muy difícil, pero esto depende de tu gramática. Así que sugiero mantener tu 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 en una representación intermedia lineal. Como un buen ejemplo de esto, el código de bytes de Lua se cita a menudo. Pero la representación intermedia realmente depende de tu idioma.

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

Si vas a compilar el lenguaje, 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 de ellos para uso general. La mayoría de ellos son demasiado académicos o demasiado prácticos. No hay "Enseñe a compilador a escribir 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 clase. Tal vez haya una biblioteca universitaria cerca de ti donde puedas tomar prestados libros de compiladores.

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


Encontré el libro del Dragón demasiado difícil de leer con demasiado enfoque en la teoría del lenguaje que no es realmente necesario para escribir un compilador en la práctica.

Me gustaría agregar el libro de Oberon que contiene la fuente completa de un compilador de Oberon increíblemente rápido y simple, el Proyecto Oberon .


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ífica de la plataforma.

No obstante, 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 con solo construir la mitad superior.

El solo hecho de hacer 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é). Así que tomará su programa fuente y lo convertirá en otra representación y realizará una optimización (si lo desea), que es el corazón de un compilador. La mitad inferior luego 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 de PE.

Algunos libros sobre este tema que me parecieron particularmente útiles fueron los Principios y Técnicas de los compiladores (o el Libro del Dragón, debido al lindo dragón en la portada). Tiene una gran teoría y definitivamente cubre las gramáticas libres de contexto de una manera realmente accesible. Además, para crear el analizador y analizador léxico, probablemente use las herramientas * nix lex y yacc. Y, lo que es bastante poco interesante, el libro llamado " lex and yacc " retomó donde el Libro del Dragón se quedó para esta parte.


Estoy buscando en el mismo concepto, y encontré este artículo prometedor de Joel Pobar,

Cree un compilador de idiomas para .NET Framework - no está seguro de a dónde se ha ido

Cree un compilador de idiomas para .NET Framework - copia en pdf del documento original

discute un concepto de alto nivel de un compilador y procede a inventar su propio lenguaje para el framework .Net. Aunque está dirigido a .Net Framework, muchos de los conceptos deberían poder reproducirse. El artículo cubre:

  1. Definición de idioma
  2. Escáner
  3. Analizador (el bit estoy interesado principalmente en)
  4. Apuntando al .Net Framework The
  5. Generador de códigos

Hay otros temas, pero te dan lo justo.

Está dirigido a personas que comienzan, escritas en C # (no del todo Java)

HTH

huesos


Lo sentimos, está en español, pero esta es la bibliografía de un curso llamado "Compiladores e Intérpretes" (Compiladores e intérpretes) en Argentina.

El curso fue desde la teoría del lenguaje formal hasta la construcción del compilador, y estos son los temas que necesita para construir, al menos, un compilador simple:

  • Diseño de compiladores en C.
    Allen I. Holub

    Prentice Hall. 1990.

  • Compiladores. Teoría y Construcción.
    Sanchís Llorca, FJ, Galán Pascual, C. Editorial Paraninfo. 1988.

  • Construcción del compilador.
    Niklaus Wirth

    Addison-Wesley. 1996.

  • Lenguajes, gramáticas y autómatas. Un enfoque práctico.
    Pedro Isasi Viñuela, Paloma Martínez Fernández, Daniel Borrajo Millán. Addison-Wesley Iberoamericana (España). 1997.

  • El arte del diseño del compilador. Teoría y práctica.
    Thomas Pittman, James Peters.

    Prentice Hall. 1992.

  • Construcción de compiladores orientados a objetos.
    Jim Holmes.
    Prentice Hall, Englewood Cliffs, NJ 1995

  • Compiladores. Conceptos Fundamentales.
    B. Teufel, S. Schmidt, T. Teufel.

    Addison-Wesley Iberoamericana. 1995.

  • Introducción a la teoría de los autómatas, lenguajes y computación.

    John E. Hopcroft. Jeffref D. Ullman.
    Addison-Wesley. 1979.

  • Introducción a los lenguajes formales.
    György E. Révész.

    Mc Graw Hill. 1983.

  • Técnicas de análisis. Una guía práctica.
    Dick Grune, Ceriel Jacobs.
    Impreso por los autores. 1995
    http://www.cs.vu.nl/~dick/PTAPG.html

  • YACC: Sin embargo, otro compilador-compilador.
    Stephen C. Johnson
    Informe Técnico de Ciencias de la Computación Nº 32, 1975. Laboratorios Bell. Murray Hill, Nuevo
    Jersey.

  • Lex: un generador de analizador léxico.
    ME Lesk, E. Schmidt. Informe Técnico de Ciencias de la Computación Nº 39, 1975. Laboratorios Bell. Murray Hill, Nueva Jersey.

  • lex y yacc.
    John R. Levine, Tony Mason, Doug Brown.
    O'Reilly y Asociados. 1995.

  • Elementos de la teoría de la computación.
    Harry R. Lewis, Christos H. Papadimitriou. Segunda Edición. Prentice Hall. 1998.

  • Un Algoritmo Eficiente para la Construcción del Grafo de Dependencia de Control.
    Salvador V. Cavadini.
    Trabajo Final de Grado para obtener el Título de Ingeniero en Computación.
    Facultad de Matemática Aplicada. UCSE 2001.


No es un libro, sino un documento técnico y una experiencia de aprendizaje enormemente divertida si desea saber más sobre los compiladores (y metacompiladores) ... Este sitio web lo guía a través de la creación de un sistema de compiladores completamente autónomo que puede compilarse a sí mismo y a otros idiomas:

Tutorial: Metacompiladores Parte 1

Todo se basa en un pequeño y sorprendente documento técnico de 10 páginas:

Val Schorre META II: un lenguaje de escritura compilador orientado a la sintaxis

de honesto a dios 1964. Aprendí a construir compiladores a partir de esto en 1970. Hay un momento alucinante cuando finalmente asimilas cómo el compilador puede regenerarse a sí mismo ...

Conozco al autor del sitio web desde mis días universitarios, pero no tengo nada que ver con el sitio web.


Recuerdo haber hecho esta pregunta hace unos siete años, cuando era bastante nuevo en la programación.

Fui muy cuidadoso cuando pregunté y, sorprendentemente, no recibí tantas críticas como usted está recibiendo aquí. Sin embargo, me apuntaron en la dirección del " Libro del Dragón ", que, en mi opinión, es un libro realmente genial que explica todo lo que necesitas saber para escribir un compilador (por supuesto, tendrás que dominar uno o dos idiomas). idiomas que conoces, el mejor.).

Y sí, mucha gente dice que leer ese libro es una locura y no aprenderá nada de él, pero no estoy de acuerdo con eso.

Muchas personas también dicen que escribir compiladores es estúpido y sin sentido. Bueno, hay varias razones por las que el desarrollo del compilador es útil:

  • Porque es divertido.
  • Es educativo. Cuando aprenda a escribir compiladores, aprenderá mucho sobre informática y otras técnicas que son útiles para escribir otras aplicaciones.
  • Si nadie escribiera compiladores, los lenguajes existentes no mejorarían.

No escribí mi propio compilador de inmediato, pero después de preguntar, sabía por dónde empezar. Y ahora, después de aprender muchos idiomas diferentes y leer el Libro del Dragón, escribir no es un gran problema. (También estoy estudiando cajeros automáticos de ingeniería informática, pero la mayor parte de lo que sé sobre programación es autodidacta).

En conclusión, The Dragon Book es un gran "tutorial". Pero dedique un tiempo a dominar uno o dos idiomas antes de intentar escribir un compilador. Sin embargo, no esperes ser un gurú del compilador dentro de la próxima década.

El libro también es bueno si desea aprender a escribir analizadores / intérpretes.


Si desea utilizar herramientas potentes de nivel superior en lugar de construir todo por sí mismo, una buena opción es repasar los proyectos y las lecturas de este curso . Es un curso de idiomas por el autor del motor de análisis de Java ANTLR. Puede obtener el libro para el curso en formato PDF de los programadores pragmáticos .

El curso repasa el compilador estándar que verías en otros lugares: análisis, tipos y verificación de tipos, polimorfismo, tablas de símbolos y generación de código. Casi lo único 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 posible escribir todo el compilador en un solo día (tengo una prueba de existencia de esto, aunque me refiero a ~ 24 horas). Es pesado en ingeniería práctica usando herramientas modernas, un poco más ligero en teoría.

LLVM, por cierto, es simplemente fantástico. Muchas situaciones en las que normalmente se puede compilar hasta el ensamblaje, sería mucho mejor compilar en la Representación Intermedia de LLVM . Es de nivel superior, multiplataforma y LLVM es bastante bueno para generar ensamblajes optimizados a partir de él.


Si está interesado en escribir un compilador para un lenguaje funcional (en lugar de uno de procedimiento), Simon Peyton-Jones y David Lester " Implementando lenguajes funcionales: un tutorial " es una excelente guía.

Los conceptos básicos de cómo funciona la evaluación funcional están guiados por ejemplos en un lenguaje funcional simple pero poderoso llamado "Núcleo". Además, cada parte del compilador de lenguaje Core se explica con ejemplos de código en Miranda (un lenguaje funcional puro muy similar a Haskell).

Se describen varios tipos diferentes de compiladores, pero incluso si solo sigue el llamado compilador de plantillas para Core, tendrá una excelente comprensión de lo que hace que la programación funcione.


Si tiene poco tiempo, recomiendo ethoberon.ethz.ch/WirthPubl/CBEAll.pdf , un pequeño folleto que puede leer en un día, pero explica los conceptos básicos (incluido cómo implementar lexers, analizadores de descendencia recursiva, 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.


Una forma fácil de crear un compilador es usar bison y flex (o similar), construir un árbol (AST) y generar código en C. La generación de código C es el paso más importante. Al generar el código C, su idioma funcionará automáticamente en todas las plataformas que tengan un compilador de C.

Generar código C es tan fácil como generar HTML (solo use imprimir, o equivalente), que a su vez es mucho más fácil que escribir un analizador C o un analizador HTML.


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

O echa un vistazo a SLANG . Esto es similar a "Vamos a construir un compilador", pero es un recurso mucho mejor, especialmente para los principiantes. Esto viene con un tutorial en pdf que tiene un enfoque de 7 pasos para enseñarle un compilador. Agregando el enlace de 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, escritos originalmente con C # y la plataforma .NET.





language-agnostic