How to check if this grammar is ambiguous or not?

Question

I´m having trouble to see if this grammar it´s ambiguous or not. How can I check if it is ambiguous?

G = ({S,A,B}, {0,1}, P, S}

P:

S → 0B | 1A

A → 0 | 0S | 1AA

B → 1 | 1S | 0BB

Answer 1

What you'd like is an algorithm that, for a given context-free grammar, tells you whether it's ambiguous or not. However, it's been proven that no such algorithm can exist.

One approach is to apply a parser-construction technique that's known to only work for a subset of unambiguous grammars.

• If the construction succeeds, then you know for sure that the grammar is unambiguous.
• If the construction fails, then you still don't know: the grammar might be ambiguous, or it might be unambiguous but outside the subset that the technique can handle. However, the way in which the construction fails may give you insight into the problem.

For instance, if you construct the LR(0) automaton for your grammar, you get 2 states with conflicts, so that's inconclusive. But you know that if it is ambiguous, then any sentence that demonstrates the ambiguity would have to involve at least one of those states. (Any sentence that avoids those states could be parsed deterministically.) So you can concentrate on that area of the grammar.

Another approach is to use heuristics. E.g. the production B -> 0BB looks like it might cause ambiguity. (Having the two Bs right next to each other is kind of suspicious.) So you'd concentrate on the BB and ask if there's some way that that can derive a form XYZ where the two Bs 'fight' over the Y. I.e. if there's one derivation where

B -> X   and B -> YZ

and another where

B -> XY  and B -> Z

(and Y is non-empty, of course) then you can use that to demonstrate ambiguity.

Answer 2

A grammar is said to be ambiguous if there exists more than one leftmost derivation or more than one rightmost derivation or more than one parse tree for the given input string. If the grammar is not ambiguous, then it is called unambiguous.

Thus, let's try to reproduce 0011 from the above grammar.

Example for 0011: S->OB->00BB->001B->0011

Example for 1100: S->1A->11AA->110A->1100

It seems that only one leftmost derivation or rightmost derivation is produced, if parsing this input string. So the grammar is unambigous.