Re: Detection of ambiguous grammar

"ulf.schwekendiek@googlemail.com" <ulf.schwekendiek@googlemail.com> writes:


> I am thinking of a special case in GLR parsing. I am wondering whether
> it is possible to check if a grammar is ambiguous.


Ambiguity of context-free grammars is not decidable, so in general you
can't check it. You can make some tests that will detect certain
cases of ambiguity (test a number of strings for multiple parse
trees), but that will not (in bounded time) catch all cases of
ambiguity. You can also prove certain grammars unambiguous. For
example, conflict-free LR(k) grammars are unambiguous, and there are
other tests that can verify even more grammars as unambiguous. But
there will always be unambiguous grammars that these methods can not
prove to be so, and there will always be ambiguous grammars that are
not detected to be so by finite testing.


Torben

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