A Question about Reduction Events in Light of Memoization

Hello everyone.


I've a question about how to handle reduction in the presence of
memoization in my backtracking Meta-S parsing engine.


I've recently been experimenting with memoization. A nasty (albeit
contrived) example of a backtracking grammar that benefits from
memoization is this:


grammar HeavyBacktracker
{
S ::= (Y | X | Z) ".";
Z ::= ((A [G] B [G] C) | (A [G] B [G] D [G] F) | (A [G] B [G] D [G] E))
".";
Y ::= (( G | A | B | C | D | E | F)<+>) "!";
X ::= ((A [G] B [G] C) | (A [G] B [G] D [G] F) | (A [G] B [G] D [G] E))
"@";
A ::= pppp; // A
pppp ::= pp pp;
pp ::= "a";


B ::= "b";
C ::= "c";
D ::= "d";
E ::= "e";
F ::= "f";
G ::= H | "G";
H ::= A;
};


Given the input


      aabde..


the meta-s parser correctly accepts Z, but only after much nasty look
ahead. If A had an event handler, it would generate many calls on
incomplete matches. With memoization, only the first pass generates
those events -- better but wrong.


My thinking is that I can cure the problem by delaying reduction
events by pushing them to a stack, and then popping that stack when
backtracking occurs, and then firing those events on the stack only
when a "wall" has been reached (no backtracking can occur).


That's not too hard to do -- it cures the problem when memoization is
not used. I'm thinking that the event stack also has to be memoized
(already have to do that with the parse tree anyway), and then pull it
from the memoization store.


Are there any better solutions to this problem? Literature references?
--
Quinn Tyler Jackson
http://members.shaw.ca/grammarforge/

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