Tabla de Reglas #

En este capítulo se verá cómo implementar la tabla de reglas.

Implementar esta tabla consiste en crear un código que recorra el árbol y aplique las reglas semánticas correspondientes a cada nodo que vaya visitando.

Recorrido de un Árbol #

En esta asignatura, para recorrer el árbol, se usará el patrón Visitor.

Aplicando el patrón Visitor, habría un método visit por cada nodo del árbol. Un método visit tiene como parámetro el nodo que se está visitando en ese momento. Y dicho nodo tendría como atributos a sus hijos y a aquellos atributos que se hayan añadido en la gramática atribuída.

a ⟶ b c ...

visit(NodeA a) {
    // Usar 'a.b' y 'a.c' para acceder a los hijos
    ...
}

Ahora quedaría por determinar cuál es la implementación de cada uno de esos métodos visit.

Implementación de un visit #

Cada fila de la tabla de reglas se corresponde con un método visit del visitor. Y el contenido de las columnas de dicha fila dicta cómo debe implementarse éste.

La estructura de cada método visit deberá seguir el siguiente patrón de recorrido postorden.

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

Obviamente, habrá que saltarse los pasos no aplicables como, por ejemplo, la asignación de atributos heredados en los hijos que no los tengan o comprobar los predicados si el nodo no tiene.

Por ejemplo, supóngase la siguiente tabla:

La implementación sería:

visit(NodeA a) {

    // Asignar atributos heredados y visitar el primer hijo
    a.b.val = ...
    a.b.accept(this);

    // Asignar atributos heredados y visitar el segundo hijo
    a.c.val = ...
    a.c.accept(this);

    // Comprobar predicados del nodo actual
    predicado(<p1>)

    // Asignar atributos sintetizados del nodo actual
    a.val = ...
}

Nótese cómo las funciones semánticas (las tres asignaciones), se implementan en distinto sitio en función de que sean asignaciones a atributos heredados o sintetizados.

Quedaría por explicar qué es la sentencia predicado(<p1>) que se ha usado para implementar el predicado. A la hora de implementar un predicado, hay que comprobar que se cumpla (es decir, que sea true). En caso contrario, hay que notificar un error semántico. Esto, normalmente, se implementaría con un if.

visit(NodeA a) {
    ...
    if(! <p1>)
        error()
    ...
}

El if anterior será tan común que se aconseja tener un método auxiliar llamado, por ejemplo, predicado, para simplificar la implementación de los visit y centralizar la gestión de errores. Por eso el predicado se implementará de esa manera.

visit(NodeA a) {
    ...
    predicado(<p1>)
    ...
}

// --- Método auxiliar
private void predicado(bool condicion) {
    if (! condicion)
        error();
}

Para acabar este capítulo, cabe recordar que, a la hora de aplicar una gramática atribuida, el objetivo era lograr un orden topológico (que ninguna regla use un atributo antes de que se haya inicializado). Por tanto, el anterior patrón postorden, para que fuera útil, debería generar un código que, al ejecutarse, siga un orden topológico. Y sin embargo... no es así.

El patrón postorden no es una solución universal para implementar cualquier gramática atribuida. De hecho, sólo produce un orden topológico con gramáticas que tengan unas características, las gramáticas L-atribuidas. Antes de usar este patrón hay que asegurarse que la gramática a implementar es de este tipo. En el capítulo siguiente se verá cómo son estas gramáticas y qué opciones se tienen si la gramática a implementar no lo es.