Determining Ambiguity in Context Free Grammars 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?


Another rule: all CFG (without useless symbols) with left-recursivity and right-recursivity for the same non-terminal is ambiguous too. Example: $E \rightarrow E + id | id \star E | id$. The string $id \star id + id$ has two leftmost derivations:


*

*$E \rightarrow E + id \rightarrow id \star E + id \rightarrow id \star id + id$, and

*$E \rightarrow id \star E \rightarrow id \star E + id \rightarrow id \star id + id$.


Besides that, ambiguity can be so simple too, like in $E \rightarrow A | a, A \rightarrow a$.
