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 -&gt; S + S | S − S | S ∗ S | S / S | (S) | x | y
My attempt: The ambiguity can be corrected by
S -&gt; S + T | T , T -&gt;T - M| M, M * N|N , N / Q | Q , Q-&gt; (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 &amp;\to E + T \mid E - T \mid T \\
   T &amp;\to T * F \mid T / F \mid F \\
   F &amp;\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 &amp;\to T + E \mid T - E \mid T * E \mid T / E \mid T \\
   T &amp;\to x \mid y \mid ( E )
\end{align*}$
The possibilities are almost endless.
To show the above aren't ambiguous isn't so easy.