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

[Steven Obua]

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

> Steven Obua wrote:
>> Hi,
>>
>> I am currently building a parser with ANTLR; I am really happy about
>> this great tool!
>>
>> I found that the most convenient settings for my purposes are
>>
>> backtrack=true
>> memoize=true
>> k=1
>>
>> when leaving out the "k=1" option, antlr cannot process my grammar,  
>> it
>> runs into a timeout or something like that.
>>
>
> You need to use the extended option -X conversiontimeout 10000

Does not work, I tried that before using 'k=1', it still does not  
terminate in reasonable time. I even give ANTLR at lot of RAM (12 GB),  
still doesn't cope.


>>
> Well, first of all, global backtracking should only be used if you  
> don't
> care about error messages or performance. It is sort of a "get the job
> done" option that is useful for prototyping, proof of concept, or one
> off conversion programs (where you know the input is valid, you just
> want to change it to something else).
>

That is not true.  That is why I am referring to packrat parsing,  
which still guarantees linear time parsing. You can't get better  
complexity for a parser :-)  About the constant factor slowdown I dont  
care so much, I just need to know that the speed I currently see from  
my parser scales. About memory usage I dont care so much either, my  
application is using way more system resources after the parsing than  
the parser itself ever will.

Cheers,
Steven