Re: Detection of ambiguous grammar

idbaxter@semdesigns.com
Fri, 24 Aug 2007 12:32:19 -0700

          From comp.compilers
Related articles
Detection of ambiguous grammar ulf.schwekendiek@googlemail.com (ulf.schwekendiek@googlemail.com) (2007-08-18)
Re: Detection of ambiguous grammar neelk@cs.cmu.edu (Neelakantan Krishnaswami) (2007-08-20)
Re: Detection of ambiguous grammar torbenm@app-2.diku.dk (2007-08-20)
Re: Detection of ambiguous grammar idbaxter@semdesigns.com (2007-08-24)
| List of all articles for this month |
From: idbaxter@semdesigns.com
Newsgroups: comp.compilers
Date: Fri, 24 Aug 2007 12:32:19 -0700
Organization: Compilers Central
References: 07-08-05207-08-056
Keywords: parse, practice
Posted-Date: 25 Aug 2007 10:37:18 EDT

On Aug 20, 3:09 am, torb...@app-2.diku.dk (Torben Fgidius Mogensen)
wrote:
> "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
> ambiguity.


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

Post a followup to this message

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