[antlr-interest] LL(*) questions

Terence Parr parrt at cs.usfca.edu
Sat Sep 10 10:25:04 PDT 2005


On Sep 8, 2005, at 6:09 AM, Martin d Anjou wrote:
> Hi,
>
> How does LL(*) work in ANTLR v3? Does it travel down the grammar to  
> find the terminals that disambiguate the alternatives and use them  
> at runtime as lookaheads? Or as predicates?

Hooray!  I have like 2 hours to work on ANTLR 3 and can answer a  
question or two.

Ok, ANTLR v3 uses static grammar analysis just like ANTLR v1 and v2.   
THe only difference is that I will look arbitrarily ahead instead of  
a fixed k to resolve parsing decisions.

> What is the runtime cost of LL(*) vs. predicates vs. higher k (k  
> for the rule not for entire grammar)?

LL(*) degenerates to LL(k) for a fixed k automatically and whenever  
possible.  Give me an LL(2) grammar and ANTLR v3 will generate an LL 
(2) parser.  For most grammars requiring arbitrary lookahead, the  
amount of lookahead is only infinite in theory.  In practice it's  
like LL(5) or something.  Again the parser tunes itself from LL(1) to  
LL(*) even within the same decision!

Ter
--
CS Professor & Grad Director, University of San Francisco
Creator, ANTLR Parser Generator, http://www.antlr.org
Cofounder, http://www.jguru.com



More information about the antlr-interest mailing list