Essence--An LR Parser Generator for Scheme
Version 1.0
March 26, 1999
Abstract
Essence is a generator for LR(k) and SLR(k) parsers in Scheme. The
generated parsers perform error recovery, and are highly efficient.
Testing and debugging a parser does not require an
edit--generate--compile--test cycle. Rather, the parser
generator results from a general parser which takes the input
grammar as a parameter; no generation and recompilation is necessary
to try out changes to a grammar. The generated parsers result from
the general parser by an automatic program transformation called
partial
evaluation [8][9].
This guarantees consistency and ensures correctness. However, no
specific knowledge of partial evaluation is required to use Essence.
This document assumes elementary knowledge about S-attributed
grammars and LR parsing, available in almost any compiler
construction
textbook [2][7][1][10].
It may also be helpful to study the documentation of more traditional
parser generation packages such as Yacc [4] or
Bison [3].
Mike
Sperber, Peter Thiemann