[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