java - 如何在 Java 中表示上下文无关文法？

Question

我有一个简单的语法：

R --> R and R | R or R | atom

我们唯一的终端是atom。这是一种递归语法，因为每个 R 都可以由嵌套的 R 组成。我面临的问题是：

1. 如何处理递归？
2. 如何构建可以通过 3 条规则之一解决的 java 类 R？

你会如何用 Java 类来表示这个语法？

Answer 1

最简单的方法是将所有规则标准化为单个选择，然后将它们表示为数组数组。

首先，我们为语法中的每个“原子”（令牌）分配一个唯一的代码。

然后，规则都应该被规范化为

LHS -->  RHS1 RHS2 ... RHSn

例如，来自的规则：a --> b | c 应该被规范化为两个规则， a --> b 和 a --> c 。如果您有其他花哨的符号 EBNF 设备，例如 kleene start 或 plus，您也可以对它们进行规范化。

现在你有 K 条规则；您可以定义一个包含 K 个插槽的数组，每个插槽包含一个规则。一个规则槽包含一对：一个 LHS，以及该规则的大小为 n 的数组。（更简单：一个规则槽保存一个大小为 n+1 的数组，最左边的元素索引 0 保存 LHS，索引 1 保存 RHS1，等等）。

现在您有了用 Java 表示的语法。

[递归是语法的语义属性，而不是它的表示。]

另一种选择：如果您为 BNF 构建经典解析器（毕竟，(E)BNF 也有语法），您可以使用解析器解析您的 BNF，并为此构建一棵树。这显然也是一种表象。作为要处理的数组数组并不方便。