PDF de programación - Compiladores

Compiladores

Curso: 2001/2002
Alumna: Laura M. Castro Souto
Profesores: Bernardino Arcay Varela
José Carlos Dafonte Vázquez

Índice general

1. Introducción

7

2. Conceptos Básicos

2.1. Lenguajes y Gramáticas

9
. . . . . . . . . . . . . . . . . . . . . . . . . . . .
9
2.1.1. Definiciones . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
9
2.1.2. Gramáticas. Tipos
. . . . . . . . . . . . . . . . . . . . . . . . . . . 10
2.1.3. Lenguajes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
2.2. Gramáticas y Autómatas . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16
2.2.1. Autómatas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16
2.3. Traductores . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18
2.3.1. Esquemas de traducción . . . . . . . . . . . . . . . . . . . . . . . . 20

3. Análisis Léxico. Scanners

3.1. Construcción de scanners mediante AFs

21
. . . . . . . . . . . . . . . . . . . 23
3.1.1. Expresiones Regulares. Propiedades . . . . . . . . . . . . . . . . . . 23
3.1.2. Algoritmo (método) de Thompson . . . . . . . . . . . . . . . . . . . 23
3.1.3. Transformación de un AFND con λ-transiciones en AFD . . . . . . 23

4. Análisis Sintáctico. Parsers

27
4.1. Tipos de parsing
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27
4.2. Análisis por precedencia . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29
4.2.1. Precedencia Simple . . . . . . . . . . . . . . . . . . . . . . . . . . . 29
4.2.2. Precedencia Operador
. . . . . . . . . . . . . . . . . . . . . . . . . 31
4.3. Análisis sintáctico LL(K) . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32
4.3.1. Análisis LL(1) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32
4.4. Análisis sintáctico LR(K) . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35
4.4.1. Análisis LR(1) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36

5. Análisis Semántico

43
5.1. Notación . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 44
5.2. Sistemas de Tipos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 45
5.2.1. Tipos básicos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 45
5.2.2. Equivalencia de expresiones de tipo . . . . . . . . . . . . . . . . . . 48
5.2.3. Conversores de tipo . . . . . . . . . . . . . . . . . . . . . . . . . . . 49
5.2.4. Sobrecarga . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 49

3

4

ÍNDICE GENERAL

6. Código Intermedio

51
6.1. Notaciones . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 51
6.1.1. Notación Polaca Inversa (RPN) . . . . . . . . . . . . . . . . . . . . 52
6.1.2. Cuartetos
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 53
6.1.3. Tercetos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 53
6.1.4. Código a tres direcciones . . . . . . . . . . . . . . . . . . . . . . . . 54
6.2. Máquina Objeto . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 54
. . . . . . . . . . . . . . . . . . . . . . . . . . 55
. . . . . . . . . . . . . . . . 56
. . . . . . . . . . . . . . . . . . . . 56
. . . . . . . . . . . . . . . . . . . . . . . 57

6.2.1. Método de las Cajas
6.2.2. Generación y Representación de saltos
6.2.3. Acceso a elementos de matrices
6.2.4. Representación de strings

7. Optimización de Código

59
7.1. Técnicas de optimización en código fuente . . . . . . . . . . . . . . . . . . 59
. . . . . . . . . . . . 59
7.1.1. Reducción simple o Reducción de operaciones
7.1.2. Reacondicionamiento o Reordenamiento de instrucciones . . . . . . 60
7.1.3. Eliminación de redundancias . . . . . . . . . . . . . . . . . . . . . . 60
7.1.4. Reducción de potencias . . . . . . . . . . . . . . . . . . . . . . . . . 60
7.1.5. Reordenación de expresiones: Algoritmo de Nakata . . . . . . . . . 60
7.1.6. Extracción de invariantes . . . . . . . . . . . . . . . . . . . . . . . . 61
7.2. Análisis Global del Flujo de Datos . . . . . . . . . . . . . . . . . . . . . . . 61
7.2.1. Detección de lazos en los grafos de flujo . . . . . . . . . . . . . . . . 61
7.3. Análisis de Flujo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 63
7.3.1. Definiciones de Alcance . . . . . . . . . . . . . . . . . . . . . . . . . 63
7.3.2. Notación Vectorial
. . . . . . . . . . . . . . . . . . . . . . . . . . . 66
7.3.3. Solución Iterativa para las ecuaciones de Flujo de Datos
. . . . . . 67
7.3.4. Análisis de Expresiones Disponibles . . . . . . . . . . . . . . . . . . 67
7.3.5. Análisis de Variables Activas . . . . . . . . . . . . . . . . . . . . . . 68

8. Errores

71
8.1. Tipos de errores . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 71
8.2. Recuperación de errores
. . . . . . . . . . . . . . . . . . . . . . . . . . . . 71
8.2.1. Corrección de errores de cambio . . . . . . . . . . . . . . . . . . . . 72
8.2.2. Corrección de errores de borrado . . . . . . . . . . . . . . . . . . . 72
8.2.3. Corrección de errores de inclusión . . . . . . . . . . . . . . . . . . . 73
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 73

8.3. Modo pánico

9. La Tabla de Símbolos

75
9.1. Tipos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 75
9.1.1. TDS lineal . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 75
9.1.2. TDS ordenada . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 75
9.1.3. TDS árbol binario
. . . . . . . . . . . . . . . . . . . . . . . . . . . 75
9.1.4. TDS con hashing . . . . . . . . . . . . . . . . . . . . . . . . . . . . 76
9.1.5. TDS enlazadas
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 77

ÍNDICE GENERAL

5

10.Rep. de Información y Gestión de Memoria

79
10.1. Representación de la Información . . . . . . . . . . . . . . . . . . . . . . . 79
10.1.1. Representación de arrays y matrices . . . . . . . . . . . . . . . . . . 79
10.1.2. Representación de cadenas y tiras de caracteres
. . . . . . . . . . . 81
. . . . . . . . . . . . . . . . . . . . . . 81
10.1.3. Representación de registros
10.2. Gestión de memoria proporcionada por el compilador . . . . . . . . . . . . 81
10.2.1. Registro de activación . . . . . . . . . . . . . . . . . . . . . . . . . 82
10.2.2. Secuencia de llamada y retorno . . . . . . . . . . . . . . . . . . . . 82
10.2.3. Subprogramas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 83
10.2.4. Estructuras COMMON y EQUIVALENCE en FORTRAN . . . . . . . . . . . 84
10.3. Montadores y Cargadores
. . . . . . . . . . . . . . . . . . . . . . . . . . . 84
10.4. Ficheros objeto . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 85
10.5. Intérpretes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 85

6

ÍNDICE GENERAL

Capítulo 1

Introducción

La asignatura de Compiladores se divide en dos grandes bloques: análisis y sínte-

sis 1, cada uno de los cuales se estructura en diferentes partes, que veremos:

Figura 1.1: Esquema de las tareas de un compilador.

1Entre ambas tendrá lugar un parcial.

7

8

CAPÍTULO 1. INTRODUCCI ÓN

Capítulo 2

Lenguajes, Gramáticas, Autómatas y
Traductores

2.1. Lenguajes y Gramáticas

2.1.1. Definiciones

Sea A = {a, b, c, d, e} un alfabeto (conjunto de caracteres). Llamamos:
√

Tira de caracteres o palabra a cualquier concatenación de caracteres del alfabeto:
α = abc.

√

√

√

√

Distancia o longitud de una tira al número de elementos (caracteres) de la tira:
α = 3. La tira nula es la tira de distancia 0 y suele representarse por ε o λ.

Potencia de una tira a la tira que resulta de yuxtaponer una consigo misma n
veces: para α = ab se tiene α0 = λ, α1 = ab, λ2 = abab, αn = ab . . . ab

. Es decir:



con A0 = λ.

An = An−1 · A

nveces

La potencia deriva del producto cartesiano: A · B = {xy/x ∈ A ∧ y ∈ B}.

Cierre transitivo a: A+ =

Ai

Cierre reflexivo a: A∗ =

Ai



i>0

i0

De lo anterior se deduce que A∗ = A+ ∪ {λ}.

demostración:
A∗ =



i0

Ai = A0 ∪



Ai



i>0

= A+ ∪ {λ}

= {λ} ∪



i>0



Ai

9

10

CAPÍTULO 2. CONCEPTOS B ÁSICOS

2.1.2. Gramáticas. Tipos

Una gramática es una upla G = (N ,T ,P,S), donde

N conjunto de símbolos no terminales

T conjunto de símbolos terminales

P conjunto de producciones

S axioma de la gramática

Según la forma de sus reglas de producción, Chomsky clasificó las gramáticas en cuatro

tipos :

Gramáticas Tipo 0: con estructura de frase, se caracterizan porque los elementos de
P son de la forma α → β con α ∈ (N ∪ T )+ y β ∈ (N ∪ T )
∗
. Son las gramáticas
más generales (admiten producciones de cualquier tipo) y se asocian con autómatas
bidireccionales.

Gramáticas Tipo 1 o sensibles al contexto: sus producciones son de la forma αAβ →
; A ∈ N ; γ ∈ (N ∪ T )+. En estas gramáticas, la sustitu-
αγβ con α, β ∈ (N ∪ T )
∗
ción de un no terminal por una cadena depende de los símbolos que tenga alrededor
(contexto).

con A ∈ N y α ∈ (N ∪ T )
∗

Gramáticas Tipo 2 o de contexto libre: los elementos de P son de la forma A → α
. Son las que se usan para lenguajes de programación.
Gramáticas Tipo 3 o regulares: sus producciones son siempre A → αB o A → α, con

A, B ∈ N y α ∈ T . Se asocian con autómatas finitos.

Las más importantes para nosotros serán las gramáticas de tipo 3 o gramáticas regu-
lares, ya que derivan conjuntos regulares que representaremos por medio de autómatas
finitos y nos ayudarán a construir analizadores léxicos (scanners). Las gramáticas de tipo
2 o gramáticas independientes del contexto harán lo propio cuando nos ocupemos del
análisis sintáctico (parsers).

Definición

Llamamos derivación α ⇒ β al conjunto de producciones que nos llevan de α a β:

α = δAµ
β = δγµ

y ∃A → γ ∈ P

Tambié