Ejemplo 630 #

Objetivo #

El objetivo de este ejemplo es mostrar una gramática atribuida con atributos heredados y cómo se aplican para reconocer una entrada.

Además, las gramáticas atribuidas pueden usarse para ampliar tanto gramáticas libres de contexto como gramáticas abstractas, es decir, se pueden aplicar tanto a árboles concretos como a árboles abstractos. En este ejercicio, con objetivo meramente didáctico (ya que no sería necesario hacer las dos versiones), se hará la gramática atribuida a partir de una gramática libre de contexto. En el ejemplo del capítulo siguiente se mostrará cómo se haría una especificación del mismo lenguaje sobre una gramática abstracta.

Enunciado #

Sea un lenguaje de definición de conjuntos de números enteros o reales que permita entradas como las siguientes:

int v = { 3, 24, 12 }

float v = { 3.0, 6.5—14.8, 12.2 }

int v = { 40—12, 221, 510—210 }

Normas:

• Un conjunto debe tener al menos un elemento.
• Los elementos del conjunto deben de ser todos del mismo tipo (el cual se indica antes del nombre del conjunto).
• Los elementos del conjunto pueden indicarse individualmente o mediante rangos de números.
• En el caso de los rangos:
  • Los dos límites del rango deben ser del tipo indicado en el conjunto.
  • No es necesario que el límite inferior sea menor que el superior. Se admiten rangos con los límites intercambiados (se asume que el rango 7-3 es equivalente al 3-7).
• Puede haber valores duplicados. Puede ponerse varias veces el mismo número o que aparezca individualmente un número que forme parte de algún rango definido.

Ejemplos de entradas inválidas serían:

int v = { 3, 24.5, 12 }         // Error: el segundo valor no es entero

float v = { 3.6, 14—6.5 }       // Error: el 14 no es un real

Se pide:

• Crear una especificación semántica mediante una gramática atribuida.

• Hacer la traza de la aplicación de la gramática atribuida a la siguiente entrada:

  int v = { 2, 4—8 }
  

Solución #

Especificación #

La GLC que expresaría la sintaxis del lenguaje anterior sería:

conjunto ⟶ tipo IDENT '=' '{' lista '}'

tipo ⟶ INT | FLOAT

lista ⟶ elemento | lista ',' elemento       // 1+cs

elemento ⟶ num | num '—' num

num ⟶ LITENT | LITREAL

Son todas construcciones secuencia, excepto lista, que es una lista 1+cs.

Para comprobar que todos los números son del tipo adecuado, se va a seguir la siguiente estrategia:

• El símbolo conjunto recibirá de su hijo tipo el tipo del que tienen que ser sus elementos. Por tanto, dado que se pasa información de un hijo a un padre, se añade a tipo un atributo sintetizado llamado val. En este ejemplo tan sencillo, para indicar el tipo, se usará un carácter con el valor 'i' o 'f' para indicar si es int o float respectivamente.
• Una vez hecho lo anterior, desde el símbolo conjunto se pasará el tipo a todos los número para que éstos puedan comprobar si son de dicho tipo. Por tanto, como se necesita pasar información del padre a los hijos (concretamente de abuelos a nietos), se usará un atributo heredado llamado tipo. Este atributo no habrá que añadírselo sólo al número, sino también a todos los símbolos intermedios en el árbol por los que tiene que pasar hasta llegar a éstos (lista y elemento).

Por tanto, los atributos necesarios para llevar a cabo la anterior se describen en la siguiente tabla de atributos:

Una vez con esa información en los nodos del árbol concreto, se puede hacer la tabla de reglas.

Nótese que toda esta transferencia de valores es para que al final los num puedan, en sus predicados, comprobar que el tipo del conjunto se corresponde con el tipo de constante que son (LITENT_o_LITREAL).

Traza de la Aplicación #

Una vez ya hecha la especificación, ya se podría aplicar a la entrada. Para ello, habría que construir su árbol. Dado que la gramática atribuida anterior se basa en una gramática libre de contexto, éste será un árbol concreto. La siguiente imagen muestra el árbol resultante y la traza del proceso de aplicación de la gramática atribuida.

Como todos los predicados se evalúan a true, la entrada es semánticamente correcta.

Nótese en la traza anterior cómo se diferencian los atributos heredados del sintetizado por el nodo que se está visitando en el momento de su asignación (el propio nodo del atributo o el padre). Nótese por ejemplo:

• En el paso 1, la función f2 asigna valor al atributo val del nodo tipo. Como cuando se asigna valor al atributo se está visitando dicho nodo, es un atributo sintetizado.
• En el paso 2, la función f1 asigna valor al atributo tipo del nodo lista. Como cuando se asigna valor al atributo se está visitando el nodo padre, es un atributo heredado.