Quitar izquierda recursividad

Question

La siguiente gramática ha dejado recursividad

E= E+T|T 
T= T*F|F 
F= a|b|c 

cómo eliminarla? ¿Hay algún procedimiento general para ello?

Answer 1

Sí, hay un procedimiento general, consulte p. Ej. wikipedia.

E = TE' 
E'= (e) | +TE' 
T = FT' 
T'= (e) | *FT' 
F = a | b | c 

Cabe mencionar que esto altera la asociatividad de + y * de izquierda a derecha. Es decir, donde antes se analizó a + b + c como (a + b) + c, ahora se analiza como a + (b + c).

Esto no es un problema para la suma y la multiplicación, pero sería un problema para la resta y la división, por ejemplo.

El artículo de Wikipedia tiene más detalles sobre el procedimiento de eliminación de recurrencias a la izquierda y sus complejidades.

Answer 2

Como han señalado otros, hay un procedimiento general para reemplazar la recursividad a la izquierda con recursión a la derecha. Las otras respuestas muestran bien cómo usar ese procedimiento general para eliminar la recursividad izquierda en la gramática dada.

Aquí hay una solución que reestructura la gramática dada de una manera específica para esa gramática.

E= T+E|T 
T= F*T|F 
F= a|b|c 

Answer 3

El procedimiento general se encuentra en Wikipedia, por ejemplo. Lo demostraré para E = E+T|T:

E es el no-recursivo izquierdo-no terminal. +T es la secuencia no nula (alfa). T es la secuencia que no comienza con E (beta).

Creamos un nuevo no terminal para el "resto", es decir. la secuencia no nula. Esto maneja la recursión.

E' = epsilon|+TE'

Y modificamos la regla original para utilizar el nuevo no terminal para manejar la recursividad.

E = TE'

Answer 4

la producción

E = E+T 
    | T 
T = T*F 
    | F 
F = a|b|c 

va a

E= T ('+' T)* 
T= F ('*' F)* 
F= a|b|c 

Para mantener el mismo procesamiento en el que el puño E disjunta se procesa con A(E,T). la nueva versión usa:

ret = T1; 
while(set.more()) ret = A(ret, set.pop_front().T);