4.2 Algoritmos para Cálculo de Atributos
|
Al igual que existen herramientas que construyen analizadores sintácticos a partir de gramáticas libres de contexto, también existen herramientas automáticas que generan evaluadores de gramáticas atribuidas o, en la mayor parte de los casos, definiciones dirigidas por sintaxis. En muchas ocasiones, las herramientas de desarrollo de procesadores de lenguaje ofrecen la posibilidad de especificar, de un modo imperativo en lugar de declarativo, las reglas semánticas de las definiciones dirigidas por sintaxis (gramáticas atribuidas). Esta notación es la que se conoce como esquema de traducción (dirigida por sintaxis): una gramática libre de contexto en la que se asocian atributos con los símbolos gramaticales y se insertan rutinas semánticas dentro de las partes derecha de las producciones [Aho90]. Las rutinas semánticas son, a su vez, fragmentos de código que el desarrollador del compilador escribe –normalmente entre llaves {} – dejando explícito el momento en el que la herramienta ha de ejecutar la misma, durante su proceso de análisis. La principal diferencia entre las herramientas que emplean gramáticas atribuidas y aquéllas que ofrecen esquemas de traducción es que en las segundas el desarrollador especifica el momento en el que se ha de ejecutar el código. Sin embargo, en las gramáticas atribuidas y definiciones dirigidas por sintaxis, el proceso de evaluación de los atributos debe ser resuelto por la propia herramienta. La evaluación de una gramática atribuida, conlleva procesos como la creación y ordenamiento topológico de un grafo de dependencias, o la limitación a priori de las características de la gramática La mayoría de las herramientas que generan analizadores sintácticos ofrecen la posibilidad de añadir rutinas semánticas, definiendo así un esquema de traducción. Herramientas como yacc/bison [Johnson75], ANTLR [ANTLR] o JavaCC [JavaCC] permiten entremezclar rutinas semánticas con las producciones de las gramáticas libres de contexto. Puesto que los esquemas de traducción ejecutan las rutinas semánticas de un modo imperativo, el modo en el que se deriven las distintas producciones de la gramática variará el orden de ejecución de las rutinas. De este modo, el diferenciar si un esquema de traducción emplea un análisis descendente o ascendente es fundamental para la ubicación de sus rutinas semánticas. En los generadores de analizadores sintácticos descendentes que incorporan esquemas de traducción (por ejemplo JavaCC o ANTLR), las rutinas semánticas pueden aparecer en cualquier parte de la parte derecha de la producción. Una rutina semántica al comienzo de la parte derecha de una producción será ejecutada cuando el analizador tome la decisión de derivar por dicha producción. Una rutina situada en el medio de la parte derecha de una producción se ejecutará una vez haya derivado todos los símbolos de la parte derecha, ubicados a su izquierda. Como se aprecia en el párrafo anterior, las limitaciones de los esquemas de traducción basados en analizadores descendentes son los mismos que los identificados para la evaluación descendente de gramáticas L-atribuidas en una única pasada (§ 5.2). Adicionalmente a estas limitaciones, hay que añadir que la ubicación de las rutinas semánticas, dentro de la parte derecha de cada producción, sea en los sitios oportunos. Las restricciones para ubicar las rutinas son [Aho90]:
|