DIAGRAMAS_DE_SINTAXIS_EXTENDIDOS_-_MEDISE

Vista previa del material en texto

3º Simpósio Internacional de Informática Educativa 255
GENERACIÓN COMPLETA DE COMPILADORES
MEDIANTE DIAGRAMAS DE SINTAXIS EXTENDIDOS
Sergio Gálvez Rojas* **, David Tinaquero Fernández, Antonio Guevara Plaza*, Antonio Luis Carrillo León*
* <galvez, guevara, carrillo>@lcc.uma.es
Dpto. de Lenguajes y Ciencias de la Computación
Universidad de Málaga. España
** sgalvez@malaga.uned.es
Universidad Nacional de Educación a Distancia
Centro Asociado de Málaga. España
Palabras clave: procesadores de lenguajes, metacompilación gráfica, mejora de la comprensión, internet, estudios
superiores.
Resumen:
La construcción de esqueletos básicos de compiladores es una labor que ha sido ampliamente superada tras
los estudios teóricos de Chomsky sobre gramáticas, y el desarrollo posterior de multitud de herramientas,
llamadas metacompiladores (Yacc, Bison, Cup, PRE-CC Xtended, etc.), cuyo objetivo es el de generar
programas que reconozcan si una frase sigue o no determinada gramática.
Todas estas herramientas se basan en elementos puramente textuales, áridos y de difícil asimilación, que no
suelen ser los más acertados a la hora de inculcar los conocimientos básicos en un curso de «Compiladores» o
«Procesadores del lenguaje» propio de la titulación de Informática.
Para solventar esta carencia, hemos desarrollado MEDISE, una herramienta que parte de una gramática
expresada de forma gráfica (mediante diagramas de sintaxis) junto con la especificación de las acciones a
ejecutar, y genera un programa en C cuyo flujo de ejecución será una fiel representación del camino seguido
en tales gráficos para reconocer (o rechazar) una secuencia de palabras dada como entrada. A medida que las
palabras de la entrada van encajando según la gramática propuesta, se van ejecutando las acciones que el
usuario haya dispuesto.
MEDISE está desarrollado en lenguaje Java, lo que la hace multiplataforma, y puede utilizarse a través de
internet o bien en modo local.
1. Introducción
En los actuales estudios conducentes a la titulación técnica o superior de Ingeniero en Informática, y
dependiendo de cada universidad, existe una materia que tiene por objetivo que el alumno adquiera los
conocimientos suficientes como para desarrollar pequeños traductores o intérpretes que le faciliten su posterior
desarrollo profesional: desde un pequeño conversor que traduzca las palabras de un lenguaje de programación en
inglés a uno en español o portugués, hasta calculadoras con funciones preprogramadas, pasando por pequeñas
hojas de cálculo, o conversores de macros en LATEX.
mailto:sgalvez@malaga.uned.es
3º Simpósio Internacional de Informática Educativa 256
Suele utilizarse para estos propósitos el tándem Lex-Yacc [Bennet, 1990] o sus correspondientes PcLex-
PcYacc, JLex-Cup, Flex++-Bison++, o cualquier otro par de herramientas que se encargan de generar
analizadores léxicos y sintácticos en un lenguaje de programación determinado. El punto de partida suele ser la
definición de una gramática que, para nuestros propósitos, podemos ver como un conjunto de reglas que sirven
para validar una frase. El objetivo es crear automáticamente programas que, partiendo de una gramática, sean
capaces de decidir si una frase está correctamente construída o no en base a dicha gramática.
Aunque estas gramáticas pueden expresarse de muy diversas formas ([Documentación oficial de JavaCC,
1998], [Parr y Dietz, 1990]), suele pasarse por alto la enorme utilidad que suponen los diagramas de sintaxis en
el desarrollo de este tipo de analizadores, especialmente en aquellas situaciones en las que el aprendizaje
depende en gran parte de la capacidad de asimilación del alumno, más que de la destreza del profesor por
transmitir los conocimientos, como ocurre en la enseñanza a distancia. Los diagramas de sintaxis constituyen un
mecanismo gráfico de especificación de gramáticas lo que le confiere un poder de comunicación superior al de
los mecanismos textuales.
El presente trabajo supone la continuación de la herramienta MDC presentada en la IE’99, [Gálvez et al.,
1999]. MDC permitía generar automáticamente programas que aceptaban o rechazaban frases en base a
diagramas de sintaxis que el alumno podía dibujar de forma interactiva. Sin embargo, con MDC era imposible
efectuar traducciones; en otras palabras, MDC se limitaba a generar programas que decían «Sí» o «No», lo cual
se corresponde con la fase de análisis sintáctico de cualquier traductor. MEDISE (MEtacompilación con
DIagramas de Sintaxis Extendidos) extiende las posibilidades de MDC y permite incorporar código en lenguaje
C dentro de un diagrama de sintaxis, con lo que es posible crear un traductor completo de cualquier lenguaje de
programación que admita un análisis de gramáticas LL(1).
El presente trabajo se estructura como sigue: en el punto 2 recordamos los conceptos básicos de un
diagrama de sintaxis y cómo se pueden extender para producir compiladores completos; el punto 3 expone el
proceso seguido por el diseñador para generar un compilador completo y las características de éste; el
procesamiento interno referido a las extensiones propuestas a los diagramas de sintaxis convencionales se
explica en el punto 4 mientras que en el punto 5 abordamos las conclusiones y el trabajo futuro.
2. Diagramas de sintaxis
Los diagramas de sintaxis aparecidos inicialmente en [Conway, 1963], constituyen un mecanismo gráfico
mediante el que aproximar, por refinamientos sucesivos, el lenguaje admisible por una gramática.
A grandes rasgos, un diagrama de sintaxis es un grafo dirigido en el que los nodos representan los
símbolos terminales y no terminales de la gramática, y los arcos expresan las secuencias en que pueden
combinarse tales símbolos para formar frases aceptables según la gramática.
Cada diagrama de sintaxis representa un símbolo no terminal (que se puede expandir), de manera que la
gramática completa estará formada por tantos diagramas distintos e interrelacionados como no terminales se
quieran incluir en su descripción. Los símbolos terminales (palabras o tokens) se dibujan como círculos o elipses
etiquetadas con el nombre del token, mientras que los no terminales que aparecen en un grafo se dibujan como
rectángulos etiquetados con su nombre correspondiente. Todo diagrama posee un punto de entrada
3º Simpósio Internacional de Informática Educativa 257
(generalmente situado a la izquierda) y un punto de salida (a la derecha), y que están representados por un arco
sin origen y un arco sin destino respectivamente.
Las figuras 1, 2 y 3 ilustran diversos diagramas de Conway correspondientes al lenguaje de programación
Modula-2 [Wirth, 1988]. La figura 1 Especifica que una secuenciaDeSentencias está formada por una
sentencia, o bien por una sentencia seguida del token ; y otra secuenciaDeSentencias. La figura 2 descompone
todas las posibles sentencias que pueden aparecer en esta gramática, y la figura 3 muestra el diagrama
correspondiente a una de ellas: sentenciaCase.
sen te nc ia
;
Ilustración 1. SecuenciaDeSentencias
asignac ión
lla madaA Procedimiento
sentenc iaIf
sentenc iaCase
sentenc iaWhil e
sentenc iaRepea t
sentenc iaLoop
sentenc iaF or
sentenc iaWi th
expresión
EXIT
RETU RN
Ilustración 2. sentencia
3º Simpósio Internacional de Informática Educativa 258
CA SE expr esión O F
|
caso
ELSE secuenciaD eSe ntencias EN D
Ilustración 3. sentenciaCase
En toda gramática existe un no terminal principal que representa a la gramática en su conjunto, (que en
nuestro ejemplo de Modula-2, representa una unidad de compilación, y cuya figura no se muestra), de manera
que, para reconocer una frase, se parte de su punto de entrada, y siguiendo algún camino en dicho diagrama, se
llega a su punto de salida. Si dicho camino no existe, la frase se rechaza. Cuando en dicho camino nos
encontramos con un no terminal, el «flujo» continúa recursivamente a través del diagrama asociado a ese no
terminal. De esta forma, la aparición de un no terminal en un diagramase expande en otro diagrama que lo
define.
2.1 Diagramas de sintaxis extendidos
Como hemos visto, una secuencia de palabras se reconoce si y sólo si hay un camino en los diversos
diagramas de sintaxis que, partiendo inicio del diagrama inicial llega al final de dicho diagrama, pasando por una
secuencia de tokens idéntica a la secuencia a reconocer.
Por ejemplo, el diagrama de la figura 4, reconoce como válida la secuencia de tokens: «dato , dato , dato
.», ya que en el diagrama hay un camino que, pasando tres veces por dato, es capaz de ir desde el inicio
(triángulo) hasta el final (triángulo invertido). La secuencia «dato , , dato .» no es válida porque en ella hay dos
comas seguidas, y ningún camino del diagrama pasa dos veces consecutivas por una coma.
Ilustración 4. Diagrama de una lista de datos
3º Simpósio Internacional de Informática Educativa 259
Con este esquema es posible decidir si una frase es válida o no, pero ¿cómo podríamos hacer para que el
propio diagrama nos dijese al final (suponiendo la frase válida) cuántas veces ha aparecido la palabra dato? Para
ello, los diagramas se extienden con nodos de código, que no son más que nodos que, cuando se «camina» sobre
ellos, realizan una acción u operación. La figura 5 ilustra cómo es posible colocar nodos intermedios
(representados por hexágonos) que realizan acciones cuando el flujo de reconocimiento pasa por ellos. De esta
forma, tantas veces se pase por dato, tantas veces se incrementará la variable cont, que se visualiza por pantalla
justo antes de llegar al final de la regla.
Ilustración 5. Diagrama con nodos de código C intercalados
3. Descripción de MEDISE
MEDISE es un metacompilador que admite gramáticas LL(1) descritas mediante diagramas de sintaxis
extendidos y genera el correspondiente analizador sintáctico escrito en lenguaje C. MEDISE ha sido desarrollado
íntegramente en lenguaje Java, utilizando la herramienta Visual C@fe 2.0 for Java [Guía del usuario de Visual
C@afé, 1997], que suministra algunos componentes gráficos muy útiles, dando la posibilidad de incorporarlas a
nuestros programas sin costo alguno.
Como hemos adelantado, en MEDISE, se han incorporado dos nodos inexistentes en la definición
original de [Conway, 1963]: uno destinado a la gestión de errores, y otro a la incorporación de acciones en
lenguaje C. El primero es necesario ya que, durante la compilación, el analizador debe indicar los problemas
sintácticos encontrados, sin abortar la compilación tras el primer error. El símbolo gestor de errores (llamado
token de seguridad) permite establecer un control del tipo «ignorar la entrada» (panic mode [Aho et al, 1986]),
de forma que, ante una frase incorrecta, se van ignorando palabras hasta encontrar el token de seguridad,
momento a partir del cual continua el reconocimiento del resto de la frase.
El segundo ha sido introducido en el punto 2.1 y sirven para colocar bloques de código que se ejecutan a
medida que la ejecución fluye por los diagramas.
Además, se han incorporado otros mecanismos que permiten la creación completa de un compilador, así
como la comunicación necesaria entre el analizador sintáctico y el lexicográfico, a través del suministro del
lexema leido.
cont=0; cont++; PRINT cont;
mailto:C@af�
3º Simpósio Internacional de Informática Educativa 260
3.1 Interfaz de MEDISE
MEDISE permite la introducción de diagramas de Conway mediante una ventana dividida en 5 bloques
principales distribuídos verticalmente: barra de menús, barra de botones y propiedades, panel del diagrama,
cuadro informativo y botones de código global.
El panel del diagrama visualiza en todo momento la regla o diagrama en edición. Las características del
panel se controlan mediante la barra de propiedades, pudiéndose ampliar o reducir el panel, modificar el tipo de
letra empleado en cada símbolo independientemente, o mostrar una rejilla que mejora estéticamente la creación
del dibujo.
La barra de botones, facilita la inserción y eliminación de símbolos en el diagrama, así como la creación
de diagramas nuevos (llamados reglas en el contexto de MEDISE). Para permitir la incorporación de nodos de
código, se tiene un botón etiquetado Nodo C. Los dos botones anexos al cuadro informativo, permiten
especificar código global al programa completo y código local a cada regla; en ambos casos, el código se ubicará
al comienzo de su ámbito. En caso de duda, se dispone de una ayuda completa sobre el funcionamiento de
MEDISE (opción Ayuda del menú ?), y de un cuadro informativo textual que nos indica tanto el cometido de
cada botón, como recomendaciones sobre la siguiente acción a realizar.
La barra de menús complementa la herramienta con opciones sobre el tamaño del panel, su orientación, el
color empleado para cada tipo de símbolo, etc. El menú Metacompilación permite obtener el analizador (escrito
en lenguaje C estándar), o bien la notación BNF correspondiente a cada regla. Estas opciones también están
disponibles en la barra de botones.
Ilustración 6. Ventana de la aplicación MEDISE
3.2 Pasos en la generación de un compilador
Los pasos a seguir en la construcción de un compilador resultan muy intuitivos:
3º Simpósio Internacional de Informática Educativa 261
• Construir las reglas que componen la gramática mediante paneles, cada uno de los cuales deberá
estar asociado a un no terminal, y viceversa.
• Incluir las acciones semánticas (nodos C) que ejecuten las sentencias necesarias, así como
incorporar los parámetros que sean necesarios y recuperar los valores devueltos. Asimismo, introducir
los bloques de código globales a todo el programa y a cada regla en particular. Los lexemas devueltos
por el analizador léxico también pueden ser manejados en código asociado a los terminales.
• Seleccionar la opción Código C del menú de Metacompilación. Si los diagramas han sido
correctamente creados, nos aparecerá en pantalla una ventana de texto conteniendo el código C que
implementa el analizador.
• Grabar el texto. Dado que MEDISE se ha construido para ser divulgado entre los estudiantes y
utilizado a través de Internet, está implementado como applet, tipo de programas que posee grandes
restricciones por motivos de seguridad. Este hecho nos ha llevado a recomendar que cada alumno se
descargue el applet en su propia máquina, con lo que podrá disfrutar sin restricciones de las opciones de
archivar y recuperar los diagramas de disco, grabar el código C generado automáticamente, así como
disfrutar de las ventajas de ejecutar MEDISE dentro de un navegador como NetscapeTM o Internet
ExplorerTM.
• Creación mediante cualquier otra herramienta -Lex, Flex, etc.- o ad hoc, de un analizador
lexicográfico que suministre secuencias de tokens a nuestro programa. Tal analizador debe poseer una
función principal llamada yylex() encargada del suministro.
3.3 Fases seguidas en el proceso de generación
El proceso seguido por MDC para la obtención del analizador sigue tres fases bien definidas:
• Obtención de la expresión BNF correspondiente a cada regla.
• Comprobación de que la gramática es LL(1), y no hay ciclos γ.
• Generación de código.
La expresión BNF se obtiene aplicando las reducciones de la figura 7. El objetivo que se persigue es la
obtención de un programa que simule en su flujo de ejecución, el camino que habría que seguir (en los grafos de
Conway) para reconocer o rechazar una sentencia del lenguaje. De esta forma:
• Cada regla da lugar a una función.
• Cada línea de conexión da lugar a un cambio de flujo en el programa.
• Cada terminal da lugar al chequeo y consumo de un token.
• Cada no terminal da lugar a una llamada recursiva a la función que lo representa.
El analizador así obtenido resulta muy fácil de entender para el alumno ya que, a la hora de reconocer una
frase en concreto, el flujo de ejecución que sigue dicho analizador coincide plenamente con el camino que se
sigue manualmente en los diagramas de sintaxis para reconocer la misma frase. Es en estasimilitud en la que se
basa el éxito de la herramienta, que resulta eficaz como introducción a la creación de compiladores, y como
preludio de otro tipo de herramientas basadas en tablas LALR(1) o LL(1).
3º Simpósio Internacional de Informática Educativa 262
∀
∃
(
∗A B
(
∗AB
∀
∃
∀
∃
∀
∃
∀
∃
(
∗ A
Z
Y
X
A B B(X|Y| ...|Z)
A
∀
(
[A]
∀ (
A
B
∀
∃
∀
∃ ∗
( (
∗A[B A]
∀
∃
A
∀
∃
∀
∃ ∗
(
(
∗{ A}
∀
∃
Entrada Reducción resultante
Ilustración 7. Reducciones para obtener la expresión BNF
4. Procesamiento interno de los nodos de código
La incorporación de código a los diagramas de sintaxis puede realizarse de 6 formas bien diferenciadas:
• Introduciendo nodos C en el diagrama. Esta es la forma más directa y visual de todas, y consiste
en especificar nodos que contienen acciones escritas en C que se ejecutarán cuando el reconocimiento
de la frase que se intenta validar obligue a «caminar» sobre dicho nodo. Estos nodos se introdujeron en
la figura 5. De esta manera, los conceptos de camino y recorrido de un camino en un grafo, se asemejan
mucho a los conceptos de flujo de ejecución y ejecución en un programa de ordenador.
• Definiendo código global a todo el compilador.
• Definiendo código local a cada no terminal (según el análisis LL(1), cada no terminal se traduce
en una función de C).
• Mediante la inclusión de parámetros reales en la llamada a función a que se traduce cada no
terminal ubicado en una regla. Esto permite utilizar atributo heredados. Los parámetros formales se
definen en cada regla.
• Mediante la recogida del valor devuelto por la llamada a función a que se traduce cada no
terminal ubicado en una regla. Los atributos sintetizados se obtienen de esta manera. El valor devuelto
se identifica en el símbolo finalizador de la regla del no terminal a que se llama.
• Mediante el lexema proporcionado por el analizador lexicográfico, que puede ser recogido por
cada terminal.
3º Simpósio Internacional de Informática Educativa 263
La figura8 ilustra un par de diagramas de sintaxis extendidos, así como el programa C generado. Las
flechas relacionan los diferentes bloques de código indicados explícitamente por el usuario, así como los
elementos de la interfaz y de los diagramas que los han producido.
Ilustración 8. Bloques de código generados explícitamente por el alumno (usuario)
frase
sumatorio
#include <stdio.h>
// Código global al programa introducido por el usuario.
#include <stdlib.h>
// Fin de codigo de usuario
#define TERM0 43 /* + */
#define NUMERO 257 /* numero */
#define BASE 258 /* base */
// Definición de las funciones
void mi_yylex(void);
void frase(void);
int sumatorio(int base);
int token;
char *lexema;
int error_sintactico=0;
void main(){
mi_yylex();
frase();
}
void frase(void) {
char * baseString;;
int total;
// Código global a la regla introducido por el usuario.
int base = 0;
// Fin de codigo de usuario
if (token==BASE){
mi_yylex();
if (token!=NUMERO){
if (!error_sintactico){
printf("Error: Lexema actual %s y esperaba token
numero.\n",lexema);
error_sintactico = 1;
}
}
else {
baseString;=strdup(lexema);
mi_yylex();
}
// Codigo de usuario
base=atoi(baseString, 10);
// Fin codigo de usuario
}
total = sumatorio(base);
// Cod igo de usuario
printf("El total es %d.\n", total);
// F in codigo de usuario
}
int sumator io( int base) {
char * numeroString;
// Cód igo global a la regla introducido por el usuario.
int toal = 0 ;
// F in de co dig o de usuario
if (tok en !=N UMERO){
if (! err or_sintactico){
printf("Error: Lexema actual %s y esperaba token
numero. \n",lex ema);
error_s intactico = 1;
}
}
else {
numeroStrin g=s trd up(lex ema);
mi_yylex ();
}
// Cod igo de usuario
total += atoi(numeroStrin g, base);
// F in codigo de usuario
w hile ((token==TERM0 )){
mi_yylex ();
if (tok en !=N UMERO){
if (! err or_sintactico){
printf("Error: Lexema actual %s y esperaba token
numero. \n",lex ema);
error_s intactico = 1;
}
}
else {
numeroStrin g=s trd up(lex ema);
mi_yylex ();
}
// Cod igo de usuario
total += atoi(numeroStrin g, base);
// F in codigo de usuario
}
// Cod igo de usuario
return to tal;
// F in codigo de usuario
}
void mi_ yylex(){
error_s intactico = 0;
token = yylex( );
lexema = yytext;
}
3º Simpósio Internacional de Informática Educativa 264
5. Conclusiones
MEDISE culmina el deseo de suministrar a los alumnos de asignaturas de «Procesadores del lenguaje»,
una herramienta fácil de asimilar y que supone grandes beneficios a la hora de comprender el análisis sintáctico
LL(1) y la generación completa de compiladores. Actualmente, el software completo está disponible para quien
lo desee en el fichero comprimido http://www.lcc.uma.es/~galvez/mdc/medise.zip que contiene, a su vez, el
programa y la página web medise.html. Esta página invoca automáticamente a MEDISE en forma de applet
local, permitiendo al usuario almacenar y recuperar los diagramas en su propia máquina.
La posibilidad de especificar atributos y código C en las reglas, eleva a MEDISE a la altura de otras
herramientas de prototipado de compiladores, como Yacc y PCCTS. Sólo la imaginación del alumno y su interés
por adquirir conocimientos serán capaces de sacar provecho a una herramienta eminentemente práctica, gráfica y
con características profesionales.
La próxima versión de MEDISE refinará aspectos gráficos (con objeto de evitar enrarecer excesivamente
el diagrama de sintaxis original con demasiados nodos C), y realizará un mejor control del token de seguridad.
Además, se utilizará la librería gráfica Swing con lo que el manejo de los componentes gráficos será más suave,
y se permitirá la impresión completa de los diferentes diagramas, junto a al contenido textual de cada nodo.
Referencias
Aho, Sethi, Ullman.(1986). Compilers: Principles, Techniques and Tools, Addison-Wesley.
Bennet, J.P. (1990). Introduction to Compiling Techniques: A First Course using ANSI C, LEX and
YACC, McGraw-Hill.
Conway, M.E. (1963). Design of a separable transition diagram compiler, Comm ACM, 6:6 396-408.
Gálvez, S., Tinaquero, D. (1999). Generación de Compiladores mediante Diagramas de Conway,
Congreso Internacional de Informática Educativa. Madrid (España).
Java Compiler Compiler Documentation. 1998.
http://www.webgain.com/products/code_analyzer/documentation.html
Terence Parr, Henry Dietz. (1990). Purdue Compiler-Construction Tools Set. Technical Report TR-EE
90-14, SEE, Purdue Univ. IN.
Symantec Visual C@feTM for JavaTM. User’s Guide, 1997.
Wirth, N. (1988). Programming in Modula-2, Springer-Verlag, 4th edition.