[antlr-interest] packrat vs. LL(*)
Steven Obua
steven at obua.de
Mon Jun 8 04:23:59 PDT 2009
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
>
More information about the antlr-interest
mailing list