Re: question about lookahead

snowscan100@yahoo.com asked:
>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.


As Torben Mogensen noted there are parsing technologies that use
NPDA's. The most common branch of them is Earley's method which has
n**3 worst case performance, as opposed to the linear performance of
DPDA's. Several years ago Tomita and Lang showed that you could use a
data structure called a shared-parse forest with an LR parser to build
an Earley style parser.


Besides the worst-case performance issue, which is generally
overstated, there are other reasons why NPDA's are not popular.


The biggest reason has to do with semantic actions. There are a lot
of advantages to executing your actions as early as possible while
processing the grammar. For one, thing it is often easiest to add
nodes to a list right after the nodes are created. In other case,
like C[++] typedefs, you need to add the typedef to the symbol table
at a specific point in the grammar or the subsequent symbol table
lookups will return the wrong results and cause you to mis-parse the
input.


With an NPDA, you may have to step several rules past the end before
you know which non-terminal is being selected (and with an ambiguous
grammar, you may never know which non-terminal is appropriate). Not
knowing prevents one from applying the semantic actions.


A similar effect occurs with error detection. Both LL and LR parsers
have nice error detection properties (the valid prefix property) that
most NPDA parsers do no possess.


The other side of this is that lookahead (at least at its most
general) is exactly equivalent to non-determinism. In other words,
you can construct a lookahead machine which effective simulates an
NPDA. If you look at parsers which use syntactic predicates, that is
often essentially what they are doing (i.e. try parsing this way and
if it works do so, otherwise backtrack and try another alternative).


Finally, there is a "correctness" issue. An LL or LR parser generator
can guarantee that your grammar is non-ambiguous. Most NPDA soultions
will merrily process an ambiguous grammar (and some will potentially
give different results for different executions).


Hope this helps,
-Chris


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

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