compiladores

Análisis y Diseño de Compiladores
Emiliano Llano Díaz

El autor y Exa Ingeniería ®no están afiliados a ningún fabricante.
Se han realizado todos los esfuerzos posibles para proveer una información veraz y completa. Sin embargo, el
autore no se hace responsables de omisiones, uso al que se destine la información o por infracciones a patentes
u otros derechos de terceros que resulten.Derechos Reservados ©por el autor 2002. Derechos mundiales reservados. Ninguna parte de esta publicación
puede ser reproducida o almacenada en ningún medio de retransmisión, fotocopiado o reproducción de ningún
tipo, incluyendo pero no limitándose a fotocopia, fotografía, fax, almacenamiento magnético u otro registro,
sin permiso expreso del autor y de la editorial.
Compuesto totalmente encomputadora por:
Exa Ingeniería SA de CV ®
Bajío 287-101
Col. Roma México, D.F.
5564-10-11 5564-02-68 FAX 5264-61-08

ISBN 970-91050-0-0
SEP 10137/91
Registrado ante la SEP en la propiedad intelectual del autor

Impreso y hecho en México.
1era edición junio 2002.

Contenido
Introducción

xi

1. Compiladores

1-1

1.1 Objetivos

1-1

1.2 Compiladores

1-1

1.2.1 Análisis ySíntesis

1.3 El Análisis

1-4

1-6

1.3.1 Análisis Léxico

1-7

1.3.2 Análisis de Sintaxis

1-7

1.3.3 Análisis Semántico

1-8

1.4 Fases de un Compilador

1-9

1.4.1 Tabla de Símbolos

1-9

1.4.2 Detección de errores

1-9

1.4.3 La fase de Análisis

1-10

1.5 Programas auxiliares

1-12

1.5.1 Preprocesadores

1-12

1.5.2 Ensambladores

1-12

1.5.3Ensambladores de dos pasos

1-13

1.5.4 Cargadores y ligadores

1-13

1.6 Agrupamiento de Fases

1-13

1.6.1 Parte Inicial y Final

1-13

1.6.2 Pasos

1-14

1.6.2.1 Reducir el número de pasos

1-14

1.7 Herramientas de Construcción

1-15

1.7.1 Modelo de un compilador

1-15

1.7.2 Relaciones entre las partes de un compilador

1-19

1.7.3 Errores

1-20

1.8Bibliografía

1-21

i

Análisis y Diseño de Compiladores

Emiliano Llano Díaz

2. Gramáticas

2-1

2.1 Objetivos

2-1

2.2. Gramática Generativa

2-1

2.3 Gramática

2-3

2.3.1 Alfabeto y cadenas

2-4

2.3.2 No terminales y Producciones

2-5

2.3.3 Ejemplos

2-5

2.4 Jerarquías de Chomsky

2-7

2.5 La gramática y su máquinas

2-8

2.5.1 Máquina de Turing2-8

2.5.2 Autómata lineal restringido

2-9

2.5.3 Autómata con pila

2-10

2.5.4 Eliminando las Producciones Vacías

2-10

2.5.5 Gramática libre de contexto y sensitiva al contexto

2-11

2.5.6 Autómatas de Estado Finito

2-11

2.6 Cadenas vacías y Lenguajes vacíos

2-12

2.7 Derivaciones Canónicas

2-12

2.8 Ambigüedades

2-14

2.9 Pensando en formagramatical

2-14

2.9.1 Los límites de los autómatas de estado finito

2-15

2.9.2 Contando en una gramática libre de contexto

2-15

2.9.3 Sensibilidad al contexto

2-17

2.10 Algunos Ejemplos de Gramáticas

2-18

2.11 Notación BNF

2-18

2.12 Notación BNF Extendida

2-20

2. 13 Bibliografía

2-21

3. Diseño de Lenguajes

3-1

3.1 Objetivos
3.2 Introducción

ii3-1
3-1

Contenido

3.3 Análisis del problema

3-1

3.4 Consideraciones Preliminares

3-2

3.5 Fuente de ideas

3-3

3.6 Metas y filosofías del diseño del lenguaje de programación

3-5

3.6.1 Comunicación humana

3-5

3.6.2 Prevención y corrección de errores

3-6

3.6.3 Utilidad

3-8

3.6.4 Efectividad

3-8

3.6.5 Grado de compilación

3-9

3.6.6 Eficiencia3-9

3.6.7 Independencia de la máquina

3-10

3.6.8 Simplicidad

3-11

3.6.9 Uniformidad

3-11

3.6.10 Ortogonalidad

3-12

3.6.11 Generalización y especialización

3-12

3.6.12 Otras filosofías de diseño

3-12

3.7 Diseño detallado

3-13

3.7.1 Microestructura

3-13

3.7.2 Estructuras de las Expresiones

3-14

3.7.3 Estructuras de datos

3-15...