Re: Why use k > 1

Oliver Zeigermann wrote:
> I was just wondering why I should use a lookahead of k > 1
> and thus increasing time for the construction of my paser,
> while I could handle all cases of lookahead using syntactic
> predicates.


Simply put, k>1 finite fixed lookahead is faster at parse-time than
syntactic predicates, which are implemented via selective backtracking
over the input stream. However, k>1 lookahead takes longer during the
static grammar analysis phase. Note that ANTLR 2.00 uses an
approximation to full LL(k) that is linear rather than exponential in
nature, but covers nearly all decisions in your grammar (these can
easily be rewritten to fit the slightly weaker scheme). ANTLR 2.00 is
much faster at grammar analysis than ANTLR 1.33, which tried to deal
with full LL(k) lookahead.


LL(1) is not very useful for many of today's parsing problems, or at
least leads to less readable grammars than LL(k). LL is weaker than
LALR(1) in general and must make up for it with large lookahead.


> Also there can be no problems involving actions,
> beacause no actions are executed in syntactic predikates
> (referring to Terence Parrs article on why use k > 1).


I think I was referring (SIGPLAN Notices article?) to actions
preventing left-factoring (while trying to reduce the need for
lookahead). I still believe that more lookahead is the answer because
you don't have to screw up your grammar while reducing lookahead
requirements.


Regards,
Terence
PS See http://java.magelang.com/antlr/ for more info on ANTLR 1.xx
and ANTLR 2.00 (the Java version).
--

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