If I rewrite a grammar to remove ambiguity, will it remain equivalent to the original one ?

166 Views Asked by At

For example, I have this grammar

E → E + E | E * E | a | b | c

It is ambiguity for the case: a * b + c, which have 2 parse tree:
E => E + E => E * E + c => a * b + c
and
E => E * E => a * E + E => a * b + c

I rewrite the grammar to remove ambiguity for the above case
E→ T | E + T
T → F | T * F
F → E | a | b | c

Is new grammar still equivalent to original grammar ?
If yes/no, how to prove it or what is the counter example ?

Thank you.

1

There are 1 best solutions below

0
On BEST ANSWER

The grammar is still ambiguous. Consider these two derivations of $a*b+c$: $$ E \to E+T \to T+T \to T+F \to T+c \to T*F + c \to F*F+c \to F*b+c \to a*b+c $$ and $$ E \to T \to T*F \to T*E \to F*E \to a*E \to a*E+T \to a*T+T \to a*T+F \\ \to a*F+F \to a*F+c \to a*b+c $$

When you do remove ambiguity, the resulting grammar is equivalent to the original, in that the languages they generates are the same.