analizador recursivo de cola

En informática , los analizadores recursivos de cola son una derivación de los analizadores descendentes recursivos más comunes . Estos analizadores se utilizan habitualmente para analizar gramáticas recursivas izquierdas . Utilizan menos espacio en la pila que los analizadores descendentes recursivos convencionales, siempre que el entorno de ejecución o la herramienta de compilación optimicen las llamadas de cola para convertirlas en saltos. Además, son fáciles de escribir. Los analizadores descendentes recursivos típicos imposibilitan el análisis de gramáticas recursivas izquierdas (debido a un problema de bucle infinito). Los analizadores recursivos de cola emplean una técnica de reasignación de nodos que permite este problema.

Dada una gramática EBNF como la siguiente:

E : T T : T { '+' F } | F F : F { '*' I } | I I : < identificador >

Un analizador sintáctico recursivo de cola simple se puede escribir de forma muy similar a un analizador sintáctico descendente recursivo. El algoritmo típico para analizar una gramática de este tipo utilizando un árbol de sintaxis abstracta es:

1. Analiza el siguiente nivel de la gramática y obtén su árbol de salida, designa este árbol como el primer árbol, F
2. Si bien existe un token de terminación, T , que puede colocarse como padre de este nodo:
   1. Asignar un nuevo nodo, N
   2. Establezca el operador actual de N como el token de entrada actual.
   3. Avanza la entrada un token
   4. Establezca el subárbol izquierdo de N como F.
   5. Analiza otro nivel más abajo y guárdalo como el siguiente árbol, X
   6. Establezca el subárbol derecho de N como X
   7. Establecer F en N
3. Regresar N

Aquí se muestra un ejemplo básico de este tipo de analizador sintáctico en C. Los detalles de implementación se han omitido por simplicidad.

typedef struct _exptree exptree ; struct _exptree { char token ; exptree * left ; exptree * right ; };exptree * parse_e ( void ) { return parse_t (); }exptree * parse_t ( void ) { exptree * first_f = parse_f (); while ( cur_token () == '+' ) { exptree * replace_tree = alloc_tree (); replace_tree -> token = cur_token (); replace_tree -> left = first_f ; next_token (); replace_tree -> right = parse_f (); first_f = replace_tree ; }devolver first_f ; }exptree * parse_f ( void ) { exptree * first_i = parse_i (); while ( cur_token () == '*' ) { exptree * replace_tree = alloc_tree (); replace_tree -> token = cur_token (); replace_tree -> left = first_i ; next_token (); replace_tree -> right = parse_i (); first_i = replace_tree ; } return first_i ; }exptree * parse_i ( void ) { exptree * i = alloc_tree (); i -> left = i -> right = NULL ; i -> token = cur_token (); next_token (); return i ; }

• META II

• Artículo publicado en la edición de enero de 2006 de la revista Dr. Dobbs Journal, titulado "Descenso recursivo, recursión de cola y la temida doble división".