COMPILADORES

Teoría e implementación

Jacinto Ruiz Catalán

COMPILADORES. Teoría e implementación
Jacinto Ruiz Catalán

ISBN: 978-84-937008-9-8

EAN: 9788493700898

Copyright © 2010 RC Libros

© RC Libros es un sello y marca comercial registrada por
Grupo Ramírez Cogollor, S.L. (Grupo RC)

COMPILADORES. Teoría e implementación. Reservados todos los derechos.

Ninguna parte de este libro incluida la cubierta puede ser reproducida, su contenido
está protegido por la Ley vigente que establece penas de prisión y/o multas a
quienes intencionadamente reprodujeren o plagiaren, en todo o en parte, una obra
literaria, artística o científica, o su transformación, interpretación o ejecución en
cualquier tipo de soporte existente o de próxima invención, sin autorización previa
y por escrito de los titulares de los derechos de la propiedad intelectual.

RC Libros, el Autor, y cualquier persona o empresa participante en la redacción, edición o

producción de este libro, en ningún caso serán responsables de los resultados del uso de su
contenido, ni de cualquier violación de patentes o derechos de terceras partes. El objetivo de la
obra es proporcionar al lector conocimientos precisos y acreditados sobre el tema pero su venta no
supone ninguna forma de asistencia legal, administrativa ni de ningún otro tipo, si se precisase
ayuda adicional o experta deberán buscarse los servicios de profesionales competentes. Productos
y marcas citados en su contenido estén o no registrados, pertenecen a sus respectivos propietarios.

Sun, el logotipo de Sun, Sun Microsystems, y Java son marcas o marcas registradas de
Sun Microsystems Inc. EE.UU. y otros países.
JLex está liberado con licencia GPL.
Cup está protegido por licencias de código abierto, siendo compatible con la licencia GPL.
Ens2001 es un Proyecto Fin de Carrera creado por Federico Javier Álvarez para su Licenciatura
en Informática por la Universidad Politécnica de Madrid.

RC Libros
Calle Mar Mediterráneo, 2
Parque Empresarial Inbisa, N-6 – P.I. Las Fronteras
28830 SAN FERNANDO DE HENARES, Madrid
Teléfono: +34 91 677 57 22
Fax: +34 91 677 57 22
Correo electrónico: info@rclibros.es
Internet: www.rclibros.es

Diseño de colección, preimpresión y cubierta: Grupo RC

Impresión y encuadernación: Gráficas Deva, S.L.
Depósito Legal: M-
Impreso en España

14-13 12 11 10 (03)
Í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

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

VIII © RC Libros
 ÍNDICE

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

© RC Libros IX
COMPILADORES

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
X © RC Libros
 ÍNDICE

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
© RC Libros XI
COMPILADORES

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

XII © RC Libros
 ÍNDICE

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

© RC Libros XIII
COMPILADORES

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

XIV © RC Libros
 ÍNDICE

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

© RC Libros XV
COMPILADORES

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

XVI © RC Libros