En términos simples, ¿qué queda de recursión?

Según una página en code.google.com, la "recursión izquierda" se define de la siguiente manera:

La recursividad izquierda solo se refiere a cualquier no terminal recurrente que, cuando produce una forma sentenciosa que se contiene a sí misma, esa nueva copia aparece a la izquierda de la regla de producción.

Wikipedia ofrece dos definiciones diferentes:

1. En términos de gramática libre de contexto, un r no terminal es recursivo a la izquierda si el símbolo más a la izquierda en cualquiera de las producciones de r ('alternativas') ya sea inmediatamente (recursivo directo / inmediato a la izquierda) o mediante algún otro no terminal Las definiciones (recursiva izquierda / indirecta oculta) se reescriben en r nuevamente.

2. "Una gramática es recursiva a la izquierda si podemos encontrar alguna A no terminal que eventualmente derivará una forma de sentencia consigo misma como símbolo de la izquierda".

Apenas estoy comenzando con la creación del lenguaje aquí, y lo estoy haciendo en mi tiempo libre. Sin embargo, cuando se trata de seleccionar un analizador de idioma, si la repetición izquierda es compatible con este analizador o si ese analizador es un problema que aparece inmediatamente al frente y al centro. Buscar términos como "forma sentencial" solo lleva a nuevas listas de jerga, pero la distinción de recursión "izquierda" casi tiene que ser algo muy simple. ¿Traducción por favor?

Una regla Res recursiva a la izquierda si, para averiguar si Rcoincide, primero debe averiguar si Rcoincide. Esto sucede cuando Raparece, directa o indirectamente, como el primer término en alguna producción de sí mismo.

Imagine una versión de juguete de la gramática para expresiones matemáticas, con solo suma y multiplicación para evitar distracciones:

Expression ::= Multiplication '+' Expression
            || Multiplication

Multiplication ::= Term '*' Term
                 || Term

Term ::= Number | Variable

Tal como está escrito, aquí no hay recursividad izquierda: podríamos pasar esta gramática a un analizador de descenso recursivo.

Pero supongamos que intentas escribirlo de esta manera:

Expression ::= Expression '*' Expression
            || Expression '+' Expression
            || Term

Term ::= Number | Variable

Esta es una gramática, y algunos analizadores pueden hacer frente a ella, pero los analizadores de descenso recursivo y los analizadores LL no pueden hacerlo, porque la regla para Expressioncomienza por Expressionsí misma. Debería ser obvio por qué en un analizador de descenso recursivo esto conduce a una recursión ilimitada sin consumir ninguna entrada.

No importa si la regla se refiere a sí misma directa o indirectamente; si Atiene una alternativa que comienza con B, y Btiene una alternativa que comienza con A, entonces Ay Bson indirectamente recursivos a la izquierda, y en un analizador de descenso recursivo, sus funciones de correspondencia conducirían a una recursión mutua interminable.

Intentaré ponerlo en términos simples.

Si piensa en términos del árbol de análisis (no el AST, sino la visita del analizador y la expansión de la entrada), la recursión izquierda da como resultado un árbol que crece hacia la izquierda y hacia abajo. La recursión correcta es exactamente lo contrario.

Como ejemplo, una gramática común en un compilador es una lista de elementos. Tomemos una lista de cadenas ("rojo", "verde", "azul") y analicemosla. Podría escribir la gramática de varias maneras. Los siguientes ejemplos son recursivos directamente hacia la izquierda o hacia la derecha, respectivamente:

arg_list:                           arg_list:
      STRING                              STRING
    | arg_list ',' STRING               | STRING ',' arg_list 

Los árboles para estos analizan:

         (arg_list)                       (arg_list)
          /      \                         /      \
      (arg_list)  BLUE                  RED     (arg_list)
       /       \                                 /      \
   (arg_list) GREEN                          GREEN    (arg_list)
    /                                                  /
 RED                                                BLUE

Tenga en cuenta cómo crece en la dirección de la recursión.

Esto no es realmente un problema, está bien querer escribir una gramática recursiva izquierda ... si su herramienta de análisis puede manejarlo. Los analizadores de abajo hacia arriba lo manejan bien. Así pueden los analizadores LL más modernos. El problema con las gramáticas recursivas no es la recursividad, es la recursividad sin avanzar el analizador, o recurrir sin consumir una ficha. Si siempre consumimos al menos 1 token cuando repetimos, eventualmente llegamos al final del análisis. La recursión izquierda se define como recurrir sin consumir, que es un bucle infinito.

Esta limitación es puramente un detalle de implementación de implementar una gramática con un ingenuo analizador LL de arriba hacia abajo (analizador recursivo de descenso). Si desea seguir con las gramáticas recursivas izquierdas, puede lidiar con eso reescribiendo la producción para consumir al menos 1 token antes de recurrir, por lo que esto asegura que nunca nos atasquemos en un ciclo no productivo. Para cualquier regla gramatical que sea recursiva a la izquierda, podemos reescribirla agregando una regla intermedia que aplana la gramática a un solo nivel de búsqueda anticipada, consumiendo una ficha entre las producciones recursivas. (NOTA: No estoy diciendo que esta sea la única forma o la forma preferida de reescribir la gramática, solo señalando la regla generalizada. En este ejemplo simple, la mejor opción es usar la forma recursiva correcta). Como este enfoque es generalizado, un generador de analizadores puede implementarlo sin involucrar al programador (teóricamente). En la práctica, creo que ANTLR 4 ahora hace exactamente eso.

Para la gramática anterior, la implementación de LL que muestra la recursión izquierda se vería así. El analizador comenzaría con la predicción de una lista ...

bool match_list()
{
    if(lookahead-predicts-something-besides-comma) {
       match_STRING();
    } else if(lookahead-is-comma) {
       match_list();   // left-recursion, infinite loop/stack overflow
       match(',');
       match_STRING();
    } else {
       throw new ParseException();
    }
}

En realidad, lo que realmente estamos tratando es "implementación ingenua", es decir. inicialmente predicamos una oración dada, luego recurrimos recursivamente a la función para esa predicción, y esa función ingenuamente llama a la misma predicción nuevamente.

Los analizadores ascendentes no tienen el problema de las reglas recursivas en ninguna dirección, ya que no vuelven a analizar el comienzo de una oración, funcionan al volver a unir la oración.

La recursividad en una gramática es solo un problema si producimos de arriba hacia abajo, es decir. nuestro analizador funciona al "expandir" nuestras predicciones a medida que consumimos tokens. Si en lugar de expandirnos, colapsamos (las producciones se "reducen"), como en un analizador ascendente LALR (Yacc / Bison), entonces la recurrencia de cualquier lado no es un problema.