13 Jun 1997 22:10:52 -0400

Related articles |
---|

Re: Why use k > 1 parrt@magelang.com (Terence Parr) (1997-06-13) |

From: | Terence Parr <parrt@magelang.com> |

Newsgroups: | comp.compilers.tools.pccts,comp.compilers |

Date: | 13 Jun 1997 22:10:52 -0400 |

Organization: | MageLang Institute |

References: | <33A00773.5C67@maz-hh.de> |

Keywords: | PCCTS, parse |

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

--

Post a followup to this message

Return to the
comp.compilers page.

Search the
comp.compilers archives again.