A Question about Reduction Events in Light of Memoization

Quinn Tyler Jackson <quinn-j@shaw.ca>
17 Nov 2004 11:42:08 -0500

          From comp.compilers

Related articles
A Question about Reduction Events in Light of Memoization quinn-j@shaw.ca (Quinn Tyler Jackson) (2004-11-17)
| List of all articles for this month |

From: Quinn Tyler Jackson <quinn-j@shaw.ca>
Newsgroups: comp.compilers
Date: 17 Nov 2004 11:42:08 -0500
Organization: Compilers Central
Keywords: parse, design question
Posted-Date: 17 Nov 2004 11:42:08 EST

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


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

Post a followup to this message

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