java - 将 BNF 语法转换为 Java

Question

如何将这个简单(递归)语法转换为 Java？

C --> a | not C | C and C | C or C ;

这个问题并不是指我必须使用什么工具来解析语法(例如 Javacc 或 Antlr)，而是如何使用面向对象范例来建模这个简单的语法。

Answer 1

我认为没有单一的方法可以使用 OOP 对此进行建模，并且有许多同样有效的方法可以解决这个问题。以下是一种合理的策略，用于思考这在代码中可能是什么样子。

通常，在解析表达式时，您的目标是为输入重建抽象语法树。该树结构根据可能的不同产生式具有不同类型的节点，在 Java 中，您可能会用某种多态类型来表示它们。例如，您可能有一个基类 ASTNode，它具有子级 ANode、NotNode、AndNode 和 >OrNode。最后三种类型将存储指向构成复合表达式的子表达式的指针。

一旦有了这些类型，您就需要组合某种解析器 - 可能还有扫描器 - 它将获取输入并从中构造适当的树。由于您正在查看由具有不同优先级的不同运算符组成的语法，因此您可以使用简单的优先级解析器，例如 Dijkstra's shunting-yard algorithm进行解析。该算法的实现相对简单。

此时，这实际上取决于您想要使用 AST 做什么。例如，如果您想根据提供的输入来计算表达式，您可以向 ASTNode 类型添加一个抽象方法 evaluate ，然后让每个派生类型提供一个执行适当操作的实现。您还可以考虑使用访问者模式来构建遍历 AST 并在每个步骤执行适当操作的访问者。

我不确定这是否有帮助，但不久前我写了一些与您正在为我经常教的类(class)生成命题逻辑真值表的内容非常相似的内容。该工具本身是available here ，并且注释得很好的源文件是 available here 。它是用 JavaScript 而不是 Java 编写的，但它展示了上述所有部分 - AST 节点类型、用于解析的分流场算法以及用于评估不同表达式的重写方法。