PDF de programación - Guía para realizar compiladores

CASA ABIERTA AL TIEMPO

DIVISION DE CIENCIAS BASICAS E INGENIERIA

LIC E N CIA1 U RA E N C OM P UTACIO N

PROYECTO DE INVESTIGACION

144172

A U I A PARA REALKAR COMPILADORES

ALUMNO : AGUILAR CORNEJO MANUEL.

7

ASESOR : M. EN C. SERGiO PREZ RODEA.

ABRIL DE 1993.

INDICE

INDICE ..................................................... 1
CAPITULO I . BOSQUEJO GENERAL ...............................
2
1.1 introducción ...........................................
1.2 Las fases de un compilador .............................
2
1.2.1 Análisis léxico ..................................
4
1.2.2 Análisis sintáctico ..............................
5
1.2.3 Análisis semántica ...............................
5
1.2.4 Administración de la tabla de símbolos ........... 7
6
1.2.5 Detección e información de errores ............... 7
1.2.6 Generación de código intermedio .................. 8
1.2.7 Optimización de código ...........................
1.2.8 Generación de código .............................
CAPITULO I1 . ANALISIS LEXICO ...............................
12
2.1 Expresiones regulares ..................................
2.2 Definiciones regulares .................................
14
2.3 Autómatas ..............................................
18
2.4 LEX (Generador de analizadores léxicos) ................ 28
19
2.4.1 Algunos ejemplos de especificación para LEX ...... 31
2.4.2 Ejemplo de un analizador léxico .................. 36

9
9

3 8

CAPITULO I11 . ANALISIS SINTACTICO .........................
3.1 Gramáticas independientes del contexto ................. 38
3.2 Análisis sintáctico descendente ........................
3.2.1 Gramáticas LL(1) .................................
42
3.2.1.1 Cálculo del FIRST .......................
48
-50
gramáticas LL(1) .........................
3.2.1.2 Otras características de las
3.2.1.3 Cálculo del FOLLOW ....................... 55
54
3.3 Análisis sintáctico ascendente .........................
57
sintáctico por desplazamiento y reducción ........ 61
3.3.1 Implementación por medio de una pila de análisis
3.3.2 Conflictos durante el análisis sintáctico ........ 62
3.3.3 Algoritmo de análisis sintáctico LR(1) ........... 64
3.3.4 Construcción de tablas de análisis sintáctico .... 65
3.3.4.1 La operación cerradura ................... 66
3.3.4.2 La operación ir-a ........................
3.3.4.3 Tablas de análisis sintáctico LR ......... 70
3.4 YACC (Generador de analizadores sintácticos) ........... 72
3.4.1 Especificaciones básicas ......................... 73
3.4.2 Acciones .........................................
3.4.3 Ejemplos de una gramática completa ............... 78
75

68

1

-

.



l

l

l

l

l

l

l-.

l

-,

..........

*

. . . . . . . . . . . . . . .

L__-

.

.....

.........

5.1 Lenguaje ensamblador para el 8088-8086 ................. 93

5.2 Generando código .......................................g8
5.3 Ejemplo de un compilador completo . . . . . . . . . . . . . . . . . . . . . . 9 9

I#TRODüCCIO#

lenguaje, el lenguaje objeto (vease figura 1.1) . Como parte

A grandes rasgos, un compilador es un programa que lee un
programa escrito en un lenguaje fuente (lenguaje expresivo de
alto nivel), y lo traduce a un programa equivalente en otro
importante de este proceso de traducción, el compilador informa a
su usuario de la presencia de errores en el programa fuente.

(Lenguaje expresivo ---
Programa Fuente
de alto nivel).

Programa Objeto
(Lenguaje de bajo

nivel) .

Fig. 1.1 Función de un compilador.

Los compiladores a menudo se clasifican como de una pasada, de
multiples pasadas, de carga y ejecución, de depuración o de
optimización, dependiendo de como háyan sido construidos o de que
función depende que realizan. A pesar de esta aparente
complejidad, las tareas básicas que debe realizar cualquier
compilador son escencialmente las mismas. Al comprender tales
tareas, se pueden construir compiladores de gran diversidad de
lenguaje fuente y máquina objeto útilizando las mismas técnicas
básicas.

Nuestro conocimiento sobre como organizar y escribir
compiladores ha aumentado mucho desde que comenzaron a aparecer
los primeros compiladores a pricipios de los años cincuenta. Es
dificil dar una fecha exacta de la aparición de el primer
compilador, Por que en un principio gran parte de el 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 formulas
aritméticas a código máquina.

En la decada de 1950, se consideró a los compiladores como
programas notablemente difíciles de escribir. El primer
compilador de FORTRAN, por ejemplo, necesitó para su
implementación 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
implementación, entornos de programación y herramientas de
software (como generadores de analizadores léxicos y
sintácticos). Con estos avances, puede hacerse un compilador real
incluso como proyecto de estudio, en un curso sobre diseño de
compiladores.

3

En la compilación hay .dos partes: análisis y síntesis. La
parte del análisis divide al programa fuente en sus elementos
componentes y crea una representación intermedia del programa
fuente. La parte de la síntesis construye el programa objeto
deseado a partir de la representación intermedia. De las dos
partes, la síntesis es la que requiere las tecnicas más
especializadas. Se examinará el análisis y se esbozará la forma
de sintetizar el código objeto en un compilador estándar.

1.2 LAS FASES DE 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 1.2 se muestra una descomposición típica de
un compilador. En la práctica, se pueden agrupar algunas fases, y
las representaciones intermedias entre las fases agrupadas no
necesitan ser construidas explícitamente.

Programa Fuente

I
V

Analizador Léxico

I
V

1

!

Administrador
de la tabla
I I V
de símbolos

Analizador Semantic0

Manej ador

L

de

Errores

\t-------j

\

I

Optimizador de
Código Intermedio

.

/

r

4

Las tres primeras fases, forman la mayor parte de la porción
de análisis de un compilador. Otras actividades, la adquisición
de la tabla de 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,
optimización de código y generacíon de código. De modo informal
también se llamarán nfasesn al administrador de la tabla de
símbolos y al manejador de errores.

1.2.1 Análisis Léxico.
Análisis Lineal: análisis de cadenas de caracteres que
constituyen el programa fuente leyéndose de izquierda a derecha y
agrupándose en componentes léxicos, que son secuencias de
caracteres que tienen un significado colectivo.

En un compilador, el análisis lineal se llama análisis léxico
o exploración. Por ejemplo, en el análisis léxico los caracteres
de la proposición de asignación

posición := inicial + velocidad * 60

se agruparían en los componentes léxicos siguientes:
1.- El identificador posición.
2.- El símbolo de asignación :=.
3.- El identificador inicial.
4.- El signo de suma.
5.- El identificador velocidad.
6 . - El signo de multiplicación.
7 . - El nilmero 60.
Los espacios en blanco que separan los caracteres de estos
léxico .
componentes léxicos normalmente se eliminan durante el análisis

1.2.2 Análisis Sintáctico.

Análisis sintáctico implica agrupar los componentes léxicos de
el programa fuente en frases gramaticales que el compilador
utiliza para sintetizar la salida. Por lo general, las frases
gramaticales del programa fuente se representan mediante un árbol
de análisis sintáctico como el que se ilustra en la figura 1.3.
En la expresión I) inicial + velocidad * 60 I(, la frase

velocidad * 60 es una unidad lógica, por que las convenciones
usuales de las expresiones aritméticas indican que la
multiplicación se hace antes que la suma. Puesto que la expresión
va seguida de un *, no se agrupa en una
sÓ1a frase independiente en la figura 1.3

inicial + velocidad

5

proposición
de asignación

I
:=

1

identificador

pos 1 ción

expresión

i
I
+

expresión

identificador

1
I
I

expresión

\
I
*

inicial

expresión

7
I
I

expresión
número
I
velocidad

I

identificador

velocidad

Fig 1.3 Arbol de análisis sintáctico para una expresión

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ón1 y expresión2 son expresiones entonces también

lo son:

expresión1 + expresión2
expresión1 * expresión2
( expresión ) .

La división entre análisis léxico y análisis sintáctico es
algo arbitraria. Generalmente se elige una división que
simplifique la tarea completa de el análisis.

1.2.3 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