Re: Packrat parsers and memoization

>[...]
> G -> A1 b / A2 c
> A1 -> a
> A2 -> a
>[...]
> I fail to see how this helps here because 'A1 c' would simply be an
> unknown rule and create the wrong parse tree.


Packrat/memoization parser would probably help with rules such as:


G -> A b | A c
A -> a


by recognizing that the first "A" of second rule immediately on "ac",
because it was already found in first alternate.


also rules such as:


G -> A b | A c
A -> a | a A


could then be greatly enhanced on "aaaaaaaaaaaaaac", for the same reason: A
of "G->A c" will be skipped, testing immediately the "c".


I do not think that memoization will do any good to your original case
because the parser would have to "deduce" that a A1 and a A2 are indeed the
same. Grammar preparation could do this computation and actually macth one
for the other, then disambiguate on G rules acceptation but I think its
beyond simple packrat/memoization.


Regards
Armel

Return to the comp.compilers page.
Search the comp.compilers archives again.