|Kelbt: Backtracking LR parsing firstname.lastname@example.org (Adrian Thurston) (2006-12-11)|
|From:||Adrian Thurston <email@example.com>|
|Date:||11 Dec 2006 16:10:23 -0500|
|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.
Return to the
Search the comp.compilers archives again.