Historia de la construcción de compiladores

Historia de la informática
Hardware
Software
Ciencias de la Computación
Conceptos modernos
Por país
Cronología de la informática
Glosario de informática

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 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 poder ejecutarse, por lo que todos los programadores que utilizan un lenguaje de este tipo utilizan un compilador o un intérprete . Las mejoras en un compilador pueden dar lugar a una gran cantidad de funciones mejoradas en los programas ejecutables.

El compilador de calidad de producción, Compiler-Compiler , a finales 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, un front-end que maneja la sintaxis y la semántica y un back-end que genera el código de máquina).

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í, los compiladores tardaron un tiempo en establecerse, porque generaban un código que no funcionaba tan bien como el ensamblador escrito a mano, eran proyectos de desarrollo abrumadores por sí mismos y la capacidad de memoria muy limitada de las primeras computadoras creó muchos problemas técnicos para las implementaciones prácticas de compiladores.

Entre 1942 y 1945, Konrad Zuse desarrolló Plankalkül ("cálculo de planos"), el primer lenguaje de alto nivel para ordenador, para el que imaginó un Planfertigungsgerät ("dispositivo de montaje de planos"), que traduciría automáticamente la formulación matemática de un programa en una película perforada legible por máquina . [1] Sin embargo, el primer compilador real para el lenguaje se implementó solo décadas después.

Entre 1949 y 1951, Heinz Rutishauser propuso Superplan , un lenguaje de alto nivel y traductor automático. [2] Sus ideas fueron refinadas posteriormente por Friedrich L. Bauer y Klaus Samelson . [3]

El primer compilador práctico fue escrito por Corrado Böhm en 1951 para su tesis doctoral, [4] [5] uno de los primeros doctorados en informática otorgados en cualquier parte del mundo.

El primer compilador implementado fue escrito por Grace Hopper , quien también acuñó el término "compilador", [6] [7] refiriéndose a su sistema A-0 que funcionaba como un cargador o enlazador , no a la noción moderna de un 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. [8] [9] El equipo FORTRAN dirigido por John W. Backus en IBM presentó el primer compilador disponible comercialmente, en 1957, cuya creación llevó 18 años-persona. [10]

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 et al. habían estado trabajando en tecnología de compiladores para la traducción secuencial de fórmulas en los años anteriores.

En 1960, un compilador Fortran extendido, ALTAC, estaba disponible en el Philco 2000, por lo que es probable que se compilara un programa Fortran para las arquitecturas informáticas de IBM y Philco a mediados de 1960. [11] 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. [7] [12]

Compiladores autoalojados

Al igual que cualquier otro software, existen beneficios al implementar un compilador en un lenguaje de alto nivel. En particular, un compilador puede ser autoalojado , es decir, escrito en el lenguaje de programación que compila. Construir un compilador autoalojado es un problema de arranque , es decir, el primer compilador de este tipo para un lenguaje debe ser un código de máquina escrito a mano, compilado por un compilador escrito en otro lenguaje o compilado ejecutando el código fuente del compilador sobre sí mismo en un intérprete .

Tesis doctoral de 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 presentada en 1951. [4] [5] No solo describió un compilador completo, sino que también definió por primera vez ese compilador en su propio lenguaje. 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 .

NELIACO

El compilador internacional ALGOL 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. [13]

NELIAC fue una creación de Harry Huskey , entonces presidente de la ACM y un conocido científico informático (y más tarde supervisor académico de Niklaus Wirth ), y contó con el apoyo de Maury Halstead, el jefe del centro computacional de NEL. La primera versión se implementó en el prototipo de computadora USQ-17 (llamada Countess) en el laboratorio. Fue el primer compilador autocompilador del mundo: el compilador primero se codificó 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, lo que hizo que el bootstrap quedara obsoleto.

Ceceo

Otro compilador autoalojado temprano fue escrito para Lisp por Tim Hart y Mike Levin en el MIT en 1962. [14] Escribieron un compilador de Lisp en Lisp, probándolo dentro de un intérprete de Lisp existente. Una vez que mejoraron el compilador hasta el punto en que podía compilar su propio código fuente, pasó a ser autoalojado. [15]

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

—  Memorándum de la IA 39 [15]

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

Adelante

Forth es un ejemplo de un compilador autoalojado. Las características de autocompilación y compilación cruzada de Forth son sinónimos de metacompilación y metacompiladores . [16] [17] Al igual que Lisp , Forth es un lenguaje de programación extensible . Son las características de 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 independientes del contexto

Un analizador sintáctico es un componente importante de un compilador. Analiza el código fuente de un lenguaje de programación informática para crear algún tipo 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 sintácticos rápidos y eficientes para ellos. Los analizadores sintácticos se pueden escribir a mano o generar 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 . [18]

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

Las gramáticas independientes del 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 hacerlo. Si un diseñador de lenguaje de programación está dispuesto a trabajar dentro de algunos subconjuntos limitados de gramáticas independientes del contexto, es posible crear analizadores sintácticos más eficientes.

Análisis LR

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

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

Korenjak (1969) fue el primero en demostrar que se podían producir analizadores sintácticos para lenguajes de programación utilizando estas técnicas. [20] 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. [21] [22] Este fue un avance importante, porque los traductores LR(k), tal como los definió Donald Knuth, eran demasiado grandes para su implementación en sistemas informáticos en los años 1960 y 1970.

En la práctica, LALR ofrece una buena solución; la potencia añadida de los analizadores LALR(1) sobre los analizadores 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) (véase más abajo) (LALR(1) no puede analizar todas las gramáticas LL(1)), la mayoría de las gramáticas LL(1) que se encuentran en la práctica pueden analizarse con LALR(1). Las gramáticas LR(1) son más potentes que LALR(1); sin embargo, una gramática LR(1) requiere un analizador LR canónico que sería extremadamente grande en tamaño y no se considera práctico. La sintaxis de muchos lenguajes de programación está definida por gramáticas que pueden analizarse 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 recursivo ascendente implementa un analizador LALR utilizando funciones recursivas mutuas en lugar de tablas. Por lo tanto, el analizador se codifica directamente en el lenguaje anfitrión de manera similar al descenso recursivo . La codificación directa generalmente produce un analizador que es más rápido que su equivalente controlado por tablas [23] por la misma razón que la compilación es más rápida que la interpretación. También es posible (en principio) editar manualmente un analizador recursivo ascendente, mientras que una implementación tabular es casi ilegible para el ser humano promedio.

El ascenso recursivo fue descrito por primera vez por Thomas Pennello en su artículo "Very fast LR parsing" en 1986. [23] La técnica fue posteriormente expuesta por GH Roberts [24] en 1988 así como en un artículo de Leermakers, Augusteijn, Kruseman Aretz [25] en 1992 en la revista Theoretical Computer Science .

Análisis LL

Un analizador LL analiza la entrada de izquierda a derecha y construye una derivación de la oración que se encuentre más a la izquierda (de ahí el nombre de LL, en lugar de 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 de gramáticas libres de contexto aún más restringida que las gramáticas LR. Sin embargo, son de gran interés para los escritores de compiladores, porque un analizador de este tipo es simple y eficiente de implementar.

Las gramáticas LL(k) pueden analizarse mediante un analizador descendente recursivo que normalmente se codifica a mano, aunque alternativamente se puede utilizar una notación como META II .

El diseño de ALGOL dio lugar a la investigación de la descendencia recursiva, ya que el lenguaje ALGOL en sí es recursivo. El concepto de análisis sintáctico por descendencia recursiva se analizó 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. [26] [27] Richard Waychoff y sus colegas también implementaron la descendencia recursiva en el compilador ALGOL de Burroughs en marzo de 1961, [28] los dos grupos utilizaron enfoques diferentes pero estaban en contacto al menos informal. [29]

La idea de las gramáticas LL(1) fue introducida por Lewis y Stearns (1968). [30] [31]

El descenso recursivo fue popularizado por Niklaus Wirth con PL/0 , un lenguaje de programación educativo utilizado para enseñar la construcción de compiladores en la década de 1970. [32]

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

Analizador sintáctico Earley

En 1970, Jay Earley inventó lo que se conocería como el analizador sintáctico Earley . Los analizadores sintácticos Earley son atractivos porque pueden analizar todos los lenguajes independientes del contexto con una eficiencia razonable. [33]

Descripción gramatical de los idiomas

John Backus propuso "fórmulas metalingüísticas" [34] [35] 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 postcanónico ideado por Emil Post .

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

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

Generadores de analizadores sintácticos

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 puede usarse en un compilador para ese lenguaje específico. El analizador detecta e identifica las palabras y los símbolos reservados del lenguaje específico a partir 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 que use una descripción de sintaxis formal con reglas de precedencia como entrada.

El primer compilador-compilador que utilizó ese nombre fue escrito por Tony Brooker en 1960 y se utilizó 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 lo describiría como algo intermedio 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.

A principios de la década de 1960, Robert McClure en Texas Instruments inventó un compilador-compilador llamado TMG , nombre tomado de "transmogrificación". [37] [38] [39] [40] En los años siguientes, TMG fue portado a varias computadoras mainframe UNIVAC e IBM.

El proyecto Multics , una empresa conjunta entre el 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. [41] 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.

No mucho 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 alto nivel del nuevo sistema: una implementación del TMG de McClure. [42] TMG también fue la herramienta de definición del compilador utilizada por Ken Thompson para escribir el compilador para el lenguaje B en su PDP-7 en 1970. B fue el antecesor inmediato de C.

Uno de los primeros generadores de analizadores sintácticos LALR se llamó "TWS" y fue 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 informáticos. Fue diseñado e implementado en 1967 por un equipo formado por William M. McKeeman, James J. Horning y David B. Wortman en la Universidad de Stanford y la Universidad de California en Santa Cruz . Se anunció por primera vez en la Conferencia Conjunta de Informática de Otoño de 1968 en San Francisco. [43] [44]

XPL incluía un sistema de escritura de traductores relativamente simple, denominado ANALYZER , basado en una técnica de análisis de precedencia de compilador ascendente denominada MSP (precedencia de estrategia mixta). XPL se implementó 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 distribuyeron).

Yacc

Yacc es un generador de analizadores sintácticos (vagamente, 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 . [45] 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 los años 1970 en Bell Labs . [46] Estaba familiarizado con TMG y su influencia se puede ver en Yacc y en 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. Derivados como GNU Bison todavía se utilizan.

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 tanto para Lex como para 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 de Zúrich (ETHZ) en 1985.

ANTR

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 los años 90 como sucesor de un generador anterior llamado PCCTS.

Metacompiladores

Los metacompiladores se diferencian de los generadores de analizadores sintácticos en que toman 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 integradas 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 y convertirse en compiladores de lenguaje extensibles y autoalojados.

Muchos metacompiladores se basan en el trabajo de Dewey Val Schorre . Su compilador META II , publicado por primera vez en 1964, fue el primer metacompilador documentado. Capaz de definir su propio lenguaje y otros, META II aceptó fórmulas sintácticas 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 de reconocimiento de tokens incorporadas: .ID, .STRING y .NUMBER. Las cadenas entre comillas en fórmulas sintácticas reconocen lexemas que no se conservan. [47]

TREE-META , un metacompilador de Schorre de segunda generación, apareció alrededor de 1968. Amplió las capacidades de META II, añadiendo reglas de desanálisis que separaban la producción de código del análisis gramatical. Las operaciones de transformación de árboles en la fórmula sintáctica producen árboles sintácticos abstractos sobre los que operan las reglas de desanálisis. La coincidencia de patrones de árboles de desanálisis proporcionó la capacidad de optimización de mirillas .

CWIC , descrito en una publicación de ACM de 1970, es un metacompilador Schorre de tercera generación que agregó reglas de análisis léxico y operadores de retroceso al análisis gramatical. LISP 2 se combinó con las reglas de desanálisis de TREEMETA en el lenguaje generador CWIC. Con el procesamiento de LISP 2, CWIC puede generar código completamente optimizado. CWIC también proporcionó generación de código binario en secciones de código con nombre. Se podían implementar compilaciones de una o varias pasadas utilizando 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 un conjunto de instrucciones de pseudomáquina, macros, que podrían definirse por separado o asignarse a las instrucciones de una máquina real. Las optimizaciones que se aplican a las instrucciones secuenciales podrían luego aplicarse a la pseudoinstrucción antes de su expansión al código de la 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. [7]

El compilador ALGOL 68C generaba una salida ZCODE , que luego podía compilarse en el código de máquina local mediante un traductor ZCODE o ejecutarse interpretado. ZCODE es un lenguaje intermedio basado en registros. Esta capacidad de interpretar o compilar ZCODE alentó la adaptació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 se propusieron generar código que fuera mejor que el ensamblador promedio codificado a mano, de modo que los clientes pudieran realmente usar su producto. En uno de los primeros compiladores reales, a menudo lo lograron. [48]

Los compiladores posteriores, como el compilador Fortran IV de IBM , dieron más prioridad a los buenos diagnósticos y a una 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 independientes: un verificador de código de ejecución rápida y otro más lento y optimizador.

Frances E. Allen , trabajando sola y en conjunto con John Cocke , introdujo muchos de los conceptos para la optimización. El artículo de Allen de 1966, Program Optimization, [49] introdujo el uso de estructuras de datos de gráficos para codificar el contenido del programa para la optimización. [50] Sus artículos de 1970, Control Flow Analysis [51] y A Basis for Program Optimization [52] establecieron los intervalos como el contexto para el análisis y la optimización eficiente y eficaz del flujo de datos. Su artículo de 1971 con Cocke, A Catalogue of Optimizing Transformations , [53] proporcionó la primera descripción y sistematización de las transformaciones de optimización. Sus artículos de 1973 y 1974 sobre el análisis del flujo de datos interprocedimental extendieron el análisis a programas completos. [54] [55] 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. [56]

Allen desarrolló e implementó sus métodos como parte de los compiladores para el 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 de la máquina y del lenguaje. Luego estableció y dirigió el proyecto PTRAN sobre la ejecución paralela automática de programas FORTRAN. [57] Su equipo 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 paralelizadores.

El libro 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 e incluyó muchas de las técnicas que hoy conocemos, como la eliminación de código redundante y la reducción de la fuerza . [58]

En 1972, Gary A. Kildall [59] introdujo la teoría del análisis del flujo de datos que hoy se utiliza para optimizar compiladores [60] (a veces conocida como el método de Kildall ).

Optimización de mirilla

La optimización por mirilla es una técnica de optimización sencilla pero eficaz. Fue inventada por William M. McKeeman y publicada en 1965 en CACM. [61] Se utilizó en el compilador XPL que McKeeman ayudó a desarrollar.

Optimizador COBOL de Capex

Capex Corporation desarrolló el "Optimizador COBOL" a mediados de los años 70 para COBOL . Este tipo de optimizador dependía, en este caso, del conocimiento de las "debilidades" del compilador estándar IBM COBOL, y en realidad reemplazaba (o parcheaba ) secciones del código objeto con código más eficiente. El código de reemplazo podía reemplazar una búsqueda de tabla lineal con una búsqueda binaria, por ejemplo, o, a veces, simplemente reemplazar una instrucción relativamente "lenta" con una instrucción conocida más rápida que, por lo demás, era funcionalmente equivalente dentro de su contexto. Esta técnica ahora se conoce como " reducción de fuerza ". Por ejemplo, en el hardware IBM System/360, la instrucción CLI era, dependiendo del modelo particular, entre dos y cinco veces más rápida que una instrucción CLC para comparaciones de un solo byte. [62] [63]

Los compiladores modernos generalmente proporcionan opciones de optimización para permitir a los programadores elegir si ejecutar o no un pase de optimización.

Diagnóstico

Cuando se le asigna a un compilador un programa sintácticamente incorrecto, resulta útil contar con un mensaje de error claro y claro. Desde la perspectiva del autor del compilador, esto suele ser difícil de lograr.

El compilador Fortran WATFIV fue desarrollado en la Universidad de Waterloo , Canadá, a finales de los años 60. Fue diseñado para proporcionar mejores mensajes de error que los compiladores Fortran de IBM de la época. Además, WATFIV era mucho más fácil de usar, 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 informática desarrollado en la Universidad de Cornell a principios de los años 70. Aunque PL/C era un subconjunto del lenguaje PL/I de IBM, se diseñó con el objetivo específico de ser utilizado para la enseñanza de la programación. Los dos investigadores y profesores académicos que diseñaron PL/C fueron Richard W. Conway y Thomas R. Wilcox. Presentaron el famoso artículo "Diseño e implementación de un compilador de diagnóstico para PL/I", publicado en Communications of ACM en marzo de 1973. [64]

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 inusual capacidad de no dejar de compilar ningún programa, mediante el uso de una corrección automática extensiva de muchos errores de sintaxis y convirtiendo los errores de sintaxis restantes en instrucciones 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 sintáctico 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 utiliza una representación intermedia, el mismo generador de código puede utilizarse para muchos lenguajes de alto nivel diferentes.

Existen muchas posibilidades para la representación intermedia. El código de tres direcciones , también conocido como cuádruple o cuadruple , es una forma común en la que hay un operador, dos operandos y un resultado. Los códigos de dos direcciones o triples tienen una pila en la que se escriben los resultados, a diferencia de 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. [65] En SSA, a una variable se le asigna 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.

Generación de código

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

Asignación de registros

El algoritmo de Sethi-Ullman o numeración de Sethi-Ullman es un método para minimizar la cantidad de registros necesarios para almacenar variables.

Compiladores notables

Véase también

Referencias

  1. ^ Hellige, Hans Dieter (2004). Geschichten der Informatik - Visionen, Paradigmen, Leitmotive (en alemán) (1 ed.). Berlín, Alemania: Springer. págs.45, 104, 105. ISBN 3-540-00217-0.
  2. ^ Rutishauser, Heinz (1951). "Über automatische Rechenplanfertigung bei programmgesteuerten Rechenanlagen". Zeitschrift für Angewandte Mathematik und Mechanik (en alemán). 31 : 255. doi : 10.1002/zamm.19510310820.
  3. ^ Fothe, Michael; Wilke, Thomas, eds. (2015) [2014-11-14]. Escrito en Jena, Alemania. Keller, Stack und automatisches Gedächtnis – eine Struktur mit Potenzial [ Bodega, pila y memoria automática: una estructura con potencial ] (PDF) (Tagungsband zum Kolloquium, 14 de noviembre de 2014 en Jena). Serie GI: Apuntes de conferencias sobre informática (LNI) - Temáticas (en alemán). vol. T-7. Bonn, Alemania: Gesellschaft für Informatik (GI) / Köllen Druck + Verlag GmbH. págs. 20-21. ISBN 978-3-88579-426-4. ISSN  1614-3213. Archivado (PDF) del original el 12 de abril de 2020 . Consultado el 12 de abril de 2020 .[1] (77 páginas)
  4. ^ ab Böhm, Corrado (1954). Calculatrices digitales: Du déchiffrage de formules logicomathématiques par la machine même dans la conception du program (PDF) (Doctor) (en francés). Zúrich: ETH Zúrich . Consultado el 27 de septiembre de 2022 .
  5. ^ ab Böhm, Corrado (1954). Computadoras digitales: sobre la codificación de fórmulas lógico-matemáticas utilizando la propia máquina durante la concepción del programa (PDF) (PhD). Zúrich: ETH Zurich . Consultado el 27 de septiembre de 2022 .
  6. ^ Maurice V. Wilkes . 1968. Computers Then and Now. Journal of the Association for Computing Machinery, 15(1):1–7, enero. p. 3 (un comentario entre corchetes añadido por el editor), "(No creo que el término compilador fuera de uso general en ese entonces [1953], aunque de hecho había sido introducido por Grace Hopper.)"
  7. ^ abc [2] Los primeros compiladores COBOL del mundo Archivado el 13 de octubre de 2011 en Wayback Machine.
  8. ^ Knuth, Donald E.; Pardo, Luis Trabb. "Desarrollo temprano de los lenguajes de programación". Enciclopedia de Ciencias de la Computación y Tecnología . 7 : 419–493.
  9. ^ Bentley, Peter J. (2012). Digitalizado: La ciencia de las computadoras y cómo moldea nuestro mundo. Oxford University Press. pág. 87. ISBN 978-0-19-969379-5Archivado desde el original el 29 de agosto de 2016.
  10. ^ Backus et al. "El sistema de codificación automática FORTRAN", Proc. AFIPS 1957 Western Joint Computer Conf., Spartan Books, Baltimore 188–198
  11. ^ [3] Rosen, Saul. ALTAC, FORTRAN y compatibilidad . Actas de la 16.ª reunión nacional de la ACM de 1961
  12. ^ Norman, Jeremy. "Grace Hopper y sus colegas presentan COBOL". HistoryOfInformation.com . Jeremy Norman . Consultado el 14 de diciembre de 2022 .
  13. ^ "Implementaciones y dialectos de Algol 58 — Software Preservation Group".
  14. ^ T. Hart y M. Levin "El nuevo compilador", AIM-39 CSAIL Digital Archive – Serie de laboratorios de inteligencia artificial
  15. ^ ab Hart, Tim; Levin, Mike. "AI Memo 39: El nuevo compilador" (PDF) . Archivado desde el original (PDF) el 13 de diciembre de 2020. Consultado el 23 de mayo de 2008 .
  16. ^ "Introducción a la metacompilación en FORTH". 24 de marzo de 2021.
  17. ^ Howe, Richard James. "Un metacompilador, una implementación de eForth y un tutorial sobre ambos". GitHub . Consultado el 27 de septiembre de 2022 .
  18. ^ Chomsky, Noam (septiembre de 1956). "Tres modelos para la descripción del lenguaje". IEEE Transactions on Information Theory . 2 (3): 113–124. doi :10.1109/TIT.1956.1056813. S2CID  19519474.
  19. ^ Knuth, Donald. "Sobre la traducción de lenguas de izquierda a derecha" (PDF) . Archivado desde el original (PDF) el 15 de marzo de 2012. Consultado el 29 de mayo de 2011 .
  20. ^ Korenjak, A. "Un método práctico para construir procesadores LR(k)", Communications of the ACM , vol. 12, n.º 11, 1969
  21. ^ DeRemer, F. Traductores prácticos para lenguajes LR(k). Tesis doctoral, MIT, 1969.
  22. ^ DeRemer, F. "Gramáticas LR(k) simples", Comunicaciones de la ACM , Vol. 14, Núm. 7, 1971.
  23. ^ de Thomas J Pennello (1986). "Análisis LR muy rápido". Avisos SIGPLAN de ACM . Vol. 21, núm. 7.
  24. ^ GH Roberts (1988). "Ascenso recursivo: un análogo LR al descenso recursivo". Avisos SIGPLAN de ACM . 23 (8): 23–29. doi : 10.1145/47907.47909 . S2CID  12740771.
  25. ^ René Leermakers; Lex Augusteijn; Frans EJ Kruseman Aretz (1992). "Un analizador LR funcional". Informática Teórica . 104 (2): 313–323. doi : 10.1016/0304-3975(92)90128-3 .
  26. ^ AA Grau, "Procesos recursivos y traducción ALGOL", Communications of the ACM , 4, No. 1, pp. 10-15. Enero de 1961
  27. ^ Edgar T. Irons, "Un compilador dirigido por sintaxis para ALGOL 60", Communications of the ACM , 4, No. 1, enero de 1961, págs. 51–55.
  28. ^ "Historias del B5000 y de las personas que estuvieron allí" (PDF) . Archivado desde el original (PDF) el 1 de marzo de 2021 . Consultado el 1 de agosto de 2016 .
  29. ^ Waychoff, Richard; Turner, Lloyd; Rosin, Robert F.; Pearson, Ralph W.; Oliphint, G. Clark; MacKenzie, F. Brad; MacDonald, Ray W.; MacDonald, Duncan N.; Lonergan, William D.; Kreuder, Norman L.; King, Paul D.; Hootman, Joseph T.; Hauck, Erwin A.; Hale, John E.; Galler, Bernard A.; Ford, James; Eppert, Ray R.; Dent, Benjamin A.; Dahm, David M.; Creech, Bobby A.; Collins, George A.; Berce, Henri; Barton, Robert S. (6 de septiembre de 1985). "Conferencia Burroughs B 5000". Universidad de Minnesota . hdl :11299/107105.
  30. ^ PM Lewis, RE Stearns, "Transducción dirigida por sintaxis", focs, págs. 21-35, 7.º Simposio anual sobre conmutación y teoría de autómatas (SWAT 1966), 1966
  31. ^ Lewis, P. y Stearns, R. "Transducción dirigida por sintaxis", Journal of the ACM , vol. 15, núm. 3, 1968.
  32. ^ "El compilador/intérprete PL/0". Archivado desde el original el 8 de diciembre de 2008 . Consultado el 7 de julio de 2011 .
  33. ^ J. Earley, "Un algoritmo de análisis libre de contexto eficiente", Communications of the Association for Computing Machinery , 13 :2:94-102, 1970.
  34. ^ Backus, JW (1959). "La sintaxis y la semántica del lenguaje algebraico internacional propuesto en la Conferencia ACM-GAMM de Zurich". Actas de la Conferencia Internacional sobre Procesamiento de la Información : 125–132.
  35. ^ Farrell, James A. (agosto de 1995). "Extended Backus Naur Form". Conceptos básicos del compilador . Consultado el 11 de mayo de 2011 .
  36. ^ Donald E. Knuth, "Forma normal de Backus frente a forma de Backus Naur", Comunicaciones de la ACM , 7(12):735–736, 1964.
  37. ^ "TMG Meta Compiler". reocities.com . Archivado desde el original el 4 de marzo de 2016. Consultado el 30 de junio de 2011 .
  38. ^ "La enciclopedia de lenguajes informáticos". Archivado desde el original el 21 de septiembre de 2007. Consultado el 30 de junio de 2011 .
  39. ^ McClure, RM (1965). "Lenguajes de programación para procesamiento no numérico---1: ​​TMG---un compilador dirigido por sintaxis". Actas de la 20.ª conferencia nacional de 1965. págs. 262-274. doi :10.1145/800197.806050. ISBN 978-1-4503-7495-8.S2CID44606611  .​ {{cite book}}: |work=ignorado ( ayuda )
  40. ^ RM McClure, TMG—A Syntax Directed Compiler Proc. 20.ª Conferencia Nacional ACM (1965), págs. 262–274.
  41. ^ "Multics PL/I". multicians.org .
  42. ^ "Chistory". Archivado desde el original el 10 de enero de 2015. Consultado el 3 de agosto de 2011 .Dennis M. Ritchie. El desarrollo del lenguaje C
  43. ^ McKeeman, William Marshall; Horning, James J.; y Wortman, David B., Un generador de compiladores (1971), ISBN 978-0-13-155077-3 . 
  44. ^ Departamento de Ciencias de la Computación, Universidad de Toronto , "El lenguaje de programación XPL"
  45. ^ Johnson, SC, "Yacc – Otro compilador más", Computing Science Technical Report 32, AT&T Bell Labs, 1975
  46. ^ Hamilton, Naomi (5 de octubre de 2023). "Lenguajes de programación de la A a la Z: YACC". TechWorld .
  47. ^ Schorre, DV (1964). "META II, un lenguaje de escritura de compiladores orientado a la sintaxis". Actas de la 19.ª conferencia nacional de la ACM de 1964. págs. 41.301–41.3011. doi :10.1145/800257.808896. ISBN 978-1-4503-7918-2. Número de identificación del sujeto  43144779. {{cite book}}: |work=ignorado ( ayuda )
  48. ^ "Comp.compilers: Re: Historia y evolución de los compiladores". iecc.com .
  49. ^ Frances E. Allen , "Optimización de programas" En Mark I. Halpern y Christopher J. Shaw, editores, Annual Review in Automatic Programming , volumen 5, páginas 239–307. Pergamon Press, Nueva York, 1969.
  50. ^ Allen, Frances E.; Cocke, John (11 de julio de 1972). Graph-Theoretic Constructs for Program Control Flow Analysis (RC 3923) (PDF) . Yorktown Heights, NY: IBM Thomas J. Watson Research Center . Consultado el 6 de mayo de 2021 .
  51. ^ Frances E. Allen. "Análisis del flujo de control". ACM SIGPLAN Notices , 5(7):1–19, julio de 1970.
  52. ^ Frances E. Allen. "Una base para la optimización de programas". En Proc. IFIP Congress 71 , páginas 385–390. Holanda Septentrional, 1972.
  53. ^ Frances E. Allen y John Cocke. "Un catálogo de transformaciones optimizadoras". En R. Rustin, editor, Design and Optimization of Compilers , páginas 1–30. Prentice-Hall, 1971.
  54. ^ Frances E. Allen. "Análisis del flujo de datos interprocedimental". En Proc. IFIP Congress 74, páginas 398-402. Holanda Septentrional, 1974.
  55. ^ Frances E. Allen. "Un método para determinar las relaciones entre los datos de un programa". En Andrei Ershov y Valery A. Nepomniaschy, editores, Proc. International Symposium on Theoretical Programming , Novosibirsk, URSS, agosto de 1972, volumen 5 de Lecture Notes in Computer Science, páginas 299-308. Springer-Verlag, 1974.
  56. ^ Frances E. Allen y John Cocke. "Un procedimiento de análisis del flujo de datos de un programa", Communications of the ACM , 19(3):137–147, marzo de 1976.
  57. ^ Sarkar, Vivek (1991). "PTRAN—el sistema de traducción paralela de IBM". Lenguajes funcionales paralelos y compiladores. Nueva York, NY: Association for Computing Machinery. págs. 309–391. doi :10.1145/107214.129260. ISBN 0-201-52243-8. Recuperado el 6 de mayo de 2021 .
  58. ^ John Cocke y Jacob T. Schwartz, Lenguajes de programación y sus compiladores . Courant Institute of Mathematical Sciences, Universidad de Nueva York, abril de 1970.
  59. ^ Kildall, Gary Arlen (mayo de 1972). Optimización de expresiones globales durante la compilación (tesis doctoral). Seattle, Washington, EE. UU.: Universidad de Washington , Computer Science Group. Tesis n.º 20506, Informe técnico n.º 72-06-02.
  60. ^ Kildall, Gary Arlen (1 de octubre de 1973). "Un enfoque unificado para la optimización global de programas" (PDF) . Actas del 1.º Simposio anual ACM SIGACT-SIGPLAN sobre principios de lenguajes de programación (POPL) . Boston, Massachusetts, EE. UU.: 194–206. doi :10.1145/512927.512945. hdl :10945/42162. S2CID  10219496 . Consultado el 2 de mayo de 2023 .
  61. ^ McKeeman, WM "Optimización de la mirilla". Communications of the ACM 8, 7 (julio de 1965), 443–444
  62. ^ Información sobre temporización de instrucciones del sistema/360 (PDF) . Biblioteca de referencia de sistemas IBM. Mayo de 1964 . Consultado el 6 de mayo de 2021 .
  63. ^ Evans, Michael (1982). "Ingeniería de software para el entorno Cobol". Comunicaciones de la ACM . 25 (12): 874–882. ​​doi : 10.1145/358728.358732 . S2CID  17268690.
  64. ^ CACM marzo de 1973 págs. 169-179.
  65. ^ Cytron, Ron; Ferrante, Jeanne; Rosen, Barry K.; Wegman, Mark N.; Zadeck, F. Kenneth (1991). "Computación eficiente de la forma de asignación única estática y el gráfico de dependencia de control" (PDF) . ACM Transactions on Programming Languages ​​and Systems . 13 (4): 451–490. CiteSeerX 10.1.1.100.6361 . doi :10.1145/115372.115320. S2CID  13243943. 

Lectura adicional

  • Backus, John , et al., "El sistema de codificación automática FORTRAN", Actas de la Conferencia Conjunta de Computación Occidental, Los Ángeles, California, febrero de 1957. Describe el diseño y la implementación del primer compilador FORTRAN realizado por el equipo de IBM.
  • Knuth, DE, RUNCIBLE-traducción algebraica en una computadora limitada , Comunicaciones de la 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 de ALGOL 60: un traductor de ALGOL 60 para X1 y elaboración de un traductor para ALGOL 60 (PDF) (informe técnico). Ámsterdam: Mathematisch Centrum. 35.
  • Conway, Melvin E. , Diseño de un compilador de diagrama de transición separable , Communications of the 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ág. 31. (1964).
  • Randell, Brian ; Russell, Lawford John, Implementación de ALGOL 60: la traducción y el uso de programas de ALGOL 60 en una computadora , Academic Press, 1964
  • Knuth, DE (julio de 1965). "Sobre la traducción de lenguas de izquierda a derecha". Información y Control . 8 (6): 607–639. doi :10.1016/S0019-9958(65)90426-2.
  • Cocke, John ; Schwartz, Jacob T. , Lenguajes de programación y sus compiladores: notas preliminares , informe técnico del Courant Institute of Mathematical Sciences , Universidad de Nueva York , 1969.
  • Bauer, Friedrich L .; Eickel, Jürgen (Eds.), Construcción de compiladores, un curso avanzado , 2ª ed. Apuntes de conferencias sobre informática 21, Springer 1976, ISBN 3-540-07542-9 
  • Gries, David , Construcción de compiladores para computadoras digitales , Nueva York: Wiley, 1971. ISBN 0-471-32776-X 
  • Construcción de compiladores antes de 1980: lista de literatura comentada por Dick Grune
  • "Una historia de la escritura de compiladores". Computadoras y automatización . XI (12): 8–10, 12, 14, 24–25. Diciembre de 1962.
Obtenido de "https://es.wikipedia.org/w/index.php?title=Historia_de_la_construcción_de_compiladores&oldid=1240527285"