How can I make the following grammar unambiguous

Question

Given the below ambiguous grammar how can I make it inambiguous and how can I prove the new modified unambiguous grammar is unambiguous? S -> S + S | S − S | S ∗ S | S / S | (S) | x | y

My attempt: The ambiguity can be corrected by

S -> S + T | T , T ->T - M| M, M * N|N , N / Q | Q , Q-> (I) | x| y|

But I'm unsure how to provide a proof for this and I do not know if the |x|y| will have an affect on making this grammar ambiguous. I was thinking I could do an induction proof but I'm unsure how I would begin.

Answer 1

This is a typical ambiguous grammar for arithmetic expressions. You can write different unambiguous equivalent grammars. For example, if you use the traditional precedences and associativities;

$\begin{align*} E &\to E + T \mid E - T \mid T \\ T &\to T * F \mid T / F \mid F \\ F &\to x \mid y \mid ( E ) \end{align*}$

You could also go the way of APL: All operations the same precedence, associate to the right.

$\begin{align*} E &\to T + E \mid T - E \mid T * E \mid T / E \mid T \\ T &\to x \mid y \mid ( E ) \end{align*}$

The possibilities are almost endless.

To show the above aren't ambiguous isn't so easy.