En informática , los analizadores sintácticos recursivos de cola son una derivación de los analizadores sintácticos descendentes recursivos más comunes . Los analizadores sintácticos recursivos de cola se utilizan comúnmente para analizar gramáticas recursivas izquierdas. Usan una cantidad menor de espacio de pila que los analizadores sintácticos descendentes recursivos regulares. También son fáciles de escribir. Los analizadores sintácticos descendentes recursivos típicos hacen imposible el análisis sintáctico de las gramáticas recursivas izquierdas (debido a un problema de bucle infinito). Los analizadores recursivos de cola utilizan una técnica de reparación de nodos que lo permite.
Ejemplo
Dada una gramática EBNF como la siguiente:
E : T T : T { '+' F } | F F : F { '*' I } | Yo 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 como esta usando un árbol de sintaxis abstracta es:
- Analizar el siguiente nivel de la gramática y obtener su árbol de salida, designarlo como el primer árbol, F
- Si bien hay un token de terminación, T , que se puede poner como padre de este nodo:
- Asignar un nuevo nodo, N
- Establecer el operador actual de N como el token de entrada actual
- Avanzar la entrada un token
- Establecer el subárbol izquierdo de N como F
- Analice otro nivel hacia abajo nuevamente y almacene esto como el siguiente árbol, X
- Establecer el subárbol derecho de N como X
- Establecer F en N
- Regresar N
Aquí se muestra un ejemplo básico de este tipo de analizador en C. Los detalles de implementación se han omitido por simplicidad.
typedef struct _exptree exptree ; struct _exptree { Char token de ; exptree * left ; exptree * derecho ; };exptree * parse_e ( void ) { return parse_t (); }exptree * parse_t ( void ) { exptree * first_f = parse_f ();while ( cur_token () == '+' ) { exptree * replace_tree = alloc_tree (); reemplazar_árbol -> token = cur_token (); reemplazar_árbol -> izquierda = primer_f ; next_token (); reemplazar_árbol -> derecha = parse_f (); first_f = replace_tree ; }return first_f ; }exptree * parse_f ( void ) { exptree * first_i = parse_i ();while ( cur_token () == '*' ) { exptree * replace_tree = alloc_tree (); reemplazar_árbol -> token = cur_token (); reemplazar_árbol -> izquierda = primer_i ; next_token (); reemplazar_árbol -> derecha = parse_i (); first_i = replace_tree ; }return first_i ; }exptree * parse_i ( void ) { exptree * i = alloc_tree (); i -> izquierda = i -> derecha = NULL ; i -> token = cur_token (); next_token (); volver i ; }