En informática, un compilador es un programa informático que transforma código fuente escrito en un lenguaje de programación o lenguaje informático (el lenguaje fuente), en otro lenguaje informático (el lenguaje objetivo, estando a menudo en formato binario conocido como código objeto). La razón más común para querer transformar código fuente es crear un programa ejecutable.

Cualquier programa escrito en un lenguaje de programación de alto nivel debe ser traducido a código objeto antes de que pueda ser ejecutado, para que todos los programadores que usen tal lenguaje usen un compilador o un intérprete. Por esto, los compiladores son muy importantes para los programadores. Cualquier mejora hecha a un compilador lleva a un gran número de programas mejorados.

Los compiladores son programas grandes y complejos, pero el análisis sistemático y la investigación de los científicos informáticos ha llevado a un entendimiento más claro de la construcción de los compiladores y una gran cantidad de teoría ha sido desarrollada sobre ellos. La investigación en la construcción de compiladores ha conducido a herramientas que hacen mucho más fácil crear compiladores, de modo que los estudiantes de informática de hoy en día pueden crear sus propios lenguajes pequeños y desarrollar un compilador simple en pocas semanas.

El software para los primeros computadores estaba primariamente escrito en lenguaje ensamblador. Normalmente para un programador es más productivo usar un lenguaje de alto nivel, y los programas escritos en lenguajes de alto nivel pueden ser reutilizados en distintos tipos de computadores. Aun teniendo en cuenta esto, pasó un tiempo hasta que los compiladores se establecieran, porque generaban código que no tenía tan buen rendimiento como los ensambladores escritos a mano, eran enormes proyectos de desarrollo por sí mismos, y la limitadísima capacidad de memoria de los primeros computadores creó muchos problemas técnicos para las implementaciones prácticas de los compiladores.

El primer compilador fue escrito por Grace Hopper, en 1952, para el lenguaje Sistema A-0. El término compilador fue acuñado por Hopper.^[1]​ El equipo FORTRAN dirigido por John W. Backus de IBM está generalmente acreditado por haber presentado el primer compilador completo, en 1957. El primer compilador FORTRAN necesitó de 18 años-persona para su creación.^[2]​

En 1960, un compilador FORTRAN extendido, ALTAC, estaba también disponible en el Philco 2000, por lo que es probable que un programa FORTRAN fuera compilado para ambas arquitecturas de computadores a mediados de los años 60.^[3]​ El primer lenguaje de alto nivel multiplataforma demostrado fue COBOL. En una demostración en diciembre de 1960, un programa COBOL fue compilado y ejecutado en el UNIVAC II y el RCA 501.^[1]​

El compilador COBOL para el UNIVAC II fue probablemente el primero en ser escrito en un lenguaje de alto nivel, llamado FLOW-MATIC, por un equipo dirigido por Grace Hopper.

Como cualquier otro software, hay beneficios obtenidos de la implementación de un compilador en un lenguaje de alto nivel. En particular, un compilador puede ser auto-alojado, es decir, escrito en el lenguaje de programación que lo compila. Construir un compilador auto-alojado es un problema de bootstrapping —el primer compilador para un lenguaje debe ser compilado o en un compilador escrito en un lenguaje distinto, o compilado ejecutando el compilador en un intérprete.

El Navy Electronics Laboratory International ALGOL Compiler o NELIAC fue un dialecto e implementación del compilador del lenguaje de programación ALGOL 58 desarrollado por el Naval Electronics Laboratory en 1958.

ELIAC fue el invento de Harry Huskey — por aquel entonces presidente de la ACM y un reconocido científico informático, y apoyado por Maury Halstead, el jefe del centro computacional en el NEL. La primera versión fue implementada en el ordenador prototipo USQ-17 (llamado la Condesa) en el laboratorio. Fue el primer compilador auto-compilado del mundo. Esto significa que el compilador fue primero codificado en forma simplificada en un lenguaje ensamblador (el bootstrap), y luego reescrito en su propio lenguaje, compilado por el compilador bootstrap, y recompilado por sí mismo, haciendo obsoleto el bootstrap.

El primer compilador auto-alojado (excluyendo ensambladores) fue escrito para Lisp por Tim Hart y Mike Levin en el MIT en 1962.^[4]​ Ellos escribieron un compilador de Lisp en Lisp, probándolo en un intérprete de Lisp existente. Una vez que ellos hubieron mejorado el compilador hasta el punto de que se pudiera compilar en su propio código fuente, fue auto-alojado.^[5]​

El compilador tal como existe en la cinta de compilador estándar es un programa en lenguaje de máquina que fue obtenido al tener la definición de la Expresión S del trabajo de compilador en sí mismo a través del intérprete. (AI Memo 39)^[5]​

Esta técnica solo es posible cuando un intérprete ya existe para el propio lenguaje que va a ser compilado. Lo toma prestado directamente de la noción de ejecutar un programa en sí mismo como salida, lo cual también es usado en varias pruebas de la ciencia computacional teórica, por ejemplo en la prueba de que el problema de la parada es indeterminable.

Un analizador sintáctico es un componente importante de un compilador. Analiza el código fuente de un lenguaje de programación para crear algún tipo de representación interna. Los lenguajes de programación tienden a ser especificados en términos de una gramática libre de contexto a causa de los analizadores sintácticos rápidos y eficientes que pueden ser escritos para ellos. Los analizadores sintácticos pueden ser escritos a mano o generado por un compilador de computador. Una gramática libre de contexto ofrece un mecanismo sencillo y preciso para describir la estructura de bloque de un programa - es decir, cómo el lenguaje de programación se construye a partir de bloques más pequeños. El formalismo de las gramáticas libres de contexto fue desarrollado por Noam Chomsky a mediados de los años 50.^[6]​

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

Las gramáticas libres de contexto son lo suficientemente simples como para permitir la construcción de algoritmos de análisis sintáctico eficientes los cuales, para una cadena dada, determinan cuándo y cómo pueden ser generados a partir de la gramática. Si un diseñador de lenguajes de programación está dispuesto a trabajar dentro de algunos subconjuntos limitados de las gramáticas libres de contexto, es posible crear analizadores sintácticos más eficientes.

El analizador sintáctico LR (left to right: izquierda a derecha) fue inventado por Donald Knuth en 1965 en un artículo, "On the Translation of Languages from Left to Right". 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 por la derecha. El término analizador sintáctico LR(k) es también usado, donde k se refiere al número de símbolos de entrada predichos ("look-ahead") sin consumir que son usados en las decisiones que toma el analizador.

Knuth demostró que las gramáticas LR(k) pueden ser analizadas en un tiempo de ejecución esencialmente proporcional a la longitud del programa, y cada gramática LR(k) con k > 1 puede ser mecánicamente transformada en una gramática LR(1) para el mismo lenguaje. En otras palabras, solo es necesario tener un símbolo de predicción para analizar cualquier gramática libre de contexto determinista (DCFG: deterministic context-free grammar).^[7]​

Korenjak (1969) fue el primero en demostrar que los analizadores sintácticos para los lenguajes de programación podían ser producidos usando estas técnicas.^[8]​ Frank DeRemer ideó las técnicas más prácticas SLR y LALR, publicadas en su tesis doctoral del MIT en 1969.^[9]​^[10]​ Esto supuso un importante avance, porque los traductores LR(k), como los definió Donald Knuth, eran demasiado grandes para su implementación en los sistemas informáticos de los años 60 y 70.

En la práctica, LALR ofrece una buena solución, porque las gramáticas LALR(1) son más potentes que las gramáticas SLR(1) y LL(1). Las gramáticas LR(1) son más potentes que las LALR(1), sin embargo, los analizadores sintácticos LR(1) pueden ser extremadamente grandes en tamaño y no se consideran prácticos. Los analizadores sintácticos LR(1) mínimos son pequeños en tamaño y comparables a los analizadores sintácticos LALR(1). La sintaxis de muchos lenguajes de programación son definidos por una gramática LALR(1), y por esta razón los analizadores sintácticos LALR son usados a menudo por compiladores para llevar a cabo el análisis sintáctico del código fuente.

Un analizador sintáctico ascendente recursivo implementa un analizador LALR usando funciones mutuamente recursivas en vez de usar tablas. Por esto, el analizador sintáctico es directamente codificado en el lenguaje anfitrión de forma parecida al recursivo descendente. La codificación directa normalmente produce un analizador más rápido que su equivalente basado en tablas^[11]​ por la razón de que la compilación es más rápida que la interpretación. También es posible (en principio) editar a mano un analizador sintáctico recursivo ascendente, donde una implementación en forma de tabla es casi ilegible para el ser humano medio.

La recursión ascendente fue descrita por primera vez por Thomas Pennello en su artículo "Very fast LR parsing" en 1986.^[11]​ La técnica fue expuesta después por G.H. Roberts^[12]​ en 1988 así como en un artículo de Leermakers, Augusteijn y Kruseman Aretz^[13]​ en 1992 en el diario Theoretical Computer Science.

Un analizador sintáctico LL analiza la entrada de izquierda a derecha, y construye una derivación por la izquierda de la sentencia o enunciado, al contrario que LR. La clase de gramáticas que son analizables por este método son conocidas como gramáticas LL. Las gramáticas LL son una clase de gramáticas libres de contexto aún más restrictiva que las gramáticas LR. Sin embargo, son de gran interés para los escritores de compiladores, puesto que este analizador es simple y eficiente de implementar.

Las gramáticas LL(k) pueden ser analizadas por un analizador sintáctico descendente recursivo, que es normalmente codificado a mano.

El diseño de ALGOL provocó la investigación del recursivo descendente, dado que el lenguaje ALGOL es en sí mismo recursivo. El concepto de análisis sintáctico descendente recursivo fue objeto de debate en la edición de enero de 1961 del CACM en artículos separados de A.A. Grau y Edgar T. "Ned" Irons.^[14]​^[15]​ Richard Waychoff concibió y usó el descendente recursivo en el compilador ALGOL de Burroughs de marzo de 1961.^[16]​

La idea de las gramáticas LL(1) fue presentada por Lewis y Stearns (1968).^[17]​^[18]​

El recursivo descendente fue popularizado por Niklaus Wirth con PL/0, un lenguaje de programación educacional usado para enseñar la construcción de compiladores en los años 70.^[19]​

El análisis sintáctico LR puede manejar un rango mayor de lenguajes que el análisis sintáctico LL, y proporciona mejores informes de errores, es decir, detecta errores sintácticos cuando la entrada no está conforme a la gramática tan pronto como sea posible.

En 1970, Jay Earley inventó lo que después se llamó el Algoritmo de Earley. Este algoritmo es atractivo porque puede analizar cualquier lenguaje libre de contexto de forma bastante eficiente.^[20]​

John Backus propuso "fórmulas meta-lingüísticas"^[21]​ ^[22]​ para describir la sintaxis del nuevo lenguaje de programación IAL, conocido hoy en día como ALGOL 58 (1959). El trabajo de Backus estaba basado en la Máquina de Post ideada por Emil Post.

El posterior desarrollo de ALGOL llevó al ALGOL 60; en su informe (1963), Peter Naur llamó Notación de Backus-Naur (Backus Normal Form: BNF) a la notación de Backus,^[23]​ y lo simplificó para minimizar el conjunto de caracteres usados.

Niklaus Wirth definió la Notación de Backus-Naur Extendida (Extended Backus-Naur Form: EBNF), una versión refinada de la BNF, a principios de los años 70 para PL/0. La Notación de Backus-Naur Aumentada (Augmented Backus-Naur Form: ABNF) es otra variante. Tanto EBNF como ABNF son muy usadas para especificar la gramática de los lenguajes de programación, como en las entradas de los generadores de analizadores sintácticos, y en otros campos como la definición de protocolos de comunicación.

Un compilador de computador (compiler compiler) o generador de analizador sintáctico es un programa que toma una descripción de la gramática formal de un lenguaje de programación y produce un analizador sintáctico para ese lenguaje.

El primer compilador de computador en usar ese nombre fue escrito por Tony Brooker en 1960 y fue usado para crear compiladores para la computadora Atlas en la Universidad de Mánchester, incluyendo el compilador Atlas Autocode. Sin embargo, era bastante diferente de los compiladores de computador modernos, y hoy probablemente sería descrito como algo entre un compilador genérico altamente personalizable y un lenguaje extensible. El nombre 'compilador de computador' era bastante más apropiado para el sistema de Brooker de lo que lo es para la mayoría de los compiladores de computador modernos, los cuales sería mejor llamarlos generadores de analizadores sintácticos. Es casi seguro que el nombre "compilador de computador" se usa comúnmente debido a Yacc más que al trabajo de Brooker.

A principios de los años 60, Robert McClure en Texas Instruments inventó un compilador de computador llamado TMG, el nombre extraído de "transmogrificación".^[24]​^[25]​^[26]​^[27]​ En los posteriores años TMG fue portado a muchos computadores centrales de UNIVAC e IBM.

El proyecto Multics, un proyecto conjunto entre el MIT y los Laboratorios Bell, fue uno de los primeros en desarrollar un sistema operativo en un lenguaje de alto nivel. PL/1 fue escogido como el lenguaje, pero un proveedor externo no podía proveer un compilador en funcionamiento.^[28]​ El equipo Multics desarrolló su propio dialecto de PL/1, llamado Early PL/1 (EPL), como su lenguaje de implementación de 1964. TMG fue portado a las GE-600 series y usado 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, Doug McIlroy creó el primer lenguaje de programación de alto nivel del nuevo sistema: una implementación del TMG de McClure.^[29]​ TMG fue también la herramienta de definición del compilador usada por Ken Thompson para escribir el compilador del lenguaje B en su PDP-7 en 1970. B fue el inmediato predecesor de C.

Uno de los primeros generadores de analizador sintáctico LALR fue llamado “TWS”, creado por Frank DeRemer y Tom Pennello.

XPL es un dialecto del lenguaje de programación PL/1, desarrollado en 1967, usado para el desarrollo de compiladores de lenguajes de computación. Fue diseñado e implementado por un equipo formado por William McKeeman, James J. Horning y David B. Wortman en la Universidad Stanford y la Universidad de California, Santa Cruz. Se anunció por primera vez en la Conferencia de Ordenadores de Otoño de 1968 en San Francisco, California.^[30]​^[31]​

Es el nombre de tanto el lenguaje de programación como el sistema generador de analizador sintáctico LALR (o TWS: Translator Writing System) basado en el lenguaje.

XPL presentó un sistema de compilador de abajo a arriba (bottom-up compiler) relativamente simple denominado MSP (Mixed Strategy Precedence) por sus autores. Fue cargado a través de Burroughs Algol en el computador de IBM S/360. Implementaciones posteriores de XPL ofrecieron un analizador sintáctico SLR(1).

Yacc es un generador de analizador sintáctico desarrollado por Stephen C. Johnson en AT&T para el sistema operativo Unix.^[32]​ El nombre es un acrónimo de "Yet Another Compiler Compiler". Genera un analizador sintáctico LALR(1) basado en una gramática escrita en una notación similar a la Notación de Backus-Naur.

Johnson trabajó en Yacc a principios de los años 70 en Laboratorios Bell.^[33]​ Estaba familiarizado con TMG y su influencia puede verse en Yacc y en el diseño del lenguaje de programación C. A causa de que Yacc fue el generador de analizador sintáctico por defecto en la mayoría de sistemas Unix, fue ampliamente distribuido y usado. Desarrollos como GNU Bison todavía están en uso.

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

Un compilador cruzado se ejecuta en un entorno pero produce código objeto para otro. Los compiladores cruzados son usados para desarrollo embebido, donde el ordenador objetivo tiene capacidades limitadas.

Uno de los primeros ejemplos de compilación cruzada fue AIMICO, donde un programa FLOW-MATIC en un UNIVAC II fue usado para generar lenguaje ensamblador para el IBM 705, que fue después ensamblado en el computador de IBM.^[1]​

El compilador ALGOL 68C generaba una salida ZCODE, que luego podía ser compilado en código de la máquina local por un traductor ZCODE o ejecutarlo interpretado. ZCODE es un lenguaje intermedio basado en registros. Esta habilidad para interpretar o compilar ZCODE fomentó la portabilidad de ALGOL 68C a numerosas plataformas de computador diferentes.

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

Los desarrolladores del primer compilador de FORTRAN se propusieron generar código que fuese mejor que la media de los ensambladores codificados a mano, para que los clientes pudieran usar su producto. En uno de sus primeros compiladores, ellos tuvieron éxito.^[34]​

Posteriores compiladores, como el compilador Fortran IV de IBM, priorizó más en los buenos diagnósticos y en ejecutarse más rápidamente, a costa de la optimización del código objeto. No fue hasta las series IBM 360 en las que IBM proveyó dos compiladores separados en las que estuvo disponible: un comprobador de ejecución de código rápida y un optimizador más lento.

Frances E. Allen, trabajando sola y conjuntamente con John Cocke, presentó muchos de los conceptos de optimización. El artículo de Allen de 1966, Program Optimization,^[35]​ presentó el uso de las estructuras en forma de grafo para codificar el contenido de un programa para la optimización.^[36]​ Su artículo de 1970, Control Flow Analysis^[37]​ y A Basis for Program Optimization^[38]​ estableció intervalos como el contexto para el análisis y la optimización del flujo de datos eficiente y efectivo. Su artículo de 1971 conjunto con Cocke, A Catalog of Optimizing Transformations,^[39]​ dio 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 interprocedural extendió el análisis a los programas por completo.^[40]​^[41]​ Su artículo de 1976 conjunto con Cocke describe una de las dos principales estrategias de análisis usadas en los compiladores de optimización de hoy día.^[42]​

Allen desarrolló e implementó sus métodos como parte de compiladores para el IBM 7030 Stretch-Harvest y el experimental Advanced Computing System. Este trabajo estableció la factibilidad y la estructura de los optimizadores de las máquinas modernas. Ella llegó a establecer y liderar el proyecto PTRAN en la ejecución paralela automática de programas FORTRAN.^[43]​ Su equipo PTRAN desarrolló nuevos esquemas de detección de paralelismo y creó el concepto de grafo de dependencias del programa, el método de estructurado primario usado por la mayoría de los compiladores de paralelización.

Programming Languages and their Compilers de John Cocke y Jacob T. Schwartz, publicado por primera vez en 1970, dedicó más de 200 páginas a algoritmos de optimización. Incluyó muchas de las ahora familiares técnicas tales como eliminación de código redundante y reducción de esfuerzo.^[44]​

La optimización Peephole es una técnica de optimización muy simple pero efectiva. Fue inventada por William McKeeman y publicada en 1965 en CACM.^[45]​ Fue usada en el compilador XPL que McKeeman ayudó a desarrollar.

La Corporación Capex desarrolló el "Optimizador COBOL" a mediados de los años 70 para COBOL. Este tipo de optimizador depende, en este caso, del conocimiento de las 'debilidades' en el compilador IBM COBOL estándar, y de hecho reemplaza (o parchea secciones del código objeto con un código más eficiente. El código de reemplazo podría sustituir una tabla de consulta linear con una búsqueda binaria por ejemplo o a veces simplemente reemplazar una instrucción relativamente 'lenta' por una conocida más rápida que fuese funcionalmente equivalente en su contexto. Esta técnica es ahora conocida como "Reducción de esfuerzo". Por ejemplo en el hardware IBM S/360 la instrucción CLI era, dependiendo del modelo, entre 2 y 5 veces tan rápido como una instrucción CLC para comparaciones de un único byte.^[46]​^[47]​

Los compiladores modernos típicamente proveen opciones de optimización, para que los programadores puedan elegir si quieren o no ejecutar un pase de optimización.

Cuando a un compilador se le pasa un programa incorrecto sintácticamente, un buen, claro mensaje de error es útil. Desde la perspectiva del escritor del compilador, esto es a menudo difícil de conseguir.

El compilador Fortran WATFIV fue desarrollado en la Universidad de Waterloo, Canadá en los finales de los años 60. 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, enlazado y ejecución en un paso, mientras que los compiladores de IBM tenían tres componentes separados para su ejecución.

PL/C fue un lenguaje de programación de computador desarrollado en la Universidad de Cornell a principios de los años 70. Mientras que el PL/C era un subconjunto del lenguaje de IBM PL/1, fue diseñado con el objetivo específico de ser usado 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 "Design and implementation of a diagnostic compiler for PL/1" publicado en las comunicaciones del ACM en marzo de 1973.^[48]​

PL/C eliminó algunas de las más complejas características de PL/1, y añadió depuración extensiva y facilidades para recuperación de errores. El compilador PL/C tenía la inusual capacidad de nunca fallar al compilar cualquier programa, mediante el uso de la corrección automática de muchos errores sintácticos y la conversión de los errores sintácticos restantes a las declaraciones de salida.

• Compilador
• Lenguaje de programación
• Proceso de traducción de programas
• Lenguaje ensamblador
• Intérprete
• Lenguaje de alto nivel
• Lenguaje de bajo nivel
• Lenguaje de máquina
• Analizador sintáctico LL
• Lex, el analizador sintáctico de token comúnmente usado en conjunción con Yacc (y Bison)
• Analizador léxico
• BNF, una metasintaxis usada para expresar gramáticas libres de contexto: es decir, una manera formal de describir lenguajes formales.

• Backus, John, et al., "The FORTRAN Automatic Coding System", Proceedings of the Western Joint Computer Conference, Los Angeles, California, febrero de 1957. Describe el diseño y la implementación del primer compilador de FORTRAN por el equipo IBM.
• Bauer, Friedrich L.; Eickel, Jürgen (Eds.), Compiler Construction, An Advanced Course, 2nd ed. Lecture Notes in Computer Science 21, Springer 1976, ISBN 3-540-07542-9
• Cheatham, T. E., and Sattley, K., Syntax directed compilation, SJCC p. 31. (1964).
• Cocke, John; Schwartz, Jacob T., Programming Languages and their Compilers: Preliminary Notes, Courant Institute of Mathematical Sciences technical report, New York University, 1969.
• Conway, Melvin E., Design of a separable transition-diagram compiler, Communications of the ACM, Volume 6, Issue 7 (julio 1963)
• Floyd, R. W., Syntactic analysis and operator precedence, Journal of the ACM, Vol. 10, p. 316. (julio 1963).
• Gries, David, Compiler Construction for Digital Computers, New York: Wiley, 1971. ISBN 0-471-32776-X
• Irons, Edgar T., A syntax directed compiler for ALGOL 60, Communications of the ACM, Vol. 4, p. 51. (Jan. 1961)
• Knuth, D. E., On the translation of languages from left to right., Information and Control, Vol. 8, p. 607. (1965).
• Knuth, D. E., RUNCIBLE-algebraic translation on a limited computer, Communications of the ACM, Vol. 2, p. 18, (Nov. 1959).
• Randell, Brian]]; Russell, Lawford John, ALGOL 60 Implementation: The Translation and Use of ALGOL 60 Programs on a Computer, Academic Press, 1964
• Dick Grune's Annotated Literature Lists - Compiler Construction before 1980 [3]

• Este artículo utiliza contenidos de History of compiler construction en Wikipedia en Inglés.