Compiladores

Indice
1.
Introducción
2. Clasificación de
Compiladores
3. Funciones de un
compilador
4. Partes en las que trabaja un
compilador
5. Forma de examinar de un
compilador
6. Como se sintetiza el
código objeto un compilador estándar,
teórica y gráficamente generación de
código
7. Árboles
sintácticos para representar como sintetiza el
código objeto un compilador
8. Herramientas que
muestran tipos de análisis de programas
fuente
9. Diagrama de
análisis de un programa fuente, definiendo cada una de sus
partes
10.
Conclusiones
11.
Bibliografía

1.
Introducción

En 1946 se desarrolló el primer ordenador
digital. En un principio, estas máquinas
ejecutaban instrucciones consistentes en códigos
numéricos que señalan a los circuitos de
la máquina los estados correspondientes a cada
operación. Esta expresión mediante códigos
numéricos se llamó Lenguaje
Máquina, interpretado por un secuenciador cableado o por
un microprograma. Pero los códigos numéricos de las
máquinas son engorrosos. Pronto los
primeros usuarios de estos ordenadores descubrieron la ventaja de
escribir sus programas
mediante claves más fáciles de recordar que esos
códigos numéricos; al final, todas esas claves
juntas se traducían manualmente a Lenguaje
Máquina. Estas claves constituyen los llamados lenguajes
ensambladores, que se generalizaron en cuanto se dio el paso
decisivo de hacer que las propias máquinas realizaran el
proceso
mecánico de la traducción. A este trabajo se le
llama ensamblar el programa.
Dada su correspondencia estrecha con las operaciones
elementales de las máquinas, las instrucciones de los
lenguajes ensambladores obligan a programar cualquier función de
una manera minuciosa e iterativa. De hecho, normalmente, cuanto
menor es el nivel de expresión de un lenguaje de
programación, mayor rendimiento se obtiene en el uso
de los recursos
físicos (hardware). A pesar de todo,
el lenguaje
ensamblador seguía siendo el de una máquina,
pero más fácil de manejar. Los trabajos de investigación se orientaron entonces hacia
la creación de un lenguaje que expresara las distintas
acciones a
realizar de una manera lo más sencilla posible para
el hombre.
Así, en 1950, John Backus dirigió una investigación en I.B.M. en un lenguaje
algebraico. En 1954 se empezó a desarrollar un lenguaje
que permitía escribir fórmulas matemáticas de manera traducible por un
ordenador. Le llamaron FORTRAN (FORmulae TRANslator). Fue el
primer lenguaje considerado de alto nivel. Se introdujo en 1957
para el uso de la computadora
IBM modelo 704.
Permitía una programación más cómoda y breve
que lo existente hasta ese momento, lo que suponía un
considerable ahorro de
trabajo. Surgió así por primera vez el concepto de un
traductor, como un programa que
traducía un lenguaje a otro lenguaje. En el caso
particular de que el lenguaje a
traducir es un lenguaje de alto nivel y el lenguaje
traducido de bajo nivel, se emplea el término
compilador.
La tarea de realizar un compilador no fue fácil. El primer
compilador de FORTRAN tardó 18 años-persona en
realizarse y era muy sencillo. Este desarrollo del
FORTRAN estaba muy influenciado por la máquina objeto en
la que iba a ser implementado. Como un ejemplo de ello tenemos el
hecho de que los espacios en blanco fuesen ignorados, debido a
que el periférico que se utilizaba como entrada de
programas (una
lectora de tarjetas
perforadas) no contaba correctamente los espacios en blanco.
Paralelamente al desarrollo de
FORTRAN en América, en Europa
surgió una corriente más universitaria, que
pretendía que la definición de un lenguaje fuese
independiente de la máquina y en donde los algoritmos se
pudieran expresar de forma más simple.
Esta corriente estuvo muy influida por los trabajos sobre
gramáticas de contexto libre publicados por Chomsky dentro
de su estudio de lenguajes naturales.Con estas ideas
surgió un grupo europeo
encabezado por el profesor F.L.Bauer (de la Universidad de
Munich). Este grupo
definió un lenguaje de usos múltiples independiente
de una realización concreta sobre una máquina.
Pidieron colaboración a la asociación americana
A.C.M. (Association for Computing Machinery) y se formó un
comité en el que participó J. Backus que colaboraba
en esta investigación. De esa unión surgió
un informe
definiendo un International Algebraic Language (I.A.L.),
publicado en Zurich en 1958. Posteriormente este lenguaje se
llamó ALGOL 58 (ALGOritmic Language). En 1969, el lenguaje
fue revisado y llevó a una nueva versión que se
llamó ALGOL 60. La versión actual es ALGOL 68, un
lenguaje modular estructurado en bloques.
En el ALGOL aparecen por primera vez muchos de los conceptos de
los nuevos lenguajes
algorítmicos:

• Definición de la sintaxis en notación
  BNF (Backus-Naur Form).
• Formato libre.
• Declaración explícita de tipo para
  todos los identificadores.
• Estructuras iterativas más
  generales.
• Recursividad.
• Paso de parámetros por valor y
  por nombre.
• Estructura de bloques, lo que determina la
  visibilidad de los identificadores.

Junto a este desarrollo en los lenguajes, también
se iba avanzando en la técnica de compilación. En
1958, Strong y otros proponían una solución al
problema de que un compilador fuera utilizable por varias
máquinas objeto. Para ello, se dividía por primera
vez el compilador en dos fases, designadas como el "front end" y
el "back end". La primera fase (front end) es la encargada de
analizar el programa fuente y la segunda fase (back end) es la
encargada de generar código
para la máquina objeto. El puente de unión entre
las dos fases era un lenguaje intermedio que se designó
con el nombre de UNCOL (UNiversal Computer Oriented Language).
Para que un compilador fuera utilizable por varias
máquinas bastaba únicamente modificar su back end.
Aunque se hicieron varios intentos para definir el UNCOL, el
proyecto se ha
quedado simplemente en un ejercicio teórico. De todas
formas, la división de un compilador en front end y back
end fue un adelanto importante.
Ya en estos años se van poniendo las bases para la
división de tareas en un compilador. Así, en 1959
Rabin y Scott proponen el empleo de
autómatas deterministas y no deterministas para el
reconocimiento lexicográfico de los lenguajes.
Rápidamente se aprecia que la construcción de analizadores léxicos
a partir de expresiones regulares es muy útil en la
implementación de los compiladores. En
1968, Johnson apunta diversas soluciones. En
1975, con la aparición de LEX surge el concepto de un
generador automático de analizadores léxicos a
partir de expresiones regulares, basado en el sistema operativo
UNIX.
A partir de los trabajos de Chomsky ya citados, se produce una
sistematización de la sintaxis de los lenguajes de
programación, y con ello un desarrollo de diversos
métodos de
análisis sintáctico.

Con la aparición de la notación BNF – desarrollada
en primer lugar por Backus en 1960 cuando trabajaba en un
borrador del ALGOL 60, modificada en 1963 por Naur y formalizada
por Knuth en 1964 – se tiene una guía para el desarrollo
del análisis sintáctico. Los diversos
métodos de
parsers ascendentes y descendentes se desarrollan durante la
década de los 60. En 1959, Sheridan describe un método de
parsing de FORTRAN que introducía paréntesis
adicionales alrededor de los operandos para ser capaz de analizar
las expresiones. Más adelante, Floyd introduce la
técnica de la precedencia de operador y el uso de las
funciones de
precedencia. A mitad de la década de los 60, Knuth define
las gramáticas LR y describe la construcción de una tabla canónica
de parser LR. Por otra parte, el uso por primera vez de un
parsing descendente recursivo tuvo lugar en el año 1961.
En el año 1968 se estudian y definen las gramáticas
LL así como los parsers predictivos. También se
estudia la eliminación de la recursión a la
izquierda de producciones que contienen acciones
semánticas sin afectar a los valores de
los atributos.
En los primeros años de la década de los 70, se
describen los métodos SLR y LALR de parser LR. Debido a su
sencillez y a su capacidad de análisis para una gran
variedad de lenguajes, la técnica de parsing LR va a ser
la elegida para los generadores automáticos de parsers. A
mediados de los 70, Johnson crea el generador de analizadores
sintácticos YACC para funcionar bajo un entorno UNIX . Junto al
análisis sintáctico, también se fue
desarrollando el análisis semántico.
En los primeros lenguajes (FORTRAN y ALGOL 60) los tipos posibles
de los datos eran muy
simples, y la comprobación de tipos era muy sencilla. No
se permitía la coerción de tipos, pues ésta
era una cuestión difícil y era más
fácil no permitirlo. Con la aparición del ALGOL 68
se permitía que las expresiones de tipo fueran construidas
sistemáticamente. Más tarde, de ahí
surgió la equivalencia de tipos por nombre y estructural.
El manejo de la memoria
como una implementación tipo pila se usó por
primera vez en 1958 en el primer proyecto de LISP.
La inclusión en el ALGOL 60 de procedimientos
recursivos potenció el uso de la pila como una forma
cómoda de manejo
de la memoria .
Dijkstra introdujo posteriormente el uso del display para acceso
a variables no
locales en un lenguaje de bloques.
También se desarrollaron estrategias para
mejorar las rutinas de entrada y de salida de un procedimiento .
Así mismo, y ya desde los años 60, se
estudió el paso de parámetros a un procedimiento por
nombre, valor y
variable. Con la aparición de lenguajes que permiten la
localización dinámica de datos , se
desarrolla otra forma de manejo de la memoria ,
conocida por el nombre de heap (montículo). Se han
desarrollado varias técnicas
para el manejo del heap y los problemas que
con él se presentan, como son las referencias perdidas y
la recogida de basura .
La técnica de la optimización apareció desde
el desarrollo del primer compilador de FORTRAN. Backus comenta
cómo durante el desarrollo del FORTRAN se tenía el
miedo de que el programa resultante de la compilación
fuera más lento que si se hubiera escrito a mano. Para
evitar esto, se introdujeron algunas optimizaciones en el
cálculo
de los índices dentro de un bucle. Pronto se sistematizan
y se recoge la división de optimizaciones independientes
de la máquina y dependientes de la máquina. Entre
las primeras están la propagación de valores , el
arreglo de expresiones, la eliminación de redundancias,
etc.

Entre las segundas se podría encontrar
lalocalización de registros, el uso
de instrucciones propias de la máquina y el reordenamiento
de código.
A partir de 1970 comienza el estudio sistemático de las
técnicas del análisis de flujo de
datos. Su repercusión ha sido enorme en las
técnicas de optimización global de un programa. En
la actualidad, el proceso de la
compilación ya está muy asentado. Un compilador es
una herramienta bien conocida, dividida en diversas fases.
Algunas de estas fases se pueden generar automáticamente
(analizador léxico y sintáctico) y otras requieren
una mayor atención por parte del escritor de compiladores (las
partes de traducción y generación de
código).
De todas formas, y en contra de lo que quizá pueda
pensarse, todavía se están llevando a cabo varias
vías de investigación en este fascinante campo de
la compilación. Por una parte, se están mejorando
las diversas herramientas
disponibles (por ejemplo, el generador de analizadores
léxicos Aardvark para el lenguaje PASCAL).
También la aparición de nuevas generaciones de
lenguajes -ya se habla de la quinta generación, como de un
lenguaje cercano al de los humanos-ha provocado la
revisión y optimización de cada una de las fases
del compilador. El último lenguaje de
programación de amplia aceptación que se ha
diseñado, el lenguaje Java, establece
que el compilador no genera código para una máquina
determinada sino para una virtual, la Java Virtual
Machine (JVM), que posteriormente será ejecutado por un
intérprete, normalmente incluido en un navegador de
Internet. El gran
objetivo de
esta exigencia es conseguir la máxima portabilidad de los
programas escritos y compilados en Java, pues es
únicamente la segunda fase del proceso la que depende de
la máquina concreta en la que se ejecuta el
intérprete.

¿Qué es un compilador?
Un traductor es cualquier programa que toma como entrada un
texto escrito
en un lenguaje, llamado fuente y da como salida otro texto en un
lenguaje, denominado objeto.

Compilador
En el caso de que el lenguaje fuente sea un lenguaje de programación de alto nivel y el objeto sea
un lenguaje de bajo nivel (ensamblador o
código de máquina), a dicho traductor se le
denomina compilador. Un ensamblador es
un compilador cuyo lenguaje fuente es el lenguaje
ensamblador. Un intérprete no genera un programa
equivalente, sino que toma una sentencia del programa fuente en
un lenguaje de alto nivel y la traduce al código
equivalente y al mismo tiempo lo
ejecuta. Históricamente, con la escasez de memoria de los
primeros ordenadores, se puso de moda el uso de
intérpretes frente a los compiladores, pues el programa
fuente sin traducir y el intérprete juntos daban una
ocupación de memoria menor que la resultante de los
compiladores. Por ello los primeros ordenadores personales iban
siempre acompañados de un intérprete de BASIC
(Spectrum, Commodore VIC-20, PC XT de IBM, etc.). La mejor
información sobre los errores por parte del
compilador así como una mayor velocidad de
ejecución del código resultante hizo que poco a
poco se impusieran los compiladores. Hoy en día, y con el
problema de la memoria prácticamente resuelto, se puede
hablar de un gran predominio de los compiladores frente a los
intérpretes, aunque intérpretes como los incluidos
en los navegadores de
Internet para
interpretar el código JVM de Java son la gran
excepción.
Ventajas de compilar frente a interpretar:

• Se compila una vez, se ejecuta n veces.
• En bucles, la compilación genera
  código equivalente al bucle, pero
  interpretándolo se traduce tantas veces una
  línea como veces se repite el bucle.
• El compilador tiene una visión global del
  programa, por lo que la información de mensajes de error es mas
  detallada.
• Ventajas del intérprete frente al
  compilador:
• Un intérprete necesita menos memoria que un
  compilador. En principio eran más abundantes dado que
  los ordenadores tenían poca memoria.
• Permiten una mayor interactividad con el
  código en tiempo de
  desarrollo.

Un compilador no es un programa que funciona de manera
aislada, sino que necesita de otros programas para conseguir su
objetivo:
obtener un programa ejecutable a partir de un programa fuente en
un lenguaje de alto nivel. Algunos de esos programas son el
preprocesador, el linker, el depurador y el ensamblador. El
preprocesador se ocupa (dependiendo del lenguaje) de incluir
ficheros, expandir macros, eliminar
comentarios, y otras tareas similares. El linker se encarga de
construir el fichero ejecutable añadiendo al fichero
objeto generado por el compilador las cabeceras necesarias y las
funciones de
librería utilizadas por el programa fuente. El depurador
permite, si el compilador ha generado adecuadamente el programa
objeto, seguir paso a paso la ejecución de un programa.
Finalmente, muchos compiladores, en vez de generar código
objeto, generan un programa en lenguaje ensamblador que debe
después convertirse en un ejecutable mediante un programa
ensamblador.

2. Clasificación de
Compiladores

El programa compilador traduce las instrucciones en un
lenguaje de alto nivel a instrucciones que la computadora
puede interpretar y ejecutar. Para cada lenguaje de
programación se requiere un compilador separado. El
compilador traduce todo el programa antes de ejecutarlo. Los
compiladores son, pues, programas de traducción insertados
en la memoria por el sistema operativo
para convertir programas de cómputo en pulsaciones
electrónicas ejecutables (lenguaje de máquina). Los
compiladores pueden ser de:

• una sola pasada: examina el código fuente una
  vez, generando el código o programa objeto.
• pasadas múltiples: requieren pasos intermedios
  para producir un código en otro lenguaje, y una pasada
  final para producir y optimizar el código producido
  durante los pasos anteriores.
• Optimación: lee un código fuente, lo
  analiza y descubre errores potenciales sin ejecutar el
  programa.
• Compiladores incrementales: generan un código
  objeto instrucción por instrucción (en vez de
  hacerlo para todo el programa) cuando el usuario teclea cada
  orden individual. El otro tipo de compiladores requiere que
  todos los enunciados o instrucciones se compilen
  conjuntamente.
• Ensamblador: el lenguaje fuente es lenguaje
  ensamblador y posee una estructura
  sencilla.
• Compilador cruzado: se genera código en
  lenguaje objeto para una máquina diferente de la que se
  está utilizando para compilar. Es perfectamente normal
  construir un compilador de Pascal que
  genere código para MS-DOS y que
  el compilador funcione en Linux y se haya
  escrito en C++.
• Compilador con montador: compilador que compila
  distintos módulos de forma independiente y
  después es capaz de enlazarlos.
• Autocompilador: compilador que está escrito en
  el mismo lenguaje que va a compilar. Evidentemente, no se puede
  ejecutar la primera vez. Sirve para hacer ampliaciones al
  lenguaje, mejorar el código generado, etc.
• Metacompilador: es sinónimo de compilador de
  compiladores y se refiere a un programa que recibe como entrada
  las especificaciones del lenguaje para el que se desea obtener
  un compilador y genera como salida el compilador para ese
  lenguaje. El desarrollo de los metacompiladores se encuentra
  con la dificultad de unir la generación de código
  con la parte de análisis. Lo que sí se han
  desarrollado son generadores de analizadores léxicos y
  sintácticos. Por ejemplo, los conocidos:
  LEX: generador de analizadores léxicos
  YACC: generador de analizadores sintácticos
  desarrollados para UNIX. Los inconvenientes que tienen son que
  los analizadores que generan no son muy eficientes.
• Descompilador: es un programa que acepta como entrada
  código máquina y lo traduce a un lenguaje de alto
  nivel, realizando el proceso inverso a la
  compilación.

3. Funciones de un
compilador

A grandes rasgos un compilador es un programa que lee un
programa escrito es un lenguaje, el lenguaje fuente, y lo traduce
a un programa equivalente en otro lenguaje, el lenguaje objeto.
Como parte importante de este proceso de traducción, el
compilador informa a su usuario de la presencia de errores en el
programa fuente.
A primera vista, la diversidad de compiladores puede parecer
abrumadora. Hay miles de lenguajes fuente, desde los lenguajes de
programación tradicionales, como FORTRAN o Pascal,
hasta los lenguajes especializados que han surgido virtualmente
en todas las áreas de aplicación de la informática. Los lenguajes objeto son
igualmente variados; un lenguaje objeto puede ser otro lenguaje
de programación o el lenguaje de máquina de
cualquier computador
entre un microprocesador y
un supercomputador. A pesar de existir una aparente complejidad
por la clasificación de los compiladores, como se vio en
el tema anterior, las tareas básicas que debe realizar
cualquier compilador son esencialmente las mismas. Al comprender
tales tareas, se pueden construir compiladores para una gran
diversidad de lenguajes fuente y máquinas objeto
utilizando las mismas técnicas básicas.
Nuestro conocimiento
sobre cómo organizar y escribir compiladores ha aumentado
mucho desde que comenzaron a aparecer
los primeros compiladores a principios de los
años cincuenta. Es difícil dar una fecha exacta de
la aparición del primer compilador, porque en un principio
gran parte del trabajo de experimentación y
aplicación se realizó de manera independiente por
varios grupos. Gran
parte de los primeros trabajos de compilación estaba
relacionada con la traducción de fórmulas
aritméticas a código de máquina.

En la década de 1950, se consideró a los
compiladores como programas notablemente difíciles de
escribir. EL primer compilador de FORTRAN, por ejemplo,
necesitó para su implantación de 18 años de
trabajo en grupo (Backus y otros [1975]). Desde entonces, se han
descubierto técnicas sistemáticas para manejar
muchas de las importantes tareas que surgen en la
compilación. También se han desarrollado buenos
lenguajes de implantación, entornos de programación
y herramientas
de software. Con
estos avances, puede hacerse un compilador real incluso como
proyecto de estudio en un curso de un semestre sobre diseño
sobre de compiladores.

4. Partes en las que
trabaja un compilador

Conceptualmente un compilador opera en fases. Cada una
de las cuales transforma el programa fuente de una
representación en otra. En la figura 3 se muestra una
descomposición típica de un compilador. En la
práctica se pueden agripar fases y las representaciones
intermedias entres las fases agrupadas no necesitan ser
construidas explícitamente.

Programa fuente

Programa objeto
Figura 3.- Fases de un compilador.
Las tres primeras fases, que forman la mayor parte de la
porción de análisis de un compilador se analizan en
la sección IX. Otras dos actividades, la
administración de la tabla se símbolos y el
manejo de errores, se muestran en interacción con las seis
fases de análisis léxico, análisis
sintáctico, análisis semántico,
generación de código intermedio, optimación
de código y generación de código. De modo
informal, también se llamarán "fases" al administrador de
la tabla de símbolos y al manejador de errores.

Administrador de la tabla de símbolos
Una función
esencial de un compilador es registrar los identificadores
utilizados en el programa fuente y reunir información
sobre los distintos atributos de cada identificador. Estos
atributos pueden proporcionar información sobre la memoria
asignada a un identificador, su tipo, su ámbito (la parte
del programa donde tiene validez) y, en el caso de nombres de
procedimientos, cosas como el número y
tipos de sus argumentos, el método de
pasar cada argumento (por ejemplo, por referencia) y el tipo que
devuelve, si los hay.
Una tabla de símbolos es una estructura de
datos que contiene un registro por cada
identificador, con los campos para los atributos del
identificador. La estructura de
datos permite encontrar rápidamente el registro de cada
identificador y almacenar o consultar rápidamente datos en
un registro
Cuando el analizador léxico detecta un indentificador en
el programa fuente, el identificador se introduce en la tabla de
símbolos. Sin embargo, normalmente los atributos de un
identificador no se pueden determinar durante el análisis
léxico. Por ejemplo, en una declaración en Pascal
como var posición, inicial, velocidad :
real;
El tipo real no se conoce cuando el analizador léxico
encuentra posición, inicial y velocidad.
Las fases restantes introducen información sobre los
identificadores en la tabla de símbolos y después
la utilizan de varias formas. Por ejemplo, cuando se está
haciendo el análisis semántico y la
generación de código intermedio, se necesita saber
cuáles son los tipos de los identificadores, para poder
comprobar si el programa fuente los usa de una forma
válida y así poder generar
las operaciones
apropiadas con ellos. El generador de código, por lo
general, introduce y utiliza información detallada sobre
la memoria asignada a los identificadores.

Detección e información de errores
Cada frase puede encontrar errores. Sin embargo, después
de detectar un error. Cada fase debe tratar de alguna forma ese
error, para poder continuar la compilación, permitiendo la
detección de más errores en el programa fuente. Un
compilador que se detiene cuando encuentra el primer error, no
resulta tan útil como debiera.
Las fases de análisis sintáctico y semántico
por lo general manejan una gran proporción de los errores
detectables por el compilador. La fase léxica puede
detectar errores donde los caracteres restantes de la entrada no
forman ningún componente léxico del lenguaje. Los
errores donde la cadena de componentes léxicos violan las
reglas de estructura
(sintaxis) del lenguaje son determinados por la fase del
análisis sintáctico.
Durante el análisis semántico el compilador intenta
detectar construcciones que tengan la estructura
sintáctica correcta, pero que no tengan significado para
la operación implicada, por ejemplo, si se intenta sumar
dos identificadores. Uno de los cuales es el nombre de una
matriz, y el
otro, el nombre de un procedimiento.

Las fases de análisis
Conforme avanza la traducción, la representación
interna del programa fuente que tiene el compilador se modifica.
Para ilustrar esas representaciones, considérese la
traducción de la proposición
Posición := inicial + velocidad * 60 (1)
La figura 4 muestra la
representación de esa proposición después de
cada frase.
Posición := inicial + velocidad * 60
Id1 := id2 + id3 * 60
Tabla de símbolos
1
2
3
4 : =
id1 +
id2 *
id3 entareal
60
temp1 := entareal(60)
temp2 := id3 * temp1
temp3 := id2 + temp2
id1 := temp3
temp1 := id3 * 60.0
id1 := id2 + temp1
MOVF id3, R2
MULF #60.0, R2
MOVF id2, R1
ADDF R2, R1
MOVF R1, id1

Figura 4.- Representación de una
proposición.
La fase de análisis léxico lee los caracteres de un
programa fuente y los agrupa en una cadena de componentes
léxicos en los que cada componente representa una
secuencia lógicamente coherente de caracteres, como un
identificador, una palabra clave (if, while, etc), un carácter
de puntuación, o un operador de varios caracteres, como
:=. La secuencia de caracteres que forman un componente
léxico se denomina lexema del componente.
A ciertos componentes léxicos se les agregará un
"valor léxico". Así, cuando se encuentra un
identificador como velocidad, el analizador léxico no
sólo genera un componente léxico, por ejemplo, id,
sino que también introduce el lexema velocidad en la tabla
de símbolos, si aún no estaba allí. El valor
léxico asociado con esta aparición de id
señala la entrada de la tabla de símbolos
correspondiente a velocidad.
Usaremos id1 , id2 e id3 para
posición, inicial y velocidad, respectivamente, para
enfatizar que la representación interna de un
identificador es diferente de la secuencia de caracteres que
forman el identificador. Por tanto, la representación de
(1) después del análisis léxico queda
sugerida por:
id1 := id2 + id3 *
60 (2)

Se deberían construir componentes para el
operador de varios caracteres := y el número 60, para
reflejar su representación interna. En la sección
IX ya se introdujeron las fases segunda y tercera: los
análisis sintáctico y semántico. El
análisis sintáctico impone una estructura
jerárquica a la cadena de componentes léxicos, que
se representará por medio de árboles
sintácticos, como se muestra en la figura 5A). Una
estructura de datos típica para el árbol se muestra
en la figura 5B), en la que un nodo interior es un registro con
un campo para el operador y dos campos que contienen apuntadores
a los registros de los
hijos izquierdo y derecho. Una hoja es un registro con dos o
más campos, uno para identificar el componente
léxico de la hoja, y los otros para registrar
información sobre el componente léxico. Se puede
tener información adicional sobre las construcciones del
lenguaje añadiendo más campos a les registros de
los nodos.
: =
id1 +
id2 *
id360
(a)

(b)

Figura 5.- La estructura de datos en (b) corresponde
al árbol en (a).

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.