java - 支持歧义的 Java CFG 解析器

Question

我正在寻找用 Java 实现的 CFG 解析器。问题是我正在尝试解析一种自然语言。而且我需要所有可能的解析树（歧义），而不仅仅是其中之一。我已经研究过很多 NLP 解析器，比如斯坦福解析器。但是它们主要需要统计数据（我没有的树库），并且很难将它们改编成新的语言，而且文档记录也很差。我发现了一些解析器生成器，例如 ANTRL 或 JFlex，但我不确定它们能否处理歧义。那么哪个解析器生成器或 java 库最适合我呢？提前致谢

Answer 1

您需要一个使用 Earley 算法的解析器。我没有使用这两个库中的任何一个，但是PEN和PEP似乎在 Java 中实现了这个算法。

Answer 2

另一种选择是Bison，它实现了GLR。GLR 是一种支持歧义语法的 LR 类型解析算法。除了 C++ 之外，Bison 还生成 Java 代码。

Answer 3

看看这里的相关讨论。在我对该讨论的最后评论中，我解释说，您可以通过在推导失败之前克隆到目前为止派生的解析树来使任何解析器生成器生成所有解析树。

如果你的语法是：

G -> ...

你会增加是这样的：

G' -> G {semantic:deal-with-complete-parse-tree} <NOT-VALID-TOKEN>.

解析引擎最终将在所有派生上失败，但您的程序将要么：

• 保存所有树木的克隆。
• 在发现每棵树时处理它们的语义。

ANTLR 和 JavaCC 在我教学时都做得很好。我更喜欢 ANTLR，因为它的 BNF 词法分析，以及它不那么复杂的历史、愿景、y 和许可。