openSUSE Build Service

Overview Repositories Revisions Requests Users Attributes Meta

File kelbt.txt of Package kelbt (Revision 75c9d6b93a098e6a0d4c74c6bbf5dc4a)

Currently displaying revision 75c9d6b93a098e6a0d4c74c6bbf5dc4a , Show latest

#Dump of http://complang.org/kelbt/

Kelbt: Backtracking LR Parsing                                                
 
 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

Adrian D. Thurston and James R. Cordy. A Backtracking LR Algorithm for
 [1]  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

Kelbt has a mailing list kelbt-users for discussion and announcements. Please
 feel free to discuss anything related to Kelbt.

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

Places

File kelbt.txt of Package kelbt (Revision 75c9d6b93a098e6a0d4c74c6bbf5dc4a)

Places