Transferencia de Valores #

Necesidad de Información #

A la hora de dar valor a los atributos de un nodo mediante las funciones semánticas, será habitual que se necesite información que provenga del padre o de los hijos de dicho nodo. Dado que las gramáticas atribuidas sólo disponen del concepto de atributo para contener información, hay que utilizar estos para transferir información entre los nodos del árbol.

En las gramáticas de capítulos anteriores, aunque no ha surgido el caso en el que se necesite información del padre, sí que han surgido casos en los que se ha necesitado información de los hijos.

• En la gramática usada como ejemplo de la aplicación de una gramática atribuida, aparecía la siguiente regla:

  Producción	Predicados	Funciones
  ...	...
  exp ⟶ exp1 '+' exp2		exp.val = exp1.val + exp2.val

  En dicha regla, para calcular el valor del atributo del padre (exp.val), se ha necesitado información que proviene de los hijos (exp₁.val y exp₂.val)

• En el ejemplo 620 se usaron los atributos menor y mayor de los hijos.

  Producción	Predicados	Funciones
  ...		...
  serie ⟶ serie1 ',' serie2	...	serie.menor = serie1.menor serie.mayor = serie2.mayor

En este capítulo se va a generalizar lo anterior y se va a mostrar cómo representar, a la hora de crear una gramática atribuida, el paso de información entre los nodos del árbol.

Atributos Heredados y Sintetizados #

Como ya se ha visto, en las reglas de una gramática atribuida sólo se puede acceder a los símbolos de la producción a la que están asociadas.

Por tanto, a la hora de definir una función semántica, es decir, de inicializar un atributo, sólo hay dos posibilidades:

• O se asigna a un atributo del símbolo antecedente de la regla (el padre del subárbol).
• O se asigna un atributo de un símbolo del consecuente (a un hijo).

a ⟶ b ...   [ a.val = ...]

a ⟶ b ...   [ b.val = ...]

Consecuencias:

• Cuando un atributo se asigna estando visitando el nodo al que pertenece dicho atributo (el caso de la columna izquierda de la tabla anterior), el efecto que se produce es que dicho valor se pasa de un hijo hacia su padre. Un atributo que se use para este efecto se denomina atributo sintetizado. Por tanto, se usan estos atributos cuando se quiere que la información fluya hacia arriba en el árbol.
• Cuando un atributo se asigna estando visitando el padre del nodo al que pertenece dicho atributo (el caso de la columna derecha de la tabla anterior), el efecto que se produce es que su valor pase del padre hacia el hijo. Un atributo que se use para conseguir este efecto se denomina atributo heredado (el nodo hijo recibe o hereda el valor de su padre). Se usan estos atributos cuando se quiere que la información fluya hacia abajo en el árbol.

Ambos tipos de atributos son fáciles de distinguir en una traza de aplicación de una gramática atribuida a una entrada. Como puede verse en el dibujo siguiente:

• Los atributos sintetizados se inicializan cuando se está visitando el propio nodo al que pertenece el atributo (el nº de paso ❶ está en el mismo nodo que el atributo val).
• Los atributos heredados se inicializan cuando se está visitando el padre del nodo al que pertenece el atributo (el nº de paso ❶ y el atributo val están en distintos nodos).

Para comparar ambos tipos de atributos, supóngase que un símbolo b tiene un atributo de cada tipo: un atributo sintetizado s y uno heredado h. En la siguiente tabla se resumen sus diferencias.

a ⟶ b ...
b ⟶ ...     [ b.s = ...]

a ⟶ b ...   [ b.h = ...]
b ⟶ ...

visita(a) {
    visita(b)
    // Aquí se usa 'b.s'
    ... = b.s ...
}

visita(b) {
    // Aquí se inicializa 'b.s'
    b.s = ...
}

visita(a) {
    // Aquí se inicializa 'b.h'
    b.h = ...
    visita(b)
}

visita(b) {
    // Aquí se usa 'b.h'
    ... = b.h ...
}

El resumen de todo este apartado, y la conclusión que debe quedar, es que, a la hora de hacer una gramática atribuida:

• cuando se quiera pasar un valor de un padre a a un hijo b, hay que crear un atributo en el hijo b que se inicialice en el padre a (atributo heredado).
• cuando se quiera pasar un valor de un hijo b a un padre a, hay que crear un atributo en el hijo b que se inicialice en el propio nodo b (atributo sintetizado).

Otras Transferencias de Valores #

Se ha visto sólo como pasar información en un árbol entre un padre y sus hijos inmediatos (atributos sintetizados o heredados dependiendo de la dirección). Las gramáticas atribuidas sólo permiten estas dos formas de comunicación. El motivo, como ya se comentó anteriormente, es que en una regla sólo se pueden usar símbolos de su producción y, por tanto, no se tiene acceso a los símbolos de los nietos, abuelos o hermanos del nodo.

Sin embargo, se puede conseguir pasar información entre nodos que no sean padre/hijo directos.

Entre Abuelos y Nietos #

Para pasar información entre abuelos y nietos, habría que pasar la información por todos los niveles intermedios (utilizando en éstos funciones semánticas que reenvíen la información de un nivel al siguiente). Por tanto, todo nodo entre ellos tendrán que tener el atributo a propagar, que será heredado o sintetizado en función de la dirección en la que se quiera transferir la información.

Supóngase que se quiere pasar un valor desde un nodo a hasta un nieto c, concretamente se quiere pasar el valor 5. El nodo c necesita dicho valor para hacer una operación f() con él (lo que haga dicha función con el valor no es relevante).

Para ello, dado que se quiere pasar información hacia abajo, se crearía un atributo heredado en c al que se le llamará val. Pero este atributo también habría que añadirlo en el nodo intermedio b para poder propagar el valor.

Por último, habría que añadir las funciones semánticas que realicen la propagación de los valores entre dichos atributos.

Si se quisiera hacer el proceso inverso, es decir, pasar información de nieto a abuelo, simplemente habría que cambiar la dirección del flujo de información utilizando atributos sintetizados.

Entre Hermanos #

Para pasar información entre nodos hermanos, habría que usar al padre de intermediario. Este cogería el valor a transmitir de un atributo sintetizado del hermano emisor y lo asignaría a un atributo heredado del hijo receptor. En el siguiente ejemplo se muestra cómo se pasaría el valor 5 del nodo b a su hermano c.

Tabla de Atributos

Tabla de Reglas Semánticas

Recuérdese que, a la hora de seguir estos ejemplos, las reglas hay que aplicarlas en el orden adecuado para que los atributos estén ya inicializados cuando se usen (orden topológico). Por tanto, en este caso hay que aplicar primero la regla del nodo b y luego la de a. En caso contrario, en a se estaría cogiendo el valor de un atributo sin inicializar.

Si se hubiera querido pasar información en el sentido opuesto, del nodo c al b, las funciones semánticas hubieran sido las siguientes y también habría cambiado el orden de recorrido del árbol.