将 BNF 语法转换为 Java

Convert BNF grammar to Java

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

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

这个问题并不是说我必须使用什么工具来解析语法(比如Javacc或Antlr),而是model这个简单语法的方法使用面向对象范式。

这是一个非常宽泛的问题,无需实际提及特定工具即可回答,因为任何语法的实现都可能以多种方式发生,具体取决于您选择在哪种语言中实现解析器...如果您查看你提到的 ANTLR 和 Javacc 等工具的来源,它将揭示其他人如何实现他们的工具以及他们用来开发自上而下的解析器等的技术,但仅仅因为他们如何实现他们的工具并不意味着它必然是唯一的方法。

BNF 仅用于提供描述语言结构的正式方式:

They are applied wherever exact descriptions of languages are needed: for instance, in official language specifications, in manuals, and in textbooks on programming language theory.

因为它们仅用于分解输入的预期内容,由程序员决定如何使用语言工具实现以及 api 他们是否可以使用它java 中的正则表达式或另一种语言提供的字符串搜索或标记化,不幸的是,这完全是您的选择,除非您正在使用专门为您的语言生成解析器的工具,此时我们可以回答这个问题,如果它有意义的话.

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

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

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

到那时它真的取决于你想用 AST 做什么。例如,如果您想根据提供的输入来评估表达式,您可以将抽象方法 evaluate 添加到 ASTNode 类型,然后让每个派生类型提供执行适当操作的实现.您还可以考虑使用访问者模式来构建遍历 AST 并在每一步执行适当操作的访问者。

我不确定这是否有帮助,但前一段时间我写了一些与您正在查看的内容非常相似的内容,为我经常教的 class 生成命题逻辑的真值表。该工具本身是 available here, and the source files, which are decently well-commented, are available here。它是用 JavaScript 而不是 Java 编写的,但它展示了上面描述的所有部分 - AST 节点类型,shunting-yard 算法进行解析,以及重写的方法来评估不同的表达式。