El analizador descendente recursivo es un algoritmo de análisis de arriba hacia abajo implementado por procedimientos de llamada mutua , donde cada procedimiento corresponde a una de las reglas de la gramática libre de contexto o BNF . Las aplicaciones de las reglas consumen secuencialmente, de izquierda a derecha, los tokens recibidos del analizador léxico . Es uno de los algoritmos de análisis sintáctico más simples, adecuado para una implementación completamente manual.
Para analizadores de este tipo, se necesita una gramática COP adecuada , específicamente, una gramática LL (k) que permita seleccionar (predecir) sin ambigüedad una de las opciones alternativas para expandir cada no terminal para el siguiente token o tokens.
Tal analizador se ejecuta en tiempo lineal.
Una variante es el analizador LL , una implementación de un analizador predictivo con construcción automática de una "tabla de predicción" que determina la regla apropiada para expandir el no terminal en función del no terminal dado y el siguiente token.
En lugar de hacer una predicción, el analizador simplemente intenta aplicar todas las opciones de reglas alternativas en orden, hasta que uno de los intentos tiene éxito.
Dicho analizador puede requerir un tiempo de ejecución exponencial y no siempre se garantiza que se complete, según la gramática. Vulnerable a la recursividad izquierda .
| Lenguajes formales y gramáticas formales | |
|---|---|
| Conceptos generales | |
| tipo 0 | |
| Tipo 1 |
|
| Tipo 2 | |
| Tipo 3 |
|
| analizando | |