COMO IDENTIFICAR LA RECURSIVIDAD

RECURSIVIDAD

Al analizar la recursividad en gramáticas, y por lo tanto también en el lenguaje generado, podemos hacer una analogía con el concepto de función recursiva en el ámbito de la programación, donde una función es recursiva cuando se llama a sí misma.

PRODUCCIONES RECURSIVAS

Una producción es recursiva cuando el símbolo no terminal del lado izquierdo de la regla de producción, aparece también en el lado izquierdo de la misma.

Las siguientes producciones son recursivas: A := 0A1, B := BA01

COMO IDENTIFICAR LA RECURSIVIDAD

RECURSIVIDAD POR IZQUIERDA

Una producción es recursiva por izquierda cuando el símbolo no terminal del lado izquierdo de la regla de producción, aparece en primer lugar en el lado derecho de la misma.

Ejemplo: A := A1101

RECURSIVIDAD POR DERECHA

Una producción es recursiva por derecha cuando el símbolo no terminal del lado izquierdo de la regla de producción, aparece en el último lugar en el lado derecho de la misma.

Por ejemplo, la siguiente producción es recursiva por derecha: B := 0100B

GRAMÁTICAS RECURSIVAS

Una gramática es recursiva cuando posee al menos una producción recursiva.

RECURSIVIDAD EN UN PASO

Las producciones recursivas antes mencionadas, poseen recursividad en un paso, dado que al efectuar una derivación, aplicando la regla de producción recursiva, obtenemos una forma sentencial que incluye el mismo símbolo no terminal usado al derivar.

RECURSIVIDAD EN MÁS DE UN PASO

Otro caso de recursividad, diferente al caso anterior, al aplicar sucesivas derivaciones, obtenemos una forma sentencial que incluye un símbolo no terminal, que habíamos derivado anteriormente.

El caso más sencillo, puede verse con solamente dos producciones:

A := B0, B := 0A100

ELIMINAR LA RECURSIVIDAD POR LA IZQUIERDA:

Para eliminar la recursividad por la izquierda se utiliza la siguiente fórmula:

Para eliminar la recursividad por la izquierda se utiliza la siguiente fórmula:

Ejemplo:

Gramática Recursiva

...