What are some common ways to determine if a grammar is ambiguous or not? What are some common attributes that ambiguous grammars have?
For example, consider the following Grammar G:
$S \rightarrow S(E)|E$
$E \rightarrow (S)E|0|1|\epsilon$
My guess is that this grammar is not ambiguous, because of the parentheses I could not make an equivalent strings with distinct parse trees. I could have easily made a mistake since I am new to this. What are some common enumeration techniques for attempting to construct the same string with different parse trees?
- How can I know that I am right or wrong?
- What are common attributes of ambiguous grammars?
- How could I prove this to myself intuitively?
- How could I prove this with formal mathematics?
Best Answer
To determine if a context free grammar is ambiguous is undecidable (there is no algorithm which will correctly say "yes" or "no" in a finite time for all grammars). This doesn't mean there aren't classes of grammars where an answer is possible.
To prove a grammar ambiguous, you do as you outline: Find a string with two parses. To prove it unambiguous is harder: You have to prove the above isn't possible. It is known that the $LL(k)$ and $LR(k)$ grammars are unambiguous, and for $k = 1$ the conditions are relatively easy to check.