递归下降解析器的复杂性

Question

众所周知，递归下降解析器在某些情况下可能需要指数时间；有人能给我指出这种情况的示例吗？特别是对于PEG（即具有优先选择的情况）感兴趣。

- fithu

---

只有他们回溯才能达到真正的“LL(1)”风格，如果他们继续从左到右前进，复杂度应该是O(N)。 - user207421

@EJP，显然。但即使回溯，在大多数情况下也不会引入指数复杂度。我正在尝试弄清楚在什么情况下会发生这种情况。 - fithu

并非所有递归下降解析器都会表现出指数行为。例如，ANTLR 4生成具有[半]优先选择的递归下降解析器，但最坏情况下是O(n⁴)（证明是我目前正在研究的一篇论文的一部分）。 - Sam Harwell

Answer 1

任何自顶向下的解析器，包括递归下降解析器，在输入和语法需要大量回溯时理论上都可能变成指数级。如果语法是这样的，即决策性选择放在长序列的末尾，就会发生这种情况。例如，如果您有一个符号像 & 表示“所有以前的减号实际上是加号”，然后有数据像 “((((a-b)-c)-d)-e&)”，那么解析器必须向后移动并将所有加号更改为减号。如果按照这些方式开始创建嵌套表达式，则可以创建一个有效的非终止输入集。

您必须意识到，您正在涉及一个政治问题，因为现实情况是，大多数正常的语法和数据集并不是这样的，但是有很多人系统地抹黑递归下降，因为它不容易自动化。所有早期的解析器都是 LALR，因为它们比 RD 更容易自动生成。所以发生的事情是，每个人都写了 LALR，并且抹黑了 RD，因为在过去，制作 RD 的唯一方法是手工编码。例如，如果您读龙书，您会发现 Aho&Ullman 只写了一段关于 RD 的话，基本上只是一次意识形态的攻击，说“RD 很糟糕，不要这么做”。

当然，如果您开始手工编写 RD（就像我），您会发现它们比 LALR 更好，原因有很多。在过去，您总是可以告诉一个手工编码的 RD 编译器，因为它具有有意义的错误消息和位置精度，而具有 LALR 的编译器会显示错误发生在真正位置的 50 行处。事情已经发生了很大变化，但是当您开始阅读关于 RD 的 FUD 时，应该意识到它来自“某些圈子”内长期以来对 RD 进行口头抨击的传统。

- Tyler Durden

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) 第二次失败，我们就不会再遍历它的整个子树了。我不想把整个过程都写出来，但你可以看到它会重复很多次相同的子树。

这种情况发生的时候是当您有许多重叠的转换时。优先选择不会改变任何东西-如果最低优先级规则最终成为唯一正确的规则（或没有正确的规则），则必须检查所有规则。

- svinja