Actualizado el 21 de Marzo del 2018 (Publicado el 22 de Diciembre del 2017)
665 visualizaciones desde el 22 de Diciembre del 2017
507,2 KB
75 paginas
Creado hace 16a (23/10/2007)
UNIVERSIDAD SIMÓN BOLÍVAR
Ingeniería de la Computación
GENERACIÓN DE RECONOCEDORES LALR EN
DIVERSOS LENGUAJES DE PROGRAMACIÓN
Por:
CARLOS ALBERTO PÉREZ DÍAZ
Tutor:
PROF. ASCÁNDER SUÁREZ
Proyecto de Grado
Presentado ante la Ilustre Universidad Simón Bolívar
como Requisito Parcial para Optar el Título de
Ingeniero en Computación
Sartenejas, 23 de octubre de 2007.
UNIVERSIDAD SIMÓN BOLÍVAR
Ingeniería de la Computación
GENERACIÓN DE RECONOCEDORES LALR EN
DIVERSOS LENGUAJES DE PROGRAMACIÓN
Por:
CARLOS ALBERTO PÉREZ DÍAZ
Proyecto de Grado
Presentado ante la Ilustre Universidad Simón Bolívar
como Requisito Parcial para Optar el Título de
Ingeniero en Computación
Sartenejas, 23 de octubre de 2007.
UNIVERSIDAD SIMÓN BOLÍVAR
DECANATO DE ESTUDIOS PROFESIONALES
COORDINACIÓN DE INGENIERÍA DE LA COMPUTACIÓN
ACTA FINAL DEL PROYECTO DE GRADO
GENERACIÓN DE RECONOCEDORES LALR EN DIVERSOS
LENGUAJES DE PROGRAMACIÓN
Presentado por:
CARLOS ALBERTO PÉREZ DÍAZ
Este Proyecto de Grado ha sido aprobado por
el siguiente jurado examinador:
————————————————————
Prof. Ascánder Suárez
————————————————————
Prof. Luis Astorga
————————————————————
Prof. Óscar Meza
SARTENEJAS, 17/10/2007
GENERACIÓN DE RECONOCEDORES LALR EN
DIVERSOS LENGUAJES DE PROGRAMACIÓN
POR:
CARLOS ALBERTO PÉREZ DÍAZ
RESUMEN
Claire es una herramienta de generación de reconocedores sintácticos desarrollada en la Uni-
versidad Simón Bolívar utilizada principalmente en el compilador del lenguaje GaCeLa, en varios
proyectos de grado de estudiantes de Ingeniería de la Computación y en los laboratorios de las
asignaturas “Traductores e Interpretadores” y “Lenguajes de Programación”.
Esta herramienta fue diseñada para poder generar reconocedores sintácticos en varios lengua-
jes, pero en sus implementaciones iniciales sólo fue desarrollado el generador para el lenguaje de
programación Java.
El trabajo realizado en este proyecto de grado busca implementar extensiones para generar
reconocedores en otros lenguajes distintos de Java, en especial a los lenguajes de programación
Ruby y Python, lenguajes que han tenido auge últimamente.
Además, se plantea la especificación de un procedimiento que se pueda seguir para la imple-
mentación de nuevas extensiones en lenguajes distintos a los ya implementados. Para realizar esto,
se desarrolló una referencia para el contenido de una extensión. Además, se expone el diseño y la
implementación de las extensiones para los lenguajes anteriormente mencionados, utilizando esta
referencia.
ii
Agradecimientos
Agradezco a mi mamá y a mi papá, Ana María y Francisco,
y a todos mis hermanos por todo el apoyo que me han brindado
Agradezco a César por siempre estar en las buenas y en las malas.
Agradezco a mis demás amigos fuera de la universidad
por haberme acompañado durante este largo trayecto.
Agradezco a mi tutor, el prof. Ascánder Suárez, a mi profesor guía,
prof. Pedro Borges, y a todos los demás profesores con los que he tenido
el honor de ser su alumno, por el apoyo suministrado durante toda mi carrera.
Agradezco a la Comisión de Carrera de Ing. de Computación 2006 - 07,
por ser un grupo de personas únicas en toda la universidad.
Agradezco a la Universidad Simón Bolívar,
por formarme como persona y como profesional.
Agradezco a Nintendo,
por ser motivante fundamental en mi carrera.
iii
Dedicatoria
A mi familia, sin ellos no sería la persona que soy.
iv
Índice general
1. Introducción
2. Marco Teórico
2.1. Lenguajes Formales . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
2.2. Reconocimiento de Lenguajes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
2.2.1. Autómatas Finitos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
2.2.2. Autómatas de Pila . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
2.2.3. Técnicas especiales de reconocimiento . . . . . . . . . . . . . . . . . . . . . .
2.3. Compilador. Definición y Estructura . . . . . . . . . . . . . . . . . . . . . . . . . . .
2.4. Análisis de un Programa . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
2.4.1. Análisis Lexicográfico . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
2.4.2. Análisis Sintáctico . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
2.4.3. Análisis Semántico . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
3. Introducción a la Herramienta Claire
Introducción a Claire . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
3.1.
3.2. Definición de una Gramática en Claire . . . . . . . . . . . . . . . . . . . . . . . . . .
3.2.1. Preámbulo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
3.2.2. Directivas del reconocedor . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
3.2.3. Definición de las reglas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
3.3. Estructura Interna de Claire . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
3.3.1. Reconocimiento de la gramática
. . . . . . . . . . . . . . . . . . . . . . . . .
3.3.2. Reconocimiento de las unidades lexicográficas . . . . . . . . . . . . . . . . . .
v
1
3
3
5
5
6
7
10
11
11
11
12
13
13
14
14
14
15
18
18
19
3.3.3. Generación de tablas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . .
3.3.4. Construcción de reconocedores
3.3.5. Paquete de ejecución dependiente del lenguaje
. . . . . . . . . . . . . . . . .
3.4. Generación de Reconocedores en Claire
. . . . . . . . . . . . . . . . . . . . . . . . .
3.4.1. Reconocimiento de la gramática
. . . . . . . . . . . . . . . . . . . . . . . . .
3.4.2. Generación de las tablas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
3.4.3. Traducción al lenguaje destino . . . . . . . . . . . . . . . . . . . . . . . . . .
3.5. Estado Actual . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
4. Herramientas Relacionadas
4.1. JavaCC . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
4.1.1. Características de JavaCC . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
4.2. ANTLR . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
4.2.1. Características de ANTLR . . . . . . . . . . . . . . . . . . . . . . . . . . . .
4.3. CUP . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
4.3.1. Características de CUP . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
4.4. Yapps . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
4.4.1. Características de Yapps . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
4.5. SPARK . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
4.5.1. Características de SPARK . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
4.6. Racc . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
4.6.1. Características de Racc . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
5. Planteamiento del Problema
5.1. Lenguajes Seleccionados . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
5.1.1. Lenguaje de Programación Ruby . . . . . . . . . . . . . . . . . . . . . . . . .
5.1.2. Lenguaje de Programación Python . . . . . . . . . . . . . . . . . . . . . . . .
6. Referencia de una Extensión
6.1. Estructura de una Extensión . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
6.2. Generación de reconocedores
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
19
19
19
20
20
21
21
22
23
23
23
24
24
24
24
25
25
25
25
26
26
27
28
28
29
31
31
32
vi
6.3. Librerías de soporte para ejecución . . . . . . . . . . . . . . . . . . . . . . . . . . . .
6.3.1. Algoritmos para reconocimiento en LR y en autómatas finitos . . . . . . . . .
6.3.2. Lector especial
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
6.3.3. Símbolos y unidades lexicográficas . . . . . . . . . . . . . . . . . . . . . . . .
6.3.4. Manejador de tablas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Interacción entre el reconocedor y las tablas . . . . . . . . . . . . . . . . . . .
6.3.5.
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
6.4.1. Preámbulo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Implementación de referencia - Lenguaje Java . . . . . . . . . . . . . . . . . . . . . .
6.5.1. Librería de soporte . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
6.5.2. Generación de reconocedores
. . . . . . . . . . . . . . . . . . . . . . . . . . .
6.4. Otras consideraciones
6.5.
7. Diseño e Implementación
7.1. Extensión para el lenguaje Ruby . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
7.1.1. Composición de la librería de soporte
. . . . . . . . . . . . . . . . . . . . . .
7.1.2. Estructura de la definición gramatical y del reconocedor generado . . . . . .
7.2. Extensión para el lenguaje Python . . . . . . . . . . . . . . . . . . . . . . . . . . . .
7.2.1. Librería de soporte . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
7.2.2. Estructura de la definición gramatical y del reconocedor generado . . . . . .
Implementación . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
7.3.1.
Interpretes para la JVM de los lenguajes destinos . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
7.3.2. Otras alternativas
7.3.3. Estado actual de las extensiones
. . . . . . . . . . . . . . . . . . . . . . . . .
7.3.
8. Conclusiones y Recomendaciones
A. Ejemplos de gramáticas de Claire
A.1. Calculadora . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
A.1.1. Con destino en jruby . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
A.1
Comentarios de: GENERACIÓN DE RECONOCEDORES LALR EN DIVERSOS LENGUAJES DE PROGRAMACIÓN (0)
No hay comentarios