Download Compiladores e Interpretes Teoria y Practica PDF

TitleCompiladores e Interpretes Teoria y Practica
File Size2.1 MB
Total Pages375
Table of Contents
                            Compiladores e interpretes : teoría y práctica
Contenido
Capítulo 1. Lenguajes, gramáticas y procesadores
Capítulo 2. Tabla de símbolos
Capítulo 3. Análisis morfológico
Capítulo 4. Análisis sintáctico
Capítulo 5. Análisis semántico
Capítulo 6. Generación de código
Capítulo 7. Optimización de código
Capítulo 8. Intérpretes
Capítulo 9. Tratamiento de errores
Capítulo 10. Gestión de memoria
Índice analítico
                        
Document Text Contents
Page 1

LibroSitePulido.eps


Compiladores e interpretes:
teoría y práctica

Manuel Alfonseca Moreno
Marina de la Cruz Echeandía
Alfonso Ortega de la Puente
Estrella Pulido Cañabate

www.pearsoneducacion.com

Compiladores e Intérpretes: Teoría y Práctica, es un texto dirigido a
Escuelas y Facultades de Informática, en cuya titulación existe esta asignatura
bajo el nombre usual de Procesadores de Lenguaje. El libro describe con
detalle y ejemplos las distintas fases del proceso de compilación o
interpretación y los algoritmos que se pueden utilizar para implementarlas.

Cada capítulo se acompaña con ejercicios, cuya solución aparece en
www.librosite.net/pulido, donde también se incluye el código completo de
un compilador para un lenguaje sencillo, así como los pasos que hay que dar
para construirlo.

ISBN 978-84-205-5031-2

Otro libro de interés:

Alfred V. Aho, Ravi Sethi y
Jeffrey Ullman:
Compiladores: Principios, técnicas
y herramientas. México,
Pearson Addison Wesley, 1990.
ISBN: 968-4443-33-1

Incluye:

LibroSite es una página web
asociada al libro, con una
gran variedad de recursos y
material adicional tanto para
los profesores como para
estudiantes. Apoyos a la
docencia, ejercicios de
autocontrol, enlaces
relacionados, material de
investigación, etc., hacen de
LibroSite el complemento
académico perfecto para este
libro.

Co
m

p
il

ad
or

es
e

i
nt

er
p
re

te
s

Alfonseca
de la Cruz

Ortega
Pulido

www.librosite.net/pulido

Page 2

00a-portadillas 9/2/06 12:22 Página 2

Page 187

La matriz booleana equivalente a F es la siguiente matriz B:

N C 0 1 2 3 4 5 6 7 8 9
N: 1 1 0 0 0 0 0 0 0 0 0 0
C: 0 0 1 1 1 1 1 1 1 1 1 1
0: 0 0 0 0 0 0 0 0 0 0 0 0
1: 0 0 0 0 0 0 0 0 0 0 0 0
2: 0 0 0 0 0 0 0 0 0 0 0 0
3: 0 0 0 0 0 0 0 0 0 0 0 0
4: 0 0 0 0 0 0 0 0 0 0 0 0
5: 0 0 0 0 0 0 0 0 0 0 0 0
6: 0 0 0 0 0 0 0 0 0 0 0 0
7: 0 0 0 0 0 0 0 0 0 0 0 0
8: 0 0 0 0 0 0 0 0 0 0 0 0
9: 0 0 0 0 0 0 0 0 0 0 0 0

donde las filas y las columnas corresponden a los símbolos {N,C,0,1,2,3,4,5,
6,7,8,9}, en ese orden. De aquí se puede calcular que B2 = B3 = ... = la siguiente matriz:

N C 0 1 2 3 4 5 6 7 8 9
N: 1 1 1 1 1 1 1 1 1 1 1 1
C: 0 0 0 0 0 0 0 0 0 0 0 0
0: 0 0 0 0 0 0 0 0 0 0 0 0
1: 0 0 0 0 0 0 0 0 0 0 0 0
2: 0 0 0 0 0 0 0 0 0 0 0 0
3: 0 0 0 0 0 0 0 0 0 0 0 0
4: 0 0 0 0 0 0 0 0 0 0 0 0
5: 0 0 0 0 0 0 0 0 0 0 0 0
6: 0 0 0 0 0 0 0 0 0 0 0 0
7: 0 0 0 0 0 0 0 0 0 0 0 0
8: 0 0 0 0 0 0 0 0 0 0 0 0
9: 0 0 0 0 0 0 0 0 0 0 0 0

(En cuanto dos potencias de la matriz coinciden, las restantes son todas iguales). B+ es la
unión booleana de todas las matrices (las dos) anteriores:

N C 0 1 2 3 4 5 6 7 8 9
N: 1 1 1 1 1 1 1 1 1 1 1 1
C: 0 0 1 1 1 1 1 1 1 1 1 1
0: 0 0 0 0 0 0 0 0 0 0 0 0
1: 0 0 0 0 0 0 0 0 0 0 0 0
2: 0 0 0 0 0 0 0 0 0 0 0 0
3: 0 0 0 0 0 0 0 0 0 0 0 0
4: 0 0 0 0 0 0 0 0 0 0 0 0
5: 0 0 0 0 0 0 0 0 0 0 0 0
6: 0 0 0 0 0 0 0 0 0 0 0 0
7: 0 0 0 0 0 0 0 0 0 0 0 0
8: 0 0 0 0 0 0 0 0 0 0 0 0
9: 0 0 0 0 0 0 0 0 0 0 0 0

Capítulo 4. Análisis sintáctico 173

04-CAPITULO 04 9/2/06 11:50 Página 173

Page 188

Por tanto,

F + = {(N,N), (N,C), (N,0), (N,1), (N,2), ..., (N,9),
(C,0), (C,1), (C,2), ..., (C,9)}

Y así se tiene que:

first(C) = {0, 1, 2, ..., 9}

Ahora se calcula el conjunto last(N). Para ello, se define la relación L:

La matriz de la relación L+ se calcula igual que la de F+ y sale:

N C 0 1 2 3 4 5 6 7 8 9
N: 0 1 1 1 1 1 1 1 1 1 1 1
C: 0 0 1 1 1 1 1 1 1 1 1 1
0: 0 0 0 0 0 0 0 0 0 0 0 0
1: 0 0 0 0 0 0 0 0 0 0 0 0
2: 0 0 0 0 0 0 0 0 0 0 0 0
3: 0 0 0 0 0 0 0 0 0 0 0 0
4: 0 0 0 0 0 0 0 0 0 0 0 0
5: 0 0 0 0 0 0 0 0 0 0 0 0
6: 0 0 0 0 0 0 0 0 0 0 0 0
7: 0 0 0 0 0 0 0 0 0 0 0 0
8: 0 0 0 0 0 0 0 0 0 0 0 0
9: 0 0 0 0 0 0 0 0 0 0 0 0

Luego last(N) es igual a {C,0,1,2,3,4,5,6,7,8,9}.

174 Compiladores e intérpretes: teoría y práctica

Regla Relación L

N::=NC N L C

N::=C N L C

C::=0 C L 0

C::=1 C L 1

C::=2 C L 2

C::=3 C L 3

C::=4 C L 4

C::=5 C L 5

C::=6 C L 6

C::=7 C L 7

C::=8 C L 8

C::=9 C L 9

04-CAPITULO 04 9/2/06 11:50 Página 174

Page 374

vacía, 5-10, 15, 17, 24, 67, 168-169
palíndromo, 19
Pappert, Seymour, 322
parser, véase analizador sintáctico
PASCAL, lenguaje de programación, 26, 27,

56, 340, 346
paso

del análisis, 57, 99, 113-114, 116, 118,
123, 127

de un compilador, 29, 58-60, 194, 196,
199, 221, 227-228, 258, 285

pila, 58-60, 113-114, 116-118, 120-123, 126,
141, 144, 178-180, 195, 217, 228, 231,
244-247, 258, 260-261, 268, 272, 274-
275, 302, 324, 337-339, 341-344,

véase también autómata a pila
plataforma, 247, 248, 253, 324
pop, 60, 119, 122-123, 228, 245, 265, 266,

273, 274, 339, 341
potencia, 7, 9-10, 169, 171, 173
primero_LR(1), conjunto, 155-156
problemas

no computables, 4
recursivamente enumerables, 4

procedimiento, 62, 192, 229, 233, 334
producción, véase regla de producción
programa enlazador, 243, 345
programa main, 80, 81, 82, 239-240, 328, 329,

330
PROLOG, lenguaje de programación, 26, 28,

56, 318, 322
puntero, véase apuntador

puntero a la pila, 244, 246
push, 60, 119, 228, 244, 261, 264-266, 269-

274, 339

R

raíz, 19, 21
recolección de basuras, 347-353
recorrido en profundidad por la izquierda con

vuelta atrás, 218
recuperación de errores, 29, 77, 329-331
recursividad, 15, 176, 352

a izquierdas, 100

redimensionamiento, 55
reducción, 29, 93

acción de análisis, 115-117, 122-124, 128-
129, 131, 137, 141-142, 144-145, 147-
150, 154, 158, 218, 223, 227

de fuerza, 304-306, 311-313
redundancia, eliminación de, 292-293
reflexión, 7, 10
región, 309-313, 327

fuertemente conexa, 309
registro, 230-231, 286-287, 302

de activación, 341-343
de segmentación, 337-340
de trabajo, 246, 323
gestión de, 246-249

regla
de producción, 11-12, 15, 16-18, 19, 30,

114-117, 120-122, 124, 128-129, 141,
148-150, 203, 209, 211, 214-215, 234,
237

de redenominación, 23, 24, 211
innecesaria, 23
no generativa, 23, 24, 168, 169
recursiva, 15, 168, 169, 176, 212, 215
superflua, 23

regla-l, 101-102, 104-106, 113, 114, 210-211,
238

rehash, véase sondeo
relaciones

de precedencia, 175-176
teoría de, 168, 169-174

reordenación
de código, 287
de operaciones, 300

S

salto, 230, 232
condicional, 246, 266
incondicional, 245, 255, 257, 258, 266,

276, 277
scanner, véase analizador morfológico
semántica, 3, 29-30, 191
semigrupo, 6-7

360 Compiladores e intérpretes: teoría y práctica

Indice alfabético 9/2/06 11:54 Página 360

Page 375

sentencia, 14, 16, 17, 20, 21, 22, 81
Shannon, Claude Elwood, 2
símbolo

de adelanto, 155
inaccesible, 23
no generativo, 23, 24
no terminal, 11-12, 14, 16, 20, 23-24, 90,

94, 99, 100, 102, 103, 104, 105, 111,
117, 128-130, 132, 141-142, 144, 145,
147, 152, 157, 160, 168, 194, 210-211,
215, 231-232, 235, 254, 255, 260, 332

terminal, 11, 14, 20, 21, 23, 28, 94, 99, 102,
103, 111, 114, 117, 130-131, 142, 144,
145, 152, 160, 168, 211, 235, 237, 253,
260, 268, 332, 333

sintaxis, 3, 17, 25-26, 29-30, 89, 191, 243,
253, 259, 327, 328

Smalltalk, lenguaje de programación, 26, 28,
259, 318, 320, 322

SNOBOL, lenguaje de programación, 318,
322

sondeo, 50, 51, 52, 55
aleatorio, 54
cuadrático, 54
lineal , 52
multipicativo, 53

subárbol, 21
submeta, 94-97
subrutina, 29, 56, 58, 229, 233, 243, 246, 254,

320, 337, 338, 339, 341-345, 346, 348
SLR(1), véase gramática o análisis

T

tabla
de análisis, 227
de análisis ascendente, 118-119, 122-123,

125, 137-138, 140, 145-149, 158, 167
de referencias, 324-325, 348
de símbolos o identificadores, 28, 30, 33,

56, 58-59, 61-62, 202, 196, 206-208,
217, 230-233, 289, 293, 320, 322, 324-

325, 327, 328, 330, 331, 332, 339, 340,
347, 348

hash, véase hash, tabla
terminal, véase símbolo terminal
tipo, de dato, 62, 192, 194, 196, 199-203, 206-

207, 209, 223, 230-233, 288
Thue, relación de , 14
transición, 68, 72, 73, 75, 76

diagrama de, 68, 69, 141, 143-145, 147-
149, 156-157, 160-161

extendida, función de, véase función de
transición extendida

función de, véase función de transición
triplete, 259, 267-268

indirecto, 267-268
tupla, 195, 259
Turing, Alan Mathison, 1-2, 4
Turing, máquina de, 1, 2, 4, 30

U

unidad sintáctica, 28, 65, 75, 76, 77, 80, 81,
82, 83, 196, 217, 240, 253, 255, 327,
333

unión, 8, 9, 67, 68, 78, 170, 173

V

variable 57
automática, 341-345
estática, 338, 339-341
intermedia, 292-293, 311-312
de bucle, 305-308

vector, 55, 247, 323, 324, 327, 328, 340, 349-
352

W

while, instrucción, véase instrucción iterativa

Y

yacc, 168, 234, 235, 238, 239, 240

Índice analítico 361

Indice alfabético 9/2/06 11:54 Página 361

Similer Documents