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

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

Right recursion tests

Direct left recursion tests

Indirect left recursion tests