Análisis Sintáctico
Ascendente
Al
contrario que el analizador descendente, el ascendente (el tipo de
análisis ascendente más conocido es el análisis
por desplazamiento/reducción) utiliza derivaciones más
a la derecha, construyendo el árbol sintáctico desde
las hojas hasta la raíz. Es decir, se parte desde la cadena de
entrada a evaluar y a partir de ella se intenta llegar al símbolo
inicial de la gramática. En cada paso, el analizador lo que
hace es reducir una parte de la cadena por la parte izquierda de
alguna producción, donde su parte derecha concuerde con la
subcadena que se está reduciendo. Sería como hacer una
derivación más a la derecha pero en orden inverso, es
decir, partir de la cadena a evaluar y terminar en el símbolo
inicial de la gramática.
Por
ejemplo con la siguiente gramática:
S→aBCa
B→bb
C→c
La cadena
abbca se podría reducir al símbolo S
inicial de la gramática de forma ascendente
con los siguientes pasos.
1.- abbca
2.- aBca
Reduciendo por la producción B→bb
3.- aBCa
Reduciendo por la producción C→c
4.- S
Reduciendo por la producción S→aBCa
Lo primero
que se hace es ver la cadena de entrada, y buscar una subcadena de
dicha entrada que concuerde con alguna parte derecha de alguna
producción. En este caso la subcadena bb
concuerda con la parte derecha de la producción B→bb,
con ello se obtiene la cadena aBca
Después la subcadena c
concuerda con la parte derecha de la producción C→
c, reduciendo dicha subcadena por la parte
izquierda de esta producción se obtiene la cadena aBc.
Finalmente esta subcadena concuerda con la parte derecha de la
primera producción, haciendo esta última reducción
se consigue llegar al símbolo inicial de la gramática,
con lo que se ha conseguido analizar con éxito la cadena de
entrada. Como se puede ver este proceso es una derivación más
a la derecha.
S aBCaaBcaabbca
Submenu
|
