UNIDAD V.- Traducción dirigida por la sintaxis.

5.1.- Traducción o definición dirigida por sintaxis.

Una definición dirigida por sintaxis es una gramática de contexto libre en la que cada símbolo gramatical (terminales y no terminales) tiene un conjunto de atributos asociados, dividido en dos subconjuntos llamados atributos sintetizados y atributos heredados de dicho símbolo gramatical.

Un atributo puede representar cualquier cosa. El valor de un atributo en un nodo de un árbol de análisis sintáctico se define mediante una regla semántica asociada a la regla de producción utilizada en dicho nodo. El valor de un atributo sintetizado de un nodo se calcula a partir de los valores de los atributos hijos de dicho nodo en el árbol de análisis sintáctico; el valor de un atributo heredado se calcula a partir de los valores de los atributos en los hermanos y el padre de dicho nodo.

Las reglas semánticas establecen las dependencias entre los atributos que serán representadas mediante un grafo. Del grafo de dependencias se obtiene un orden de evaluación de las reglas semánticas. La evaluación de las reglas semánticas define los valores de los atributos en los nodos del árbol de análisis sintáctico para la cadena de entrada.

5.2.-Forma de una traducción dirigida por sintaxis.

En una definición dirigida por sintaxis, cada regla de producción A Ú . tiene asociado un conjunto de reglas semánticas de la forma b:=f(c1, c2, ..., ck), donde f es una función, y, o bien

1. b es un atributo sintetizado de A y c1, c2, ..., ck son atributos de los símbolos de ., o

Bien

2. b es un atributo heredado de uno de los símbolos de . , y c1, c2, ..., ck son atributos de los restantes símbolos de . o bien de A.

En cualquier caso, se dice que el atributo b depende de los atributos c1, c2, ..., ck.

Una gramática con atributos es una definición dirigida por sintaxis en la que las funciones en las reglas semánticas no pueden tener efectos colaterales.

En una definición dirigida por sintaxis, se asume que los terminales sólo tienen atributos sintetizados, ya que la definición no proporciona ninguna regla semántica para los terminales. 

El analizador léxico es el que proporciona generalmente los valores de los atributos de los terminales. Además se asume que el símbolo inicial no tiene ningún atributo heredado, a menos que se indique lo contrario.

5.3.- Atributos sintetizados.

Los atributos sintetizados son muy utilizados en la práctica. Una definición dirigida por sintaxis que usa atributos sintetizados exclusivamente se denomina definición con atributos sintetizados. Siempre se puede anotar un árbol de análisis sintáctico para una definición con atributos sintetizados mediante la evaluación de las reglas semánticas para los atributos en cada nodo de forma ascendente, de las hojas a la raíz.

5.4.- Atributos heredados.

Un atributo heredado es uno cuyo valor en un nodo de un árbol de análisis sintáctico está definido a partir de los atributos en el padre y/o de los hermanos de dicho nodo. Los atributos heredados sirven para expresar la dependencia de una construcción de un lenguaje de programación en el contexto en el que aparece.

5.5.- Grafo de dependencias y evaluación de orden.

Las interdependencias entre los atributos heredados y sintetizados en los nodos de un árbol de análisis sintáctico se pueden representar mediante un grafo dirigido llamado grafo de dependencias. El grafo de dependencias se construye como se indica más arriba. A partir de un ordenamiento topológico del grafo de dependencias, se obtiene un orden de evaluación para las reglas semánticas. La evaluación de las reglas semánticas en este orden produce la traducción de la cadena de entrada.

5.6.- Gramática L-atribuida.

También llamada atribuida por la izquierda, o definición con atributos por la izquierda.  En toda regla A Ú X1 X2 ... Xn, cada atributo heredado de Xj 1 j n depende sólo de:

1. Los atributos (sintetizados o heredados) de los símbolos X1 X2 ... Xj-1.

2. Los atributos heredados de A.

Este tipo de gramáticas no producen ciclos y además admiten un orden de evaluación en profundidad.

5.7.- Gramática S-atribuida.

Es una gramática atribuida que sólo contiene atributos sintetizados Una gramática S- atribuida es también L-atribuida. Los atributos sintetizados se pueden evaluar con un analizador sintáctico ascendente conforme la entrada es analizada.