关于递归下降解析器的复杂性 [英] On complexity of recursive descent parsers

问题描述

众所周知，在某些情况下，递归下降解析器可能需要指数时间.谁能指出我的样本，发生在哪里?对PEG案例特别感兴趣(即优先选择).

It's known that recursive descent parsers may require exponential time in some cases; could anyone point me to the samples, where this happens? Especially interested in cases for PEG (i.e. with prioritized choices).

推荐答案

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

It's because you can end up parsing the same things (check the same rule at the same position) many times in different recursion branches. It's kind of like calculating the n-th Fibonacci number using recursion.

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)第二次失败，并且我们不会再遍历整个子树.我不想写出全部内容，但是您可以看到它会重复相同的子树很多次.

* - where we parse a rule at the same position where we have already parsed it in a different branch. If we had saved the results - which rules fail at which positions - we'd know xA(xyxyy) fails the second time around and we wouldn't go through its whole subtree again. I didn't want to write out the whole thing, but you can see it will repeat the same subtrees many times.

何时会发生-当您有许多重叠的转换时.优先选择不会改变一切-如果最低优先级规则最终成为唯一正确的规则(或者没有正确的规则)，则无论如何您都必须检查所有规则.

When it will happen - when you have many overlapping transformations. Prioritized choice doesn't change things - if the lowest priority rule ends up being the only correct one (or none are correct), you had to check all the rules anyway.

这篇关于关于递归下降解析器的复杂性的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！