Re: Have I discovered something new?

"Joachim Durchholz" <joachim_d@gmx.de>
21 Jul 2002 02:05:44 -0400

          From comp.compilers

Related articles
Have I discovered something new? steve.horne@iris.co.uk (Stephen Horne) (2002-07-15)
Re: Have I discovered something new? torbenm@diku.dk (Torben Ęgidius Mogensen) (2002-07-21)
Re: Have I discovered something new? joachim_d@gmx.de (Joachim Durchholz) (2002-07-21)
Have I discovered something new? cfc@world.std.com (Chris F Clark) (2002-07-21)
Re: Have I discovered something new? kgw-news@stiscan.com (2002-07-21)
Re: Have I discovered something new? whopkins@alpha2.csd.uwm.edu (Mark) (2002-07-24)
Re: Have I discovered something new? steve@lurking.demon.co.uk (Steve Horne) (2002-07-25)
Re: Have I discovered something new? robert.corbett@sun.com (Robert Corbett) (2002-07-31)
Re: Have I discovered something new? whopkins@alpha2.csd.uwm.edu (Mark) (2002-07-31)
[2 later articles]
| List of all articles for this month |

From: "Joachim Durchholz" <joachim_d@gmx.de>
Newsgroups: comp.compilers
Date: 21 Jul 2002 02:05:44 -0400
Organization: Compilers Central
References: 02-07-057
Keywords: parse
Posted-Date: 21 Jul 2002 02:05:44 EDT

Stephen Horne wrote:
>
  > If a grammar is ambiguous that can be detected in the
  > precalculated tables.


There is a proof that it is undecidable to check whether a grammar is
ambiguous. If the quoted sentence means you can decide whether a
grammar is ambiguous just by transforming it, you have done the
impossible. (I think it's more likely that either I misunderstood
what you meant, or your algorithm detects most but not all
ambiguities, or your algorithm cannot handle all grammars.)


> So really, I want to know whether this is worth persuing (ie has it
> already be done).


You'd have to prove a few things. The most important is whether the
parser accepts exactly those inputs that are part of the language, and
rejects all that aren't. (This is also the area that most novel parsing
approaches fail in.)
The ambiguity stuff above is also an issue. It's not a problem to check
whether a given input has an ambiguous parse, but it's impossible to
check whether a grammar is ambiguous for an arbitrary input. However, if
you can prove that your method is more general than existing methods
(chokes on substantially less inputs than LALR) without adding undue
overhead, it's still interesting.
One of the things that are interesting is whether your method can handle
all LR languages or not. The most important grammar classes are LL(k),
LR(k), LALR(k), and general operator precedence (these techniques allow
parsing fairly large classes of grammars with little overhead).


HTH
Joachim


Post a followup to this message

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