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

[Terence Parr]

On Jun 8, 2009, at 1:09 PM, Steven Obua wrote:

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

k=1 backtrack=true should give you a PEG equiv. to get packrat  
parsing, memoize=true

Ter

>
>
> 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
>
> List: http://www.antlr.org/mailman/listinfo/antlr-interest
> Unsubscribe: http://www.antlr.org/mailman/options/antlr-interest/your-email-address