3.4 Análisis Sintáctico Ascendente

En esta sección se introduce un estilo general de análisis sintáctico ascendente, conocido como análisis sintáctico por desplazamiento y reducción.  El análisis sintáctico por desplazamiento y reducción intenta construir un árbol de análisis sintáctico para una cadena de entrada que comienza por las hojas (el fondo) y avanza hacia la raíz (la cima). Se puede considerar este proceso como de "reducir" una cadena w al símbolo inicial de la gramática. En cada paso de reducción se sustituye una subcadena determinada que concuerde con el lado derecho de una producción por el símbolo del lado izquierdo de dicha producción y si en cada paso se elige correctamente la subcadena, se traza una derivación por la derecha en sentido inverso.

Ejemplo Considérese la gramática

S-> aABe

A-> Abc | b

B->d

La frase abbcde se puede reducir a S por los siguientes pasos:

abbcde

aAbcde

aAde

aABe

S

Se examina abbcde buscando una subcadena que concuerde con el lado derecho de alguna producción. Las subcadenas b y d sirven. Elijase la b situada más a la izquierda y sustitúyase por A, el lado izquierdo de la producción A-> b; así se obtiene la cadena aAbcde. A continuación, las subcadenas Abc, b y d concuerdan con el lado derecho de alguna producción. Aunque b es la subcadena situada más a la izquierda que concuerda con el lado derecho de una producción, se elige sustituir la subcadena Abc por A, que es el lado derecho de la producción A->Abc. Se obtiene ahora aAde. Sustituyendo después d por B, que es el lado izquierdo de la producción B-> d, se obtiene aABe. Ahora se puede sustituir toda esta cadena por S. Por tanto, mediante una secuencia de cuatro reducciones se puede reducir abbcde a S. De hecho, estas reducciones trazan la siguiente derivación por la derecha en orden inverso:

S =>_md aABe =>_md aAde => aAbcde =>_md abbcde

Mangos

Informalmente, un ''mango" de una cadena es una subcadena que concuerda con el lado derecho de una producción y cuya reducción al no terminal del lado izquierdo de la producción representa un paso a lo largo de la inversa de una derivación por la derecha. En muchos casos, la subcadena situada más a la izquierda β que concuerda con el lado derecho de alguna producción A -> β no es un mango, porque una reducción por la producción A->β produce una cadena no reducible al símbolo inicial.

Ejemplo

S-> aABe

A-> Abc | b

B->d

La frase abbcde se puede reducir a S por los siguientes pasos:

abbcde

aAbcde

aAde

aABe

S

En el ejemplo, si se sustituyera b por A en la segunda cadena aAbcde se obtendría la cadena aAAcde que no se puede reducir posteriormente a S. Por esta razón, se debe dar una definición más precisa de un mango. Formalmente, un mango de una forma de frase derecha γ es una producción A ->β y una posición de γ donde la cadena β podría encontrarse y sustituirse por A para producir la forma de frase derecha previa en una derivación por la derecha de γ. Es decir, si S*=>_md aAw *=>_md aβw, entonces A->β si la posición que sigue de a es un  mango de aβw. La cadena w a la derecha del mango contiene sólo símbolos terminales. Obsérvese que dice "un mango" en lugar de “el mango”, porque la gramática podría ser ambigua, con más de una derivación por la derecha de aβw. Si una gramática no es ambigua, entonces toda forma de frase derecha de la gramática tiene exactamente un mango.

En el ejemplo anterior abbcde es una forma de frase derecha cuyo mango es A->b en la posición 2. Del mismo modo, aAbcde es una forma de frase derecha cuyo mango es A -> Abc en la posición 2. Algunas veces se dice "la subcadena β es un mango de aβw" si están claras la posición de β y la producción A->β que se tienen en mente.

El mango representa al subárbol completo situado más a la izquierda que consta de un nodo y todos sus hijos. En la figura A es el nodo interior situado más abajo y más a la izquierda con todos sus hijos en el árbol. Se puede considerar como "poda del mango", es decir, eliminación de los hijos de A del árbol de análisis sintáctico.

Poda

Se puede obtener una derivación por la derecha en orden inverso mediante la "poda de mangos". Es decir, se comienza con una cadena de terminales w que se desee analizar sintácticamente. Si w es una frase de la gramática en cuestión. Entonces w = γ_n, donde γ_n es la n-ésima forma de frase derecha de una, aún desconocida, derivación por la derecha.

S=γ₀=>_md γ₁=>_mdγ₂ . . . =>_md γ_n-1=>γ_n=w

Para reconstruir esta derivación en orden inverso, se coloca el mango βn, en γ_n y se reemplaza βn  por el lado izquierdo de alguna producción An->βn para obtener la (n - 1)-ésima forma de frase derecha γn-1• Obsérvese que aún no se sabe cómo encontrar los mangos, pero pronto se verán los métodos para hacerlo.

Después se repite este proceso. Es decir, se sitúa el mango β_n , en γ_n-1 y se reduce este mango para obtener la forma de frase derecha γ_{n – 2}. Si al continuar este proceso se produce una forma de frase derecha que conste sólo del símbolo inicial S, entonces se para y se anuncia la realización con éxito del análisis sintáctico. La inversa de la secuencia de producciones utilizada en estas reducciones es una derivación por la derecha de la cadena de entrada.