Compilador-compilador

En informática , un compilador-compilador o generador de compiladores es una herramienta de programación que crea un analizador sintáctico , un intérprete o un compilador a partir de alguna forma de descripción formal de un lenguaje de programación y una máquina.

El tipo más común de compilador-compilador se llama generador de analizadores sintácticos . ^{[ 1 ]} Solo maneja análisis sintáctico .

La descripción formal de un lenguaje suele ser una gramática que se utiliza como entrada para un generador de analizadores sintácticos. A menudo se asemeja a la forma Backus-Naur (BNF), a la forma Backus-Naur extendida (EBNF) o tiene su propia sintaxis. Los archivos de gramática describen la sintaxis del lenguaje de programación de destino del compilador generado y las acciones que deben realizarse sobre sus construcciones específicas.

El generador de analizadores devuelve el código fuente del analizador sintáctico del lenguaje de programación. Este código fuente se compila en un analizador, que puede ser independiente o estar integrado. El analizador compilado recibe como entrada el código fuente del lenguaje de programación de destino y realiza una acción o genera un árbol de sintaxis abstracta (AST).

Los generadores de analizadores sintácticos no manejan la semántica del AST ni la generación de código máquina para la máquina de destino. ^{[ 2 ]}

Un metacompilador es una herramienta de desarrollo de software que se utiliza principalmente para la construcción de compiladores , traductores e intérpretes de otros lenguajes de programación. ^{[ 3 ]} La entrada a un metacompilador es un programa informático escrito en un metalenguaje de programación especializado , diseñado principalmente para la construcción de compiladores. ^{[ 3 ] [ 4 ]} El lenguaje del compilador resultante se denomina lenguaje objeto. La entrada mínima para producir un compilador es un metaprograma que especifica la gramática del lenguaje objeto y las transformaciones semánticas en un programa objeto . ^{[ 4 ] [ 5 ]}

Un generador de analizadores sintácticos típico asocia código ejecutable a cada una de las reglas de la gramática que deben ejecutarse cuando el analizador aplica dichas reglas. Estos fragmentos de código a veces se denominan rutinas de acción semántica, ya que definen la semántica de la estructura sintáctica que analiza el analizador. Dependiendo del tipo de analizador que se deba generar, estas rutinas pueden construir un árbol de análisis (o árbol de sintaxis abstracta ) o generar código ejecutable directamente.

Una de las primeras versiones (1964), sorprendentemente potente, de compiladores-compiladores es META II , que aceptaba una gramática analítica con funciones de salida que producían código máquina de pila, y es capaz de compilar su propio código fuente y otros lenguajes.

Entre los primeros programas de las versiones originales de Unix que se desarrollaban en Bell Labs se encontraba el sistema de dos partes lex y yacc , que normalmente se utilizaba para generar código en lenguaje de programación C , pero que contaba con un sistema de salida flexible que podía utilizarse para todo, desde lenguajes de programación hasta la conversión de archivos de texto . Sus versiones modernas de GNU son flex y bison .

Algunos compiladores experimentales toman como entrada una descripción formal de la semántica del lenguaje de programación, generalmente mediante semántica denotacional . Este enfoque se conoce como «compilación basada en semántica» y fue desarrollado por Peter Mosses en 1978 con su Sistema de Implementación Semántica (SIS). ^{[ 6 ]} Sin embargo, tanto el compilador generado como el código resultante eran ineficientes en tiempo y espacio. Actualmente no se construyen compiladores de producción de esta manera, pero la investigación continúa.

El proyecto Production Quality Compiler-Compiler ( PQCC ) de la Universidad Carnegie Mellon no formaliza la semántica, pero sí cuenta con un marco semiformal para la descripción de máquinas.

Existen muchos tipos de compiladores, incluidos los generadores de máquinas de reescritura ascendentes (véase JBurg ) que se utilizan para organizar los árboles de sintaxis según una gramática de reescritura para la generación de código, y los generadores de analizadores de gramática de atributos (por ejemplo, ANTLR se puede utilizar para la comprobación de tipos simultánea, la propagación de constantes y más durante la etapa de análisis).

El diseño del compilador-compilador original fue iniciado por Tony Brooker y Derrick Morris en 1959, con las pruebas iniciales comenzando en marzo de 1962. ^{[ 8 ]} El compilador-compilador Brooker Morris (BMCC) se utilizó para crear compiladores para la nueva computadora Atlas en la Universidad de Manchester , para varios lenguajes: Mercury Autocode , Extended Mercury Autocode, Atlas Autocode , ALGOL 60 y ASA Fortran . Aproximadamente al mismo tiempo, ET (Ned) Irons estaba realizando trabajos relacionados en Princeton, y Alick Glennie en el Atomic Weapons Research Establishment en Aldermaston, cuyo artículo "Syntax Machine" (desclasificado en 1977) inspiró la serie META de sistemas de escritura de traductores mencionados más adelante.

La historia temprana de los metacompiladores está estrechamente ligada a la historia del Grupo de Trabajo 1 de SIG/PLAN sobre Compiladores Dirigidos por Sintaxis. El grupo se inició principalmente gracias al esfuerzo de Howard Metcalfe en el área de Los Ángeles. ^{[ 9 ]} En el otoño de 1962, Howard Metcalfe diseñó dos intérpretes para escribir compiladores. Uno utilizaba una técnica de análisis de abajo hacia arriba basada en un método descrito por Ledley y Wilson. ^{[ 10 ]} El otro utilizaba un enfoque de arriba hacia abajo basado en el trabajo de Glennie para generar oraciones aleatorias en inglés a partir de una gramática libre de contexto . ^{[ 11 ]}

Al mismo tiempo, Val Schorre describió dos "metamáquinas", una generativa y otra analítica. La máquina generativa se implementó y produjo expresiones algebraicas aleatorias. Meta I, el primer metacompilador, fue implementado por Schorre en un IBM 1401 en la UCLA en enero de 1963. Sus intérpretes y metamáquinas originales fueron escritos directamente en un lenguaje pseudomáquina. META II , sin embargo, fue escrito en un metalenguaje de nivel superior capaz de describir su propia compilación en el lenguaje pseudomáquina. ^{[ 12 ] [ 13 ] [ 14 ]}

Lee Schmidt, de Bolt, Beranek y Newman, escribió un metacompilador en marzo de 1963 que utilizaba una pantalla CRT en el PDP-1 de tiempo compartido. ^{[ 15 ]} Este compilador producía código máquina real en lugar de código interpretado y se basaba parcialmente en Meta I.

Schorre desarrolló Meta II a partir de Meta I durante la primavera de 1963. El artículo sobre el sistema de metacompilación refinado, presentado en la conferencia ACM de Filadelfia de 1964, es el primer artículo sobre un metacompilador disponible como referencia general. La sintaxis y la técnica de implementación del sistema de Schorre sentaron las bases para la mayoría de los sistemas posteriores. El sistema se implementó en un pequeño microprocesador 1401 y se utilizó para implementar un lenguaje similar a ALGOL .

Inmediatamente después surgieron muchos sistemas similares.

Roger Rutman de AC Delco desarrolló e implementó LOGIK, un lenguaje para simulación de diseño lógico, en el IBM 7090 en enero de 1964. ^{[ 16 ]} Este compilador utilizaba un algoritmo que producía código eficiente para expresiones booleanas.

Otro artículo en las actas de la ACM de 1964 describe Meta III , desarrollado por Schneider y Johnson en la UCLA para la IBM 7090. ^{[ 17 ]} Meta III representa un intento de producir código máquina eficiente para una amplia gama de lenguajes. Meta III se implementó completamente en lenguaje ensamblador. Se escribieron dos compiladores en Meta III: CODOL, un compilador de demostración para la escritura de compiladores, y PUREGOL, un dialecto de ALGOL 60. (Fue una verdadera osadía llamarlo ALGOL).

A finales de 1964, Lee Schmidt desarrolló el metacompilador EQGEN, desde el PDP-1 hasta el Beckman 420. EQGEN era un lenguaje generador de ecuaciones lógicas.

En 1964, System Development Corporation inició un importante proyecto para el desarrollo de metacompiladores. Este proyecto incluye los potentes metacompiladores Book1 y Book2, escritos en Lisp, que cuentan con una amplia capacidad de búsqueda en árbol y de copia de seguridad. Meta 5, derivado de uno de los sistemas Q-32 de SDC, es un resultado de este proyecto. ^{[ 18 ]} El sistema Meta 5 incorpora la copia de seguridad del flujo de entrada y otras funcionalidades suficientes para analizar cualquier lenguaje sensible al contexto. Este sistema se lanzó con éxito a un gran número de usuarios y contaba con numerosas aplicaciones de manipulación de cadenas, además de la compilación. Dispone de elaboradas pilas de pila, funciones para la configuración y comprobación de atributos, y mecanismos de salida. El hecho de que Meta 5 traduzca con éxito programas JOVIAL a programas PL/I demuestra su potencia y flexibilidad.

Robert McClure, de Texas Instruments, inventó un compilador-compilador llamado TMG (presentado en 1965). TMG se utilizó para crear los primeros compiladores de lenguajes de programación como B , PL/I y ALTRAN . Junto con el metacompilador de Val Schorre, fue una de las primeras inspiraciones para el último capítulo de * El arte de la programación de computadoras * de Donald Knuth . ^{[ 19 ]}

El sistema LOT se desarrolló en 1966 en el Instituto de Investigación de Stanford y se basó casi exclusivamente en Meta II. ^{[ 20 ]} Contaba con nuevas construcciones específicas que le permitían generar un compilador que, a su vez, podía compilar un subconjunto de PL/I. Este sistema disponía de amplias herramientas para la recopilación de estadísticas y se utilizaba para estudiar las características del análisis descendente.

SIMPLE es un sistema de traducción especializado diseñado para ayudar a escribir preprocesadores para PL/I. SIMPLE, escrito en PL/I, se compone de tres componentes: un ejecutor, un analizador sintáctico y un constructor semántico. ^{[ 21 ]}

El compilador TREE-META fue desarrollado en el Instituto de Investigación de Stanford en Menlo Park, California, en abril de 1968. La historia temprana de los metacompiladores está bien documentada en el manual de TREE-META. TREE-META siguió algunos de los desarrollos de SDC. A diferencia de los metacompiladores anteriores, separó el procesamiento semántico del procesamiento sintáctico. Las reglas sintácticas contenían operaciones de construcción de árboles que combinaban elementos del lenguaje reconocidos con nodos de árbol. La representación de la estructura de árbol de la entrada se procesaba mediante una forma simple de reglas de análisis sintáctico. Estas reglas utilizaban el reconocimiento de nodos y la comprobación de atributos que, al coincidir, daban como resultado la ejecución de la acción asociada. Además, también se podía comprobar la similitud de elementos del árbol en una regla de análisis sintáctico. Las reglas de análisis sintáctico también constituían un lenguaje recursivo, pudiendo llamar a otras reglas pasando elementos del árbol antes de que se ejecutara la acción de la regla.

El concepto de metamáquina propuesto originalmente por Glennie es tan simple que se han diseñado tres versiones de hardware y una de ellas se ha implementado. Esta última se encuentra en la Universidad de Washington en San Luis. Esta máquina se construyó con componentes macromodulares y utiliza como instrucciones los códigos descritos por Schorre.

CWIC (Compiler for Writing and Implementing Compilers) es el último metacompilador Schorre conocido. Fue desarrollado en Systems Development Corporation por Erwin Book, Dewey Val Schorre y Steven J. Sherman. Con toda la potencia de Lisp 2, un lenguaje de procesamiento de listas que optimizaba algoritmos podía operar sobre listas y árboles generados sintácticamente antes de la generación de código. CWIC también incluía una tabla de símbolos integrada en el lenguaje.

Con el resurgimiento de los lenguajes específicos de dominio y la necesidad de generadores de analizadores sintácticos que sean fáciles de usar, fáciles de entender y fáciles de mantener, los metacompiladores se están convirtiendo en una herramienta valiosa para proyectos avanzados de ingeniería de software.

Otros ejemplos de generadores de analizadores sintácticos en la línea de yacc son ANTLR , Coco/R , ^{[ 22 ]} CUP, GNU Bison , Eli, ^{[ 23 ]} FSL, SableCC , SID (Syntax Improving Device), ^{[ 24 ]} y JavaCC . Si bien son útiles, los generadores de analizadores sintácticos puros solo abordan la parte de análisis sintáctico del problema de construir un compilador. Las herramientas con un alcance más amplio, como PQCC , Coco/R y DMS Software Reengineering Toolkit, brindan un soporte considerable para actividades posteriores al análisis sintáctico más difíciles, como el análisis semántico, la optimización y la generación de código.

Los primeros metacompiladores de Schorre, META I y META II, fueron desarrollados por D. Val Schorre en la UCLA. Posteriormente surgieron otros metacompiladores basados ​​en Schorre, cada uno con mejoras en el análisis del lenguaje y/o la generación de código.

En programación, es común usar el nombre del lenguaje de programación para referirse tanto al compilador como al lenguaje en sí, dependiendo del contexto. Un programa en C++ se compila con un compilador de C++. Esto también se aplica a continuación. Por ejemplo, META II es tanto el compilador como el lenguaje.

Los metalenguajes de la línea de metacompiladores Schorre son lenguajes de programación funcionales que utilizan ecuaciones de sintaxis de análisis gramatical descendente con construcciones de transformación de salida integradas.

Una ecuación sintáctica:

<nombre> = <cuerpo>;

es una función de prueba compilada que devuelve éxito o fracaso . <name> es el nombre de la función. <body> es una forma de expresión lógica que consta de pruebas que pueden agruparse, tener alternativas y producir resultados. Una prueba es como un booleano en otros lenguajes, donde éxito es verdadero y fracaso es falso .

Definir un lenguaje de programación analíticamente de arriba hacia abajo es natural. Por ejemplo, un programa podría definirse como:

programa = $declaración; 

Definir un programa como una secuencia de cero o más declaraciones.

En los lenguajes Schorre META X existe una regla de control. La regla de programa anterior es un ejemplo de esta regla. La regla de programa es una función de prueba que llama a una declaración, una regla de prueba , que devuelve éxito o fracaso . El operador de bucle $ llama repetidamente a la declaración hasta que se devuelve un fracaso . El operador $ siempre es exitoso, incluso cuando no hay ninguna declaración. El programa anterior siempre devolvería éxito. (En CWIC, un fallo prolongado puede omitir la declaración. Un fallo prolongado forma parte del sistema de retroceso de CWIC).

Los conjuntos de caracteres de estos primeros compiladores eran limitados. El carácter / se usaba para el operador de disyunción (o). "A o B" se escribe como A / B. Los paréntesis ( ) se usan para agrupar.

A (B / C)

Describe una construcción de A seguida de B o C. Como expresión booleana sería

A y (B o C)

Una secuencia XY implica el significado de X e Y. Los paréntesis ( ) indican agrupación y / el operador OR . El orden de evaluación siempre es de izquierda a derecha, ya que la secuencia de caracteres de entrada se especifica mediante el orden de las pruebas.

Para mayor claridad, se utilizan operadores especiales cuyo primer carácter es un "." Se utiliza .EMPTY como última alternativa cuando no es necesario que haya ninguna alternativa previa.

X (A / B / .VACÍO)

Indica que X puede ir seguido opcionalmente de A o B. Esta es una característica específica de estos metalenguajes, que son lenguajes de programación. El retroceso se evita con lo anterior. Otros sistemas de construcción de compiladores podrían haber declarado las tres secuencias posibles y dejado que el analizador sintáctico las interpretara.

Las características de los metalenguajes de metaprogramación mencionados anteriormente son comunes a todos los metacompiladores de Schorre y a los derivados de ellos.

 function-name(first-unparse_rule) => first-production_code_generator (segunda-regla_de_análisis) => segundo-generador_de_código_de_producción (third-unparse_rule) => third-production_code_generator ...

 expr_gen(ADD[expr_gen(x),expr_gen(y)]) => <AR + (x*16)+y;> registro de liberación(y); devolver x; (SUB[expr_gen(x),expr_gen(y)])=> <SR + (x*16)+y;> registro de liberación(y); devolver x; (MUL[expr_gen(x),expr_gen(y)])=> . . . (x)=> r1 = getreg(); cargar(r1, x); devolver r1; ...

 (x)=> devolver load(getreg(), x); 

• ANTLR
• GNU Bison
• Coco/R , Coco-2 ^{[ 22 ]}
• Cobre ^{[ 25 ]}
• Kit de herramientas de reingeniería de software DMS , un sistema de transformación de programas con generadores de analizadores sintácticos.
• Estudio de Gramática Epsilon
• Generador de analizadores Lemon
• LRSTAR: Generador de analizadores LR(*)
• META II
• parboiled , una biblioteca Java para construir analizadores sintácticos.
• Analizador Packrat
• PQCC , un compilador-compilador que es más que un generador de analizadores sintácticos.
• Dispositivo de mejora de la sintaxis (SID)
• SYNTAX , un conjunto de herramientas integradas para la construcción de compiladores.
• tacc - El compilador alternativo ^{[ 26 ]}
• ÁRBOL-META
• Yacc
• Texto cruzado
• XPL
• JavaCC

• Gramática de expresiones de análisis sintáctico
• Analizador LL
• Analizador LR
• Analizador LR simple
• Analizador LALR
• Analizador GLR
• Análisis de dominio
• Lenguaje específico del dominio
• Historia de la construcción de compiladores
  • Historia de la construcción de compiladores# Compiladores autoalojados
• Metacompilación
• Transformación del programa

• Brooker, RA ; MacCallum, IR; Morris, D.; Rohl, JS (1963). "El compilador-compilador" (PDF) . Annual Review in Automatic Programming . 3 : 229–275 . doi : 10.1016/S0066-4138(63)80009-9 .
• Brooker, R.A.; Morris, D.; Rohl, J.S. (febrero de 1967). "Experiencia con el compilador" (PDF) . Computer Journal . 9 : 350. doi : 10.1093/comjnl/9.4.350 . Consultado el 7 de mayo de 2021 .
• Napper, RB E (diciembre de 1965). Una introducción al compilador (PDF) .
• MacCallum, IR (enero de 1963). Algunos aspectos de la implementación del compilador en ATLAS (PDF) (Tesis).
• Johnson, Stephen C. (julio de 1975). Yacc: otro compilador más . Murray Hill, Nueva Jersey, EE. UU.: Bell Laboratories . Informe técnico de informática 32.
• McKeeman, William M.; Horning, James J .; Wortman, David B. (1970). Un generador de compiladores . Englewood Cliffs, Nueva Jersey, EE. UU.: Prentice-Hall . ISBN 978-0-13-155077-3. Consultado el 13 de diciembre de 2012 .

• Tony Brooker y el compilador Atlas
• Explicación del compilador. Listados del compilador (1963).
• Código fuente del compilador (comienza aproximadamente en la página 182 del PDF)
• Diagramas de flujo del compilador original
• Computer50.org , Brooker Autocodes
• Catalog.compilertools.net Archivado el 13/08/2011 en Wayback Machine , El catálogo de herramientas para la construcción de compiladores
• Labraj.uni-mb.si , Lisa
• Recursos de Skenz.it , Jflex y Cup (en italiano)