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

One Comment to “Turorial: Parser Descendente Recursivo”

  1. Muchas Gracias!! Me sirvió mucho.

Responder

Introduce tus datos o haz clic en un icono para iniciar sesión:

Logo de WordPress.com

Estás comentando usando tu cuenta de WordPress.com. Cerrar sesión / Cambiar )

Imagen de Twitter

Estás comentando usando tu cuenta de Twitter. Cerrar sesión / Cambiar )

Foto de Facebook

Estás comentando usando tu cuenta de Facebook. Cerrar sesión / Cambiar )

Google+ photo

Estás comentando usando tu cuenta de Google+. Cerrar sesión / Cambiar )

Conectando a %s

A %d blogueros les gusta esto: