Eliminación de la Recursividad Izquierda

Eliminación de la Recursividad Izquierda

1. Se agrupan todas las producciones de A en la forma: 

A→ A α 1|A α 2| … |A α m| β 1 |β 2| … | β n , donde ninguna βi comienza con una A. 

2. Se sustituyen las producciones de A por: 

 A→ β 1A’| β 2A’|…|β nA’ • A’→ α 1A’|α 2A’|…|α mA’| ε

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.

Ejemplo: Eliminar la recursividad a izquierdas de: E → E+T E → T T → F F → (E) F → id T → T*F

•Se identifica si cada una de las producciones que tienen la forma: 

A→ A α| β 

•La producción E → E+T ,

 tiene recursividad izquierda, por lo que: E → E+T | T A→ A α| β Se igualan los símbolos según la formula:

 A = E 

α = + T

 β = T

 Se utilizan las reglas de remplazo

 A→ β1A’| β2A’|…|βnA’

 A’→ α1A’|α2A’|…|αmA’|

 ε E → TE’

 E’ → +TE’|ε 6 

A las producciónes T → T*F | F, también se le aplica el mismo proceso : 

A = T 

α = *F

 β = F 

• Se utilizan las reglas de remplazo 

A→ β1A’| β2A’|…|βnA’ 

A’→ α1A’|α2A’|…|αmA’| 

ε T→ FT’

 T’→ *FT’ | ε

Se hace necesario eliminar las producciones del tipo A→ λ para dejar una gramática bien formada.

 E → TE’

 E’ → +TE’ 

E→ T

 E’→ +T

T→ FT’ 

T→ F

 T’→ *FT’ 

T’→ *F 

F→ (E) 

F→ id

Se hace necesario también eliminar las reglas de redenominación.

 E → TE’

 E’ → +TE’

 E→ (E)

 E→ id

 E’→ +T

 T→ FT’

 T→ (E) 

T→ id 

T’→ *FT’

 T’→ *F

 F→ (T)

 F→ id

Finalmente la gramática no recursiva por izquierda es:

 E → TE’

 E’ → +TE’

 E→ (E) 

E→ id 

E→ +T 

T→ FT’ 

T→ (E)

 T→ id

 T’→ *FT’ 

T’→ *F 

F→ (T) 

F→ id