Analizador sintáctico descendente
| ||||
Analizador sintáctico descendente. (Top-Down-Parser): un analizador puede empezar con el símbolo inicial e intentar transformarlo en la entrada, intuitivamente esto sería ir dividiendo la entrada progresivamente en partes cada vez más pequeñas.
Sumario
Características
El análisis sintáctico descendente (ASD) intenta encontrar entre las producciones de la gramática la derivación por la izquierda del símbolo inicial para una cadena de entrada.
Parte del axioma de la gramática
- Procesa la entrada de izquierda a derecha.
- Escoge reglas gramaticales.
Para trabajar el análisis sintáctico descendente se debe realizar primeramente algunas operaciones para que la gramática sea LL1 las cuales son:
- ELIMINAR AMBIGUEDAD: Para eliminar la ambigüedad se debe reescribir la gramática.
- ELIMINAR RECURSIVIDAD POR LA IZQUIERDA: Una gramática es recursiva por la izquierda si tiene un nodo Terminal a tal que existe una derivación A->Aα para alguna cadena . Es decir por simple observación podemos identificar.
Para eliminar la recursividad por la izquierda se utiliza la siguiente formula.
Factorizar: Se trata de rescribir las producciones de la gramática con igual comienzo para retrasar la decisión hasta haber visto lo suficiente de la entrada como para elegir la opción correcta.
Ejemplo:
Funcionamiento
La forma en que funciona un analizador sintáctico descendente es:
- Los terminales se examinan en el orden en que aparecen en la cadena de tokens: t1 t2 t3 t4 t5
- Escoger reglas gramaticales.
- Obtener el árbol de análisis sintáctico o error
El árbol de derivación se construye:
- Desde la raíz
- De izquierda a derecha
Clasificación
- Analizador sintáctico descendente con retroceso.
- Analizador sintáctico descendente con recursión.
- Analizador sintáctico descendente LL(1)
Análisis sintáctico descendente con retroceso
El método parte del axioma inicial y aplica todas las posibles reglas al no terminal más a la izquierda.
- Se usa el retroceso para resolver la incertidumbre.
- Sencillo de implementar.
- Muy eficiente.
Ejemplo:
Análisis sintáctico descendente con predictivo
El analizador debe realizar la previsión de la regla a aplicar sólo con ver el primer símbolo que produce para que el algoritmo tenga una complejidad lineal.
Las gramáticas que son susceptibles de ser analizadas sintácticamente de forma descendente mediante un análisis predictivo y consultando un únicamente un símbolo de entrada pertenecen al grupo LL(1).
A partir de gramáticas LL(1) se pueden construir analizadores sintácticos descendentes predictivos (ASDP), que son ASD sin retroceso.
Ejemplo:
Conjuntos de Predicción
- Son conjuntos de símbolos terminales
- Ayudan a predecir qué regla se debe aplicar para el no terminal que hay que derivar.
- Se construyen a partir de los símbolos de las partes derechas de las producciones de la gramática.
- El analizador consulta el siguiente símbolo en la entrada.
- Si pertenece al conjunto de predicción de una regla aplica esa regla, si no da error.
Analizador sintáctico descendente LL(1)
Características de la condición LL(1)
- La secuencia de tokens se analiza de izquierda a derecha.
- Siempre deriva el no terminal que aparezca más a la izquierda.
- Sólo es necesario ver un token de la secuencia de entrada para averiguar que regla de producción seguir.
Diferencias entre el descendente y el ascendente
- En el análisis sintáctico descendente: se construye el árbol sintáctico de arriba hacia abajo y se utiliza más reglas.
- En el análisis sintáctico ascendente: se construye el árbol sintáctico de abajo hacia arriba, lo cual disminuye el número de reglas mal aplicadas con respecto al caso descendente.
Véase también
- Intérprete
- Compilador
- Lenguaje de programación
- Tokens
- Analizador sintáctico LL
- Analizador sintáctico LR
- Analizador sintáctico ascendente
