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

Steven Obua steven at obua.de
Mon Jun 8 02:19:49 PDT 2009


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.

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.

Cheers,

Steven Obua

PS: USF rules!, have been an exchange student there for almost a year  
about 10 years ago :-)


More information about the antlr-interest mailing list