Coincidentally, I gave a presentation on this paper earlier this morning for a class of mine, as well as writing a report on it. You can find both attached. I have been meaning to look into this for adding left recursion support to PEGs.
Personally, I find the presentation better structured as I wrote it yesterday after having stewed on the ideas from the paper (and my report on it) for a week or two. You can find both here: http://ioreader.com/media/memo-parser-presentation.pdf http://ioreader.com/media/memo-parser-report.pdf Let me know if those clear up any of the ideas. Best Regards, Peter Goodman, http://ioreader.com 70 Winston Circle, Montreal, Quebec H9S 4X6 On Sat, Nov 27, 2010 at 8:35 AM, Andrew Lentvorski <bs...@allcaps.org> wrote: > I've been trying to work my way through Mark Johnson's "Memoization in Top > Down Parsing" paper. I've been trying to work through the continuation > passing style parts, but I just can't seem to figure out what is wrong with > the alt operator. > > I expect (FOOORBAR identity '(foo bar baz)) to return '(bar baz) for > consistency with the rest of the code, but all I'm getting is an empty list. > > What am I missing? Do I have to bottom out in something like a "future" > rather than identity and only fully-evaluate when I return? Is it as simple > as I'm missing a "union" in the function (but, I don't necessarily expect > that a continuation should allow things to come back so that seems like it > would be useless)? > > I suspect that I really need to understand this *well* before I try > memoizing the continuations for left-recursion evaluation. > > Thanks, > -a > > This is the code I used: > > (define (identity args) > args) > > (define (terminal word) > (lambda (continuation pos) > (if (and (pair? pos) (eq? (car pos) word)) > (continuation (cdr pos)) > (continuation '())))) > > (define (seq seq1 seq2) > (lambda (continuation pos) > (seq1 (lambda (pos1) (seq2 continuation pos1)) > pos))) > > (define (alt alt1 alt2) > (lambda (continuation pos) > (begin (alt1 continuation pos) > (alt2 continuation pos)))) > > (define FOO (terminal 'foo)) > (define BAR (terminal 'bar)) > (define FOOANDBAR (seq FOO BAR)) > (define FOOORBAR (alt FOO BAR)) > >> (FOO identity '(foo bar baz)) > '(bar baz) >> (BAR identity '(foo bar baz)) > '() >> (FOOANDBAR identity '(foo bar baz)) > '(baz) >> (FOOANDBAR identity '(bar baz foo)) > '() >> (FOOORBAR identity '(foo bar baz)) > '() ; <-- Not what I expected > > _______________________________________________ > PEG mailing list > PEG@lists.csail.mit.edu > https://lists.csail.mit.edu/mailman/listinfo/peg > _______________________________________________ PEG mailing list PEG@lists.csail.mit.edu https://lists.csail.mit.edu/mailman/listinfo/peg
