Análisis sintáctico descendente y ascendente.

ANALIZADOR SINTACTICO DESCENDENTE

En éste analizador las entradas son de izquierda a derecha, y construcciones de derivaciones por la izquierda de una sentencia o enunciado.

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.

Bueno primeramente 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.

- Primeros y siguientes

Ejemplo:

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 predictivo (ASDP)

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:

ANÁLISIS SINTÁCTICO 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 amplia el número de gramáticas susceptibles de ser analizadas (si hablamos del caso LL(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 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.

DIFERENCIAS

• 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 al símbolo inicial de la gramática.
• 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.
• Se basan su funcionamiento en la existencia de una tabla especial asociada de forma única a una gramática.
• El principal inconveniente del método ascendente es que supone demasiado trabajo construir manualmente un analizador sintáctico para una gramática de un lenguaje de programación típico.

Funte:
Wikipedia