|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)|
|Date:||Fri, 24 Aug 2007 12:32:19 -0700|
|Posted-Date:||25 Aug 2007 10:37:18 EDT|
On Aug 20, 3:09 am, torb...@app-2.diku.dk (Torben Fgidius Mogensen)
> "ulf.schwekend...@googlemail.com" <ulf.schwekend...@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
Our DMS Software Reengineering Toolkit's GLR table generator has an
ambiguity check. It searches for short strings of tokens that have
ambiguous parses, and shows the grammar engineer those strings.
Clearly doesn't make any guarantees about nonambiguous grammars, but
it does make it easy to check that the grammar you have doesn't have
any (unexpected, after all we are using GLR!) silly ambiguities.
Ira Baxter, CTO Semantic Designs
Return to the
Search the comp.compilers archives again.