thumb|right|Esquema de compilación

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.

Primeros compiladores

thumb|left|140px|Lenguaje de programación COBOL

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. The World's First COBOL Compilers 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.Backus et al. "The FORTRAN automatic coding system", Proc. AFIPS 1957 Western Joint Comuter Conf., Spartan Books, Baltimore 188-198

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. Rosen, Saul. ALTAC, FORTRAN, and compatibility. Proceedings of the 1961 16th ACM national meeting 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.

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.

Compiladores autoalojados

thumb|right|195px|Máquina LISP

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 autoalojado, es decir, escrito en el lenguaje de programación que lo compila. Construir un compilador autoalojado 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.

ELIAC

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 autocompilado 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.

Lisp

El primer compilador autoalojado (excluyendo ensambladores) fue escrito para Lisp por Tim Hart y Mike Levin en el MIT en 1962. CSAIL Digital Archive - Artificial Intelligence Laboratory Series 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 autoalojado.

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)

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.

Gramáticas libres de contexto y analizadores sintácticos

thumb|left|Analizador sintáctico

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.

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.

Análisis sintáctico LR

thumb|right|Analizador sintáctico LR

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).

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.Korenjak, A. “A Practical Method for Constructing LR(k) Processors,” Communications of the ACM, Vol. 12, No. 11, 1969 Frank DeRemer ideó las técnicas más prácticas SLR y LALR, publicadas en su tesis doctoral del MIT en 1969.DeRemer, F. Practical Translators for LR(k) Languages. Ph.D. dissertation, MIT, 1969.DeRemer, F. “Simple LR(k) Grammars,” Communications of the ACM, Vol. 14, No. 7, 1971. 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 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. La técnica fue expuesta después por G.H. Roberts en 1988 así como en un artículo de Leermakers, Augusteijn y Kruseman Aretz en 1992 en el diario Theoretical Computer Science.

Análisis sintáctico LL

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.