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.

Reputation: 5840

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

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.

Upvotes: 4

Answers (3)

user1524750

Reputation:

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.

Upvotes: 4

Ira Baxter

Reputation: 95316

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).

Upvotes: 4

Jost

Reputation: 5840

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.

Upvotes: 3

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

Answers (3)

Related Questions