Ejemplo 610 #

Objetivo #

El objetivo de este ejemplo es mostrar cómo crear una gramática atribuida. Es decir, a partir de una especificación informal en lenguaje natural, se creará la especificación correspondiente de manera formal con dicho metalenguaje.

Enunciado #

Se quiere un lenguaje formado por tres símbolos a, b y c. Cada uno de ellos se puede repetir varias veces, pero con los siguientes requisitos:

• Los símbolos tienen que estar en este orden: las a tienen que estar todas al principio y las c todas al final.
• El número de veces que aparezca cada símbolo debe ser el mismo. Es decir, si aparecen tres a, deberán también aparecer tres b y tres c. En caso contrario, la cadena no sería válida.

Ejemplos de entradas válidas serían:

abc
aabbcc
aaabbbccc

Ejemplos de entradas inválidas serían:

abbc
aabcc

Solución #

La primero será hacer una GLC que exprese la sintaxis del lenguaje.

s ⟶ listaA listaB listaC

listaA ⟶ A | listaA  A
listaB ⟶ B | listaB  B
listaC ⟶ C | listaC  C

Como puede observarse, la gramática no es más que aplicar tres veces el patrón de listas 1+ss para los tokens A, B y C.

Sin embargo, esa solución no es suficiente, ya que admitiría también como válidas las entradas anteriores que eran inválidas. Por tanto, hay que completar la GLC ampliándola a una gramática atribuida.

Lo primero, se necesita que cada símbolo guarde en un atributo el número de elementos que tiene. Esto se indica en la tabla de atributos.

Una vez que se puede contar con que esa información esté en el árbol, se puede hacer la tabla de reglas.