PDF de programación - Java a tope: Compiladores

JAVA A TOPE:
TRADUCTORES Y COMPILADORES CON LEX/YACC, JFLEX/CUP Y JAVACC.
EDICIÓN ELECTRÓNICA

AUTORES:

ILUSTRACIÓN
DE PORTADA:

SERGIO GÁLVEZ ROJAS
MIGUEL ÁNGEL MORA MATA

JOSÉ MIGUEL GÁLVEZ ROJAS

Sun, el logotipo de Sun, Sun Microsystems y Java son marcas o marcas registradas de Sun Microsystems
Inc. en los EE.UU. y otros países. El personaje de «Duke» es una marca de Sun M icrosystems Inc.
PCLex y PCYacc son productos de Abraxas Software Inc.
JFlex está liberado con licencia GPL.
Cup está protegido por las licencias de código abierto, siendo compatible con la licencia GPL.
JavaCC está sujeto a la licencia BSD (Berkeley Software Distribution) de código abierto.

© 2005 por Sergio Gálvez Rojas
DEPÓSITO LEGAL: MA-185-2005
ISBN: 84-689-1037-6

Java a tope:

Compiladores

Traductores y Compiladores

con Lex/Yacc, JFlex/cup y JavaCC

Sergio Gálvez Rojas

Doctor Ingeniero en Informática

Miguel Ángel Mora Mata

Ingeniero en Informática

Dpto. de Lenguajes y Ciencias de la Computación

E.T.S. de Ingeniería Informática

Universidad de Málaga

Java a tope: Traductores y compiladores con Lex/Yacc, JFlex/Cup y JavaCC

Índice

Prólogo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . vii

Capítulo 1

1.2.1

Introducción . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1
1.1 Visión general
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1
1.2 Concepto de traductor. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2
Tipos de traductores . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2
1.2.1.1 Traductores del idioma
. . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
1.2.1.2 Compiladores . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
1.2.1.3 Intérpretes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
1.2.1.4 Preprocesadores . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4
1.2.1.5 Intérpretes de comandos . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4
1.2.1.6 Ensambladores y macroensambladores . . . . . . . . . . . . . . . . . 5
1.2.1.7 Conversores fuente-fuente . . . . . . . . . . . . . . . . . . . . . . . . . . 5
1.2.1.8 Compilador cruzado . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6
Conceptos básicos relacionados con la traducción . . . . . . . . . . . 6
1.2.2.1 Compilación, enlace y carga.
. . . . . . . . . . . . . . . . . . . . . . . . 6
1.2.2.2 Pasadas de compilación . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8
1.2.2.3 Compilación incremental
. . . . . . . . . . . . . . . . . . . . . . . . . . . 9
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
1.2.2.4 Autocompilador
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
1.2.2.5 Metacompilador
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
1.2.2.6 Descompilador
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
. . . . . . . . . . . . . . . . 12
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14
1.4 Ejemplo de compilación . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15
Preprocesamiento . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16
Etapa de análisis
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16
1.4.2.1 Fase de análisis lexicográfico . . . . . . . . . . . . . . . . . . . . . . . 17
1.4.2.2 Fase de análisis sintáctico . . . . . . . . . . . . . . . . . . . . . . . . . . 17
Compilación dirigida por sintaxis . . . . . . . . . . . . . 18
1.4.2.3 Fase de análisis semántico . . . . . . . . . . . . . . . . . . . . . . . . . 19
Etapa de síntesis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19
1.4.3.1 Fase de generación de código intermedio . . . . . . . . . . . . . . 19
1.4.3.2 Fase de optimización de código . . . . . . . . . . . . . . . . . . . . . 20
1.4.3.3 Fase de generación de código máquina . . . . . . . . . . . . . . . 20

Construcción sistemática de compiladores
La tabla de símbolos

1.3 Estructura de un traductor

1.4.2.2.1

1.2.2

1.3.1
1.3.2

1.4.1
1.4.2

1.4.3

i

Índice

Capítulo 2

2.2.1
2.2.2

2.3.1

2.4.1
2.4.2
2.4.3

Análisis lexicográfico . . . . . . . . . . . . . . . . . . . . . . . 23
2.1 Visión general
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23
2.2 Concepto de analizador léxico . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23
Funciones del analizador léxico . . . . . . . . . . . . . . . . . . . . . . . . . 24
Necesidad del analizador léxico . . . . . . . . . . . . . . . . . . . . . . . . . 25
2.2.2.1 Simplificación del diseño . . . . . . . . . . . . . . . . . . . . . . . . . . 25
2.2.2.2 Eficiencia . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27
2.2.2.3 Portabilidad . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27
2.2.2.4 Patrones complejos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28
2.3 Token, patrón y lexema . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28
Aproximaciones para construir un analizador lexicográfico . . . 30
2.4 El generador de analizadores lexicográficos: PCLex . . . . . . . . . . . . . . . . 31
Visión general
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31
Creación de un analizador léxico . . . . . . . . . . . . . . . . . . . . . . . . 32
El lenguaje Lex . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33
2.4.3.1 Premisas de Lex para reconocer lexemas . . . . . . . . . . . . . . 34
2.4.3.2 Caracteres especiales de Lex . . . . . . . . . . . . . . . . . . . . . . . 34
2.4.3.3 Caracteres de sensibilidad al contexto . . . . . . . . . . . . . . . . 35
2.4.3.4 Estado léxicos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36
2.4.3.5 Área de definiciones y área de funciones . . . . . . . . . . . . . . 37
2.4.3.6 Funciones y variables suministradas por PCLex . . . . . . . . 38
2.5 El generador de analizadores lexicográficos JFlex . . . . . . . . . . . . . . . . . 42
Ejemplo preliminar
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42
Área de opciones y declaraciones . . . . . . . . . . . . . . . . . . . . . . . 44
2.5.2.1 Opciones . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 44
Opciones de clase . . . . . . . . . . . . . . . . . . . . . . . . . 44
Opciones de la función de análisis . . . . . . . . . . . . 44
Opciones de fin de fichero . . . . . . . . . . . . . . . . . . 45
Opciones de juego de caracteres . . . . . . . . . . . . . . 45
Opciones de contadores . . . . . . . . . . . . . . . . . . . . 46
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 46
Declaraciones de estados léxicos. . . . . . . . . . . . . . 46
2.5.2.2.1
2.5.2.2.2
Declaraciones de reglas. . . . . . . . . . . . . . . . . . . . . 46
Área de reglas. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 46
Funciones y variables de la clase Yylex . . . . . . . . . . . . . . . . . . 47

2.5.2.1.1
2.5.2.1.2
2.5.2.1.3
2.5.2.1.4
2.5.2.1.5

2.5.2.2 Declaraciones.

2.5.1
2.5.2

2.5.3
2.5.4

Capítulo 3

Análisis sintáctico . . . . . . . . . . . . . . . . . . . . . . . . . . 49
3.1 Visión general
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 49
3.2 Concepto de analizador sintáctico . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 49
3.3 Manejo de errores sintácticos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 50
Ignorar el problema . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 51
Recuperación a nivel de frase . . . . . . . . . . . . . . . . . . . . . . . . . . 52
Reglas de producción adicionales . . . . . . . . . . . . . . . . . . . . . . . 52

3.3.1
3.3.2
3.3.3

ii

Java a tope: Traductores y compiladores con Lex/Yacc, JFlex/Cup y JavaCC

3.3.4

3.5.1
3.5.2

3.4.1
3.4.2

Corrección Global

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 52
3.4 Gramática utilizada por un analizador sintáctico . . . . . . . . . . . . . . . . . . . 52
Derivaciones
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 53
Árbol sintáctico de una sentencia de un lenguaje . . . . . . . . . . . 54
3.5 Tipos de análisis sintáctico . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 56
Análisis descendente con retroceso . . . . . . . . . . . . . . . . . . . . . . 57
Análisis descendente con funciones recursivas . . . . . . . . . . . . . 60
3.5.2.1 Diagramas de sintaxis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 61
3.5.2.2 Potencia de los diagramas de sintaxis . . . . . . . . . . . . . . . . . 61
3.5.2.3 Correspondencia con flujos de ejecución . . . . . . . . . . . . . . 62
3.5.2.4 Ejemplo completo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 63
3.5.2.5 Conclusiones sobre el análisis descendente con funciones
recursivas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 66
Análisis descendente de gramáticas LL(1)
. . . . . . . . . . . . . . . . 67
Generalidades del análisis ascendente . . . . . . . . . . . . . . . . . . . . 70
3.5.4.1 Operaciones en un analizador ascendente . . . . . . . . . . . . . . 71
Análisis ascendente con retroceso . . . . . . . . . . . . . . . . . . . . . . . 72
. . . . . . . . . . . . . . . . . 74
Análisis ascendente de gramáticas LR(1)
3.5.6.1 Consideraciones sobre el análisis LR(1) . . . . . . . . . . . . . . . 79
Recursión a derecha o a izquierda . . . . . . . . . . . . 79
Conflictos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 80
3.5.6.2 Conclusiones sobre el análisis LR(1) . . . . . . . . . . . . .