Análisis descendente

Un analizador gramatical descendente es conducido por una tabla (llamada M) que permite sustituir al axioma por los lados derechos de producciones de la gramática hasta obtener la entrada que se está analizando.

Generalmente esta sustitución se realiza reemplazando al noterminal más a la izquierda en una sustitución anterior por una forma equivalente (el lado derecho de una producción para ese noterminal). La tabla M tiene entradas por renglones para los noterminales de la gramática y columnas que representan los terminales.

La tabla M se construye con el siguiente algoritmo: CREACION DE LA TABLA M   1.- Por cada producción AflechaAlfa de la gramática, hacer 2 y 3. 2.- Por cada terminal a en primero ( Alfa), agregar
AflechaAlfa a M [A, a] 3.- Si epsilonesta en PRIMERO(Alfa), agregar
AflechaAlfa a M [A, b]
para cada b en SIGUIENTE(A). 4.- Hacer error para cada localidad vacía.

El analizador descendente se guía consultando la tabla M y realizando las acciones que indica el siguiente algoritmo:   ANALIZADOR GRAMATICAL DESCENDENTE PREDICTIVO NO RECURSIVO Entrada: Cuerda W y tabla M para la gramática G.
Salida: Si W está generada de acuerdo a G, se obtiene la derivación más a la izquierda; si no, error.
Método: Inicialmente $ Axioma están en la pila del analizador y W$ está en el buffer de entrada.

1.- Colocar ip en el símbolo inicial de W$.
2.- REPETIR.
Sea X el simbolo en la cima de la pila y a el simbolo apuntado por ip.
Si X es un terminal o $ 
Entonces
 Si X = a 
 Entonces
  Saca X de la pila y avanza ip
 Sino 
  error
 Fin -Si
Sino
 Si M[X,a] = X flecha Y1 Y2 ...Yk 
 Entonces
  Saca X de la pila.
  Mete Yk, Yk-1 , ........ Y1 en la pila con Y1 en la cima.
  Escribe la produccion X flecha Y1 Y2 ...Yk
 Sino 
  error
 FinSi
FinSi
3.- Hasta - Que X = $

Ejemplo: Considernado la siguiente gramática (sin recursión izquierda)

 EXPRESIONflechaFACTOR TERMINO ‘ EXPRESION ‘ (1)
EXPRESION ‘flechaOPSR TERMINO EXPRESION ‘ (2)
flecha lambda (3)
TERMINOflechaFACTOR TERMINO ‘ (4)
 TERMINO ‘flechaOPMD FACTOR TERMINO’ (5)
flechalambda (6)
FACTORflecha( EXPRESION ) (7)
flechaOPERANDO (8)
 OPSRflecha+ (9)
 flecha (10)
OPMD flecha* (11)
 flecha / (12)

Podemos construir la siguiente tabla M:

 Noterminal Operando + – * / ( ) $
 EXPRESION (1) (1)
 EXPRESION’ (2) (2) (3) (3)
 TERMINO (4) (4)
 TERMINO’ (6) (6) (5) (5) (6) (6)
 FACTOR (8) (7)
 OPSR (9) (10)
 OPMD (11) (12)