Turorial: Parser Descendente Recursivo

Bueno para los que se preguntan como hacer un parser a partir de una gramática que hemos diseñado, aquí le enseñare brevemente como hacer un parser descendente recursivo

Tenemos que tomar en cuenta lo siguiente:

1. Nuestra gramática no debe ser recursiva a la izquierda.Por ejemplo la producción

E::=Er

es recursiva  la izquierda, para este tipo de gramáticas nuestro parser no sería funcional, asi que hay que quitarle la recursividad a la izquierda

2.Debemos construir los conjuntos: First, Follow, para cada producción de nuestra gramatica.

Estructura del parser:

LookAhead: Esta variable(global), inicialmente es el token de mas a la izquierda de la entrada.

Por cada NO TERMINAL de la gramática debe existir un procedimiento del parser.Para hacer mas fácil su programación, el nombre del procedimiento tendrá el nombre del no terminal.

Cada una de las opciones del no terminal formaran el cuerpo del procedimiento.

Procedimiento Match: Con este procedimiento sabremos si es el TERMINAL correcto, lo detallare a continuación

void Match(token simbolo){

if(lookahead==simbolo)

lookahead=siguienteSimbolo;/* para obtener el siguiente simbolo se puede hacer un procedimiento para pedir el siguiente toke que recibimos del analizador lexico*/

else

ERROR
}

Bueno, ahora a programar, escribiré un parser para la siguiente gramática:

terminales: x,y,z;

E:=xP | H     /*  E produce x segido de la producción P ó la producción H       */

P:=Tz

H:=y

T:=yx;

****************************************************************

var token lookahead;//variable del tipo del token que ustedes utilicen

void main {

//Iniciar Scanner si s necesario

lookahead=nexToken() // funcion que devuelve el token siguiente

E();

}

void E(){

if(lookahead==x)

Match(x);

P();

else

H();

}

void P(){

T();

Match(z);

}

void T(){

Match(y);

Match(x);

}

void H(){

Match(z);

}

Y así de sencillo es un parser descendente Recursivo 🙂

Si se dan cuenta el parser recorre el árbol de arriba hacia abajo de allí viene descendente,

Y Recursivo se debe a que el parser puede llamarse a si mismo directa o indirectamente por medio de sus funciones 🙂

Espero que les sirva de algo,

Dudas, comentarios o sugerencias, no duden en escribir

saludos

Anuncio publicitario

Agenda FX, proyecto Estructuras de Datos

AGENDAFX

Muchas veces es difícil al principio de un proyecto implementar o abstraer lo que se nos esta pidiendo, creo que a la mayoría en el curso de Estructuras de Datos al principio andamos un poco perdidos de como empezar.

Los ejemplos visto en clase no son lo suficiente claros o muy sencillos, luego acudimos a la web para ver si podemos darnos una idea de como implementar lo que se nos pide, pero al final solo encontramos ejemplos sencillos o los mismos ejemplos en todas las paginas.

Por eso e decidido subir mis proyectos, al menos los que me queden bien jaja, para poder ayudar  a los que tienen este problema, y empiezo con mi proyecto de Estructuras de Dato.

Se nos pidió desarrollar una agenda web, con las siguientes funciones:

Calendario, cada día del año con una festividad y evento, Una lista de contactos, una libreta de apuntes, y gráficas de reporte.

Ahora vamos con lo emocionante, para implementar la parte de el calendario hice lo siguiente:

Voy a empezar con el nodo mas elemental, que era el nodo de eventos, este esta contenido en una lista doble enlazada ordenada por prioridad de evento. La lista de los eventos esta contenida en el nodo de día, este nodo de día esta contenido en una Matriz Ortogonal(en el proyecto es la clase melOrto.java) o Lista Ortogonal, es decir cada nodo tiene 4 punteros a otros nodos.Cada instancia de la Matriz Ortogonal conforma una lista doble enlazada que es con la que se maneja el año en curso.

Para almacenar los contactos utilice un árbol AVL, el cual tenía que desplegar sus contactos : InOrden, post-Orden, PreOrden.

También se despliegan los contactos en un grafo.

Para los apuntes no es mayor ciencia, una lista doble enlazada circular.

Para ingresar los eventos y contactos se puede hacer de 2 maneras:

Manual o cargando un archivo XML al servidor.

A continuacion les describo que herramientas use para hacer la agenda:

Sistema Operativo: GNU/Linux Debian Lenny 5.0.2
Tecnologia:JSP
Java: Java Enterprise Editition.
IDE: NetBeans 6.7.1
Servidor web: Glassfish v2.1
Parser XML: JDOM.
JAR  para enviar archivos al servidor: commons-fileupload-1.2.1, commons-io-1.4.

El enunciado se encuentra en la carpeta del proyecto, los JAR antes mencionados y el JDOM se encuentran en la carpeta «dist» donde encuentran un archivo con extensión «war» lo descomprimen , en la carpeta resultante pueden encontrar las librerías.

Cualquier duda o comentario de como implementar una estructura, no duden en preguntar en este blog, haré lo posible por contestar 😛

CLICK EN LA IMAGEN PARA DESCAGAR