Generic Interpreter
Example Instances


Arithmetic (implementation, source, output)

A left-recursive (non-LL(1)) Grammar for simple arithmetic expressions. The embedded Semantics evaluate the arithmetic expression in one pass as the source stream is read. Try using an LL(1) recursive descent parser around this Grammar. It could descend forever (yes, this can happen), but the productions that terminate recursion are constructed after those that recurse, giving them higher precedence when descending in the parse tree. Unfortunately, that also causes LL(1) parsing to terminate prematurely on all but the simplest expressions. The Grammar submits to SLR(1) and LR(1) parsers without conflict.

ArithmeticLL (implementation, source, output)

An LL(1) Grammar equivalent to Arithmetic obtained by removing left recursion. The embedded Semantics evaluate the arithmetic expression in one pass as the source stream is read. The Grammar submits to all parsers without conflict.

CodeGenerator (implementation, source, output)

An LL(1) Grammar for a small programming language with statements and expressions. The embedded Semantics generate assembler code for a simple stack-oriented machine in one pass as the source stream is read.

ERE (implementation)

A Grammar for POSIX extended regular expressions (EREs), as used in egrep. The embedded Semantics construct an Expression from a String containing an ERE. It is used in the Generic Interpreter to implement the Lexicon.expression(String) method.

Java10 (implementation)

An allegedly LALR(1) (and therefore LR(1)) Grammar for Java 1.0. I encounter conflicts when parsing a ConstructorBody with a lookahead terminal like this, which could appear first in an ExplicitConstructorInvocation like

this(argument);

or a Statement like

this.field = argument;

There are no embedded Semantics.

Java12 (implementation)

A Grammar for Java 1.2. There are no embedded Semantics... I don't have that much free time ;)

LittleLexer (implementation, source, output)

Illustrates use of a Lexicon alone as a lexical analyzer.

PureLisp (implementation, source, output)

An SLR(1) Grammar for Pure Lisp, an original version of Lisp authored by John McCarthy. The embedded Semantics interpret Pure Lisp expressions. The example source shows a Tower of Hanoi (what else) algorithm in Pure Lisp.

TypeChecker (implementation, source, output)

An LL(1) Grammar for a small subset of Pascal. The embedded Semantics perform type checking in one pass as the source stream is read. If no semantic errors occur, an annotated ParseTree is printed.


Craig A. Rich -- carich@acm.org