# How can I make the following grammar unambiguous

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.

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.

• APL associates to the right. – rici Mar 1 at 1:54
• @rci, my faulty memory. Checked with IBM's knowledge center, fixed. Thanks! – vonbrand Mar 2 at 0:51