Aplicación de una Gramática Atribuida #

En este capítulo se verá, dada una gramática atribuida y una entrada, cómo se aplica la primera para comprobar si la segunda es válida o no.

Descripción del ejemplo #

El lenguaje que se va a usar como ejemplo de validación es el del capítulo anterior. Como recapitulación de lo visto, se tiene un lenguaje con:

• Una entrada que se quiere validar:

  [10+20 — 3*40]
  

  Para aplicarla una gramática atribuida a esta entrada, hay que representarla en forma de árbol. Recuérdese que una gramática atribuida puede hacerse a partir de una gramática libre de contexto o de una gramática abstracta (es decir, la gramática que aparece en la primera columna de la tabla de reglas). Por tanto, la entrada se representará como un árbol concreto en el primer caso o como un AST en el segundo. En este caso, en el que la gramática original es una gramática libre de contexto, la entrada se representará en forma de árbol concreto.

  

• La especificación formal mediante una gramática atribuida que indica qué condiciones debe cumplir todo árbol válido. En este caso, sólo hay una condición y es que el límite inferior del rango debe ser menor que el superior.

En el capítulo anterior se había llegado a la siguiente gramática atribuida, expresada en estas tablas de atributos y de reglas.

Tabla de Atributos

Tabla de Reglas Semánticas

Se han añadido etiquetas 🏷️ a las reglas para luego poder referirse a ellas de manera más fácil.

Validación del Árbol #

Para validar el árbol basta con recorrerlo aplicando en cada nodo sus reglas asociadas. El significado de aplicar una regla depende del tipo de regla que sea:

• Si es un predicado, significa comprobar si es cierto. En caso contrario, se notificaría un error.
• Si es una función, significa asignar el valor al atributo indicado.

El árbol, una vez finalizada la aplicación de la gramática atribuida, quedaría de la siguiente forma:

La notación usada en la traza de la aplicación de la gramática es la siguiente:

• Con un número dentro de un círculo negro se indica el orden en el que se han visitado los nodos.
• Debajo del número se pone el nombre de la regla que se esté aplicando a dicho nodo. Nótese que tendrá que ser una de las reglas asociadas al nodo que se está visitando (de su misma fila en la tabla).

  Nota

  📌 Es importante ser capaz de ver rápidamente cuál es la producción correspondiente a un subárbol y viceversa. Tal y como se vio en la estructura de un árbol concreto, la producción que se corresponde con un subárbol es aquella que tiene al nodo padre del mismo como antecedente y a los nodos hijos en el consecuente.

  

  Las reglas asociadas a un subárbol serán las asociadas a su producción, es decir, las reglas que estén en la misma fila de la tabla de reglas.

• Finalmente, con una flecha que sale del nombre de la regla, se indica el efecto que ha producido la aplicación de ésta. Apuntará al atributo cuyo valor asigna la regla.

Tal y como puede observarse, dado que todos los predicados han sido true (en realidad, el único predicado que hay en esta gramática), se puede concluir que la entrada es válida.

Orden de Aplicación de las Reglas #

Las gramáticas atribuidas no dictan en qué orden hay que recorrer el árbol (o, dicho de otra manera, en qué orden hay que aplicar las reglas). Por tanto, en el ejemplo anterior, se ha usado libremente un recorrido postorden.

Podría plantearse la duda de por qué se ha recorrido el árbol en ese orden y si se podría haber hecho de otra manera. La respuesta es que sí, se podrían haber visitado los nodos en otro orden, pero también es cierto que no vale cualquier orden. Por ejemplo:

• Los pasos 1 y 2 podrían haberse intercambiado. También podrían haberse hecho los pasos 4 y 5 antes que el 3. Todo esto no hubiera tenido consecuencias.
• Sin embargo, si el paso 3 se hubiera hecho antes que el 2, la regla f2 se hubiera aplicado antes que la regla f1 del hijo derecho y, por tanto, se hubiera hecho la suma de los valores de los hijos cuando aún no se ha asignado el valor 20 al hijo derecho. Por tanto, el resultado hubiera sido erróneo.

En definitiva, las reglas se pueden aplicar en distintos órdenes, pero, en cualquier caso, hay que asegurarse de que no se use ningún atributo que aún no haya sido inicializado. A un orden de aplicación de las reglas que cumpla esta condición se le llama órden topológico.

La duda que se plantearía ahora es, a la hora de aplicar una gramática atribuida ¿cómo se asegura que se esté siguiendo un orden topológico? Esta pregunta se dejará sin contestar hasta que posteriormente se vea cómo implementar una gramática atribuida. Hasta entonces, los ejemplos que se presenten se recorrerán de manera postorden ya que están preparados para que éste sea un orden válido para ellos. Pero no olvidar que, como se verá, este recorrido no es una solución que valga para aplicar cualquier gramática atribuida.