|Detection of ambiguous grammar email@example.com (firstname.lastname@example.org) (2007-08-18)|
|Re: Detection of ambiguous grammar email@example.com (Neelakantan Krishnaswami) (2007-08-20)|
|Re: Detection of ambiguous grammar firstname.lastname@example.org (2007-08-20)|
|Re: Detection of ambiguous grammar email@example.com (2007-08-24)|
|From:||firstname.lastname@example.org (Torben =?iso-8859-1?Q?=C6gidius?= Mogensen)|
|Date:||Mon, 20 Aug 2007 10:09:52 +0200|
|Organization:||Department of Computer Science, University of Copenhagen|
|Posted-Date:||20 Aug 2007 09:49:21 EDT|
"email@example.com" <firstname.lastname@example.org> 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.
Return to the
Search the comp.compilers archives again.