PDF de programación - GENERACIÓN DE RECONOCEDORES LALR EN DIVERSOS LENGUAJES DE PROGRAMACIÓN

Imágen de pdf GENERACIÓN DE RECONOCEDORES LALR EN DIVERSOS LENGUAJES DE PROGRAMACIÓN

GENERACIÓN DE RECONOCEDORES LALR EN DIVERSOS LENGUAJES DE PROGRAMACIÓNgráfica de visualizaciones

Actualizado el 21 de Marzo del 2018 (Publicado el 22 de Diciembre del 2017)
304 visualizaciones desde el 22 de Diciembre del 2017
507,2 KB
75 paginas
Creado hace 12a (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
  • Links de descarga
http://lwp-l.com/pdf7985

Comentarios de: GENERACIÓN DE RECONOCEDORES LALR EN DIVERSOS LENGUAJES DE PROGRAMACIÓN (0)


No hay comentarios
 

Comentar...

Nombre
Correo (no se visualiza en la web)
Valoración
Comentarios
Es necesario revisar y aceptar las políticas de privacidad