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

[Jim Idle]

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
> So, as I understand, with backtrack=true and memoize=true I basically  
> switch to linear time / linear space packrat parsing. If I accept the  
> constant slow down and the added space requirements, then it seems to  
> me that LL(*) parsing becomes superfluous. Shouldn't antlr therefore  
> maybe include a documented option "packrat" which implies the above  
> three option settings? I think packrat parsing is pretty popular, but  
> it took  me about a day to figure out the exact settings I need to  
> make it happen in ANTLR.
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).

So, if your project qualifies for the above paragraph, then congrats - 
you are done ;-). However, the fact that you need these options probably 
means that your grammar as typed isn't really LL anything and probably 
needs a lot of left factoring. This usually happens when people type in 
a grammar by reading through the language spec and typing what they see; 
such documents are rarely written with writing an ANTLR grammar in mind. 
However, perhaps before too long, that's how languages will be 
documented! :-)

Jim