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，并为其构建一棵树。这显然也是一种表象。作为数组的数组来处理并不方便。