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.

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.