Download generación de reconocedores lalr en diversos lenguajes de
Document related concepts
no text concepts found
Transcript
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