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

Question

众所周知,递归下降解析器在某些情况下可能需要指数时间; 谁能指点我的样品,这会发生什么？特别感兴趣的是PEG的情况(即优先选择).

Answer 1

这是因为您可以在不同的递归分支中多次解析相同的事物(在相同位置检查相同的规则).这有点像使用递归计算第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)第二次失败,我们不会再次通过它的整个子树.我不想写出整件事,但你可以看到它会多次重复相同的子树.

当它发生时 - 你有很多重叠的转换.优先选择不会改变事物 - 如果最低优先级规则最终成为唯一正确的规则(或者没有一个是正确的),则必须检查所有规则.

Answer 2

如果输入和语法的组合使得需要大量的回溯,那么任何自上而下的解析器(包括递归下降)理论上可以成为指数.如果语法使得确定性选择被放置在长序列的末尾,则会发生这种情况.例如,如果你有一个符号,意思是"所有以前的弊端实际上都是加号"然后有像"(((((a - b) - c) - d) - e&)这样的数据"那么解析器必须去向后并将所有加分变为最小.如果您开始沿这些行创建嵌套表达式,则可以创建一个有效的非终止输入集.

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

当然,如果你开始手工编写RD(就像我一样)你会发现它们比LALR好得多,原因有很多.在过去,你总是可以告诉编译器有一个手工编码的RD,因为它有定位精度的有意义的错误消息,而具有LALR的编译器会显示错误发生的距离实际上是50行.自从过去以来,情况已经发生了很大的变化,但是你应该意识到,当你开始阅读RD上的FUD时,它就是在"某些圈子"中口头诋毁RD的长期传统.