Árboles De Sintaxis Abstracta (AST) y Gramática Con Atributos
Es una representación de árbol de la estructura sintáctica abstracta (simplificada) del código fuente escrito en cierto lenguaje de programación. Cada nodo del árbol denota una construcción que ocurre en el código fuente. Estos difieren de los arboles de análisis sintáctico en que las distinciones superficiales de forma, sin importancia en la traducción, no aparecen en los arboles sintacticos La sintaxis es abstracta en el sentido que no representa cada detalle que aparezca en la sintaxis verdadera. Los AST (Abstract Syntax Trees, o Árboles de Sintaxis Abstracta) sirven para manejar la información semántica de un código. La forma más eficiente de manejar la información proveniente de un lenguaje de programación es la forma arbórea; por eso la estructura de datos elegida es un árbol. Además, construyendo AST a partir de un texto podemos obviar mucha información irrelevante; si un AST se construye bien, no habrá que tratar con símbolos de puntuación. Al contrario que los flujos, una estructura en árbol puede especificar la relación jerárquica entre los símbolos de una gramática.
Los AST pueden intervenir en varias fases del análisis: como producto del análisis sintáctico, como elemento intermedio en sucesivos análisis semánticos y como entrada para la generación de código.
Una gramática con atributos es una gramática de contexto libre cuyos símbolos pueden tener asociados atributos y las producciones pueden tener asociadas reglas de evaluación de los atributos.
Cada símbolo puede tener asociado un número finito de atributos.
Cada producción puede tener asociada un número finito de reglas de evaluación de los atributos.
Los valores de los atributos deberán estar asociados con un dominio de valores.
Sea G = (T, N, P, S) una gramática de contexto libre y C = {c1,c2,…, cn} el conjunto de atributos asociados con los símbolos de la gramática G.
Dada una regla de evaluación b = f(c1,…,ck) asociado con la producción A ?a ? P.
Atributo Heredado: Si b está asociado con algún símbolo de alfa.
Atributo Sintetizado: Si b está asociado con el símbolo no terminal A.
Atributos Sintetizados
Evaluación:
Las reglas de evaluación de los atributos sintetizados se realizan cuando se aplican reducciones en el análisis sintáctico.
Requisitos para la evaluación:
Las reglas de evaluación de los atributos deben definirse en función de los atributos asociados con los símbolos gramaticales a su derecha.
Gramáticas S-Atribuidas
Cuando todos los atributos asociados con los símbolos gramaticales son sintetizados.
Ejemplo. Se muestra un ejemplo de gramática S-Atribuida:
Deseamos evaluar expresiones a la vez que la analizamos:
Sea el conjunto de producciones y acciones siguientes:
ACCIONES
L ->E { print (E1.val) }
E ->E + T { E0.val=E1.val + T3.val }
E ->T { E0.val =T1.val }
T ->T * F { T0.val = T1.val * F3.val }
T ->F { T0.val = F1.val }
F ->(E) { F0.val = E2.val }
F ->digito { F0.val = digito }
La evaluación de la expresión: 3*5+4n
Atributos Heredados
La evaluación de un atributo heredado depende de los atributos asociados con los símbolos precedentes en la derivación.
Requisitos:
Realizar un análisis descendente.
Dada la gramática y las reglas de evaluación siguientes:
Producciones Reglas
D ->TL L2.in = T1.tipo;
T ->int T0.tipo = entero;
T ->real T0.tipo = real;
L ->L,id L1.in = L0.in;
añadetipo(id, L0.in);
L ->id añadetipo(id, L0.in);
Real id1,id2,id3
Grafos De Dependencia
Cuando aparecen definidos atributos sintetizados y heredados, es necesario establecer un orden de evaluación de los atributos.
El grafo de dependencia es un grafo dirigido construido por el algoritmo siguiente:
Nodos: Para cada nodo del árbol de análisis n hacer:
Para cada atributo s asociado a Los símbolos del nodo n hacer:
Construir un nodo etiquetado con a.
Arcos: Para cada regla semántica b=f(e1,...,en) asociada con la producción del nodo n hacer:
Para i=1,..n Hacer: Trazar arcos desde ci a b.
Métodos de Evaluación de las Reglas Semánticas:
1. Árbol de análisis: para cada entrada se construye el árbol sintáctico (Grafos cíclicos).
2. Basado en las reglas semánticas: Dependiendo de las reglas semánticas (atributos heredados o sintetizados) se establece el orden de evaluación.
3. Dirigido por sintaxis: El orden de evaluación es impuesto por la estrategia de análisis.
Evaluación Ascendente
Gramáticas S-Atribuidas:
La estructura de la pila se adecua para que cada símbolo de la gramática disponga de sus atributos asociados.
La evaluación de los atributos se realiza cuando se REDUCE.
Gramáticas L-Atribuidas:
Sea la producción A->X1 X2 ...Xn. Una gramática es L-atribuida si todos los atributos Heredados asociados con Xj , 1 menorigual j menorigual n, sólo depende:
1. de los atributos asociados con los símbolos X1X2...Xj-1
2. de atributos asociados con A
Toda gramática l-atribuida puede ser evaluada mediante análisis ascendente.