Martin Pluskal
273653b0ae
OBS-URL: https://build.opensuse.org/request/show/404192 OBS-URL: https://build.opensuse.org/package/show/devel:tools/kelbt?expand=0&rev=1
71 lines
3.1 KiB
Plaintext
71 lines
3.1 KiB
Plaintext
#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.
|
|
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
|