Elkhound is a parser generator, similar to Bison. The
parsers it generates use the Generalized LR (GLR) parsing algorithm.
GLR works with any context-free grammar, whereas LR parsers
(such as Bison) require grammars to be LALR(1).
This page is an overview of the implementation. Additional documentation
To download Elkhound and Elsa, see the
Elkhound distribution page.
Elkhound requires the following external software:
- ast, a system for making abstract syntax trees.
- smbase, my utility library.
a lexical analyzer generator.
a parser generator. (Elkhound does not need Bison once it has been compiled.)
$ make check
these options. You can also
look at the Makefile.
AssocKind, an enumeration of the kinds of associativity.
CycleTimer, which times a section of code in cycles and milliseconds.
EmitCode, a class to manage the printing of generated code. Its
main contribution is knowledge of how to insert #line directives.
A few utilities on top of the Flatten interface
This module generates parse tables as ML syntax, for when Elkhound is
running in ML mode.
Core module for the Elkhound parser (the on-line component, not the
offline parser generator). Implements a variant of the GLR
parsing algorithm. See glr.h for
Grammar analysis module. Includes algorithms for computing parse
tables. Also includes the main() for the parser generator program,
Grammar AST. The input grammar is initially parsed into an AST,
before a corresponding Grammar (grammar.h)
object is created.
Aborted attempt to make an interactive grammar analyzer/explorer/modifier.
Lexical analyzer for grammar input files. Uses
Analysis-time representation of a grammar. Stores symbols,
productions, etc. Note that the grammar is distilled down to parse
tables for the parser itself; this representation is not normally
available during parsing.
Grammar parser module.
LexerInterface, the interface the parser uses to access the
Module for parsing embedded fragments of ML in reduction actions.
ParseTables, a container class for the parse tables of a grammar.
The parser generator creates the tables, then
emittables.cc renders the tables out
as code for use by the parser during parsing.
A generic set of user actions that build parse trees for any grammar.
By making a ParseTreeLexer and ParseTreeActions, you can have a
version of your parser which just makes (and optionally prints) a
parse tree. This is very useful for debugging grammars.
PTreeNode, a generic parse tree node. Forms the basis for the
parse trees constructed by ptreeact.cc.
RCPtr, a reference-counting pointer. Used by the parser core
to maintain the stack node reference counts.
Lexer and driver program for experimental grammars.
UserActions interface, used by the parser core to invoke the
actions associated with reductions (and other events).
Some random macros.
I used smbase/scan-depends.pl
to make dependency diagrams of the parser generator, and the run-time
The parser generator:
Or as Postscript.
The run-time parser:
Or as Postscript.
This script finds dependencies among automatically-generated
source files. Output is extradep.mk.
Given the .out file from a run of Elkhound with the
-tr lrtable option, produce a Dot-format graph of the
Read a C++ header file containing a token code enumeration
declaration, and produce a corresponding .tok file for
This script makes an Elkhound .gr file from a more-compact
description of an experimental grammar.
Run some performance tests.
Run the regression tests.
Contains a few examples written for the ASF+SDF meta-framework, for
performance comparison with Elkhound.
Contains a C parser written in Elkhound. The grammar is almost free
of shift/reduce conflicts. It uses the lexer hack (feedback from the
symbol table into the lexer) to distinguish variables from types. The
lexer itself is very slow (just bad engineering). This parser could
be evolved into something useful in its own right, but at this time
it's mostly just a test of Elkhound's deterministic parser.
This is a C++ parser that uses the C++ Standard's grammar without
modification. Consequently, it has many shift/reduce and
reduce/reduce conflicts, and also many true ambiguities. This grammar
is not a very good grammar to use for parsing C++ input; rather, it's
essentially the skeleton on which the standard's English description
hangs. Nevertheless, it's useful because it will output exactly the
parse tree (ambiguities and all) that the standard grammar induces,
and this can then be compared to similar output from Elsa
Contains some example parsers written with Elkhound:
Simple parser for arithmetic expressions. This example was intended
to introduce a new user to some of Elkhound's syntax and semantics.
This contains an abstracted fragment of the C grammar, demonstrating the
ambiguity between variable and type names. The accompanying code
resolves the ambiguity using reduction cancellation.
This has two examples of parsing C expressions. The examples are
old and don't show much; I used them to test Elkhound during early
One of several directories of files used in the
This has a bunch of inputs for various testing grammars.
This is a collection of micro-grammars for performance and correctness
testing. The name "triv" comes from the fact that they all use the
trival lexer, i.e. a lexer that yields every character as a separate