Libro Técnico Compiladores - Teoría E Implementación

Descripción

Compiladores - teoría e implementación
Autor: RUIZ, Jacinto
Páginas: 448
ISBN: 978-607-7854-68-5
Coedición: Alfaomega, RC Libros

Este libro es un manual de ayuda para estudiosos de procesadores de lenguajes y/o compiladores, trata de la construcción de un compilador paso a paso, desde la especificación del lenguaje hasta la generación del código final (generalmente, un ejecutable), un tema que está poco tratado, sobre todo en español.
Lo que pretendemos con este libro es dar las bases teóricas suficientes para poder abordar la construcción de un compilador completo, y luego implementarlo.
Ventajas Competitivas

En la parte teórica se detallan todas las fases para la creación de un procesador de lenguajes, y además se incluyen ejercicios que ayudan a aclarar las ideas expuestas.
La parte práctica desarrolla por completo un traductor para un lenguaje sencillo de lógica de proposiciones. Asimismo, se implementan dos compiladores, ambos desarrollados por completo, de un subconjunto del lenguaje C; el primero de ellos, sencillo para iniciarse, y el segundo, más completo que sirve para avanzar en el tema; es decir, que se trata desde el análisis léxico hasta la generación de código final (utilizando un emulador de ensamblador llamado Ens2001).
Con este libro el estudiante y el profesional estará preparado no solo para entender mejor el complejo mundo de los compiladores, sino también de los lenguajes de programación y de las máquinas donde se aplican.
Utilizando las técnicas aprendidas los lectores podrán desarrollar sus propios compiladores o traductores, por ejemplo, para un microcontrolador PIC.

Conozca

Los aspectos teóricos de los procesadores de lenguajes y/o compiladores.
El proceso de creación de un compilador: análisis léxico, análisis sintáctico, análisis sintáctico descendente, análisis sintáctico ascendente, la tabla de tipos y de símbolos, análisis semántico y la generación de código intermedio y final.

Realice

Un traductor para un lenguaje de lógica de proposiciones.
Un compilador para un subconjunto de C.

Índice
Agradecimientos .................................................................................................. XVII
Prólogo ..................................................................................................................... XIX
Parte I. Teoría
Capítulo 1. Introducción ............................................................................................ 3
1.1 Definición de compilador .................................................................... 3
1.2 Estructura de un compilador .............................................................. 5
1.2.1 Análisis léxico ................................................................................. 7
1.2.2 Análisis sintáctico .......................................................................... 8
1.2.3 Análisis semántico ......................................................................... 9
1.2.4 Generación de código intermedio ............................................. 10
1.2.5 Generación de código final ......................................................... 13
1.2.6 Tablas de símbolos y de tipos .................................................... 13
1.2.7 Manejo de errores ........................................................................ 14
1.3 Fases del proceso de compilación ..................................................... 14
1.4 Herramientas y descripción del lenguaje ....................................... 16
Capítulo 2. Análisis léxico ...................................................................................... 17
2.1 Utilidad del análisis léxico ................................................................. 17
2.2 Funcionamiento .................................................................................. 18
2.3 Términos utilizados ............................................................................ 21
2.4 Especificación del analizador léxico ................................................. 22
2.5 Construcción de un analizador léxico .............................................. 23
COMPILADORES
VIII
2.5.1 Identificar las palabras reservadas ........................................... 23
2.5.2 Construir el diagrama de transiciones ..................................... 24
2.6 Ejercicios resueltos ............................................................................. 27
Ejercicio 2.1 ........................................................................................... 27
Ejercicio 2.2 ........................................................................................... 30
Capítulo 3.Análisis sintáctico ................................................................................ 33
3.1 Funciones del analizador sintáctico ................................................ 33
3.2 Diseño de gramáticas ........................................................................ 35
3.3 Dificultades para la creación de gramáticas ................................... 38
3.3.1 La recursividad ............................................................................ 38
3.3.2 La ambigüedad ............................................................................ 39
3.3.3 La asociatividad .......................................................................... 40
3.3.4 La precedencia ............................................................................. 41
3.3.5 La parentización .......................................................................... 41
3.4 Análisis sintáctico lineal .................................................................... 41
3.5 Diagramas de sintaxis ....................................................................... 42
3.6 Ejercicios resueltos ............................................................................. 46
Ejercicio 3.1 ........................................................................................... 46
Ejercicio 3.2 ........................................................................................... 47
Ejercicio 3.3 ........................................................................................... 48
Capítulo 4. Análisis sintáctico descendente ....................................................... 51
4.1 Introducción ........................................................................................ 51
4.2 Analizadores sintácticos predictivos ............................................... 54
4.3 Conjuntos de predicción y gramáticas LL(1) ................................. 55
4.3.1 Conjunto de primeros ................................................................. 56
4.3.2 Conjunto de siguientes ............................................................... 59
4.3.3 Conjunto de predicción y gramáticas LL(1) ............................ 60
4.4 Conversión a gramáticas LL(1) ........................................................ 64
4.4.1 Eliminación de la factorización por la izquierda .................... 65
4.4.2 Eliminación de la recursividad por la izquierda .................... 66
4.5 Analizadores sintácticos descendentes recursivos (ASDR) ......... 68
4.6 Implementación de ASDP’s .............................................................. 68
4.6.1 Construcción de la tabla de análisis ......................................... 69
© Alfaomega - RC Libros
ÍNDICE
IX
4.6.2 Algoritmo de análisis .................................................................. 71
4.7 Ejercicios resueltos .............................................................................. 74
Ejercicio 4.1 ............................................................................................ 74
Ejercicio 4.2 ............................................................................................ 75
Capítulo 5. Análisis sintáctico ascendente ........................................................... 79
5.1 Introducción ........................................................................................ 79
5.2 Algoritmo de desplazamiento y reducción ..................................... 80
5.2.1 Acción ACEPTAR ........................................................................ 82
5.2.2 Acción RECHAZAR .................................................................... 82
5.2.3 Método GOTO .............................................................................. 82
5.2.4 Acción REDUCIR ......................................................................... 82
5.2.5 Acción DESPLAZAR ................................................................... 82
5.2.6 Ejemplo de aplicación del algoritmo de desplazamiento
y reducción ............................................................................................ 82
5.3 Construcción de tablas de análisis sintáctico SLR .......................... 85
5.3.1 Elemento ....................................................................................... 85
5.3.2 Cierre o clausura .......................................................................... 86
5.3.3 Operación ir_a .............................................................................. 87
5.3.4 Construcción de la colección canónica de conjuntos de
elementos ............................................................................................... 87
5.3.5 Construcción de un autómata a partir de la colección
canónica .................................................................................................. 91
5.3.6 Construcción de la tabla de análisis a partir de un
autómata ................................................................................................ 92
5.3.7 Conflictos en las tablas SLR ........................................................ 95
5.4 Organigrama de las gramáticas ........................................................ 96
5.5 Ejercicios resueltos .............................................................................. 98
Ejercicio 5.1 ............................................................................................ 98
Ejercicio 5.2 .......................................................................................... 100
Capítulo 6. Tabla de tipos y de símbolos ........................................................... 105
6.1 Introducción ...................................................................................... 105
6.2 La tabla de tipos ................................................................................ 105
6.2.1 Implementación de la tabla de tipos ....................................... 108
© Alfaomega - RC Libros
COMPILADORES
X
6.2.2 Implementación de una tabla de tipos única ........................ 110
6.2.3 Implementación de una pila de tablas de tipos .................... 119
6.2.4 Dimensión y acceso a los elementos de los tipos ................. 123
6.3 La tabla de símbolos ........................................................................ 126
6.4 Ejercicios resueltos ........................................................................... 130
Ejercicio 6.1 ......................................................................................... 130
Capítulo 7. Análisis semántico ............................................................................ 137
7.1 Introducción ...................................................................................... 137
7.2 Atributos y acciones semánticas .................................................... 138
7.3 Tipos de atributos ............................................................................ 143
7.4 Notaciones para la especificación de un traductor ..................... 145
7.4.1 Definición dirigida por sintaxis (DDS) .................................. 145
7.4.2 Esquema de traducción (ETDS) .............................................. 147
7.5 Comprobaciones semánticas .......................................................... 150
7.6 Ejercicios resueltos ........................................................................... 151
Ejercicio 7.1 ......................................................................................... 151
Ejercicio 7.2 ......................................................................................... 153
Ejercicio 7.3 ......................................................................................... 154
Capítulo 8. Generación de código intermedio y final ..................................... 155
8.1 Introducción ...................................................................................... 155
8.2 Tipos de código intermedio ............................................................ 157
8.2.1 Código de tres direcciones ....................................................... 157
8.2.2 Código de máquina virtual de pila ........................................ 158
8.2.3 Operadores sobrecargados ...................................................... 159
8.3 Código intermedio para expresiones ............................................ 159
8.4 Código intermedio para asignaciones .......................................... 163
8.5 Sentencias de entrada y salida ....................................................... 165
8.6 Sentencia condicional ...................................................................... 165
8.7 Iteración tipo while .......................................................................... 169
8.8 Iteración tipo repeat-until y do-while ........................................... 171
8.9 Iteración tipo for ............................................................................... 172
8.10 La selección ..................................................................................... 174
8.11 Código intermedio para vectores ................................................ 175
© Alfaomega - RC Libros
ÍNDICE
XI
8.12 Código intermedio para registros ................................................ 178
8.13 Espacio de direcciones ................................................................... 179
8.14 Registro de activación (RA) ........................................................... 184
8.15 Secuencia de acciones en subprogramas no recursivos ............ 186
8.16 Secuencia de acciones en subprogramas recursivos .................. 198
8.16.1 Compilación del cuerpo del subprograma ........................... 203
8.16.2 Compilación de la llamada al subprograma ........................ 205
8.17 Secuencia de acciones en subprogramas locales ........................ 216
8.17.1 Encadenamiento de accesos ................................................... 217
8.17.2 Display ...................................................................................... 218
Parte II. Implementación de L-0
Capítulo 9. Especificación de L-0 ......................................................................... 221
9.1 Introducción ...................................................................................... 221
9.2 Instrucciones ...................................................................................... 222
9.3 Variables lógicas ............................................................................... 222
9.4 Operadores ........................................................................................ 223
9.5 Expresiones ........................................................................................ 223
9.6 Ejemplo de programa válido ........................................................... 223
Capítulo 10. Análisis léxico de L-0 ...................................................................... 225
10.1 Preparativos ..................................................................................... 225
10.2 Patrones ............................................................................................ 226
10.3 Tokens válidos ................................................................................. 226
Capítulo 11.Análisis sintáctico de L-0 ................................................................. 229
11.1 Preparativos ..................................................................................... 229
11.2 Inicialización y arranque ............................................................... 230
11.3 Situación de terminales y no terminales ...................................... 232
11.4 Sentencias ......................................................................................... 233
11.5 Expresiones ...................................................................................... 234
11.6 Asignación ....................................................................................... 235
11.7 Sentencias de escritura ................................................................... 235
© Alfaomega - RC Libros
COMPILADORES
XII
11.8 Tablas de verdad ............................................................................ 236
11.9 Funciones ........................................................................................ 236
Capítulo 12. Análisis semántico y generación de código de L-0 ................... 237
12.1 Preparativos .................................................................................... 237
12.2 Tabla de símbolos .......................................................................... 237
12.3 Tratamiento de expresiones ......................................................... 240
12.3.1 La función tautología ............................................................... 242
12.3.2 La función contradicción .......................................................... 244
12.3.3 La función decidible .................................................................. 244
12.4 Operaciones con tablas de verdad ............................................... 245
12.5 La asignación .................................................................................. 247
12.6 Operaciones de impresión ............................................................ 248
Parte III. Implementación de C-0
Capítulo 13. Especificación de C-0 ..................................................................... 253
13.1 Introducción .................................................................................... 253
13.2 Tokens .............................................................................................. 253
13.3 Constantes ....................................................................................... 254
13.4 Operadores y delimitadores ......................................................... 254
13.5 Identificadores y palabras reservadas ......................................... 254
13.6 Tipos de datos ................................................................................. 255
13.7 Sentencias de control de flujo ....................................................... 255
13.8 Instrucciones de entrada-salida ................................................... 255
13.9 Declaración de variables ............................................................... 255
13.10 Programa principal ...................................................................... 255
13.11 Sentencia if-then-else ................................................................... 255
13.12 Sentencia while ............................................................................. 256
13.13 Ejemplo de programa válido ...................................................... 256
Capítulo 14. Análisis léxico, sintáctico y semántico de C-0 ........................... 257
14.1 Análisis léxico ................................................................................. 257
14.2 Análisis sintáctico .......................................................................... 258
14.3 Análisis semántico ......................................................................... 263
© Alfaomega - RC Libros
ÍNDICE
XIII
Capítulo 15. Generación de código intermedio de C-0 .................................... 269
15.1 Introducción .................................................................................... 269
15.2 Código de tres direcciones ............................................................. 270
15.3 Espacio de direcciones ................................................................... 273
15.4 Asignación de direcciones a variables ......................................... 274
15.5 Asignación de direcciones a expresiones y condiciones ........... 275
15.6 CI de expresiones ............................................................................ 280
15.7 CI de condiciones ............................................................................ 283
15.8 CI de asignación .............................................................................. 284
15.9 CI de bloques if-then-else .............................................................. 286
15.10 CI de bloques while ...................................................................... 289
15.11 CI de putw ..................................................................................... 290
15.12 CI de puts ....................................................................................... 291
Capítulo 16. Generación de código final de C-0 ............................................... 297
16.1 Introducción .................................................................................... 297
16.2 Preparativos ..................................................................................... 297
16.3 Introducción a Ens2001 .................................................................. 298
16.4 CARGAR_DIRECCION op1 null res ........................................... 300
16.5 CARGAR_VALOR op1 null res .................................................... 301
16.6 SUMAR op1 op2 res ....................................................................... 301
16.7 RESTAR op1 op2 res ...................................................................... 302
16.8 MULTIPLICAR op1 op2 res .......................................................... 302
16.9 DIVIDIR op1 op2 res ...................................................................... 302
16.10 OR op1 op2 res .............................................................................. 302
16.11 AND op1 op2 res .......................................................................... 302
16.12 MAYOR op1 op2 res ..................................................................... 303
16.13 MENOR op1 op2 res ..................................................................... 303
16.14 IGUAL op1 op2 res ....................................................................... 303
16.15 DISTINTO op1 op2 res ................................................................. 304
16.16 ETIQUETA null null res............................................................... 304
16.17 SALTAR_CONDICION op1 null res ......................................... 304
16.18 SALTAR_ETIQUETA null null res ............................................. 305
© Alfaomega - RC Libros
COMPILADORES
XIV
16.19 IMPRIMIR_ENTERO op1 null null ........................................... 305
16.20 IMPRIMIR_CADENA op1 null null.......................................... 305
16.21 PONER_CADENA op1 null res ................................................. 305
16.22 Punto y final .................................................................................. 306
16.23 Posibles ampliaciones .................................................................. 311
Parte IV. Implementación de C-1
Capítulo 17. Especificación de C-1 ..................................................................... 315
17.1 Introducción .................................................................................... 315
17.2 Tipos estructurados ....................................................................... 316
17.2.1 Registros ................................................................................... 316
17.2.2 Vectores .................................................................................... 317
17.3 Declaración conjunta de variables y variables locales .............. 317
17.4 Nuevos operadores y delimitadores ........................................... 318
17.5 Subprogramas ................................................................................ 318
17.6 Asignación ...................................................................................... 319
17.7 Comentarios .................................................................................... 319
Capítulo 18. Análisis léxico y sintáctico de C-1 ............................................... 321
18.1 Introducción .................................................................................... 321
18.2 Análisis léxico ................................................................................. 321
18.3 Análisis sintáctico .......................................................................... 324
Capítulo 19. Análisis semántico de C-1 ............................................................. 331
19.1 Introducción .................................................................................... 331
19.2 La tabla de tipos ............................................................................. 331
19.3 La tabla de símbolos ...................................................................... 334
19.4 Análisis semántico ......................................................................... 338
19.4.1 Definición del tipo struct ....................................................... 339
19.4.2 Definición del tipo vector ...................................................... 342
19.4.3 Declaración de variables globales ......................................... 343
19.4.4 Declaración de variables locales ........................................... 348
19.4.5 Declaración de subprogramas ............................................... 352
19.4.6 Argumentos de subprogramas ............................................. 354
© Alfaomega - RC Libros
ÍNDICE
XV
19.4.7 Expresiones ............................................................................... 355
19.4.8 Condiciones .............................................................................. 362
19.4.9 Sentencia de asignación .......................................................... 364
19.4.10 Sentencia de retorno de una función ................................... 369
19.4.11 Sentencia de llamada a un procedimiento ......................... 369
19.4.12 Resto de sentencias ................................................................ 370
Capítulo 20. Generación de código de C-1 ......................................................... 371
20.1 Introducción .................................................................................... 371
20.2 CI de expresiones ............................................................................ 373
20.2.1 Suma, resta, producto, multiplicación, división y módulo ........ 373
20.2.2 CI para enteros ......................................................................... 374
20.2.3 CI para identificadores ............................................................ 374
20.2.4 CI para funciones ..................................................................... 375
20.2.5 CI para procedimientos ........................................................... 381
20.2.6 CI para campos de registros ................................................... 382
20.2.7 CI para elementos de un vector ............................................. 383
20.3 CI para asignaciones ....................................................................... 384
20.3.1 Asignación a una variable sencilla ........................................ 384
20.3.2 Asignación a un campo de un registro ................................. 384
20.3.3 Asignación a un elemento de un vector ............................... 384
20.4 Sentencias condicionales y bucles ................................................ 385
20.5 Sentencias para imprimir ............................................................... 386
20.6 Declaración de funciones y procedimientos ............................... 386
20.7 Finalización ...................................................................................... 388
20.8 Generación de código final ............................................................ 388
20.9 Ampliación para C-2 ...................................................................... 390
Parte V. Apéndices, bibliografía e índice alfabético
Apéndice A. Herramientas .................................................................................... 395
A.1 Herramientas .................................................................................... 395
A.2 Instalación de las herramientas ..................................................... 398
© Alfaomega - RC Libros
COMPILADORES
XVI
A.2.1 Java ............................................................................................. 398
A.2.2 JLex ............................................................................................ 398
A.2.3 CUP ............................................................................................ 398
A.2.4 ENS2001 .................................................................................... 398
A.3 Uso de las herramientas ................................................................. 399
A.3.1 Uso de JLex ............................................................................... 399
A.3.2 Uso de Cup ............................................................................... 404
Apéndice B. Código intermedio y final para C-1 en Ens2001 ........................ 409
B.1 Introducción ..................................................................................... 409
B.2 Tabla de código intermedio y final para Ens2001 ....................... 409
B.3 Ejemplo de programa en C-1 ......................................................... 412
Bibliografía ............................................................................................................. 419
Libros y manuales .................................................................................. 419
Software ................................................................................................... 420
Índice alfabético ..................................................................................................... 421