LR(k) or LALR(k) parser generator with features similar to ANTLR
-
28-06-2021 - |
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.
Solution 3
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.
OTHER TIPS
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).
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.