众所周知,递归下降解析器在某些情况下可能需要指数时间;有人能给我指出这种情况的示例吗?特别是对于PEG(即具有优先选择的情况)感兴趣。
众所周知,递归下降解析器在某些情况下可能需要指数时间;有人能给我指出这种情况的示例吗?特别是对于PEG(即具有优先选择的情况)感兴趣。
您必须意识到,您正在涉及一个政治问题,因为现实情况是,大多数正常的语法和数据集并不是这样的,但是有很多人系统地抹黑递归下降,因为它不容易自动化。所有早期的解析器都是 LALR,因为它们比 RD 更容易自动生成。所以发生的事情是,每个人都写了 LALR,并且抹黑了 RD,因为在过去,制作 RD 的唯一方法是手工编码。例如,如果您读龙书,您会发现 Aho&Ullman 只写了一段关于 RD 的话,基本上只是一次意识形态的攻击,说“RD 很糟糕,不要这么做”。
当然,如果您开始手工编写 RD(就像我),您会发现它们比 LALR 更好,原因有很多。在过去,您总是可以告诉一个手工编码的 RD 编译器,因为它具有有意义的错误消息和位置精度,而具有 LALR 的编译器会显示错误发生在真正位置的 50 行处。事情已经发生了很大变化,但是当您开始阅读关于 RD 的 FUD 时,应该意识到它来自“某些圈子”内长期以来对 RD 进行口头抨击的传统。
这是因为在不同的递归分支中可能会多次解析相同的内容(在相同的位置检查相同的规则)。这有点类似于使用递归计算第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) 第二次失败,我们就不会再遍历它的整个子树了。我不想把整个过程都写出来,但你可以看到它会重复很多次相同的子树。
这种情况发生的时候是当您有许多重叠的转换时。优先选择不会改变任何东西-如果最低优先级规则最终成为唯一正确的规则(或没有正确的规则),则必须检查所有规则。