Ejemplo 410 #

Este ejercicio es un ejemplo de tratamiento de gramáticas ambiguas.

Enunciado #

Sea la siguiente gramática ambigua.

expr ⟶ expr '+' NUM
    | NUM
    | '(‘ tipo ')' expr 	// Suponemos tipo definido

Se pide:

1. Demostrar que es ambigua.
2. Dar una solución no ambigua con cambio de lenguaje y otra usando reglas de selección en ANTLR.

Solución #

1. Demostrar que es Ambigua #

Tal y como se dijo anteriormente, no existe un algoritmo que dada una gramática cualquiera indique si es ambigua o no. Pero una forma de demostrar que una gramática en particular sí es ambigua es mostrar una entrada para la cual al menos se puedan crear dos árboles concretos (es decir, que haya dos formas de interpretarla).

Una entrada que demostraría que la gramática es ambigua sería la siguiente:

(double) 3 + 4

Esta entrada puede producir dos árboles concretos (es decir, se puede llegar del símbolo inicial a la cadena mediante dos caminos) ya que hay dos formas de interpretarla:

En el primer árbol se interpreta que primero se convierte el 3 a double y al resultado de la conversión se suma al 4. En el árbol de la derecha se interpreta que primero hay que sumar y luego realizar la conversión de todo ello.

Por tanto, la gramática es ambigua.

2. Solución con Cambio de Lenguaje #

Se podría cambiar el lenguaje para que el valor sobre el que se realiza la conversión tuviera que estar delimitado, por ejemplo, con '<' y '>'. En esta caso, ya no habría dos formas de interpretar la entrada:

expr ⟶ expr '+' NUM
    | NUM
    | '(' tipo ')' '<' expr '>'

Las entradas dejarían claro el alcance de la conversión:

(double)<3 + 4>

(double)<3> + 4

Solución con Reglas de Selección #

En vez de cambiar el lenguaje, se puede dejar como está y, dejando la gramática ambigua, determinar qué derivación (interpretación) se quiere para dichas entradas.

De los dos árboles que generaba la entrada anterior, lo habitual es que se quiera interpretar que primero se hace la conversión y luego la suma, es decir, que la conversión tenga mayor prioridad. Por tanto, se quiere seguir la derivación que se corresponda con el árbol de la izquierda.

Para ello, en ANTLR habría que dar mayor prioridad (poner primero) la regla de la conversión y luego la de la suma.

expr ⟶ NUM
    | '(' tipo ')' expr
    | expr '+' NUM

Solución con Gramática Equivalente #

Aunque no se ha pedido en el enunciado, por si se tiene curiosidad, aquí estaría la solución hallando una gramática equivalente que no es ambigua.

expr ⟶ termino
    	| expr + termino

termino ⟶ factor
	    | '(' type ')' termino

factor ⟶ NUM