ANÁLISIS SINTÁCTICO DESCENDENTE Y ANÁLISIS SINTÁCTICO ASCENDENTE

ANÁLISIS ASCENDENTE

Parte de la cadena de entrada para construir la inversa de una derivación por la derecha. Genera el árbol de análisis sintáctico partiendo de las hojas hasta alcanzar el axioma.

Análisis ascendente se construye el árbol de análisis sintáctico de la cadena de entrada desde las hojas hasta  la raíz. En las hojas tenemos la cadena a analizar (los símbolos terminales) que se intentan reducir al axioma,  que se encontrara en la raíz, si la cadena es correcta sintácticamente. 

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 deforma 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 DESCENDENTE

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. 

Partir del axioma de la gramática

Escoger reglas gramaticales

Hacer derivaciones por la izquierda

Procesar la entrada de izquierda a derecha

Carácteristicas

• 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.

 ¿Cómo construir el árbol?

Se trata de desplazarse en la entrada hasta encontrar una subcadena de símbolos que represente la parte derecha de una producción, en ese momento sustituimos esa subcadena por el no-terminal de la parte izquierda  correspondiente de la producción, la reducimos.

Ejemplo: Supongamos la siguiente gramática que permite generar expresiones aritméticas donde aparece el operador suma y potencia y combinar números e identificadores.

Nos restringimos al caso de métodos deterministas (no hay vuelta atrás) analizando un solo símbolo de pre  análisis sabemos exactamente en todo momento que acción realizar: bien desplazarnos en la entrada o bien  aplicar una reducción. En el caso de una reducción debemos saber de forma única que producción aplicar.

Los métodos ascendentes se caracterizan porque analizan la cadena de componentes léxicos de izquierda a  derecha, obtienen la derivación más a la derecha y el árbol de derivación se construye desde la raíz hasta las hojas.

Diferencia entre Análisis Sintáctico Descendente, Análisis Sintáctico Ascendente:

Ascendente: Se parte de las hojas y se intenta construir el árbol hacia arriba hasta llegar al símbolo inicial de la gramática

• En un análisis top-down un parser hacer corresponder cadenas de entrada con sus correspondientes derivaciones izquierdas.
• En un análisis bottom-up un parser hace corresponder cadenas de entrada con las inversas de las correspondientes derivaciones derechas.

Descendente: En este tipo de análisis, se va recorriendo el árbol sintáctico desde la raíz hasta las hojas, llegando a generar la sentencia que se está analizando. La raíz representa el símbolo inicial de la gramática. 

BIBLIOGRAFÍA:

Análisis sintáctico descendente y análisis sintáctico ascendente, diferencias en linea [http://www.infor.uva.es/~teodoro/Ejer3-3.pdf] 14 de diciembre del 2010.