Notación de las Gramáticas Atribuidas #

Las gramáticas atribuidas, en su definición básica, sólo incluyen asignaciones para definir las reglas semánticas (de hecho, no diferencian entre predicados y funciones). Esto las hace insuficientes en la práctica, por lo que en distintos textos se añaden variaciones de la notación a usar en las reglas. En este capítulo se mostrará la notación que se utilizará en estos apuntes.

Cabe decir que otra forma de expresar las reglas sería usar directamente un lenguaje de programación (por ejemplo Java). Sin embargo, se recomienda recurrir a esto como última opción y preservar así el objetivo de que una gramática atribuida sea independiente del lenguaje de programación. Aún así, habrá casos, y en estos apuntes se verá uno, en el que la notación no es suficiente y se tendrá que utilizar Java. Sin embargo, que esto sea necesario en casos puntuales no implica que no sea más compacto y sencillo usar la notación siguiente siempre que sea posible.

Notación de las Reglas #

Símbolos accesibles en las Reglas #

En una regla semántica sólo se pueden usar los símbolos de la producción a la que está asociada, es decir, no se pueden usar otros símbolos de la gramática que no estén en dicha regla.

Por ejemplo, en las reglas de la producción a ⟶ b c no se puede usar el símbolo d, ya que no forma parte de la misma.

Pseudocódigo #

Será habitual que, en función del contexto del subárbol, haya que aplicar unas reglas u otras a un mismo nodo. Para determinar las reglas a utilizar, se puede utilizar sentencias si y si no (o, si se prefiere en inglés, if y else).

Funciones Auxiliares #

Si una regla compleja se tiene que repetir en varias partes de la gramática, se puede sacar a una función auxiliar que se invoque desde dichas partes. La notación de esta función auxiliar debe ser la misma que se usaría en la gramática.

Por ejemplo, supóngase que se quiere sacar la regla anterior a una función auxiliar:

Entonces, se definiría debajo de la gramática la función mayor:

mayor(tipo1, tipo2) {
    si tipo1 == 'i' AND tipo2 == 'i'
        mayor = 'i'
    si no
        mayor = 'f'
}

Esta posibilidad de sacar reglas a funciones auxiliares debe reservarse únicamente para reglas no triviales y que se usen en varios sitios. En caso contrario, el abusar de esta característica dificulta la lectura de la gramática al sacar fuera de ella las reglas.

Conjuntos #

En las reglas se pueden usar conjuntos definidos en la propia regla junto con sus operaciones habituales: ∈, ∉, ⊂, ⊄, ∪ y ∩. Esto es especialmente útil para comprobar si una expresión toma uno de entre varios valores posibles.

Otra forma de hacer lo anterior, quizás un poco forzado para mostrar otro ejemplo, podría ser:

Y, si un conjunto se va a usar varias veces, puede sacarse fuera de la gramática como en el caso de las funciones auxiliares.

Donde dicho conjunto TiposSimples se define aparte como:

TiposSimples = { int, real, char }

Otros Operadores #

También puede ser útil utilizar otros operadores habituales.

Hijos Multivaluados #

En las gramáticas abstractas podía indicarse que un nodo podía tener una lista de hijos del mismo tipo mediante el operador *. Por ejemplo, la siguiente producción indica que una estructura tiene un nombre y varios campos.

Cuando en una regla hay hijos múltiples es útil usar una notación específica para ellos. En todos los siguientes ejemplos, se supone que se están refiriendo a reglas asociadas a defStruct (reglas en la primera fila de la tabla anterior).

• |campo| devolverá el número de hijos que tiene la lista (de manera independiente del lenguaje de programación).
• campo₀ devolverá el primer elemento de la lista, es decir, el nodo del primer campo de la estructura.
• campo_i se referirá a todos los elementos de la lista. Es una forma más compacta que un for para indicar que la regla debe aplicarse a cada hijo. Por ejemplo:

  Regla	Descripción
  hijoi.val = 5	Se asigna 5 al atributo val de todos los hijos
  campoi.tipo == INT	El tipo de todos los campos debe ser int
  ∑campoi.tipo.size	Suma del tamaño de todos los campos
  { campoi.nombre }	Conjunto con los nombres de todos los campos

• campo[<condición>] devolvería el primer hijo que cumpla la condición. Por ejemplo, el siguiente predicado comprobaría que el tipo del campo de la estructura llamado sueldo sea de tipo real.

  campo[nombre == "sueldo"].tipo == FLOAT
  

Representación de las Tablas #

En este apartado se comentarán algunas simplificaciones a la hora de representar las gramáticas atribuidas para simplificar su uso en ciertos capítulos posteriores.

Número de Columnas #

Se ha visto que la tabla de reglas semánticas está formada por tres columnas, siendo las dos últimas los predicados y las funciones.

Sin embargo, habrá situaciones en las que, para explicar algo, no será necesario distinguir entre estos dos tipos de reglas. Por ello, a veces se presentarán tablas con dos columnas, siendo la última la que representaría las reglas asociadas al nodo sin importar la clase de regla.

Notación Textual #

Aunque se intentará seguir la representación basada en tablas, debido a limitaciones de las herramientas con las que se están realizando estos apuntes, a veces esto no será posible. En estos casos, se usará una notación que representará las tablas usando texto plano.

Supóngase una tabla como la siguiente:

Esta tabla se representará en ciertos lugares de la siguiente forma, usando corchetes para separar las columnas:

a ⟶ b c   [ p1 ] [ f1 ]

De la misma manera que en el apartado anterior, cuando no se quiera diferencias entre predicados y funciones, se usará sólo una sección de reglas sin importar cual de las dos clases de reglas sean.

a ⟶ b c   [ r1  r2 ]