Decimos que se requiere considerar estos puntos pues escribir un compilador es cosa de tiempo, recursos y dinero. En 1950 cuando surgen los primeros compiladores de FORTRAN el proyecto llevó 18 años hombre realizarlo. Es claro que también desde esa época se han descubierto técnicas sistemáticas para manejar la mayoría de las tareas más importantes que ocurren durante una compilación. Aún más, se han logrado mejores lenguajes de construcción, ambientes de trabajo y herramientas de programación para manejo de problemas más complejos.
Un lenguaje de programación se especifica generalmente con dos gramáticas separadas. La primera para definir las palabras del lenguaje y su función y otra para definir como van juntas las palabras. Una gramática similar puede definirse para el lenguaje destino, y nos adherimos a la técnica tradicional de definirse una gramática de atributos que define explícitamente la forma en que se realizará la traducción. Se puede, de la misma forma, definir gramáticas especificas para cada parte que constituye el compilador.
Una solución por medio de un programa a un problema será más fácil mientras el lenguaje de programación este más cerca de la terminología utilizada para definir el problema. Tal tipo de lenguaje se denomina de alto nivel a diferencia del que entiende o acepta un máquina que consiste en una larga cadena de unos y ceros y denominamos de bajo nivel. Una jerarquía basada en la dependencia de la máquina podría ser:
1. Lenguajes al nivel de la máquina. La forma más primitiva de un lenguaje de computación. Cada instrucción se representa con un código numérico y una dirección numérica para referirse a partes de la memoria principal de la computadora. Toda la responsabilidad de diagnóstico, ayudas de programación, codificación, etc. recae en el programador.
2. Lenguaje ensamblador. Versión simbólica del lenguaje de máquina. Cada operación se le asigna un código simbólico y a las localidades de memoria se les identifica con una etiqueta. Algunos lenguajes ensambladores ofrecen macroinstrucciones y cierta ayuda para el diagnostico y localización de errores.
3. De alto nivel o lenguajes orientados al usuario. Ofrecen la mayoría de las características de los lenguajes ensambladores al mismo tiempo que proporcionan estructuras de programación enriquecidas como son estructuras de control, bloques de anidamiento, procedimientos, funciones, etc. Normalmente el acceso a las características de la máquina es limitado o no existe.
4. Lenguajes orientados a un problema. Ayudan al modelado y expresión programática de problemas específicos en cierta área.
Las ventajas de los lenguajes de alto nivel sobre los de bajo nivel, tales como lenguaje de máquina o ensamblador, incluyen entre otros los siguientes:
a) Son más fáciles de aprender requiriendo poco o ningún conocimiento de la electrónica de la computadora pues son relativamente independientes de la máquina en la que se van a usar.
b) El programador se desentiende de tareas de mantenimiento incluyendo referencias numéricas y simbólicas a instrucciones, localidades de memoria, constantes, etc. De tales tareas se encarga el compilador.
c) No se requiere saber como convertir tipos de datos externos a representaciones internas. Por ejemplo, datos numéricos a números de punto flotante, representaciones decimales, ASCII, decimal empacado, etc.
d) Ofrecen estructuras de control no disponibles en lenguajes de bajo nivel que mejoran la eficiencia de programación, el mantenimiento, la lectura y la comprensión posterior del programa.
e) Son más fáciles de espulgar que sus equivalentes de bajo nivel, por ejemplo, el uso de declaraciones de tipo de variables ofrece redundancia que beneficia en la detección de errores, un uso de apuntadores ordenado y disciplinado.
f) Al contener estructuras de control más poderosa, la representación de un problema se realiza con mayor facilidad.
g) Al ser modulares puede repartirse el problema entre un grupo de programadores integrándose al final.
h) Son relativamente independientes de la computadora en que son ejecutados, por ejemplo, un programa en C estándar puede transcribirse a cualquier otra computadora con poca o ninguna modificación, cosa que no es cierta para ciertos lenguajes que dependen de algún sistema operativo específico para su funcionamiento.
1.2.1 Análisis y Síntesis
Existen dos partes en una compilación: el análisis y la síntesis. El análisis desglosa el programa fuente en sus partes constituyentes y crea una representación intermedia. La síntesis construye el programa destino de la representación intermedia del programa fuente. De las dos partes. la síntesis es la que requiere de técnicas más especializadas.
Durante el análisis las operaciones requeridas por el programa fuente son determinadas y colocadas en una estructura jerárquica llamada árbol. Usualmente se emplea un árbol de sintaxis en el que cada nodo representa una operación y sus ramas los argumentos de la operación como se representa en la siguiente figura:
Muchas herramientas de programación manipulan programas fuentes para realizar este tipo de análisis entre ellos:
1. Editores de estructura. Programa que acepta como entrada una serie de comandos para construir un programa fuente. No sólo realiza las operaciones de creación y de modificación de texto sino que analiza el texto del programa para responder de acuerdo a ciertas reglas establecidas que son útiles en la creación de programas, por ejemplo, completar estructuras (al colocar la palabra inicial, cierra la estructura: FOR, NEXT; WHILE, DO; BEGIN, END; etc.) y con frecuencia su salida es similar a la fase de análisis de un compilador.
2. Impresores de Fuentes. Toma un programa fuente y lo imprime de forma tal que la estructura sea claramente visible (comentarios, sangría, estructuras, etc.).
3. Verificadores estáticos. Lee un programa fuente, lo analiza e intenta descubrir errores sin ejecutar el programa. Ejemplos de tales eerores son fragmentos de código que no se ejecutan, operaciones entre tipos incompatibles, etc.
4. Interpretes. En lugar de producir un programa destino como una traducción, interpretan instrucción a instrucción del programa fuente. Son frecuentemente utilizados para lenguajes de comandos complejos o lenguajes de muy alto nivel como APL en los que muchas operaciones no pueden deducirse al momento de compilar.
Además de estas aplicaciones podemos encontrar otras en la que podríamos pensar que las técnicas de compilación no son utilizadas:
1. Formato de texto. Toma como entrada una cadena de caracteres que incluye texto junto con las instrucciones para dar formato al mismo, figuras, estructuras matemáticas, etc. y realiza el análisis necesario para entregar a su salida las instrucciones requeridas para ejecutar el formato.
2. Compiladores de Silicio. Las variables del lenguaje representan señales lógicas de un circuito digital.
3. Interpretes de Acceso. Toman como entrada predicados que contienen relaciones lógicas para buscar en archivos los registros que los satisfagan .
Además del compilador puede ser que se requiera varios otros programas para llegar a un programa destino ejecutable. Un programa fuente puede dividirse en módulos que se guardan en archivos separados, la tarea de reunir todos estos pedazos es algunas veces encargada a otro programa llamado preprocesador. El preprocesador expande algunos macros e instrucciones en el lenguaje que entiende el compilador.
programa fuente en forma de esqueleto
preprocesador programa fuente compilador programa destino ensamblador
código de máquina intermedio liga
código de maquina
En un compilador el análisis consta de tres partes:
1. Análisis lineal. Llamado en los compiladores análisis léxico o búsqueda. La cadena de caracteres que forman el programa fuente son leídos línea a línea y de izquierda a derecha y agrupados en fichas que son secuencias de caracteres que tienen un significado colectivo.
2. Análisis Jerárquico. Llamado en los compiladores análisis de sintaxis o agrupamiento. Los caracteres o fichas se agrupan en forma jerárquica en agrupaciones anidadas que tiene un significado conjunto.
3. Análisis Semántico. Se realizan ciertas verificaciones para asegurarse que los componentes de un programa encajen entre ellos de forma lógica y significativa.
1.3.1 Análisis Léxico
Tiene como propósito agrupar las expresiones en fichas. Por ejemplo:
distancia = velocidad + aceleración * 30
1. Identificador distancia
2. Símbolo de asignación =
3. Identificador velocidad
4. Signo +
5. Identificador aceleración
6. Signo *
7. El número entero 30
Normalmente los espacios son eliminados en el proceso de crear las fichas.
1.3.2 Análisis de Sintaxis
Su trabajo consiste en agrupar las fichas en frases gramaticales usadas por el compilador para sintetizar la salida. Usualmente las frases gramaticales son representadas en un árbol como el mostrado a continuación
En la fórmula representada, la multiplicación se realiza antes de la suma y no puede expresarse en una unidad por si misma.
La estructura jerárquica se expresa generalmente con reglas, recursivas o no, como, por ejemplo, las siguientes reglas de la definición de una expresión:
1. Un identificador es una expresión
2. Un número es una expresión
3. Si expresión A y expresión B son expresiones también lo son(expresión
A + expresión B) y (expresión A * expresión B)
Las primeras dos son reglas básicas no recursivas mientras que la tercera define expresiones en términos de operadores aplicados a otras expresiones.
Como ejemplo de recursividad podemos usar las siguientes dos reglas:
1. Si identificador A es un identificador y expresión B es una expresión entonces: identificador A = expresión B es una declaración.
2. Si expresión A es una expresión y declaración B es una declaración, entonces:
WHILE (expresión A) DO declaración B IF (expresión A) THEN declaración B son también declaraciones.
La división entre análisis de sintaxis y léxico es arbitraria pero generalmente se elije la que facilite el análisis. Uno de los factores puede ser si el lenguaje es inherentemente recursivo o no pues los constructores léxicos no requieren recursividad mientras los de sintaxis si la requieren.
Si definimos un identificador como una serie finita de letras y números que comienzan siempre por letra, estos pueden reconocerse fácilmente de la entrada agrupándolos en una unidad, asignándoles una ficha, guardando el identificador en una tabla de símbolos y eliminando la cadena de la entrada para buscar el siguiente identificador. Desgraciadamente este tipo de análisis no es lo suficientemente poderoso para analizar expresiones y declaraciones sin colocar algún tipo de jerarquía o anidamiento en el análisis.
1.3.3 Análisis Semántico
Este tipo de análisis verifica los errores semánticos (de significado) y recoge información para las subsecuentes fases del compilador. Utiliza la estructura jerárquica determinada en la fase de análisis de sintaxis para identificar operadores y operando de las expresiones y declaraciones.
Un componente importante de esta fase es la verificación de consistencia de tipos de números. En algunos lenguajes no está permitido mezclar distintos tipos de números para ciertas operaciones y en algunos otros es requisito indispensable definirlos de antemano. Debemos recordar para esto que hay una diferencia significativa entre la representación de un entero sin signo, entero con signo, real, real en doble palabra, etc. dentro de los registros de memoria y es requisito del compilador que pueda manejar los distintos tipos de forma coherente sin resultados extraños o equivocados.
En su forma conceptual un compilador realiza su trabajo en fases cada una de las cuales transforma su entrada en una representación útil para la siguiente fase. Algunas de estas fases pueden agruparse y una división tan tajante quizá no sea tan evidente.
A. analizador léxico B. analizador de sintaxis
C. analizador semántico D. generador intermedio de código
E. Mejora del código F. generador de código
Cada una de las fases hace uso del manejo de una tabla de símbolos y de errores.
1.4.1 Tabla de Símbolos
Una función esencial de un compilador es guardar en un área de memoria los identificadores utilizados en las expresiones y declaraciones junto con sus atributos. Dentro de estos atributos pueden encontrarse el tipo de número, el espacio asignado, su alcance (dónde es válido) y en el caso de procedimientos o rutinas las variables de argumentos, el método de acceder a los argumentos (por valor o por referencia) el tipo de valor resultante en caso de función, etc.
Un tabla de símbolos se forma básicamente de una estructura de datos donde cada registro representa un identificador y sus campos los atributos del identificador. El analizador léxico coloca los identificadores en la tabla pero usualmente no puede saber sus atributos.
Las fases siguientes del compilador agregan información de los identificadores en la tabla de símbolos usando esta información de forma variada. Por ejemplo, se puede agregar de que tipo de identificador se trata y asegurarse que el programa fuente los usa de forma válida a ese lenguaje.
1.4.2 Detección de errores
En cada fase de la compilación pueden encontrarse errores y deben manejarse de forma tal que se pueda seguir con las demás fases sin interrumpir el proceso para poder identificar otros errores, si es que los hay, en el código.
El análisis sintáctico y semántico generalmente detectan la mayoría de los errores:
El análisis de sintaxis detecta cuando la cadena de fichas viola las reglas de estructura (sintaxis) permitidas en el lenguaje.
El análisis semántico detecta las construcciones que, aunque tengan la semántica correcta, no respetan las reglas de construcción del lenguaje (por ejemplo sumar un arregla a una función).
Durante el análisis léxico se detectan los errores de cadenas que no forman fichas válidas en el lenguaje.
1.4.3 La fase de Análisis
Conforme avanza el proceso de compilación, la representación interna del programa fuente va cambiando. Por ejemplo en la asignación
distancia = velocidad + aceleración * 30
a. El análisis léxico toma los caracteres de la cadena y los agrupa en fichas en las que cada una de ellas representa una secuencia de caracteres cohesiva de forma lógica, tales como un identificador, una palabra clave (ELSE, IF, DO, etc.), una marca de puntuación o un operador de varios caracteres tal como >=. La secuencia de caracteres que forma una ficha es llamado el lexema. No sólo se genera una ficha sino que se introduce el lexema en la tabla de símbolos. La frase queda entonces similar a id1=id2+id3*30
b. El analizador sintáctico impone una estructura jerárquica en la cadena de fichas que representamos por un árbol en forma esquemática o una lista ligada en forma interna en una computadora.
=
id1 +
id2 *
id3 30
c. El análisis semántico verifica la coherencia de las operaciones. En nuestro ejemplo aceleración es tipo real mientras que 30 es entero, se debe entonces tomar las medidas adecuadas para que exista consistencia entre los tipos de operaciones:
=
id1 +
id2 *
id3 entero a real
30
d. En la generación intermedia de código se genera una representación explícita del programa fuente en un código intermedio específico del compilador que consta de dos características importantes:
1. Debe ser fácil de producir
2. Debe ser fácil de traducir al código objeto
Si el código objeto será el ensamblador es entonces es importante tener un lenguaje intermedio que use un esquema de "código de tres direcciones" donde cada localidad de memoria funciona como un registro, por ejemplo:
temp1 = entero a real (30) temp2 = id3 * temp1 temp3 = id2 + temp2
iId1 = temp3
Note del código anterior las siguientes características (debido a las limitaciones del lenguaje ensamblador):
1. Cada instrucción de tres direcciones tiene solamente un operando adicional a una asignación.
2. Existe un registro temporal para almacenar resultados intermedios de cada instrucción.
3. Pueden existir operaciones que tengan menos de dos operandos pero no más de dos.
e. Mejorar el código consiste en perfeccionar el código intermedio para obtener un programa que ejecute más rápido. Debido a su importancia, gran parte del tiempo del compilador es usado en esta fase. Un resultado posible al mejorar el código podría ser:
temp1 = id3 * 30
Id1 = id2 + temp1
f. La generación de código es la fase final del compilador y consiste en generar el programa objeto relocalizable, usualmente ensamblador o lenguaje de máquina. Aquí, cada instrucción del código mejorado es traducida a su equivalente
en el lenguaje objeto. Un aspecto crucial es la asignación de variables a los registros. Un ejemplo en lenguaje ensamblador de las máquinas 80×86 sería:
MOV AX,id3
MUL 30
MOV BX,id2
ADD AX,BX MOV id1,AX
En este caso se debe cuidar el uso de reales y enteros especialmente en la multiplicación y suma para evitar errores y resultados extraños.
Un compilador moderno puede o no usar programas auxiliares para realizar su función. Entre los más importantes tenemos:
1.5.1 Preprocesadores
Un preprocesador traduce cierta información contenida en el programa fuente para su proceso por el compilador. Entre sus funciones están:
a. Procesamiento de macros. Es común la definición de cadenas cortas de caracteres que sustituyen a otros durante la compilación, ya sea para ahorra tiempo al reemplazar por cadenas más largas o para ayudar en la claridad del lenguaje al sustituir constantes por nombres o funciones definidas por el usuario.
b. Inclusión de archivos. Se agregan archivos completos al programa fuente, ya sea para realizar programas claramente diferenciados y luego integrarlos o para incluir librerías de funciones que el lenguaje no realiza por sí mismo.
c. Preprocesamiento racional. Complementa a lenguajes antiguos agregándole la característica de estructuras modernas para que su compilación sea más fácil y su desarrollo más ágil.
d. Extensiones del lenguaje. Mejoranun lenguaje al incluir capacidades no contempladas en el diseñó inicial del mismo, por ejemplo librerías de bases de datos, gráficos, estadísticas, etc.
1.5.2 Ensambladores
Algunos compiladores producen lenguaje ensamblador y dejan el proceso final de traducción a un ensamblador comercial mientras que otros dan como resultado un programa relocalizable objeto.
La tarea del ensamblador consiste en tomar los mnemónicos válidos del lenguaje defindo de la unidad de procesamiento central (UPC) en cuestión y entregar los unos y ceros que serán colocados en la memoria principal para su ejecución.
1.5.3 Ensambladores de dos pasos
La forma más sencilla de ensamblador realiza dos pasos o lecturas del archivo de entrada para lograr su salida. En el primer paso todos los identificadores que denotan localidades de almacenamiento son guardados en una tabla de símbolos separada de la del compilador. En esta tabla se les asignan localidades de memoria para su almacenamiento.
En el segundo paso, el ensamblador traduce cada operación a la secuencia de bits que lo representan dentro de la máquina. Su salida es generalmente un código que se puede localizar en cualquier área de memoria, esto es, que puede cambiar su punto de inicio dentro de la memoria sin afectar el resultado final del programa. Para lograr esta re localización es necesario que todos los saltos a una dirección sean relativos y no absolutos.
1.5.4 Cargadores y ligadores
Usualmente el programa llamado cargador se encarga de realizar las dos funciones: la de posicionar el programa objeto en memoria y la de ligar-editar el programa objeto. Aunque bien pueden ser dos programas separados.
El ligado (link) toma varios programas y los junta en uno sólo, resuelve también las referencias externas, esto es, las llamadas a localidades que no se encuentran en el mismo módulo. Estos programas pueden ser otros programas o librerías que contienen ciertas funciones que se requieren dentro del programa fuente para realizar sus funciones.
Si en la tablas de símbolos se encuentran referencias a símbolos externos que no se pueden resolver dentro de la compilación y el ligado de programas, es necesario incluir la tabla de símbolos como parte del código re-localizable
En el diseño de compiladores se acostumbra algunas veces agrupar varios de los elementos lógicos que conforman el compilador. Entre otras agrupaciones podemos encontrar las descritas a continuación.
1.6.1 Parte Inicial y Final
Constituye un tipo de agrupación genérica. La parte inicial consiste en todas las fases que son independientes del lenguaje objeto mientras que la parte final son todas aquellas que dependen del programa objeto. 1-13
En la parte inicial encontramos el análisis léxico y sintáctico, la creación de la tabla de símbolos, el análisis semántico y la generación de código intermedio. Se puede encontrar también aquí una cierta mejora de código y el manejo de errores de cada fase de este grupo.
La parte final consta de la fase de generación de código objeto y el manejo de errores de cada fase junto con las operaciones de la tabla de símbolos. Si se diseña bien la parte inicial, la parte final puede cambiarse para obtener distintos programas objeto para distintas máquinas. Se puede intentar también diseñar la parte inicial de forma tal que se genere un mismo código intermedio para distintos lenguajes y usar una sola parte final para compilar todos los lenguajes pero debido a las diferencias sutiles entre lenguajes el alcance de la técnica ha sido limitada.
1.6.2 Pasos
Varias fases de la compilación se agrupan en una sola pasada que consiste en una lectura del archivo fuente y una escritura de un archivo de salida. En la practica existe una gran variedad en la forma en que estos pasos son utilizados por lo que se prefiere organizar el compilador en fases en lugar de pasos.
Por ejemplo, se puede agrupar en un paso la fase de analizador léxico, sintáctico, semántico y la generación intermedia del código. Una forma de concebir este paso consistiría en dejar que el analizador sintáctico se encuentra a cargo e intente descubrir la estructura gramatical localizada en las fichas que le entrega el analizador léxico, una vez descubierta la estructura gramatical se llama al generador de código intermedio para realizar un análisis semántico y generar una porción de código.
1.6.2.1 Reducir el número de pasos
Es recomendable reducir el número de pasos en el compilador puesto que el leer y escribir de un archivo lleva tiempo, pero para lograr esto nos vemos forzados a tener un programa muy grande en memoria pues algunas fases pueden requerir datos de otras fases. La estructura del compilador no es sencilla y puede ser mucho más grande que el programa fuente y objeto por lo que la limitante de memoria es importante.
Algunas fases son fáciles de agrupar mientras que en otras tendremos problemas según el lenguaje. En algunos lenguajes se permite el uso de variables sin previa definición por lo que es difícil generar código objeto en el momento. Lo mismo ocurre con saltos a otras porciones del programa que aun no han sido analizadas.
En algunos casos es posible dejar "casillas" en blanco que luego llenaremos cuando conozcamos la información. Esto lo logramos en dos pasos o con una técnica llamada "relleno hacia atrás".
1.7 Herramientas de Construcción
1.7.1 Modelo de un compilador
La tarea de construir un compilador para un lenguaje particular es compleja. La complejidad y la naturaleza de la compilación dependen, en gran extensión, del lenguaje fuente. La complejidad del compilador puede reducirse si el diseñador toma en cuenta varios factores. Discutiremos a lo largo de libro algunos de ellos. Si especificamos un lenguaje tal como BASIC, ALGOL, C, PASCAL o cualquier otro de alto nivel ya diseñado podremos explicar el modelo en relación a ellos sin preocuparnos del diseño en sí del lenguaje. Aunque el modelo puede cambiar dependiendo del lenguaje es, sin embargo, representativo del proceso de compilación.
Un compilador requiere realizar dos tareas principales: El análisis del programa fuente y la síntesis del correspondiente programa objeto. La tarea del análisis comprende la descomposición del programa fuente en sus partes básicas. Usando estas partes, en la síntesis se construye los módulos equivalentes del programa objeto. La conversión se realiza de forma más fácil si se construyen y mantienen varias tablas.
Un programa fuente consiste de una cadena de símbolos tales como +, -, ), (, etc. y contiene generalmente de construcciones elementales del lenguaje tales como nombres de variables, etiquetas, constantes, palabras claves y operadores. Es requisito entonces del compilador, identificar tales tipos como clases. Los constructores del lenguaje se dan en la definición del mismo y son responsabilidad del diseñador del lenguaje.
Si observamos la siguiente figura vemos que el programa fuente es la entrada al analizador léxico o buscador cuyo propósito es separar el texto que entra en fichas tales como constantes, variables, palabras clave y operadores. En esencia un analizador léxico realiza un análisis de sintaxis a un nivel bajo. Por razones de eficiencia, cada tipo de ficha se le da una representación numérica interna única. Por ejemplo podemos escoger el 1 para las variables, el 2 para una valor numérico constante, el 3 para etiquetas, el operador de suma (+) como 4, etc.
En el siguiente código en PL/1 ejemplificamos tal traducción del analizador léxico:
PRUEBA: IF A>B THEN X=Y;
Texto PRUEBA | Ficha resultante 3 |
: | 26 |
IF | 20 |
A | 1 |
> | 15 |
B | 1 |
THEN | 21 |
X | 1 |
= | 10 |
Y | 1 |
; | 27 |
Note que hemos ignorado los espacios, aunque en general se deben procesar, junto con los comentarios pues no representan instrucciones válidas del lenguaje.
Algunos lenguajes permiten continuar las instrucciones en varias líneas lo que se debe tomar en cuenta. Algunos analizadores léxicos incluyen las constantes, variables y etiquetas en una tabla apropiada. Una entrada en este tipo de tabla puede contener el tipo de variable además de su nombre, dirección en el programa objeto, valor y línea en la cual fue declarada.
El analizador léxico proporciona las fichas al analizador sintáctico. Estas fichas pueden tomar la forma de pares de valores donde el primero indica la dirección o localización de la ficha en una tabla de símbolos y el segundo la representación numérica de la ficha. Tal simplificación nos reporta ventajas al tener todas las fichas representadas con información de longitud fija y consistente: Una dirección o apuntador y un número entero.
El analizador sintáctico es mucho más complejo que el léxico pues su función consiste en determinar la manera en que el programa fuente (en forma de fichas) se descompone en los distintos constituyentes. Esto es, el analizador sintáctico determina la estructura global del programa fuente. El proceso es análogo a determinar la estructura de una oración en español donde nos interesa reconocer ciertas clases de objetos tales como "verbo", "predicado", "sustantivo", "adjetivo", etc.
En el análisis sintáctico estamos preocupados del agrupamiento de las fichas en grandes clases sintácticas como expresiones, asignaciones y declaraciones. Como salida obtenemos una estructura de árbol o su equivalente en listas ligadas, en la que las hojas son las fichas y cada una de las ramificaciones representa una clase sintáctica. Por ejemplo, para analizar la siguiente oración:
(A+B)*(C+D)
podemos producir las clases sintácticas < factor>, < termino> y < expresión> como se representa en la siguiente figura:
La aproximación a la solución utilizando un árbol de sintaxis utiliza una serie de reglas conocidas como gramática que es utilizada para describir precisamente el lenguaje. Una gramática es utilizada por el analizador sintáctico para determinar la estructura del programa fuente. Este proceso se le denomina análisis y, consecuentemente, nos referimos a los analizadores sintácticos como analizadores en general.
El árbol de sintaxis producido por el analizador semántico es usado por el analizador semántico. La función del analizador semántico es determinar el significado (o semántica) del programa fuente. Aunque es conceptuosamente deseable el separar la sintaxis del programa fuente de su semántica, el analizador sintáctico trabaja en estrecha colaboración con el semántico. Sin embargo, el proceso del analizador semántico es diferente y único dentro del compilador. Para una expresión tal como (A+B)*(C+D) el analizador semántico debe encontrar que acciones necesarias para realizar la suma y multiplicación en el orden deseado. Cuando el analizador reconoce símbolos tales como * ó +, llama a una rutina "semántica" que especifica las acciones a realizar. Esta rutina verifica si las dos cxantidades o expresiones utilizadas para la suma han sido definidas de antemano, si son del mismo tipo (si no, la rutina probablemente las convierta al mismo tipo) y si ya tienen un valor definido. El analizador semántico interactúa con varias tablas del compilador mientras realiza su tarea.
Entre las operaciones asignadas al analizador semántico se puede incluir la de generar una forma de código intermedio que facilite la conversión a un lenguaje objeto. Para la expresión (A+B)*(C+D) este código intermedio en forma de cuartetos podría bien ser:
(+,A,B,T1) (+,C,D,T2) (*,T1,T2,T3)
Donde (+,A,B,T1) se interpreta como "suma A con B y coloca el resultado intermedio en una localidad temporal T1" y así para cada cuarteto de valores. La forma exacta del lenguaje intermedio depende en su totalidad de como va a procesarse durante la fase de síntesis. Una expresión infija puede convertirse en una Polaca Inversa o sufija por lo que (A+B)*(C+D) queda como AB+CD+* que contiene los operadores en el orden en que deben ejecutarse. Otro tipo de representación intermedia puede ser un árbol de sintaxis en el que se representa el análisis del programa fuente.
La salida del analizador semántico se pasa al generador de código. En este punto la forma intermedia del código se traduce ya sea a lenguaje de máquina o a lenguaje ensamblador. Como ejemplo tomemos los cuartetos de la expresión que hemos analizado para convertirlos a la secuencia de instrucciones de ensamblador de una dirección y un acumulador:
MOV | AX,A | ;A en el acumulador | ||
ADD | AX,B | ;A+B | ||
MOV | T1,AX | ;Guarda en T1 | ||
MOV | AX,C | ;C en acumulador | ||
ADD | AX,D | ;C+D | ||
MOV | T2,AX | ;Guarda en T2 | ||
MOV | BX,T1 | ;T1 en BX | ||
MUL | BX | ;T1*T2 | ||
MOV | AX,T3 | ;Guarda en T3 | ||
Esta salida del generador de código es pasada al mejorado de código cuyo propósito es obtener una secuencia de instrucciones óptima para la máquina de la cual deseamos obtener el programa objeto. Esta fase se encuentra sólo en los compiladores más sofisticados. Algunas mejoras que son posibles a un nivel local incluyen la evaluación de expresiones constantes, el uso de ciertas propiedades de los operadores como la asociatividad, conmutatividad, distribución y detección de subexpresiones comunes. Debido a la conmutatividad de la multiplicación, el ejemplo anterior pude reducirse a:
MOV | AX,A | ;A en el acumulador | ||
ADD | AX,B | ;A+B | ||
MOV | T1,AX | ;Guarda en T1 | ||
MOV | AX,C | ;C en acumulador | ||
ADD | AX,D | ;C+D | ||
MUL | T1 | ;T1*(A+B) | ||
MOV | AX,T2 | ;Guarda en T2 | ||
Existen mejoras a nivel global que pueden realizarse tales como la evaluación única de expresiones idénticas que ocurren varias veces, eliminar instrucciones invariables que se encuentren dentro de lazos y situarlas fuera de ellos, etc. Estas mejoras son independientes de la máquina objeto. Existen, sin embargo, mejoras que dependen de la máquina objeto como el uso óptimo de registros. Un mejorador de código bien diseñado puede producir código de igual o mejor calidad que un programador experimentado.
1.7.2 Relaciones entre las partes de un compilador
El modelo planteado hasta el momento realiza distinciones muy marcadas entre una fase y otra dentro de un compilador pero en la mayoría de ellos las fases se encuentran combinadas. En nuestra discusión hemos omitidola descripción de cómo cada proceso interactúa con los demás. Examinemos las posibles relaciones entre los analizadores léxico y sintáctico. Una posibilidad es que el analizador léxico entregue una sola ficha al analizador sintáctico para su proceso. El analizador sintáctico "llama" al léxico cada vez que requiere una nueva ficha pasando una sola vez sobre el código del programa fuente a lo que se denomina compilador de una sola pasada. Otra posibilidad es que, como en nuestro ejemplo, el analizador léxico entregue todas las fichas correspondientes al código del programa fuente de una sola vez y luego el analizador sintáctico pase de nuevo por todas las fichas analizadoras, a este proceso se denomina compilador de dos pasadas. Existen compiladores que realizan solo una pasada y algunos que lo hacen hasta 30 veces como los primeros compiladores para PL/I de IBM.
Los factores que influencian el número de pasos para un compilador en especial incluyen los siguientes:
1. Memoria disponible.
2. Velocidad y tamaño del compilador.
3. Velocidad y tamaño del programa objeto.
4. Requerimientos para espulgar el programa.
5. Detección de errores y técnicas de recuperación requeridas.
6. Número de personas y el tiempo utilizados para escribir el compilador.
Algunos compiladores educativos realizan sólo una pasada pues se ha comprobado que se utiliza mucho más tiempo compilando que ejecutando y que una vez que los programas han quedado listos la mayoría son descartados pues sólo sirvieron para el propósito de aprender. En ellos las fases semánticas y de generación de código son combinadas en una sola. Se hace especial énfasis en espulgar, detectar errores, la recuperación de errores y el diagnostico del programa.
Ciertos lenguajes no pueden compilarse en una sola pasada, en especial lenguajes como FORTRAN y PL/I que requieren de varios pasos en la mejora de código y ésta se encuentra en varias partes del proceso y no como un ente único.
Algunas otras combinaciones son posibles. Muchas veces las fases de análisis sintáctico, análisis semántico y generación de código se combinan en un sólo módulo.
1.7.3 Errores
Un aspecto de la construcción de compiladores ha sido omitido de nuestro análisis y es la detección y recuperación de errores. La recuperación de errores se asocia de forma cercana a la fase de análisis sintáctico y su propósito es prolongar la vida de compilación del programa en caso de que un error ocurra. Una estrategia utilizada es la de, si es posible, ejecutar el programa aún con errores. Esto reduce el número de veces que el programa fuente tiene que compilarse antes de estar libre de errores. Algunas técnicas de recuperación insertan o descartan fichas para intentar corregir la parte del programa fuente sintácticamente incorrecto.
Otro aspecto no discutido es el del manejo de tablas de símbolos que son creadas y mantenidas durante todo el proceso de compilar un programa. Existen también construcciones que requieren conservar y crear estructuras en la memoria de la computadora. El diseño y realización de estas estructuras es llamada organización de ejecución y realización o algunas veces manejo de la memoria. Para los lenguajes que permiten la creación de estructuras complejas, lenguajes estructurados en bloques y objetos el manejo de memoria es complejo e importante.
Para terminar, analicemos la dificultad relativa de cada fase del compilador. La fase del analizador léxico es quizá la más directa. La siguiente en dificultad es el análisis sintáctico o fase de análisis. Mucha investigación se ha realizado en estas dos fases y como resultado, han sido automatizadas en gran medida. Las dificultades reales en los compiladores recaen en las fases del análisis semántico, generación de código y mejora del mismo. Otra área siempre problemática es tratar de portar los programas de una máquina a otra.
1.8 Bibliografía
• Aho, A.V., J.D. Ullman: Principles of Compiler Design Addison-Weley, 1995.
• Jean-Paul Trembla, Paul G. Sorenson: The Theory and Practice of Compiler Writing McGraw-Hill Book Company 1994.
EL PRESENTE TEXTO ES SOLO UNA SELECCION DEL TRABAJO ORIGINAL. PARA CONSULTAR LA MONOGRAFIA COMPLETA SELECCIONAR LA OPCION DESCARGAR DEL MENU SUPERIOR.
| Página siguiente |