Recursividad a Izquierda
Se dice que una regla es recursiva cuando el antecedente aparece en el consecuente de la regla.
a ⟶ ... a ...
Se dice que una regla es recursiva a izquierda (RI) cuando el antecedente aparece como primer símbolo del consecuente.
a ⟶ a ...
De la misma manera, se dice que una regla es recursiva a derecha (RD) cuando el antecedente aparece como último símbolo del consecuente.
a ⟶ ... a
Problema de la Recursividad a Izquierda
La recursividad a izquierda (no la derecha), presenta un problem para los parsers LL(k). Para verlo, basta intentar implementar una regla que tenga esta característica.
a ⟶ a ...
void a() {
a();
...
}
Como puede observarse, entraría en un bucle infinito.
Esto no deja de ser un caso especial del problema anterior, es decir, el problema sigue siendo que habrá reglas con símbolos directores comunes.
a ⟶ a ...
| b
En el caso anterior, tanto la primera regla como la segunda tendrán como símbolos directores aquellos que tenga el símbolo b (ya que a puede ser sustituida por b). Y, por muchos tokens que se mire hacia adelante, no podrá distinguirse entre ambas reglas, ya que siempre coincidirán.
Por tanto, el ver recursividad a izquierda es una forma rápida de descartar una gramática que pretenda ser implementada con un parser LL(k).
Nota
📌 Ojo, que una gramática tenga recursividad a izquierda implica que no puede ser implementada de manera descendente. Pero el que no la tenga, no implica que pueda serlo. Habrá que validar la gramática para averiguar si es LL(1).
Situación
Por lo que se acaba de ver, una gramática que tenga recursividad a izquierda no puede implementarse con un parser descendente predictivo, es decir, un parser LL(k) (da igual cuantos tokens mire hacia adelante).
Por tanto, la gramática no puede ser LL(k) y en el mapa de gramáticas no podría estar en la zona señalada en rojo.
Posibles Soluciones
A diferencia del capítulo anterior, aquí no es solución mirar más tokens hacia adelante. Las alternativas que sí permanecen son las otras dos:
- Cambiar de dirección de reconocimiento del parser.
- Buscar una gramática equivalente sin RI.
Cambiar la Dirección
La primera opción es cambiar de dirección de reconocimiento del parser y pasar a uno ascendente (yacc). La técnica predictiva ascendente no tiene ningún problema con la recursividad a izquierda. De hecho, es más eficiente con ella que con la recursividad a derecha (que también admite).
Gramática Equivalente
Al igual que ocurría en la situación del capítulo anterior, se puede buscar una gramática equivalente que no tenga recursividad a izquierda y sí sea LL(1).
Sea la siguiente gramática con recursividad a izquierda.
expr ⟶ expr '+' NUM
| NUM
Para eliminar la recursividad a izquierda de esta regla, puede probarse con la siguiente técnica.
Qué hace ANTLR
ANTLR es un parser recursivo descendente. Por tanto, no puede implementar una gramática con recursividad a izquierda. Pero lo que sí hace, de manera automática, es transformar la gramática tal y como se acaba de ver en el apartado anterior. Y es esta otra nueva gramática (que no tiene RI) la que realmente implementa.
Pero ANTLR no puede tratar todo tipo de recursividad a izquierda. Sólo puede tratar la recursividad a izquierda directa, es decir, cuando la recursividad se halla en la propia regla (que son los ejemplos vistos anteriormente). Sin embargo, si la gramática tiene recursividad a izquierda indirecta, no puede transformarla y la gramática es rechazada.
Un ejemplo de recursividad a izquierda indirecta seria el siguiente, en el cual ANTLR produciría un error.
a ⟶ b ...
b ⟶ a ...