Diseño del compilador: analizador de arriba hacia abajo

Hemos aprendido en el último capítulo que la técnica de análisis de arriba hacia abajo analiza la entrada y comienza a construir un árbol de análisis desde el nodo raíz que se mueve gradualmente hacia los nodos hoja. Los tipos de análisis de arriba hacia abajo se muestran a continuación:

Análisis de descenso recursivo

El descenso recursivo es una técnica de análisis de arriba hacia abajo que construye el árbol de análisis desde la parte superior y la entrada se lee de izquierda a derecha. Utiliza procedimientos para cada entidad terminal y no terminal. Esta técnica de análisis analiza de forma recursiva la entrada para crear un árbol de análisis, que puede requerir o no un retroceso. Pero la gramática asociada con él (si no se deja factorizada) no puede evitar el retroceso. Una forma de análisis sintáctico de descenso recursivo que no requiere ningún retroceso se conoce comopredictive parsing.

Esta técnica de análisis se considera recursiva ya que utiliza una gramática libre de contexto que es recursiva por naturaleza.

Seguimiento

Los analizadores de arriba hacia abajo comienzan desde el nodo raíz (símbolo de inicio) y comparan la cadena de entrada con las reglas de producción para reemplazarlas (si coinciden). Para entender esto, tome el siguiente ejemplo de CFG:

S → rXd | rZd
X → oa | ea
Z → ai

Para una cadena de entrada: read, un analizador de arriba hacia abajo, se comportará así:

Comenzará con S de las reglas de producción y hará coincidir su rendimiento con la letra más a la izquierda de la entrada, es decir, 'r'. La misma producción de S (S → rXd) coincide con él. Entonces, el analizador de arriba hacia abajo avanza a la siguiente letra de entrada (es decir, 'e'). El analizador intenta expandir la 'X' no terminal y verifica su producción desde la izquierda (X → oa). No coincide con el siguiente símbolo de entrada. Entonces, el analizador de arriba hacia abajo retrocede para obtener la siguiente regla de producción de X, (X → ea).

Ahora el analizador compara todas las letras de entrada de forma ordenada. Se acepta la cadena.

Analizador predictivo

El analizador predictivo es un analizador de descenso recursivo, que tiene la capacidad de predecir qué producción se utilizará para reemplazar la cadena de entrada. El analizador predictivo no sufre retroceso.

Para realizar sus tareas, el analizador predictivo utiliza un puntero de anticipación, que apunta a los siguientes símbolos de entrada. Para que el analizador sea libre de retroceso, el analizador predictivo impone algunas restricciones a la gramática y acepta solo una clase de gramática conocida como gramática LL (k).

El análisis predictivo utiliza una pila y una tabla de análisis para analizar la entrada y generar un árbol de análisis. Tanto la pila como la entrada contienen un símbolo de fin$para indicar que la pila está vacía y la entrada se consume. El analizador se refiere a la tabla de análisis para tomar cualquier decisión sobre la combinación de elementos de entrada y pila.

En el análisis sintáctico descendente recursivo, el analizador puede tener más de una producción para elegir para una única instancia de entrada, mientras que en el analizador sintáctico predictivo, cada paso tiene como máximo una producción para elegir. Puede haber casos en los que no haya producción que coincida con la cadena de entrada, lo que hace que el procedimiento de análisis falle.

Analizador LL

Un analizador LL acepta la gramática LL. La gramática LL es un subconjunto de la gramática libre de contexto, pero con algunas restricciones para obtener la versión simplificada, con el fin de lograr una implementación fácil. La gramática LL se puede implementar por medio de ambos algoritmos, a saber, descenso recursivo o impulsado por tablas.

El analizador LL se denota como LL (k). La primera L en LL (k) está analizando la entrada de izquierda a derecha, la segunda L en LL (k) representa la derivación más a la izquierda y k en sí mismo representa el número de miradas hacia adelante. Generalmente k = 1, por lo que LL (k) también se puede escribir como LL (1).

Algoritmo de análisis de LL

Podemos ceñirnos a LL (1) determinista para la explicación del analizador sintáctico, ya que el tamaño de la tabla crece exponencialmente con el valor de k. En segundo lugar, si una gramática determinada no es LL (1), normalmente no es LL (k), para cualquier k dada.

A continuación se muestra un algoritmo para el análisis de LL (1):

Input: 
   string ω 
   parsing table M for grammar G

Output:
   If ω is in L(G) then left-most derivation of ω,
   error otherwise.

Initial State : $S on stack (with S being start symbol)
   ω$ in the input buffer

SET ip to point the first symbol of ω$.

repeat
   let X be the top stack symbol and a the symbol pointed by ip.

   if X∈ Vt or $
      if X = a
         POP X and advance ip.
      else
         error()
      endif
      
   else	/* X is non-terminal */
      if M[X,a] = X → Y1, Y2,... Yk    
         POP X
         PUSH Yk, Yk-1,... Y1 /* Y1 on top */
         Output the production X → Y1, Y2,... Yk 
      else
         error()
      endif
   endif
until X = $	/* empty stack */

Una gramática G es LL (1) si A → α | β son dos producciones distintas de G:

• para ningún terminal, tanto α como β derivan cadenas que comienzan con a.

• como máximo uno de α y β puede derivar una cadena vacía.

• si β → t, entonces α no deriva ninguna cadena que comience con una terminal en FOLLOW (A).