Posts tagged ‘parser’

mayo 25, 2011

Tutorial Jlex y Cup

por Josue Ortega

Finalmente tengo una versión final del tutorial de Jlex y Cup que empece a escribir y un tiempo atrás y no había podido terminarlo por falta de tiempo.

El tutorial se encuentra en la seccion de Jlex y Cup de este blog.

Enlace:

https://openfecks.wordpress.com/jlex-y-cup/

Anuncios
septiembre 28, 2009

Turorial: Parser Descendente Recursivo

por Josue Ortega

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