Have I discovered something new?

Steve Horne wrote:
> This book contained a statement that the possibility
> of an linear-time parsing algorithm for arbitrary context-free
> grammars was still an open question - that there was no proof or
> disproof, that every known context-free grammar can be parsed in
> linear time using specially designed methods, but that no general
> algorithm currently exists which works for all context-free grammars.
>
> Is this still the state of play?


Yes. As far as I can tell there is no published algorithm the parses
every known context free grammar in linear time. Nor is there even
anyone who claims to have implemented an algorithm the does that (that
I am aware of).


> The reason I ask is that I believe I have found an algorithm to do
> precisely this.


Well, that would be something new and it is certainly worth pursuing
what you have done further, even if what you believe is not
*completely* true.


> It will certainly handle any grammar that a Tomita parser will
> handle, and do so without needing stack duplication.


At one level I believe your claim for this, because we have an
(unpublished) algorithm implemented in an experimental version of
Yacc++ that does roughly this. (We call our technique LR(infinity)
because it effectively extends the lookahead of the parser out in an
unbounded fashion.) The idea is that instead of duplicating the stack
at runtime as a Tomita parser does, one precomputes the stack
extensions at compile time (the same way that an LR parser does
relative to an LL one).


I believe for non-ambiguous grammar the process of doing so always
terminates. So, if that is what you have invented, I think the basic
concept is sound.


On the other hand, your ability to produce all possible pairings for
ambiguous grammars in linear time is not believable. I have seen a
proof that such pairings grow at an n**2 rate. Thus, writing them
will necessarily take n**2 time.


> The only area where I have a serious uncertainty is in the issue of
> parsing infinitely ambiguous grammars. I need to think about this some
> more. I'm pretty sure the technique can be adapted, and the final
> output from parsing a grammar and scentence with infinite ambiguity
> would be essentially a regular grammar (with branches instead of
> alternatives) describing the structure of the parse tree.


If your technique is similar to the one I described, this is a real
problem. For one thing, there is a proof that there is no algorithm
that can determine if an arbitrary cfg is unambiguous--one can use an
algorithm that determines if an arbitrary cfg is ambiguous to solve
the Post-correspondence problem, which is equivalent to solving the
halting problem. If your algorithm could detect these infinite
ambiguities (and halt), then it would have essentially solved the cfg
ambiguity problem.


Our technique founders on this very rock. Although there are certain
ambiguities it can detect, on other grammars the algorithm loops
forever attempting to resolve the lookahead.


That is not a completely hopeless situation. For every set of
grammars less than some finite length, there is a finite maximum
number of states that any unambiguous grammar has and all ambiguous
grammars are "detectable" by that point. The only problem is that we
cannot know (via an algorithm) what that number is in advance for some
unspecified finite length. That is, if I tell you in advance what the
length is, you can tell me a number, because it exists. However, if
you tell me that you can calculate the number for any length, I can
come up with a length for which your calculation fails.


In any case, we use that property to constrain our algorithm by
allowing the user to fix the maximum nuber of lookahead states.
Unambiguous grammars don't generally need very many lookahead states.
It is worth losing a few unambiguous grammars to have an algorithm
that always terminates.


Hope this helps,
-Chris


*****************************************************************************
Chris Clark Internet : compres@world.std.com
Compiler Resources, Inc. Web Site : http://world.std.com/~compres
3 Proctor Street voice : (508) 435-5016
Hopkinton, MA 01748 USA fax : (508) 435-4847 (24 hours)

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