Sunday, February 26, 2006

Analizador lexico y sintactico

Aun no me recupero del examen, creo que tuve algunos problemas con el primer ejercicio, pero ni modo hay que seguir adelante aun se puede pasar compiladores, no se desanimen...

La respuesta del ejercicio de puntos extra lo muestro a continuacion:

package wordcount;
%%
%char
%int
%{
public int cuentaPalabras = 0;
public int cuentaCaracteres = 0;
public int cuentaLineas = 0;

%}
Palabras = [^\n\r\f\t ]+
%%
{
[\n\r\f]
{
cuentaLineas++;
cuentaCaracteres++;
}

[\t ] {
cuentaCaracteres++;
}
{Palabras}
{
cuentaPalabras++;
cuentaCaracteres += yytext().length();
}
}


En cuanto a lo que respecta a mi analizador lexico pues ya tengo definidos identificadores, expresiones regulares para reconocer comentarios tradicionales, algunas macros, comentarios simples, numeros enteros, todas las palabras reservadas las tengo divididos en estados por ejemplo:
"break" { }
"char" { }
estas palabras reservadas estan ordenadas en orden alfabetico por sugerencias de jose carlos palma...



Creo que mi analizador lexico ya esta casi terminado aunque se que puedo encontrar algunos bugs en el camino, creo que lo dejare asi por el momento, y continuare con el analizador sintactico, dejare las depuraciones profundas para despues.

El analizador sintactico esta en construccion previsto para esta semana esperos que no tenga mayores problemas.

Sunday, February 12, 2006

Avances al 12 de Febrero

Gracias al laboratorio realizado anteriormente ahora tengo una mejor y más clara idea de como es que funciona el analizador léxico y como este le proporciona los tokens de entrada al parser.

He tomado como modelo la gramática implementada en minimal.cup para poder continuar con mi proyecto, ya que se parece algo.

Además de esto en estos momentos ya tengo integrada la herramiento JCreator LE 2.0 con Jflex, ya que no se como hacerlo con Netbeans o Eclipse y no perder tiempo en mi proyecto.


Creo que si alguien encuentra la forma pues de alguna manera veré la posibilidad de integrar Jflex con otra herramienta pero mientras tanto, asi estoy tranquilo.


Antes de introducir toda la gramática proporcionada, he estado haciendo pruebas (siempre a partir del minimal.cup), es decir simplemente generando sentencias como: if num> 64 then, reconociendo los tokens if, num y then para poder familiarizarme un poco mas con esto de las gramaticas.


Creo que la próxima semana voy a entrarle mas de lleno con lo que va a ser mi proyecto final, introduciendo las gramáticas que finalmente utilizaré para la implementación de la estructura de arreglos.

Sunday, February 05, 2006

Lema del bombeo y forma normal de Greybach

El lema de bombeo se define de la siguiente forma:

Sea L un lenguaje regular infinito. Entonces hay una constante n de forma que, sí w es una cadena de L cuya longitud es ³ n, se tiene que w=uvx, siendo uvixÎ L para todo i ³ 0, con v ³ 1 y uv £ n.

El lema de bombeo facilita una forma de determinar si un lenguaje es regular; de esta forma se podrá decir si es finito y por ello se podrá construir un autómata finito o una expresión regular dada la conexión que existe entre ambos. Recordemos que un lenguaje regular es generado por una expresión regular (para mayor comprensión del tema ver la sección de lenguajes regulares de este capítulo). Para demostrar que un lenguaje no es regular, se mostrará que, cualquier valor n lo bastante grande, se tendrá al menos una cadena de longitud n o mayor que falle al ser "bombeada".

Por ejemplo: Considérese el lenguaje L={a i i ³ 1}
Toda cadena L debe tener una longitud que sea un cuadrado perfecto. Supongamos que L es regular y sea n la constante dada en el lema de bombeo. Obsérvese que an Î L y que, por el lema de bombeo, tenemos an = uvx de forma que 1£ v £ n y uvix Î L para todo i ³ 1. Entonces se obtiene que:


n2 = uvx < uv2x
£ n2 + n < (n+1)2


El lema de bombeo dice básicamente lo siguiente:

Si un lenguaje infinito es regular, este puede ser definido por un autómata finito.
El autómata tiene un numero finito de estados. (digamos, p)
Como el lenguaje es infinito, algunas cadenas en el lenguaje pasarán mas de una vez por algun estado. (estas serán las cadenas que tengan un largo mayor que el número de estados del autómata).
Para que una cadena como la anterior pase mas de una vez por el mismo estado, el autómata debetener un ciclo en alguna parte.
Al repetir el ciclo cuantas veces queramos, el generaremos cademas que tambien estan en el lenguaje


Es decir, la longitud de uv2x se encuentra, estrictamente, entre cuadrados perfectos consecutivos y, por tanto, no es un cuadrado perfecto. Luego uv2x no puede pertenecer a L. Es decir, L no puede ser regular.

Para qué sirve?Lo anterior es sencillo, verdad?... incluso es muy lógico. Entonces, dónde radica la importancia del lema de bombeo?... Si analizamos lo anterior, vemos que:
Si un lenguaje es regular (e infinito), ENTONCES cumple el lema del bombeo
O lo que es lo mismo:
Si un lenguaje no cumple el lema del bombeo, ENTONCES no es infinito y regular.
Como lo anterior es una implicancia, no podemos decir que si un lenguaje cumple el lema del bombeo es regular.
Por lo tanto, la forma de usarlo es siempre para demostrar que un lenguaje NO es regular, NUNCA AL REVES!




Forma Normal de Greibach (1)
Definición:
􀁺 Una GLC se dice que está en Forma Normal de
Greibach (FNG) si todas sus producciones son de la
forma:
A → aα, donde A ∈ N, a ∈ T, α ∈ N*
􀁺 Excepcionalmente se permite la producción S → ε
cuando ε, ∈ L(G).
􀁺 ¿Hasta qué profundidad deberíamos explorar el árbol
de expansión para decidir si una cadena w de longitud n
es generada o no por una gramática en FNC/FNG?



Eliminación de recursividad a izquierdas (1):

􀁺 Dada una GLC G, se dice que una producción es
recursiva a izquierdas si tiene la forma:
A → Aβ, donde A ∈ N, β ∈ (N∪T)*
􀁺 Para pasar una GLC G a FNG necesitaremos que esté
limpia y que no contenga recursividad a izquierdas.



Eliminación de recursividad a izquierdas (2):

􀁺 Algoritmo:
1. Para cada símbolo no terminal A con recursividad a
izquierdas tendremos:
A → Aα1 ... Aαr β1 ... βs
2. Para cada símbolo de este tipo, crear un nuevo no
terminal Bi y sustituir el anterior conjunto de
producciones por el siguiente:
A → β1 ... βs β1Bi ... βsBi
Bi → α1 ... αr α1Bi ... αrBi