LR(k) or LALR(k) parser generator with features similar to ANTLR

Question

I'm currently in the process of writing a parser for some language. I've been given a grammar for this language, but this grammar has some left recursions and non-LL(*) constructs, so ANTLR doesn't do very well, even with backtracking.

Because removing these left recursions and non-LL(*) constructs is harder than it looked at first glance, I now want to try a LR(k) or LALR(k) parser generator. The higher k the better.

Can anyone recommend me a parser generator fulfilling these requirements?

• The generated parser is preferably a LR(k) parser with some high (or even arbitrary) k, or at least a LALR(k) parser with some high k.
• The generated parser is written in C or C++, and if it is written in C, it is linkable to C++-Code.
• A feature set similar to ANTLR (especially the AST rewriting) would be nice.
• Performance is not the most pressing issue, the generated parser is intended to be used on desktop machines with much memory and cpu power.

Thanks and greetings,
Jost

PS: I'm not asking because I can't google myself, but because there is no time left to test some generators myself. So please only answer if you have experience with the recommended parser generators.

Answer 1

I have now decided to use DParser, which is a GLR-Parser generator capable of recognizing any context free language. It seems to be well programmed (look at the tests in the source distribution), but lacks a lot of the features ANTLR provides, most notably the AST-Construction tools.

As a plus, it mostly reuses ANTLRs grammar file format, which was the format my grammar is in.

Answer 2

You might consider LRSTAR.

I have no experience with the tool itself, but I've met the author and he seems like a pretty competent guy. (I do build parsing engines and related technology for a living).

Answer 3

LRSTAR 10.0 is available now. On the comparison page, there is a comparison of LRSTAR, ANTLR and Bison. LRSTAR now reads ANTLR's style notation using the same EBNF operators (:, |, *, +, ?). It's a C++ based system generating LR(k) parsers in C++. The parsers do automatic AST construction and traversal. The new version 10.0 reads Yacc/Bison grammars if there is no action code in the grammar.