使用迭代重写递归 BNF 规则

Question

查看以下递归 BNF 规则

(1) X = Xa | b

这会产生这样的句子

X = b
X = ba
X = baa
X = baaa
...

这可以写成

(2) X = b a*

其中右侧不是递归的

现在看看下面的递归 BNF 规则

(3) X = { X } | b

这会产生这样的句子

X = b
X = {b}
X = {{b}}
X = {{{b}}}
...

有没有办法以非递归的方式重写规则（3），类似于我们将规则（1）重写为规则（2）时所做的那样。

请注意，X = {* b }* 不好，因为括号需要平衡。

Answer 1

我不知道

上面的问题是否可以回答。上面问题的原因是我想避免在我的解析器（用 Java 编写）中无限循环。一种方法是确保 BNF 规则不是递归的，因此我的问题。但另一种方法是使用递归规则，但避免我的（Java）程序中的无限循环。事实证明，您可以通过延迟实例化来避免循环。

例如，查看以下规则：

expression = term ('+' term)*;
term       = factor ('*' factor)*;
factor     = '(' expression ')' | Num;

表达式（） 调用 term（），它调用 factor（），后者调用表达式（），因此我们最终可以得到无限循环。为了避免这种情况，我们可以使用延迟实例化，因此不要编写类似以下内容的内容：

public Parser expression() {
    expression = new ...
    return expression;
}

我们改为写：

public Parser expression() {
    if (expression == null) {
        expression = new ...
    }
    return expression;
}

请注意，您必须将表达式声明为实例变量才能使其正常工作。