LENGUAJE RECURSIVOS

Ejemplo de intérprete de lenguaje recursivo 

En este apartado se describe la implementación de un intérprete de un sencillo lenguajerecursivo. Se describen tres posibles diseños indicando las ventajas e inconvenientes de cada uno.

•   Definición del lenguaje

Un lenguaje recursivo en matemáticas, lógica e informática, es un tipo de lenguaje formal que también es llamado recursivo, decidible o Turing-decidible. Se caracterizan porque para cada uno de ellos existe una máquina de Turing que aceptará cualquier palabra del lenguaje y parará siempre.

El lenguaje consta de dos categorías sintácticas fundamentales: expresiones y órdenes, quetienen la siguiente estructura:

<comm> : : = while <expr> do <comm>

                | if <expr> then <comm> else <comm>

                | <var> : = <expr>

                | <comm> ; <comm> 

<expr> : : = <expr> <binOp> <expr> 

                                                                          |  <var>

                                                                          | <integer> 

<binOp> : : = + | - | * | / | = | <

•       Diseño imperativo simple

La implementación imperativa simple consistiría en utilizar una instrucción de selección que,dependiendo del tipo de instrucción, ejecute una porción de código determinada. El código tendría lasiguiente apariencia:

void exec(Context &c) { 

switch (c.code) { 

case WHILE : . . .

 case IF: . . . 

. . . 

}

}

Como en el lenguaje intermedio, la representación interna de las instrucciones se puederealizar mediante una unión.El diseño imperativo tiene como principal ventaja la eficiencia y sencillez de aplicación.Sin embargo, su utilización puede perjudicar la eficiencia de la representación interna de lasinstrucciones, desperdiciando memoria para instrucciones pequeñas. Otras desventajas son ladificultad para añadir instrucciones sin modificar el código anterior y la falta de seguridad (esposible acceder a campos de la unión equivocados sin que el compilador lo detecte.

• Diseño Orientado a Objetos simple

La representación de las instrucciones puede realizarse mediante una clase abstracta

Comm

quecontiene un método

exec

que indica cómo ejecutar dicha instrucción en un contexto determinado.

abstract class Comm {void exec(Context ctx);}

Cada una de las instrucciones será una subclase de la clase abstracta que definirá el método

exec

e incluirá los elementos necesarios de dicha instrucción.

class While extends Comm { 

Expr e; 

Comm c;

void exec(Context ctx) { 

for (;;) {Bvalue v = (Bvalue) e.eval(ctx); 

if (!v.b) break;

c.exec(ctx); 

}

}

}

class If extends Comm { 

Expr e;Comm c1, c2; 

void exec(Context ctx) { 

Bvalue v = (Bvalue) e.eval (ctx) ;

- Bibliografia 

http://es.wikipedia.org/wiki/Lenguaje_recursivo

http://es.scribd.com/doc/50382478/9/Ejemplo-de-interprete-de-lenguaje-recursivo