Compilador

En informática , un compilador es un programa informático que traduce el código informático escrito en un lenguaje de programación (el lenguaje fuente ) a otro lenguaje (el lenguaje destino ). El nombre "compilador" se utiliza principalmente para los programas que traducen el 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 producen resultados en diferentes formas útiles. Un compilador cruzado produce código para una CPU o un sistema operativo diferente de aquel en el que se ejecuta el compilador cruzado. Un compilador de arranque suele ser un compilador temporal, que se utiliza para compilar un compilador más permanente o mejor optimizado para un lenguaje.

El software relacionado incluye descompiladores , programas que traducen desde lenguajes de bajo nivel a lenguajes de nivel superior; programas que traducen entre lenguajes de alto nivel, usualmente llamados compiladores de fuente a fuente o transpiladores ; reescritores de lenguaje , usualmente programas que traducen la forma de expresiones sin un cambio de lenguaje; y compiladores-compiladores , compiladores que producen compiladores (o partes de ellos), a menudo de una manera genérica y reutilizable para poder producir muchos compiladores diferentes.

Es probable que un compilador realice algunas o todas las siguientes operaciones, a menudo llamadas fases: preprocesamiento , análisis léxico , análisis sintáctico , análisis semántico ( traducción dirigida por 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 el diseño eficiente y la corrección de las transformaciones de la entrada de origen a la salida de destino. Los fallos del programa causados ​​por un comportamiento incorrecto del compilador pueden ser muy difíciles de rastrear y solucionar; por lo tanto, los implementadores de compiladores invierten un esfuerzo significativo para garantizar la corrección del compilador . ^[4]

Los compiladores no son el único procesador de lenguaje utilizado para transformar programas fuente. Un intérprete es un software informático que transforma y luego ejecuta las operaciones indicadas. ^{[2] : p2} El proceso de traducción influye en el diseño de los lenguajes informáticos, lo que lleva a una preferencia de compilación o interpretación. En teoría, un lenguaje de programación puede tener tanto un compilador como un intérprete. En la práctica, los lenguajes de programación tienden a estar asociados con solo uno (un compilador o un intérprete).

Los conceptos teóricos de computación desarrollados por científicos, matemáticos e ingenieros formaron la base 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 fines de la década de 1940, se crearon lenguajes ensambladores para ofrecer una abstracción más viable de las arquitecturas de las computadoras. ^{[5] La capacidad} de memoria limitada de las primeras computadoras generó desafíos técnicos sustanciales cuando se diseñaron los primeros compiladores. Por lo tanto, el proceso de compilación necesitaba dividirse en varios programas pequeños. Los programas front-end producen los productos de análisis utilizados por los programas back-end para generar el código de destino. 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, resulta más productivo para un programador utilizar un lenguaje de alto nivel, por lo que el desarrollo de lenguajes de alto nivel surgió de manera 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 , que forman la arquitectura del lenguaje de alto nivel. Los elementos de estos lenguajes formales incluyen:

• Alfabeto , cualquier conjunto finito de símbolos;
• Cadena , una secuencia finita de símbolos;
• Idioma , cualquier conjunto de cadenas de un alfabeto.

Las oraciones de un idioma pueden definirse mediante un conjunto de reglas llamadas 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] "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 (algorítmico) para computadoras llamado Plankalkül ("Cálculo de planos"). Zuse también imaginó un Planfertigungsgerät ("Dispositivo de ensamblaje de planos") para traducir automáticamente la formulación matemática de un programa en una película perforada legible por máquina . ^[10] Si bien no se produjo una implementación real hasta la década de 1970, presentó conceptos que luego se vieron en APL diseñado por Ken Iverson a fines 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 refinadas posteriormente por Friedrich L. Bauer y Klaus Samelson . ^[13]

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

• FORTRAN (Formula Translation) para aplicaciones científicas y de ingeniería se considera uno de los primeros lenguajes de alto nivel implementados y el primer compilador optimizador. ^{[14] [ se necesita una fuente de terceros ]}
• COBOL (Lenguaje común orientado a los negocios) evolucionó a partir de A-0 y FLOW-MATIC para convertirse en el lenguaje de alto nivel dominante para aplicaciones comerciales. ^[15]
• LISP (Procesador de listas) para cálculo simbólico. ^[16]

La tecnología de compiladores surgió de la necesidad de una transformación estrictamente definida del programa fuente de alto nivel en un programa de destino de bajo nivel para la computadora digital. El compilador podría considerarse como una interfaz para analizar el código fuente y una interfaz de usuario para sintetizar el análisis en el código de destino. La optimización entre la interfaz de usuario y la interfaz de usuario podría producir un código de destino más eficiente. ^[17]

Algunos hitos tempranos 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 la noción moderna de un compilador completo. ^{[21] [22] [23]}
• 1952, antes de septiembre : Un compilador Autocode desarrollado por Alick Glennie para la computadora Manchester Mark I de la Universidad de Manchester es considerado por algunos como el primer lenguaje de programación compilado. ^[24]
• 1954–1957 : Un equipo dirigido por John Backus en IBM desarrolló FORTRAN , que suele considerarse el primer lenguaje de alto nivel. En 1957, completaron un compilador de FORTRAN al que generalmente se le atribuye haber introducido el primer compilador inequívocamente completo. ^[25]
• 1959 : La Conferencia sobre lenguaje de sistemas de datos (CODASYL) inició el 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 compiló en múltiples arquitecturas.
• 1958–1960 : Algol 58 fue el precursor de ALGOL 60. Introdujo 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 alcance léxico . Incluía recursión . Su sintaxis se definió utilizando BNF . ALGOL 60 inspiró a muchos lenguajes que lo siguieron. 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 diseñó LISP en el MIT . ^[28] Las capacidades de procesamiento de símbolos proporcionaron características útiles para la investigación de 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, un compilador y ensamblador escrito por Tim Hart y Mike Levin. ^[29]

Los primeros sistemas operativos y software se escribieron en lenguaje ensamblador. En la década de 1960 y principios de la de 1970, el uso de lenguajes de alto nivel para la programación de sistemas todavía era controvertido debido a las limitaciones de recursos. Sin embargo, varias investigaciones y esfuerzos de la industria iniciaron el cambio hacia lenguajes de programación de sistemas de alto nivel, por ejemplo , BCPL , BLISS , B y C.

BCPL (Basic Combined Programming Language) diseñado en 1966 por Martin Richards en la Universidad de Cambridge fue desarrollado originalmente como una herramienta de escritura de compiladores. ^[30] Se han implementado varios compiladores, el libro de Richards proporciona información sobre el lenguaje y su compilador. ^[31] BCPL no solo fue un lenguaje de programación de sistemas influyente que todavía se usa en la investigación ^[32] sino que también proporcionó una base para el diseño de los lenguajes B y C.

BLISS (Basic Language for Implementation of System Software) fue desarrollado para una computadora PDP-10 de Digital Equipment Corporation (DEC) por el equipo de investigación de la Universidad Carnegie Mellon (CMU) de WA Wulf. El equipo de la CMU desarrolló el compilador BLISS-11 un año después, en 1970.

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 dirigido 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 empresarial, científica y de sistemas. Había otros lenguajes que podrían haberse considerado, pero PL/I ofrecía la solución más completa a pesar de que no se había implementado. ^[35] Durante los primeros años del proyecto Multics, un subconjunto del lenguaje podía compilarse en lenguaje ensamblador con el compilador Early PL/I (EPL) de Doug McIlory y Bob Morris de Bell Labs. ^[36] EPL apoyó el proyecto hasta que se pudo desarrollar un compilador de arranque para el 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 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 se deletreó Unix.

Bell Labs comenzó 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 front-end para el compilador B de Bell Labs mientras se desarrollaba un compilador C. En 1971, un nuevo PDP-11 proporcionó el recurso para definir extensiones a B y reescribir el compilador. En 1973, el diseño del lenguaje C estaba esencialmente completo y el núcleo Unix para un PDP-11 se reescribió en C. Steve Johnson comenzó el desarrollo de Portable C Compiler (PCC) para soportar la reorientación de los compiladores C a nuevas máquinas. ^{[39] [40]}

La programación orientada a objetos (POO) ofrecía algunas posibilidades interesantes para el desarrollo y mantenimiento de aplicaciones. Los conceptos de POO se remontan a tiempos más antiguos, 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 funciones orientadas a objetos se añadieron en 1983. ^[43] El programa Cfront implementó una interfaz 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 nivel superior se impuso rápidamente. Debido a la creciente funcionalidad admitida por los lenguajes de programación más nuevos y a la creciente complejidad de las arquitecturas informáticas, los compiladores se volvieron más complejos.

En 1970, la DARPA (Defense Advanced Research Projects Agency) patrocinó un proyecto de compilador con el equipo de investigación de la CMU de Wulf. El diseño del compilador de calidad de producción-compilador 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 como generador de analizadores sintácticos (por ejemplo, Yacc ) sin mucho éxito. Sería más apropiado hacer referencia a PQCC como un generador de compiladores.

La investigación de PQCC sobre el proceso de generación de código buscó 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 incluyeron análisis (front end), traducción intermedia a máquina virtual (middle end) y traducción al destino (back end). TCOL fue desarrollado para la investigación de PQCC para manejar construcciones específicas del lenguaje en la representación intermedia. ^[46] Las variaciones de TCOL soportaron varios lenguajes. El proyecto PQCC investigó técnicas de construcción automatizada de compiladores. Los conceptos de diseño demostraron ser útiles para optimizar compiladores y compiladores para el lenguaje de programación (desde 1995, orientado a objetos) Ada .

El documento STONEMAN de Ada ^[a] formalizó el entorno de soporte de programas (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 Estándares (ISO). El desarrollo inicial del compilador de Ada por parte de los Servicios Militares de los EE. UU. incluyó los compiladores en un entorno de diseño integrado completo en línea con el documento STONEMAN . El Ejército y la Marina trabajaron en el proyecto Ada Language System (ALS) orientado a la arquitectura DEC/VAX mientras que la Fuerza Aérea comenzó con el Ada Integrated Environment (AIE) orientado 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 proyectos de compilación de Ada se pusieron en marcha en Gran Bretaña, en la Universidad de York, y en Alemania, en la Universidad de Karlsruhe. En los EE. UU., Verdix (posteriormente adquirida por Rational) entregó el Verdix Ada Development System (VADS) al Ejército. VADS proporcionó un conjunto de herramientas de desarrollo que incluía un compilador. Unix/VADS podía alojarse en una variedad de plataformas Unix, como DEC Ultrix y Sun 3/60 Solaris, destinado a Motorola 68020 en una evaluación 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 GNU Compiler Collection (GCC), que proporciona una capacidad básica para soportar 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 siguieron 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. Se incluyeron más compiladores en distribuciones de lenguajes (PERL, Java Development Kit) y como un componente de un IDE (VADS, Eclipse, Ada Pro). La interrelación e interdependencia de las tecnologías aumentó. La llegada de los servicios web promovió el crecimiento de los lenguajes web y los lenguajes de script. Los scripts se remontan a los primeros días de las interfaces de línea de comandos (CLI), donde el usuario podía ingresar comandos para que los ejecutara el sistema. Los conceptos de User Shell se desarrollaron con lenguajes para escribir programas de shell. Los primeros diseños de Windows ofrecían una capacidad de programación por lotes simple. La transformación convencional de estos lenguajes usaba un intérprete. Si bien no se usan ampliamente, se han escrito compiladores Bash y Batch. Más recientemente, los lenguajes interpretados sofisticados se convirtieron en parte del kit de herramientas de los desarrolladores. Los lenguajes de script modernos incluyen PHP, Python, Ruby y Lua. (Lua se usa ampliamente en el desarrollo de juegos). Todos ellos tienen soporte de intérprete y compilador. ^[49]

"Cuando el campo de la compilación comenzó a fines de los años 50, su enfoque se limitaba a la traducción de programas de lenguaje de alto nivel a código de máquina... El campo de los compiladores está cada vez más entrelazado con otras disciplinas, incluidas la arquitectura informática, los lenguajes de programación, los métodos formales, la ingeniería de software y la seguridad informática". ^[50] El artículo "Compiler Research: The Next 50 Years" destacó la importancia de los lenguajes orientados a objetos y Java. La seguridad y la computación paralela se mencionaron entre los futuros objetivos de investigación.

This section includes a list of general references, but it lacks sufficient corresponding inline citations. Please help to improve this section by introducing more precise citations. (December 2019) (Learn how and when to remove this message)

Un compilador implementa una transformación formal de un programa fuente de alto nivel a un programa de destino de bajo nivel. El diseño del compilador puede definir una solución de extremo a extremo o abordar un subconjunto definido que interactúa con otras herramientas de compilación, por ejemplo, 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 apoyo.

En los primeros tiempos, el enfoque adoptado para el diseño de compiladores se veía afectado directamente por la complejidad del lenguaje informático que se iba a procesar, la experiencia de la(s) persona(s) que lo diseñaban y los recursos disponibles. Las limitaciones de recursos llevaron a la necesidad de revisar el código fuente más de una vez.

Un compilador para un lenguaje relativamente simple escrito por una sola persona puede ser una pieza de software única y monolítica. Sin embargo, a medida que el lenguaje fuente se vuelve más complejo, el diseño puede dividirse en varias fases interdependientes. Las fases separadas proporcionan mejoras de diseño que centran el desarrollo en las funciones del proceso de compilación.

La clasificación de los compiladores por número de pasadas tiene su origen en las limitaciones de recursos de hardware de las computadoras. La compilación implica realizar mucho trabajo y las primeras computadoras no tenían suficiente memoria para contener un programa que hiciera todo este trabajo. Como resultado, los compiladores se dividieron en programas más pequeños que realizaban cada uno una pasada sobre el código fuente (o alguna representación del mismo) y realizaban parte del análisis y las traducciones necesarias.

La capacidad de compilar en una sola pasada se ha considerado clásicamente como una ventaja porque simplifica el trabajo de escribir un compilador y los compiladores de una sola pasada generalmente realizan compilaciones más rápido que los compiladores de múltiples pasadas . Por lo tanto, en parte debido a las limitaciones de recursos de los primeros sistemas, muchos de los primeros lenguajes se diseñaron específicamente para que pudieran compilarse en una sola pasada (por ejemplo, Pascal ).

En algunos casos, el diseño de una característica del lenguaje puede requerir que un compilador realice más de una pasada sobre el código fuente. Por ejemplo, considere una declaración que aparece en la línea 20 del código fuente que afecta la traducción de una declaración que aparece en la línea 10. En este caso, la primera pasada debe recopilar información sobre las declaraciones que aparecen después de las declaraciones a las que afectan, y la traducción real se realiza durante una pasada posterior.

La desventaja de compilar en una sola pasada es que no es posible realizar muchas de las optimizaciones sofisticadas necesarias para generar código de alta calidad. Puede resultar difícil contar exactamente cuántas pasadas realiza un compilador optimizador. Por ejemplo, las diferentes fases de optimización pueden analizar una expresión muchas veces, pero solo analizar otra expresión una vez.

Dividir un compilador en programas pequeños es una técnica que utilizan los investigadores interesados ​​en producir compiladores demostrablemente correctos. Demostrar la corrección de un conjunto de programas pequeños suele requerir menos esfuerzo que demostrar la corrección de un programa más grande, único y equivalente.

Independientemente del número exacto de fases en el diseño del compilador, las fases se pueden asignar a una de tres etapas. Las etapas incluyen una etapa inicial, una etapa intermedia y una etapa final.

• El front-end escanea la entrada y verifica la sintaxis y la semántica de acuerdo con un lenguaje fuente específico. Para lenguajes tipados estáticamente, realiza la verificación de tipos mediante la recopilación de 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 real puede estar (mucho) antes en el programa. Los aspectos del front-end incluyen 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 (IR) para su posterior procesamiento por el middle-end. Esta IR suele ser una representación de nivel inferior del programa con respecto al código fuente.
• El extremo intermedio realiza optimizaciones en el IR que son independientes de la arquitectura de CPU a la que se dirige. Esta independencia del código fuente/código de máquina tiene como objetivo permitir que se compartan optimizaciones genéricas entre versiones del compilador que admiten diferentes lenguajes y procesadores de destino. Algunos ejemplos de optimizaciones del extremo intermedio son la eliminación de código inútil ( eliminación de código muerto ) o inalcanzable ( análisis de accesibilidad ), el descubrimiento y la propagación de valores constantes ( propagación constante ), la reubicación del cálculo a un lugar que se ejecuta con menos frecuencia (por ejemplo, fuera de un bucle) o la especialización del cálculo en función del contexto, lo que finalmente produce el IR "optimizado" que utiliza el extremo posterior.
• El back end toma el IR optimizado del middle end. Puede realizar más análisis, transformaciones y optimizaciones que son específicas para la arquitectura de 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 programación de instrucciones , que reordena las instrucciones para mantener ocupadas las unidades de ejecución paralela llenando las ranuras de retardo . Aunque la mayoría de los problemas de optimización son NP-hard , 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 un código de máquina especializado para un procesador y un sistema operativo en particular.

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

El front-end analiza el código fuente para crear una representación interna del programa, denominada representación intermedia (IR). También administra la tabla de símbolos , una estructura de datos que asigna cada símbolo del código fuente a información asociada, como ubicación, tipo y alcance.

Si bien el frontend puede ser una única función o programa monolítico, como en un analizador sin escáner , tradicionalmente se implementaba y analizaba como varias fases, que pueden ejecutarse secuencial o simultáneamente. Este método es el preferido debido a su modularidad y separación de preocupaciones . Lo más común es que el frontend se divida en tres fases: análisis léxico (también conocido como lexing o escaneo), análisis sintáctico (también conocido como escaneo 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 simples, estos módulos (el analizador léxico y el parser) se pueden generar automáticamente a partir de una gramática para el lenguaje, aunque en casos más complejos requieren una 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 es generalmente más compleja y se escribe a mano, pero puede automatizarse parcial o totalmente mediante gramáticas de atributos . Estas fases se pueden dividir en: análisis léxico, como escaneo y evaluación, y análisis sintáctico, como construcción de un árbol de sintaxis concreto (CST, parse tree) y luego transformación en un árbol de sintaxis abstracto (AST, syntax tree). En algunos casos se utilizan fases adicionales, en particular reconstrucción de líneas y preprocesamiento, pero son poco frecuentes.

Las fases principales del frontend 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. Los lenguajes queeliminansus palabras clave o permiten espacios arbitrarios dentro de los identificadores requieren esta fase. Losde arriba hacia abajo,de descenso recursivoy controlados por tablas que se usaban en la década de 1960 normalmente leían la fuente un carácter a la vez y no requerían una fase de tokenización separada.Atlas AutocodeeImp(y algunas implementaciones deALGOLyCoral 66) son ejemplos de lenguajes eliminados cuyos compiladores tendrí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 produce antes del análisis sintáctico o semántico; por ejemplo, en el caso de C, el preprocesador manipula tokens léxicos en lugar de 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ños fragmentos llamados 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 token comunes pueden incluir identificadores, palabras clave, separadores, operadores, literales y comentarios, aunque el conjunto de categorías de token varía en diferentes lenguajes de programación . La sintaxis del lexema es típicamente un lenguaje regular , por lo que se puede usar 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 . Este puede no ser un paso separado: se puede combinar con el paso de análisis 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 análisis sintáctico ) implica analizar la secuencia de tokens para identificar la estructura sintáctica del programa. Esta fase generalmente construye un árbol de análisis sintáctico , que reemplaza la secuencia lineal de tokens con una estructura de árbol construida de acuerdo con las reglas de una gramática formal que define la sintaxis del lenguaje. El árbol de análisis sintáctico a menudo se analiza, aumenta y transforma en fases posteriores del compilador. ^[55]
• El análisis semántico añade información semántica al árbol de análisis y construye la tabla de símbolos . Esta fase realiza comprobaciones semánticas como la comprobación de tipos (comprobación de errores de tipo), la vinculación de objetos (asociación de referencias de variables y funciones con sus definiciones), o la asignación definitiva (requerimiento de que todas las variables locales se inicialicen antes de su uso), el rechazo de programas incorrectos o la emisión de advertencias. El análisis semántico normalmente requiere un árbol de análisis completo, lo que significa que esta fase sigue lógicamente a la fase de análisis y precede lógicamente a la fase de generación de código , aunque a menudo es posible incorporar varias fases en una sola pasada sobre el código en una implementación del compilador.

El extremo medio, también conocido como optimizador, realiza optimizaciones en la representación intermedia para mejorar el rendimiento y la calidad del código de máquina producido. ^[56] El extremo medio contiene aquellas optimizaciones que son independientes de la arquitectura de CPU a la que se apunta.

Las fases principales del final medio incluyen las siguientes:

• Análisis : es la recopilación de información del programa a partir de la representación intermedia derivada de la entrada; el análisis del flujo de datos se utiliza para construir cadenas de definición de uso , junto con el análisis de dependencia , el análisis de alias , el análisis de punteros , el análisis de escape , etc. El análisis preciso es la base para cualquier optimización del compilador. El gráfico de flujo de control de cada función compilada y el gráfico de llamadas del programa también se construyen normalmente durante la fase de análisis.
• Optimización : la representación intermedia del lenguaje se transforma en formas funcionalmente equivalentes pero más rápidas (o más pequeñas). Las optimizaciones populares son la expansión en línea , la eliminación de código muerto , la propagación constante , 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 dependencia es crucial para la transformación de bucles .

El alcance del análisis y las optimizaciones del compilador varía enormemente; su alcance puede ir desde operar dentro de un bloque básico , hasta procedimientos completos o incluso el programa completo. Existe un equilibrio entre la granularidad de las optimizaciones y el costo de la compilación. Por ejemplo, las optimizaciones de mirilla se realizan rápidamente durante la compilación, pero solo afectan a un pequeño fragmento local del código y se pueden realizar independientemente del contexto en el que aparece el fragmento de código. Por el contrario, la optimización interprocedimental requiere más tiempo de compilación y espacio de memoria, pero permite optimizaciones que solo son posibles considerando el comportamiento de múltiples funciones simultáneamente.

El análisis y las optimizaciones interprocedimentales son comunes 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 optimizaciones interprocedimentales potentes, pero está cambiando en este sentido. Otro compilador de código abierto con una infraestructura completa de análisis y optimización es Open64 , que es utilizado por muchas organizaciones con fines comerciales y de investigación.

Debido al tiempo y espacio adicionales necesarios para el análisis y las optimizaciones del compilador, algunos compiladores las omiten de forma predeterminada. Los usuarios deben usar opciones de compilación para indicarle explícitamente al compilador qué optimizaciones deben habilitarse.

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 principales fases 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 mirilla , que reescriben secuencias cortas de instrucciones del ensamblador en instrucciones más eficientes.
• Generación de código : el lenguaje intermedio transformado se traduce al lenguaje de salida, normalmente el lenguaje de máquina nativo del sistema. Esto implica decisiones sobre recursos y almacenamiento, como decidir qué variables encajar en los registros y la memoria y la selección y programación de 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 .

La corrección del compilador es la rama de la ingeniería de software que trata de intentar demostrar que un compilador se comporta de acuerdo con su especificación de lenguaje . ^[58] Las técnicas incluyen el desarrollo del compilador utilizando métodos formales y el uso de pruebas rigurosas (a menudo llamadas validación del compilador) en un compilador existente.

This section does not cite any sources. Please help improve this section by adding citations to reliable sources. Unsourced material may be challenged and removed. (October 2018) (Learn how and when to remove this message)

Los lenguajes de programación de alto nivel suelen aparecer con un tipo de traducción en mente: ya sea diseñados como lenguaje compilado o lenguaje interpretado . Sin embargo, en la práctica rara vez hay algo en un lenguaje que requiera que sea 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 generalmente refleja las implementaciones más populares o extendidas de un lenguaje; por ejemplo, a veces se dice que BASIC es un lenguaje interpretado y que C es un lenguaje compilado, a pesar de la existencia de compiladores BASIC e intérpretes C.

La interpretación no reemplaza por completo la compilación. Solo la oculta al usuario y la hace gradual. Aunque un intérprete puede ser interpretado por sí mismo, se necesita un conjunto de instrucciones de máquina ejecutadas directamente en algún lugar en la parte inferior de la pila de ejecución (ver lenguaje de máquina ).

Además, para optimizar los compiladores pueden incluir funciones de interpretación, y los intérpretes pueden incluir técnicas de compilación anticipada. Por ejemplo, cuando una expresión se puede ejecutar durante la compilación y los resultados se insertan en el programa de salida, se evita que tenga que volver a calcularse cada vez que se ejecuta el programa, lo que puede acelerar enormemente el programa final. Las tendencias modernas hacia la compilación en tiempo real y la interpretación de bytecode a veces difuminan aún más las categorizaciones tradicionales de compiladores e intérpretes.

Algunas especificaciones de lenguajes establecen 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 que se interprete. Otros lenguajes tienen características que son muy fáciles de implementar en un intérprete, pero que hacen que escribir un compilador sea mucho más difícil; por ejemplo, APL , SNOBOL4 y muchos lenguajes de scripts 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 enviarse con una biblioteca de tiempo de ejecución que incluya una versión del compilador en sí.

Una clasificación de los compiladores es según la plataforma en la que se ejecuta el código generado, conocida como plataforma de destino.

Un compilador nativo o alojado es aquel cuya salida está destinada a ejecutarse directamente en el mismo tipo de computadora y sistema operativo en el que se ejecuta el compilador. La salida de un compilador cruzado está diseñada para ejecutarse en una plataforma diferente. Los compiladores cruzados se utilizan a menudo al desarrollar software para sistemas integrados que no están destinados a admitir un entorno de desarrollo de software.

La salida de un compilador que produce código para una máquina virtual (VM) puede o no ejecutarse en la misma plataforma que el compilador que lo produjo. Por este motivo, dichos compiladores no suelen clasificarse como compiladores nativos o cruzados.

El lenguaje de nivel inferior que es el objetivo de un compilador puede ser en sí mismo un lenguaje de programación de alto nivel . C, visto por algunos como una especie de lenguaje ensamblador portable, es con frecuencia el lenguaje de destino de tales compiladores. Por ejemplo, Cfront , el compilador original de C++ , utilizó C como su lenguaje de destino. El código C generado por un compilador de este tipo normalmente no está destinado a ser legible y mantenido por humanos, por lo que se ignoran el estilo de sangría y la creación de código intermedio C bonito. 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 admitir la depuración de la fuente original, y el amplio soporte de plataformas disponible con los compiladores de C.

Si bien un tipo de compilador común genera código de 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 genera un lenguaje de alto nivel como salida. Por ejemplo, un compilador de paralelización automática con frecuencia tomará un programa de lenguaje de alto nivel como entrada y luego transformará el código y lo anotará con anotaciones de código paralelo (por ejemplo, OpenMP ) o construcciones de lenguaje (por ejemplo, declaraciones de Fortran DOALL). Otros términos para un compilador de código fuente a código fuente son transcompilador o transpilador. ^[59]
• Los compiladores de bytecode compilan en lenguaje ensamblador de una máquina teórica, como algunas implementaciones de Prolog.
  • Esta máquina Prolog también se conoce como Máquina Abstracta Warren (o WAM).
  • Los compiladores de bytecode para Java y Python también son ejemplos de esta categoría.
• Los compiladores Just-in-time (compiladores JIT) posponen la compilación hasta el momento de ejecución. Existen compiladores JIT para muchos lenguajes modernos, incluidos Python , JavaScript , Smalltalk , Java , el lenguaje intermedio común (CIL) de Microsoft .NET y otros. Un compilador JIT generalmente se ejecuta dentro de un intérprete. Cuando el intérprete detecta que una ruta de código está "activa", lo que significa que se ejecuta con frecuencia, se invocará el compilador JIT y compilará el código "activo" para aumentar el rendimiento.
  • En el caso de algunos lenguajes, como Java, las aplicaciones se compilan primero mediante 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 traducirá el bytecode a código de máquina cuando sea necesario aumentar el rendimiento. ^{[60] [ Se necesita una fuente no primaria ]}
• 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 redes o de otro modo, 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 estructurado de aplicación específica (ASIC). ^{[61] [ fuente no primaria necesaria ]} 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 opera. 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. ^{[62] [ se necesita una fuente no primaria ]} Hay herramientas similares disponibles de Altera, ^{[63] [ se necesita una fuente no primaria ]} Synplicity, Synopsys y otros proveedores de hardware. ^{[ cita requerida ]}
• Un programa que traduce de un lenguaje de bajo nivel a uno de nivel superior es un descompilador . ^[64]
• Un programa que traduce a un formato de código objeto que no es 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 integradas. ^{[65] [ se necesita una mejor fuente ]}
• Un programa que reescribe el código objeto en el mismo tipo de código objeto mientras aplica optimizaciones y transformaciones es un recompilador binario .

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

Busque compilador en Wikcionario, el diccionario libre.

Wikilibros tiene un libro sobre el tema: Construcción de compiladores

Wikimedia Commons tiene medios relacionados con Compiladores .

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