Compilador

En informática , un compilador es un software que traduce código informático escrito en un lenguaje de programación (el lenguaje fuente ) a otro lenguaje (el lenguaje destino ). El término "compilador" se utiliza principalmente para programas que traducen código fuente de un lenguaje de programación de alto nivel a un lenguaje de programación de bajo nivel (por ejemplo, lenguaje ensamblador , código objeto o código máquina ) para crear un programa ejecutable . ^{[ 1 ] [ 2 ] : p1 [ 3 ]}

Existen muchos tipos diferentes de compiladores que generan código en distintos formatos útiles. Un compilador cruzado produce código para una unidad central de procesamiento (CPU) o sistema operativo distinto al del propio compilador. Un compilador de arranque suele ser un compilador temporal, utilizado para compilar un compilador más permanente o mejor optimizado para un lenguaje de programación.

El software relacionado incluye descompiladores , programas que traducen de lenguajes de bajo nivel a lenguajes de alto nivel; programas que traducen entre lenguajes de alto nivel, generalmente llamados compiladores de código fuente a código fuente o transpiladores ; reescritores de lenguaje , generalmente programas que traducen la forma de las expresiones sin cambiar el idioma; y compiladores-compiladores , compiladores que producen compiladores (o partes de ellos), a menudo de forma genérica y reutilizable para poder producir muchos compiladores diferentes.

Es probable que un compilador realice algunas o todas las siguientes operaciones, a menudo denominadas fases: preprocesamiento , análisis léxico , análisis sintáctico , análisis semántico ( traducción dirigida por la sintaxis ), conversión de programas de entrada a una representación intermedia , optimización de código y generación de código específico de la máquina . Los compiladores generalmente implementan estas fases como componentes modulares, lo que promueve un diseño eficiente y la corrección de las transformaciones de la entrada fuente a la salida objetivo. Los fallos de programa causados ​​por un comportamiento incorrecto del compilador pueden ser muy difíciles de rastrear y solucionar; por lo tanto, los desarrolladores de compiladores invierten un esfuerzo significativo para garantizar la corrección del compilador . ^{[ 4 ]}

Con respecto a hacer que el código fuente sea ejecutable, un intérprete proporciona una función similar a la de un compilador, pero a través de un mecanismo diferente. Un intérprete ejecuta el código sin convertirlo a código máquina. ^{[ 2 ] : p2} Por lo tanto, algunos intérpretes ejecutan el código fuente mientras que otros ejecutan una forma intermedia como el código de bytes .

Un programa compilado a código nativo tiende a ejecutarse más rápido que cuando se interpreta, mientras que los entornos con un formato intermedio de bytecode tienden a una velocidad intermedia. Por otro lado, la compilación justo a tiempo permite la velocidad de ejecución nativa con un coste de tiempo de procesamiento de inicio único.

Los lenguajes de programación de bajo nivel , como el ensamblador y C , suelen compilarse, sobre todo cuando la velocidad es un factor importante, en lugar de ofrecer compatibilidad multiplataforma . En estos lenguajes, existe una correspondencia más directa entre el código fuente y el código máquina resultante , lo que facilita a los programadores el control del uso del hardware.

En teoría, cualquier lenguaje de programación puede utilizarse mediante un compilador o un intérprete, pero en la práctica, los lenguajes suelen usarse solo con uno de ellos. No obstante, es posible escribir un compilador para un lenguaje que se interpreta habitualmente. Por ejemplo, Common Lisp puede compilarse a código de bytes de Java (y luego ser interpretado por la máquina virtual de Java ), a código C (que posteriormente puede compilarse de nuevo a código máquina nativo) o directamente a código nativo.

Los conceptos teóricos de computación desarrollados por científicos, matemáticos e ingenieros sentaron las bases del desarrollo de la computación digital moderna durante la Segunda Guerra Mundial. Los lenguajes binarios primitivos evolucionaron porque los dispositivos digitales solo entienden unos y ceros y los patrones de circuitos en la arquitectura de la máquina subyacente. A finales de la década de 1940, se crearon lenguajes ensamblador para ofrecer una abstracción más práctica de las arquitecturas de computadoras. ^{[ 5 ]} La limitada capacidad de memoria de las primeras computadoras generó importantes desafíos técnicos al diseñar los primeros compiladores. Por lo tanto, el proceso de compilación debía dividirse en varios programas pequeños. Los programas de la parte frontal producían los productos de análisis que los programas de la parte posterior utilizaban para generar el código objetivo. A medida que la tecnología informática proporcionó más recursos, los diseños de compiladores pudieron alinearse mejor con el proceso de compilación.

Por lo general, para un programador es más productivo usar un lenguaje de alto nivel, por lo que el desarrollo de estos lenguajes surgió de forma natural a partir de las capacidades que ofrecen las computadoras digitales. Los lenguajes de alto nivel son lenguajes formales que se definen estrictamente por su sintaxis y semántica , las cuales conforman la arquitectura del lenguaje. Algunos elementos de estos lenguajes formales son:

• Alfabeto , cualquier conjunto finito de símbolos
• Cadena , una secuencia finita de símbolos
• Lenguaje , cualquier conjunto de cadenas de caracteres en un alfabeto.

Las oraciones en un idioma pueden definirse mediante un conjunto de reglas llamado gramática. ^{[ 6 ]}

La forma Backus-Naur (BNF) describe la sintaxis de las "oraciones" de un lenguaje. Fue desarrollada por John Backus y utilizada para la sintaxis de Algol 60. [ ^{7 ] Las} ideas derivan de los conceptos de gramática libre de contexto del lingüista Noam Chomsky . ^{[ 8 ]} "La BNF y sus extensiones se han convertido en herramientas estándar para describir la sintaxis de las notaciones de programación. En muchos casos, partes de los compiladores se generan automáticamente a partir de una descripción BNF." ^{[ 9 ]}

Entre 1942 y 1945, Konrad Zuse diseñó el primer lenguaje de programación ( algoritmo ) para computadoras llamado Plankalkül ("Plan Calculus"). Zuse también concibió un Planfertigungsgerät ("Plan Assembly Device") para traducir automáticamente la formulación matemática de un programa a una película perforada legible por máquina . ^{[ 10 ]} Si bien no se implementó hasta la década de 1970, presentó conceptos que luego se vieron en APL , diseñado por Ken Iverson a finales de la década de 1950. ^{[ 11 ]} APL es un lenguaje para cálculos matemáticos.

Entre 1949 y 1951, Heinz Rutishauser propuso Superplan , un lenguaje de alto nivel y traductor automático. ^{[ 12 ]} Sus ideas fueron posteriormente perfeccionadas por Friedrich L. Bauer y Klaus Samelson . ^{[ 13 ]}

El diseño de lenguajes de alto nivel durante los años formativos de la informática digital proporcionó herramientas de programación útiles para una variedad de aplicaciones:

• FORTRAN (Formula Translation) para aplicaciones de ingeniería y ciencia se considera uno de los primeros lenguajes de alto nivel implementados y el primer compilador optimizador. ^{[ 14 ]}
• COBOL (Common Business-Oriented Language) evolucionó a partir de A-0 y FLOW-MATIC para convertirse en el lenguaje de alto nivel dominante para aplicaciones empresariales. ^{[ 15 ]}
• LISP (List Processor) para computación simbólica. ^{[ 16 ]}

La tecnología de compiladores evolucionó a partir de la necesidad de una transformación estrictamente definida del programa fuente de alto nivel en un programa objetivo de bajo nivel para la computadora digital. El compilador puede considerarse como una interfaz para el análisis del código fuente y una parte posterior para sintetizar dicho análisis en el código objetivo. La optimización entre la interfaz y la parte posterior puede generar un código objetivo más eficiente. ^{[ 17 ]}

Algunos hitos iniciales en el desarrollo de la tecnología de compiladores:

• Mayo de 1952 : El equipo de Grace Hopper en Remington Rand escribió el compilador para el lenguaje de programación A-0 (y acuñó el término compilador para describirlo), ^{[ 18 ] [ 19 ] [ 20 ]} aunque el compilador A-0 funcionaba más como un cargador o enlazador que como un compilador completo según la noción moderna. ^{[ 21 ] [ 22 ] [ 23 ]}
• 1952, antes de septiembre : Un compilador Autocode desarrollado por Alick Glennie para la computadora Manchester Mark I en la Universidad de Manchester es considerado por algunos como el primer lenguaje de programación compilado. ^{[ 24 ]}
• 1954–1957 : Un equipo liderado por John Backus en IBM desarrolló FORTRAN , considerado generalmente el primer lenguaje de alto nivel. En 1957, completaron un compilador de FORTRAN al que se le atribuye haber introducido el primer compilador completo sin ambigüedades. ^{[ 25 ]}
• 1959 : La Conferencia sobre Lenguajes de Sistemas de Datos (CODASYL) dio inicio al desarrollo de COBOL . El diseño de COBOL se basó en A-0 y FLOW-MATIC. A principios de la década de 1960, COBOL se compilaba en múltiples arquitecturas.
• 1958–1960 : ALGOL 58 fue el precursor de ALGOL 60. Introdujo los bloques de código , un avance clave en el auge de la programación estructurada . ALGOL 60 fue el primer lenguaje en implementar definiciones de funciones anidadas con ámbito léxico . Incluía recursión . Su sintaxis se definió utilizando BNF . ALGOL 60 inspiró a muchos lenguajes posteriores. Tony Hoare comentó: «... no solo fue una mejora con respecto a sus predecesores, sino también con respecto a casi todos sus sucesores». ^{[ 26 ] [ 27 ]}
• 1958–1962 : John McCarthy del MIT diseñó LISP . ^{[ 28 ]} Las capacidades de procesamiento de símbolos proporcionaron características útiles para la investigación en inteligencia artificial. En 1962, la versión 1.5 de LISP incluyó algunas herramientas: un intérprete escrito por Stephen Russell y Daniel J. Edwards, y un compilador y ensamblador escritos por Tim Hart y Mike Levin. ^{[ 29 ]}

Los primeros sistemas operativos y programas informáticos se escribían en lenguaje ensamblador. En las décadas de 1960 y principios de 1970, el uso de lenguajes de alto nivel para la programación de sistemas seguía siendo controvertido debido a las limitaciones de recursos. Sin embargo, diversas investigaciones e iniciativas industriales impulsaron la transición hacia lenguajes de programación de sistemas de alto nivel, como BCPL , BLISS , B y C.

BCPL (Basic Combined Programming Language), diseñado en 1966 por Martin Richards en la Universidad de Cambridge, se desarrolló originalmente como una herramienta para escribir compiladores. ^{[ 30 ]} Se han implementado varios compiladores; el libro de Richards ofrece información valiosa sobre el lenguaje y su compilador. ^{[ 31 ]} BCPL no solo fue un lenguaje de programación de sistemas influyente que aún se utiliza en la investigación ^{[ 32 ]} , sino que también sentó las bases para el diseño de los lenguajes B y C.

BLISS (Lenguaje Básico para la Implementación de Software de Sistema) fue desarrollado para la computadora PDP-10 de Digital Equipment Corporation (DEC) por el equipo de investigación de W. A. ​​Wulf en la Universidad Carnegie Mellon (CMU). Un año después, en 1970, el equipo de la CMU desarrolló el compilador BLISS-11.

Multics (Multiplexed Information and Computing Service), un proyecto de sistema operativo de tiempo compartido, involucró al MIT , Bell Labs , General Electric (más tarde Honeywell ) y fue liderado por Fernando Corbató del MIT. ^{[ 33 ]} Multics fue escrito en el lenguaje PL/I desarrollado por IBM e IBM User Group. ^{[ 34 ]} El objetivo de IBM era satisfacer los requisitos de programación de sistemas, científicos y empresariales. Había otros lenguajes que podrían haberse considerado, pero PL/I ofrecía la solución más completa, aunque no se había implementado. ^{[ 35 ]} Durante los primeros años del proyecto Multics, un subconjunto del lenguaje podía compilarse a lenguaje ensamblador con el compilador Early PL/I (EPL) de Doug McIlory y Bob Morris de Bell Labs. ^{[ 36 ]} EPL dio soporte al proyecto hasta que se pudo desarrollar un compilador de arranque para PL/I completo. ^{[ 37 ]}

Bell Labs abandonó el proyecto Multics en 1969 y desarrolló un lenguaje de programación de sistemas, B, basado en conceptos de BCPL, escrito por Dennis Ritchie y Ken Thompson . Ritchie creó un compilador de arranque para B y escribió el sistema operativo Unics (Uniplexed Information and Computing Service) para un PDP-7 en B. Unics finalmente pasó a escribirse Unix.

Bell Labs inició el desarrollo y la expansión de C basándose en B y BCPL. El compilador BCPL había sido trasladado a Multics por Bell Labs y BCPL era un lenguaje preferido en Bell Labs. ^{[ 38 ]} Inicialmente, se utilizó un programa de interfaz para el compilador B de Bell Labs mientras se desarrollaba un compilador C. En 1971, un nuevo PDP-11 proporcionó los recursos para definir extensiones a B y reescribir el compilador. Para 1973, el diseño del lenguaje C estaba prácticamente completo y el núcleo Unix para un PDP-11 se reescribió en C. Steve Johnson comenzó el desarrollo del Compilador C Portátil (PCC) para admitir la adaptación de compiladores C a nuevas máquinas. ^{[ 39 ] [ 40 ]}

La programación orientada a objetos (POO) ofreció algunas posibilidades interesantes para el desarrollo y mantenimiento de aplicaciones. Los conceptos de POO se remontan a mucho antes, pero formaban parte de la ciencia del lenguaje LISP y Simula . ^{[ 41 ]} Bell Labs se interesó en la POO con el desarrollo de C++ . ^{[ 42 ]} C++ se utilizó por primera vez en 1980 para la programación de sistemas. El diseño inicial aprovechó las capacidades de programación de sistemas del lenguaje C con conceptos de Simula. Las funcionalidades orientadas a objetos se añadieron en 1983. ^{[ 43 ]} El programa Cfront implementó un front-end de C++ para el compilador del lenguaje C84. En los años siguientes se desarrollaron varios compiladores de C++ a medida que crecía la popularidad de C++.

En muchos ámbitos de aplicación, la idea de utilizar un lenguaje de alto nivel se popularizó rápidamente. Debido a la creciente funcionalidad que ofrecían los lenguajes de programación más recientes y a la creciente complejidad de las arquitecturas informáticas, los compiladores se volvieron más complejos.

DARPA (Agencia de Proyectos de Investigación Avanzada de Defensa) patrocinó un proyecto de compilador con el equipo de investigación de Wulf en la CMU en 1970. El diseño del compilador de calidad de producción ( PQCC ) produciría un compilador de calidad de producción (PQC) a partir de definiciones formales del lenguaje fuente y el lenguaje de destino. ^{[ 44 ]} PQCC intentó extender el término compilador-compilador más allá del significado tradicional de generador de analizadores sintácticos (por ejemplo, Yacc ), sin mucho éxito. Quizás sería más apropiado denominar a PQCC como generador de compiladores.

La investigación del PQCC sobre el proceso de generación de código buscaba construir un sistema de escritura de compiladores verdaderamente automático. El esfuerzo descubrió y diseñó la estructura de fases del PQC. El compilador BLISS-11 proporcionó la estructura inicial. ^{[ 45 ]} Las fases incluían análisis (front end), traducción intermedia a máquina virtual (middle end) y traducción al destino (back end). TCOL se desarrolló para la investigación del PQCC para manejar construcciones específicas del lenguaje en la representación intermedia. ^{[ 46 ]} Variaciones de TCOL admitían varios lenguajes. El proyecto PQCC investigó técnicas de construcción automatizada de compiladores. Los conceptos de diseño resultaron útiles en la optimización de compiladores y compiladores para el lenguaje de programación Ada (orientado a objetos desde 1995) .

El documento Ada STONEMAN ^{[ a ]} formalizó el entorno de soporte del programa (APSE) junto con el núcleo (KAPSE) y el mínimo (MAPSE). Un intérprete de Ada NYU/ED apoyó los esfuerzos de desarrollo y estandarización con el Instituto Nacional Estadounidense de Estándares (ANSI) y la Organización Internacional de Normalización (ISO). El desarrollo inicial del compilador de Ada por parte de los Servicios Militares de EE. UU. incluyó los compiladores en un entorno de diseño integrado completo según las líneas del documento STONEMAN . El Ejército y la Armada trabajaron en el proyecto del Sistema de Lenguaje Ada (ALS) dirigido a la arquitectura DEC/VAX, mientras que la Fuerza Aérea comenzó con el Entorno Integrado de Ada (AIE) dirigido a la serie IBM 370. Si bien los proyectos no proporcionaron los resultados deseados, sí contribuyeron al esfuerzo general en el desarrollo de Ada. ^{[ 47 ]}

Otros esfuerzos para compilar Ada se pusieron en marcha en Gran Bretaña en la Universidad de York y en Alemania en la Universidad de Karlsruhe . En EE. UU., Verdix (adquirida posteriormente por Rational) entregó el Sistema de Desarrollo Ada de Verdix (VADS) al Ejército. VADS proporcionó un conjunto de herramientas de desarrollo, incluido un compilador. Unix/VADS podía alojarse en una variedad de plataformas Unix, como DEC Ultrix y Sun 3/60 Solaris, dirigido a Motorola 68020 en una evaluación del CECOM del Ejército. ^{[ 48 ]} Pronto hubo muchos compiladores de Ada disponibles que pasaron las pruebas de validación de Ada. El proyecto GNU de la Free Software Foundation desarrolló la Colección de Compiladores GNU (GCC), que proporciona una capacidad central para admitir múltiples lenguajes y objetivos. La versión de Ada GNAT es uno de los compiladores de Ada más utilizados. GNAT es gratuito, pero también hay soporte comercial; por ejemplo, AdaCore se fundó en 1994 para proporcionar soluciones de software comerciales para Ada. GNAT Pro incluye GNAT, basado en GNU GCC, con un conjunto de herramientas para proporcionar un entorno de desarrollo integrado .

Los lenguajes de alto nivel continuaron impulsando la investigación y el desarrollo de compiladores. Las áreas de enfoque incluyeron la optimización y la generación automática de código. Las tendencias en lenguajes de programación y entornos de desarrollo influyeron en la tecnología de compiladores. Cada vez más compiladores se incluyeron en distribuciones de lenguajes (PERL, Java Development Kit) y como componente de un IDE (VADS, Eclipse, Ada Pro). La interrelación e interdependencia de las tecnologías creció. La llegada de los servicios web impulsó el crecimiento de los lenguajes web y de scripting. Los scripts se remontan a los inicios de las interfaces de línea de comandos (CLI), donde el usuario podía ingresar comandos para que el sistema los ejecutara. Los conceptos de shell de usuario se desarrollaron con lenguajes para escribir programas de shell. Los primeros diseños de Windows ofrecían una sencilla capacidad de programación por lotes. La transformación convencional de estos lenguajes utilizaba un intérprete. Si bien no se utilizan ampliamente, se han escrito compiladores de Bash y Batch. Más recientemente, los lenguajes interpretados sofisticados se han incorporado al conjunto de herramientas de los desarrolladores. Los lenguajes de scripting modernos incluyen PHP, Python, Ruby y Lua. (Lua se utiliza ampliamente en el desarrollo de videojuegos). Todos ellos cuentan con soporte para intérpretes y compiladores. ^{[ 49 ]}

Cuando el campo de la compilación comenzó a finales de los años 50, su enfoque se limitaba a la traducción de programas de lenguajes de alto nivel a código máquina... El campo de los compiladores está cada vez más entrelazado con otras disciplinas, como la arquitectura de computadoras, los lenguajes de programación, los métodos formales, la ingeniería de software y la seguridad informática. ^{[ 50 ]} El artículo «Investigación sobre compiladores: los próximos 50 años» destacó la importancia de los lenguajes orientados a objetos y Java. La seguridad y la computación paralela se mencionaron entre los objetivos de investigación futuros.

Un compilador implementa una transformación formal de un programa fuente de alto nivel a un programa objetivo de bajo nivel. El diseño de un compilador puede definir una solución integral o abordar un subconjunto específico que interactúa con otras herramientas de compilación, como preprocesadores, ensambladores y enlazadores. Los requisitos de diseño incluyen interfaces rigurosamente definidas, tanto internamente entre los componentes del compilador como externamente entre los conjuntos de herramientas de soporte.

En sus inicios, el enfoque adoptado para el diseño de compiladores se veía directamente afectado por la complejidad del lenguaje de programación a procesar, la experiencia de la(s) persona(s) que lo diseñaban y los recursos disponibles. Las limitaciones de recursos obligaban a recorrer el código fuente más de una vez.

Un compilador para un lenguaje relativamente sencillo, escrito por una sola persona, podría ser un único programa monolítico. Sin embargo, a medida que el lenguaje fuente se vuelve más complejo, el diseño puede dividirse en varias fases interdependientes. Estas fases permiten mejorar el diseño y centrar el desarrollo en las funciones del proceso de compilación.

Estructura de compilador de tres etapas

Independientemente del número exacto de fases en el diseño del compilador, estas pueden asignarse a una de tres etapas. Dichas etapas incluyen una fase inicial, una fase intermedia y una fase final.

• El front-end escanea la entrada y verifica la sintaxis y la semántica según un lenguaje fuente específico. Para lenguajes de tipado estático, realiza la comprobación de tipos recopilando información de tipos. Si el programa de entrada es sintácticamente incorrecto o tiene un error de tipo, genera mensajes de error y/o advertencia, que generalmente identifican la ubicación en el código fuente donde se detectó el problema; en algunos casos, el error puede estar (mucho) antes en el programa. El front-end incluye análisis léxico, análisis sintáctico y análisis semántico. El front-end transforma el programa de entrada en una representación intermedia (RI) para su posterior procesamiento por el middle-end. Esta RI suele ser una representación de nivel inferior del programa con respecto al código fuente.
• La parte intermedia realiza optimizaciones en el IR que son independientes de la arquitectura de la CPU de destino. Esta independencia entre el código fuente y el código máquina tiene como objetivo permitir que las optimizaciones genéricas se compartan entre versiones del compilador que admiten diferentes lenguajes y procesadores de destino. Ejemplos de optimizaciones de la parte intermedia son la eliminación de código inútil ( eliminación de código muerto ) o inaccesible ( análisis de alcanzabilidad ), el descubrimiento y la propagación de valores constantes ( propagación de constantes ), la reubicación de cálculos a un lugar de ejecución menos frecuente (por ejemplo, fuera de un bucle) o la especialización de cálculos en función del contexto, produciendo finalmente el IR "optimizado" que utiliza la parte final.
• El back-end toma el IR optimizado del middle-end. Puede realizar análisis, transformaciones y optimizaciones adicionales específicas para la arquitectura de la CPU de destino. El back-end genera el código ensamblador dependiente del destino, realizando la asignación de registros en el proceso. El back-end realiza la planificación de instrucciones , que reordena las instrucciones para mantener ocupadas las unidades de ejecución paralelas mediante el llenado de ranuras de retardo . Aunque la mayoría de los problemas de optimización son NP-difíciles , las técnicas heurísticas para resolverlos están bien desarrolladas e implementadas en compiladores de calidad de producción. Normalmente, la salida de un back-end es código máquina especializado para un procesador y sistema operativo en particular.

Este enfoque de front-end/middle/back-end permite combinar front-ends para diferentes lenguajes con back-ends para diferentes CPU , compartiendo las optimizaciones del middle-end. ^{[ 51 ]} Ejemplos prácticos de este enfoque son GNU Compiler Collection , Clang ( compilador de C/C++ basado en LLVM ), ^{[ 52 ]} y Amsterdam Compiler Kit , que tienen múltiples front-ends, optimizaciones compartidas y múltiples back-ends.

Interfaz

El front-end analiza el código fuente para construir una representación interna del programa, denominada representación intermedia (IR). También gestiona la tabla de símbolos , una estructura de datos que relaciona cada símbolo del código fuente con información como su ubicación, tipo y ámbito.

Aunque el frontend puede ser una única función o programa monolítico, como en un analizador sintáctico sin escáner , tradicionalmente se implementaba y analizaba en varias fases, que podían ejecutarse de forma secuencial o concurrente. Este método se prefiere debido a su modularidad y separación de responsabilidades . Lo más común es que el frontend se divida en tres fases: análisis léxico (también conocido como lexing o scan), análisis sintáctico (también conocido como scan o parsing) y análisis semántico . El lexing y el parsing comprenden el análisis sintáctico (sintaxis de palabras y sintaxis de frases, respectivamente), y en casos sencillos, estos módulos (el lexer y el parser) pueden generarse automáticamente a partir de una gramática del idioma, aunque en casos más complejos requieren modificación manual. La gramática léxica y la gramática de frases suelen ser gramáticas libres de contexto , lo que simplifica significativamente el análisis, y la sensibilidad al contexto se maneja en la fase de análisis semántico. La fase de análisis semántico suele ser más compleja y se realiza manualmente, pero puede automatizarse parcial o totalmente mediante gramáticas de atributos . Estas fases, a su vez, pueden subdividirse: el análisis léxico como escaneo y evaluación, y el análisis sintáctico como la construcción de un árbol sintáctico concreto (CST, árbol de análisis) y su posterior transformación en un árbol sintáctico abstracto (AST, árbol de sintaxis). En algunos casos se utilizan fases adicionales, como la reconstrucción de líneas y el preprocesamiento, pero son poco frecuentes.

Las fases principales del desarrollo front-end incluyen las siguientes:

• La reconstrucción de línea convierte la secuencia de caracteres de entrada a una forma canónica lista para el analizador sintáctico. Los lenguajes quelimitansus palabras clave o permiten espacios arbitrarios dentro de los identificadores requieren esta fase. Losdescendentes,recursivosy basados ​​en tablas utilizados en la década de 1960 solían leer el código fuente carácter por carácter y no requerían una fase de tokenización independiente.Atlas AutocodeeImp(y algunas implementaciones deALGOLyCoral 66) son ejemplos de lenguajes limitados cuyos compiladores sí incluían unade reconstrucción de línea.
• El preprocesamiento admite la sustitución de macros y la compilación condicional . Normalmente, la fase de preprocesamiento se realiza antes del análisis sintáctico o semántico; por ejemplo, en el caso de C, el preprocesador manipula los tokens léxicos en lugar de las formas sintácticas. Sin embargo, algunos lenguajes, como Scheme, admiten sustituciones de macros basadas en formas sintácticas.
• El análisis léxico (también conocido como lexing o tokenización ) divide el texto del código fuente en una secuencia de pequeñas piezas llamadas tokens léxicos . ^{[ 53 ]} Esta fase se puede dividir en dos etapas: el escaneo , que segmenta el texto de entrada en unidades sintácticas llamadas lexemas y les asigna una categoría; y la evaluación , que convierte los lexemas en un valor procesado. Un token es un par que consta de un nombre de token y un valor de token opcional . ^{[ 54 ]} Las categorías de tokens comunes pueden incluir identificadores, palabras clave, separadores, operadores, literales y comentarios, aunque el conjunto de categorías de tokens varía en diferentes lenguajes de programación . La sintaxis de los lexemas es típicamente un lenguaje regular , por lo que se puede utilizar un autómata de estados finitos construido a partir de una expresión regular para reconocerlo. El software que realiza el análisis léxico se llama analizador léxico . Puede que no se trate de un paso independiente; puede combinarse con el paso de análisis sintáctico en el análisis sin escáner , en cuyo caso el análisis se realiza a nivel de carácter, no a nivel de token.
• El análisis sintáctico (también conocido como parsing ) consiste en analizar la secuencia de tokens para identificar la estructura sintáctica del programa. Esta fase suele construir un árbol de análisis , que reemplaza la secuencia lineal de tokens con una estructura de árbol construida según las reglas de una gramática formal que define la sintaxis del lenguaje. El árbol de análisis suele ser analizado, ampliado y transformado por fases posteriores del compilador. ^{[ 55 ]}
• El análisis semántico añade información semántica al árbol de análisis sintáctico y construye la tabla de símbolos . Esta fase realiza comprobaciones semánticas como la verificación de tipos (para detectar errores de tipo), la vinculación de objetos (que asocia las referencias a variables y funciones con sus definiciones) o la asignación definida (que exige que todas las variables locales se inicialicen antes de su uso), rechazando programas incorrectos o emitiendo advertencias. El análisis semántico suele requerir un árbol de análisis sintáctico completo, lo que significa que esta fase sigue lógicamente a la fase de análisis sintáctico y precede lógicamente a la fase de generación de código , aunque a menudo es posible combinar varias fases en una sola pasada sobre el código en una implementación del compilador.

Extremo medio

La etapa intermedia, también conocida como optimizador, realiza optimizaciones en la representación intermedia para mejorar el rendimiento y la calidad del código máquina producido. ^{[ 56 ]} La etapa intermedia contiene aquellas optimizaciones que son independientes de la arquitectura de CPU a la que se dirige.

Las fases principales de la etapa intermedia incluyen las siguientes:

• Análisis : Consiste en recopilar información del programa a partir de la representación intermedia derivada de la entrada. El análisis de flujo de datos se utiliza para construir cadenas de definiciones de uso , junto con el análisis de dependencias , el análisis de alias , el análisis de punteros , el análisis de escape , etc. Un análisis preciso es la base de cualquier optimización del compilador. El grafo de flujo de control de cada función compilada y el grafo de llamadas del programa también se suelen construir durante la fase de análisis.
• Optimización : la representación del lenguaje intermedio se transforma en formas funcionalmente equivalentes pero más rápidas (o más pequeñas). Las optimizaciones más comunes son la expansión en línea , la eliminación de código muerto , la propagación de constantes , la transformación de bucles e incluso la paralelización automática .

El análisis del compilador es un requisito previo para cualquier optimización del compilador, y ambos trabajan en estrecha colaboración. Por ejemplo, el análisis de dependencias es crucial para la transformación de bucles .

El alcance del análisis y las optimizaciones del compilador varía considerablemente; puede abarcar desde operaciones dentro de un bloque básico hasta procedimientos completos, o incluso el programa entero. Existe una compensación entre la granularidad de las optimizaciones y el costo de la compilación. Por ejemplo, las optimizaciones de inspección son rápidas durante la compilación, pero solo afectan a un pequeño fragmento local del código y pueden realizarse independientemente del contexto en el que aparece dicho fragmento. En cambio, la optimización interprocedimental requiere más tiempo de compilación y espacio de memoria, pero permite optimizaciones que solo son posibles al considerar el comportamiento de múltiples funciones simultáneamente.

El análisis y la optimización interprocedimental son habituales en los compiladores comerciales modernos de HP , IBM , SGI , Intel , Microsoft y Sun Microsystems . El software libre GCC fue criticado durante mucho tiempo por carecer de potentes optimizaciones interprocedimentales, pero está cambiando en este aspecto. Otro compilador de código abierto con una infraestructura completa de análisis y optimización es Open64 , utilizado por numerosas organizaciones con fines de investigación y comerciales.

Debido al tiempo y espacio adicionales que requiere el análisis y las optimizaciones del compilador, algunos compiladores las omiten por defecto. Los usuarios deben usar las opciones de compilación para indicarle explícitamente al compilador qué optimizaciones debe habilitar.

parte trasera

El back-end es responsable de las optimizaciones específicas de la arquitectura de la CPU y de la generación de código . ^{[ 56 ]}

Las fases principales del back-end incluyen las siguientes:

• Optimizaciones dependientes de la máquina : optimizaciones que dependen de los detalles de la arquitectura de la CPU a la que apunta el compilador. ^{[ 57 ]} Un ejemplo destacado son las optimizaciones de "peephole" , que reescriben secuencias cortas de instrucciones de ensamblador en instrucciones más eficientes.
• Generación de código : el lenguaje intermedio transformado se traduce al lenguaje de salida, generalmente el lenguaje de máquina nativo del sistema. Esto implica decisiones sobre recursos y almacenamiento, como determinar qué variables se asignarán a los registros y la memoria, así como la selección y programación de las instrucciones de máquina adecuadas junto con sus modos de direccionamiento asociados (véase también el algoritmo de Sethi-Ullman ). También puede ser necesario generar datos de depuración para facilitar la depuración .

Los lenguajes de programación de alto nivel suelen aparecer con un tipo de traducción en mente: diseñados como lenguajes compilados o interpretados . Sin embargo, en la práctica, rara vez un lenguaje requiere ser exclusivamente compilado o exclusivamente interpretado, aunque es posible diseñar lenguajes que dependan de la reinterpretación en tiempo de ejecución. La categorización suele reflejar las implementaciones más populares o extendidas de un lenguaje. Por ejemplo, a BASIC a veces se le llama lenguaje interpretado y a C, compilado, a pesar de la existencia de compiladores de BASIC e intérpretes de C. ^{[ 59 ]}

La interpretación no reemplaza la compilación por completo. Simplemente la oculta al usuario y la hace gradual. Si bien un intérprete puede interpretarse a su vez, se necesita un conjunto de instrucciones de máquina ejecutadas directamente en algún punto de la parte inferior de la pila de ejecución (véase lenguaje máquina ).

Además, para optimizar el rendimiento, los compiladores pueden incluir funcionalidades de intérprete, y estos, a su vez, pueden incorporar técnicas de compilación anticipada. Por ejemplo, si una expresión se ejecuta durante la compilación y sus resultados se insertan en el programa de salida, se evita tener que recalcularla cada vez que se ejecuta el programa, lo que puede acelerar considerablemente el resultado final. Las tendencias modernas hacia la compilación justo a tiempo y la interpretación de bytecode a veces difuminan aún más las categorizaciones tradicionales de compiladores e intérpretes. El metatrazado es un método automatizado de síntesis de compiladores que va más allá y permite sintetizar un compilador a partir de un intérprete de lenguaje.

Algunas especificaciones de lenguajes estipulan que las implementaciones deben incluir una función de compilación; por ejemplo, Common Lisp . Sin embargo, no hay nada inherente en la definición de Common Lisp que impida su interpretación. Otros lenguajes tienen características que son muy fáciles de implementar en un intérprete, pero que dificultan mucho la escritura de un compilador; por ejemplo, APL , SNOBOL4 , ^{[ 60 ]} y muchos lenguajes de scripting permiten que los programas construyan código fuente arbitrario en tiempo de ejecución con operaciones de cadena regulares, y luego ejecuten ese código pasándolo a una función de evaluación especial . Para implementar estas características en un lenguaje compilado, los programas generalmente deben distribuirse con una biblioteca de tiempo de ejecución que incluya una versión del propio compilador.

Una clasificación de los compiladores se basa en la plataforma en la que se ejecuta el código que generan. Esto se conoce como plataforma de destino.

Un compilador nativo o alojado es aquel cuyo resultado está diseñado para ejecutarse directamente en el mismo tipo de ordenador y sistema operativo en el que se ejecuta el propio compilador. El resultado de un compilador cruzado está diseñado para ejecutarse en una plataforma diferente. Los compiladores cruzados se utilizan a menudo al desarrollar software para sistemas embebidos que no están diseñados para soportar un entorno de desarrollo de software.

El código generado por un compilador para una máquina virtual (VM) puede o no ejecutarse en la misma plataforma que el compilador que lo produjo. Por este motivo, estos compiladores no suelen clasificarse como compiladores nativos ni cruzados.

El lenguaje de bajo nivel que sirve de destino a un compilador puede ser, a su vez, un lenguaje de programación de alto nivel . C, considerado por algunos como una especie de lenguaje ensamblador portable, suele ser el lenguaje de destino de dichos compiladores. Por ejemplo, Cfront , el compilador original de C++ , utilizaba C como lenguaje de destino. El código C generado por dicho compilador generalmente no está pensado para ser legible ni mantenido por humanos, por lo que se ignoran el estilo de indentación y la creación de código intermedio C legible. Algunas de las características de C que lo convierten en un buen lenguaje de destino incluyen la #linedirectiva, que puede ser generada por el compilador para facilitar la depuración del código fuente original, y la amplia compatibilidad de plataformas que ofrecen los compiladores de C.

Si bien un tipo común de compilador genera código máquina, existen muchos otros tipos:

• Los compiladores de código fuente a código fuente son un tipo de compilador que toma un lenguaje de alto nivel como entrada y produce un código en un lenguaje de alto nivel. Por ejemplo, un compilador de paralelización automática suele tomar como entrada un programa en un lenguaje de alto nivel, transformar el código y anotarlo con anotaciones de código paralelo (p. ej., OpenMP ) o construcciones del lenguaje (p. ej., DOALLlas sentencias de Fortran). Otros términos para un compilador de código fuente a código fuente son transcompilador o transpilador. ^{[ 61 ]}
• Los compiladores de código de bytes compilan a lenguaje ensamblador de una máquina teórica, como algunas implementaciones de Prolog.
  • Esta máquina Prolog también se conoce como la Máquina Abstracta de Warren (o WAM).
  • Los compiladores de código de bytes para Java y Python también son ejemplos de esta categoría.
• Los compiladores Just-In-Time (JIT) posponen la compilación hasta el tiempo de ejecución. Existen compiladores JIT para muchos lenguajes modernos, como Python , JavaScript , Smalltalk , Java , el Lenguaje Intermedio Común (CIL) de .NET (originalmente en Microsoft .NET Framework ) y otros. Un compilador JIT generalmente se ejecuta dentro de un intérprete. Cuando el intérprete detecta que una ruta de código es "caliente", es decir, se ejecuta con frecuencia, el compilador JIT se invoca y compila dicho código para mejorar el rendimiento.
  • Para algunos lenguajes, como Java, las aplicaciones se compilan primero con un compilador de bytecode y se entregan en una representación intermedia independiente de la máquina . Un intérprete de bytecode ejecuta el bytecode, pero el compilador JIT lo traduce a código máquina cuando se requiere un mayor rendimiento. ^{[ 62 ]}
• Los compiladores de hardware (también conocidos como herramientas de síntesis) son compiladores cuya entrada es un lenguaje de descripción de hardware y cuya salida es una descripción, en forma de lista de conexiones o de otro tipo, de una configuración de hardware.
  • La salida de estos compiladores apunta al hardware de la computadora a un nivel muy bajo, por ejemplo, una matriz de puertas programables en campo (FPGA) o un circuito integrado de aplicación específica estructurado (ASIC). ^{[ 63 ]} Se dice que estos compiladores son compiladores de hardware, porque el código fuente que compilan controla efectivamente la configuración final del hardware y cómo funciona. La salida de la compilación es solo una interconexión de transistores o tablas de búsqueda .
  • Un ejemplo de compilador de hardware es XST, la herramienta de síntesis de Xilinx utilizada para configurar FPGAs. ^{[ 64 ]} Herramientas similares están disponibles en Altera, ^{[ 65 ]} Synplicity, Synopsys y otros proveedores de hardware. ^{[ 66 ]}
  • Los sistemas de investigación compilan subconjuntos de lenguajes seriales de alto nivel, como Python o C++, directamente en lógica digital paralelizada. Esto suele ser más fácil de hacer para lenguajes funcionales o subconjuntos funcionales de lenguajes multiparadigma. ^{[ 67 ]}
• Un programa que traduce de un lenguaje de bajo nivel a uno de nivel superior es un descompilador . ^{[ 68 ]}
• Un programa que traduce a un formato de código objeto no compatible con la máquina de compilación se denomina compilador cruzado y se utiliza comúnmente para preparar código para su ejecución en aplicaciones de software embebido. ^{[ 69 ]}
• Un programa que reescribe el código objeto para convertirlo de nuevo en el mismo tipo de código objeto, aplicando optimizaciones y transformaciones, es un recompilador binario .

Los ensambladores, que traducen el lenguaje ensamblador legible por humanos a las instrucciones de código máquina ejecutadas por el hardware, no se consideran compiladores. ^{[ 70 ] [ b ]} (El programa inverso que traduce el código máquina a lenguaje ensamblador se llama desensamblador ).

• Enfoque incremental para la construcción de compiladores : un tutorial en PDF. 
• Conceptos básicos del diseño de compiladores en Wayback Machine (archivado el 15 de mayo de 2018)
• Breve animación en YouTube que explica la diferencia conceptual clave entre compiladores e intérpretes.
• Análisis sintáctico y análisis sintáctico LL1 en YouTube
• Construyamos un compilador , por Jack Crenshaw
• Foro sobre el desarrollo de compiladores en Wayback Machine (archivado el 10 de octubre de 2014)