Re: Detection of ambiguous grammar

torbenm@app-2.diku.dk (Torben =?iso-8859-1?Q?=C6gidius?= Mogensen)
Mon, 20 Aug 2007 10:09:52 +0200

          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: torbenm@app-2.diku.dk (Torben =?iso-8859-1?Q?=C6gidius?= Mogensen)
Newsgroups: comp.compilers
Date: Mon, 20 Aug 2007 10:09:52 +0200
Organization: Department of Computer Science, University of Copenhagen
References: 07-08-052
Keywords: parse
Posted-Date: 20 Aug 2007 09:49:21 EDT

"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



Post a followup to this message

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