ELIMINACION DE RECURSIVIDAD IZQUIERDA

Una gramática es recursiva por la izquierda si tiene un no terminal A tal que existe una derivación A           Aα  para alguna cadena  α. Los métodos de análisis sintáctico descendente no pueden manejar gramáticas  recursivas por la izquierda, así que se necesita una transformación que elimine la recursión por la izquierda.

Recursión por la izquierda inmediata simple  (Eliminación de la recursividad izquierda de las producciones)

En este caso la recursión por la izquierda se presenta solo en las reglas gramaticales

A → A α | β

Donde α y β son cadenas de terminales y no terminales y  β no comienza en A. Esta regla genera todas las cadenas de la forma β, β α, β α α…Todas las cadenas comienzan con una β, seguida por     (0 o mas α). Esta regla gramatical es equivalente a la expresión regular β αⁿ

Para eliminar  la recursión por la izquierda  volvemos a escribir estas reglas gramaticales divididas en dos: una para que primero genere β y otra que genere  las repeticiones de α utilizando recursión por la derecha en vez de recursión por la izquierda:

A → β A´

A´→ α A´|є

Ejemplo Considere de nueva cuenta la regla recursiva izquierda de la gramática de expresión simple:

exp → exp opsuma term | term

La forma de esta regla es  A → A α | β, con A= exp,  α=opsuma term y β=term. Al volverla a escribir para eliminar la recursividad por la izquierda obtenemos que

exp → term exp´

exp´→ opsuma term exp´ |є

Recursión por la izquierda inmediata general  (Eliminando la recursión directa por la izquierda de una producción general)

Este es el caso en que tenemos producciones de la forma

A → A α₁| A α₂|……|A α n | β₁ | β ₂|……… | βm

Donde ninguna β₁…… βm comienzan con una A. Después se sustituyen las producciones de A por:

A→ β₁ A´| β ₂ A´|…….| βm  A´

A´→ α₁ A´| α₂ A´|…….| α n A´|є

Ejemplo. Considere la regla gramatical

exp → exp + term | exp -  term | term

Eliminemos la recursión por la izquierda de la manera siguiente

exp → term exp´

exp → + term exp´ | - term exp´ |є

Recursión por la izquierda general (Eliminación de la recursividad izquierda de una gramática completa puede ser mas difícil debido a la recursividad izquierda indirecta).

Es indirectamente recursiva porque elimina por completo la recursividad izquierda

El algoritmo que aquí describimos  eliminara sistemáticamente la recursión por la izquierda general de una gramática. Siempre funciona si la gramática no tiene ciclos (donde un ciclo es una derivación de por lo menos un paso que comienza y finaliza con el mismo no terminal: 

A      A)

O producciones  є (producciones de la forma A → є)

Algoritmo

Entrada La gramática G sin ciclos ni producciones є

Salida Una gramática equivalente sin recursión por la izquierda

1.- Ordénense los no terminales en un orden A₁, A₂,……..,An

2.- PARA i =: 1 hasta n HACER

       COMIENZA {PARA i}

      PARA  j=: 1 hasta i-1 HACER

Reemplace cada producción de la forma  Ai → Ajβ por las producciones:

Ai → α₁β| α₂β|……| αk β

Donde:

Aj→ α₁| α₂|……| αk

Son todas las producciones de Aj actuales

Eliminar  la recursividad inmediata por la izquierda entre las producciones de Ai

Ejemplo: Dada la gramática

S→ Aa | b

A→ Ac|Sd|є

Se ordenan los no terminales S, A. No hay recursión directa por la izquierda entre las producciones de S, de modo que no ocurre  nada durante el paso 2 para el caso i=1. Para i=2, se sustituyen las producciones de S en A→ Sd para obtener las siguientes producciones de A.

A → Ac|Aad | bd  |є

Eliminando la recursión directa por la izquierda entre las producciones de A, se obtiene la siguiente gramática

S → Aa | b

A→bdA´ | A´

A´→c A´|ad A´| є

La eliminación de la recursión por la izquierda no cambia el lenguaje que se esta reconociendo, pero modifica la gramática y, en consecuencia, también los arboles de derivación.

Bibliografia: 

• Compiladores. Principios Técnicas Y Herramientas.- .Aho.Sethi.Ullman
• Construcción de compiladores principios y practica-Kenneth-C-Louden-International-Thomson-Editores  

Integrantes de Exposición:

• Imelda Montiel Santos
• Yuliana Areli Garcia Domingez
• Pedro Eduardo Cortez Mayorga