File kelbt.txt of Package kelbt
#Dump of http://complang.org/kelbt/
Kelbt: Backtracking LR Parsing
Kelbt generates backtracking LALR(1) parsers. Where traditional LALR(1)
parser generators require static resolution of shift/reduce conflicts, Kelbt
generates parsers that handle conflicts by backtracking at runtime. Kelbt is
able to generate a parser for any context-free grammar that is free of hidden
Kelbt is different from other backtracking LR systems in two ways. First, it
introduces a class of actions called undo actions. These actions are invoked
as the backtracker undoes parsing and allow the user to revert any side
effects of forward semantic actions. This makes it possible to backtrack over
language constructs that must modify global state in preparation for handling
Second, Kelbt enables a user-controlled parsing strategy that approximates
that of generalized recursive-descent parsing with ordered choice. This makes
it easy for the user to resolve language ambiguities by ordering the grammar
productions of a non-terminal according to precedence. It is approximate in
the sense that for most grammars the equivalent of an ordered choice parsing
strategy is achieved. In cases where productions are parsed out of the order
given, there is a simple grammar transformation that remedies the problem.
See the CASCON paper for more details.
As a proof of concept, Kelbt has been used to write a partial C++ parser
(included) that is composed of strictly a scanner, a name lookup stage and a
grammar with standard semantic actions and semantic undo actions.
Adrian D. Thurston and James R. Cordy. A Backtracking LR Algorithm for
 Parsing Ambiguous Context-Dependent Languages. In 2006 Conference of the
Centre for Advanced Studies on Collaborative Research (CASCON 2006), pp.
39-53, Toronto, October 2006. pdf.
Note: The commit feature in Kelbt has diverged from the one described in this
article. Commits are no longer scoped to the production they are given in.
They always cause a full commit of the parse stack. See the ChangeLog for
Kelbt has a mailing list kelbt-users for discussion and announcements. Please
feel free to discuss anything related to Kelbt.
The latest is version is kelbt-0.15.tar.gz, released on Jan 22, 2012. The
ChangeLog is here.
Kelbt 0.15 is the final release.
My parsing work is continued in Colm.
Kelbt is released under the GNU General Public License. Kelbt copies portions
of its source code to the generated output, which normally would mean that
Kelbt parsers are covered under the GNU General Public License. As a special
exception to this technicality, you may use the output of Kelbt without
Kelbt was written by Adrian Thurston.