14 Nov 2008 - 03:58:35
Análisis Sintáctico Descendente.
Como ya se ha comentado en publicaciones anteriores, el analizador sintáctico corresponde a la segunda fase del proceso de compilación y su tarea primordial es identificar las formaciones de sintaxis definidas en un lenguaje formal, este análisis está vinculado de manera estrecha con el análisis lexicográfico por que este último le otorga los tokens al analizador sintáctico para definir las estructuras gramaticales que en este caso son los arboles de análisis gramatical. Por la naturaleza de funcionamiento del análisis sintáctico se le necesita otorgar un carácter predictivo por que trabaja en base derivaciones que requieren que el analizador este prevenido en los tokens posteriores que le serán entregados. Una de las técnicas más sencillas para generar este tipo de estructuras es realizar un análisis sintáctico descendente recursivo, esta técnica indica que por cada símbolo no terminal que se encuentre deberá existir un procedimiento que se encargue de derivar este símbolo hasta llegar a sus símbolos terminales. Esto es parecido a la forma en cómo en un lenguaje de programación se pueden realizar llamadas de procedimientos dentro de otros, como resultado se obtiene una casada de llamadas de procedimientos que involucran recursividad.En otras palabras el análisis sintáctico pertenece a un tipo de método determinativo, tomando en cuenta que todo parte de un símbolo de pre análisis que puede ser considerado como la raíz del árbol gramatical y que nos va a determinar que regla de producción será aplicada y cada símbolo no terminal que se encuentre en las derivaciones posteriores de esta regla sustituirá a la raíz de nuestro árbol actual de producción, es por eso que se le llaman descendentes y recursivos.
Gramáticas LL.
Estas gramáticas son una forma de realizar un análisis sintáctico descendente recursivo con la única diferencia de que una tabla para realizar el análisis (LL(1)), “La primera L establece el hecho de que la cadena de caracteres de entrada se rastrea de izquierda a derecha. La segunda L., que se construye una derivación de extremo izquierdo, y el 1 significa que puede utilizarse un símbolo hacia adelante para crear la tabla” (Lemone 1996 p.71). En palabras llanas, el concepto anterior nos indica que con las LL(I) vamos a poder examinar en cada momento el símbolo actual de la cadena de entrada procesándola de izquierda a derecha al igual que sus derivaciones utilizando un solo símbolo de análisis para decidir la regla a aplicar.Para esta técnica es necesario utilizar dos apuntadores uno para identificar el símbolo de pre análisis en un determinado nivel de producción del árbol gramatical (símbolos no terminales) y otro para considerar sus derivaciones de izquierda a derecha (símbolos terminales).Se debe crear una tabla de derivaciones que permita consultar la acción siguiente a realizar dentro del análisis sintáctico, después de que sea creada esta tabla y se sepa cual es la próxima derivación a realizar, se implementa la parte más importante de esta técnica que es la utilización de una pila para saber la secuencia de sintaxis que deben tener los símbolos ya sean terminales o no terminales. El algoritmo de la implementación de esta pila inicia en el momento en que se otorga el primer símbolo que nos va a indicar que producción realizar, en este momento se inicializa la pila con el valor del símbolo en su tope y mientras esta pila no se encuentre vacía el símbolo que se encuentra en el tope será comparado para determinar si es terminal o no terminal, en el primero de los casos (terminal) se procesa el símbolo y la pila se vacía, en el segundo caso (no terminal) se busaca la producción correcta en la tabla de derivaciones, se vacía la pila y se introduce de derecha a izquierda los símbolos de la producción en cuestión. Esto se realizara hasta que la tabla ya no indique más derivaciones y la por lo tanto la pila estará vacía y ya no cumplirá con la condición del ciclo “mientras pila no vacía”.De esta manera a la hora de extraer los símbolos finales de la pila se cumplirá con el formato establecido por la técnica LL(i) basada en empezar a procesar los símbolos de izquierda a derecha.Otra de las opciones para realizar estas estructuras de análisis sintáctico es utilizar una de las muchas herramientas disponibles para generar analizadores sintácticos.
Referencias.
Lemone A. (1996) Fundamentos de Compiladores. (1ª. Ed.). México:
Compañía Editorial Continental S.A.
Sindicación
Este artículo no tiene Comentario por el momento .....