Re: Have I discovered something new?

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

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