Historia de la construcción de los compiladores para niños
En informática, un compilador es un programa informático especial que toma un texto escrito en un lenguaje de programación (llamado código fuente) y lo convierte en otro tipo de lenguaje que la computadora puede entender y ejecutar directamente (conocido como código objeto o código binario). La razón principal para hacer esto es crear un programa que funcione en tu computadora.
Cualquier programa que escribes en un lenguaje de programación de alto nivel (como Python o Java) necesita ser traducido a código que la máquina entienda antes de poder ejecutarse. Por eso, los compiladores son herramientas muy importantes para los programadores. Cada mejora en un compilador puede hacer que muchos programas funcionen mejor.
Los compiladores son programas grandes y complejos. Sin embargo, gracias al trabajo de muchos científicos informáticos, ahora entendemos mejor cómo construirlos. Incluso existen herramientas que facilitan mucho la creación de compiladores. Esto permite que estudiantes de informática puedan crear sus propios lenguajes sencillos y desarrollar un compilador básico en pocas semanas.
Contenido
- Historia de los compiladores: ¿Cómo empezaron?
- Compiladores autoalojados: Cuando un compilador se construye a sí mismo
- Gramáticas y analizadores sintácticos: Entendiendo el lenguaje
- Lenguajes para describir gramáticas
- Compilador de compiladores: Creando herramientas para crear compiladores
- Compilación cruzada: Para diferentes computadoras
- Compiladores de optimización: Haciendo los programas más rápidos
- Diagnósticos: Ayudando a los programadores
- Galería de imágenes
- Véase también
Historia de los compiladores: ¿Cómo empezaron?
Al principio, los programas para las computadoras se escribían en un lenguaje llamado lenguaje ensamblador. Este lenguaje es muy cercano a cómo funciona la máquina, pero es difícil de usar para los humanos. Es mucho más fácil y rápido para un programador usar un lenguaje de alto nivel. Además, los programas escritos en lenguajes de alto nivel pueden funcionar en diferentes tipos de computadoras.
A pesar de estas ventajas, los compiladores tardaron en popularizarse. Esto se debía a que el código que generaban no era tan eficiente como el código escrito a mano por expertos. Además, crear un compilador era un proyecto enorme y las primeras computadoras tenían muy poca memoria, lo que dificultaba su implementación.
Los primeros pasos de la compilación
El primer compilador fue creado por Grace Hopper en 1952 para un lenguaje llamado Sistema A-0. Ella fue quien acuñó el término "compilador". El equipo de FORTRAN, liderado por John W. Backus en IBM, es reconocido por haber presentado el primer compilador completo en 1957. Este primer compilador de FORTRAN tardó 18 años-persona en ser creado, lo que significa que muchas personas trabajaron en él durante mucho tiempo.
En 1960, otro compilador de FORTRAN llamado ALTAC estuvo disponible para otra computadora. Esto hizo posible que un programa FORTRAN se pudiera usar en diferentes máquinas. El primer lenguaje de alto nivel que funcionó en varias plataformas fue COBOL. En una demostración en diciembre de 1960, un programa COBOL se compiló y ejecutó en dos computadoras diferentes: la UNIVAC II y la RCA 501.
El compilador COBOL para la UNIVAC II fue probablemente el primero en ser escrito en un lenguaje de alto nivel, llamado FLOW-MATIC. Este trabajo también fue dirigido por Grace Hopper.
Compiladores autoalojados: Cuando un compilador se construye a sí mismo
Al igual que otros programas, es útil que un compilador esté escrito en un lenguaje de alto nivel. Un compilador puede ser "autoalojado", lo que significa que está escrito en el mismo lenguaje de programación que compila. Crear un compilador autoalojado es como un proceso de "arranque" (bootstrapping). El primer compilador para un lenguaje debe ser compilado por otro compilador (escrito en un lenguaje diferente) o ejecutado por un intérprete.
ELIAC: El primer compilador que se compiló a sí mismo
El Navy Electronics Laboratory International ALGOL Compiler (NELIAC) fue una versión del lenguaje ALGOL 58. Fue desarrollado por el Naval Electronics Laboratory en 1958.
ELIAC fue una idea de Harry Huskey, un reconocido científico informático. La primera versión se hizo para una computadora prototipo llamada USQ-17. Fue el primer compilador que se compiló a sí mismo. Esto significa que el compilador se escribió primero de forma sencilla en lenguaje ensamblador (el "bootstrap"). Luego, se reescribió en su propio lenguaje, se compiló con el compilador "bootstrap", y finalmente se compiló a sí mismo, haciendo que el "bootstrap" ya no fuera necesario.
Lisp: Otro ejemplo temprano
El primer compilador autoalojado (sin contar los ensambladores) fue escrito para Lisp por Tim Hart y Mike Levin en el MIT en 1962. Ellos escribieron un compilador de Lisp en Lisp, probándolo con un intérprete de Lisp que ya existía. Una vez que el compilador fue lo suficientemente bueno como para compilar su propio código fuente, se convirtió en autoalojado.
Esta técnica solo es posible si ya existe un intérprete para el lenguaje que se va a compilar.
Gramáticas y analizadores sintácticos: Entendiendo el lenguaje
Un analizador sintáctico es una parte muy importante de un compilador. Su trabajo es examinar el código fuente de un programa para entender su estructura y crear una representación interna. Los lenguajes de programación suelen definirse usando algo llamado "gramática libre de contexto". Esto permite crear analizadores sintácticos rápidos y eficientes.
Los analizadores sintácticos pueden escribirse a mano o generarse con herramientas especiales. Una gramática libre de contexto es una forma sencilla y precisa de describir cómo se construyen los programas a partir de partes más pequeñas. Esta idea de las gramáticas libres de contexto fue desarrollada por Noam Chomsky a mediados de los años 50.
La forma de organizar el código en bloques fue introducida en los lenguajes de programación por el proyecto ALGOL (1957-1960). Este proyecto también ofreció una gramática libre de contexto para describir la forma de ALGOL.
Las gramáticas libres de contexto son lo suficientemente simples como para permitir la creación de algoritmos de análisis eficientes. Estos algoritmos pueden determinar cómo se puede generar una secuencia de texto a partir de la gramática. Si un diseñador de lenguajes trabaja con ciertas reglas de estas gramáticas, puede crear analizadores sintácticos aún más eficientes.
Análisis sintáctico LR: Leyendo de izquierda a derecha
El analizador sintáctico LR (que significa "de izquierda a derecha") fue inventado por Donald Knuth en 1965. Un analizador LR lee el código de izquierda a derecha y construye la estructura del programa. El término analizador sintáctico LR(k) se usa para indicar cuántos símbolos de entrada se "miran hacia adelante" sin consumir para tomar decisiones.
Knuth demostró que las gramáticas LR(k) pueden analizarse muy rápidamente. También mostró que cualquier gramática LR(k) con k mayor que 1 puede transformarse en una gramática LR(1). Esto significa que solo se necesita mirar un símbolo hacia adelante para analizar cualquier gramática determinista.
En la práctica, los analizadores LALR son una buena solución. Las gramáticas LALR(1) son más potentes que otras, y por eso los analizadores LALR se usan a menudo en los compiladores para analizar el código fuente.
Análisis sintáctico LL: Otra forma de leer
Un analizador sintáctico LL también lee la entrada de izquierda a derecha, pero construye la estructura del programa de una manera diferente a los analizadores LR. Las gramáticas que pueden ser analizadas por este método se llaman "gramáticas LL". Son un tipo de gramáticas libres de contexto más restrictivas que las LR. Sin embargo, son muy interesantes para quienes escriben compiladores porque son más sencillas y eficientes de implementar.
Las gramáticas LL(k) pueden ser analizadas por un tipo de analizador llamado "descendente recursivo", que a menudo se escribe a mano.
El diseño de ALGOL impulsó la investigación sobre el análisis descendente recursivo. Niklaus Wirth popularizó el análisis descendente recursivo con PL/0, un lenguaje de programación educativo usado para enseñar cómo construir compiladores en los años 70.
Los analizadores LR pueden manejar una gama más amplia de lenguajes que los LL. Además, los LR suelen dar mejores mensajes de error, detectando los problemas de sintaxis lo antes posible.
Algoritmo de Earley: Para cualquier lenguaje
En 1970, Jay Earley inventó el Algoritmo de Earley. Este algoritmo es útil porque puede analizar cualquier lenguaje libre de contexto de manera bastante eficiente.
Lenguajes para describir gramáticas
John Backus propuso "fórmulas meta-lingüísticas" para describir la forma del nuevo lenguaje de programación IAL, que hoy conocemos como ALGOL 58 (1959). El trabajo de Backus se basó en la Máquina de Post.
El desarrollo posterior de ALGOL llevó a ALGOL 60. En su informe (1963), Peter Naur llamó a la notación de Backus Notación de Backus-Naur (BNF) y la simplificó.
Niklaus Wirth definió la Notación de Backus-Naur Extendida (EBNF), una versión mejorada de BNF, a principios de los años 70 para PL/0. La Notación de Backus-Naur Aumentada (ABNF) es otra variante. Tanto EBNF como ABNF se usan mucho para especificar la gramática de los lenguajes de programación, y también en otros campos como la definición de protocolos de comunicación.
Compilador de compiladores: Creando herramientas para crear compiladores
Un compilador de compiladores 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 compiladores con ese nombre fue escrito por Tony Brooker en 1960. Se usó para crear compiladores para la computadora Atlas. Sin embargo, era diferente de los compiladores de compiladores modernos. Hoy en día, la mayoría de estos programas se llamarían mejor "generadores de analizadores sintácticos".
A principios de los años 60, Robert McClure inventó un compilador de compiladores llamado TMG. TMG fue llevado a muchas computadoras de UNIVAC e IBM.
El proyecto Multics, una colaboración entre el MIT y los Laboratorios Bell, fue uno de los primeros en desarrollar un sistema operativo en un lenguaje de alto nivel. Eligieron PL/1 como lenguaje. El equipo de Multics desarrolló su propia versión de PL/1, llamada Early PL/1 (EPL), como su lenguaje de implementación desde 1964. TMG se usó para desarrollar EPL.
Poco después de que Ken Thompson escribiera la primera versión de Unix en 1969, Doug McIlroy creó el primer lenguaje de programación de alto nivel para el nuevo sistema: una implementación del TMG de McClure. TMG también fue la herramienta usada por Ken Thompson para escribir el compilador del lenguaje B en 1970. B fue el predecesor directo de C.
XPL: Un lenguaje para crear compiladores
XPL es una versión del lenguaje de programación PL/1, desarrollado en 1967. Se usó para crear compiladores de lenguajes de computadora. Fue diseñado e implementado por un equipo de la Universidad Stanford y la Universidad de California, Santa Cruz.
XPL era tanto el nombre del lenguaje de programación como el sistema generador de analizador sintáctico LALR basado en el lenguaje.
Yacc: Un generador muy popular
Yacc es un generador de analizador sintáctico desarrollado por Stephen C. Johnson en AT&T para el sistema operativo Unix. Su nombre significa "Yet Another Compiler Compiler" (Otro compilador de compiladores más). Genera un analizador sintáctico LALR(1) basado en una gramática escrita de forma similar a la Notación de Backus-Naur.
Johnson trabajó en Yacc a principios de los años 70 en los Laboratorios Bell. Como Yacc era el generador de analizador sintáctico predeterminado en la mayoría de los sistemas Unix, se distribuyó y usó ampliamente. Desarrollos como GNU Bison todavía se usan hoy en día.
El analizador sintáctico generado por Yacc necesita un analizador léxico. Los generadores de analizadores léxicos, como Lex o Flex, están muy disponibles.
Compilación cruzada: Para diferentes computadoras
Un compilador cruzado es un tipo de compilador que se ejecuta en un tipo de computadora, pero produce código para otro tipo de computadora. Los compiladores cruzados se usan mucho en el desarrollo de sistemas "embebidos" (como los que controlan electrodomésticos o coches), donde la computadora de destino tiene capacidades limitadas.
Un ejemplo temprano de compilación cruzada fue AIMICO. Un programa FLOW-MATIC en una UNIVAC II se usó para generar lenguaje ensamblador para la IBM 705.
Compiladores de optimización: Haciendo los programas más rápidos
La optimización de compiladores es el proceso de mejorar la calidad del código que produce un compilador sin cambiar los resultados del programa. El objetivo es hacer que el programa sea más rápido o use menos recursos.
Los creadores del primer compilador de FORTRAN querían generar código que fuera mejor que el escrito a mano por la mayoría de los programadores. Y lo lograron.
Más tarde, algunos compiladores se enfocaron más en dar buenos mensajes de error y en compilar más rápido, aunque el código resultante no fuera el más optimizado. No fue hasta las series IBM 360 que IBM ofreció dos compiladores diferentes: uno para una ejecución rápida y otro más lento que optimizaba el código.
Frances E. Allen, una destacada científica informática, desarrolló muchos conceptos de optimización. Su trabajo ayudó a establecer cómo se podían analizar y optimizar los programas de manera eficiente. Ella también lideró un proyecto para ejecutar programas FORTRAN de forma paralela, lo que significa que varias partes del programa se ejecutan al mismo tiempo para acelerarlo.
El libro "Programming Languages and their Compilers" de John Cocke y Jacob T. Schwartz, publicado en 1970, dedicó muchas páginas a los algoritmos de optimización. Incluyó técnicas que ahora son comunes, como eliminar código innecesario y reducir el esfuerzo que la computadora necesita para realizar ciertas operaciones.
Optimización Peephole: Pequeños ajustes
La optimización Peephole es una técnica de optimización muy sencilla pero efectiva. Fue inventada por William McKeeman y publicada en 1965. Se usó en el compilador XPL. Consiste en examinar pequeñas secuencias de instrucciones del código y reemplazarlas por otras más eficientes.
Optimizador Capex COBOL: Mejorando el código existente
La Corporación Capex desarrolló el "Optimizador COBOL" a mediados de los años 70. Este optimizador conocía las "debilidades" del compilador estándar de IBM COBOL. Reemplazaba partes del código generado con código más eficiente. Por ejemplo, podía cambiar una búsqueda lineal en una tabla por una búsqueda binaria, que es mucho más rápida.
Los compiladores modernos suelen ofrecer opciones de optimización. Así, los programadores pueden elegir si quieren que el compilador intente hacer su programa más rápido.
Diagnósticos: Ayudando a los programadores
Cuando un compilador recibe un programa con errores de sintaxis (es decir, que no está bien escrito según las reglas del lenguaje), es muy útil que dé un mensaje de error claro. Desde la perspectiva de quien escribe el compilador, esto a menudo es 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 dar mejores mensajes de error que los compiladores de IBM de la época. Además, WATFIV era más fácil de usar porque combinaba la compilación, el enlazado y la ejecución en un solo paso. Los compiladores de IBM tenían tres componentes separados.
PL/C: Un compilador para aprender
PL/C fue un lenguaje de programación desarrollado en la Universidad de Cornell a principios de los años 70. Aunque PL/C era una versión simplificada del lenguaje PL/1 de IBM, fue diseñado específicamente para enseñar programación. Los profesores Richard W. Conway y Thomas R. Wilcox lo diseñaron.
PL/C eliminó algunas de las características más complejas de PL/1 y añadió muchas herramientas para depurar (encontrar y corregir errores) y recuperar errores. El compilador PL/C tenía la capacidad inusual de nunca fallar al compilar un programa. Lo hacía corrigiendo automáticamente muchos errores de sintaxis y convirtiendo los errores restantes en mensajes de salida.
Galería de imágenes
-
Esquema de compilación
Véase también
En inglés: 