detecting ambiguous grammars

Thant Tessman <>
15 Feb 2001 00:43:44 -0500

          From comp.compilers

Related articles
detecting ambiguous grammars (Thant Tessman) (2001-02-15)
Re: detecting ambiguous grammars (David Pereira) (2001-02-17)
Re: detecting ambiguous grammars (Chris F Clark) (2001-02-23)
Re: detecting ambiguous grammars (Joachim Durchholz) (2001-03-01)
Re: detecting ambiguous grammars (2001-03-04)
Re: detecting ambiguous grammars (Thant Tessman) (2001-03-04)
Re: detecting ambiguous grammars (David Pereira) (2001-03-08)
[16 later articles]
| List of all articles for this month |

From: Thant Tessman <>
Newsgroups: comp.compilers
Date: 15 Feb 2001 00:43:44 -0500
Organization: XMission
Keywords: parse, question
Posted-Date: 15 Feb 2001 00:43:44 EST

Is there a general algorithm for detecting whether a grammar is
ambiguous? I've read posts that suggest the answer is no, but could
someone point me at the reason why?

A naive approach would be to systematically generate all possible
strings less than a given length and just check to see if any of the
strings are equivalent. Of course this only works for statements less
than the given string length. (Is there a way to prove that this is
sufficient for some class of grammars?)

But how about generating all possible strings where each non-terminal
is expanded at least three times. Why three times? Because that's what
seems to work in the hand expansions I've done.

Given the grammar

E:= id
E:= E + E

the strings are

    E1 + E1
        id + id
        id + E2 + E2
            id + id + id
            id + id + E3 + E3
            id + E3 + E3 + id
            id + E3 + E3 + E3 + E3
                (don't bother generating E4s)
        E2 + E2 + id
            id + id + id
            id + E3 + E3 + id
            E3 + E3 + id + id
            E3 + E3 + E3 + E3 + id
                (don't bother generating E4s)
        E2 + E2 + E2 + E2
        id + id + id + id
            (a bunch more E3 statements, you get the idea)

The grammar has produced two instances of the string "id + id + id" (as
well as some identical E3 strings) which shows that the grammar is
ambiguous. Can folks suggest why this approach may or may not be a wild
goose chase? (I'm going to be using a top-down parser and my goal is not
efficiency, but the exploration of the implications of various grammar


Post a followup to this message

Return to the comp.compilers page.
Search the comp.compilers archives again.