¿Por qué es mala la recursividad?

20

En el diseño del compilador, ¿por qué debería eliminarse la recursividad izquierda en las gramáticas? Estoy leyendo que es porque puede causar una recursión infinita, pero ¿no es cierto también para una gramática recursiva correcta?

Rafael
fuente
2
Por lo general, los compiladores utilizan el análisis de arriba hacia abajo. Si tiene una recursión izquierda, el analizador entra en una recursión infinita. Sin embargo, en la recursión derecha, el analizador puede ver el prefijo de la cadena que tiene hasta ahora. Por lo tanto, puede verificar si la derivación fue "demasiado lejos". Puede, por supuesto, intercambiar los roles e interpretar expresiones desde la derecha, haciendo que la recursión derecha sea mala y la recursividad izquierda correcta.
Shaull
66
La recursividad izquierda es mala porque en los viejos tiempos, cuando las computadoras tenían 16 KB de RAM, el generador de analizador analizador más comúnmente usado no podía soportarlo.
Andrej Bauer

Respuestas:

15

Las gramáticas recursivas izquierdas no son necesariamente algo malo. Estas gramáticas se analizan fácilmente utilizando una pila para realizar un seguimiento de las frases ya analizadas, como es el caso en el analizador LR .

Recuerde que una regla recursiva izquierda de una gramática CF tiene la siguiente forma:sol=(V,Σ,R,S)

ααβ

con un elemento de y un elemento de . (Ver la definición formal completa de la tupla allí ).V β V Σ ( V , Σ , R , S )αVβVΣ(V,Σ,R,S)

Por lo general, es en realidad una secuencia de terminales y no terminales, y hay otra regla para donde no aparece en el lado derecho.α αβαα

Cada vez que el analizador gramatical recibe un nuevo terminal (del lexer), este terminal se coloca sobre la pila: esta operación se llama turno .

Cada vez que el lado derecho de una regla se corresponde con un grupo de elementos consecutivos en la parte superior de la pila, este grupo se reemplaza por un solo elemento que representa la frase recién coincidente. Este reemplazo se llama reducción .

Con las gramáticas recursivas correctas, la pila puede crecer indefinidamente hasta que se produzca una reducción, lo que limita drásticamente las posibilidades de análisis. Sin embargo, los que sean recursivos dejarán que el compilador genere reducciones antes (de hecho, lo antes posible). Vea la entrada de wikipedia para más información.

didierc
fuente
Sería útil si definiera sus variables.
Andrew S
12

Considera esta regla:

example : 'a' | example 'b' ;

Ahora considere un analizador LL tratando de hacer coincidir una cadena no coincidente como 'b'esta regla. Como 'a'no coincide, intentará coincidir example 'b'. Pero para hacerlo, tiene que coincidir example... que es lo que estaba tratando de hacer en primer lugar. Podría atascarse intentando siempre para ver si puede coincidir, porque siempre está tratando de hacer coincidir la misma secuencia de tokens con la misma regla.

Para evitar eso, tendrías que analizar desde la derecha (lo cual es bastante poco común, hasta donde yo he visto, y haría que la recursión correcta sea el problema), limitar artificialmente la cantidad de anidación permitida o hacer coincidir un token antes de que comience la recursión, por lo que siempre hay un caso base (es decir, donde se han consumido todos los tokens y todavía no hay una coincidencia completa). Como una regla recursiva a la derecha ya hace la tercera, no tiene el mismo problema.

cHao
fuente
3
Asume ciegamente que el análisis es necesariamente un análisis ingenuo de arriba hacia abajo.
reinierpost
Estoy destacando una trampa de un método de análisis bastante común, un problema que se puede evitar fácilmente. Ciertamente es posible manejar la recursividad izquierda, pero retenerla crea una limitación casi siempre innecesaria sobre el tipo de analizador que puede usarlo.
cHao
Sí, esa es una forma más constructiva y útil de decirlo.
reinierpost
4

(Sé que esta pregunta ya es bastante antigua, pero en caso de que otras personas tengan la misma pregunta ...)

¿Estás preguntando en el contexto de analizadores de descenso recursivo? Por ejemplo, para la gramática expr:: = expr + term | term, por qué algo así (dejado recursivo):

// expr:: = expr + term
expr() {
   expr();
   if (token == '+') {
      getNextToken();
   }
   term();
}

es problemático, pero no esto (correcto recursivo)?

// expr:: = term + expr
expr() {
   term();
   if (token == '+') {
      getNextToken();
      expr();
   }
}

Parece que ambas versiones de se expr()llaman a sí mismas. Pero la diferencia importante es el contexto, es decir, el token actual cuando se realiza esa llamada recursiva.

En el caso recursivo de la izquierda, expr()se llama continuamente con el mismo token y no se avanza. En el caso recursivo correcto, consume parte de la entrada en la llamada a term()y el token PLUS antes de llegar a la llamada expr(). Entonces, en este punto, la llamada recursiva puede llamar a término y luego finalizar antes de llegar a la prueba if nuevamente.

Por ejemplo, considere analizar 2 + 3 + 4. El analizador recursivo izquierdo llama expr()infinitamente mientras está atascado en el primer token, mientras que el analizador recursivo derecho consume "2 +" antes de expr()volver a llamar . La segunda llamada expr()coincide con "3 +" y expr()solo quedan las 4 restantes. Los 4 coincide con un término y el análisis termina sin más llamadas a expr().

usuario65808
fuente
2

Del manual de Bison:

"Cualquier tipo de secuencia se puede definir usando la recursión izquierda o la recursiva derecha, pero siempre debes usar la recursión izquierda , porque puede analizar una secuencia de cualquier número de elementos con espacio de pila limitado. La recursión derecha usa espacio en la pila de Bison en proporción al número de elementos en la secuencia, porque todos los elementos deben desplazarse a la pila antes de que la regla se pueda aplicar, incluso una vez. Consulte el Algoritmo del analizador de Bison, para obtener una explicación más detallada de esto ".

http://www.gnu.org/software/bison/manual/html_node/Recursion.html

Por lo tanto, depende del algoritmo del analizador, pero como se indica en otras respuestas, algunos analizadores pueden simplemente no funcionar con la recursividad izquierda

Eduardo Wada
fuente