detecting ambiguous grammars

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

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