Definición Dirigida por la Sintáxis

Una definición dirigida por la sintáxis es un pariente cercano de los esquemas de traducción. En una definición dirigida por la sintáxis una gramática $G = (V, \Sigma, P, S)$ se aumenta con nuevas características:

• A cada símbolo $S \in V \cup \Sigma$ de la gramática se le asocian cero o mas atributos. Un atributo queda caracterizado por un identificador o nombre y un tipo o clase. A este nivel son atributos formales, como los parámetros formales, en el sentido de que su realización se produce cuando el nodo del árbol es creado.
• A cada regla de producción $A \rightarrow X_1 X_2 \ldots X_n \in P$ se le asocian un conjunto de reglas de evaluación de los atributos o reglas semánticas que indican que el atributo en la parte izquierda de la regla semántica depende de los atributos que aparecen en la parte derecha de la regla. El atributo que aparece en la parte izquierda de la regla semántica puede estar asociado con un símbolo en la parte derecha de la regla de producción.
• Los atributos de cada símbolo de la gramática $X \in V \cup \Sigma$ se dividen en dos grupos disjuntos: atributos sintetizados y atributos heredados. Un atributo de $X$ es un atributo heredado si depende de atributos de su padre y hermános en el árbol. Un atributo sintetizado es aquél tal que el valor del atributo depende de los valores de los atributos de los hijos, es decir en tal caso $X$ ha de ser una variable sintáctica y los atributos en la parte derecha de la regla semántica deben ser atributos de símbolos en la parte derecha de la regla de producción asociada.
• Los atributos predefinidos se denominán atributos intrínsecos. Ejemplos de atributos intrínsecos son los atributos sintetizados de los terminales, los cuáles se han computado durante la fase de análisis léxico. También son atributos intrínsecos los atributos heredados del símbolo de arranque, los cuales son pasados como parámetros al comienzo de la computación.

La diferencia principal con un esquema de traducción está en que no se especifica el orden de ejecución de las reglas semánticas. Se asume que, bien de forma manual o automática, se resolverán las dependencias existentes entre los atributos determinadas por la aplicación de las reglas semánticas, de manera que serán evaluados primero aquellos atributos que no dependen de ningún otro, despues los que dependen de estos, etc. siguiendo un esquema de ejecución que viene guiado por las dependencias existentes entre los datos.

Aunque hay muchas formas de realizar un evaluador de una definición dirigida por la sintáxis, conceptualmente, tal evaluador debe:

1. Construir el árbol de análisis sintáctico para la gramática y la entrada dadas.
2. Analizar las reglas semánticas para determinar los atributos, su clase y las dependencias entre los mismos.
3. Construir el grafo de dependencias de los atributos, el cual tiene un nodo para cada ocurrencia de un atributo en el árbol de análisis sintáctico etiquetado con dicho atributo. El grafo tiene una arista entre dos nodos si existe una dependencia entre los dos atributos a través de alguna regla semántica.
4. Supuesto que el grafo de dependencias determina un orden parcial (esto es cumple las propiedades reflexiva, antisimétrica y transitiva) construir un orden topológico compatible con el orden parcial.
5. Evaluar las reglas semánticas de acuerdo con el orden topológico.

Una definición dirigida por la sintáxis en la que las reglas semánticas no tienen efectos laterales se denomina una gramática atribuída.

Si la definición dirigida por la sintáxis puede ser realizada mediante un esquema de traducción se dice que es L-atribuída. Para que una definición dirigida por la sintáxis sea L-atribuída deben cumplirse que cualquiera que sea la regla de producción $A \rightarrow X_1 \ldots X_n$, los atributos heredados de $X_j$ pueden depender únicamente de:

1. Los atributos de los símbolos a la izquierda de $X_j$
2. Los atributos heredados de $A$

Nótese que las restricciones se refieren a los atributos heredados. El cálculo de los atributos sintetizados no supone problema para un esquema de traducción. Si la gramática es LL(1), resulta fácil realizar una definición L-atribuída en un analizador descendente recursivo predictivo.

Si la definición dirigida por la sintáxis sólo utiliza atributos sintetizados se denomina S-atribuída. Una definición S-atribuída puede ser fácilmente trasladada a un programa jison.

Ejercicio 5.17.1   El siguiente es un ejemplo de definición dirigida por la sintáxis:

S $\rightarrow$ a A C	$C{i} = $A{s}
S $\rightarrow$ b A B C	$C{i} = $A{s}
C $\rightarrow$ c	$C{s} = $C{i}
A $\rightarrow$ a	$A{s} = "a"
B $\rightarrow$ b	$B{s} = "b"

Determine un orden correcto de evaluación de la anterior definición dirigida por la sintáxis para la entrada b a b c.

Ejercicio 5.17.2   Lea el artículo Are Attribute Grammars used in Industry? por Josef Grosch

I am observing a lack of education and knowledge about compiler construction in industry. When I am asking the participants of our trainings or the employees we met in our projects then only few people have learned about compiler construction during their education. For many of them compiler construction has a bad reputation because of what and how they have learned about this topic. Even fewer people have a usable knowledge about compilers. Even fewer people know about the theory of attribute grammars. And even fewer people know how to use attribute grammars for solving practical problems. Nevertheless, attribute grammars are used in industry. However, in many cases the people in industry do not know about this fact. They are running prefabricated subsystems constructed by external companies such as ours. These subsystems are for example parsers which use attribute grammar technology.