23
$\begingroup$

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?

  1. How can I know that I am right or wrong?
  2. What are common attributes of ambiguous grammars?
  3. How could I prove this to myself intuitively?
  4. How could I prove this with formal mathematics?
$\endgroup$
3

4 Answers 4

22
$\begingroup$

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.

$\endgroup$
2
  • 3
    $\begingroup$ in case anyone wants to know why the problem is undecidable check this out cstheory.stackexchange.com/questions/4352/… $\endgroup$
    – KFkf
    Commented Apr 27, 2015 at 18:50
  • 1
    $\begingroup$ although it is not easy to understand $\endgroup$
    – KFkf
    Commented Apr 27, 2015 at 18:52
6
$\begingroup$

let $G= (V,T,P,S)$, where $P$ are:

  • $S\to S(E)|E$
  • $E\to (S)E|0|1|ϵ$

Now consider a string $w \in L(G)$

$w = (0)(0)()1$

Construct Left Derivation

$S\to E\to (S)E\to (0)E\to (0)(S)E\to (0)(0)E\to (0)(0)(S)E\to (0)(0)(ϵ)E\to (0)(0)()E\to (0)(0)()1.$

Construct Right Derivation $S\to E\to (S)E\to (S)(S)E\to (S)(S)(S)E\to (S)(S)(S)1\to (S)(S)(ϵ)1\to (S)(S)()1\to (S)(0)()1\to (0)(0)()1.$

We were able to construct 2 distinct Derivations. Hence This Grammar is ambiguous.

"If a grammar produces at least 2 distinct parse tree or derivations, then the grammar is ambiguous."

$\endgroup$
2
  • 5
    $\begingroup$ An even simpler ambiguous string is $()$. $\endgroup$ Commented Dec 2, 2013 at 8:05
  • 1
    $\begingroup$ Correctly, if it has more than one leftmost or rightmost derivation, not just any derivation. Here it looks like the parse trees are the same. $\endgroup$
    – vonbrand
    Commented Mar 28, 2020 at 18:47
1
$\begingroup$

If CFG may produce more than one parse tree for the same input string then the grammar is said to be ambiguous. Very easily we can able to identify that. (i.e) when the same non-terminal appears twice on a right hand side of the production then it has the ambiguity problem. The general form of the ambiguous grammar is: S -> α S β S γ | α1| α2 | α3 | …. |αn this production has an ambiguity problem because S are present twice on the right hand side of the production. Where α,β and γ are some string. Example E -> E + E | E * E | (E) | id

$\endgroup$
1
  • 2
    $\begingroup$ You say "when the same non-terminal appears twice on the right side of the production then it has the ambiguity problem". That doesn't necessarily follow. E.g. A -> B B; B -> id; is unambiguous. Do you mean "when the same non-terminal that's on the left hand side appears twice on the right hand side"? $\endgroup$
    – Don Hatch
    Commented Feb 26, 2020 at 2:45
1
$\begingroup$

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:

  1. $E \rightarrow E + id \rightarrow id \star E + id \rightarrow id \star id + id$, and
  2. $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$.

$\endgroup$
1
  • $\begingroup$ Welcome on the MathSE! This site supports latex, just type $E \rightarrow E + id$ and you get $E \rightarrow E + id$. $\endgroup$
    – peterh
    Commented May 29, 2018 at 23:10

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .