Gramáticas Atribuidas

¿Qué es un Atributo?

Dentro del contexto de una gramática atribuida; un atributo es el campo asociado a un elemento, terminal o no terminal, el cual puede tomar un número infinito de valores.

Un elemento de una gramática puede contener un número finito de atributos; los cuales pueden representar cualquier cosa (un valor, un tipo de dato, una dirección de memoria, etc.…); los cuales sirven durante el proceso de análisis semántico para determinar que la cadena de entrada tiene sentido semántico; por ejemplo, que se pueda ejecutar una suma de dos o más valores del mismo tipo.

¿Qué son las Acciones Semánticas?

Una acción semántica es un fragmento de código asociado a una regla de producción de una gramática, el cual se ejecuta cuando se usa dicha regla en una derivación. Por lo general se usan para traducir las reglas de producción durante las derivaciones; pero también se utilizan para realizar otras acciones que se requiere que se ejecuten durante cada derivación; como la presentación de un error o un resultado.

Cada regla de producción puede tener una o varias acciones semánticas asociadas; lo cual obliga a tener mucho cuidado, debido a que cada vez que se utilice una determinada regla de producción, todas sus acciones semánticas asociadas se ejecutarán; esto puede conllevar a tener efectos colaterales. Para aclarar esta idea, obsérvese el siguiente ejemplo:

Para la cadena de entrada: x + (3 + 5)

REGLAS DE PRODUCCIÓN ACCIONES SEMÁNTICAS

E  F + T {E = F + T; printf(E);}

T  (E) {T = ( E );}

T  F {T = F;}

F  ID {F = ID;}

F  NUM {F = NUM;}

1) E Se coloca el axioma inicial.

2) F + T Se ejecuta la derivación y se presenta el valor de E

3) ID + T Se deriva F

4) ID + (E) Se deriva T

5) ID + (F + T) Se vuelve a presentar el valor del elemento E

6) etc.…

Como se vio en el ejemplo, la primera regla, que tenía dos acciones asociadas, se usó dos veces durante la derivación; lo cual produjo que se imprima dos veces el valor del elemento E.

Reglas sobre los Atributos

Existen tres reglas que rigen a la hora de usar atributos durante las acciones semánticas. Dichas reglas se indican a continuación con sus respectivos ejemplos:

• Un atributo sólo puede ser usado detrás del símbolo al que pertenece.

E.val à S.val {printf (S) ;}

• Un atributo del antecedente, puede ser usado en la acción semántica definida en el consecuente.

E.val à S.val {printf (E.val) ;}

• La acción semántica sólo puede utilizar los atributos de los terminales y no terminales que le anteceden.

E.val à C.val + D.val {E.val=C.val+D.val;} X.val

Tipos de Atributos

Atributos Sintetizados

Son aquellos que se calculan a partir de sus nodos hijo en el árbol de análisis sintáctico. Su cálculo se realiza a través de un recorrido ascendente del árbol sintáctico. Por ejemplo; considérese el siguiente fragmento de un árbol sintáctico:

E.val

F.val + T.val

NUM.val F.val

NUM.val

Los nodos terminales tienen un atributo .val; para almacenar el valor que se va a evaluar; dicho atributo, será sintetizado por los nodos F de cada rama y luego por el nodo T (en la rama derecha) y el nodo E. Si queremos evaluar la cadena de entrada: 3 + 5, El valor 3 será sintetizado en la rama izquierda del árbol y el valor 5 en la derecha; luego, estos valores serán pasados de nodo a nodo hasta llegar al nivel en el que se ejecuta la operación y se obtiene el resultado en el nodo E.

Atributos Heredados

Los atributos heredados son aquellos que se calculan a partir de los nodos padre y/o hermanos del árbol de análisis sintáctico. Son muy útiles a la hora de expresar la dependencia de una construcción de un lenguaje en el contexto en que ésta aparece.

A continuación se ejemplifica el cálculo de un atributo heredado (.type); el cual ha sido definido en la declaración “int x;”, y sirve para validar que los tipos de datos de la operación que se intenta ejecutar, sean compatibles:

E.type

ID.type = T.type

F.type + T.type

ID.type F.type

ID.type

Como se dijo anteriormente, el atributo del nodo terminal ID en la rama izquierda, fue declarado con el valor “int”; por lo que hará que éste valor sea heredado por el nodo no terminal T, que es su hermano, y éste a su vez, heredará éste valor a sus nodos hijos F y T. De ésta forma, si cualquiera de los nodos terminales ID del lado derecho del árbol de análisis sintáctico tiene un valor del atributo .type diferente de “int”, se detectará un error semántico.

Este tipo de atributos y observaciones, son resumidas en el siguiente tema.

Grafo de Dependencias

Se trata de un grafo dirigido que sirve para representar las interdependencias de los atributos de un árbol sintáctico. Para determinar dichas dependencias, tenemos que valernos de las reglas semánticas.

Para construir un grafo de dependencias, se tiene que tener en cuenta qué atributo depende de otro; pues se debe asegurar que el valor de un atributo esté disponible cuando sea invocado por otro. Además, una construcción del grafo de dependencias bien elaborada, nos permitirá obtener un buen orden de evaluación de las reglas semánticas.

Podemos citar como ejemplo de grafo de dependencias, el desarrollado anteriormente en el tema de los atributos heredados:

E.type

ID.type = T.type

(type = int) F.type + T.type

...