¿Por qué es mala la recursividad?

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?

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:$G = (V,\Sigma,R,S)$

$\alpha \rightarrow \alpha \beta$

con un elemento de y un elemento de . (Ver la definición formal completa de la tupla allí ).V β V ∪ Σ ( V , Σ , R , S $\alpha$$V$$\beta$$V \cup \Sigma$$(V,\Sigma,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.α $\beta$$\alpha$$\alpha$

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.

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.

(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().

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