Ejemplo 620 #

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 tiene la siguiente GLC que describe un lenguaje formado por números separados por comas.

programa ⟶ serie
serie ⟶ NUM
serie ⟶ serie ',' serie

Se quiere que se consideren válidas sólo aquellas entradas cuyos árboles tengan la características de que, en todo subárbol, todos los números que haya a su izquierda (a cualquier profundidad) sean todos menores que todos los hijos de la derecha.

Aquí se presenta un ejemplo de árbol válido y otro inválido.

Nótese que el árbol de la derecha es inválido porque el 14 es mayor que el 12 del subárbol de la derecha. Por tanto, el símbolo serie debajo del programa no cumple que todos sus hijos de la izquierda sean menores que los de la derecha.

Se pide expresar estas restricciones en forma de gramática atribuida.

Solución #

Para poder comprobar si todos los hijos de la parte izquierda son menores que los de la derecha, se necesitaría que cada serie guardara cuál es su menor y su mayor número. Esto se expresa con la tabla de atributos.

Ahora, ya se puede poner el predicado que comprueba los números que se hayan en cada subárbol.