Arithmetic
(implementation,
source,
output)
A left-recursive (non-LL(1))
Grammar
for simple arithmetic expressions. The embeddedSemantics
evaluate the arithmetic expression in one pass as the source stream is read. Try using an LL(1) recursive descent parser around thisGrammar
. 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. TheGrammar
submits to SLR(1) and LR(1) parsers without conflict.
ArithmeticLL
(implementation,
source,
output)
An LL(1)
Grammar
equivalent toArithmetic
obtained by removing left recursion. The embeddedSemantics
evaluate the arithmetic expression in one pass as the source stream is read. TheGrammar
submits to all parsers without conflict.
CodeGenerator
(implementation,
source,
output)
An LL(1)
Grammar
for a small programming language with statements and expressions. The embeddedSemantics
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 embeddedSemantics
construct anExpression
from aString
containing an ERE. It is used in the Generic Interpreter to implement theLexicon.expression(String)
method.
Java10
(implementation)
An allegedly LALR(1) (and therefore LR(1))
Grammar
for Java 1.0. I encounter conflicts when parsing aConstructorBody
with a lookahead terminal likethis
, which could appear first in anExplicitConstructorInvocation
likethis(argument);
or a
Statement
likethis.field = argument;
There are no embedded
Semantics
.
Java12
(implementation)
A
Grammar
for Java 1.2. There are no embeddedSemantics
... 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 embeddedSemantics
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 embeddedSemantics
perform type checking in one pass as the source stream is read. If no semantic errors occur, an annotatedParseTree
is printed.