Search code examples
grammarambiguous-grammar

How to check if this grammar is ambiguous or not?

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

Solution

  • 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.