词法分析和语法分析工具

Question

我正在寻找除了Flex或Bison之外的词法分析和解析器生成实用程序。要求如下：

• 使用上下文无关的LL(*)或GLR语法规定解析器。我也会考虑PEG。
• 与一种编程语言紧密集成，可用于脚本编写和应用开发。该语言还应具有便于与C进行接口的功能。很好的例子是Python、Ruby和Guile。不要使用C、Java或Perl。我希望语言是同质的；我想让解析器生成器输出相同语言的代码。
• 文档完善且达到生产级别。
• 开源。免费也是可取的（尽管不是必需的）。
• 兼容Linux发行版或其中一个开源BSD。我会考虑OpenSolaris。
• 快速开发比效率更重要。
• 适用于解析自然语言以及形式语言。自然语言解析仅限于短小简单的句子，几乎没有歧义。

我已经留意了ANTLR，尽管我从未使用过。欢迎提供相关评论。请告诉我您最喜欢的符合这些要求的实用程序，并说明为什么会推荐它们。

- Jerrad Genson

---

关于http://pyparsing.wikispaces.com/Introduction或者http://www.dabeaz.com/ply/，你觉得怎么样？ - GWW

考虑到您的限制，使用flex/bison有什么异议吗？ - Ira Baxter

每个LALR语法在定义上都是LR语法。此外，坚持使用LR而不是LALR解析器生成器通常会使您获得巨大的表格，但并没有太多额外的实际好处。所以我不确定为什么你坚持使用非LALR解析器生成器。如果你只关注为Python、Ruby、Guile生成代码，那么我更理解了。顺便说一句，我认为ANTLR没有生成任何这些内容。但我仍然感到困惑：如果你选择的语言“容易与C接口”（例如Python），bison仍然是一个很好的选择：只需使用你的语言调用Bison生成的C代码即可。 - Ira Baxter

我的经验是使用Bison和LALR语法，但这次它们不能满足我的需求；我正在寻找一种具有更具表现力语法的工具。 我原本认为一个典型的LR或LL(*)语法就可以胜任。 然而，现在似乎GLR语法可能是更好的选择。 至于这些解析器所涉及的语言，它们将作为基础程序的扩展框架的一部分生成，该基础程序是用C编写的。 我希望扩展语言是同质的，并且不想使用C。ANTLR能够生成Python。 - Jerrad Genson

Answer 1

这里有一份现代的Packrat解析器列表（点击此处）。

- SK-logic

---

我认为OP需要使用无上下文语法，而PEG似乎不属于这一类。不过，也许OP会发现PEGs可接受。 - C. K. Young

任何无上下文的LL(*)或LR都可以用PEG表示，因此在实践中这种差异并不重要。基于自动机的解析器生成器不太适合OP的第二个要求，而PEG可以轻松地集成到几乎任何语言中。 - SK-logic

Answer 2

NL文本往往存在大量的歧义。如果你想解析自然语言，我认为传统的编译器类型解析器生成器（如LALR、LL [包括ANTLR]）都不会对你有太大帮助，而且编译器类型的解析器生成器通常根本不处理这个问题。

一个能够处理歧义的GLR解析器可能会有所帮助；bison提供了这个选项。

- Ira Baxter

Answer 3

Guile 2.0（将在几天内发布）具有LALR（1）解析库。

- C. K. Young