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:

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 yapp.

Casiano Rodríguez León
2013-04-23