An Implementation of Mark Johnson's "Memoization in Top-Down Parsing" in JavaScript

In "Memoization in Top-Down Parsing", Mark Johnson describes a technique based on memoization and Continuation-Passing Style (CPS) for implementing top-down parsers that support left recursion and polynomial parse times.

This page contains a JavaScript implementation of Johnson's technique; it was used to generate the results below. Note that it is able to support both direct and indirect left recursion.

(A result of PASSED means that the production was able to recognize a string of five xs.)

Right recursion tests

     rrRule1 ::= x <rrRule1> | x     
rrRule2 ::= x | x <rrRule2>

Direct left recursion tests

lrRule1 ::= <lrRule1> x | x
lrRule2 ::= x | <lrRule2> x

Indirect left recursion tests

lrRule3a ::= <lrRule3b>
lrRule3b ::= <lrRule3c>
lrRule3c ::= <lrRule3d>
lrRule3d ::= <lrRule3e>
lrRule3e ::= <lrRule3f>
lrRule3f ::= <lrRule3a> x | x