Kelbt: Backtracking LR Parsing

*** NOTICE *** Kelbt is no longer active.

Introduction

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 left recursion.

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 context dependencies.

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.

Publications

[1] 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 more details.

Mailing List

Mailing list archives: kelbt-users.

Download

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.

License

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 restriction.

Author

Kelbt was written by Adrian Thurston.