Generación de código en C# para un reconocedor sintáctico ascendente (página 2)

Usemos el SP-PS1 para generar el código C#, definiendo las 6 expresiones regulares para los 6 AFD"s que reconocen a los tokens siguientes :

1. AFD para el token delim.- Debemos reconocerlo pero no almacenar la pareja token-lexema.

2. AFD para el token id y palres.- Usaremos un solo AFD para reconocer a los identificadores y a las palabras reservadas. Las palabras reservadas son : inicio, fin, const, entero, real, cadena, var, leer y visua. Agreguemos el metodo EsID() a la clase Lexico que determina si se almacena al token id o a la palabra reservada –su lexema-. Para el caso de que el token sea id, num, o cad, guardaremos al nombre del token, de otra manera almacenamos al lexema en el arreglo _tokens. Para todos los casos, siempre guardamos en el arreglo _lexemas, el lexema encontrado.

3. Dos AFD"s para el token num.- Debemos construir 2 AFD"s para reconocer al token num, uno para reconocer a los reales y otro para reconocer a los enteros.

4. AFD para el token cad.- Aquí especificamos todas las secuencias de caracteres, encerradas entre comillas. La cadena nula también es reconocida por este AFD.

5. AFD para el token otros.- Este autómata sirve para reconocer a todos los demás símbolos terminales : =, ;, ",", +, -, *, /, (, ). La pareja que se almacena es lexema-lexema, es decir, en el arreglo _tokens almacenamos al lexema encontrado.

Agreguemos las 2 clases : Lexico y Automata a la aplicación Windos C#. Debemos rellenar las clases con el código que produce SP-PS1. Ensambla los 6 AFDs en el orden en que los enumeramos.

Recordemos que los tokens id, num, delim, requieren de un Retraer() en su AFD.

El código generado por SP-PS1 para las 2 clases Lexico y Automata, se muestra en la tabla siguiente :

Si aún no lo habias hecho, agrega a las clases Lexico y Automata de tu aplicación C#, el código generado por SP-PS1.

4. Prueba de funcionamiento del análizador léxico o analex

Si ejecutamos la aplicación C# tendremos errores. Además debemos efectuar los cambios :

• Evitar almacenar a los delimitadores, • Reconocer a las palabras reservadas con el mismo AFD que se usa para el token id.

• También debemos guardar el lexema en lugar del token, para cuando reconocemos a los caracteres que agrupamos como otros.

• Otra consideración es juntar el reconocimiento de los token real y entero, y agruparlos en el reconocimiento del token num.

Primero evitemos el error en la compilación, situemos entre comentarios a las llamadas y definiciones sobre el objeto oAnaSinAscSLR. Entremos al código de la forma Form1 t hagamos los cambios mostrados en el listado siguiente :

Ejecutemos la aplicación y debemos de obtener la ventana de la aplicación, fig#4.1.

Fig. No. 4.1 Aplicación C# en ejecución, después de la compilación con comentarios.

Ahora empecemos a programar los cambios antes mencionados. Modifiquemos el método Analiza() de la clase Lexico según se muestra enseguida :

La primera flecha señala que hemos puesto entre comentarios la sentencia que almacena el token delim. La segunda flecha, señala que hemos condicionado el almacenamiento del lexema, sólo para cuando el noAuto que se reconoció es diferente al delim (noAuto!=0). Lo anterior condiciona a que el delimitador sea el token reconocido por el primer autómata, noAuto==0.

Para reconocer a las palabras reservadas usando el AFD para el token id, debemos modificar el método Analiza() de la clase Lexico. También debemos agregar un nuevo método a la clase Lexico, el método EsId(). El método EsId() retorna un true si el lexema encontrado es un identificador, retorna false si el lexema es una palabra reservada registrada en el arreglo local palRes.

La definición del método EsId() la muestro para las palabras reservadas de nuestro lenguaje de ejemplo. Debemos añadirla dentro de la clase Lexico. Házlo.

Ahora insertemos la llamada dentro del método Analiza() :

Otra cuestión es modificar el método Analiza() de la clase Lexico para que almacene una pareja lexema-lexema, cuando el token es cualquier símbolo definido en la expresión regular, otros. La modificación la muestro en el listado siguiente :

La última cuestión por modificar es el agrupar los tokens real y entero, en un solo token llamado num. A continuación tenemos el listado que contiene la modificación.

Finalmente para hacer la prueba sobre el funcionamiento del analizador léxico, agergamos el código en la clase Form1 del archivo Form1.cs.

Este código insertado dentro del evento Click del button1 –ANALISIS SINTACTICO-, lo usamos para visualizar en el dataGridView1 las parejas token-lexema reconocidas durante el análisis léxico hecho por el objeto oAnaLex.

En la figura #4.2 tenemos la visualización de las parejas token-lexema encontrados durante el análisis léxico hecho por el objeto oAnaLex.

Fig. No. 4.2 Prueba del buen funcionamiento del analizador léxico oAnaLex.

5. Clases propuestas

La propuesta de clases que propongo de acuerdo a la teoría presentada por el libro del dragón, son las enumeradas a continuación :

• class SintAscSLR • class Item • class Pila • class SimbGram La clase SintAscSLR es la fundamental. Esta clase hace uso de objetos pertenecientes a las otras clases. La clase Item es usada para representar a los conjuntos de items que forman parte de la colección canónica de items. La colección canónica es un atributo de la clase SintAscSLR, y representa la base para la construcción de la tabla M de reconocimiento.

En el código –clases- que genera el programa RA-SLR, la tabla M no existe. Esta tabla es representada por los atributos _action y _goTo.

Las clase Pila es necesaria, para representar a la pila que encontramos en el modelo conceptual del analizador sintactico ascendente SLR.

Los elementos que contiene la pila son símbolos gramaticales y estados. Tanto los símbolos gramaticales como los estados, son objetos pertenecientes a la clase SimbGram.

En la sección siguiente trataremos acerca de los atributos de las clases SintAscSLR e Item. Respecto a las clases Pila y SimbGram, su explicación es trivial y se deja al lector su análisis.

6. Atributos en las clases

SintAscSLR e Item para reconocedores ascendentes Slr, Propuesta por R.A.F.

Mi propuesta de atributos para la clase SintAscSLR es muy simple. Se basa en la teoría expresada en el libro del dragón, en su capítulo 4 tema análisis sintactico ascendente SLR.

Descripción de atributos de la clase SintAscSLR.

Descripción de atributos de la clase Item.

Continuaremos con los métodos definidos en las clases SintAscSLR e Item. Empezaremos con los constructores.

7. Constructores en las clases

SintAscSLR e Item.

La clase SintAscSLR tiene un solo constructor :

Adiferencia de la clase SintAscSLR, la clase Item tiene 2 constructores :

El primer constructor de la clase Item recibe 2 parámetros : un arreglo bidimensional de enteros que contiene un conjunto de items, y la longitud del arreglo –número de renglones-, que a su vez es el número de items. El arreglo arre es copiado al arreglo _item.

El segundo constructor es el llamado por defecto, no tiene parámetros. Sólo dimensiona al arreglo _item y asigna al atributo _noItems el valor de 0.

8. Métodos de la clase

SintAscSLR.

Esta clase contiene los 11 métodos –además del constructor-, que se listan en la tabla siguiente :

La codificación propuesta es mostrada enseguida :

Observemos que en el código anterior no están definidos el número de producciones NOPROD, ni los atributos :

string[] _vts; string[] _vns; int[,] _prod; int[,] _sig; Estos atributos serán generados por el programa SA-SLR.

9. Métodos de la clase

Item.

Son 4 los métodos definidos en esta clase además de los 2 constructores previamente mencionados en la sección 7. También se ha incluido una propiedad en la clase.

La clase Item con sus atributos, métodos y propiedades es listada a continuación :

10. El programa RA-SLR

RA-SLR es un programa que consiste de un ejecutable, y de 4 archivos tipo texto. Cada archivo texto contiene a una de las clases : SintAscSLR, Item, Pila y SimbGram.

• RA-SLR.exe • molde-clase-sintascslr • clase-item • clase-pila • clase-simbgram Los 5 archivos deben residir en el mismo directorio. Los archivos texto contienen los atributos, métodos y propiedades que han sido descritos en las secciones previas.

Su interfase consiste de 4 carpetas : Generar gramática, Generación de código, Otras clases, Acerca de y Salir, fig#10.1.

Fig. No. 10.1 Interfase del programa RA-SLR.

La tarea fundamental de RA-SLR es la de permitir ingresar una gramática de contexto libre, que contenga las reglas de sintaxis de determinadas sentencias, para luego producir un análisis de esta gramática. El resultado del análisis es la identificación y registro de los componentes de la gramática : símbolos terminales Vts, símbolos no terminalesVns, símbolo de inicio S y el conjunto de producciones sin agrupar. También calcula los conjuntos Primeros y Siguientes para cada símbolo no terminal de la gramática.

Ya que la gramática ha sido ingresada –dentro de la carpeta Generar gramática-, el programa RA-SLR permite generar el código C# que contiene a las 4 clases propuestas por R.A.F. que podrá ser copiado e insertado a una aplicación C# que haga un reconocimiento sintactico ascendente SLR.

Antes de usar el programa debemos haber hecho las siguientes tareas :

• Diseño de la gramática, donde debemos tener a cada producción de la gramática SIN AGRUPAR.

• Conocer el número máximo de Y"s que podrá tener una producción de la gramática. Cada Y representa a un símbolo gramatical, ya sea no terminal, ya sea terminal.

• Debemos identificar cual es el número de Y"s de cada producción, además de su miembro izquierdo que siempre será un no terminal.

Las carpetas Otras clases, Acerca de y Salir no tienen gran dificultad en su comprensión. Otras clases sólo visualiza las clases Item, Pila y SimbGram, las cuales podemos copiar e insertar en la aplicación que estemos construyendo, fig#10.2.

Fig. No. 10.2 Carpeta Otras clases.

La carpeta Acerca de contiene información del autor del programa –R.A.F.-. La carpeta Salir permite abandonar el programa RA-SLR.

En las secciones siguientes veremos el uso de las carpetas Generar gramática y Generación de código. Seguiremos construyendo el ejemplo citado en la sección 2, para el cual ya se ha presentado la gramática y se ha construido el analizador léxico usando el programa SP-PS1.

11. Carpeta generar gramática

Permite ingresar la grámatica dentro de un componente DataGridView. Debemos tener previamente diseñada la gramática. La gramática debe ser de contexto libre, es decir, en el miembro izquierdo de cada producción consiste de sólo un símbolo no terminal –variable sintáctica-.

Existen ciertas reglas que deben seguirse cuando se ingresa la gramática a la rejilla :

• Un renglón representa a una sóla producción. NO debe ingresarse diferentes alternativas – producciones- en un mismo renglón.

• Los símbolos no terminales sólo pueden nombrarse con una sóla letra y debe ser una letra MAYÚSCULA. De aquí que sólo podemos tener en esta versión del RA-SLR hasta 26 símbolos no terminales –variables sintacticas-.

• Los símbolos terminales no deben empezar con letra MAYÚSCULA y pueden contener cualquier caracter menos los espacios blancos y caracteres no visibles.

• El número de Y"s tecleada en la segunda columna de la rejilla no puede ser 0. Por consecuencia, la gramática no puede contener producciones empty –vacias-.

• El número de Y"s tecleado debe coincidir con las Y"s que se han ingresado en la columna correspondiente Y1, Y2, Y3, …,Yn.

Conociendo estas sencillas reglas, iniciemos con el ejemplo de la sección 2. La gramatica citada en esa sección, tiene 40 producciones cuyo máximo número de Y"s es de 6. por omisión el número de Y"s es de 6, asi que en este ejemplo no es necesario cambiar el número de Y"s.

Si se requiriera cambiar el número de Y"s, debemos teclear el nuevo valor en el TextBox etiquetado con la leyenda No de Yes y hacer click en el botón Cambiar No Yes.

Fig. No. 11.1 Cambio del número de Y"s a 4.

Tecleemos las 40 producciones de la gramática en la rejilla con leyenda TECLEA LA GRAMATICA, usando las teclas de flechas para navegar en la rejilla, e ir agregando renglones, fig#11.2 :

Fig. No. 11.2 Gramática ingresada antes de ser analizada.

Una vez que hemos ingresado a la gramática, hacemos click en el botón con leyenda ANALIZAR GRAMATICA. Si la gramática ha sido tecleada sin errores, el programa RA-SLR contesta con una caja de mensajes, fig#11.3.

Fig. No. 11.3 Mensaje de éxito en el análisis.

Luego de que hacemos click en el botón de la caja de mensajes, RA_SLR visualiza las producciones, los Vts, los Vns además de los primeros y los siguientes para cada Vn de la gramática, fig#11.4.

Observemos en la figura#11.4, que el letrero de estado de la gramática se ha actualizado a OK, además que se pueden comprobar los resultados con los nuestros.

Para nuestro ejemplo tenemos 40 producciones, 21Vts y 16 Vns.

Recomiendo al lector que haga pruebas no respetando las reglas citadas anteriormente en esta sección, con el fin de observar los mensajes que produce RA-SLR.

Fig. No. 11.4 Análisis de la gramática con resultado OK.

Ahora seguiremos con la generación del código de la clase SintAscSLR.

12. Carpeta generación de código

La carpeta Generación de código presenta las producciones de la gramática, los símbolos terminales Vts, los símbolos no terminales Vns, los Primeros y los Siguientes de cada Vn de la gramática, además de la clase SintAscSLR sin código incrustado, figura#11.5.

La generación de código sólo podemos efectuarla cuando el estado de la gramática es OK. Cuando el estado de la gramática es DEFICIENTE, el botón con leyenda GENERAR CODIGO es deshabilitado.

Cuando hacemos click en el botón GENERAR CODIGO simplemente insertamos el valor para la constante NOPROD, la definición de los atributos _vts, _vns, _prod y _sig.

La tabla M que contiene las acciones y los gotos, la colección canónica de items, son construidos dentro del método Inicia() de la clase SintAscSLR.

Como hemos visto, la generación de código es muy simple. Lo que realmente vale la pena es explicar lo propuesto por R.A.F. y que ha sido programado en los métodos de la clase SintAscSLR y las otras clases.

Fig. No. 12.1 Código generado por RA-SLR para nuestra gramática de ejemplo.

13. Inscrustación de código en la aplicación C#

Iniciada en la sección 2 Abramos la aplicación Windows C# que hará el análisis sintactico de sentencias que responden a las reglas de sintaxis contenidas en la gramática que ingresamos en la sección anterior.

Lo que sigue es agregar el código generado por RA-SLR al proyecto C# que estamos construyendo. Recordemos que RA-SLR genera el código de 4 clases : SintAscSLR, Item, Pila y SimbGram.

Entonces, agreguemos 4 clases al proyecto usando la trayectoria del menu Project | Add Class, y asignemos el nombre de a cada clase que añadimos :

• SintAscSLR.cs • Item.cs • Pila.cs • SimbGram.cs El cuerpo de estas clases inicialmente está vacio, solamente contiene la inclusión de espacios de nombres y el encabezado con el nombre de la clase, ver figura #13.1.

Todas las clases pertenecen al espacio de nombres de nuestro proyecto –aplicación Windows C#-. En nuestro caso el espacio de nombres es anasinascSLR.

Fig. No. 13.1 Aplicación C# con las 4 clases añadidas.

Procedamos a insertar el código de las clases que genera RA-SLR a nuestro proyecto. La cuestión es muy simple, sólo copia el código de cada clase al portapapeles e insertalo en la clase adecuada. La figura #13.2 muestra el código de la clase SintAscSLR añadido.

Fig. No. 13.2 Código insertado en las 4 clases.

14. Puesta a punto de la aplicación Windows C#

Sólo nos resta quitar los comentarios a los mensajes sobre el objeto oAnaSintAscSLR definido en el archivo Form1.cs de nuestro proyecto.

Fig. No. 14.1 Comentarios que debemos eliminar.

La ejecución de la aplicación C# nos reporta un error. El error consiste en que no hemos definido el método Anade() en la clase Lexico.

El método Anade() es usado dentro del método Analiza() de la clase SintAscSLR. Su propósito es añadir el símbolo $ a los arreglos _tokens y _lexemas, atributos de la clase Lexico. Es necesario este método, debido a que el símbolo $ es usado dentro del modelo conceptual de un reconocedor ascendente expuesto en el libro del dragón. Su uso es un truco para lograr la aceptación de una sentencia bien formada.

Así que debemos agregar este método dentro de la clase Lexico. Su código es mostrado a continuación.

El método Anade() agrega la pareja token-lexema que recibe de parámetros, a los arreglos _tokens y _lexemas.

Las figuras #14.2 y 14.3, muestran el caso de un reconocimiento sintactico exitoso y uno erróneo, respectivamente. El error de sintaxis lo provocamos quitando un ; de la terminación de la instrucción de visualización.

Fig. No. 14.2 Reconocimiento exitoso del texto de entrada.

Fig. No. 14.3 Error de sintaxis, caracter de terminación ; faltante en la sentencia visua "teclea x:".

15. Salvando y cargando una gramática

Podemos salvar las producciones que hemos tecleado para usarlas mas tarde. Lo anterior es hecho por medio del botón con leyenda GUARDAR GRAMATICA.

La gramática es salvada en un archivo binario cuyo nombre es tecleado por el usuario. La extensión no importa, puede añadirse o no.

La figura 15.1 muestra el cuadro de diálogo que presenta la aplicación RA-SLR cuando hacemos click sobre el botón antes mencionado.

Es importante mencionar que el estado de una gramática no es salvado en el archivo.

Fig. No. 15.1 Cuadro de diálogo para salvar una gramática.

Para cargar una gramática que reside en un archivo, sólo debemos hacer click sobre el botón marcado con la leyenda CARGAR GRAMATICA. La figura 15.2 muestra el cuadro de diálogo estandar que se presenta cuando el usuario requiere de cargar una gramática.

Fig. No. 15.2 Cuadro de diálogo que permite cargar una gramática.

16. limpiar la rejilla de ingreso de gramática

Cuando necesitemos limpiar la rejilla de ingreso de la gramática que contiene la sintaxis de las sentencias a reconocer, debemos hacer click sobre el botón con leyenda LIMPIAR, fig#16.1.

La acción del botón es eliminar los renglones de todas las rejillas de visualización y de ingreso de datos, además de las etiquetas.

Fig. No. 16.1 Interfase de RA-SLR después de hacer click sobre el botón LIMPIAR.

17. Visualización de la colección canónica de items

La colección canónica de items C={I0, I1, I2, …, In} es calculada al momento que es analizada una gramática. Si el resultado del análisis es OK, entonces podemos visualizar la colección canónica de items.

Un item es una producción de la gramática con un punto en cualquier parte del miembro derecho de la producción. Por ejemplo, para la producción :

La figura 17.1 muestra la colección canónica de items para la gramática :

Sólo es necesario hacer click en la pestaña de la aplicación con leyenda Colección canónica de items.

Fig. No. 17.1 Colección canónica de items para la gramática con símbolo de inicio A.

El item en forma numérica indica el par {noProd, posPto}, donde noProd es el número de producción y posPto es la posición del punto.

La posición del punto inicia en 0 y su valor máximo es el número de Y"s de la producción. En cuanto al número de la producción debemos conocer lo siguiente :

• El número de la producción que resulta de aumentar la gramática es el -1. Para nuestro caso la producción A"-> A tiene el número -1.

• El criterio para enumerar las producciones de la gramática, es iniciar con 0 la primera, 1 la segunda, hasta llegar a la última. Si tenemos una gramática con n producciones, la última tendrá el número n-1.

El número asignado a cada producción la podemos obtener de la interfase mostrada en la pestaña Generar gramática.

18. Visualización de la tabla de reconocimiento

Otra de las tareas agregadas a RA-SLR es la visualización de la tabla de reconocimiento. La tabla de reconocimiento incluye las acciones y los gotos para cada estado generado por la colección canónica de items.

Recordemos que un estado es un conjunto de items en la colección canónica de items.

Para acceder a la tabla de reconocimiento generada por RA-SLR, es necesario que el estado de la gramática sea igual a OK. Si el estado es DEFICIENTE no será generada la tabla.

La pestaña con leyenda Tabla de reconocimiento permite la visualización de la tabla de reconicimiento, incluyendo a los estados, los vts en las acciones y los vns para los gotos.

La figura #18.1 muestra la tabla de reconocimiento para la gramática :

Fig. No. 18.1 Tabla de reconocimiento para la gramática con símbolo de inicio A.

19. Restricción importante

Quizá el lector ya habrá observado que la gramática que hemos puesto de ejemplo en las 3 secciones anteriores :

A -> B B -> B , id B -> id Puede ser simplificada a 2 producciones :

B -> B , id B -> id Y es correcto, el lenguaje generado por la gramática es el mismo. En esta primera versión de RA-SLR tenemos que observar esta restricción.

Podemos generalizar que cuando el símbolo de inicio de la gramática también sea encontrado en el miembro derecho de la producción, debemos agregar una producción que retrase la sustitución de este símbolo de inicio. Lo anterior lo hicimos cuando agregamos la producción :

A -> B A la gramática :

B -> B , id B -> id Veamos otro ejemplo :

K -> K [ L ] K -> [ L ] L -> id L -> num La gramática anterior genera el lenguaje de las dimensiones de un arreglo en C. Cuando efectuamos la simulación en RA-SLR tendremos siempre un error, fig#19.1 :

Fig. No. 19.1 "Error que no es un error", recordando a Mario Moreno.

En la figura #19.1 vemos que la derivación a la derecha producida por el simulador integrado en RA- SLR muestra que el resultado de la simulación "ES UN ERROR QUE NO ES UN ERROR".

Para corregir esta deficiencia debemos agregar la producción J -> K a la gramática original. Ahora el símbolo de inicio es J.

J -> K K -> K [ L ] K -> [ L ] L -> id L -> num Si ingresamos esta nueva gramática con la restricción observada, dentro de la pestaña de simulación tenemos la respuesta correcta deseada, fig#19.2.

Fig. No. 19.2 Evitamos el "error que no es un error".

20. Simulando el reconocimiento de una sentencia

Una vez que hemos ingresado la gramática, podemos simular el reconocimiento usando la pestaña con leyenda Simulación.

Esta interfase permite ingresar una sentencia compuesta de tokens. Los tokens deberán ser conocidos por el usuario del RA-SLR.

Veamos el ejemplo de la sección anterior. la gramática usada sirve para reconocer las repeticiones de dimensión en una declaración de un arreglo.

J -> K K -> K [ L ] K -> [ L ] L -> id L -> num Es fácil ver que la sentencia mínima es :

[id] Las siguientes 2 serían :

[id][id] y [id][id][id] Ingresemos a la pestaña Simulación e ingresemos la 3 sentencia :

[id][id][id] Notemos que necesitamos 9 celdas que acepten cada una de ellas a los tokens en la sentencia. Las celdas por omisión son 8. Lo primero que debemos hacer es asignar el valor de 9 a las celdas en la rejilla, usando el botón con leyenda Cambiar No de columnas. la figura #20.1 muestra la acción del botón cuando es leído un 9 en la ventana de lectura de No. de columnas.

Fig. No. 20.1 Cambio del # de columnas a 9.

Ahora ingresemos la sentencia [id][id][id] en la rejilla con leyenda TECLEA EL CONTENIDO DE W$.

Luego hacemos click en el botón con leyenda ANALISIS SINTACTICO y obtenemos el resultado del análisis. El análisis puede ser exitoso o erróneo.

La derivación a la derecha que produce el reconocedor ascendente es mostrada en la rejilla con leyenda DERIVACION A LA DERECHA.

Las figuras #20.2 y #20.3 muestran un reconocimiento exitoso y uno erróneo.

Fig. No. 20.2 Éxito en el reconocimiento de la sentencia [id][id][id].

Fig. No. 20.3 Error de sintaxis en el reconocimiento de la sentencia [id][id[id], falta del corchete que cierra al segundo id.

Instituto Tecnológico de la Laguna Torreón,Coah; a 17 de diciembre del 2007.

Autor:

Ing. Francisco Ríos Acosta.