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

[Steven Obua]

I am not entirely sure it is the same thing, too, but I don't see any  
difference so far (given the three options settings of backtrack=true,  
memoize=true, k=1). Sure, it is all in one grammar, but this is more a  
convenience thing than a true difference to packrat parsing?

As for the ordered rules, it is the same in ANTLR when you use  
backtrack=true. Look for example at the following grammar:

---------------------------------------------
grammar rats_test;

options {
language=Java;
output=AST;
ASTLabelType=CommonTree;
backtrack=true;
memoize=true;
k=1;
}

a 	:	 'A' | 'A' 'B'^;
------------------------------------------

This grammar will not recognize "AB"  for a.

Cheers,

Steven


On Jun 8, 2009, at 12:43 PM, Michael wrote:

>> So, as I understand, with backtrack=true and memoize=true I basically
>> switch to linear time / linear space packrat parsing.
>
> I'm not sure if it's a the same as a packrat parser (like rats! for  
> example).
> There are some differences, the biggest is in a packrat parser you  
> have
> ordered choises:
> if in a rule  e1 | e2   the first (e1) succeeds. the second is  
> ignored. So
> unlike normal BNF definitions you cannot simply switch the order of  
> the
> alternatives.
>
> And you don't use a separate lexer, it's all in one grammar
>