[anterior] [seguinte]
Considere a gramática seguinte:
S → if b then S else S
S → if b then S
S → a
a) mostre que a gramática é ambígua (por exemplo, encontre uma frase que tenha 2 árvores sintácticas);
b) rescreva a gramática de forma a torná-la não ambígua (das diversas soluções possíveis escolha apenas uma).
a) a frase "if b then if b then a else a" podes ser construída de 2 modos diferentes, num o else pertence ao 1º if, no outro o else pertence ao último:
b) Para retirarmos a ambiguidade da gramática, temos várias alternativas das quais apresento 2:
inserimos um símbolo a ladear o S, de modo a sabermos onde termina cada um dos S's, poe exemplo umas chavetas
S → if b then {S} else {S}
S → if b then {S}
S → a
o que torna as duas frases diferentes "if b then {if b then {a}} else {a}" e "if b then {if b then {a} else {a}}";
rescrevemos a gramatica de modo a só ser possível definir uma das alternativas, neste caso a 2ª
S → U | M
M → a | if b then M else M
U → if b then S | if b then M else U
que agrupa todos os if´s sem else no final das frases e que gera a seguinte árvore de derivação
[anterior] [seguinte]
Ultima alteração: terça-feira, 24 de Abril de 2007 às 23:35