Trabajando en nuestro Analizador Sintáctico.

Hola que tal mis queridos amigos, gusto de saludarles nuevamente, deseándoles que hayan tenido una linda semana.
Poco a poco se acerca la fecha de entrega del proyecto, y día a día el trabajo se hace más intenso. Como todo buen hondureño! Espero que sepan a que me refiero.

La semana estuvo dedicada al analizador sintáctico CUP, y era de esperarse, que no sería tan fácil. Pero gracias a la ayuda del libro Traductores y Compiladores escrito por Sergio Gálvez Rojas y Miguel Ángel Mora, se nos ha facilitado en buena forma el uso de este poderoso generador de analizadores sintácticos.
Uno de los capítulos que más nos ayudaron fue, el capítulo 4 Gramáticas Atribuidas en donde existe una sección dedicada a CUP muy completa y muy didáctica, de la cual se puede obtener mucho provecho.
El capítulo 6 Tabla de símbolos, nos ha servido muchísimo para tomar una idea en torno a la creación de la tabla de símbolos.

En cuanto al trabajo ya en el archivo .cup, les quiero contar que, ya se ha copiado íntegramente la gramática proporcionada en la descripción del proyecto, así también, como la declaración de los símbolos terminales y los no terminales.
Una vez hecho esto, falta lógicamente programar el código que va a estar por ejemplo dentro de las cláusulas parser code {: :}, init with {: :} y algunas otras mas. En relación al código java que va a ir dentro de esas cláusulas que les dije anteriormente, ya se tiene una idea, por lo que se esta trabajando en eso.

En relación a la tabla de símbolos, ya se ha elegido una estructura para su representación; la cual será un objeto HashTable. Y en donde introduciremos objetos de la clase cToken que la hemos creado específicamente para guardar cada token que reconozca nuestro analizador léxico. Así mismo hemos creado funciones para mostrar mensajes de error personalizados, las cuales darán a conocer al usuario: la línea, columna y el nombre del token que ha sido el culpable de que se generará x ó y error en el código fuente.

Hablando un poco de la gramática del micro-C, hemos detectado algunas inconsistencias a nuestro parecer, como el hecho de en el interior del cuerpo de una función se puedan declarar otras funciones, y según de lo que yo recuerdo de C++ esto no era posible, pero voy a revisar más detenidamente, porque la verdad es que no estoy completamente seguro de lo anterior. Además detectamos que dentro de una función podemos generar código como el siguiente: Identifier == Identifier = Identifier == Identifier el cual no sé, si es un error sintáctico, o un error semántico, ya que no creo que sea correcto.

Bueno y aquí paramos, fue un placer compartirles estos pocos renglones en relación al avance en nuestro proyecto, y espero verlos por acá en los próximos días.

Saludos!

Perfeccionando el analizador léxico.

Muy buenas tardes, estimados amigos, es un placer estar de nuevo por acá, para comentarles algunas de las experiencias vividas esta semana en la realización de nuestro proyecto.

Primero les quiero expresar que, como ésta semana que recién inicio hoy es semana de exámenes y el día de mañana tenemos examen precisamente de Compiladores, sin duda, hemos tenido que estudiar mucho y eso de una u otra forma nos ha restado un poco de tiempo, para dedicárselo a nuestro proyecto.

La parte del analizador léxico ya esta casi finalizada, tuvimos algunos contratiempos con la declaración de las macros, el uso de los estados y otras cosas más, pero poco a poco hemos ido asimilando sus respectivas funciones y solucionando cada uno de los problemas que se nos han presentado para salir avante con la construcción de este analizador.

Sin duda, que el uso de estados en JFlex, es una característica muy útil al momento de escribir nuestro lexer, además es uno de los aspectos que más me ha llamado la atención en JFlex.

En otro par de cosas, todavía no hemos terminado de entender la función que tiene el símbolo “^” dentro de las expresiones regulares, y esto nos ha atrasado un poco en nuestro trabajo.
Hablando un poco acerca de las dudas que se nos han presentado durante la semana, es que en la gramática del micro-C no aparecen los símbolos condicionales “or” y “and”, y me imagino que este lenguaje los ha de tener. Por los momentos no los he incluido como palabras claves, pero tendré que investigar más al respecto.

Como les conté la semana pasada, la integración de JFlex con Netbeans ya esta hecha, y lógicamente ya podemos generar nuestro archivo .java a partir del archivo .lex con la ayuda de JFlex. Aunque el archivo del lexer no lo hemos terminado aún, ya hemos generado el archivo .java a partir de él, a manera de prueba. Pero la verdad no lo hemos podido ejecutar debido a que presenta algunos errores, ya que existen unos tipos de tokens que no reconoce, y no los reconoce me imagino porque aun no hemos terminado de construir el archivo .cup.

Esperamos tener mejores noticias para la próxima semana. Que pasen un buen día.

Y otro pasito más...

Hola a todos, es un placer estar por acá nuevamente, para saludarlos muy afectuosamente y contarles acerca del avance en la realización de nuestro proyecto.
Sin duda este proyecto, ha sido en lo particular, un proyecto un tanto trabajoso ya que se han tenido que aprender muchas conceptos nuevos.
En lo que nos enfocamos estas dos semanas anteriores, fue en conocer a fondo la estructura del archivo .lex y .cup, además de conocer la función que desempeñan los otros archivos .java que vienen en el cd del curso, como por ejemplo los que están ubicados en la carpeta java_cup/runtime/, y otros. Esto lo hicimos porque hemos notado, al analizar los archivos que generamos durante el laboratorio, que la mayoría de éstos hacen uso de la librería runtime de Java_cup.

Además aprendimos la forma en que el parser realiza su trabajo y cómo este trabajo se realiza en conjunto con otras clases.

Después de conocer un poco acerca del analizador léxico, comenzamos a escribir las primeras líneas en nuestro lexer, las cuales son para validar las palabras claves, identificadores, dígitos, espacios en blanco, entre otros.
La que no hemos construido completamente es la expresión regular para reconocer los comentarios, pero esperamos terminarla en los próximos días.
También en cuanto a la interpretación de cómo es la forma de representar las constantes de carácter y las constantes de string, existe algo de confusión, ya que en la definición del proyecto se dice que las dos deben de estar entre comillas dobles (“), lo cual no puede ser, ya que no habría una forma de diferenciarlas; entonces por mientras aclaramos esta duda, hemos decidido utilizar las comillas simples para las constantes de carácter y las comillas dobles para las constantes de string.

En relación a CUP aún no hemos comenzado a escribir la gramática de micro-C, pero lo importante es que ya se tiene una noción más clara sobre las funciones que realiza CUP.
En este apartado, estuvimos analizando algunas archivos .cup de la carpeta JavaGrammar, que nos han dado una idea más clara de como colocar la gramática de micro-C.

También estuvimos conociendo acerca de, cómo hacer que trabajen juntos Netbeans, CUP y JFlex, y aquí hay que agradecerle a nuestro compañero José Palma por las ideas dadas a través de su blog, en relación a este tema.

Y para finalizar les quiero decir que no me siento para nada contento con el rendimiento que estoy teniendo en la construcción de este proyecto, porque la verdad es que no he trabajado como debo trabajar, así que espero traerles mejores noticias para la semana que entra.

En esta semana vamos a conocer un poco sobre el lema de bombeo de Pumping y también sobre la Forma Normal de Greibach.

PUMPING LEMMA O LEMA DE BOMBEO PARA LENGUAJES REGULARES.

Si L es un lenguaje finito, es regular y se podrá construir un autómata finito o una expresión regular para ellos de forma sencilla. También, si L es especificado ya sea por medio de un autómata finito o una expresión regular, la respuesta es obvia. Por desgracia, hay relativamente pocos lenguajes que sean regulares y, en el caso de un lenguaje infinito, la búsqueda exhaustiva de una expresión regular o un autómata finito puede resultar inútil. En este caso, se necesita obtener algunas propiedades que compartan todos los lenguajes regulares infinitos y que no estén presentes en los lenguajes regulares.
Supongamos que un lenguaje es regular y que, por tanto, es aceptado por un DFA M=(Q, S, q0, d, F), donde Q contiene n estados. Si L(M) es infinito, podremos encontrar cadenas cuya longitud sea mayor que n. Supongamos que w= a1, a2, ...,an+1 es una de las cadenas de longitud n+1 que pertenecen a L(M).

Si tuviéramos
q1= d(q0, a1)
q2= d(q1, a2)
y así sucesivamente, obtendríamos los n+1 estados, q1, q2 ,..., qn+1. Puesto que Q contiene sólo n estados , los qi no serán todos distintos. En consecuencia, para algunos índices j y k, con 1£ j £n+1, se obtendrá que qj= qk. Por lo tanto, tendremos un ciclo en el camino que parte de q0 hasta un estado de aceptación según se muestra en la siguiente figura.

Puesto que j< w="uvx," l="{a" an =" uvx" n2 =" uvx">

PUMPING LEMMA PARA LENGUAJES LIBRES DE CONTEXTO.

El planteamiento formal del lema de bombeo (Pumping Lemma en inglés) para CFL’s es el siguiente: Sea L un lenguaje libre de contexto que no contiene e. Entonces existe un entero k para el cual, si z Î L y ½z½>k , entonces z se puede volver a escribir como z = uvwxy con las propiedades siguientes:

1. ½vwx½£ k.
2. Al menos v o x no es e.
3. uvi wxi y Î L para todo i ³ 0.

Al igual que el lema de bombeo para lenguajes regulares, el lema de bombeo para lenguajes libres de contexto nos proporciona la posibilidad de probar si ciertos lenguajes no son libres de contexto, por tanto, utilizaremos el mismo planteamiento que en el caso de los lenguajes regulares.
Supongamos que L ={ai bj j= i2} es libre de contexto, entonces se puede aplicar el lema de bombeo y por tanto habrá un k que satisfaga las condiciones del lema. Consideremos z= ak bk2.
Desde luego, z Î L y ½z½>k. Por tanto, z se puede descomponer en z=uvwxy y se puede asegurar que uvi wxi y Î L para todo i ³ 0, tal que ½vxz½>1 y ½vwx½£ k. Obsérvese que, si v= ar bs para algún r y s, entonces vi= (ar bs) i y, por tanto, uvi wxi y tiene b’s antes de a’s con lo que no puede pertenecer a L. De forma similar, si x= ar bs, tampoco pueden ser bombeados. Por lo que debemos obtener que:
v= ar y x= as o
v= br y x= bs o también
v= ar y x= bs

para algún valor de r y s. En el primer caso se tiene uv2 wx2 y= ak+r+sbk2

En el segundo caso tenemos uv2 wx2 y= akbk2+r+s
En ambos casos, cuando al menos uno de los dos r o s, son ³ 1 (como se requiere en el lema de bombeo), la cadena resultante no puede pertenecer a L. En el tercer caso, se obtendrá uvi wxi y= ak+(i-1)rbk2+(i-1)s el cual no pertenece a L para toda i a excepción de un número finito. Por tanto, L no puede ser libre de contexto puesto que para él no se cumple el lema de bombeo.


Forma Normal de Greibach

Definición: Sea G = (Vn, Vt, S,P) una gramática libre de contexto. Diremos que G respeta la forma normal de Greibach (FN Greibach) si toda regla de P es de la forma:
A→ a Z, donde A∈Vn , a∈Vt , y Z∈Vn*

El siguiente teorema relaciona los Lenguajes LC y las GLC en Forma Normal de Greibach.

Teorema: Cualquier Lenguaje libre de contexto puede ser generado por una gramática que respeta la forma normal de Greibach.

Algoritmo [esquema] para GLC G à FN Greibach
Entrada: G=(Vn,Vt, S ,P),
Salida: G’=(Vn’,Vt, S ,P’) en FN Greibach
Eliminar la recursión a izquierda (ej: A→Aa) sustituyendo cada sublenguaje generado recursivamente por un conjunto de reglas equivalente, pero sin recursión.

Agregar nuevas reglas de reescritura y no terminales para llevar las reglas existentes a la forma de Greibach:
Reemplazar A∈Vn en cada α →β, de a una por vez, para introducir terminales a izquierda.
Reemplazar cada a∈Vt que no está en la parte izquierda de β por nuevos A’ ∈Vn (esto deja solo no terminales a derecha).


Ejemplo: aplicando FNGreibach (1)

G=(Vn,Vt, S ,P), Vn ={S , A,B}, Vt={a,b,c},
P={S → ABB, A→ Aab, B→ Abc}

Reescribamos para simplificar lectura:
P={ S→AB, S→B, A→Aa, A→b, B→Ab, B→c }

Esta gramática tiene la regla con recursión a izq.:
A→ Aa
Esta regla junto con “A→b” genera secuencias de la forma ba*. Puede transformarse en una secuencia equivalente reemplazando las reglas anteriores por:
{ A→b, A→bD, D→aD, D→a}
Se tiene así:


Ejemplo: aplicando FNGreibach (2)
P’={ S→AB, S→B, A→b, A→bD,
D→aD, D→a B→Ab, B→c }
Ahora es necesario realizar reemplazos para dejar los terminales del lado izquierdo en cada parte derecha de una regla.

Podemos comenzar reemplazando el no terminal B en la parte derecha de una regla. Podemos comenzar reemplazando B en la parte derecha de las reglas de P’. En este caso solo es estrictamente necesario en S → B, obteniendo:

P’’={ S →AB, S→Ab, S→c, A→b, A→bD, D→aD, D→a, B→ Ab, B→c }

Ej.: aplicando FNGreibach (3)
P’’={S →AB, S→Ab, S→c, A→b, A→bD, D→aD, D→a, B→ Ab, B→ c}

Análogamente, podemos reemplazar las apariciones del no terminal A. Obtenemos:
P’’’={ S→bB, S→ bDB, S→ bb, S→ bDb, S→ c, D→aD ,D→ a,B→bb, B→ bDb, B→ c}

Ej.: aplicando FNGreibach (4)
P’’’={S→bB, S→ bDB, S→ bb, S→ bDb, S→ c, D→aD , D→ a,B→bb, B→ bDb, B→c }

Pero no toda regla es de la forma A→ a Z, Z∈Vn*. Entonces finalmente introducimos una nueva regla E →b para respetar la FNGreibach:

P’’’’={ S→bB, S→ bDB, S→ bE, S→ bDE, S→ c, D→aD, D→a, B→bE, B→ bDE, B→ c, E→b}
P’’’’={ S→bBbDBbEbDEc, D→aDa, B→bEbDEc, E→b}

Ventaja de FNGreibach: se conoce que cada cadena de longitud n es derivable en n pasos.

Y para finalizar, les dejo una pequeñisima reseña de la mujer creadora de la FNG.

Sheila Greibach
Nacida en New York (1939), obtuvo su doctorado en 1963 en la Univ. de Harvard. Actualmente trabaja en el Dep. de Cs. de la Computación de la UCLA (EEUU). Si usted desea comunicarse con ella puede hacerlo a la siguiente direccion de email: greibach@cs.ucla.edu.

Les ruego disculpas, ya que al parecer las fuentes disponibles al momento de crear las entradas, no reconocen ciertos símbolos que se encuentran en el cuerpo del artículo.
Y también me gustaría decirles, que si alguien conoce cómo hacer para solucionar este problema, que me lo haga saber mediante un mensaje en este blog.
Además me gustaría subir el documento pero creo que esto no es factible. Si alguien lo quisiera solo hagame saberlo enviandome un email a racosta2001@hotmail.com.