Generic Interpreter
Example Instances


Arithmetic (implementation, source, output)

A left-recursive (non-LL(1)) Grammar for simple arithmetic expressions. The embedded Semantics evaluate an arithmetic expression in one pass as the source stream is read. Try using an LL(1) recursive descent parser around this Grammar. It descends forever on all but the simplest expressions, since the productions that recurse are put into the Grammar after those that terminate recursion, giving them higher precedence when descending the parse tree. 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 an arithmetic expression in one pass as the source stream is read. The Grammar submits to all parsers without conflict.

BitLexer (implementation, source, output)

Illustrates use of a Lexicon alone as a lexical analyzer.

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.

Java20 (implementation)

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

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 attributed ParseTree is printed.

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.

VirtualMachine (implementation, source, output)

An SLR(1) Grammar for an assembler language, such as that generated by the CodeGenerator example above. The embedded semantics operate a simple stack-oriented machine with a runtime stack, memory, instruction counter and comparator, and print the state of the machine after executing assembler code.


Craig A. Rich -- carich@csupomona.edu