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:
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) |