Analisi-diseño-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. DerechosReservados ©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 en computadorapor: 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 1. Compiladores
1.1 Objetivos 1.2 Compiladores
1.2.1 Análisis y Síntesis

xi 1-1
1-1 1-1
1-4

1.3 ElAnálisis
1.3.1 Análisis Léxico 1.3.2 Análisis de Sintaxis 1.3.3 Análisis Semántico

1-6
1-7 1-7 1-8

1.4 Fases de un Compilador
1.4.1 Tabla de Símbolos 1.4.2 Detección de errores 1.4.3 La fase de Análisis

1-9
1-9 1-9 1-10

1.5 Programas auxiliares
1.5.1 Preprocesadores 1.5.2 Ensambladores 1.5.3 Ensambladores de dos pasos 1.5.4 Cargadores y ligadores

1-12
1-12 1-12 1-13 1-13

1.6Agrupamiento de Fases
1.6.1 Parte Inicial y Final 1.6.2 Pasos 1.6.2.1 Reducir el número de pasos

1-13
1-13 1-14 1-14

1.7 Herramientas de Construcción
1.7.1 Modelo de un compilador 1.7.2 Relaciones entre las partes de un compilador 1.7.3 Errores

1-15
1-15 1-19 1-20

1.8 Bibliografía

1-21

i

Análisis y Diseño de Compiladores

Emiliano Llano Díaz

2. Gramáticas
2.1 Objetivos2.2. Gramática Generativa 2.3 Gramática
2.3.1 Alfabeto y cadenas 2.3.2 No terminales y Producciones 2.3.3 Ejemplos

2-1
2-1 2-1 2-3
2-4 2-5 2-5

2.4 Jerarquías de Chomsky 2.5 La gramática y su máquinas
2.5.1 Máquina de Turing 2.5.2 Autómata lineal restringido 2.5.3 Autómata con pila 2.5.4 Eliminando las Producciones Vacías 2.5.5 Gramática libre de contexto y sensitiva al contexto 2.5.6Autómatas de Estado Finito

2-7 2-8
2-8 2-9 2-10 2-10 2-11 2-11

2.6 Cadenas vacías y Lenguajes vacíos 2.7 Derivaciones Canónicas 2.8 Ambigüedades 2.9 Pensando en forma gramatical
2.9.1 Los límites de los autómatas de estado finito 2.9.2 Contando en una gramática libre de contexto 2.9.3 Sensibilidad al contexto

2-12 2-12 2-14 2-14
2-15 2-15 2-17

2.10 Algunos Ejemplos de Gramáticas 2.11Notación BNF 2.12 Notación BNF Extendida 2. 13 Bibliografía

2-18 2-18 2-20 2-21

3. Diseño de Lenguajes
3.1 Objetivos 3.2 Introducción

3-1
3-1 3-1

ii

Contenido

3.3 Análisis del problema 3.4 Consideraciones Preliminares 3.5 Fuente de ideas 3.6 Metas y filosofías del diseño del lenguaje de programación
3.6.1 Comunicación humana 3.6.2 Prevención y corrección de errores 3.6.3Utilidad 3.6.4 Efectividad 3.6.5 Grado de compilación 3.6.6 Eficiencia 3.6.7 Independencia de la máquina 3.6.8 Simplicidad 3.6.9 Uniformidad 3.6.10 Ortogonalidad 3.6.11 Generalización y especialización 3.6.12 Otras filosofías de diseño

3-1 3-2 3-3 3-5
3-5 3-6 3-8 3-8 3-9 3-9 3-10 3-11 3-11 3-12 3-12 3-12

3.7 Diseño detallado
3.7.1 Microestructura 3.7.2 Estructuras de las Expresiones 3.7.3Estructuras de datos 3.7.3.1 Tipos simples 3.7.3.1.1 Tipos numéricos 3.7.3.1.2 Tipo carácter 3.7.3.1.3 Tipo Lógico 3.7.3.2 Tipos compuestos 3.7.3.2.1 Arreglos 3.7.3.2.2 Registros 3.7.3.2.3 Conjunto 3.7.3.2.4 Apuntadores 3.7.3.3 Tipos complejos 3.7.4 Estructuras de Control

3-13
3-13 3-14 3-15 3-16 3-16 3-16 3-17 3-17 3-17 3-17 3-18 3-18 3-18 3-19

iii

Análisis y Diseño de Compiladores...