Además de un traductor, se pueden necesitar otros programas para crear un programa objeto ejecutable. Un programa fuente se puede dividir en módulos almacenados en archivos distintos. La tarea de reunir el programa fuente a menudo se confía a un programa distinto, llamado preprocesador. El preprocesador también puede expandir abreviaturas, llamadas a macros, a proposiciones del lenguaje fuente.

Contenido 1 Etapas del proceso 1.1 Fase de análisis 1.1.1 Análisis léxico 1.1.2 Análisis sintáctico 1.1.3 Análisis semántico 1.2 Fase de síntesis 1.2.1 Generación de código intermedio 1.2.2 Optimización de código 2 Estructura de datos principales 2.1 Componentes léxicos o tokens 2.2 Árbol sintáctico 2.3 Tabla de símbolos 2.4 Tabla de literales 2.5 Código intermedio 2.6 Archivos temporales 3 Véase también

Etapas del proceso

El proceso de traducción se compone internamente de varias etapas o fases, que realizan distintas operaciones lógicas. Es útil pensar en estas fases como en piezas separadas dentro del traductor, y pueden en realidad escribirse como operaciones codificadas separadamente aunque en la práctica a menudo se integren juntas.

Fase de análisis

Análisis léxico

El análisis léxico constituye la primera fase, aquí se lee el programa fuente de izquierda a derecha y se agrupa en componentes léxicos (tokens), que son secuencias de caracteres que tienen un significado. Además, todos los espacios en blanco, líneas en blanco, comentarios y demás información innecesaria se elimina del programa fuente. También se comprueba que los símbolos del lenguaje (palabras clave, operadores,...) se han escrito correctamente.

Como la tarea que realiza el analizador léxico es un caso especial de coincidencia de patrones, se necesitan los métodos de especificación y reconocimiento de patrones, y éstos métodos son principalmente las expresiones regulares y los autómatas finitos. Sin embargo, un analizador léxico también es la parte del traductor que maneja la entrada del código fuente, y puesto que esta entrada a menudo involucra un importante gasto de tiempo, el analizador léxico debe funcionar de manera tan eficiente como sea posible.

Análisis sintáctico

En esta fase los caracteres o componentes léxicos se agrupan jerárquicamente en frases gramaticales que el compilador utiliza para sintetizar la salida. Se comprueba si lo obtenido de la fase anterior es sintácticamente correcto (obedece a la gramática del lenguaje). Por lo general, las frases gramaticales del programa fuente se representan mediante un árbol de análisis sintáctico.

La estructura jerárquica de un programa normalmente se expresa utilizando reglas recursivas. Por ejemplo, se pueden dar las siguientes reglas como parte de la definición de expresiones:

1. Cualquier identificador es una expresión.
2. Cualquier número es una expresión.
3. Si expresión₁ y expresión₂ son expresiones, entonces también lo son:
   • expresión₁ + expresión₂
   • expresión₁ * expresión₂
   • ( expresión₁ )

Las reglas 1 y 2 son reglas básicas (no recursivas), en tanto que la regla 3 define expresiones en función de operadores aplicados a otras expresiones.

La división entre análisis léxico y análisis sintáctico es algo arbitraria. Un factor para determinar la división es si una construcción del lenguaje fuente es inherentemente recursiva o no. Las construcciones léxicas no requieren recursión, mientras que las construcciones sintácticas suelen requerirla. No se requiere recursión para reconocer los identificadores, que suelen ser cadenas de letras y dígitos que comienzan con una letra. Normalmente, se reconocen los identificadores por el simple examen del flujo de entrada, esperando hasta encontrar un carácter que no sea ni letra ni dígito, y agrupando después todas las letras y dígitos encontrados hasta ese punto en un componente léxico llamado identificador. Por otra parte, esta clase de análisis no es suficientemente poderoso para analizar expresiones o proposiciones. Por ejemplo, no podemos emparejar de manera apropiada los paréntesis de las expresiones, o las palabras begin y end en proposiciones sin imponer alguna clase de estructura jerárquica o de anidamiento a la entrada.

Análisis semántico

La fase de análisis semántico revisa el programa fuente para tratar de encontrar errores semánticos y reúne la información sobre los tipos para la fase posterior de generación de código. En ella se utiliza la estructura jerárquica determinada por la fase de análisis sintáctico para identificar los operadores y operandos de expresiones y proposiciones.

Un componente importante del análisis semántico es la verificación de tipos. Aquí, el compilador verifica si cada operador tiene operandos permitidos por la especificación del lenguaje fuente. Por ejemplo, las definiciones de muchos lenguajes de programación requieren que el compilador indique un error cada vez que se use un número real como índice de una matriz. Sin embargo, la especificación del lenguaje puede imponer restricciones a los operandos, por ejemplo, cuando un operador aritmético binario se aplica a un número entero y a un número real.

Fase de síntesis

Consiste en generar el código objeto equivalente al programa fuente. Sólo se genera código objeto cuando el programa fuente está libre de errores de análisis, lo cual no quiere decir que el programa se ejecute correctamente, ya que un programa puede tener errores de concepto o expresiones mal calculadas. Por lo general el código objeto es código de máquina relocalizable o código ensamblador. Las posiciones de memoria se seleccionan para cada una de las variables usadas por el programa. Después, cada una de las instrucciones intermedias se traduce a una secuencia de instrucciones de máquina que ejecuta la misma tarea. Un aspecto decisivo es la asignación de variables a registros.

Generación de código intermedio

Después de los análisis sintáctico y semántico, algunos compiladores generan una representación intermedia explícita del programa fuente. Se puede considerar esta representación intermedia como un programa para una máquina abstracta. Esta representación intermedia debe tener dos propiedades importantes; debe ser fácil de producir y fácil de traducir al programa objeto.

La representación intermedia puede tener diversas formas. Existe una forma intermedia llamada "código de tres direcciones" que es como el lenguaje ensamblador de una máquina en la que cada posición de memoria puede actuar como un registro. El código de tres direcciones consiste en una secuencia de instrucciones, cada una de las cuales tiene como máximo tres operandos. Esta representación intermedia tiene varias propiedades:

• Primera.- Cada instrucción de tres direcciones tiene a lo sumo un operador, además de la asignación, por tanto, cuando se generan estas instrucciones, el traductor tiene que decidir el orden en que deben efectuarse las operaciones.
• Segunda.- El traductor debe generar un nombre temporal para guardar los valores calculados por cada instrucción.
• Tercera.- Algunas instrucciones de "tres direcciones" tienen menos de tres operandos, por ejemplo, la asignación.

Optimización de código

La fase de optimización de código consiste en mejorar el código intermedio, de modo que resulte un código máquina más rápido de ejecutar. Esta fase de la etapa de síntesis es posible sobre todo si el traductor es un compilador (difícilmente un interprete puede optimizar el código objeto). Hay mucha variación en la cantidad de optimización de código que ejecutan los distintos compiladores. En los que hacen mucha optimización, llamados "compiladores optimizadores", una parte significativa del tiempo del compilador se ocupa en esta fase. Sin embargo, hay optimizaciones sencillas que mejoran sensiblemente el tiempo de ejecución del programa objeto sin retardar demasiado la compilación.

Estructura de datos principales

La interacción entre los algoritmos utilizados por las fases del compilador y las estructuras de datos que soportan estas fases es, naturalmente, muy fuerte. El escritor del compilador se esfuerza por implementar estos algoritmos de una manera tan eficaz como sea posible, sin aumentar demasiado la complejidad. De manera ideal, un compilador debería poder compilar un programa en un tiempo proporcional al tamaño del mismo.

Componentes léxicos o tokens

Cuando un analizador léxico reúne los caracteres en un token, generalmente representa el token de manera simbólica, es decir, como un valor de un tipo de datos enumerado que representa el conjunto de tokens del lenguaje fuente. En ocasiones también es necesario mantener la cadena de caracteres misma u otra información derivada de ella, tal como el nombre asociado con un token identificador o el valor de un token de número.

En la mayoría de los lenguajes el analizador léxico sólo necesita generar un token a la vez. En este caso se puede utilizar una variable global simple para mantener la información del token. En otros casos (cuyo ejemplo más notable es FORTRAN), puede ser necesario un arreglo (o vector) de tokens.

Árbol sintáctico

Si el analizador sintáctico genera un árbol sintáctico, por lo regular se construye como una estructura estándar basada en un puntero que se asigna de manera dinámica a medida que se efectúa el análisis sintáctico. El árbol entero puede entonces conservarse como una variable simple que apunta al nodo raíz. Cada nodo en la estructura es un registro cuyos campos representan la información recolectada tanto por el analizador sintáctico como, posteriormente, por el analizador semántico. Por ejemplo, el tipo de datos de una expresión puede conservarse como un campo en el nodo del árbol sintáctico para la expresión.

En ocasiones, para ahorrar espacio, estos campos se asignan de manera dinámica, o se almacenan en otras estructuras de datos, tales como la tabla de símbolos, que permiten una asignación y desasignación selectivas. En realidad, cada nodo del árbol sintáctico por sí mismo puede requerir de atributos diferentes para ser almacenado, de acuerdo con la clase de estructura del lenguaje que represente. En este caso, cada nodo en el árbol sintáctico puede estar representado por un registro variable, con cada clase de nodo conteniendo solamente la información necesaria para ese caso.

Tabla de símbolos

Esta estructura de datos mantiene la información asociada con los identificadores: funciones, variables, constantes y tipos de datos. La tabla de símbolos interactúa con casi todas las fases del compilador: el analizador léxico, el analizador sintáctico o el analizador semántico pueden introducir identificadores dentro de la tabla; el analizador semántico agregará tipos de datos y otra información; y las fases de optimización y generación de código utilizarán la información proporcionada por la tabla de símbolos para efectuar selecciones apropiadas de código objeto.

Puesto que la tabla de símbolos tendrá solicitudes de acceso con tanta frecuencia, las operaciones de inserción, eliminación y acceso necesitan ser eficientes, preferiblemente operaciones de tiempo constante. Una estructura de datos estándar para este propósito es la tabla de dispersión o de cálculo de dirección, aunque también se pueden utilizar diversas estructuras de árbol. En ocasiones se utilizan varias tablas y se mantienen en una lista o pila.

Tabla de literales

La búsqueda y la inserción rápida son esenciales también para la tabla de literales, la cual almacena constantes y cadenas utilizadas en el programa. Sin embargo, una tabla de literales necesita impedir las eliminaciones porque sus datos se aplican globalmente al programa y una constante o cadena aparecerá sólo una vez en esta tabla. La tabla de literales es importante en la reducción del tamaño de un programa en la memoria al permitir la reutilización de constantes y cadenas. También es necesaria para que el generador de código construya direcciones simbólicas para las literales y para introducir definiciones de datos en el archivo de código objeto.

Código intermedio

De acuerdo con la clase de código intermedio (por ejemplo, código de tres direcciones o código P) y de las clases de optimizaciones realizadas, este código puede conservarse como un arreglo de cadenas de texto, un archivo de texto temporal o bien una lista de estructuras ligadas. En los compiladores que realizan optimizaciones complejas debe ponerse particular atención a la selección de representaciones que permitan una fácil reorganización.

Generación de código intermedio Después de los análisis sintáctico y semántico, algunos compiladores generan una representación intermedia explícita del programa fuente. Se puede considerar esta representación intermedia como un programa para una máquina abstracta. Esta representación intermedia debe tener dos propiedades importantes; debe ser fácil de producir y fácil de traducir al programa objeto. La representación intermedia puede tener diversas formas. Existe una forma intermedia llamada "código de tres direcciones", que es como el lenguaje ensamblador para una máquina en la que cada posición de memoria puede actuar como un registro. El código de tres direcciones consiste en una secuencia de instrucciones, cada una de las cuales tiene como máximo tres operandos. El programa fuente de (1) puede aparecer en código de tres direcciones como

temp1 := entarea1(60) temp2 := id3 * temp1 (2) temp3 := id2 + temp2 id1 := temp3 Esta representación intermedia tiene varias propiedades. Primera, cada instrucción de tres direcciones tiene a lo sumo un operador, además de la asignación. Por tanto, cuando se generan esas instrucciones el compilador tiene que decidir el orden en que deben efectuarse, las operaciones; la multiplicación precede a la adición al programa fuente de (1). Segunda, el compilador debe generar un nombre temporal para guardar los valores calculados por cada instrucción. Tercera, algunas instrucciones de "tres direcciones" tienen menos de tres operadores, por ejemplo la primera y la última instrucciones de (2). Optimación de Código La fase de optimación de código trata de mejorar el código intermedio de modo que resulte un código de máquina más rápido de ejecutar. Algunas optimaciones son triviales. Por ejemplo, un algoritmo natural genera el código intermedio (2) utilizando una instrucción para cada operador de la representación del árbol después del análisis semántico, aunque hay una forma mejor de realizar los mismos cálculos usando las dos instrucciones

Temp1 := id3 * 60.0 (3) Id1 := id2 + temp1

Este sencillo algoritmo no tiene nada de malo, puesto que el problema se puede solucionar en la fase de optimación de código. Esto es, el compilador puede deducir que la conversión de 60 de entero a real se puede hacer de una vez por todas en el momento de la compilación, de modo que la operación entreal se puede eliminar. Además, temp3 se usa sólo una vez, para transmitir su valor a id1. Entonces resulta seguro sustituir a id1 por temp3, a partir de lo cual la última proposición de (2) no se necesita y se obtiene el código de (3).

Hay muchas variaciones en la cantidad de optimación de código que ejecutan los distintos compiladores. En lo que hacen mucha optimación llamados "compiladores optimadores", una parte significativa del tiempo del compilador se ocupa en esta fase. Sin embargo hay optimaciones sencillas que mejoran significativamente del tiempo del compilador se ocupa en esta fase. Sin embargo, hay optimaciones sencillas que mejoran sensiblemente el tiempo de ejecución del programa objeto sin retardar demasiado la compilación.

Archivos temporales

Al principio las computadoras no tenían la suficiente memoria para guardar un programa completo durante la compilación. Este problema se resolvió mediante el uso de archivos temporales para mantener los productos de los pasos intermedios durante la traducción o bien al compilar "al vuelo", es decir, manteniendo sólo la información suficiente de las partes anteriores del programa fuente que permita proceder a la traducción.

Las limitaciones de memoria son ahora un problema mucho menor, y es posible requerir que una unidad de compilación entera se mantenga en memoria, en especial si se dispone de la compilación por separado en el lenguaje. Con todo, los compiladores ocasionalmente encuentran útil generar archivos intermedios durante alguna de las etapas del procesamiento. Algo típico de éstos es la necesidad de direcciones de corrección hacia atrás durante la generación de código.

Véase también

• Compilador
• Intérprete (informática)
• Depurador