Historia de la construcción del compilador - History of compiler construction

En informática , un compilador es un programa informático que transforma el código fuente escrito en un lenguaje de programación o lenguaje informático (el lenguaje fuente ) en otro lenguaje informático (el lenguaje de destino , que a menudo tiene una forma binaria conocida como código objeto o código máquina ). La razón más común para transformar el código fuente es crear un programa ejecutable .

Cualquier programa escrito en un lenguaje de programación de alto nivel debe traducirse a código objeto antes de que pueda ejecutarse, por lo que todos los programadores que utilizan dicho lenguaje utilizan un compilador o un intérprete . Por tanto, los compiladores son muy importantes para los programadores. Las mejoras en un compilador pueden conducir a una gran cantidad de funciones mejoradas en los programas ejecutables.

El Compilador-Compilador de Calidad de Producción , a fines de la década de 1970, introdujo los principios de organización del compilador que todavía se utilizan ampliamente en la actualidad (por ejemplo, una sintaxis y semántica de manejo de front-end y un código de máquina de generación de back-end).

Primeros compiladores

El software para las primeras computadoras se escribía principalmente en lenguaje ensamblador y, antes de eso, directamente en código máquina . Por lo general, es más productivo para un programador utilizar un lenguaje de alto nivel, y los programas escritos en un lenguaje de alto nivel se pueden reutilizar en diferentes tipos de computadoras . Aun así, tomó un tiempo para que los compiladores se establecieran, porque generaban código que no funcionaba tan bien como el ensamblador escrito a mano, eran proyectos de desarrollo desalentadores por derecho propio, y la capacidad de memoria muy limitada de las primeras computadoras creó muchos Problemas técnicos para implementaciones prácticas de compiladores.

El primer compilador práctico fue escrito por Corrado Böhm , en 1951, para su tesis doctoral . El primer compilador implementado fue escrito por Grace Hopper , quien también acuñó el término "compilador", refiriéndose a su sistema A-0 que funcionaba como cargador o enlazador , no como la noción moderna de compilador. El primer Autocode y compilador en el sentido moderno fueron desarrollados por Alick Glennie en 1952 en la Universidad de Manchester para la computadora Mark 1 . El equipo de FORTRAN dirigido por John W. Backus en IBM introdujo el primer compilador disponible comercialmente, en 1957, que tardó 18 años-persona en crearse.

El primer compilador ALGOL 58 fue completado a fines de 1958 por Friedrich L. Bauer , Hermann Bottenbruch, Heinz Rutishauser y Klaus Samelson para la computadora Z22 . Bauer y col. había estado trabajando en la tecnología de compilación para Sequentielle Formelübersetzung (es decir , traducción secuencial de fórmulas ) en los años anteriores.

Para 1960, un compilador Fortran extendido, ALTAC, estaba disponible en Philco 2000, por lo que es probable que se compilara un programa Fortran para las arquitecturas de computadora IBM y Philco a mediados de 1960. El primer lenguaje de alto nivel multiplataforma demostrado conocido fue COBOL . En una demostración en diciembre de 1960, se compiló y ejecutó un programa COBOL tanto en el UNIVAC II como en el RCA 501.

Compiladores autohospedados

Como cualquier otro software, existen ventajas al implementar un compilador en un lenguaje de alto nivel. En particular, un compilador puede ser autohospedado , es decir, escrito en el lenguaje de programación que compila. La construcción de un compilador autohospedado es un problema de arranque , es decir, el primer compilador de este tipo para un lenguaje debe ser código de máquina escrito a mano o compilado por un compilador escrito en otro lenguaje, o compilado ejecutando el compilador en un intérprete .

Tesis doctoral Corrado Böhm

Corrado Böhm desarrolló un lenguaje, una máquina y un método de traducción para compilar ese lenguaje en la máquina en su tesis doctoral de 1951. No solo describió un compilador completo, sino que también definió por primera vez ese compilador en su propio idioma. El lenguaje era interesante en sí mismo, porque cada declaración (incluidas las declaraciones de entrada, las declaraciones de salida y las declaraciones de control) era un caso especial de una declaración de asignación .

NELIAC

El Compilador de ALGOL Internacional del Laboratorio de Electrónica Naval o NELIAC fue una implementación de dialecto y compilador del lenguaje de programación ALGOL 58 desarrollado por el Laboratorio de Electrónica Naval en 1958.

NELIAC fue una creación de Harry Huskey , entonces presidente de ACM y un científico informático muy conocido (y más tarde supervisor académico de Niklaus Wirth ), y con el apoyo de Maury Halstead, director del centro de computación de NEL. La primera versión se implementó en el prototipo de computadora USQ-17 (llamada Countess) en el laboratorio. Fue el primer compilador autocompilable del mundo: el compilador se codificó primero en forma simplificada en lenguaje ensamblador (el bootstrap ), luego se reescribió en su propio lenguaje y se compiló mediante el bootstrap, y finalmente se volvió a compilar por sí mismo, haciendo que el bootstrap obsoleto.

Ceceo

Otro compilador de autohospedaje temprano fue escrito para Lisp por Tim Hart y Mike Levin en el MIT en 1962. Escribieron un compilador Lisp en Lisp, probándolo dentro de un intérprete Lisp existente. Una vez que habían mejorado el compilador hasta el punto en que podía compilar su propio código fuente, se autohospedaba.

El compilador tal como existe en la cinta del compilador estándar es un programa en lenguaje de máquina que se obtuvo haciendo que la definición de expresión S del compilador trabaje sobre sí mismo a través del intérprete. (Nota 39 de AI)

Esta técnica solo es posible cuando ya existe un intérprete para el mismo idioma que se va a compilar. Toma prestada directamente de la noción de ejecutar un programa en sí mismo como entrada, que también se utiliza en varias pruebas de la informática teórica , como la prueba de que el problema de la detención es indecidible .

Adelante

Forth es un ejemplo de un compilador autohospedado. Las funciones de autocompilación y compilación cruzada de Forth se confunden comúnmente con metacompilación y metacompiladores . Como Lisp , Forth es un lenguaje de programación extensible . Son las características del lenguaje de programación extensible de Forth y Lisp las que les permiten generar nuevas versiones de sí mismos o portarse a nuevos entornos.

Gramáticas y analizadores sintácticos libres de contexto

Un analizador es un componente importante de un compilador. Analiza el código fuente de un lenguaje de programación de computadoras para crear alguna forma de representación interna. Los lenguajes de programación tienden a especificarse en términos de una gramática libre de contexto porque se pueden escribir analizadores rápidos y eficientes para ellos. Los analizadores pueden escribirse a mano o generarse mediante un generador de analizadores sintácticos . Una gramática libre de contexto proporciona un mecanismo simple y preciso para describir cómo se construyen las construcciones del lenguaje de programación a partir de bloques más pequeños . El formalismo de las gramáticas libres de contexto fue desarrollado a mediados de la década de 1950 por Noam Chomsky .

La estructura de bloques se introdujo en los lenguajes de programación de computadoras por el proyecto ALGOL (1957-1960), que, como consecuencia, también presentó una gramática libre de contexto para describir la sintaxis ALGOL resultante.

Las gramáticas libres de contexto son lo suficientemente simples como para permitir la construcción de algoritmos de análisis eficientes que, para una cadena dada, determinan si se puede generar a partir de la gramática y cómo. Si un diseñador de lenguajes de programación está dispuesto a trabajar con algunos subconjuntos limitados de gramáticas libres de contexto, son posibles analizadores sintácticos más eficientes.

Análisis sintáctico LR

El analizador sintáctico LR (de izquierda a derecha) fue inventado por Donald Knuth en 1965 en un artículo, "Sobre la traducción de idiomas de izquierda a derecha". Un analizador sintáctico LR es un analizador que lee la entrada de L eft a derecha (tal como aparecería si se muestra visualmente) y produce un R derivación ightmost . También se utiliza el término analizador sintáctico LR ( k ) , donde k se refiere al número de símbolos de entrada anticipada no consumidos que se utilizan para tomar decisiones de análisis sintáctico.

Knuth demostró que las gramáticas LR ( k ) se pueden analizar con un tiempo de ejecución esencialmente proporcional a la longitud del programa, y que cada gramática LR ( k ) para k > 1 se puede transformar mecánicamente en una gramática LR (1) para la misma. idioma. En otras palabras, solo es necesario tener un símbolo de anticipación para analizar cualquier gramática determinista libre de contexto (DCFG).

Korenjak (1969) fue el primero en mostrar que se podían producir analizadores sintácticos para lenguajes de programación utilizando estas técnicas. Frank DeRemer ideó las técnicas más prácticas Simple LR (SLR) y Look-ahead LR (LALR), publicadas en su tesis doctoral en el MIT en 1969. Este fue un avance importante, porque los traductores LR (k), según la definición de Donald Knuth, eran demasiado grandes para su implementación en sistemas informáticos en las décadas de 1960 y 1970.

En la práctica, LALR ofrece una buena solución; el poder agregado de los analizadores sintácticos LALR (1) sobre los analizadores sintácticos SLR (1) (es decir, LALR (1) puede analizar gramáticas más complejas que SLR (1)) es útil y, aunque LALR (1) no es comparable con LL ( 1) (Ver más abajo) (LALR (1) no puede analizar todas las gramáticas LL (1)), la mayoría de las gramáticas LL (1) encontradas en la práctica pueden ser analizadas por LALR (1). Las gramáticas LR (1) son más poderosas de nuevo que LALR (1); sin embargo, una gramática LR (1) requiere un analizador sintáctico LR canónico que sería de tamaño extremadamente grande y no se considera práctico. La sintaxis de muchos lenguajes de programación se define mediante gramáticas que se pueden analizar con un analizador LALR (1) y, por esta razón, los compiladores suelen utilizar analizadores LALR para realizar análisis de sintaxis del código fuente.

Un analizador de ascenso recursivo implementa un analizador LALR utilizando funciones recursivas recursivas en lugar de tablas. Por lo tanto, el analizador se codifica directamente en el idioma anfitrión de manera similar a la descendencia recursiva . La codificación directa generalmente produce un analizador que es más rápido que su equivalente basado en tablas por la misma razón que la compilación es más rápida que la interpretación. También es (en principio) posible editar manualmente un analizador sintáctico ascendente recursivo, mientras que una implementación tabular es casi ilegible para el humano promedio.

El ascenso recursivo fue descrito por primera vez por Thomas Pennello en su artículo "Análisis sintáctico LR muy rápido" en 1986. La técnica fue posteriormente expuesta por GH Roberts en 1988, así como en un artículo de Leermakers, Augusteijn, Kruseman Aretz en 1992 en la revista Theoretical Ciencias de la Computación .

Análisis de LL

Un analizador LL analiza la entrada de L eft a la derecha y construye una derivación L eftmost de la oración (por lo tanto LL, en contraposición a LR). La clase de gramáticas que se pueden analizar de esta manera se conoce como gramáticas LL . Las gramáticas LL son una clase aún más restringida de gramáticas libres de contexto que las gramáticas LR. Sin embargo, son de gran interés para los escritores de compiladores, porque dicho analizador es simple y eficiente de implementar.

Las gramáticas LL (k) se pueden analizar mediante un analizador sintáctico descendente recursivo que normalmente se codifica a mano, aunque también se podría utilizar una notación como META II .

El diseño de ALGOL provocó la investigación de la descendencia recursiva, ya que el lenguaje ALGOL en sí es recursivo. El concepto de análisis sintáctico de descendencia recursiva se discutió en la edición de enero de 1961 de Communications of the ACM en artículos separados de AA Grau y Edgar T. "Ned" Irons . Richard Waychoff y sus colegas también implementaron el descenso recursivo en el compilador ALGOL de Burroughs en marzo de 1961, los dos grupos utilizaron enfoques diferentes pero estaban al menos en contacto informal.

Lewis y Stearns (1968) introdujeron la idea de las gramáticas LL (1).

Niklaus Wirth popularizó el descenso recursivo con PL / 0 , un lenguaje de programación educativo utilizado para enseñar la construcción de compiladores en la década de 1970.

El análisis sintáctico LR puede manejar una gama más amplia de idiomas que el análisis sintáctico LL , y también es mejor en el informe de errores (esto es discutible, se requiere REFERENCIA), es decir, detecta errores sintácticos cuando la entrada no se ajusta a la gramática lo antes posible.

Analizador Earley

En 1970, Jay Earley inventó lo que se conoció como el analizador sintáctico Earley . Los analizadores sintácticos de Earley son atractivos porque pueden analizar todos los lenguajes sin contexto de manera razonablemente eficiente.

Idiomas de descripción gramatical

John Backus propuso "fórmulas metalingüísticas" para describir la sintaxis del nuevo lenguaje de programación IAL, conocido hoy como ALGOL 58 (1959). El trabajo de Backus se basó en el sistema canónico Post ideado por Emil Post .

Un mayor desarrollo de ALGOL condujo a ALGOL 60 ; en su informe (1963), Peter Naur nombró a la notación Backus forma normal (BNF) de Backus y la simplificó para minimizar el conjunto de caracteres utilizado. Sin embargo, Donald Knuth argumentó que BNF debería leerse más bien como la forma Backus-Naur , y ese se ha convertido en el uso comúnmente aceptado.

Niklaus Wirth definió la forma extendida Backus-Naur (EBNF), una versión refinada de BNF, a principios de la década de 1970 para PL / 0. La forma aumentada Backus-Naur (ABNF) es otra variante. Tanto EBNF como ABNF se utilizan ampliamente para especificar la gramática de los lenguajes de programación, como entradas a los generadores de analizadores sintácticos y en otros campos, como la definición de protocolos de comunicación.

Generadores de analizadores

Un generador de analizador genera la parte del analizador léxico de un compilador. Es un programa que toma una descripción de una gramática formal de un lenguaje de programación específico y produce un analizador para ese lenguaje. Ese analizador se puede utilizar en un compilador para ese lenguaje específico. El analizador detecta e identifica las palabras y los símbolos reservados del idioma específico de un flujo de texto y los devuelve como tokens al código que implementa la validación sintáctica y la traducción al código objeto. Esta segunda parte del compilador también puede ser creada por un compilador-compilador usando una descripción de sintaxis de reglas de precedencia formal como entrada.

El primer compilador-compilador que usó ese nombre fue escrito por Tony Brooker en 1960 y se usó para crear compiladores para la computadora Atlas en la Universidad de Manchester , incluido el compilador Atlas Autocode . Sin embargo, era bastante diferente de los compiladores-compiladores modernos, y hoy probablemente se describiría como algo entre un compilador genérico altamente personalizable y un lenguaje de sintaxis extensible . El nombre "compilador-compilador" era mucho más apropiado para el sistema de Brooker que para la mayoría de los compiladores-compiladores modernos, que se describen con mayor precisión como generadores de analizadores sintácticos. Es casi seguro que el nombre "Compilador-Compilador" ha entrado en uso común debido a que se recuerda Yacc en lugar del trabajo de Brooker.

A principios de la década de 1960, Robert McClure de Texas Instruments inventó un compilador-compilador llamado TMG , el nombre tomado de "transfiguración". En los años siguientes, TMG se trasladó a varios ordenadores centrales UNIVAC e IBM.

El proyecto Multics , una empresa conjunta entre MIT y Bell Labs , fue uno de los primeros en desarrollar un sistema operativo en un lenguaje de alto nivel. Se eligió PL / I como lenguaje, pero un proveedor externo no pudo proporcionar un compilador funcional. El equipo de Multics desarrolló su propio dialecto de subconjunto de PL / I conocido como Early PL / I (EPL) como su lenguaje de implementación en 1964. TMG fue portado a la serie GE-600 y utilizado para desarrollar EPL por Douglas McIlroy , Robert Morris y otros. .

Poco después de que Ken Thompson escribiera la primera versión de Unix para el PDP-7 en 1969, Douglas McIlroy creó el primer lenguaje de nivel superior del nuevo sistema: una implementación del TMG de McClure. TMG fue también la herramienta de definición compilador utilizado por Ken Thompson a escribir el compilador para el lenguaje B en su PDP-7 en 1970. B fue el antepasado inmediato del C .

Uno de los primeros generadores de analizadores sintácticos LALR se llamaba "TWS", creado por Frank DeRemer y Tom Pennello.

XPL

XPL es un dialecto del lenguaje de programación PL / I , utilizado para el desarrollo de compiladores para lenguajes de computadora. Fue diseñado e implementado en 1967 por un equipo con William M. McKeeman , James J. Horning y David B. Wortman en la Universidad de Stanford y la Universidad de California, Santa Cruz . Se anunció por primera vez en la Conferencia de Computación Conjunta de Otoño de 1968 en San Francisco.

XPL presentó un sistema de escritura de traductor relativamente simple denominado ANALYZER , basado en una técnica de análisis de precedencia de compilador de abajo hacia arriba llamada MSP (precedencia de estrategia mixta). XPL se cargó a través de Burroughs Algol en la computadora IBM System / 360 . (Algunas versiones posteriores de XPL utilizadas en proyectos internos de la Universidad de Toronto utilizaron un analizador SLR (1), pero esas implementaciones nunca se han distribuido).

Yacc

Yacc es un generador de analizador sintáctico (en general, compilador-compilador ), que no debe confundirse con lex , que es un analizador léxico que Yacc utiliza con frecuencia como primera etapa. Yacc fue desarrollado por Stephen C. Johnson en AT&T para el sistema operativo Unix . El nombre es un acrónimo de " Yet Another Compiler Compiler ". Genera un compilador LALR (1) basado en una gramática escrita en una notación similar a la forma Backus-Naur.

Johnson trabajó en Yacc a principios de la década de 1970 en Bell Labs . Estaba familiarizado con TMG y su influencia se puede ver en Yacc y el diseño del lenguaje de programación C. Debido a que Yacc era el generador de compiladores predeterminado en la mayoría de los sistemas Unix, se distribuyó y utilizó ampliamente. Los derivados como GNU Bison todavía están en uso.

El compilador generado por Yacc requiere un analizador léxico . Los generadores de analizadores léxicos, como lex o flex, están ampliamente disponibles. El estándar IEEE POSIX P1003.2 define la funcionalidad y los requisitos para Lex y Yacc.

Coco / R

Coco / R es un generador de analizadores sintácticos que genera analizadores sintácticos LL (1) en Modula-2 (con complementos para otros lenguajes) a partir de gramáticas de entrada escritas en una variante de EBNF. Fue desarrollado por Hanspeter Mössenböck en el Instituto Federal Suizo de Tecnología en Zurich (ETHZ) en 1985.

ANTLR

ANTLR es un generador de analizadores sintácticos que genera analizadores sintácticos LL (*) en Java a partir de gramáticas de entrada escritas en una variante de EBNF. Fue desarrollado por Terence Parr en la Universidad de San Francisco a principios de la década de 1990 como sucesor de un generador anterior llamado PCCTS.

Metacompiladores

Los metacompiladores se diferencian de los generadores de analizadores sintácticos, tomando como entrada un programa escrito en un metalenguaje . Su entrada consiste en una fórmula de análisis gramatical combinada con operaciones de transformación incrustadas que construyen árboles de sintaxis abstracta, o simplemente generan cadenas de texto reformateadas que pueden ser código de máquina de pila.

Muchos pueden programarse en su propio metalenguaje, lo que les permite compilarse a sí mismos, lo que los convierte en compiladores de lenguaje extensible autohospedados.

Muchos metacompiladores se basan en el trabajo de Dewey Val Schorre . Su compilador META II , lanzado por primera vez en 1964, fue el primer metacompilador documentado. Capaz de definir su propio lenguaje y otros, META II aceptó la fórmula de sintaxis con salida incorporada (producción de código) . También se tradujo a una de las primeras instancias de una máquina virtual . El análisis léxico se realizó mediante funciones integradas de reconocimiento de tokens: .ID, .STRING y .NUMBER. Las cadenas entre comillas en la fórmula de sintaxis reconocen los lexemas que no se guardan.

TREE-META , un metacompilador de Schorre de segunda generación, apareció alrededor de 1968. Amplió las capacidades de META II, agregando reglas no analizadas que separan la producción de código del análisis gramatical. Las operaciones de transformación de árbol en la fórmula de sintaxis producen árboles de sintaxis abstractos sobre los que operan las reglas de análisis. La coincidencia de patrones de árboles no analizados proporcionó la capacidad de optimización de mirillas .

CWIC , descrito en una publicación de ACM de 1970, es un metacompilador de Schorre de tercera generación que agregó reglas de lexing y operadores de retroceso al análisis gramatical. LISP 2 se casó con las reglas unparse de TREEMETA en el lenguaje generador de CWIC. Con el procesamiento de LISP 2 [[]], CWIC puede generar código totalmente optimizado. CWIC también proporcionó generación de código binario en secciones de código con nombre. Las compilaciones de una o varias pasadas se pueden implementar usando CWIC.

CWIC compilado en instrucciones de código de máquina direccionables por bytes de 8 bits diseñadas principalmente para producir código IBM System / 360.

Las generaciones posteriores no están documentadas públicamente. Una característica importante sería la abstracción del conjunto de instrucciones del procesador de destino, generando macros en un conjunto de instrucciones pseudo-máquina, que podrían definirse por separado o mapearse a las instrucciones de una máquina real. Las optimizaciones que se aplican a instrucciones secuenciales se podrían aplicar a la pseudoinstrucción antes de su expansión al código de máquina de destino.

Compilación cruzada

Un compilador cruzado se ejecuta en un entorno pero produce código objeto para otro. Los compiladores cruzados se utilizan para el desarrollo integrado, donde la computadora de destino tiene capacidades limitadas.

Un ejemplo temprano de compilación cruzada fue AIMICO, donde se utilizó un programa FLOW-MATIC en un UNIVAC II para generar lenguaje ensamblador para el IBM 705 , que luego se ensambló en la computadora IBM.

El compilador ALGOL 68C generó una salida ZCODE , que luego podría ser compilada en el código de máquina local por un traductor ZCODE o ejecutada interpretada. ZCODE es un lenguaje intermedio basado en registros. Esta capacidad para interpretar o compilar ZCODE alentó la migración de ALGOL 68C a numerosas plataformas informáticas diferentes.

Optimización de compiladores

La optimización del compilador es el proceso de mejorar la calidad del código objeto sin cambiar los resultados que produce.

Los desarrolladores del primer compilador FORTRAN tenían como objetivo generar un código que fuera mejor que el ensamblador codificado a mano promedio, para que los clientes realmente usaran su producto. En uno de los primeros compiladores reales, a menudo tuvieron éxito.

Los compiladores posteriores, como el compilador Fortran IV de IBM , dieron más prioridad a los buenos diagnósticos y la ejecución más rápida, a expensas de la optimización del código objeto . No fue hasta la serie IBM System / 360 que IBM proporcionó dos compiladores separados: un verificador de código de ejecución rápida y otro más lento y de optimización.

Frances E. Allen , trabajando sola y junto con John Cocke , introdujo muchos de los conceptos de optimización. El artículo de 1966 de Allen, Optimización de programas, introdujo el uso de estructuras de datos de gráficos para codificar el contenido del programa para su optimización. Sus artículos de 1970, Control Flow Analysis y A Basis for Program Optimization establecieron los intervalos como el contexto para el análisis y la optimización del flujo de datos eficientes y efectivos. Su artículo de 1971 con Cocke, A Catalog of Optimizing Transformations , proporcionó la primera descripción y sistematización de la optimización de transformaciones. Sus artículos de 1973 y 1974 sobre análisis de flujo de datos entre procedimientos extendieron el análisis a programas completos. Su artículo de 1976 con Cocke describe una de las dos principales estrategias de análisis utilizadas en la optimización de compiladores en la actualidad.

Allen desarrolló e implementó sus métodos como parte de compiladores para IBM 7030 Stretch - Harvest y el sistema de computación avanzada experimental . Este trabajo estableció la viabilidad y la estructura de los optimizadores modernos independientes del lenguaje y de la máquina. Continuó estableciendo y dirigiendo el proyecto PTRAN sobre la ejecución automática paralela de los programas FORTRAN. Su equipo de PTRAN desarrolló nuevos esquemas de detección de paralelismo y creó el concepto del gráfico de dependencia del programa, el método de estructuración principal utilizado por la mayoría de los compiladores de paralelismo.

Lenguajes de programación y sus compiladores de John Cocke y Jacob T. Schwartz , publicado a principios de 1970, dedicó más de 200 páginas a los algoritmos de optimización. Incluía muchas de las técnicas ahora familiares, como la eliminación de código redundante y la reducción de la fuerza .

Optimización de mirillas

La optimización de mirillas es una técnica de optimización simple pero efectiva. Fue inventado por William M. McKeeman y publicado en 1965 en CACM. Se usó en el compilador XPL que McKeeman ayudó a desarrollar.

Optimizador de Capex COBOL

Capex Corporation desarrolló el "Optimizador COBOL" a mediados de la década de 1970 para COBOL . Este tipo de optimizador dependía, en este caso, del conocimiento de las "debilidades" en el compilador IBM COBOL estándar, y en realidad reemplazó (o parcheó ) secciones del código objeto con código más eficiente. El código de reemplazo podría reemplazar una búsqueda de tabla lineal con una búsqueda binaria, por ejemplo, o algunas veces simplemente reemplazar una instrucción relativamente "lenta" con una conocida más rápida que de otra manera sería funcionalmente equivalente dentro de su contexto. Esta técnica ahora se conoce como " Reducción de la fuerza ". Por ejemplo, en el hardware IBM System / 360 , la instrucción CLI fue, según el modelo particular, entre dos y cinco veces más rápida que una instrucción CLC para comparaciones de un solo byte.

Los compiladores modernos generalmente brindan opciones de optimización para permitir a los programadores elegir si ejecutar o no una pasada de optimización.

Diagnósticos

Cuando un compilador recibe un programa sintácticamente incorrecto, es útil un mensaje de error claro y bueno. Desde la perspectiva del redactor del compilador, a menudo es difícil de lograr.

El compilador WATFIV Fortran se desarrolló en la Universidad de Waterloo , Canadá, a fines de la década de 1960. Fue diseñado para dar mejores mensajes de error que los compiladores Fortran de IBM de la época. Además, WATFIV era mucho más útil porque combinaba la compilación, el enlace y la ejecución en un solo paso, mientras que los compiladores de IBM tenían tres componentes separados para ejecutar.

SOCIEDAD ANÓNIMA

PL / C fue un lenguaje de programación de computadoras desarrollado en la Universidad de Cornell a principios de la década de 1970. Si bien PL / C era un subconjunto del lenguaje PL / I de IBM, fue diseñado con el objetivo específico de ser utilizado para enseñar programación. Los dos investigadores y profesores académicos que diseñaron PL / C fueron Richard W. Conway y Thomas R. Wilcox. Presentaron el célebre artículo "Diseño e implementación de un compilador de diagnóstico para PL / I" publicado en las Comunicaciones de ACM en marzo de 1973.

PL / C eliminó algunas de las características más complejas de PL / I y agregó amplias funciones de depuración y recuperación de errores. El compilador PL / C tenía la capacidad inusual de nunca fallar al compilar ningún programa, mediante el uso de una amplia corrección automática de muchos errores de sintaxis y convirtiendo los errores de sintaxis restantes en declaraciones de salida.

Recopilación justo a tiempo

La compilación Just-in-time (JIT) es la generación de código ejecutable sobre la marcha o lo más cerca posible de su ejecución real, para aprovechar las métricas de tiempo de ejecución u otras opciones que mejoran el rendimiento.

Representación intermedia

La mayoría de los compiladores modernos tienen un analizador léxico y un analizador que producen una representación intermedia del programa. La representación intermedia es una secuencia simple de operaciones que puede ser utilizada por un optimizador y un generador de código que produce instrucciones en el lenguaje de máquina del procesador de destino. Debido a que el generador de código usa una representación intermedia, el mismo generador de código se puede usar para muchos lenguajes de alto nivel diferentes.

Hay muchas posibilidades para la representación intermedia. El código de tres direcciones , también conocido como cuádruple o cuádruple, es una forma común, donde hay un operador, dos operandos y un resultado. El código de dos direcciones o los triples tienen una pila en la que se escriben los resultados, en contraste con las variables explícitas del código de tres direcciones.

La asignación única estática (SSA) fue desarrollada por Ron Cytron , Jeanne Ferrante , Barry K. Rosen , Mark N. Wegman y F. Kenneth Zadeck , investigadores de IBM en la década de 1980. En SSA, a una variable se le da un valor solo una vez. Se crea una nueva variable en lugar de modificar una existente. SSA simplifica la optimización y la generación de código.

Codigo de GENERACION

Un generador de código genera instrucciones en lenguaje de máquina para el procesador de destino.

Asignación de registros

El algoritmo Sethi-Ullman o la numeración Sethi-Ullman es un método para minimizar el número de registros necesarios para contener variables.

Compiladores notables

Kit de compilación de Amsterdam por Andrew Tanenbaum y Ceriel Jacobs
Berkeley Pascal, escrito por Ken Thompson en 1975. Bill Joy y otros en la Universidad de California, Berkeley agregaron mejoras
Colección GNU Compiler , anteriormente GNU C Compiler. Originalmente escrito por Richard Stallman en 1987, GCC es un importante compilador moderno que se utiliza para compilar muchos proyectos de software libre , especialmente Linux .
LLVM , anteriormente conocido como la máquina virtual de bajo nivel
Small-C de Ron Cain y James E Hendrix
Turbo Pascal , creado por Anders Hejlsberg , lanzado por primera vez en 1983.
WATFOR , creado en la Universidad de Waterloo . Uno de los primeros compiladores educativos populares, aunque ahora en gran parte obsoleto.

Ver también

Historia de los lenguajes de programación
Lex (y analizador léxico Flex ), el analizador de tokens comúnmente utilizado junto con yacc (y Bison).
BNF , una metasintaxis utilizada para expresar gramática libre de contexto : es decir, una forma formal de describir lenguajes formales.
Auto-intérprete , un intérprete escrito en un idioma que puede interpretar.

Referencias

Otras lecturas

Backus, John , et al., "The FORTRAN Automatic Coding System" , Actas de la Western Joint Computer Conference, Los Ángeles, California, febrero de 1957. Describe el diseño y la implementación del primer compilador FORTRAN por parte del equipo de IBM.
Knuth, DE, traducción algebraica RUNCIBLE en una computadora limitada , Communications of the ACM, vol. 2, pág. 18, (noviembre de 1959).
Irons, Edgar T., Un compilador dirigido por sintaxis para ALGOL 60 , Communications of the ACM, Vol. 4, pág. 51. (enero de 1961)
Dijkstra, Edsger W. (1961). "Traducción ALGOL 60: Un traductor ALGOL 60 para el X1 y un traductor para ALGOL 60 (PDF) (Informe técnico). Amsterdam: Mathematisch Centrum. 35.
Conway, Melvin E. , Diseño de un compilador de diagrama de transición separable , Comunicaciones del ACM, Volumen 6, Número 7 (julio de 1963)
Floyd, RW , Análisis sintáctico y precedencia de operadores , Journal of the ACM, Vol. 10, pág. 316. (julio de 1963).
Cheatham, TE y Sattley, K., compilación dirigida por sintaxis , SJCC p. 31. (1964).
Randell, Brian ; Russell, Lawford John, Implementación de ALGOL 60: la traducción y el uso de programas ALGOL 60 en una computadora , Academic Press, 1964
Knuth, DE (julio de 1965). "Sobre la traducción de idiomas de izquierda a derecha" (PDF) . Información y control . 8 (6): 607–639. doi : 10.1016 / S0019-9958 (65) 90426-2 . Archivado desde el original (PDF) el 15 de marzo de 2012 . Consultado el 29 de mayo de 2011 .
Cocke, John ; Schwartz, Jacob T. , Lenguajes de programación y sus compiladores: notas preliminares , informe técnico del Instituto Courant de Ciencias Matemáticas , Universidad de Nueva York , 1969.
Bauer, Friedrich L .; Eickel, Jürgen (Eds.), Compiler Construction, An Advanced Course , 2ª ed. Notas de conferencia en Ciencias de la Computación 21, Springer 1976, ISBN 3-540-07542-9
Gries, David , Compiler Construction for Digital Computers , Nueva York: Wiley, 1971. ISBN 0-471-32776-X

enlaces externos

Construcción del compilador antes de 1980 - Lista de literatura anotada por Dick Grune
"Una historia de la escritura de compiladores" (PDF) . Informática y Automatización . XI (12): 8-10, 12, 14, 24-25. Diciembre de 1962.

Languages

In other projects