Re: Have I discovered something new?

"Chris F Clark" <cfc@world.std.com> wrote in message news:02-07-079...


> > 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.


I doubt it. Consider the grammar


        S -> aSa | a


This grammar is unambiguous, but it features unbounded nondeterminism.


Parsing this grammar requires finding the middle of the input string.
Finding the middle using a left-to-right parser requires pairing off
the terminal symbols to the left and right of the current point of the
parse. The information that must be saved essentially amounts to
counting the number of terminal symbols in the input string. Thus,
the amount information needed is unbounded. Precomputing an unbounded
amount of information is likely to take a long time.


The language generated by the grammar can be recognized in linear
time. The grammar can be parsed in linear time using a two-headed
bi-directional parsing automaton if the automaton can tell when the
two heads are positioned on the same input symbol.


Determinisic grammars and grammars with bounded nondeterminism can be
parsed in linear time. That is an old result. I learned it thirty
years ago.


A problem with parsing ambiguous grammars is choosing a suitable
representation for the derivations. Consider the grammar


        S -> S | a


The single string generated by this grammar has an infinite number of
derivations.


                                                                                        Sincerely,
                                                                                        Bob Corbett

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