3.5 Analisis Sintáctico Descendente

En esta sección se introducen las ideas básicas del análisis sintáctico descendente y se enseña a construir una forma eficiente sin retroceso de un analizador sintáctico descendente llamada analizador sintáctico predictivo. Se define la clase de gramáticas LL a partir de las cuales se pueden construir de manera automática analizadores sintácticos predictivos.

Análisis sintáctico por descenso recursivo

Se puede considerar el análisis sintáctico descendente como un intento de encontrar una derivación por la izquierda para una cadena de entrada También se puede considerar como un intento de construir un árbol de análisis sintáctico para la entrada comenzando desde la raíz y creando los nodos del árbol en orden previo.

El descenso recursivo,  puede incluir retrocesos, es decir, varios exámenes de la entrada. Sin embargo, no hay muchos analizadores sintácticos con retroceso. En parte, porque casi nunca se necesita el retroceso para analizar sintácticamente las construcciones de los lenguajes de programación. En casos como el análisis sintáctico del lenguaje natural, el retroceso tampoco es muy eficiente, y se prefieren los métodos tabulares, como el algoritmo de programación dinámica o el método de Earley [1970)

Ejemplo  Considérese la gramática

S -> cAd

A ->ab |a

y la cadena de entrada w = cad. Para construir un árbol de análisis sintáctico descendente para esta cadena, primero se crea un árbol formado por un solo nodo etiquetado con S. Un apuntador a la entrada apunta a c, el primer símbolo de w. Después se utiliza la primera producción de S para expandir el árbol y obtener el árbol de la figura (a).

Se empareja la hoja situada más a la izquierda, etiquetada con c, con el primer símbolo de w, y a continuación se aproxima el apuntador de entrada a α, el segundo símbolo de w, y se considera la siguiente hoja etiquetada con A. Entonces se puede expandir A utilizando la primera alternativa de A para obtener el árbol de la figura (b). Como ya se tiene una concordancia para el segundo símbolo de la entrada se lleva el apuntador de entrada a d. el tercer símbolo de la entrada, y se compara d con la hoja siguiente, etiquetada con b. Como b no concuerda con d, se indica fallo y se regresa a A para saber si existe otra alternativa de A que no se haya intentado, pero que pueda dar lugar a un emparejamiento.

Al regresar a A , se debe restablecer el apuntador de entrada a la posición 2, aquella que tenía al ir a A por primera vez, lo cual significa que el procedimiento para A debe almacenar el apuntador a la entrada en una variable local. Se intenta a continuación la segunda alternativa de A para obtener el árbol de la figura (c). Se empareja la hoja a con el segundo símbolo de w. y la hoja d con el tercer símbolo. Como ya se ha producido un árbol de análisis sintáctico para w, se para y se anuncia el éxito de la realización completa del análisis sintáctico.

Una gramática recursiva por la izquierda puede hacer que un analizador sintáctico por descenso recursivo, incluso uno con retroceso, entre en un lazo infinito. Es decir, cuando se intenta expandir A, puede que de nuevo se esté intentando expandir A sin haber consumido ningún símbolo de entrada.

Analizadores sintácticos predictivos

En muchos casos, escribiendo con cuidado una gramática, eliminando su recursión por la izquierda y factorizando por La izquierda la gramática resultante, se puede obtener una gramática analizable con un analizador sintáctico por descenso recursivo que no necesite retroceso, es decir, un analizador sintáctico predictivo, para construir un analizador sintáctico predictivo, se debe conocer, dado el símbolo actual a de entrada y el no terminal A a expandir, cuál de las alternativas de producción A->α₁ | α₂ | . . . | α_n, es la única alternativa que da lugar a una cadena que comience con α. Es decir, la alternativa apropiada debe ser detectable con sólo ver el primer símbolo al que da lugar. Así se detectan generalmente las construcciones de flujo de control de la mayoría de los lenguajes de programación, con sus palabras clave diferenciadoras. Por ejemplo, si se tienen las producciones

prop -> if expr then prop else prop

| while expr do prop

| begin lista_props end

Las palabras clave if, while y begin indican qué alternativa es la única con posibilidad de éxito para encontrar una proposición.

Análisis sintáctico predictivo no recursivo

Se puede construir un analizador sintáctico predictivo no recursivo explícitamente manteniendo una pila, en lugar de hacer lo implícitamente mediante llamadas recursivas. El problema clave durante el análisis sintáctico predictivo es determinar la producción que debe aplicarse a un no terminal el analizador sintáctico no recursivo de la figura  busca la producción que debe aplicarse en una tabla de análisis sintáctico. A continuación se verá cómo se puede construir directamente la tabla a partir de ciertas gramáticas.

Figura 4.5 Análisis sintáctico predictivo no recursivo

Un analizador sintáctico predictivo guiado por tablas tiene un buffer de entrada, una pila, una tabla de análisis sintáctico y una cadena de salida. El buffer de entrada contiene la cadena que se va a analizar, seguida de $, un símbolo utilizado como delimitador derecho para indicar el fin de la cadena de entrada. La pila contiene una secuencia de símbolos gramaticales con $ en la parte de abajo, que indica la base de la pila. Al principio, la pila contiene el símbolo inicial de la gramática encima de $.

La tabla de análisis sintáctico es una matriz bidimensional M[ A, α], donde A es un no terminal y a es un terminal o el símbolo$.

Se controla el analizador sintáctico mediante un programa que se comporta como sigue. El programa tiene en cuenta X, el símbolo de la cima de la pila, y a, el símbolo en curso de la entrada. Estos dos símbolos determinan la acción del analizador. Existen tres posibilidades:

1. Si X = a = $, el analizador sintáctico se detiene y anuncia el éxito de la realización del análisis.
2. Si X = a ≠ $, el analizador sintáctico saca a X de la pila y mueve el apuntador de entrada al siguiente símbolo de entrada.
3. Si X es un no terminal, el programa consulta la entrada M[X, α] de la tabla M de análisis sintáctico. Esta entrada será o una producción de X de la gramática o una entrada de error. Si, por ejemplo, M[X, α] = {X-> UVW}, el analizador sintáctico sustituye la X de la cima de la pila por WVU (con U en la cima). Como salida, se sabe que el analizador sintáctico sólo imprime la producción utilizada: ahí se podría ejecutar cualquier otro código. Si M[X, α] = error, el analizador sintáctico llama a una rutina de recuperación de error.

Se puede describir el comportamiento del analizador sintáctico en función de sus configuraciones, que dan el contenido de la pila y la entrada restante.

Algoritmo Análisis sintáctico predictivo no recursivo.

Entrada. Una cadena w y una tabla de análisis sintáctico M para la gramática G.

Salida. Si w está en L(G), una derivación por la izquierda de w; de lo contrario, una indicación de error.

Método. Al principio, el analizador sintáctico está en una configuración en la que tiene a $S en la pila con S, el símbolo inicial de G en el tope, y w$ en el buffer de entrada.