PDF de programación - Notas para la Materia de Compiladores

Notas para la Materia de Compiladores

José Antonio Camarena Ibarrola

Marzo de 2008

2

Índice general

1. Introducción

5
6
1.1. Objetivo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
6
1.2. Justificación . . . . . . . . . . . . . . . . . . . . . . . . . . . .
6
1.3. Usuarios . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
7
1.4. Definiciones . . . . . . . . . . . . . . . . . . . . . . . . . . . .
8
1.5. El Análisis Léxico . . . . . . . . . . . . . . . . . . . . . . . . .
9
1.6. El Análisis Sintáctico . . . . . . . . . . . . . . . . . . . . . . .
9
1.7. El Análisis Semántico . . . . . . . . . . . . . . . . . . . . . . .
1.8. Generador de Código Intermedio
9
. . . . . . . . . . . . . . . .
1.9. El Optimizador de Código . . . . . . . . . . . . . . . . . . . . 10
1.10. La Tabla de Símbolos . . . . . . . . . . . . . . . . . . . . . . . 10
. . . . . . . . . . . . . . . . . . . . . . . . 10
1.11. Manejo de Errores

2. Análisis Léxico

11
2.1. Construcción de Analizadores Léxicos . . . . . . . . . . . . . . 11
2.2. El Generador de Analizadores lexicos: lex . . . . . . . . . . . . 13

3. Análisis Sintáctico

17
3.1. Análisis Sintáctico Descendente . . . . . . . . . . . . . . . . . 17
3.1.1. Parser descendente recursivo . . . . . . . . . . . . . . . 18
3.1.2. Parser predictivo descendente para gramáticas LL(1)
. 19
3.2. Análisis Sintáctico Ascendente . . . . . . . . . . . . . . . . . . 32
3.2.1. Parsers LR . . . . . . . . . . . . . . . . . . . . . . . . 33
3.3. El generador de analizadores sintácticos: yacc . . . . . . . . . 41

3

4

ÍNDICE GENERAL

Capítulo 1

Introducción

Escribir un compilador es normalmente el primer gran Sistema de Soft-
ware que un estudiante de Ingeniería en Computación desarrolla y requiere
conocimientos de las siguientes áreas:

Programación de Computadoras

Arquitectura de Computadoras

Teoría de Autómatas y Lenguajes Formales

Ingeniería de Software

Programación de Sistemas

El estudiante requiere entonces toda la ayuda posible. Estas Notas fueron
escritas con el ánimo de facilitar la compresión de las técnicas que se utilizan
para desarrollar las partes de un compilador que son el analizador lexicográfi-
co, el analizador sintático, el generador de código intermedio y el optimizador
de código. Hasta el momento, estas notas se centran en los dos primeros
módulos pero incluyen una introducción a las valiosas herramientas conoci-
das como lex y yacc (o sus clones conocidos como flex y bison), este último
no solo es útil en el análisis sintáctico sino en la generación de código.

5

6

CAPÍTULO 1. INTRODUCCI ÓN

1.1. Objetivo

Proveer al alumno con principios y técnicas útiles para la construcción
de Compiladores. El alumno deberá ser capaz de implementar la traducción
de un lenguaje de programación de alto nivel al lenguaje de máquina de un
computador.

1.2. Justificación

El estudiante debe aprender como implementar compiladores utilizando

la tecnología actual, estas notas deberán serle de gran ayuda.

1.3. Usuarios

Estudiantes de Ingeniería en COmputación de la Facultad de Ingeniería

Eléctrica

1.4. DEFINICIONES

1.4. Definiciones

7

Un compilador es un TRADUCTOR de un lenguaje de programación de
alto nivel a un lenguaje ensamblador el cual será traducido a su vez a código
objeto por algún ensamblador [1], [2], [3]. El conjunto de compiladores es
un subconjunto del producto cartesiano del conjunto de Lenguajes de alto
nivel, el conjunto de computadoras y el conjunto de sistemas operativos. Por
Ejemplo el compilador de C++ para McCintosh en ambiente Linux se podría
representar por:

(C++,MAC,Linux)
Otros ejemplos podrían ser:
(Modula2,PC,DOS), (Pascal,Risc,Unix), (Java,Sun,OS/2), Etc....
Para colmo, se generan versiones nuevas frecuentemente de compiladores
ya existentes. Esto quiere decir que hay mucha gente el mundo trabajando
en el desarrollo de los compiladores. El primer compilador de Fortran IV
requirió de trabajo en equipo durante casi quince años. Sin embargo, ahora
se cuenta con muchas herramientas CASE para el desarrollo de compiladores,
así como bases matemáticas y toda una tecnología que por cierto se utiliza
también para el desarrollo de otro tipo de software como:

Editores de Ecuaciones (Ej TEX)

CAD’s de Electrónica (Ej OrCAD)

Parser de Consultadores de BD (Ej SQL)

Compilación de Textos (Ej Latex)

Editores de código fuente

Impresores de Código fuente

Traductores de lenguajes formales

Un compilador tiene básicamente dos etápas:

1. La etapa de análisis del código fuente

2. La de Síntesis de código Ensamblador

8

CAPÍTULO 1. INTRODUCCI ÓN

La tecnología desarrollada para la etapa de análisis de código fuente se
utiliza también en software como: Editores e impresores de Código fuente,
Verificadores de software y también en Intérpretes. La etapa del análisis con-
sta de tres partes o fases:

1. El analizador léxico

2. El analizador sintáctico

3. El analizador semántico

La etapa de síntesis también consta de tres partes:

1. El generador de código intermedio

2. El optimizador de código

3. El generador de código

Adicionalmente se debe de contar con dos partes más, las cuales no for-
man una etapa en sí sino que se utilizan a lo largo de las diversas fases del
compilador. Estas son:

1. El administrador de tabla de símbolos

2. El manejador de errores

1.5. El Análisis Léxico

Se conoce también como análisis lineal debido a que se trata de un bar-
rido secuencial del código fuente. La función de un analizador léxico es la
de identificar a los elementos sintácticos básicos del lenguaje los cuales son
indivisibles y a los que llamamos tokens. El anallizador debe de ignorar car-
acteres blancos (espacios, tabuladores y retornos de carro) y reconocer a la
cadena mas larga de caracteres que forme un token válido. Por ejemplo, debe
decidir que la cadena “for3” es un token del tipo identificador y no dos iden-
tificadores del tipo palabra reservada (for) seguida de otro token del tipo
constante entera (3). El analizador léxico entrega el tipo de token de que
se trata mediante una constante predeterminada y la cadena leída a la cual
por cierto llamamos lexema. Una manera preferida de entregar el lexema es
insertándolo en una tabla conocida como “Tabla de símbolos” y entregando
la posición que el lexema ocupa en esa tabla. El analizador léxico es llamado
por el analizador sintáctico cada vez que este requiere de otro token.

1.6. EL AN ÁLISIS SINT ÁCTICO

9

1.6. El Análisis Sintáctico

Se conoce también como análisis jerárquico debido a que convierte una
secuencia de tokens en un árbol de sintaxis el cual es como sabemos una
estructura jerárquica. Algunos compiladores construyen realmente el árbol,
esto puede ser útil para la fase de optimización, otros en cambio, solamente
llevan el registro de en que parte del árbol se encuentran.

La división entre el análisis léxico y el sintáctico es un tanto arbitraria, un
buen criterio para dividirlos consiste en decidir si determinada construcción
requiere recursividad o no. Por ejemplo, para reconocer identificadores no se
necesita la recursión, basta con autómatas finitos, sin embargo, con estos no
sería posible analizar expresiones matemáticas o sentencias estructuradas.

1.7. El Análisis Semántico

Verifica si tiene sentido el programa fuente, es en esta fase en donde se
hace la verificación de tipos, algunos analizadores semánticos convierten el
dato de menor precisión al de mayor precisión con el que se está realizando
alguna operación, otros marcan conflicto de tipos. Pero todos deben marcar
error si se utiliza un flotante como exponente de un arreglo por poner un
ejemplo.

1.8. Generador de Código Intermedio

Esta fase del compilador no es en realidad una parte separada del compi-
lador, la mayoría de los compiladores generan código como parte del proceso
de análisis sintáctico, esto es debido a que requieren del árbol de sintaxis
y si este no va a ser construido físicamente, entonces deberá acompañar al
analizador sintáctico al barrer el árbol implícito. En lugar de generar código
ensamblador directamente, los compliadores generan un código intermedio
que es más parecido al código ensamblador, las operaciones por ejemplo nun-
ca se hacen con más de dos operandos. Al no generarse código ensamblador
el cual es dependiente de la computadora específica, sino código intermedio,
se puede reutilizar la parte del compilador que genera código intermedio en
otro compilador para una computadora con diferente procesador cambiando
solamente el generador de código ensamblador al cual llamamos back-end, la
desventaja obviamente es la lentitud que esto conlleva.

10

CAPÍTULO 1. INTRODUCCI ÓN

1.9. El Optimizador de Código

Debe al menos eliminar código que no hace nada así como variables no
referenciadas. Un buen optimizador de código debe modificar la manera co-
mo se pretende implementar un algoritmo para que este sea ejecutado más
eficientemente, los optimizadores de código pueden configurarse para optar
por ahorro de memoria o por ahorro de tiempo de procesador.

1.10. La Tabla de Símbolos

tiene información acerca de los identificadores que aparecen en el pro-
grama, como el tipo de identificador (nombre de función, nombre de una
variable, etc. ), la memoria asignada, el ámbito o alcance del mismo, etc.

El analizador léxico introduce registros en la tabla de símbolos pero deja
en blanco campos cuya contenido no se puede determinar durante el análisis
lineal, estos serán llenados y/o utilizados por las fases restantes

1.11. Manejo de Errores

Un compilador que se detiene al encontrar el primer error no es de mucha
utilidad. Así pues, es necesario que el compilador sea capaz de recuperarse de
los errores encontrados y de proporcionar mayor información que conduzca
a la fácil reparación de los mismos, de hecho el compila