Page 88 - LENGUAJES FORMALES AUTOMATAS Y COMPILADOS

88

ENTREGA IX

GRAMÁTICA INDEPENDIENTE DEL CONTEXTO QUE REQUIERE UN LL (2)

1- S XSZ
2- SXYTYZ
3- TΛ

Con el principio de pre análisis se resuelven las incertidumbres de los analizadores sintácticos
predictivos. Obsérvese que con esta gramática, con el hecho de que sepamos que el primer
símbolo a leer es x no me sirve para saber si aplico la derivación 1 o la 2, la decisión depende de
los 2 símbolos siguientes; por lo que se requiere el uso de almacenamiento de memoria para 2
símbolos de entrada.

Hay que indicar, que existen lenguajes que no pueden ser analizados con este sistema de pre
análisis por muy grande que sea k (números de símbolos pre analizados por el analizador).

Para realizar este trabajo de análisis conviene construir tablas de análisis sintácticos, previo a
llevar la rutina a una forma programable, solo para efectos de entenderlo y aplicarlo mejor.

Tablas para realizar análisis sintáctico

Consiste en un matriz bidimensional donde las filas representan los no terminales de la gramática.
Las columnas etiquetan a los símbolos terminales. En ocasiones se coloca una última columna de
fin de cadena (FC)

Un elemento (M, N) de esta matriz, representa la acción que debe tomarse cuando el no terminal
m aparece en la cima de la pila y el símbolo de pre análisis es n. Se coloca en esa posición del
elemento (M, N) la regla de reescritura correspondiente, de lo contrario debe indicar un error.

Verificando la siguiente gramática, para efectos de construir la tabla, sería lo siguiente:

S ZMNZ
MAMA
MZ
NBNB
NZ

A B Z FC
S ERROR ERROR ZMNZ ERROR
M AMA ERROR Z ERROR
N ERROR BNB Z ERROR

Debería entenderse que cuando el símbolo s, está en la cima de la pila, y el elemento leído (de la
entrada para el pre análisis) es a, no hay ninguna derivación prevista por la gramática, en
consecuencia la salida es hacia una rutina de error. Si fuera el caso, que en la cima de la pila se
ve al no terminal s y el símbolo leído para pre análisis es z, la derivación a escoger es la primera
citada, esto es: S ZMNZ. Igual debe analizarse, tal como se ve en la tabla. Es evidente que con
un solo símbolo en este caso para S, solo es Z. Obsérvese que para el caso de el no terminal M,