|A Question about Reduction Events in Light of Memoization firstname.lastname@example.org (Quinn Tyler Jackson) (2004-11-17)|
|From:||Quinn Tyler Jackson <email@example.com>|
|Date:||17 Nov 2004 11:42:08 -0500|
|Keywords:||parse, design question|
|Posted-Date:||17 Nov 2004 11:42:08 EST|
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:
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
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
Return to the
Search the comp.compilers archives again.