Re: question about lookahead

>It Seems Like Lookahead Is Used By Various Parsing Methods
>To Choose (Disambiguate) Between Several Productions That
>Can Be Taken At Any Point.


>My Question Is Why Lookahead At All ? Just Use A
>*Non Deterministic* PDA As Your Engine. (Just As You Use
>NFA'S To Find Reg-Expressions). A NPDA Would Then Choose
>All Productions That Were Applicable, As Opposed To Looking
>Ahead And Deciding Which One To Choose Beforehand.


Some parser generators (e.g. Ratatosk, which can be found through my
webpage at http://www.diku.dk/users/torbenm) use nondeterministic
PDA's, but there is a cost penalty: The parsers may use up to cubic
time compared to linear time for deterministic PDA's. It is even worse
if the NPDA's are implemented naively by backtracking (as is the case
with Ratatosk). However, in practice you rarely get into the worst
case, and there are numerous examples from real programming languages
that require unbounded lookahead but are easily handled in (average)
linear time by a naively implemented NPDA.


See also Daniel J. Salomon, Gordon V. Cormack: Scannerless NSLR(1)
Parsing of Programming Languages from PLDI'89.


>The NPDA Would Of Course Be Converted Into An *Equivalent*
>Deterministic PDA In Order To Actually Run It...


That, I'm afraid is not possible. Or to be precise, it is AFAIK still
an open problem: Noone knows of a way to convert arbitrary NPDA's to
DPDA's (or even methods that can simulate NPDA's in linear time) but
it has not been proven to be impossible, though few people expect it
to be.


Torben Mogensen (torbenm@diku.dk)

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