[antlr-interest] packrat vs. LL(*)

Steven Obua steven at obua.de
Mon Jun 8 13:09:28 PDT 2009


On Jun 8, 2009, at 9:43 PM, Jim Idle wrote:

> And how are you guaranteeing linear time with global backtrack=true?  
> All
> this really means is that it tries every alt you specify n the order  
> you
> specify, which means that if your particular input is alt 12, it will
> try 11 others first. Now, that isn't quite true because ANTLR is a bit

Well, that's exactly why I am asking if ANTLR supports packrat  
parsing. I think that the options
backtrack=true, memoize=true, k=1 could be equivalent to packrat  
parsing. But I am not sure about it, so I would like to know if  
somebody on this mailing list here knows this for sure or has a  
counter argument.

For the linear time complexity, that is just the great thing about  
packrat. It's due to the memoization, so that for each pair (pos, N),  
where pos is the parsing position and N is the nonterminal to be  
parsed, you remember if you have done this parsing job earlier. The  
number of pairs (pos, N) is linear in the length of the text to be  
parsed, because there are only finitely many nonterminals in a  
grammar. So even if you are backtracking, you are still linear time  
when you are memoizing, because you don't backtrack more often than  
there are such pairs.


>
> smarter than that, but it CAN be true.

So it CANNOT be true.

>
> But, if you turn on a timeout of 10000 and still cannot get through  
> the
> grammar, then you need to consider fixing up your grammar.
>

Well, with the options I give, it finishes code generation in a few  
milli seconds. My grammar is very readable (which would be destroyed  
by left-factoring), the parser is sufficiently fast. In twenty years,  
it will be even faster.


>> You can't get better complexity for a parser :-)
> I am not sure what you are trying to say here.

Don't bother.

Cheers,

Steven


More information about the antlr-interest mailing list