java - Java 的 Earley 解析器生成器

Question

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

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

Answer 1

如果我理解您的问题，“在语法中嵌入动作”是指在语法中插入语义动作，以便它们“内联”执行（例如，在解析阶段，因为正在解析输入）。

Earley 解析器不适合这种情况，因为它们允许任何 上下文无关的语言语法（甚至是模棱两可的语法）。见：http ://en.wikipedia.org/wiki/Earley_algorithm

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

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

然而，有一些关于这个主题的研究试图内联执行一些动作（对不起，只找到这个链接）https://link.springer.com/article/10.1007/s00236-009-0107-6

Answer 2

它们似乎都不允许将动作嵌入到语法中。

一般来说，将动作直接嵌入到语法中并不是一个好主意。最好将动作与语法分离。

Answer 3

不确定这是否是一个答案，但我经常使用的扫描仪生成器之一是JFlex，它输出 Java 代码。

它与CUP密切合作，后者在操作方面更接近一些。