java - 用于 Java 的 Earley 解析器生成器

Question

我正在寻找 Earley parser能够生成 Java 输出代码的生成器，即为词法分析器和解析器生成 Java 代码，并允许包含操作(实现为 Java 代码)为语法规则执行。

我查看了两个生成 Java 代码的 Earley 解析器生成器(Pep 和 PEN)但它们似乎都不允许将 Action 嵌入到语法中。

Answer 1

如果我理解你的问题，“在语法中嵌入 Action ”是指在语法中插入语义 Action ，以便它们“内联”执行(例如，在解析阶段，当输入被解析时)。

Earley 解析器不适合这种情况，因为它们允许任何 上下文无关语言语法(甚至是有歧义的语法)。请参阅:http://en.wikipedia.org/wiki/Earley_algorithm

基本上:对于给定的执行和给定的状态，Earley 解析器包含所有 可能的解析状态。传统的方法(例如 Yacc/Bison)是在规则或部分输入匹配后执行语义操作。但是当解析一个有歧义的语法时(例如，有 Reduce/Reduce 冲突的语法)，Earley 解析器将处理这两种“归约”，并且由于它的歧义，不知道应该执行哪个 Action 。

使用 Earley 解析器的通常方法是解析输入并最终得到一个森林的解析树，稍后您可以在其上执行所需的操作(例如，丢弃那些您知道无效的，或者对其应用一些语义操作或转换)。

然而，有一些关于这个主题的研究试图内联执行一些 Action (抱歉，只找到这个链接)https://link.springer.com/article/10.1007/s00236-009-0107-6