LogoopenSUSE Build Service > Projects
Sign Up | Log In

Backtracking LR Parsing

Kelbt generates backtracking LALR(1) parsers. Standard LALR(1) parser
generators emit an error upon encountering a conflict in the parse tables.
Kelbt forges onward, generating parsers which handle conflicts by backtracking
at runtime. Kelbt is able to generate a parser for any context-free grammar and
therefore implements a generalized parsing method. 

Kelbt is different from other backtracking LR systems in two ways. First, it
elevates backtracking to the level of semantic actions by introducing a class
of actions called undo actions. Undo 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
which must modify global state in preparation for handling context

Second, Kelbt enables a user-controlled parsing strategy which approximates
that of generalized recursive-descent parsing. This makes it easy for the user
to resolve language ambiguities by ordering the grammar productions of a
nonterminal according to their precedence. 

Kelbt has been used to write a C++ parser (included) which is composed of
strictly a scanner, a name lookup stage and a grammar with standard semantic
actions and semantic undo actions.

    Adrian Thurston

Source Files

Filename Size Changed Actions
kelbt-0.12.tar.gz 222 KB over 11 years ago Download File
kelbt-0.12_cxxprep.patch 298 Bytes over 11 years ago Download File
kelbt.changes 734 Bytes over 11 years ago Download File
kelbt.spec 2.7 KB over 11 years ago Download File

Comments for home:darix (0)