О сложности рекурсивных парсеров

Ответ 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) не работает во второй раз, и мы больше не будем проходить через все это поддерево. Я не хотел выписывать все это, но вы можете видеть, что он будет повторять те же поддеревья много раз.

Когда это произойдет - когда у вас много перекрывающихся преобразований. Приоритетный выбор не меняет вещи - если правило с наименьшим приоритетом становится единственным правильным (или ни один из них не является правильным), вам все равно нужно было проверить все правила.

Ответ 2

Любой анализатор сверху вниз, включая рекурсивный спуск, теоретически может стать экспоненциальным, если комбинация ввода и грамматики такова, что необходимы большие числа обратных путей. Это происходит, если грамматика такова, что определительный выбор помещается в конце длинных последовательностей. Например, если у вас есть символ, похожий и означающий "все предыдущие минусы на самом деле плюсы", а затем данные такие как "((((a - b) - c) - d) - e &)", то парсер должен вернуться назад и изменить все плюсы на минусы. Если вы начинаете делать вложенные выражения вдоль этих строк, вы можете создать эффективный без конца набор входных данных.

Вы должны понять, что здесь вы вступаете в политическую проблему, потому что реальность такова, что большинство нормальных грамматик и наборов данных не похожи на это, однако есть много людей, которые систематически ошибаются в рекурсивном росте, потому что это непросто сделать RD автоматически. Все ранние парсеры являются LALR, потому что их намного проще сделать автоматически, чем RD. Так случилось, что все просто писали LALR и badmouthed RD, потому что в прежние времена единственным способом сделать RD было его кодирование вручную. Например, если вы прочитаете книгу драконов, вы обнаружите, что Ахо и Ульман пишут только один абзац о RD, и это в основном просто идеологический демонтаж, говорящий: "RD плох, не делайте этого".

Конечно, если вы начнете ручное кодирование RD (как и я), вы обнаружите, что они намного лучше LALR по разным причинам. В прежние времена вы всегда могли сказать компилятору, у которого был ручной RD, потому что он имел значимые сообщения об ошибках с точностью локации, тогда как компиляторы с LALR отображали ошибку, имеющую место в 50 строк от того места, где она была на самом деле. С тех пор многое изменилось, но вы должны понимать, что, когда вы начинаете читать FUD на RD, это происходит из длинной давней традиции словесного обхода RD в "определенных кругах".