Especificación de Semántica #

Como se ha adelantado en el capítulo anterior, hay que comprobar si los nodos del árbol cumplen unas determinadas reglas para saber si es válido. Pero, previamente, estas reglas deben estar especificadas con alguna notación. En este capítulo se verá cómo es esta notación y cómo se aplican las reglas para realizar la validación de un árbol.

Gramáticas Atribuidas #

La notación que se usará en esta asignatura será el metalenguaje denominado gramática atribuida (también llamada gramática con atributos). Como metalenguaje que es, nos ofrece precisión y concisión. Además de esto, otra ventaja de los metalenguajes es la independencia del lenguaje de programación que vaya a ser usado en la implementación de las reglas. Las reglas que debe cumplir una entrada no dependen de en qué lenguaje se implemente el analizador semántico.

Hay que destacar, por último, que las gramáticas atribuidas, aunque sí que se crearon para este propósito, no son útiles solamente en el contexto de construir un compilador. Se pueden usar como técnica más general en cualquier aplicación que tenga datos en forma de árbol o grafo y se quiera comprobar si cumple unas determinadas reglas o simplemente añadirle más información. Con una gramática atribuida, se obtendría, de una sola vez, tanto la documentación como la implementación de dicho proceso.

Componentes de una Gramática Atribuida #

Una gramática atribuida no es más que una extensión de una gramática libre de contexto o de una gramática abstracta. Es decir, consiste en coger una de estas gramáticas y complementarla con:

• Atributos (de ahí viene el nombre de gramática atribuida). Son la información adicional que se necesite añadir a ciertos nodos del árbol.
• Reglas semánticas. Las cuales, en ciertas ocasiones, es útil dividirlas en predicados y funciones semánticas. Nótese que cuando en este texto se hable de reglas en general, se estará refiriendo a ambos tipos de reglas.

Estas dos incorporaciones a la gramática se representará en estos apuntes mediante una tabla para cada una. Por tanto, en este texto, una especificación semántica mediante una gramática atribuida se presentará como un documento formado por dos tablas: la tabla de atributos y la tabla de reglas semánticas.

La tabla de reglas semánticas no es más que el resultado de poner en forma tabular lo que en el tema inicial se representaba de forma gráfica. En cada fila se pone un nodo y, en la misma fila, las reglas que tiene asociadas.

En los siguientes apartados se verá el detalle del contenido de cada una de las dos tablas.

Predicados #

Una gramática abstracta, tal y como se vio en el tema anterior, es la forma de definir cada símbolo del árbol junto con el tipo de sus hijos.

suma ⟶ expr expr

El tipo de los hijos (expr) ya supone una restricción sobre qué nodos se pueden conectar como hijos de suma. Se sabe que no se va a encontrar, por ejemplo, que uno de los hijos sea un nodo print, ya que no es una expresión.

Sin embargo, esta primera barrera que suponen los tipos de los hijos, aunque necesaria, no es suficiente en muchos casos. Por ejemplo, una suma de dos variables (nodos var) cumpliría el requisito de que los hijos sean expresiones. Sin embargo, si una de ellas fuera un array y la otra una struct, aunque sean hijos del tipo adecuado, no debería ser válido.

Para estos casos es para lo que se usan los predicados. Estas son las condiciones adicionales que debe cumplir un nodo y/o sus hijos para ser válido. Basta que un sólo predicado de cualquier nodo no se cumpla para que el árbol sea rechazado.

Para ejemplificar la necesidad de los atributos, supóngase un lenguaje para la definición de rangos definidos mediante constantes enteras. Se tiene como requisito que el valor de la izquierda debe ser menor o igual que el de la derecha.

[1 — 10]

La sintaxis en una GLC sería la siguiente:

Sin embargo, sólo con dicha gramática libre de contexto, se admitirían como válidas entradas en las que el número de la izquierda fuera mayor que el de la derecha.

Para detectar esta situación errónea, se complementa la gramática con predicados, transformándola así en una gramática atribuida. Los predicados se ponen en la tabla de reglas en la misma fila de la producción a la que están asociados.

El que haya un predicado en la fila de una producción indica que el subárbol al que representa dicha producción sólo será válido si dicho predicado se evalúa a true. Nótese que se han añadido subíndices a los NUM para diferenciar a qué hijos se está refiriendo en cada momento.

En resumen, una gramática atribuida que en la tabla de reglas tuviera la columna de los predicados vacía indicaría que cualquier árbol que salga del analizador sintáctico es semánticamente válido. A medida que se van añadiendo predicados, se van filtrando y reduciendo el número de árboles que serían válidos semánticamente. La misión del escritor de una gramática es poner suficientes predicados para que sólo salgan del analizador semántico los árboles válidos.

Atributos #

En el ejemplo anterior, dada su simplicidad, no hubo que añadir más información al árbol para poder validarlo. Sin embargo, suele ser habitual que los predicados requieran que los nodos tengan alguna información adicional a la que salió del sintáctico. Esta información que se necesite añadir es lo que se llaman atributos. Por tanto, los atributos surgen de las necesidades de las reglas y puede que haya que añadirlos o quitarlos en función de los cambios en las mismas.

Los atributos que hay que añadir a un árbol se expresan mediante la tabla de atributos, una tabla de tres columnas en las que se indica a qué nodo hay que añadirle un atributo, cómo se llamará y de qué tipo será (aunque aquí, en realidad, se está adelantando la implementación y, a nivel de especificación, esta tercera columna se podría omitir).

Viéndolo desde el punto de vista de la implementación, la tabla anterior puede interpretarse como los atributos que hay que añadir a las clases que implementen los nodos indicados. Por ejemplo, según la primera fila, habría que añadir un atributo llamado val de tipo int a la clase S.

Para ver la necesidad de los atributos, supóngase ahora que se extiende el lenguaje anterior de definición de rangos para que las expresiones puedan incluir sumas y multiplicaciones de constantes. Seguiría siendo requisito que el límite inferior del rango sea menor que el superior.

[10+20 — 3*40]

La sintaxis, ahora, sería la siguiente:

Y el árbol concreto de la entrada anterior sería:

Con esta sintaxis ya no se podría poner el predicado del apartado anterior, ya que en la regla rango ya sólo se tiene acceso a los símbolos que la componen (rango y los dos hijos expr) pero no al valor de los NUM, ya que están varios niveles por debajo (una regla sólo tiene acceso a sus hijos inmediatos).

Para poder comparar los dos nodos expr del rango, se necesitaría que éstos nodos tuvieran más información, concretamente, su valor. Para indicar que hay que añadir esta información al árbol, se crea la siguiente tabla de atributos.

Esta tabla indica que hay que añadir un atributo val de tipo int en cada expresión. El árbol, después de añadir dicho atributo a los nodos expr, quedaría así:

Nótese que se ha añadido el atributo a los nodos indicados, pero todavía está sin inicializar (en breve lo harán las funciones semánticas).

Ahora, dado que ya se cuenta con que todo nodo expr tiene un atributo val que contendrá su valor, se puede hacer un predicado que compruebe el valor de este atributo.

Nótese cómo es la sintaxis para acceder a un atributo. Hay que poner siempre primero el nombre del símbolo que tiene el atributo al que se quiere acceder y luego el nombre del mismo:

<nodo>.<atributo>

No se puede acceder a un atributo sin especificar delante el nodo al que pertenece.

Funciones Semánticas #

Una vez que se ha identificado la información que se necesita añadir al árbol (los atributos), queda ahora indicar qué valor van a tomar los mismos — cómo se van a inicializar en cada nodo. Ese valor es el que muestra las funciones semánticas.

En el ejemplo anterior se añadió un atributo val. Hay que añadir ahora las funciones semánticas que inicialicen dicho atributo en todo nodo que lo contenga. Para ello, se añade una tercera columna a la tabla de reglas de la gramática.

Con todo esto, ya se tendría la especificación semántica del lenguaje acabada, es decir, las dos tablas de su gramática atribuida. Ahora sólo quedaría ver cómo se aplican a una entrada para validarla. Eso es lo que se verá en el siguiente capítulo.