Análisis Sintáctico Descendente y Ascendente

Análisis Sintáctico Descendente y Ascendente hace referencia en la sentido en que construyen los nodos del árbol de análisis sintáctico. En el primero la construcción se inicia en la raíz de árbol y avanza hacia las hojas. En el segundo la construcción se inicia en las hojas y avanza hacia la raíz. La diferencia entre uno y otro es que en el primero se pueden construir manualmente analizadores más eficiente con mayor facilidad mientras que en el segundo se puede manejar una mayor cantidad de gramáticas y esquemas de traducción.

La consideración esencial para la elección de uno de estos dos métodos es la de ramificación, normalmente se usará el método que permita una menor ramificación a partir de los nodos. Además, estos dos enfoques pueden combinarse, y de hecho es usual, en un solo parser.

Análisis sintáctico descendente

Explicaremos este método con un ejemplo, usando la siguiente gramática simple, G1 (T1, N1, P1, S1) que define los enteros no negativos (ENN)

T1 = {0,1,2,3,4,5,6,7,8,9}

N1 = {DIGITO, ENN}

P1 = {ENN à DIGITO | ENN DIGITO}

DIGITO à 0|1|2|3|4|5|6|7|8|9|

S1 = {ENN}

Queremos analizar la frase 123. en un principio solo conocemos la raíz del árbol y la frase que debe analizarse.

Árbol semántico frase

ENN 1 2 3

En el primer paso encontramos la producción ENN à ENN DIGITO y obtenemos el inicio del árbol de análisis sintáctico.

 

En el siguiente paso hallamos de nuevo al misma producción.

Después encontramos la producción ENN à DIGITO, que expande el árbol sintáctico a lo siguiente:
Encontramos ahora la producción DIGITO à 1, que establece la conexión con el primer elemento de la frase dada.

La producción DIGITO à 2 establece la conexión con el segundo elemento de la frase:

Por ultimo el árbol de análisis sintáctico queda completo con la producción DIGITO à 3.

Podemos ver que el árbol crece de arriba abajo a medida que se lee la frase de entrada de izquierda a derecha. por consiguiente, este método se denomina análisis sintáctico descendente.

Análisis sintáctico ascendente.

Ejemplifiquemos el análisis sintáctico ascendente usando otra vez la gramática G1 y la frase 123. de nuevo, solo sabemos cual es la raíz del árbol de análisis sintáctico y la frase que debemos de analizar. En el primer paso se encuentran la reducción 1 ß DIGITO y se obtiene el inicio del árbol sintáctico.

 

En el segundo paso se encuentra la reduccion del DIGITO ß ENN y se obtiene el segundo arbol sintactico

El tercer paso reduce el segundo elemento de la frase usando la reducción 2 ß DIGITO

Entonces se aplica la reducción DIGITO ß ENN para continuar con el arbol de análisis sintactico:

En el paso siguiente se reduce a un digito el ultimo elemento de la frase: 3 ß DIGITO.

 

Para concluir se completa el árbol de análisis sintáctico con la reducción ENN DIGITO ß ENN:

A partir de este ejemplo podemos ver que comenzamos con las hojas del árbol sintáctico y asciende hacia la raíz. Por ello, este método se denomina análisis sintáctico ascendente.

Fuentes:

Responder

Introduce tus datos o haz clic en un icono para iniciar sesión:

Logo de WordPress.com

Estás comentando usando tu cuenta de WordPress.com. Cerrar sesión / Cambiar )

Imagen de Twitter

Estás comentando usando tu cuenta de Twitter. Cerrar sesión / Cambiar )

Foto de Facebook

Estás comentando usando tu cuenta de Facebook. Cerrar sesión / Cambiar )

Google+ photo

Estás comentando usando tu cuenta de Google+. Cerrar sesión / Cambiar )

Conectando a %s