detecting ambiguous grammars

Thant Tessman <thant@acm.org>
15 Feb 2001 00:43:44 -0500

          From comp.compilers

Related articles
detecting ambiguous grammars thant@acm.org (Thant Tessman) (2001-02-15)
Re: detecting ambiguous grammars davidpereira@home.com (David Pereira) (2001-02-17)
Re: detecting ambiguous grammars cfc@world.std.com (Chris F Clark) (2001-02-23)
Re: detecting ambiguous grammars joachim_d@gmx.de (Joachim Durchholz) (2001-03-01)
Re: detecting ambiguous grammars henry@spsystems.net (2001-03-04)
Re: detecting ambiguous grammars thant@acm.org (Thant Tessman) (2001-03-04)
Re: detecting ambiguous grammars davidpereira@home.com (David Pereira) (2001-03-08)
[16 later articles]
| List of all articles for this month |

From: Thant Tessman <thant@acm.org>
Newsgroups: comp.compilers
Date: 15 Feb 2001 00:43:44 -0500
Organization: XMission http://www.xmission.com/
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


E0
    id
    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
designs.)


-thant


Post a followup to this message

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