如何在Java中表示一种上下文无关文法？

Question

我有一个简单的语法：

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

我们唯一的终端是原子。 这是一个递归语法，因为每个R可以被嵌套R. 由我所面临的问题是：

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

您如何用Java类表示这种语法？

Answer 1

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

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

然后，规则都应该被归为

LHS --> RHS1 RHS2 ... RHSn 

e.g，规则由：甲 - >乙| c应该被规范化为两个规则，a - > b和a - > c。如果您有其他奇特的符号EBNF设备，例如kleene start或plus，您也可以对它们进行标准化。

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

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

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

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