Download generación de reconocedores lalr en diversos lenguajes de

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 Universidad 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 lenguajes, 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 implementació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
1
2. Marco Teórico
3
2.1. Lenguajes Formales . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
3
2.2. Reconocimiento de Lenguajes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
5
2.2.1. Autómatas Finitos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
5
2.2.2. Autómatas de Pila . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
6
2.2.3. Técnicas especiales de reconocimiento . . . . . . . . . . . . . . . . . . . . . .
7
2.3. Compilador. Definición y Estructura . . . . . . . . . . . . . . . . . . . . . . . . . . .
10
2.4. Análisis de un Programa . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
11
2.4.1. Análisis Lexicográfico . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
11
2.4.2. Análisis Sintáctico . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
11
2.4.3. Análisis Semántico . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
12
3. Introducción a la Herramienta Claire
13
3.1. Introducción a Claire . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
13
3.2. Definición de una Gramática en Claire . . . . . . . . . . . . . . . . . . . . . . . . . .
14
3.2.1. Preámbulo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
14
3.2.2. Directivas del reconocedor . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
14
3.2.3. Definición de las reglas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
15
3.3. Estructura Interna de Claire . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
18
3.3.1. Reconocimiento de la gramática
. . . . . . . . . . . . . . . . . . . . . . . . .
18
3.3.2. Reconocimiento de las unidades lexicográficas . . . . . . . . . . . . . . . . . .
19
v
3.3.3. Generación de tablas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
19
3.3.4. Construcción de reconocedores . . . . . . . . . . . . . . . . . . . . . . . . . .
19
3.3.5. Paquete de ejecución dependiente del lenguaje . . . . . . . . . . . . . . . . .
19
3.4. Generación de Reconocedores en Claire . . . . . . . . . . . . . . . . . . . . . . . . .
20
3.4.1. Reconocimiento de la gramática
. . . . . . . . . . . . . . . . . . . . . . . . .
20
3.4.2. Generación de las tablas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
21
3.4.3. Traducción al lenguaje destino . . . . . . . . . . . . . . . . . . . . . . . . . .
21
3.5. Estado Actual . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
22
4. Herramientas Relacionadas
23
4.1. JavaCC . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
23
4.1.1. Características de JavaCC . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
23
4.2. ANTLR . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
24
4.2.1. Características de ANTLR . . . . . . . . . . . . . . . . . . . . . . . . . . . .
24
4.3. CUP . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
24
4.3.1. Características de CUP . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
24
4.4. Yapps . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
25
4.4.1. Características de Yapps . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
25
4.5. SPARK . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
25
4.5.1. Características de SPARK . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
25
4.6. Racc . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
26
4.6.1. Características de Racc . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
26
5. Planteamiento del Problema
27
5.1. Lenguajes Seleccionados . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
28
5.1.1. Lenguaje de Programación Ruby . . . . . . . . . . . . . . . . . . . . . . . . .
28
5.1.2. Lenguaje de Programación Python . . . . . . . . . . . . . . . . . . . . . . . .
29
6. Referencia de una Extensión
31
6.1. Estructura de una Extensión . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
31
6.2. Generación de reconocedores . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
32
vi
6.3. Librerías de soporte para ejecución . . . . . . . . . . . . . . . . . . . . . . . . . . . .
33
6.3.1. Algoritmos para reconocimiento en LR y en autómatas finitos . . . . . . . . .
33
6.3.2. Lector especial . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
33
6.3.3. Símbolos y unidades lexicográficas . . . . . . . . . . . . . . . . . . . . . . . .
33
6.3.4. Manejador de tablas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
34
6.3.5. Interacción entre el reconocedor y las tablas . . . . . . . . . . . . . . . . . . .
34
6.4. Otras consideraciones . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
36
6.4.1. Preámbulo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
36
6.5. Implementación de referencia - Lenguaje Java . . . . . . . . . . . . . . . . . . . . . .
36
6.5.1. Librería de soporte . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
36
6.5.2. Generación de reconocedores . . . . . . . . . . . . . . . . . . . . . . . . . . .
38
7. Diseño e Implementación
39
7.1. Extensión para el lenguaje Ruby . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
7.1.1. Composición de la librería de soporte
40
. . . . . . . . . . . . . . . . . . . . . .
40
7.1.2. Estructura de la definición gramatical y del reconocedor generado . . . . . .
41
7.2. Extensión para el lenguaje Python . . . . . . . . . . . . . . . . . . . . . . . . . . . .
42
7.2.1. Librería de soporte . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
42
7.2.2. Estructura de la definición gramatical y del reconocedor generado . . . . . .
43
7.3. Implementación . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
43
7.3.1. Interpretes para la JVM de los lenguajes destinos . . . . . . . . . . . . . . . .
44
7.3.2. Otras alternativas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
44
7.3.3. Estado actual de las extensiones . . . . . . . . . . . . . . . . . . . . . . . . .
44
8. Conclusiones y Recomendaciones
46
A. Ejemplos de gramáticas de Claire
51
A.1. Calculadora . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
51
A.1.1. Con destino en jruby . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
51
A.1.2. Con destino en jython . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
52
A.2. Lenguaje funcional . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
52
vii
A.2.1. Con destino en jruby . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
52
A.2.2. Con destino en jython . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
56
A.3. Subconjunto del lenguaje GaCeLa . . . . . . . . . . . . . . . . . . . . . . . . . . . .
57
A.3.1. Destino en jruby . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
57
A.3.2. Destino en jython . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
59
viii
Índice de tablas
4.1. Comparación de distintos generadores de reconocedores . . . . . . . . . . . . . . . .
ix
26
Índice de figuras
2.1. Algoritmo de reconocimiento LL . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
10
3.1. Esquema LR utilizado para el reconocimiento . . . . . . . . . . . . . . . . . . . . . .
20
6.1. Estructura del paquete ve.usb.Claire.runtime.java. . . . . . . . . . . . . . . . .
37
7.1. Estructura del módulo Claire::Runtime . . . . . . . . . . . . . . . . . . . . . . . .
40
7.2. Estructura del paquete claire.runtime . . . . . . . . . . . . . . . . . . . . . . . . .
42
x
Lista de Símbolos y Abreviaturas
Macro Abreviación de macroinstrucción.
LR Left to right, Rightmost Derivation, Reconocimiento de Izquierda a Derecha con Derivación
más a la Derecha
LALR Look-Ahead, Left to right, Rightmost Derivation, Reconocimiento con Previsión de Izquierda a Derecha con Derivación más a la Derecha
P Conjunto potencia.
LL Left to right, Leftmost Derivation, Reconocimiento de Izquierda a Derecha con Derivación Más
a la Izquierda
BNF Forma de Backus-Naur (Backus-Naur Form).
Token Unidad indivisible que posee algún significado dentro del lenguaje original.
Scanner o Lexer Programa que realiza el análisis lexicográfico de una entrada.
Parser Programa que realiza el análisis sintáctico de una entrada.
JVM Máquina Virtual de Java (Java Virtual Machine)
xi
Capítulo 1
Introducción
Las primeras computadoras de propósito general se crearon en la década de 1940 (la Z3 de Konrad Zuse en 1941 y la ENIAC en 1946). Estas computadoras poseen como característica fundamental
el ser programables, es decir, que pueden cargar y ejecutar conjuntos de instrucciones para realizar
diferentes labores. La programación en esa época se realizaba a través del lenguaje de máquina, una
serie de códigos en sistema binario que tenía algún significado en la máquina pero era muy díficil
de entender para un ser humano convencional.
Durante la evolución de las máquinas, la programación se iba complicando gracias a las nuevas
características que éstas empezaron a tener. La primera innovación (en la década de 1950) fue la
aparición del lenguaje ensamblador. Este lenguaje no es más que una representación simbólica de
los códigos utilizados en el lenguaje nativo de máquina, pero provee una capa de abstracción que
facilita el desarrollo de programas.
En 1954, John Backus publica la especificación de FORTRAN, un lenguaje que busca abstraer
más el proceso de programación, al introducir reglas y sintaxis más legibles para el humano. A partir
de la salida del primer compilador de FORTRAN (1957), se han desarrollado muchos lenguajes
de programación. Ahora el problema radica en construir los sistemas que permitan ejecutar los
programas en estos lenguajes.
La teoría de autómatas, cuya base está fundamentada en la teoría de lenguajes formales, formalizó el proceso de reconocimiento de lenguajes y sirvió de raíz para el desarrollo de los analizadores
sintácticos y lexicográficos utilizados en los compiladores. Para facilitar aún mas la implementación
de los lenguajes, se crearon herramientas que permiten generar estos analizadores.
1
Para solventar este problema, se han desarrollado muchas herramientas, pero con el pasar del
tiempo se han establecido dos que han marcado importancia en la historia de la rama. La primera
herramienta es el generador de reconocedores lexicográficos, que genera programas que deciden acerca de la pertenencia o no de una palabra en un lenguaje regular. Son programas básicos y sencillos,
que permiten separar la entrada en unidades léxicas que luego serán enviadas a un analizador más
sofisticado para su procesamiento. Un generador utilizado normalmente es Lex [1].
La otra herramienta es el generador de reconocedores sintácticos. Un generador automático de
reconocedores sintácticos recibe un conjunto de reglas sobre un lenguaje (la gramática de éste)
y produce un programa que dada una entrada (por lo general el resultado de un análisis lexicográfico), decide si esta entrada pertenece o no al lenguaje. Estas herramientas pueden, utilizando
algún lenguaje de programación de fondo, extender la capacidad de los reconocedores para efectuar
acciones o cambios sobre el estado dependiendo de lo que se ha analizado. Varios generadores de
reconocedores han surgido en los últimos tiempos, siendo Yacc [2] (o su alternativa libre, Bison [3])
el generador más conocido.
En 1998, María Eugenia Ahues, Bernardo Muñoz y Rui Santos (bajo la supervisión del prof.
Ascánder Suárez) de la Universidad Simón Bolívar desarrollaron el sistema Yacc4J [4] de generación
de reconocedores sintácticos. Luego, en el año 2000, Paúl Pacheco [5] (igualmente supervisado por
el prof. Ascánder Suárez) trabajó en la mejora y estabilización del sistema, el cuál fue rebautizado
como Claire. Este sistema está desarrollado bajo el lenguaje de programación Java.
Un reconocedor generado por Claire integra el análisis lexicográfico y sintáctico bajo una sola infraestructura. Además, Claire presenta la capacidad de generar reglas parametrizables, mejor
conocido como macros, y como punto central del trabajo, se puede extender para generar reconocedores en otros lenguajes, aunque actualmente solo lo hace para Java.
Este proyecto tiene como fin extender la herramienta para poder generar reconocedores en
lenguajes distintos de Java.
2
Capítulo 2
Marco Teórico
En este capítulo se expondrá la teoría de los lenguajes formales y el reconocimiento de éstos,
para luego poder introducir el concepto de compilador, su estructura y los distintos algoritmos
utilizados para poder realizar el reconocimiento de los lenguajes a compilar.
2.1.
Lenguajes Formales
Para poder definir lo que es un lenguaje se debe definir antes los conceptos de símbolo, alfabeto
y frase. Un símbolo es un objeto matemático particular, mientras que un alfabeto es un conjunto
finito, no vacío de símbolos. Una frase es una secuencia finita de símbolos de un alfabeto [6].
A partir de estos conceptos, se puede decir que un lenguaje es un subconjunto de todas las
frases derivadas de un alfabeto particular [6].
Una manera de describir y especificar un lenguaje es a partir de una gramática. La definición
de gramática formal, dada por Chomsky [7], es la siguiente: una gramática G es una 4-tupla
(N, Σ, P, S) donde:
N es un conjunto de símbolos no terminales.
Σ es el alfabeto, también denominado como el conjunto de símbolos terminales. Este conjunto
tiene que ser disjunto a N .
P un conjunto finito de reglas de producción. Una regla de producción es de la forma (Σ ∪
N )∗ N (Σ ∪ N )∗ → (Σ ∪ N )∗ , donde si A es un alfabeto, A∗ representa una secuencia de cero
3
o más símbolos del conjunto A.
Una regla de producción α → β (donde α ∈ (Σ ∪ N )∗ N (Σ ∪ N )∗ y β ∈ (Σ ∪ N )∗ ) indica
transformaciones de un símbolo no terminal, que puede estar rodeado de cualquier cantidad
de símbolos terminales y no terminales (el contexto de la regla), a una frase que contiene
símbolos terminales y no terminales. Una aplicación de esta regla sustituye instancias de α
por las correspondientes instancias de β.
S es el símbolo inicial de producción. Tiene que ser un símbolo no terminal.
Una forma sentencial es una frase generada a partir del símbolo inicial. Una derivación
es una aplicación sucesiva de reglas de producción que conlleva a una palabra del lenguaje. Una
derivación es más a la derecha si siempre se reemplaza los símbolos ubicados más al extremo derecho,
mientras que una derivación más a la izquierda hace los reemplazos a partir de los símbolos más a
la izquierda. Un árbol de derivación es un árbol cuyo despliegue representa una derivación.
Se define una ambigüedad como dos derivaciones que, partiendo del mismo símbolo y tomando
caminos distintos, generan la misma frase. Una gramática es ambigua si presenta ambigüedades y
un lenguaje es inherentemente ambiguo si toda gramática que genera este lenguaje es ambigua.
Dependiendo de la forma de las reglas de producción, se puede establecer una jerarquía de
lenguajes. Esta jerarquía se conoce como la jerarquía de Chomsky [7, 8] y se compone de la siguiente
forma:
Lenguajes regulares. Son todos los lenguajes que pueden ser reconocidos usando gramáticas
regulares. Una gramática es regular si solo tiene reglas de sustitución (A → a), reglas vacías
(A → , donde es la frase vacía) o reglas de la forma A → aB ó A → Ba (mas no pueden
convivir ambos tipos de reglas en la misma gramática), donde A y B son símbolos no terminales
y a es un símbolo terminal. Un formalismo utilizado para expresar lenguajes regulares y las
operaciones sobre éstos son las expresiones regulares (REs, [6]).
Lenguajes libres de contexto. Son los lenguajes cuyas gramáticas poseen reglas de producción que no dependen del contexto. Formalmente, una gramática de este tipo posee solamente
reglas del tipo A → γ, donde A es un símbolo no terminal, y γ es una frase que contiene símbolos terminales y no terminales. Una notación utilizada para expresar una gramática libre
4
de contexto es la forma Backus-Naur (BNF) [9, 10].
Lenguajes sensitivos al contexto. Las gramáticas de este lenguaje poseen reglas de la
forma αAβ → αγβ, donde α, β y γ son frases que contienen terminales o no terminales (α y
β sería el contexto de aplicación de la regla) y A es un símbolo no terminal.
Lenguajes irrestrictos. Son aquellos lenguajes cuyas gramáticas no poseen ninguna restricción en relación a sus reglas de producción.
Se puede observar que esta jerarquía es inclusiva - todo lenguaje regular es libre de contexto,
sensitivo al contexto y sin restricciones, pero no al revés, igual para los otros tipos de lenguajes.
Para efectos de este trabajo, se limitarán los lenguajes estudiados a los regulares y libres de
contexto.
2.2.
Reconocimiento de Lenguajes
Además de las gramáticas, existen otros formalismos para definir lenguajes. Uno de estos formalismos es el de los autómatas. Un autómata es una máquina cuya función es la de decidir si una
entrada pertenece o no a un lenguaje. Esta decisión se denomina reconocimiento de un lenguaje.
Según la jerarquía de Chomsky introducida en la sección 2.1, existen cuatro tipos de lenguajes.
Para cada clase de lenguaje, existe un tipo de autómata que permite reconocer esa clase.
2.2.1.
Autómatas Finitos
Un autómata finito es una máquina simple, sin memoria y compuesta de estados y una tabla
que contenga las transiciones entre estados, que reconocen los lenguajes regulares. Formalmente, un
autómata finito M es una 5-tupla M = (Q, Σ, δ, q0 , F ) donde:
Q es el conjunto finito de estados de la máquina
Σ es el alfabeto
δ : Q × (Σ ∪ {}) → P(Q) es la función de transición entre estados.
q0 ∈ Q es el estado en el que M inicia, y
5
F ⊆ Q es el conjunto de estados finales o de aceptación.
Un autómata finito se denomina no-determinístico sin -transiciones si, para todo estado
q, se tiene que δ(q, ) = ∅. Un autómata finito es determinístico si para todo estado q y todo
símbolo a del alfabeto se tiene que |δ(q, a)| ≤ 1. Se puede ver que todos estos tipos de autómatas
son equivalentes [6], al igual que los autómatas finitos son equivalentes a las gramáticas regulares y
a las expresiones regulares [6, 11]. En este trabajo, toda autómata finito va a referir a su variante
determinística.
Uno puede implementar un reconocedor de lenguajes regulares a mano, siguiendo el proceso de
reconocimiento de los autómatas finitos y replicando la función de transición de manera algorítmica.
2.2.2.
Autómatas de Pila
Los autómatas finitos, aunque reconocen todos los lenguajes regulares, no pueden reconocer los
lenguajes libres de contexto. Para poder reconocer estos, se necesita de una máquina más potente
para el reconocimiento de estos lenguajes.
Un autómata de pila es una extensión de los autómatas finitos, con la adición de una pila y de
control sobre la entrada para poder aumentar la capacidad de reconocimiento. La definición formal
de un autómata de pila M es una 7-tupla (Q, Σ, Γ, δ, q0 , Z0 , F ) tal que:
Q es el conjunto finito de estados de la máquina
Σ es el alfabeto de entrada
Γ es el alfabeto de la pila
δ : Q × Γ∗ × (Σ ∪ {}) → P(Q × Γ∗ ) es la función de transición entre estados.
q0 ∈ Q es el estado inicial de la máquina M
Z0 ∈ Γ es el símbolo tope inicial de la pila, y
F ⊆ Q es el conjunto de estados finales o de aceptación.
El autómata puede terminar de dos formas: al acceder a un estado final o al momento de consumir
toda la pila.
6
Un autómata de pila es determinístico si en cualquier estado q y pila Z, si δ(q, Z, ) 6= ∅ entonces
para todo símbolo a del alfabeto δ(q, Z, ) = ∅ y, en el caso de que no haya estado con pila sin
transición por palabra vacía, entonces solo puede haber a lo sumo una transición para cada símbolo.
Los autómatas de pilas generales pueden reconocer toda la clase de lenguajes libres de contexto [6, 11] pero, a diferencia de los autómatas finitos, los autómatas de pila determinísticos no
reconocen la totalidad de los lenguajes libres de contexto, pero esta pérdida de generalidad no
involucra ningún problema en la práctica, por lo que se usan normalmente para su reconocimiento.
2.2.3.
Técnicas especiales de reconocimiento
Desarrollar un autómata de pila puede llegar a ser un proceso complicado para lenguajes grandes, además que una probable implementación de ese autómata puede ser ineficiente, ya que puede
requerir volver a un estado anterior para probar nuevos estados. Para simplificar el proceso, existen
técnicas de reconocimiento que, sacrificando un poco la capacidad de reconocimiento total de los
autómatas de pila, son rápidas (evitan la necesidad de realizar backtracking sobre el árbol de derivación entero) y la dificultad de construcción de estos reconocedores son menores que los tradicionales.
De estas técnicas, hay dos importantes: los ascendentes, que construyen el árbol de derivación
a partir de las hojas, y los reconocedores descendentes que fabrican el árbol a partir de la raíz del
mismo.
2.2.3.1.
Reconocedores Ascendentes LR
Un reconocedor ascendente LR analiza la entrada de izquierda a derecha (L) construyendo
la derivación más a la derecha (R) que contenga la frase a reconocer. La idea por detrás de un
reconocedor LR es aplicar, de manera inversa, las derivaciones más a la derecha para llegar al
símbolo inicial, el cuál indica que la palabra ha sido aceptada.
Un reconocedor manual ascendente iría empilando los símbolos conseguidos hasta que pueda
asociar lo empilado con una regla, la cuál sustituiría lo empilado con el símbolo presente en la parte
izquierda de la regla. Ese conjunto de símbolos que se reemplazan se denomina asa o handle de
una forma sentencial. Formalmente, es una sub-frase que corresponde con una parte derecha de una
producción tal que su reemplazo por la parte izquierda correspondiente representa un paso a través
de una derivación más a la derecha. Un prefijo viable es un prefijo de la forma sentencial que no
7
continúa más allá del asa que se encuentra más a la derecha.
Para poder realizar un reconocedor LR(0), se necesita primero un autómata que reconozca todos
los prefijos viables de G. Para poder utilizar el autómata, se necesita del concepto de item. Un item
de una gramática G son todas las tripletas de la forma (A, α, β) tales que A → αβ es una producción
de G. Se denotan como A → α.β.
El autómata se construye de la siguiente forma: sea G = (N, Σ, P, S), se define un autómata
Mp = (Q, N ∪ Σ, δp , I0 , Q − {∅}) donde:
Q = P(Items(G))
I0 es la clausura de los ítems S → .α donde S → α pertenece a las producciones de G
δp (Ij , X) es la clausura de los ítems A → αX.β tal que A → α.Xβ pertenezca al conjunto de
ítems Ij .
Un reconocedor LR(0), utilizando el autómata Mp definido anteriormente, es un autómata de
pila cuya terminación es por pila vacía donde hace alguna de las siguientes acciones:
Empilar Si el símbolo J1 se encuentra en el tope de la pila y se reconoce a, empilar aJ2 si existe
una transición de (J1 , a) a J2 en Mp .
Reducir Si x1 J1 . . . xn Jn se encuentra en el tope de la pila y el item A → x1 . . . xn . pertenece al
conjunto de ítems Jn asociado a Mp , entonces se desempilan todos los símbolos hasta x1 y se
empila el símbolo A.
Salto Si J1 A se encuentra en el tope de la pila y existe una transición de (J1 A) a J2 en Mp , entonces
se empila J2 .
Terminar En el caso que I0 S queden en la pila, se vacía y se acepta la frase.
La máquina resultante de realizar estos pasos es el reconocedor LR(0) de G. El problema con
LR(0) es que no toda gramática reconocible por un autómata de pila determinístico puede ser
reconocido por un reconocedor LR(0) determinístico, ya que hay gramáticas que, conociendo la
existencia de autómatas de pila determinísticos que lo reconozcan, pueden generar reconocedores
LR(0) no determinísticos [11] o pueden existir conflictos. Un conflicto LR ocurre cuando existe,
8
en un conjunto de ítems, dos reglas que pueden inducir a acciones de empilar y reducción simultáneamente (conflicto de empilar-reducir) o dos acciones de reducción al mismo tiempo (conflicto de
reducir-reducir).
Para resolver el problema, se añade la idea de un conjunto de look-ahead o de previsión que
permita al autómata poder decidir que camino tomar. Este conjunto se construye a partir de los
símbolos que actúen como prefijos en las frases inmediatamente después de un asa. Se extiende el
concepto de item y de clausura para contemplar este nuevo conjunto y la construcción del autómata
ahora utiliza el conjunto de previsión para poder decidir a que estado se dirige. El autómata generado
por este nuevo proceso es un autómata LR(k) donde k es una cota al conjunto de previsión, aunque
siempre se toma 1 ya que todo reconocedor LR(k) puede ser reducido a un reconocedor LR(1).
Esta solución elimina los conflictos y el indeterminismo que puede surgir en un reconocedor
LR(0), llevando a que los reconocedores LR(1) sean más generales que estos, a cambio de una
explosión de espacio considerable (ya que la clausura de ítems ahora considera el conjunto de
previsión). Una optimización que se hace a un reconocedor LR(1) es el de mezclar los conjuntos de
ítems en el autómata de prefijos viables que contengan los mismos ítems, exceptuando los conjuntos
de previsión. Esta optimización, que se conoce como LALR, reconoce menos lenguajes que LR(1)
pero utiliza una cantidad notablemente menor de espacio que éste.
2.2.3.2.
Reconocedores descendentes LL
Los reconocedores LL, a diferencia de los LR introducidos en la sección 2.2.3.1, efectúan el
reconocimiento comenzando desde la raíz del árbol de derivación buscando la derivación más a la
izquierda. A diferencia de las gramáticas LR, una gramática LL tiene que cumplir con las siguientes
restricciones:
1. La gramática no puede ser recursiva a la izquierda.
2. Si existen dos reglas A → αβ y A → αγ, entonces α = .
3. Para cada par de no terminales A y terminal a, debe haber a lo sumo una producción que,
partiendo de A, derive palabras que empiezan en a.
Si una gramática cumple con estas restricciones, construir el reconocedor LL(1) que reconoce el
lenguaje se puede hacer de la siguiente forma:
9
function llparser(w, γ)
si w = $ ∧ γ = $ entonces
devolver true
si no, entonces si w = aw0 ∧ γ = aγ 0 entonces
devolver llparser(w0 , γ 0 )
si no, entonces si w = aw0 ∧ γ = Aγ 0 entonces
Sea M [A, a] = A → Y1 . . . Yk
devolver llparser(aw0 , Y1 . . . Yk γ 0 )
si no, entonces
devolver error
end si
end function
. a símbolo terminal
. A símbolo no terminal
Figura 2.1: Algoritmo de reconocimiento LL
Se construyen dos conjuntos, uno, denominado f irst(α) que contiene el conjunto de terminales
con las que comienzan las palabras derivadas de α (o la palabra vacía. en el caso que α derive a
) y otro, f ollow(A), que contiene los terminales que pueden aparecer inmediatamente después
de A en cualquier forma sentencial.
Se construye la tabla LL(1) con la información obtenida de los conjuntos f irst y f ollow.
La máquina parte con una pila cuyo tope es el símbolo inicial de la gramática, y la entrada.
El algoritmo de reconocimiento se especifica en la figura 2.1.
Los lenguajes LL(1) reconocen un grupo de lenguajes sin relación a los lenguajes LR(1) - hay
lenguajes LL(1) que no pueden ser reconocidos por una máquina LR(1) y viceversa. Los reconocedores LL(1) son fáciles de implementar – éstos se pueden implementar rápidamente gracias a una
técnica denominada descenso recursivo. El descenso recursivo asocia cada regla con funciones que se
llaman recursivamente, de tal forma que el reconocimiento y ejecución de las reglas es una secuencia
de llamadas de estas funciones.
2.3.
Compilador. Definición y Estructura
Un compilador es un programa que lee un programa escrito en un lenguaje denominado fuente
y lo traduce en un programa equivalente en otro lenguaje, llamado lenguaje destino [12].
Aunque los compiladores varían de muchas formas (lenguaje destino, forma de reconocimiento
o funciones realizadas), éstos siguen un modelo estándar. Este modelo separa a la compilación en
10
dos fases importantes: análisis y síntesis. El análisis de un programa busca construir una forma
intermedia del programa y comprobar que este programa sea válido según la especificación del
lenguaje fuente, mientras que la síntesis busca, dada una representación intermedia de un programa
obtenida del proceso anterior, construir la representación en el lenguaje de destino [12]. La fase de
importancia de este trabajo es la fase de análisis.
2.4.
Análisis de un Programa
Para que un compilador pueda reconocer la entrada, y comprobar que es un programa válido
para el lenguaje fuente, se necesita realizar un análisis. Este análisis se divide en tres fases: análisis
lexicográfico, análisis sintáctico y análisis semántico.
2.4.1.
Análisis Lexicográfico
El análisis lexicográfico busca, dado un flujo de caracteres que representa el programa en el
lenguaje fuente, leer el flujo de manera lineal y agrupar éste en unidades indivisibles que posean
algún significado (token). La porción del compilador encargado de realizar este análisis se denomina
scanner, lexer o analizador lexicográfico. Un analizador lexicográfico se puede implementar con un
autómata finito que reconozca el lenguaje.
2.4.2.
Análisis Sintáctico
El análisis sintáctico intenta determinar, observando el orden en el que se encuentran los tokens
en el programa original (proveniente del resultado del análisis lexicográfico), si la entrada se puede
agrupar de manera jerárquica en colecciones anidadas con un significado mayor que el que puede
poseer un token solo. El programa que se encarga de efectuar el análisis recibe como nombre parser
o analizador sintáctico y éste genera un árbol sintáctico – una representación intermedia del programa en forma de árbol para una fácil navegación. El mecanismo general utilizado para el análisis
sintáctico es el reconocimiento de lenguajes libres de contexto, en especial los autómatas LR, LL y
LALR, explicados en la sección 2.2.3.1.
11
2.4.3.
Análisis Semántico
El análisis semántico revisa el árbol sintáctico generado por la fase del análisis sintáctico y
comprueba que el programa cumple las reglas semánticas del lenguaje, y completa el árbol sintáctico
con información necesaria para poder realizar la síntesis. Los chequeos que se pueden realizar en esta
fase son variados y depende del lenguaje. Algunos ejemplos de chequeos que se hacen son: análisis
de tipos, coherencia de variables con respecto a su declaración y optimización de código entre otros.
12
Capítulo 3
Introducción a la Herramienta Claire
3.1.
Introducción a Claire
Claire es un generador de reconocedores sintácticos desarrollado en el lenguaje de programación
Java por María Eugenia Ahués, Bernardo Muñoz y Rui Santos en el año 1998 [4] y mejorado por
Paúl Pachecoen el año 2000 [5]. Algunas características notables de esta herramienta son:
Los reconocedores generados con Claire son, por defecto, LALR(1) [13], aunque se pueden
generar reconocedores LR(1) pero estos no se utilizan a costa del tamaño de los reconocedores.
Un reconocedor de Claire integra la fase de análisis lexicográfico y sintáctico en una sola
herramienta, eliminando así la necesidad de integrar dos herramientas separadas.
Claire fué diseñado para poder generar reconocedores sintácticos en cualquier lenguaje, siempre y cuándo la extensión para el lenguaje correspondiente esté presente.
Claire posee unas reglas especiales, denominadas macros, que permiten generar reglas gramaticales parametrizadas para ser usadas en cualquier regla.
Entre los usos notables de la herramienta están:
El lenguaje de programación GaCeLa, un dialecto del lenguaje GCL de Edsger W. Dijkstra.
Los proyectos de grado de Wendi Uribarri y de Alejandro Ibarra sobre un editor de especificaciones y de refinamiento de algoritmos basado en la teoría de Carroll Morgan.
13
El proyecto de grado de Gabriela Montoya sobre verificación dinámica en Java.
La práctica de la asignatura “Traductores e Interpretadores” en la Universidad Simón Bolívar.
3.2.
Definición de una Gramática en Claire
La herramienta Claire tiene como entrada una gramática. La definición de esta gramática de
entrada puede llevar los siguientes componentes:
Preámbulo
Directivas referentes a la gramática
Definiciones de las reglas sintácticas
Definiciones de las reglas lexicográficas
3.2.1.
Preámbulo
El preámbulo es un fragmento de código del lenguaje destino, el cuál puede definir o ejecutar
código (dependiendo del lenguaje) antes de la definición de la gramática.
El preámbulo puede empezar de dos formas: o utilizando código directamente (e indicar en la
línea de comando cuál es el lenguaje destino, o utilizar el lenguaje defecto que es Java) o indicar el
lenguaje utilizando la directiva lang.
3.2.2.
Directivas del reconocedor
Claire acepta las siguientes directivas:
Directiva start: indica al reconocedor cuales son los posibles puntos de inicio en el autómata
LR. Por defecto, Claire empieza en la primera regla sintáctica definida.
Directiva expand: determina el número máximo de expansiones de las macros. Mayor información relacionada a las macros en la sección 3.2.3.2.
Directiva nomain y main: indica a Claire si el reconocedor generado va a incluir o no el
código necesario para que el reconocedor funcione como un programa.
14
3.2.3.
Definición de las reglas
En esta sección del archivo de definiciones, se encuentran las reglas que definen la gramática.
Hay dos tipos de reglas: las reglas lexicográficas, que definen los tokens asociados al lenguaje, y las
reglas sintácticas, que definen las producciones del lenguaje libre de contexto.
3.2.3.1.
Reglas lexicográficas
Una regla lexicográfica se define en Claire utilizando expresiones regulares. El formato de las
expresiones regulares utilizadas en la herramienta se encuentra en [5, 13, 14].
En el caso que se consigan dos expresiones regulares en sucesión, Claire dará prioridad siempre
a la primera expresión regular encontrada. Esto se puede evitar indicando el orden apropiado, o
utilizando alias para identificar las expresiones regulares.
Alias
Un alias es un identificador que se le puede asignar a un símbolo. Son utilizados principalmente
para poder identificar expresiones regulares. Un alias, en Claire se define de la siguiente forma:
alias = símbolo
En cualquier parte de la gramática que se necesite el símbolo, se puede utilizar el alias y Claire
se encarga de realizar la sustitución correspondiente.
3.2.3.2.
Reglas sintácticas
La definición de una regla sintáctica en Claire es de la forma:
parteIzquierda : parteDerecha
Varias reglas pueden utilizar la misma parte izquierda. En el caso que esto ocurra, se pueden
agrupar esas reglas como:
parteIzquierda : parteDerecha1
| parteDerecha2
| ...
| parteDerecha_n
15
Una parte derecha puede tener cero o más símbolos gramaticales, expresiones regulares o alias,
separados con espacios en blanco. En el caso de no tener símbolos, se deja la regla en blanco.
Precedencia y Asociatividad
Pueden existir gramáticas que posean ambigüedades. Para evitar estas ambiguedades (que pueden evitar que un reconocedor funcione correctamente), se puede romper las ambigüedades usando
reglas de precedencia y asociatividad.
Una regla de precedencia se representa como un número entero después de la regla correspondiente tal que mientras menor sea el número, menor es la precedencia de la regla y, por consiguiente,
esa regla tiene mayor prioridad para ser reconocida de primero. La sintaxis para asignar precedencia
es:
parteIzquierda : parteDerecha1
prec1
| parteDerecha2
prec2
| ...
| parteDerecha_n
precn
En el caso de que la reglas tengan la misma precedencia, se puede usar la asociatividad. Las
reglas de asociatividad se definen en Claire como:
parteIzquierda : parteDerecha
prec
%asoc
Una regla puede asociarse a la izquierda ( %left), a la derecha ( %right) o puede no tener asociatividad ( %nonassoc).
Acciones semánticas
A cada regla de la gramática se le puede asignar una acción semántica, que es una porción de
código del lenguaje destino que será ejecutado al momento de reconocer la regla. La sintaxis para
las acciones semánticas es la siguiente:
parteIzquierda : parteDerecha
{ codigo }
En el caso en el que el lenguaje destino acepte tipos (como es el caso de Java, el lenguaje por
defecto de Claire), se puede indicar a Claire cuál es el tipo de datos asociado a la regla. Para indicar
esto, se utiliza:
16
<Tipo>parteIzquierda : parteDerecha
{ codigo }
Dentro del código asociado a la acción semántica, se pueden utilizar dos tipos de variables:
Variables que indican el valor de un símbolo en específico. En el caso de Java, estas variables
se definen como $n, donde n es la posición del símbolo a partir del símbolo inicial (que es el
símbolo 0).
La variable $$ que define el resultado de la regla. Esta variable tiene que tener un valor del
tipo definido en la regla.
El valor devuelto por una expresión regular es siempre del tipo que define las cadenas de caracteres en el lenguaje de destino (en el caso de Java, String).
Macros
Una macro se define, en el contexto de Claire, como una regla gramatical parametrizada, en
donde los parámetros son símbolos gramaticales. Una macro puede utilizar sus parámetros en la
mano derecha y puede invocarse recursivamente.
Un ejemplo de una macro es la clausura reflexivo-transitiva (o estrella de Kleene). Una macro
que define este operador sería:
estrella(regla) : estrella(regla) regla
| /* vacio */
Claire, al encontrar una llamada de macro, realiza la expansión de ésta, que genera una regla
nueva, reemplazando los parámetros con el valor correspondiente y las llamadas recursivas por el
símbolo asociado a la regla nueva.
Un problema que puede existir con las llamadas recursivas en una macro, es que pueda ocurrir
un ciclo infinito. Sea la siguiente macro:
m(x) : m(m(x))
Al expandir la llamada de m, Claire encuentra una llamada no recursiva y realiza una nueva expansión. Al expandir la nueva regla, observa que tiene que expandir otra vez la misma regla y así sigue
hasta el infinito. Para evitar estos ciclos, se tiene un límite al número de expansiones, que se puede
17
especificar en la gramática o como un parámetro al momento de generar el reconocedor. Al llegar
al número máximo de expansiones, se cortan y se emite una advertencia al usuario.
3.3.
Estructura Interna de Claire
Claire está compuesto por cinco módulos importantes:
Reconocimiento de la gramática y las unidades sintácticas.
Reconocimiento de las unidades lexicográficas.
Generación de tablas.
Generación de los reconocedores.
Librerías de soporte para la ejecución.
Se pueden dividir estos módulos en dos grupos: aquellos módulos que no dependen del lenguaje
destino, y aquellos que si. Los tres primeros módulos no son dependientes del lenguaje a la cual
se va a generar el reconocedor, ya que se encargan de procesar la gramática y de obtener los
datos necesarios para la construcción del reconocedor. En cambio, la generación y traducción del
reconocedor y las librerías de soporte si dependen del lenguaje. Se puede observar que, para acoplar
un nuevo lenguaje, simplemente se tiene que trabajar en los dos últimos módulos.
Se procede a describir cada módulo, aunque no se va a ahondar mucho en los módulos que no
dependen del lenguaje. Una explicación más profunda referente a estos módulos se encuentra en [5].
3.3.1.
Reconocimiento de la gramática
El módulo de reconocimiento de gramáticas es el principal motor de Claire para la generación de
reconocedores, ya que realiza las labores de procesar la gramática recibida, de invocar al módulo de
unidades lexicográficas para construir el AFD que reconozca las expresiones regulares y de generar
las tablas LR/LALR en conjunción con el módulo de generación de tablas.
El resultado de la aplicación de este módulo es una estructura que contiene toda la información
relacionada al reconocedor de la gramática recibida (tablas, código a sustituir y los índices necesarios
para el funcionamiento de la tabla).
18
Este módulo está implementado en el paquete ve.usb.Claire.contextFree de la distribución
de Claire.
3.3.2.
Reconocimiento de las unidades lexicográficas
Este módulo se encarga de reconocer todas las expresiones regulares, y construir el autómata finito que reconozca estas expresiones. Dentro de la distribución de Claire, el paquete ve.usb.Claire.
regexp contiene el reconocedor de expresiones regulares y los métodos asociados al manejo de éstos.
3.3.3.
Generación de tablas
Este módulo tiene como fin el dar una infraestructura para el manejo de tablas, incluyendo la
definición de la tabla, sus métodos asociados y los métodos para la creación de tablas. La estructura
completa de las tablas aparece explicado en [5]. Este módulo reside, dentro de la distribución, en el
paquete ve.usb.Claire.table.
3.3.4.
Construcción de reconocedores
Ya después de haber procesado la entrada, y haber generado los datos referentes al lenguaje,
este módulo utiliza estos datos para poder construir el reconocedor en el lenguaje objetivo. Para
construir el reconocedor, Claire necesita de dos componentes: una plantilla que contenga un esquema
del reconocedor en el lenguaje destino y un traductor que pueda llenar la plantilla con los datos
relacionados a la gramática y sus acciones.
El contenido de la plantilla depende del lenguaje, pero debe tener capacidad de guardar la tabla
y los índices necesarios para poder obtener los datos de ésta, un método, procedimiento o función
para ejecutar las acciones asociadas a las construcciones gramaticales, y un sitio en donde se pueda
escribir el preámbulo especificado en la gramática fuente.
El traductor se encarga de escribir la plantilla con los datos recibidos del resultado del reconocimiento de la gramática, y generar el reconocedor en el lenguaje destino.
3.3.5.
Paquete de ejecución dependiente del lenguaje
Para poder ejecutar los reconocedores generados por Claire, se necesitan los siguientes componentes implementados en el lenguaje de destino:
19
pila ← pilaV acia
empilar(s0 , pila)
ip ← apuntador al primer símbolo de w$
por siempre hacer
s ← el estado en el tope de la pila
a ← el símbolo apuntado por ip
si action(s, a) = empilar s0 entonces
empilar(a, pila)
empilar(s0 , pila)
Avanzar ip al próximo símbolo de entrada
si no, entonces si action(s, a) = reducir A → β entonces
Desempilar 2|β| de la pila.
s0 ← el estado al tope de la pila
empilar(A, pila)
empilar(goto(s0 , A), pila)
Ejecutar la acción asociada a la producción A → β usando los valores en pila
si no, entonces si action(s, a) = aceptar entonces
return
end si
end por
Figura 3.1: Esquema LR utilizado para el reconocimiento
El autómata LR para poder realizar el reconocimiento de las reglas sintácticas. Este necesita
de la tabla (generada en la gramática) y del algoritmo LR. La versión utilizada por Claire se
muestra en la figura 3.1.
Un algoritmo que simule un autómata finito para el reconocimiento de las reglas lexicográficas
a partir de la entrada.
Un manejador nativo para las tablas LR y LALR.
3.4.
3.4.1.
Generación de Reconocedores en Claire
Reconocimiento de la gramática
La herramienta, al inicio, recibe por entrada una gramática (que no necesariamente posee código
válido del lenguaje destino) y, en el caso que ésta sea válida, se expanden las macros, se resuelven
los alias o nombres utilizados en la gramática fuente y se genera, de la gramática resultante, una
representación intermedia que contiene las reglas y las expresiones regulares.
20
3.4.2.
Generación de las tablas
Claire, en este punto, procede a generar la tabla LR asociada a la gramática. Por defecto,
intentará construir la tabla LALR aunque, en el caso que la gramática no pueda ser reconocida por
una tabla LALR el usuario puede solicitar que se genere la tabla LR(1) asociada a este.
Las tablas, en Claire, se construyen en dos etapas: la primera, Claire genera la tabla LR/LALR
asociada a la gramática y luego se comprimen de tal forma que los espacios vacíos se reutilicen con
la información asociada a otros estados. El resultado de esta compresión son dos tablas, la tabla
index que contiene los índices en que empiezan los datos asociados a un estado, y una tabla general
que contiene el resultado de la tabla, comprimido.
Para mayor información asociada a la compresión de las tablas, revisar [5].
3.4.3.
Traducción al lenguaje destino
Ya procesada la gramática y generada la tabla, el siguiente paso es generar el reconocedor en el
lenguaje destino. Esto involucra traducir la gramática, las acciones y las tablas al lenguaje destino.
El traductor realiza las siguientes acciones, en orden:
En el caso que el lenguaje lo facilite, reconocer el preámbulo para obtener información relevante, por ejemplo, la definición de la clase de Java más externa asociada al archivo (como
debe haber una sola clase por archivo fuente, entonces el reconocedor estará implementado en
esta clase).
Sustituir las porciones de la plantilla asociada al lenguaje (tanto las mencionadas en la sección 3.3.4 con los códigos o valores asociados a la gramática actual).
Reemplazar toda variable $n y $$ en las acciones asociadas a las reglas gramaticales con los
valores correspondientes en la pila LR.
El resultado de estas acciones es un programa en el lenguaje destino que sirve como reconocedor
del lenguaje especificado originalmente en la gramática.
21
3.5.
Estado Actual
Antes de comenzar con el trabajo, la herramienta Claire se encuentra en la versión 5.10, publicada en noviembre del 2005. Todos los componentes anteriormente mencionados funcionan completamente, pero solo genera reconocedores para el lenguaje de programación Java (de la versión 1.4
en adelante).
22
Capítulo 4
Herramientas Relacionadas
En este capítulo se presentan otros generadores de reconocedores sintácticos que generan reconocedores para los lenguajes anteriormente tratados y que se usan en la actualidad. Se plantea
además, una comparación entre estos, la cuál está reflejada en la tabla 4.1.
4.1.
JavaCC
El generador de reconocedores JavaCC (Java Compiler Complier) [24] es uno de los generadores
de reconocedores más utilizados en aplicaciones Java. Fue creado en 1996 como un proyecto de Sun
Microsystems para desarrollar un generador de reconocedores LL(k). La versión más reciente (hasta
este momento) es la 4.0.
4.1.1.
Características de JavaCC
JavaCC genera reconocedores LL(k), donde la k se puede especificar para cada regla aparte,
de ser necesario. Por defecto, JavaCC genera reconocedores LL(1).
Utiliza una notación BNF extendida.
Integra análisis lexicográfico y sintáctico en el mismo paso.
Genera reconocedores nada más para el lenguaje de programación Java.
Incluye herramientas para el preprocesamiento de árboles, documentación y reporte de errores.
23
4.2.
ANTLR
ANother Tool for Language Recognition (ANTLR) [25] es una herramienta desarrollada por el
prof. Terrence Parr de la Universidad de San Francisco cuyo fin es la automatización de labores
de generación de reconocedores descendientes recursivos. Fue diseñado con la capacidad de generar
salidas para varios lenguajes y ya tiene varios lenguajes implementados. La principal innovación de
ANTLR es su técnica de reconocimiento, denominada LL(*), que permite variar el look-ahead sin
necesidad de fijarlo. La versión más reciente de ANTLR es la 3.1.
4.2.1.
Características de ANTLR
ANTLR genera reconocedores LL(*), una variación de los reconocedores LL(k) con conjuntos
look-ahead arbitrarios determinados por el algoritmo.
Utiliza una notación similar a la notación BNF extendida.
Genera reconocedores lexicográficos y sintácticos separadamente, pero usando el mismo archivo de definición. No hay necesidad de un reconocedor lexicográfico aparte.
Tiene capacidad para generar reconocedores en varios lenguajes destino: Java, C, C++, C#,
Objective/C, Python y Ruby.
4.3.
CUP
Basado en la herramienta Yacc [2], Java(tm) Based Constructor of Useful Parsers (CUP) [26]
es un generador de reconocedores sintácticos LALR para Java. Fue diseñado para ser muy parecido
a Yacc, con la diferencia de que genera reconocedores en Java en vez de C, y que utiliza código
embebido Java. La versión más reciente de CUP es 0.10k (estable) y 0.11a (beta).
4.3.1.
Características de CUP
Los reconocedores generados por CUP son LALR(1).
Utiliza una notación similar a BNF simple.
Requiere de un reconocedor lexicográfico aparte, como por ejemplo, JLex [27] o JFlex [28].
24
Sólo genera reconocedores para Java.
4.4.
Yapps
Yet Another Python Parsing System (Yapps) [29] es un generador de reconocedores desarrollado
en Python por Amit Patel. Fue diseñado principalmente para ser fácil de usar y que se pueda integrar
a Python. El principal defecto de este reconocedor es que solo puede reconocer strings. Esto se puede
pasar si se lee todo el archivo y luego se reconoce con Yapps, pero no es recomendable para archivos
muy grandes. La última versión de Yapps es la 2.0.4 (estable) y 2.1.1 (desarrollo). No se actualiza
desde el 2003.
4.4.1.
Características de Yapps
Los reconocedores de Yapps son LL(1).
Utiliza un subconjunto de la notación BNF extendida.
Genera sus propios reconocedores lexicográficos.
Está hecho en Python y solo genera reconocedores en Python.
Solo es capaz de reconocer strings. No está diseñado con archivos en mente.
4.5.
SPARK
SPARK [30] es un reconocedor desarrollado en Python cuya característica principal es que utiliza
el algoritmo de reconocimiento de Earley [31] como la técnica de reconocimiento. Este algoritmo
es más general que LR(1) o LL(k), a cambio de velocidad. SPARK ha ganado reconocimiento al
integrarse a la distribución estándar de Python.
4.5.1.
Características de SPARK
Utiliza el algoritmo de Earley para reconocimiento sintáctico.
Utiliza notación BNF.
25
Claire
JavaCC
ANTLR
JavaCUP
Yapps
SPARK
Racc
Tipo
LR(1) / LALR(1)
LL(1) / LL(k)
LL(*)
LALR(1)
LL(1)
Earley
LALR(1)
Lexer?
Propio
Propio
Propio
Requiere
Propio
Propio
Requiere
Destinos
Java
Java
Java, C/++, Python, Ruby
Java
Python
Python
Ruby
Notación
BNF c/ macros
BNF extendido
BNF extendido
BNF
BNF extendido
BNF
BNF
Tabla 4.1: Comparación de distintos generadores de reconocedores
Genera sus propios reconocedores lexicográficos.
Está hecho en Python y solo genera reconocedores en Python.
4.6.
Racc
Racc [32] es un generador de parser desarrollado totalmente en Ruby. Al igual que CUP, éste está
diseñado para ser una implementación de Yacc en Ruby que utilice las características del lenguaje.
La versión más nueva de Racc es 1.4.5.
4.6.1.
Características de Racc
Genera reconocedores LALR(1).
Utiliza una notación similar a BNF simple.
Requiere de un reconocedor lexicográfico aparte.
Hecho en Ruby y genera reconocedores para este.
26
Capítulo 5
Planteamiento del Problema
En el capítulo anterior, se presentó la herramienta Claire, la estructura de la herramienta y un
esquema de su funcionamiento. La herramienta se compone de dos partes importantes: reconocimiento de la gramática y generación de tablas (que no depende del lenguaje destino), y generación
de reconocedores sintácticos y las librerías de soporte de ejecución (que si depende del lenguaje).
Como se puede apreciar en la sección 3.5, la herramienta solo genera reconocedores para el
lenguaje Java. El problema a tratar en este trabajo es el de expandir la herramienta Claire para
poder permitir la generación de reconocedores sintácticos en otros lenguajes.
Paúl Pacheco, en [5], especifica que una extensión del generador en Claire requiere de la implementación de los siguientes componentes:
Traductor específico al lenguaje.
Implementación de los autómatas LR y los autómatas finitos determinísticos necesarios para
el reconocimiento.
Manejador de las tablas LR y LALR.
Estructuras y componentes necesarios para la ejecución de estas.
Para poder desarrollar esta extensión, se tomaron en cuenta los siguientes pasos:
Evaluar el mecanismo de Claire para la generación de reconocedores para lenguajes distintos
de Java. Esto fue expuesto en las secciones 3.3 y 3.4.
27
Estudiar y seleccionar los posibles lenguajes de programación que puedan servir de destino
para un reconocedor en Claire.
Diseñar las extensiones para que Claire pueda generar reconocedores en otros lenguajes.
Especificar e implementar estas extensiones para varios lenguajes.
5.1.
Lenguajes Seleccionados
Para determinar los nuevos lenguajes destino para la herramienta, se tomaron en cuenta distintos parámetros: uso del lenguaje, popularidad, auge, existencia o no de herramientas estables
de generación de reconocedores y facilidad de desarrollo de la extensión para el lenguaje. De los
lenguajes estudiados, se consideraron extensiones de Claire para cuatro lenguajes: Ruby, Python,
Groovy [15] y JavaFX Script [16]. De estos lenguajes, solo las extensiones para Ruby y Python
fueron diseñadas e implementadas.
5.1.1.
Lenguaje de Programación Ruby
Ruby [17] es un lenguaje de programación orientado a objetos, cuya primera versión surgió en
1995 (0.95) y que actualmente goza de una gran popularidad gracias al framework de aplicaciones
web Ruby on Rails. La versión actual, para el momento de publicación de este trabajo, es 1.8.6.
Como lenguaje, Ruby toma inspiración de dos lenguajes principalmente: Perl y Smalltalk. De
Perl adquiere la base técnica – la sintaxis es muy parecida, el lenguaje es interpretado y el sistema
de tipos de Ruby es dinámico al igual que Perl, mientras que de Smalltalk toma la orientación a
objetos pura, es decir, que todos los tipos de datos en Ruby son objetos, incluyendo los tipos de
datos primitivos en otros lenguajes de programación con el mismo paradigma como Java o C++.
Ruby carece de un manual de referencia oficial actualizado - el manual de referencia más reciente
hace mención a la versión 1.4 (año 1998, [18]) mientras que la versión más actual de Ruby es la
versión 1.8 (2005), aunque [19] ha servido como referencia del lenguaje en estos últimos años.
5.1.1.1.
Características de Ruby
Ruby es un lenguaje orientado a objetos puro
28
Soporta herencia simple y herencia mezclada - importación textual de módulos en la definición
de una clase.
El sistema de tipos es dinámico
Realiza el manejo de memoria automáticamente, con recolección de basura
El lenguaje es interpretado
Soporta clausuras e iteradores, usando bloques de código como parámetros.
Permite sobrecarga de operadores ya existentes, mas no sobrecarga de métodos, procedimientos o funciones en el mismo alcance.
Permite agregar nuevas definiciones de métodos y variables a clases y módulos (el equivalente
a paquetes en Java) ya definidos.
5.1.2.
Lenguaje de Programación Python
Python, por su parte, nació a finales de la década de 1980, hecho por Guido van Rossum como
un sucesor de un lenguaje utilizado en el Instituto de Investigación Nacional para las Matemáticas
y Ciencias de la Computación de los Países Bajos. La primera versión de Python (versión 0.9.0) fue
publicada en 1991. La versión más reciente del intérprete oficial es la 2.5.1.
El diseño de Python gira alrededor de tres factores fundamentales: ser un lenguaje multiparadigma, contener un núcleo simple con una librería extensible y promover la legibilidad, claridad
y simplicidad por encima de sintaxis ofuscada (como, por ejemplo, Perl).
El lenguaje núcleo, en su totalidad, se encuentra especificado en [21].
5.1.2.1.
Características de Python
Python es un lenguaje que soporta múltiples paradigmas.
Soporta herencia múltiple.
El sistema de tipos es dinámico
Realiza el manejo de memoria automáticamente, con recolección de basura
29
El lenguaje es interpretado
Soporta clausuras e iteradores.
Permite sobrecarga de operadores ya existentes, mas no sobrecarga de métodos, procedimientos o funciones en el mismo alcance.
Python no permite aumentar las definiciones de una clase, es decir, que toda nueva definición
de una clase sobreescribe cualquier definición hecha anteriormente.
30
Capítulo 6
Referencia de una Extensión
En las secciones 3.3.4, 3.3.5 y el capítulo 5 se especifican tanto los componentes de Claire como
el contenido de una extensión de la misma herramienta. En este capítulo se expone el contenido de
una extensión y la implementación original en el lenguaje Java.
6.1.
Estructura de una Extensión
Una extensión de Claire para generar reconocedores para un lenguaje, como fue especificado
en 5, debe contener los siguientes componentes:
Traductor de acciones y generador de archivos fuentes en el lenguaje destino (desarrollado en
el lenguaje de programación Java).
Implementación de las librerías de soporte (en el lenguaje de destino). Los contenidos de esta
librería son:
• Algoritmos para reconocimiento de un reconocedor LR y de un autómata finito.
• Manejador de las tablas asociadas al reconocedor LR.
• Estructuras necesarias para la ejecución del reconocedor.
A continuación se introducirá cada una de las componentes esenciales para la implementación
de una extensión.
31
6.2.
Generación de reconocedores
El módulo de generación de reconocedores para un lenguaje, en Claire, es una clase desarrollada
en Java (el lenguaje en el cual Claire está basado) que permite a la herramienta generar reconocedores. Esta clase se encarga de crear los archivos fuente, utilizando posiblemente una plantilla; el
reconocedor resultante en el lenguaje destino. Además de escribir el reconocedor, debe escribir en
el archivo el preámbulo (si lo hay), la tabla LR/LALR resultante, la tabla de chequeo asociada a
ésta y los índices de localización de los datos necesarios en esta tabla. Éstos índices son:
Identificador de fin de archivo.
Índice de la tabla de acciones.
Índice de la tabla de saltos (o goto).
Índice de los símbolos de reducción por defecto.
Índice de las longitudes de las reglas.
Índice de las partes izquierdas de las reglas.
Índices del autómata finito (ubicación de la tabla asociada a ésta, los inicios de las tablas y
las ubicaciones respectivas en la tabla de chequeo).
Además, este módulo debe traducir las acciones a instrucciones válidas del lenguaje y permitir
ejecutar éstas, pudiendo distinguir la acción a ejecutar.
En conjunción con esta clase, uno puede tener una plantilla para generar el reconocedor fácilmente, indicando solamente los sitios donde se ubican los datos importantes. Una plantilla debería
contener un esqueleto de un programa con indicadores para ser reemplazados por los datos correspondientes.
Todas las clases que implementan los traductores de acciones y de generación de reconocedores
se ubican en el paquete ve.usb.Claire.translator. En el caso de Java, el subpaquete java del
paquete mencionado anteriormente se encuentra el traductor asociado a Java. Para poder indicarle
a Claire que una extensión existe, hay que modificar el archivo translators.list que contiene la
lista de traductores existentes. Un traductor se instala colocando la siguiente línea:
32
lang=class
donde lang es el nombre con el que se identificará el lenguaje tanto en la línea de comandos como
en la directiva lang del archivo de definiciones, y class la ruta completa al traductor.
Para detalles de implementación de un traductor, puede revisar en la distribución la clase
ve.usb.Claire.translator.java.JAVA.
6.3.
Librerías de soporte para ejecución
6.3.1.
Algoritmos para reconocimiento en LR y en autómatas finitos
Claire es un generador de reconocedores LR/LALR. Como tal, se requiere del algoritmo de
reconocimiento para autómatas LR, para poder ejecutar un reconocedor. Éste algoritmo está especificado en la figura 3.1.
Además, para poder reconocer las unidades lexicográficas, se requiere de un algoritmo que permita simular un autómata finito. Éste algoritmo es usado para dos funciones distintas: la primera,
para obtener la unidad lexicográfica actual y la segunda para obtener la unidad que debe seguir
dado un estado en el autómata LR. Este algoritmo toma su entrada de un lector especial, explicado
en la seccion 6.3.2.
6.3.2.
Lector especial
Para el funcionamiento correcto de los autómatas, se puede necesitar de un lector que tenga
capacidad de marcar una posición dada y que sea capaz de volver a esa posición sin ningún problema.
Además, el lector debe ser capaz de tomar una unidad lexicográfica y volver a leerla en el caso de
ser necesario.
Es recomendable que este lector, en vez de implementarse totalmente, sea un envoltorio a la
infraestructura de lectura del lenguaje destino, respetando las reglas asociadas a los lectores en éste
lenguaje.
6.3.3.
Símbolos y unidades lexicográficas
Un símbolo puede ser el resultado de un reconocimiento empleado en la pila, o puede contener
una unidad lexicográfica completa. Por lo tanto, puede ser necesario realizar una distinción entre
33
ambas.
Un símbolo genérico debe contener un identificador que permita reconocer si el símbolo representa el final de la entrada o no (que será asignado por el algoritmo a tiempo de reconocimiento), y
un valor, que puede venir dado por el reconocimiento de reglas con acciones, o simplemente llevar un
valor que lo asocie al símbolo sin valor. Además, puede llevar datos como la ubicación en el archivo
fuente y el estado sintáctico donde se generó este símbolo. Una unidad lexicográfica, además de
llevar estos elementos, debe tener la capacidad de devolver la representación de la unidad como fue
reconocida para que el lector definido en la sección 6.3.2 pueda volverlo a leer.
6.3.4.
Manejador de tablas
Esta componente debe implementar los métodos para poder extraer los datos de las tablas. La
estructura de las dos tablas (la tabla estándar LR y la tabla de chequeo) se encuentran definidas
en [5].
Los métodos que debe implementar un manejador de tablas son:
Compresión y descompresión de tablas (en el caso que la tabla venga comprimida).
Obtención de datos de las tablas. Específicamente, estos métodos deben permitir la extracción
de los datos en una posición determinada, el bit/byte/carácter o entero ubicado en esa posición.
Puede tomar en cuenta o no la tabla de chequeo.
Métodos para reconstruir enteros y otros tipos de datos (dependiendo de la implementación
usada).
6.3.5.
Interacción entre el reconocedor y las tablas
Para que un reconocedor pueda funcionar, este tiene que implementar un conjunto de métodos
de tal forma que se pueda extraer los datos necesarios. Como se puede observar en la sección 6.3.4,
los métodos para el manejo de tablas se caracterizan por ser operaciones de bajo nivel, pero que
permite a Claire interactuar con las tablas.
Existen tres clases de métodos: aquellos que son utilizados por el reconocedor sintáctico, los que
son usados por el reconocedor lexicográfico y aquellos que utilizan la estructura de las tablas de
Claire para obtener más información.
34
6.3.5.1.
Métodos asociados al reconocimiento sintáctico
Los métodos en esta categoría deben obtener:
Dado un estado y un identificador de símbolo, la acción asociada a ésta.
El símbolo de reducción por defecto asociado a un estado.
El salto (goto) que se debe realizar con un estado sintáctico y un símbolo.
La longitud de una regla dada.
La parte izquierda de una regla dada.
El resultado de ejecución de una acción asociada a una regla, considerando la pila del autómata
LR.
6.3.5.2.
Métodos asociados al reconocimiento lexicográfico
En esta clase, solo hay un método, que computa, dado un estado sintáctico y el lector que
representa la entrada, la próxima unidad lexicográfica correspondiente a estas.
6.3.5.3.
Métodos de interacción especiales de Claire
En esta categoría se definen aquellos métodos especiales de Claire para obtención de información
de las tablas. Estos métodos deben calcular:
El símbolo de reducción dado un estado sintáctico y un estado léxico.
A partir de un estado sintáctico, un estado lexicográfico y el próximo carácter en la entrada,
la transición correspondiente en el autómata LR.
Para poder realizar estas acciones, se deben tener los índices de localización dentro de las tablas
que se mencionan en la sección 6.2.
35
6.4.
6.4.1.
Otras consideraciones
Preámbulo
Puede darse el caso que el lenguaje de destino tenga restricciones en sus definiciones, como por
ejemplo Java y la restricción de que solo puede estar una clase definida por archivo fuente. En este
caso, hay que diseñar plantillas y/o reconocedores que permitan generar reconocedores que cumplan
con las normas del lenguaje.
En estos casos, puede ser considerado un procesamiento del preámbulo para poder extraer información de utilidad al interprete. Un ejemplo de este tipo de procesamiento de preámbulo se
encuentra en la sección 6.5.
6.5.
Implementación de referencia - Lenguaje Java
La distribución estándar de Claire incluye una extensión ya implementada en el lenguaje de programación Java. Solo se va a mencionar el diseño y algunos detalles de implementación dependientes
del lenguaje - los detalles exactos de implementación se encuentran en [5] y la implementación de
referencia se puede conseguir en el paquete ve.usb.Claire.runtime.java de la distribución (que
se puede ubicar en [13]).
6.5.1.
Librería de soporte
En la figura 6.1 se puede ver, de manera gráfica, la composición del paquete que implementa
la librería de soporte en Java. En la distribución actual, existen dos versiones de ciertas clases
(ClaireReader, Algorithm, Language, Scanner y ClaireScanner. Estas segundas versiones tienen
un V2 al final del nombre de la clase). Para efectos de este informe, las clases consideradas van a
ser las segundas versiones (en el caso de existir).
Vale la pena observar la distinción existente entre los reconocedores sintácticos (Parser en el
paquete) y los reconocedores lexicográficos (Scanner y ClaireScanner para los métodos especiales
de Claire). Esta distinción existe principalmente para poder separar los métodos de acuerdo a la
separación especificada en la sección 6.3.5.
36
Figura 6.1: Estructura del paquete ve.usb.Claire.runtime.java.
6.5.1.1.
Índice de paquetes
Algorithm: Define los algoritmos a ser usados por un reconocedor generado en Claire (sección 6.3.1).
Language: Define un lenguaje en Claire (sección 6.3.5). Un lenguaje implementa:
• Parser: Implementa los métodos correspondientes al reconocedor sintáctico (sección 6.3.5).
• Scanner: Implementa los métodos correspondientes al reconocedor lexicográfico (sección 6.3.5).
ClaireScanner: Implementa los métodos especiales de Claire para reconocimiento lexicográfico (sección 6.3.5). Implementa Scanner.
LanguageException: Define una excepción en el lenguaje. Esta excepción puede ser de dos
formas:
• LexerException: Define una excepción a nivel léxico.
• ParserException: Define una excepción a nivel de sintaxis.
37
Pack: Define los métodos de empaquetamiento y desempaquetamiento de datos (sección 6.3.4).
DataPool: Define los métodos de obtención de datos en las tablas (sección 6.3.4).
ClaireReader: Define el lector especificado en sección 6.3.2).
6.5.2.
Generación de reconocedores
Con respecto a la generación de los reconocedores, esta debe adaptarse a las obligaciones del
lenguaje Java, que exige que solo puede haber una clase en el nivel más externo, la herencia es
simple (solo puede heredar de una sola clase) y puede implementar cualquier cantidad de interfaces
(de las cuales éstas no pueden implementar ningún método). Debido a estas limitaciones, se tiene
que:
1. La definición de un lenguaje en la librería (y junto con ésta, la definición de un reconocedor
sintáctico y lexicográfico) debe ser una interfaz. Gracias a esto, se tiene que un reconocedor
puede extender de cualquier clase, pero está obligado a implementar localmente todos los
métodos especificados en la sección 6.3.5.
2. Uno puede definir la clase completamente en el preámbulo. Al final, el generador de reconocedores va a extraer la información necesaria y generará una clase que contenga la información
en el preámbulo mas las definiciones necesarias para poder tener un reconocedor.
3. El resultado de la generación es una clase que define el reconocedor completamente. Esta clase
es un objeto válido Java que puede ser usado en cualquier programa en este lenguaje.
38
Capítulo 7
Diseño e Implementación
En este capítulo, introduciremos los diseños propuestos para las extensiones de Claire para
generación de reconocedores en los dos lenguajes escogidos: Ruby y Python, y la implementación
de éstos.
En términos generales, se intentará implementar en cada lenguaje destino lo realizado en el
lenguaje Java. Pero, al existir diferencias entre Java y los lenguajes elegidos, también existirán
diferencias, por lo que otra cosa que se toma en cuenta es redefinir suficientemente los componentes
para aprovechar las ventajas y respetar las convenciones de estos lenguajes.
Ambos lenguajes elegidos, al ser orientados a objetos, se puede mantener el mismo esquema
utilizado en Java para la estructura de las librerías de soporte, pero con variaciones que utilizan las
capacidades que ofrece el lenguaje. Esto se analizará más a fondo en los siguientes puntos.
Además, se puede considerar que tanto los paquetes de manejo de tablas como el algoritmo
de ejecución son iguales sin importar el lenguaje, por lo que no se va a ahondar en ese punto, y
tampoco se va a tratar el punto de los lectores ya que simplemente deben de ser adaptados a las
especificaciones de entrada y salida en el lenguaje destino.
De esto se puede ver que, para los lenguajes elegidos, solo van a diferir de la implementación de
referencia en cuatro aspectos: la estructura del paquete de ejecución, el manejo de los métodos de
interacción con las tablas, la estructura del archivo de definiciones gramaticales y la estructura y
método de generación de reconocedores.
39
Figura 7.1: Estructura del módulo Claire::Runtime
7.1.
Extensión para el lenguaje Ruby
7.1.1.
Composición de la librería de soporte
La estructura del paquete para la extensión en el lenguaje Ruby se puede observar en la figura 7.1.
El lenguaje de programación Ruby descarta el concepto de interfaz que maneja Java, por el
concepto de módulo. Un módulo en Ruby permite crear un espacio de nombres y además permite lo
que se denomina herencia mezclada que hace una importación textual del contenido del módulo
en el espacio donde se invoca. Por ejemplo, si se importa un módulo en una clase, usando la herencia
mezclada, todas las definiciones dentro del módulo son ahora definiciones de la clase. Utilizando el
sistema de tipos dinámico de Ruby, permite definir métodos usando variables no existentes en un
módulo e importarlas, haciendo que la clase se encargue de definir esas variables.
El detalle importante es la eliminación de la distinción entre métodos de reconocimiento sintáctico y lexicográfico – todos estos métodos están incluidos en el módulo Language. Además de
esto, se implementaron todos los métodos dentro del módulo aprovechando la herencia mezclada
explicada anteriormente, haciendo referencia a variables que contienen tanto los índices definidos
40
en la sección 6.2 y el contenido de las tablas.
7.1.2.
Estructura de la definición gramatical y del reconocedor generado
Un reconocedor generado por Claire en el lenguaje Ruby, al igual que en uno generado por éste
en el lenguaje Java, genera una clase. Ciertas características de Ruby permite tomar una vía distinta
para la generación de reconocedores. Ruby permite:
Definir más de una clase en un archivo fuente.
Aumentar la definición de una clase ya existente.
Aprovechando estas dos características, la estructura de una definición gramatical en Ruby se
consideró de manera distinta a la implementada en la extensión para el lenguaje Java:
El preludio puede definir cualquier cantidad de módulos, clases, métodos, etc. pero debe ser
un programa Ruby válido.
Para poder definir la clase que contiene el reconocedor, ya que puede haber más de una clase,
se creó la directiva class que indica a Claire el nombre que debe llevar esta clase.
En el caso de indicar a la directiva una clase ya existente, Ruby aumentará la clase con los
métodos derivados del reconocedor, de lo contrario la clase será nueva y posee las definiciones
necesarias para implementar el reconocedor. La única limitación consiste en que el usuario no puede
definir ningún método ni inicialización en la clase que va a contener el reconocedor, ya que Ruby
no implementa sobrecarga de métodos. Si se desea inicializar la clase con nuevos elementos, se debe
utilizar un método especial diseñado para la inicialización.
Al generar el reconocedor, esta clase importa el módulo Language existente anteriormente usando
herencia mixta, y se inicializa asignando los valores a las variables que no estaban definidas en este
módulo, completando la definición del lenguaje.
41
Figura 7.2: Estructura del paquete claire.runtime
7.2.
7.2.1.
Extensión para el lenguaje Python
Librería de soporte
La librería de soporte para la extensión al lenguaje Python es muy similar a la estructura
propuesta para la extensión al lenguaje Ruby. La única diferencia existente entre ambas es que, en
vez de utilizar módulos (un concepto inexistente de la misma manera que en Ruby, ya que en Python
un archivo es un módulo), se utiliza una clase que define el lenguaje. Gracias a que Python permite
herencia múltiple, se puede utilizar una clase para definir el lenguaje. Un reconocedor hereda esta
clase, además de cualquier otra clase que requiera el usuario.
Aparte de este detalle, la estructura de la extensión para Python es la misma que la extensión
para Ruby, explicada en la sección 7.1.1. La figura 7.2 muestra la estructura del paquete que contiene
la librería de soporte para la extensión de Python.
42
7.2.2.
Estructura de la definición gramatical y del reconocedor generado
Originalmente se consideró utilizar la misma técnica que la extensión para el lenguaje Ruby, para
la estructura del archivo de definiciones en esta extensión, pero Python, aunque permite definir más
de una clase en un módulo (archivo), éstas no pueden ser redefinidas ni aumentadas.
Por lo tanto, se utiliza la misma técnica que en Java - sólo se puede definir una y solo una clase
en el preludio, y esta será utilizada para incluir el reconocedor entero. Se tomó especial precaución
en la generación de código para Python, ya que éste tiene reglas específicas con la indentación y los
bloques.
Con respecto al reconocedor generado, se tomó una vía casi idéntica a la tomada en la extensión
para Ruby - la clase hereda la clase Language (que contiene los métodos de interacción con las
tablas) en conjunción con cualquier otra clase que el usuario desee y en su inicialización asigna los
valores a los índices para poder utilizar estos métodos.
7.3.
Implementación
La implementación de todas estas extensiones fue exitosa exceptuando el manejador de las
tablas. Un operador utilizado para extraer la información de las tablas (el shift lógico a la derecha,
representado en Java como el operador >>>) no está implementado en los lenguajes elegidos, por
lo que el desarrollo de las extensiones en los interpretes tradicionales se descartó y se procedió a
investigar otras vías de implementación de estas extensiones. De esta investigación, se encontraron
interpretes de estos lenguajes que se ejecutaban en la Máquina Virtual de Java (JVM).
Antes de continuar, se inició con el trabajo de implementar el generador de reconocedores y el
traductor de las acciones. Existieron algunos inconvenientes iniciales con la distribución original ya
que ésta no estaba totalmente diseñada para aceptar otros lenguajes - en el caso de Ruby, los caracteres originales de sustitución en la plantilla y de los valores de las reglas son caracteres utilizados
en el lenguaje, por lo que fue necesario actualizar los métodos de traducción correspondientes para
acomodar esta posibilidad.
43
7.3.1.
Interpretes para la JVM de los lenguajes destinos
Vale la pena destacar que, aunque los lenguajes elegidos tienen interpretadores que se pueden
considerar como los estándares de facto (ambos desarrollados en C), existen intérpretes alternativos
que usan la Máquina Virtual de Java (JVM) para ejecutar los programas de estos lenguajes. Para
Ruby, el intérprete basado en JVM es JRuby [22] mientras que la alternativa para Python es
Jython [23].
La funcionalidad más importante que ofrece la máquina virtual de Java a Ruby y Python vía
los intérpretes anteriormente mencionados es la posibilidad de utilizar clases de Java ya existentes
cualquier programa diseñado para ejecutarse en uno de éstos.
Usando estos intérpretes, la solución fue más directa: utilizar las clases DataPool y Pack directamente en la extensión. El punto negativo es que restringe el uso de un reconocedor de Claire en
esos lenguajes a los interpretes que utilizan la JVM.
7.3.2.
Otras alternativas
Una vía que no fue considerada fue la de implementar el manejo de las tablas en C, que es el
lenguaje base de los interpretes tradicionales. Esto se puede lograr de dos vías distintas:
Implementando las funciones de C que permitan interactuar con las tablas, y crear un envoltorio en Ruby y/o Python que utilice esas funciones.
Utilizar un paquete como rubyinline [33], que permita incrustar código de C en la fuente
del lenguaje.
La única limitación es que, además de los requisitos tradicionales, se necesitaría de un compilador
de C, pero permitiría a un reconocedor generado por Claire en estos lenguajes ejecutar en Ruby o
Python.
7.3.3.
Estado actual de las extensiones
Los reconocedores generado por Claire para JRuby y Jython funcionan correctamente, para
versiones de JRuby hasta la versión 0.9.1 y para Jython para la versión más nueva de este intérprete
44
existente (2.2 al momento de este trabajo). Para versiones superiores a 0.9.1, JRuby posee un
comportamiento distinto del esperado que hacen los reconocedores inutilizables.
Después de implementar los reconocedores para la JVM, se intentó implementar los manejadores directamente en el lenguaje destino (nada más fue intentado para Ruby), pero al finalizar la
implementación se observó un comportamiento irregular. Se puede observar que, por causas desconocidas, el manejador de tablas (sin importar donde está implementado) no se comporta de manera
esperada en el lenguaje Ruby.
45
Capítulo 8
Conclusiones y Recomendaciones
La implementación de las extensiones de Claire para distintos lenguajes ha sido un éxito parcial.
Se puede observar que no todos los lenguajes han tenido éxito en la implementación de los reconocedores (Ruby). Las causas son desconocidas, aunque se estima que puede ser alguna característica
interna de Ruby que causa el comportamiento inesperado.
Una de las razones del desarrollo de este trabajo, además de implementar las extensiones, fue
la de especificar el proceso para implementar una extensión para Claire en el futuro. Se divisaron
dos vías para el desarrollo de extensiones: una que utiliza la base ya existente para implementar el
reconocedor con la limitación de que éste se tiene que ejecutar en un lenguaje que posea un intérprete
o compilador basado en la máquina virtual de Java, o uno en el que se pueda implementar todo de
manera nativa (o usando un lenguaje de mas bajo nivel con el que se pueda entrelazar).
Como fue expuesto en el punto 5.1, se consideraron cuatro lenguajes. El trabajo a realizar en el
futuro, con relación a este proyecto, será implementar las extensiones para los lenguajes Groovy y
JavaFX e implementar los reconocedores para los intérpretes estándares.
Claire es una herramienta poderosa y fácil de extender, pero existen posibilidades para continuar
el trabajo en la herramienta. Unas posibles recomendaciones que se pueden considerar son:
Desarrollar extensiones para otros lenguajes - por ejemplo, Perl o PHP como lenguajes parecidos a los seleccionado, o utilizar otros lenguajes como C/C++.
Utilizar estas extensiones implementadas actualmente para facilitar la enseñanza de la parte
práctica de la teoría de los reconocedores.
46
Expandir el uso de los lenguajes como Ruby o Python en el ámbito de reconocedores ya que
permiten obtener resultados usando poco esfuerzo.
Fuera del ámbito de las extensiones, se puede expandir el potencial de la herramienta para
permitir capacidades más amplias como, por ejemplo, parametrización de los tipos en las
macros o un marco más fuerte para la generación de gramáticas de atributos.
47
Bibliografía
[1] Lesk M., Schmidt E., “Lex - A Lexical Analyzer Generator”. En: http://dinosaur.
compilertools.net/lex/index.html
[2] Johnson S. “Yacc: Yet Another Compiler-Compiler”. En: http://dinosaur.compilertools.
net/yacc/index.html
[3] “Bison - GNU parser generator”. En: http://www.gnu.org/software/bison/
[4] Ahués M., Muñoz B., Santos R., “Yacc4J: Herramienta para la Construcción de Analizadores
Sintácticos en Java.”, Universidad Simón Bolívar, Sartenejas, 1998.
[5] Pacheco P., “Claire: Una Herramienta para Generar Analizadores Sintacticos y Lexicograficos.”,
Universidad Simón Bolívar, Sartenejas, 2000.
[6] Hopcroft J., Motwani, R. y Ullman, J., “Introduction to Automata Theory, Languages and
Computation”, Addison-Wesley, Reading, 2nd Edition, 2000, 28-31, 83-90.
[7] Chomsky N. “Three models for the description of language”, IEEE Transactions on Information
Theory, No. 2, 113-124 (1956).
[8] Chomsky N. “On certain formal properties of grammars”, Information and Control, No. 2,
137-167 (1959).
[9] Backus J. “The syntax and semantics of the proposed international algebraic language of the
Zurich ACM-GAMM Conference” (1959).
[10] Backus J., Naur, P. et al., “Revised Report on the Algorithmic Language Algol 60”, Communications of the ACM, Vol. 3 No. 5, 299-314 (1960).
48
[11] Suárez A., “Notas del Curso - Traductores e Interpretadores” En: http://www.ldc.usb.ve/
~suarez/pdf/ci3725/Traductores.pdf
[12] Aho A., Sethi R. y Ullman J., “Compilers: Principles, Techniques and Tools”, Addison-Wesley,
Reading, 1st Edition, 1986, 1-8.
[13] “ClaireWiki: El Wiki de Claire”. En: http://gacela.labf.usb.ve/ClaireWiki/Wiki.jsp
[14] Ahues M., Muñoz B., Santos R., Pacheco P., Suarez, A. “Claire User’s Manual”. 2003.
[15] “Groovy - An agile dynamic language for the Java Platform” En: http://groovy.codehaus.
org/
[16] “JavaFX Script” En: http://www.sun.com/software/javafx/script/
[17] “Ruby Programming Language” En: http://www.ruby-lang.org/.
[18] Matsumoto Y., “Ruby Language Reference Manual” (1998). En: http://www.math.hokudai.
ac.jp/~gotoken/ruby/man/ o ftp://ftp.ruby-lang.org/pub/ruby/doc/ruby-man-1.4.6.
tar.gz.
[19] Thomas D., Hunt A., “Programming Ruby: The Pragmatic Programmer’s Guide”, AddisonWesley-Longman, Boston, 1st Edition, 2000. En: http://www.rubycentral.com/pickaxe/.
[20] “Python Programming Language – Official Website” En: http://www.python.org/.
[21] van Rossum G., “Python Reference Manual” (2006). En: http://docs.python.org/ref/.
[22] Página oficial del interprete JRuby, en: http://jruby.codehaus.org/
[23] Página oficial del interprete Jython, en: http://www.jython.org/
[24] Java Compiler-Compiler (javacc), en: https://javacc.dev.java.net/
[25] ANother Tool for Language Recognition (ANTLR), en: http://www.antlr.org/
[26] Java(tm) Based Constructor of Useful Parsers (CUP), en: http://www2.cs.tum.edu/
projects/cup/
49
[27] JLex: A Lexical Analyzer Generator for Java(TM), en: http://www.cs.princeton.edu/
~appel/modern/java/JLex/
[28] JFlex - The Fast Scanner Generator for Java, en: http://jflex.de/
[29] Yet Another Python Parser System (YAPPS), en: http://theory.stanford.edu/~amitp/
yapps/.
[30] Scanning, PArsing, and Rewriting Kit, en: http://pages.cpsc.ucalgary.ca/~aycock/
spark/
[31] Earley J., “An efficient context-free parsing algorithm”, Communications of the ACM, Vol. 13,
No. 2, 94-102 (1970).
[32] Ruby yacc (racc), en: http://i.loveruby.net/en/projects/racc/doc/.
[33] RubyInline, en: http://www.zenspider.com/ZSS/Products/RubyInline/
50
Anexo A
Ejemplos de gramáticas de Claire
A.1.
Calculadora
A.1.1.
Con destino en jruby
%lang jruby {
class Calc
end
}
%class Calc
input:
/* empty string */
| input line
line:
"\n"
| exp "\n" { puts "\t" + !1.to_s }
exp:
|
|
|
|
|
|
"([0-9]+\.?[0-9]*)-\."
exp "\+" exp
%left 100
exp "\-" exp
%left 100
exp "\*" exp
%left 80
exp "\/" exp
%left 80
"\-" exp
%left 60
exp "\^" exp
%right 50
{
{
{
{
{
{
{
!1.to_f
!1 + !3
!1 - !3
!1 * !3
!1 / !3
-!2
!1 ** !3
51
}
}
}
}
}
}
}
| "\(" exp "\)"
{ !2
}
white: "."
|
A.1.2.
Con destino en jython
%lang jython {
class Calc
}
input: /* empty string */
| input line
line:
"\n"
| exp "\n"
{ print "\t", str($1) }
<double> exp: "([0-9]+\.?[0-9]*)-\."
| exp "\+" exp
%left 100
| exp "\-" exp
%left 100
| exp "\*" exp
%left 80
| exp "\/" exp
%left 80
| "\-" exp
%left 60
| exp "\^" exp
%right 50
| "\(" exp "\)"
{
{
{
{
{
{
{
{
$$
$$
$$
$$
$$
$$
$$
$$
=
=
=
=
=
=
=
=
white: "."
|
A.2.
Lenguaje funcional
A.2.1.
Con destino en jruby
class F < V
def initialize(&func)
@func = func
end
52
float($1)
$1 + $3
$1 - $3
$1 * $3
$1 / $3
-$2
$1 ** $3
$2
}
}
}
}
}
}
}
}
def fn(arg)
@func.call(arg)
end
def to_s()
return "<fnc>"
end
end
end
module Expressions
INT = 0
FNC = 1
Ops = ["+", "-", "*", "/"]
class Var
attr_reader :name
def initialize(name)
@name = name
end
def to_s()
return @name
end
end
class Int
attr_reader :val
def initialize(val)
@val = val
end
def to_s()
return @val.to_s
end
end
class Op
53
attr_reader :op, :arg
def initialize(op, arg)
@op = op
@arg = arg
end
def to_s()
return "(" + @op.to_s + " " + @arg[0].to_s + ")" if @arg.size == 1
return "(" + @arg[0].to_s + " " + @op.to_s + " " + @arg[1].to_s + ")"
end
end
class Abs
attr_reader :var, :exp
def initialize(var, exp)
@var = var
@exp = exp
end
def to_s()
return "(fun " + @var.to_s + " -> " + @exp.to_s + ")"
end
end
class App
attr_reader :left, :right, :rec
def initialize(left, right, rec = false)
@left = left
@right = right
@rec = rec
end
def to_s()
return "(" + @left.to_s + " " + @right.to_s + ")"
end
end
end
54
end
}
%class FParser
main: E
E:
|
|
|
|
|
|
|
|
|
fun ident ’->’ E
app E E
ident
num
E ’+’ E
E ’-’ E
E ’*’ E
E ’/’ E
’-’ E
’(’ E ’)’
{ puts !1 }
100
%right 100
%left
%left
%left
%left
%left
80
80
70
70
60
{
{
{
{
{
{
{
{
{
{
FPLang::Expressions::Abs.new(!2, !4) }
FPLang::Expressions::App.new(!2, !3) }
FPLang::Expressions::Var.new(!1) }
FPLang::Expressions::Int.new(!1) }
FPLang::Expressions::Op.new(!2, [!1, !3])
FPLang::Expressions::Op.new(!2, [!1, !3])
FPLang::Expressions::Op.new(!2, [!1, !3])
FPLang::Expressions::Op.new(!2, [!1, !3])
FPLang::Expressions::Op.new(!2, [!1]) }
!2 }
// Definicion de las unidades lexicograficas
num = "[0-9]+"
ident = "[a-zA-Z][a-zA-Z0-9]*-fun-app"
fun = "fun"
app = "app"
’->’ = "\-\>"
’+’ = "\+"
’-’ = "\-"
’*’ = "\*"
’/’ = "\/"
’(’ = "\("
’)’ = "\)"
// Definicion del espacio en blanco
white : whiteSpace white
|
[
whiteSpace : "[ \t\n\r]"
]
55
}
}
}
}
A.2.2.
Con destino en jython
%lang jython {
class FPLang
}
main: E
E:
|
|
|
|
|
|
|
|
|
fun ident ’->’ E
app E E
ident
num
E ’+’ E
E ’-’ E
E ’*’ E
E ’/’ E
’-’ E
’(’ E ’)’
{ print $1 }
100
%right 100
%left
%left
%left
%left
%left
80
80
70
70
60
{
{
{
{
{
{
{
{
{
{
$$
$$
$$
$$
$$
$$
$$
$$
$$
$$
// Definicion de las unidades lexicograficas
num = "[0-9]+"
ident = "[a-zA-Z][a-zA-Z0-9]*-fun-app"
fun = "fun"
app = "app"
’->’ = "\-\>"
’+’ = "\+"
’-’ = "\-"
’*’ = "\*"
’/’ = "\/"
’(’ = "\("
’)’ = "\)"
// Definicion del espacio en blanco
white : whiteSpace white
|
[
whiteSpace : "[ \t\n\r]"
]
56
=
=
=
=
=
=
=
=
=
=
"(fun
"(" +
$1 }
$1 }
"(" +
"(" +
"(" +
"(" +
"(" +
$2 }
" + $2 + " -> " + $4 + ")" }
$2 + " " + $3 + ")" }
$1
$1
$1
$1
$1
+
+
+
+
+
"
"
"
"
"
"
"
"
"
"
+
+
+
+
+
$2
$2
$2
$2
$2
+
+
+
+
+
" "
" "
" "
" "
")"
+
+
+
+
}
$3
$3
$3
$3
+
+
+
+
")"
")"
")"
")"
}
}
}
}
A.3.
Subconjunto del lenguaje GaCeLa
A.3.1.
Destino en jruby
%lang jruby {
class MiniGCL
def initialize_parser(*rest)
@vars = {}
end
def add_var(var, val)
if not @vars[var].nil?
puts "Redefinition of variable " + var + " found."
exit
end
@vars[var] = val
end
def obtain_val(var)
if @vars[var].nil?
puts "Undeclared variable " + var + " found."
exit
end
@vars[var]
end
def update_var(var, val)
if @vars[var].nil?
puts "Undeclared variable " + var + " found."
exit
end
@vars[var] = val
end
def execute_assert(bool)
if bool
puts "Failed assertion."
exit
end
end
end
}
57
%class MiniGCL
main: program ident ’|[’ insts ’]|’
insts: inst
| inst ’;’ insts
inst:
|
|
// |
|
// |
{ puts "OK" }
%right 5
ident ’:=’ exp
var ident ’:=’ exp ’:’ int
write ’(’ exp ’)’
if guards fi
’{’ expb ’}’
’{’ bound exp ’}’ do guards od
{
{
{
{
{
{
update_var(!1, !3) }
add_var(!2, !4) }
puts !3 }
puts "If instruction found" }
execute_assert !1 }
puts "Do instruction found" }
guards: expb ’->’ insts
| guards ’|’ expb ’->’ insts
exp:
|
|
|
|
|
|
|
|
num
ident
exp ’+’
exp ’-’
exp ’*’
exp ’/’
’-’ exp
exp ’^’
’(’ exp
expb:
|
|
|
|
|
|
|
|
|
exp
exp
exp
exp
exp
’)’
{
{
%left 100 {
%left 100 {
%left 80 {
%left 80 {
%left 60 {
%right 50 {
{
exp ’=’ exp
%left 30
exp ’<’ exp
%left 30
exp ’>’ exp
%left 30
exp ’<=’ exp
%left 30
exp ’>=’ exp
%left 30
exp ’!=’ exp
%left 30
expb and expb %left 20
expb or expb %left 20
’!’ expb
%left 10
’(’ expb ’)’
{
{
{
{
{
{
{
{
{
{
!1.to_i }
obtain_val(!1) }
!1 + !3 }
!1 - !3 }
!1 * !3 }
!1 / !3 }
-!2
}
!1 ** !3 }
!2
}
!1 == !3 }
!1 < !3 }
!1 > !3 }
!1 <= !3 }
!1 >= !3 }
not (!1 = !3) }
!1 && !3 }
!1 || !3 }
not !3 }
!1 }
// Definicion de unidades lexicograficas
’|[’
’]|’
’:’
’;’
’:=’
’(’
’)’
=
=
=
=
=
=
=
"\|\["
"\]\|"
"\:"
"\;"
"\:\="
"\("
"\)"
58
’{’
’}’
’->’
’|’
’+’
’-’
’*’
’/’
’^’
’=’
’<’
’>’
’<=’
’>=’
’!=’
and
or
’!’
=
=
=
=
=
=
=
=
=
=
=
=
=
=
=
=
=
=
"\{"
"\}"
"\-\>"
"\|"
"\+"
"\-"
"\*"
"\/"
"\^"
"\="
"\<"
"\>"
"\<\="
"\>\="
"\!\="
"\&\&"
"\|\|"
"\!"
program
var
int
if
fi
do
od
bound
write
ident
num
=
=
=
=
=
=
=
=
=
=
=
"program"
"var"
"int"
"if"
"fi"
"do"
"od"
"bound"
"write"
"[a-zA-Z][a-zA-Z0-9]*-program-var-int-if-fi-do-od-bound-write"
"[0-9]+"
// Definicion del espacio en blanco
white : whiteSpace white
|
[
whiteSpace : "[ \t\n\r]"
]
A.3.2.
Destino en jython
%lang jython {
59
import sys
class MiniGCL:
vars = {}
def add_var(self, var, val):
try:
tmp = self.vars[var]
print "Redefinition of variable " + var + " found."
sys.exit()
except KeyError:
self.vars[var] = val
def obtain_val(self, var):
try:
return self.vars[var]
except KeyError:
print "Undeclared variable " + var + "found"
sys.exit()
def update_var(self, var, val):
try:
self.vars[var] = val
except KeyError:
print "Undeclared variable " + var + "found"
sys.exit()
def check_assertion(self, bool):
if bool:
print "Failed assertion found"
sys.exit()
}
main: program ident ’|[’ insts ’]|’
insts: inst
| inst ’;’ insts
inst:
|
|
|
|
|
{ print "OK" }
%right 5
ident ’:=’ exp
var ident ’:=’ exp ’:’ int
write ’(’ exp ’)’
if guards fi
’{’ expb ’}’
’{’ bound exp ’}’ do guards od
{
{
{
{
{
{
self.update_var($1, $3) }
self.add_var($2, $4) }
print $3 }
print "If instruction found" }
self.check_assertion($1) }
print "Do instruction found" }
60
guards: expb ’->’ insts
| guards ’|’ expb ’->’ insts
exp:
|
|
|
|
|
|
|
|
num
ident
exp ’+’
exp ’-’
exp ’*’
exp ’/’
’-’ exp
exp ’^’
’(’ exp
expb:
|
|
|
|
|
|
|
|
|
exp
exp
exp
exp
exp
’)’
{
{
%left 100 {
%left 100 {
%left 80 {
%left 80 {
%left 60 {
%right 50 {
{
exp ’=’ exp
%left 30
exp ’<’ exp
%left 30
exp ’>’ exp
%left 30
exp ’<=’ exp
%left 30
exp ’>=’ exp
%left 30
exp ’!=’ exp
%left 30
expb and expb %left 20
expb or expb %left 20
’!’ expb
%left 10
’(’ expb ’)’
{
{
{
{
{
{
{
{
{
{
$$
$$
$$
$$
$$
$$
$$
$$
$$
=
=
=
=
=
=
=
=
=
int($1) }
self.obtain_val($1) }
$1 + $3 }
$1 - $3 }
$1 * $3 }
$1 / $3 }
-$2
}
$1 ** $3 }
$2
}
$$ = $1 == $3 }
$$ = $1 < $3 }
$$ = $1 > $3 }
$$ = $1 <= $3 }
$$ = $1 >= $3 }
not ($1 == $3) }
$$ = $1 and $3 }
$$ = $1 or $3 }
$$ = not $3 }
$$ = $1 }
// Definicion de unidades lexicograficas
’|[’
’]|’
’:’
’;’
’:=’
’(’
’)’
’{’
’}’
’->’
’|’
’+’
’-’
’*’
’/’
’^’
’=’
’<’
’>’
’<=’
’>=’
=
=
=
=
=
=
=
=
=
=
=
=
=
=
=
=
=
=
=
=
=
"\|\["
"\]\|"
"\:"
"\;"
"\:\="
"\("
"\)"
"\{"
"\}"
"\-\>"
"\|"
"\+"
"\-"
"\*"
"\/"
"\^"
"\="
"\<"
"\>"
"\<\="
"\>\="
61
’!=’
and
or
’!’
=
=
=
=
"\!\="
"\&\&"
"\|\|"
"\!"
program
var
int
if
fi
do
od
bound
write
ident
num
=
=
=
=
=
=
=
=
=
=
=
"program"
"var"
"int"
"if"
"fi"
"do"
"od"
"bound"
"write"
"[a-zA-Z][a-zA-Z0-9]*-program-var-int-if-fi-do-od-bound-write"
"[0-9]+"
// Definicion del espacio en blanco
white : whiteSpace white
|
[
whiteSpace : "[ \t\n\r]"
]
62