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 poder ejecutarse, por lo que todos los programadores que utilizan dicho lenguaje 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-Compilador de Calidad de Producción , a finales de la década de 1970, introdujo los principios de organización del compilador que todavía se utilizan ampliamente hoy en día (por ejemplo, un front-end que maneja la sintaxis y la semántica y un back-end que genera código de máquina).
El software para las primeras computadoras se escribía principalmente en lenguaje ensamblador y, antes, directamente en código de máquina . Generalmente 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 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. Problemas técnicos para implementaciones prácticas de compiladores.
Entre 1942 y 1945, Konrad Zuse desarrolló Plankalkül ("cálculo de planes"), el primer lenguaje de alto nivel para una computadora, para el cual imaginó un Planfertigungsgerät ("dispositivo de ensamblaje de planes"), que traduciría automáticamente la formulación matemática de un programa. en película perforada legible por máquina . [1] Sin embargo, el primer compilador real para el lenguaje se implementó sólo 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 posteriormente refinadas 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 compilador. El primer Autocode y compilador en el sentido moderno fue desarrollado por Alick Glennie en 1952 en la Universidad de Manchester para la computadora Mark 1 . [8] [9] El equipo de FORTRAN dirigido por John W. Backus en IBM introdujo el primer compilador disponible comercialmente, en 1957, cuya creación requirió 18 años-persona. [10]
El primer compilador ALGOL 58 fue completado a finales de 1958 por Friedrich L. Bauer , Hermann Bottenbruch, Heinz Rutishauser y Klaus Samelson para la computadora Z22 . Bauer et al. Había estado trabajando en tecnología de compilación para Sequentielle Formelübersetzung (es decir, traducción secuencial de fórmulas ) en los años anteriores.
En 1960, un compilador Fortran extendido, ALTAC, estaba disponible en Philco 2000, por lo que es probable que se compilara un programa Fortran para arquitecturas de computadora IBM y Philco a mediados de 1960. [11] El primer lenguaje de alto nivel multiplataforma demostrado conocido fue COBOL . En una demostración realizada en diciembre de 1960, se compiló y ejecutó un programa COBOL tanto en UNIVAC II como en RCA 501. [7] [12]
Como cualquier otro software, implementar un compilador en un lenguaje de alto nivel tiene ventajas. En particular, un compilador puede ser autohospedado , es decir, escrito en el lenguaje de programación que compila. Construir un compilador autohospedado 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 la fuente del compilador sobre sí mismo en un intérprete .
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 sólo describió un compilador completo, sino que también definió por primera vez que 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 declaración de asignación .
El Compilador ALGOL Internacional del Laboratorio de Electrónica de la Marina 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 apoyado por Maury Halstead, director 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, haciendo que el arranque obsoleto.
Otro de los primeros compiladores autohospedados fue escrito para Lisp por Tim Hart y Mike Levin en el MIT en 1962. [14] Escribieron un compilador Lisp en Lisp, probándolo dentro de un intérprete Lisp existente. Una vez que mejoraron el compilador hasta el punto en que podía compilar su propio código fuente, se autohospedó. [15]
Esta técnica sólo es posible cuando ya existe un intérprete para el mismo lenguaje que se va a compilar. Toma prestado directamente de la noción de ejecutar un programa sobre sí mismo como entrada, que también se utiliza en varias pruebas en informática teórica , como la prueba de que el problema de detención es indecidible .
Forth es un ejemplo de un compilador autohospedado. Las funciones 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 extensibles del lenguaje de programación de Forth y Lisp las que les permiten generar nuevas versiones de sí mismos o adaptarse a nuevos entornos.
Un analizador es un componente importante de un compilador. Analiza el código fuente de un lenguaje de programación informática 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 para ellos se pueden escribir analizadores rápidos y eficientes. Los analizadores pueden escribirse a mano o generarse mediante un generador de analizadores . 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 mediante el proyecto ALGOL (1957-1960), que, como consecuencia, también incluía 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 determinada, 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 más eficientes.
El analizador 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 LR es un analizador 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 LR( k ) , donde k se refiere al número de símbolos de entrada de anticipación no consumidos que se utilizan para tomar decisiones de análisis.
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 idioma. En otras palabras, sólo es necesario tener un símbolo anticipado para analizar cualquier gramática determinista libre de contexto (DCFG). [19]
Korenjak (1969) fue el primero en demostrar que se podían producir analizadores 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 LR(k ) los traductores, 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; el poder añadido 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)(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) vuelven a ser más poderosas que LALR(1); sin embargo, una gramática LR(1) requiere un analizador LR canónico que sería extremadamente grande y no se considera práctico. La sintaxis de muchos lenguajes de programación está definida por gramáticas que se pueden analizar con un analizador LALR(1) y, por esta razón, los compiladores suelen utilizar los analizadores LALR para realizar análisis de sintaxis del código fuente.
Un analizador de ascenso recursivo implementa un analizador LALR utilizando funciones mutuamente recursivas en lugar de tablas. Por lo tanto, el analizador está codificado directamente en el idioma 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 basado en 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 de ascenso 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 "Very fast LR parsing" en 1986. [23] La técnica fue expuesta más tarde 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 .
Un analizador LL analiza la entrada de izquierda a derecha y construye una derivación extrema izquierda de la oración (de ahí LL, a diferencia 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 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) pueden analizarse mediante un analizador de descenso recursivo que normalmente se codifica a mano, aunque alternativamente se podría utilizar una notación como META II .
El diseño de ALGOL provocó una investigación sobre el descenso recursivo, ya que el lenguaje ALGOL en sí es recursivo. El concepto de análisis de descenso recursivo 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 el descenso recursivo en el compilador ALGOL de Burroughs en marzo de 1961, [28] los dos grupos utilizaron enfoques diferentes pero estaban al menos en contacto informal. [29]
La idea de 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 a la hora de informar 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.
En 1970, Jay Earley inventó lo que se conoció como el analizador Earley . Los analizadores Earley son atractivos porque pueden analizar todos los lenguajes libres de contexto de manera razonablemente eficiente. [33]
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 canónico Post ideado por Emil Post .
Un mayor desarrollo de ALGOL condujo a ALGOL 60 ; en su informe (1963), Peter Naur nombró la notación de Backus como forma normal de Backus (BNF) y la simplificó para minimizar el conjunto de caracteres utilizado. Sin embargo, Donald Knuth argumentó que BNF debería leerse como la forma Backus-Naur , [36] 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 de 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 para generadores de analizadores y en otros campos, como la definición de protocolos de comunicación.
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 símbolos reservados del idioma 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 utilizando una descripción de sintaxis de reglas de precedencia formal 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 de 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. Es casi seguro que el nombre "Compilador-Compilador" haya entrado en uso común debido a que se recuerda Yacc en lugar del trabajo de Brooker. [ cita necesaria ]
A principios de la década de 1960, Robert McClure de Texas Instruments inventó un compilador llamado TMG , nombre tomado de "transfiguración". [37] [38] [39] [40] En los años siguientes, TMG se transfirió a varias computadoras centrales 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 que funcionara. [41] El equipo Multics desarrolló su propio subconjunto de dialecto 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 nivel superior 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 antepasado inmediato de C.
Uno de los primeros generadores de analizadores LALR se llamó "TWS", creado por Frank DeRemer y Tom Pennello.
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 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 Conjunta de Computación de Otoño de 1968 en San Francisco. [43] [44]
XPL presentaba un sistema de escritura de traductor relativamente simple denominado ANALYZER , basado en una técnica de análisis de precedencia del compilador ascendente llamada MSP (precedencia de estrategia mixta). XPL se inició 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 es un generador de analizadores (en términos generales, compilador-compilador ), que no debe confundirse con lex , que es un analizador léxico utilizado frecuentemente como primera etapa por Yacc. Yacc fue desarrollado por Stephen C. Johnson de 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 la década de 1970 en Bell Labs . [46] 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. Todavía se utilizan derivados como GNU Bison .
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 es un generador de analizadores que genera analizadores 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 es un generador de analizadores que genera analizadores 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.
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 fórmulas de análisis gramatical combinadas 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 apilado.
Muchos pueden programarse en su propio metalenguaje, lo que les permite compilarse ellos mismos, lo que los convierte en compiladores de lenguajes extensibles y 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ó una fórmula de sintaxis que tiene una salida incorporada (producción de código) . También se tradujo en una de las primeras instancias de una máquina virtual . El análisis léxico se realizó mediante funciones de reconocimiento de tokens integradas: .ID, .STRING y .NUMBER. Las cadenas entre comillas en la fórmula de sintaxis reconocen lexemas que no se conservan. [47]
TREE-META , un metacompilador Schorre de segunda generación, apareció alrededor de 1968. Amplió las capacidades de META II, agregando reglas de análisis que separan la producción de código del análisis gramatical. Las operaciones de transformación de árboles en la fórmula de sintaxis producen árboles de sintaxis abstracta en los que operan las reglas de análisis. La coincidencia de patrones de árbol sin analizar proporcionó la capacidad de optimización de mirilla .
CWIC , descrito en una publicación de ACM de 1970, es un metacompilador Schorre de tercera generación que agregó reglas de lexing y operadores de retroceso al análisis gramatical. LISP 2 estaba casado con las reglas de análisis de TREEMETA en el lenguaje generador de CWIC. Con el procesamiento 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. Se podrían implementar compilaciones de paso único y múltiple utilizando CWIC.
CWIC compiló 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 instrucciones secuenciales podrían luego aplicarse a la pseudoinstrucción antes de su expansión al código de máquina de destino.
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 generó una salida ZCODE , que luego podría ser compilada en el código de máquina local mediante un traductor ZCODE o ejecutada interpretada. ZCODE es un lenguaje intermedio basado en registros. Esta capacidad de interpretar o compilar ZCODE fomentó la migración de ALGOL 68C a numerosas plataformas informáticas diferentes.
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 pretendían generar código que fuera mejor que el ensamblador promedio codificado a mano, para que los clientes realmente usaran su producto. En uno de los primeros compiladores reales, a menudo lo consiguieron. [48]
Los compiladores posteriores, como el compilador Fortran IV de IBM , dieron más prioridad al buen diagnóstico y a 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 de optimización más lento.
Frances E. Allen , trabajando sola y junto con John Cocke , introdujo muchos de los conceptos de optimización. El artículo de Allen de 1966, Program Optimization, [49] introdujo el uso de estructuras de datos gráficos para codificar el contenido del programa para su optimización. [50] Sus artículos de 1970, Control Flow Analysis [51] y A Basis for Program Optimization [52] establecieron intervalos como contexto para un análisis y optimización eficiente y eficaz del flujo de datos. Su artículo de 1971 con Cocke, A Catalog of Optimizing Transformations , [53] 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. [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 los compiladores actuales. [56]
Allen desarrolló e implementó sus métodos como parte de los compiladores del IBM 7030 Stretch - Harvest y el sistema de computación avanzada experimental . Este trabajo estableció la viabilidad y la estructura de optimizadores modernos independientes de la máquina y el 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 de gráfico de dependencia del programa, el método de estructuración principal utilizado por la mayoría de los compiladores paralelizadores.
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 fuerza . [58]
En 1972, Gary A. Kildall [59] introdujo la teoría del análisis del flujo de datos que se utiliza hoy en día para optimizar los compiladores [60] (a veces conocida como método de Kildall ).
La optimización de mirilla es una técnica de optimización simple pero efectiva. Fue inventado por William M. McKeeman y publicado en 1965 en CACM. [61] Se utilizó en el compilador XPL que McKeeman ayudó a desarrollar.
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" del compilador COBOL estándar de IBM y, de hecho, reemplazaba (o parcheaba ) 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, a veces, simplemente reemplazar una instrucción relativamente "lenta" por una más rápida conocida 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, 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. [62] [63]
Los compiladores modernos suelen proporcionar opciones de optimización para permitir a los programadores elegir si ejecutar o no un paso de optimización.
Cuando a un compilador se le proporciona un programa sintácticamente incorrecto, un mensaje de error bueno y claro resulta útil. Desde la perspectiva del compilador, esto suele ser difícil de lograr.
El compilador WATFIV Fortran fue desarrollado en la Universidad de Waterloo , Canadá, a finales de los años 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 utilizable porque combinaba compilación, vinculación y ejecución en un solo paso, mientras que los compiladores de IBM tenían tres componentes separados para ejecutar.
PL/C fue un lenguaje de programación desarrollado en la Universidad de Cornell a principios de los años 1970. Si bien PL/C era un subconjunto del lenguaje PL/I de IBM, fue diseñado con el objetivo específico de usarse 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 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 nunca dejar de compilar ningún programa, mediante el uso de una extensa corrección automática de muchos errores de sintaxis y convirtiendo los errores de sintaxis restantes en declaraciones de salida.
La compilación justo a tiempo (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 de mejora del rendimiento.
La mayoría de los compiladores modernos tienen un lexer 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 utiliza una representación intermedia, el mismo generador de código se puede utilizar 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 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 da un valor sólo 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.
Un generador de código genera instrucciones en lenguaje de máquina para el procesador de destino.
El algoritmo de Sethi-Ullman o la numeración de Sethi-Ullman es un método para minimizar la cantidad de registros necesarios para contener variables.
{{cite book}}: |work=ignorado ( ayuda ){{cite book}}: |work=ignorado ( ayuda )