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 A de la gramática, hacer 2 y 3. 2.- Por cada terminal a en primero ( ), agregar
A a M [A, a] 3.- Si esta en PRIMERO(), agregar
A 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  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  Y1 Y2 ...Yk
 Sino 
  error
 FinSi
FinSi
3.- Hasta - Que X = $

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

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

Podemos construir la siguiente tabla M: