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
Bibliografía :
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.
Bibliografía :
- 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
me ha sido de ayuda, gracias
ResponderEliminar