Kelbt: Backtracking LR parsing

Adrian Thurston <thurston@cs.queensu.ca>
11 Dec 2006 16:10:23 -0500

          From comp.compilers

Related articles
Kelbt: Backtracking LR parsing thurston@cs.queensu.ca (Adrian Thurston) (2006-12-11)
| List of all articles for this month |

From: Adrian Thurston <thurston@cs.queensu.ca>
Newsgroups: comp.compilers
Date: 11 Dec 2006 16:10:23 -0500
Organization: Compilers Central
Keywords: parse, available, LR(1)
Posted-Date: 11 Dec 2006 16:10:23 EST

Hello, there is a new tool available called Kelbt. It is a
backtracking LR parser generator.


Kelbt is different from other backtracking LR parser generators in a
few ways. There is a separate class of semantic actions which get
executed during backtracking. These can be used to revert any changes
made to the global state that were made for the purpose of handling
context dependencies. With a little extra programming and some care,
backtracking can be made compatible with the lexical feedback hack.


The parsing strategy approximates that of recursive descent with
ordered choice. This allows one to resolve ambiguities by ordering the
productions of a non-terminal according to precedence. It can also be
used to tune the grammar to reduce the amount of backtracking when
common cases are known.


As a proof of concept a partial C++ parser is provided.


There is a paper which covers the method in detail on the homepage.


http://www.cs.queensu.ca/home/thurston/kelbt/


Thanks,
    Adrian



Post a followup to this message

Return to the comp.compilers page.
Search the comp.compilers archives again.