Gramáticas L-Atribuidas #

Limitaciones del Patrón Postorden #

Supóngase que se quiere implementar la siguiente gramática atribuida:

Se procede ahora a implementarla usando el patrón postorden visto en el capítulo anterior.

visit(Node <n>) {

    Para cada hijo de <n>, de izquierda a derecha {
        Asignar los atributos heredados del hijo actual.
        Visitar el hijo.
    }

    Comprobar los predicados de nodo <n>.
    Asignar los atributos sintetizados del nodo <n>.
}

Siguiendo dicho patrón, la implementación de los nodos a, b y c sería:

visitA(NodeA a) {
    a.b.valor = a.c.valor + 1;   // 'c.valor' está aún sin inicializar!!
    a.b.accept()
    a.c.accept()    // Aquí es donde se inicializa 'c.valor'
}

visit(NodeC c) {
    c.valor = 5
}

Como puede verse, dado que la visita al nodo c (a.c.accept()) se ejecuta después que la asignación a.b.valor = a.c.valor + 1, el atributo b.valor quedará con un valor inválido (ya que dicha visita es la que inicializa c.valor).

Por tanto, esta gramática no es apta para ser implementanda por el patrón, ya que, para ella, no ha generado código que siga un orden topológico a la hora de aplicar las reglas (se usan atributos antes de su inicialización).

Gramáticas L-Atribuidas #

El problema de la gramática anterior es que se tenía que inicializar un atributo heredado (b.h) a partir de un atributo sintetizado de un hermano c que estaba a su derecha. Y, dado que los hijos se recorren de izquierda a derecha, dicho nodo no había sido visitado aún. Y esta es la única situación que, si se da, hace que no se puede usar el patrón postorden. Éste se debe usar sólo con gramáticas que no tengan esta situación, es decir, con gramáticas L-atribuidas.

Es decir, una gramática no sería L-atribuida si tuviera alguna regla con la siguiente forma:

Donde:

• h es un atributo heredado de n_i.
• s es un atributo sintetizado de n_j.
• i es menor o igual que j (es decir, n_i aparece en la regla antes que n_j o bien son el mismo símbolo).
• f es una función cualquiera que representa el cálculo de un valor a partir de n_j.s.

Si la gramática no tiene reglas con esa forma, entonces es L-atribuida y, por tanto, al aplicar sobre ella el patrón postorden se tiene garantizado que la implementación obtenida seguirá un orden topológico.

Gramáticas S-Atribuidas #

Otro tipo de gramática atribuida común son las S-atribuidas.

Estas gramáticas se caracterizarán porque el flujo de información, dado que sólo hay sintetizados, siempre será de abajo hacia arriba en el árbol (de los hijos a los padres).

Se da la circunstancia que toda gramática S-atribuida es L-atribuida. Es fácil ver la relación de inclusión entre los dos tipos de gramáticas. Una gramática es L-atribuida si no presenta la situación de que un atributo heredado se asigne en función de un sintetizado de su derecha. Dado que las gramáticas S-atribuidas no tiene atributos heredados, es imposible que se presente esta situación y, por tanto, cumplen la condición de L-atribuida.

La conclusión es que si se tiene una gramática en la que todos los atributos son sintetizados, se puede implemementar con el patrón postorden.

Gramáticas No L-Atribuidas #

El que una gramática atribuida sea L-atribuida, en la práctica, no es algo que sea difícil de conseguir si las reglas del lenguaje no son especialmente complicadas. Y, por tanto, para todas esas gramáticas, se tiene solucionada su implementación con el patrón postorden.

Sin embargo, cabe plantearse qué ocurre cuando se haya creado una gramática que no sea L-atribuida. En ese caso, básicamente se tienen dos soluciones:

• Buscar un orden topológico a medida para dicha gramática. Para ello, habría que construir un grafo de dependencias entre atributos e implementar un recorrido de los hijos que respete las restricciones que estas presentan. Esto, en ciertos casos, puede suponer que haya que recorrer más de una vez todo o ciertas partes del árbol.
• Dividir la gramática en dos o más gramáticas de tal manera que cada una de ellas sí sea L-atribuida y, por tanto, se puedan implementar con el patrón. Cada gramática será un recorrido independiente del árbol.