[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