Andrew, You can also find a Python implementation that follows the pseudocode from my presentation/report here: http://codepad.org/Jyl0ls5y
Best Regards, Peter Goodman, http://ioreader.com 70 Winston Circle, Montreal, Quebec H9S 4X6 On Sat, Nov 27, 2010 at 7:06 PM, Peter Goodman <peter.good...@gmail.com> wrote: > 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
