algorithm - 关于递归下降解析器的复杂性

Question

众所周知，递归下降解析器在某些情况下可能需要指数时间。任何人都可以指出我的样本，这发生在哪里？对 PEG 的案例（即优先选择）特别感兴趣。

Answer 1

如果输入和语法的组合使得需要大量回溯，则任何自上而下的解析器，包括递归下降，理论上都可以成为指数。如果语法使得决定性选择放在长序列的末尾，就会发生这种情况。例如，如果你有一个类似 & 的符号，意思是“所有以前的减号实际上都是加号”，然后有类似“((((a - b) - c) - d) - e &)”的数据，那么解析器必须去倒退并将所有优点变为缺点。如果您开始按照这些思路创建嵌套表达式，您可以创建一个有效的非终止输入集。

您必须意识到您在这里介入了一个政治问题，因为现实情况是大多数正常的语法和数据集都不是这样的，但是，有很多人系统地骂递归下降，因为很难进行 RD自动地。所有早期的解析器都是 LALR，因为它们比 RD 更容易自动生成。所以发生的事情是每个人都只写了 LALR 和 RD，因为在过去，制作 RD 的唯一方法是手动编码。例如，如果你读龙书，你会发现 Aho & Ullman 在 RD 上只写了一段，基本上只是一个意识形态的删除，说“RD 不好，不要做”。

当然，如果您开始手动编码 RD（就像我一样），您会发现由于各种原因它们比 LALR 好得多。在过去，您总是可以告诉编译器具有手动编码的 RD，因为它具有位置准确的有意义的错误消息，而具有 LALR 的编译器会显示错误发生在距离实际位置 50 行的地方。与过去相比，情况发生了很大变化，但您应该意识到，当您开始阅读 RD 上的 FUD 时，它来自于“某些圈子”中口头诋毁 RD 的悠久传统。

Answer 2

这是因为您最终可以在不同的递归分支中多次解析相同的内容（检查相同位置的相同规则）。这有点像使用递归计算第 n 个斐波那契数。

Grammar:

A -> xA | xB | x
B -> yA | xA | y | A
S -> A

Input:
xxyxyy

Parsing:
xA(xxyxyy)
    xA(xyxyy)
        xA(yxyy) fail
        xB(yxyy) fail
        x(yxyy) fail
    xB(xyxyy)
        yA(yxyy)
            xA(xyy)
                xA(yy) fail
                xB(yy) fail
                x(yy) fail
            xB(xyy)
                yA(yy)
                    xA(y) fail
                    xB(y) fail
                    x(y) fail
                xA(yy) fail *
            x(xyy) fail
        xA(yxyy) fail *
        y(yxyy) fail
        A(yxyy)
            xA(yxyy) fail *
            xB(yxyy) fail *
            x(yxyy) fail *
    x(xyxyy) fail
xB(xxyxyy)
    yA(xyxyy) fail
    xA(xyxyy) *
        xA(yxyy) fail *
        xB(yxyy) fail *
        ...

*- 我们在相同的位置解析规则，我们已经在不同的分支中解析了它。如果我们保存了结果——哪些规则在哪些位置失败——我们会知道 xA(xyxyy) 第二次失败，我们不会再遍历它的整个子树。我不想写出整个事情，但你可以看到它会多次重复相同的子树。

何时发生 - 当您有许多重叠的转换时。优先选择不会改变事情 - 如果最低优先级规则最终成为唯一正确的规则（或没有一个是正确的），那么无论如何您都必须检查所有规则。