Analizador sintáctico ascendente
| ||||
Analizador sintáctico ascendente. (Bottom-Up-Parser). Un analizador puede empezar con la entrada e intentar llegar hasta el símbolo inicial, intuitivamente el analizador intenta encontrar los símbolos más pequeños y progresivamente construir la jerarquía de símbolos hasta el inicial.
Sumario
Objetivo de un análisis ascendente
El objetivo de un análisis ascendente consiste en construir el árbol sintáctico desde abajo hacia arriba, esto es, desde los tokens hacia el axioma inicial, lo cual disminuye el número de reglas mal aplicadas con respecto al caso descendente (si hablamos del caso con retroceso) o amplía el número de gramáticas susceptibles de ser analizadas (si hablamos del caso LL(1)).
Operaciones en un analizador ascendente
A medida que un analizador sintáctico va construyendo el árbol, se enfrenta a una configuración distinta (se denomina configuración al par á-â) y debe tomar una decisión sobre el siguiente paso u operación a realizar. Básicamente se dispone de cuatro operaciones diferentes, y cada tipo de analizador ascendente se distingue de los demás en base a la inteligencia sobre cuándo aplicar cada una de dichas operaciones.
Cualquier mecanismo de análisis ascendente consiste en partir de una configuración inicial e ir aplicando operaciones, cada una de las cuales permite pasar de una configuración origen a otro destino. El proceso finalizará cuando la configuración destino llegue a ser tal que α represente al árbol sintáctico completo y en β se hayan consumido todos los tokens. Las operaciones disponibles son las siguientes:
1. ACEPTAR: se acepta la cadena: β ≡ EOF y α ≡ S (axioma inicial).
2. RECHAZAR: la cadena de entrada no es valida.
3. REDUCIR: consiste en aplicar una regla de produccion hacia atras a algunos elementos situados en el extremo derecho de α.
4. DESPLAZAR: consiste unicamente en quitar el terminal mas a la izquierda de β y ponerlo a la derecha de α.
Clasificación
- Analizador sintáctico ascendente con retroceso.
- Analizador sintáctico ascendente LR(1)
Análisis ascendente con retroceso
Al igual que ocurría con el caso descendente, este tipo de análisis intenta probar todas las posibles operaciones (reducciones y desplazamientos) mediante un método de fuerza bruta, hasta llegar al árbol sintáctico, o bien agotar todas las opciones, en cuyo caso la cadena se rechaza.
En el análisis con retroceso no se permiten las reglas ԑ, puesto que estas se podrán aplicar de forma indefinida.
Análisis ascendente sin retroceso
El análisis ascendente sin retroceso busca una derivación derecha de la cadena de entrada de forma determinista.
Este se sustenta en su aplicación a las gramáticas LR(K).
La L viene de la lectura de la cadena de entrada de izquierda a derecha.
La R de producir un árbol de derivación derecho.
La k indica el número de símbolos que es necesario leer a la entrada para tomar la decisión de qué producción emplear.
Un parser del tipo shift-reduce puede verse como un autómata de pila determinista extendido que realiza el análisis de abajo hacia arriba.
Dada una cadena de entrada w, simula una derivación más a la derecha.
Análisis ascendente de gramáticas LR(1)
En esta parte se introducirá una técnica eficiente de análisis sintáctico ascendente que se puede utilizar para procesar una amplia clase de gramáticas de contexto libre. La técnica se denomina análisis sintáctico LR(k). La abreviatura LR obedece a que la cadena de entrada es examinada de izquierda a derecha (en ingles, Left-toright), mientras que la “R” indica que el proceso proporciona el árbol sintáctico mediante la secuencia de derivaciones a derecha (en ingles, Rightmost derivation) en orden inverso.
Por ultimo, la “k” hace referencia al numero de tokens de pre-búsqueda utilizados para tomar las decisiones sobre si reducir o desplazar. Cuando se omite, se asume que k, es 1.
Diferencias entre el descendente y el ascendente
- En el análisis sintáctico descendente: se construye el árbol sintáctico 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_(Informática)
- Compilador
- Lenguaje de programación
- Tokens
- Analizador sintáctico LL
- Analizador sintáctico LR
- Analizador sintáctico descendente
