PDF de programación - Un generador de analizadores léxicos traductores

Indice

Introducción

Capítulo 1: Introducción a los Analizadores Léxicos

1.1 - Función del Analizador Léxico
1.2 - Componentes léxicos o tokens, patrones y lexemas
1.3 - Especificación de los componentes léxicos

1.3.1 - Cadenas y lenguajes
1.3.2 – Operaciones aplicadas a lenguajes
1.3.3 – Expresiones Regulares
1.3.4 – Definiciones Regulares
1.3.5 – Abreviaturas en la notación

1.4 - Autómatas Finitos

1.4.1 – Autómatas Finitos no deterministas con transiciones λ
1.4.2 – Autómatas Finitos Deterministas
1.4.3 – Conversión de un AFNλ en un AFD
1.4.4 – Construcción de un AFD a partir de una expresión
regular
1.4.5 – Minimización del número de estados de un AFD

1.5 - Generación de Analizadores Léxicos
1.6 - Diseño de un Generador de Analizadores Léxicos


Capítulo 2: Introducción a los Analizadores Léxicos Traductores

2.1 – Definiciones

2.1.1 – Traducción (»)
2.1.2 - Expresión Regular Traductora (ET)
2.1.3 – Proyección sobre la primera coordenada (Π1)
2.1.4 – Proyección sobre la segunda coordenada (Π2)
2.1.5 – Traducción generada por una ET:
2.1.6 - Expresión Regular con Traducción Única (ETU)
2.1.7 - Expresión Regular Traductora Lineal (ETL)
2.1.8 - Expresión regular Traductora Lineal Cerrada (ETC)
2.1.9 - Autómata Finito Traductor (AFT)
2.1.10 – Máquina de Mealy
2.1.11 – Máquina de Moore

2.2 - Propiedades de las expresiones traductoras
2.3 - Diseño un Generador de Analizadores Léxicos para

Expresiones Traductores Lineales Cerradas

2.4 - Diseño un Generador de Analizadores Léxicos para

Expresiones Traductores Lineales

2.5 - Corrección de los algoritmos

2.5.1 – Corrección de las funciones auxiliares
2.5.2 – Corrección del algoritmo 1



iii

Vii

1
1
3
4
4
5
6
8
9
9
10
13
15
17

21
23
24

25
26
26
26
26
27
27
27
27
28
28
29
32
33
34

38

39
39
42


Un Generador de Analizadores Léxicos Traductores



Capítulo 3: Diseño de un Generador de Analizadores Léxicos

Traductores

3.1 - Decisiones de diseño
3.2 - Diseño de un Analizador Léxico Traductor

3.2.1 - Clases y relaciones del analizador
3.2.2 – Clases del Analizador
3.2.3 - Diagrama de Interacción correspondiente a next_token


3.3 - Diseño de un Generador de Analizadores Léxicos

Traductores

3.3.1 – Módulos del Generador
3.3.2 - Clases y Relaciones del Analizador


Capítulo 4: Definición del Lenguaje de Especificación

4.1 – Especificación del Generador

4.1.1 – Declaraciones

a - Definición de Atributos y Métodos del Usuario
b - Código de Inicialización del Código Usuario
c - Código de Fin de Archivo para el Analizador Léxico
d - Código de Error para el Analizador Léxico
e - Definición de Macros

4.1.2 - Reglas de las Expresiones Regulares Traductoras

Lineales

a - Acción Inicial
b - Expresión Regular Traductora Lineal
c - Acción Final
d - Gramática de las reglas de las Expresiones Regulares

Léxicos Traductores

5.3 - Reconocimiento de Errores


Capítulo 6: Generación del Código que Implementa el
Analizador Léxico Traductor Especificado

6.1 – Generación de las Estructuras de Datos
6.1.1 - Construcción del Arbol Sintáctico
6.1.2 – Cómputo de la función followpos
6.1.3 – Construcción del AFT de cada ETL

iv

Traductoras Lineales

4.1.3 - Código de Usuario
4.1.4 – Comentarios

4.2 – Gramática del Lenguaje de Especificación
4.3 - Un ejemplo de una especificación


Capítulo 5: Análisis Léxico y Sintáctico

5.1 - Análisis Léxico

5.1.1 - Lexemas y Tokens del Generador
5.1.2 - JLex: Un Generador de Analizadores Léxicos para

Java

5.1.3 - Especificación Jlex para el Generador de Analizadores

Léxicos Traductores

5.2 - Análisis Sintáctico

5.2.1 - CUP: un Generador de parsers LALR para Java
5.2.3 - Especificación CUP para el Generador de Analizadores

47

48
48
48
49
51

51

52
53

57
57
58
58
58
59
59
59
59

60
60
61
62

62
63
63
64

67
67
67
68

69

70
70
71

71

73

74
74
76
77



Indice

6.1.4 – Construcción del AFNλ
6.1.5 – Construcción del AFD
6.1.6 – Clase Table_expresions

6.2 – Generación del Código

6.2.1 – Código generado para el ejemplo

6.3 – Diagrama de Secuencia para Generar el Analizador


Capítulo 7: El Generador de Analizadores Léxicos Traductores dentro

del Entorno Japlage

7.1 - Esquema general de funcionamiento
7.2 - Generador de procesadores de lenguajes Japlage

7.2.1 - Clases del generador
7.2.2 - De análisis lexicográfico y sintáctico
7.2.3 - De análisis estático
7.2.4 - De generación de código
7.2.5 - De interface

7.3 – Interacción de las Herramientas Generadas


Conclusiones

Anexo 1: Especificación JLex para el Generador de

Analizadores Léxicos Traductores


Anexo 2: Especificación Cup para el Generador de

Analizadores Léxicos Traductores


Anexo 3: Notación utilizada en el diseño

3.1 - Descripción de clases
3.1 - Descripción de relaciones entre clases



Anexo 4: Código del Analizador Léxico Generado para el

Ejemplo del Capítulo 6


Anexo 5: Manual de Usuario
1 – Introducción
2 - Instalación y ejecución de JTLex
3 - Especificación JTLex

3.1 – Directivas de JTLex

3.1.1 – Definición de Atributos y Métodos del Usuario
3.1.2 – Código de Inicialización del Código Usuario
3.1.3 – Código de Fin de Archivo para el Analizador Léxico
3.1.4 – Código de Error para el Analizador Léxico
3.1.5 - Definición de Macros

3.2 - Reglas para Definir los símbolos del Lenguaje

3.2.1 - Acción Inicial
3.2.2 – Regla
3.2.3 - Acción Final
3.2.4 - Gramática de las Reglas

3.3 - Código de Usuario
3.4 – Comentarios en JTLex

4 – Analizadores Léxicos Generados

v

78
78
79
79
80
80


81
82
82
84
84
84
85
86
86

87

89


95



101
101
101

103



105
117
118
119
119
119
120
120
120
120
121
121
122
123
123
124
124
125

Un Generador de Analizadores Léxicos Traductores



5 - Un ejemplo de una especificación JTLex
6 – Gramática JTLex

Bibliografía

126
128



129



vi

Esta tesina constituye el último escalón de los autores para finalizar sus estudios de



Introducción



la carrera Licenciatura en Ciencias de la Computación y obtener su título de grado.


Un analizador léxico es un módulo destinado a leer caracteres del archivo de
entrada, donde se encuentra la cadena a analizar, reconocer subcadenas que correspondan a
símbolos del lenguaje y retornar los tokens correspondientes y sus atributos. Escribir
analizadores léxicos eficientes “a mano” puede resultar una tarea tediosa y complicada,
para evitarla se han creado herramientas de software – los generadores de analizadores
léxicos – que generan automáticamente un analizador léxico a partir de una especificación
provista por el usuario.


Puede asegurarse que la herramienta del tipo mencionado más conocida es Lex
[Lev92]. Lex es un generador de analizadores léxicos, originalmente incluido dentro del
ambiente de desarrollo de UNIX usando a C como lenguaje huésped y posteriormente
migrado a casi todas las plataformas y lenguajes. Otra herramienta que últimamente ha
tenido gran difusión es JLex – que usa a Java como lenguaje huésped y corresponde al
compilador de compiladores Cup – [App98][Ber97]; mientras que algunos compiladores
de compiladores actuales como Javacc [Javacc] y Eli [Com98] integran la especificación
del análisis léxico sin brindar un módulo específico.


Todas estas herramientas para generar analizadores léxicos permiten definir la
sintaxis de los símbolos mediante expresiones regulares, mientras que sus atributos deben
ser computados luego del reconocimiento de una subcadena que constituya un símbolo del
lenguaje. Una alternativa sería contar con una herramienta que permita computar los
atributos a medida que se reconocen dichas subcadenas aprovechando el mecanismo de
computo garantizado por el analizador léxico. De esta manera se libra al usuario del
control sobre la cadena a computar.


En el presente trabajo, motivado por lo expuesto en el párrafo anterior, se exponen
los puntos principales del diseño e implementación de un generador de analizadores
léxicos que, al contrario de los generadores existentes, permite la especificación conjunta
de la sintaxis y la semántica de los componentes léxicos siguiendo el estilo de los
esquemas de traducción. Para ello se basa en un nuevo formalismo, las Expresiones
Regulares Traductoras, introducido por Jorge Aguirre et al – Incorporando Traducción a
las Expresiones Regulares [Agu99] –.


Tanto su diseño como la especificación de los procedimientos con que el usuario
implementa la semántica asociada a los símbolos son Orientados a Objetos. El lenguaje de
implementación del generador es Java, como así también, el del código que genera y el
que usa el usuario para definir la semántica.


Esta herramienta se integra, como un generador de analizadores léxicos alternativo
al tradicional, a japlage; un entorno de generación de procesadores de lenguajes – en
particular de compiladores –, desarrollado en el grupo de investigación de Procesadores de

vii

Lenguajes♣, que permite la evaluación concurrente de cualquier Gramática de Atributos
Bien Formada. Los lenguajes de especificación brindados por el generador de analizadores
léxicos traductores y por el generador de analizadores sintácticos de japlage siguen el
estilo de Lex y Yacc respectivamente – que son prácticamente un estándar –.



Estructura de esta Tesis


Esta tesis se divide en dos partes – no es una división física sino lógica – bien
diferenciadas pero complementarias. La primera es netamente teórica y se refiere a los
generadores de analizadores léxicos mientra