LR(k)或LALR(k)解析器生成器，具有类似于ANTLR的功能。

Question

我目前正在编写一个某种语言的解析器。我已经得到了这种语言的语法，但是这个语法有一些左递归和非LL(*)结构，所以即使使用回溯，ANTLR也无法很好地处理。

因为去除这些左递归和非LL(*)结构比起初看来更难，所以我现在想尝试一个LR(k)或LALR(k)解析器生成器。k值越高越好。

有人能推荐符合这些要求的解析器生成器吗？

• 最好是生成LR(k)解析器，其中k值高（甚至任意），或者至少是生成LALR(k)解析器，其中k值较高。
• 生成的解析器使用C或C++编写，并且如果使用C编写，则可以连接到C++代码。
• 类似于ANTLR的功能集（特别是AST重写）将是不错的选择。
• 性能不是最紧迫的问题，生成的解析器旨在用于具有大量内存和CPU功率的台式机。

谢谢和问候， 乔斯特

注：我并不是因为我不能自己搜索而问问题，而是因为没有时间测试一些解析器生成器。因此，如果您有使用推荐的解析器生成器的经验，请回答。

- Jost

Answer 1

LRSTAR 10.0现已发布。在比较页面上，有LRSTAR、ANTLR和Bison的比较。LRSTAR现在使用与ANTLR相同的EBNF运算符（：、|、*、+、?）读取ANTLR的样式表示法。它是一个基于C++的系统，在C++中生成LR(k)解析器。解析器进行自动AST构建和遍历。如果语法中没有操作代码，新版本10.0将读取Yacc/Bison语法。

- user1524750

---

.org链接已损坏，但仍可在sourceforge上找到，谢谢提供信息。 - Fernando Gonzalez Sanchez

一个旧版本的发行版仍然可以在这里找到：http://download.cnet.com/LRSTAR-Parser-Lexer-Generator/3001-2069_4-94121.html。它包括一些示例语法。 - J Evans

LRSTAR在https://sourceforge.net/projects/lrstar/上。 - Paul B Mann

Answer 2

你可以考虑使用LRSTAR。

我对这个工具本身没有经验，但我见过作者，他看起来是一个相当能干的人。（我从事构建解析引擎和相关技术的工作）。

- Ira Baxter

---

LRStar在sourceforge上的描述看起来非常有前途，但svn存储库中没有文件，网站上也没有任何内容... - Jost

实际上，这更像是由于法律问题或其他原因而被下架，因为真的很难找到任何可下载的LRStar发行版...它甚至在大多数下载站点上都被删除了，我能找到的只有一些Windows二进制文件，但我的工作环境是Linux。 - Jost

@Jost：LRStar的作者刚刚通知我，分发文件以及整个网站已经重新上线。记得备份一下 :) - Seki

LRSTAR v10.0现已发布。进行了许多改进。如果语法中没有代码，它可以读取Yacc/Bison语法。 - user1524750

LRSTAR在https://sourceforge.net/projects/lrstar/上。 - Paul B Mann

Answer 3

我现在决定使用DParser，它是一个GLR-Parser生成器，能够识别任何上下文自由语言。它似乎编程良好（查看源代码分发中的测试），但缺少许多ANTLR提供的功能，尤其是AST构建工具。

另外，它大多重用ANTLR的语法文件格式，这也是我的语法所在的格式。

- Jost