Леворекурсивные PEG грамматики

Оригинал: ‘Left-recursive PEG Grammars’ by Guido van Rossum

Я упоминал о левой рекурсии как о камне преткновения несколько раз, и пришло время разобраться с этим. Основная проблема заключается в том, что парсер с лево-рекурсивным спуском мгновенно падает из-за переполнения стека.

Рассмотрим это гипотетическое правило грамматики:

expr: expr '+' term | term

Если бы мы реализовали в лоб этот фрагмент грамматики в метод лево-рекурсивного парсера, то получили бы что-то вроде следующего:

def expr():
    if expr() and expect('+') and term():
        return True
    if term():
        return True
    return False

Таким образом, expr() начинается с вызова expr(), который начинается с вызова expr(), который начинается с вызова… Это может закончиться только переполнением стека, выраженным как исключение RecursionError.

Традиционное решение - переписать грамматику. В предыдущих частях я сделал именно это. Фактически, приведённое выше грамматическое правило можно переписать следующим образом:

expr: term '+' expr | term

Однако, на шаге построения дерева разбора, его форма была бы другой. Это могло бы испортить ситуацию, если бы мы добавили оператор '-' в грамматику (так как a - (b - c) не то же самое как (a - b) - c). Это обычно решается с помощью более мощных функций PEG, таких как группировка и итерация, и мы могли бы переписать вышеприведённое правило как:

expr: term ('+' term)*

На самом деле именно так текущая грамматика Python и записывается для pgen парсера (у которого те же проблемы с леворекурсивными правилами).

Тем не менее, есть небольшая проблема: так как операторы типа '+' и '-' (в Python) являются в основном бинарными, то когда мы анализируем что-то вроде a + b + c, мы должны пройтись по результату парсинга (который по сути является списком ['a', '+', 'b', '+', 'c']) для создания леворекурсивного дерева разбора (которое будет выглядеть примерно так [['a', '+', 'b'] , '+', 'c']).

Оригинальная леворекурсивная грамматика уже намекает на желаемую ассоциативность, поэтому было бы неплохо генерировать парсер непосредственно из этой формы. И мы можем! Один из читателей указал мне на хороший трюк с математическим доказательством, которое было легко реализовать. Сейчас я постараюсь объяснить.

Давайте рассмотрим пример ввода foo + bar + baz. Дерево разбора, которое мы хотели бы получить из этого, соответствует (foo + bar) + baz. Для этого требуется три леворекурсивных вызова функции expr(): один соответствует оператору верхнего уровня '+' (т. е. второму); ещё один - внутреннему оператору '+' (т.е. первому); и третий - выбор второй альтернативы (то есть term).

Поскольку я плохо рисую реальные диаграммы с помощью специальных инструментов, я покажу это здесь, используя ASCII-арт:

expr------------+------+
  |              \      \
expr--+------+   '+'   term
  |    \      \          |
expr   '+'   term        |
  |            |         |
term           |         |
  |            |         |
'foo'        'bar'     'baz'

Идея состоит в том, что в функции expr() нам нужен «оракул», который сообщит нам, следует ли выбрать первую альтернативу (то есть рекурсивный вызов expr()) или вторую (то есть вызов term()). При первом вызове expr() оракул должен сказать нам идти по первой альтернативе (expr()); во втором (рекурсивном) вызове - аналогично, но при третьем он должен подсказать нам вызов term(). В коде это будет выглядеть так:

def expr():
    if oracle() and expr() and expect('+') and term():
        return True
    if term():
        return True
    return False

Как бы написать такого оракула? Давайте посмотрим… Мы могли бы попытаться отследить количество (леворекурсивных) вызовов expr() в стеке вызовов и сравнить его с количеством операторов '+' в следующем выражении. Если стек вызовов глубже, чем число операторов, оракул должен вернуть false (заставить нас выбрать term()). Мне уже не терпится реализовать это с помощью sys._getframe(), но есть лучший способ: давайте перевернем стек вызовов!

Идея в том, что мы начинаем с вызова, где оракул возвращает false, и сохраняем результат. Это дает нам последовательность expr() -> term() -> 'foo'. (Он должен возвращать дерево разбора для начального term, то есть 'foo'. Приведённый выше код просто возвращает True, но во второй части цикла статей я уже показывал, как вместо этого вернуть дерево разбора.) Такой оракул легко реализовать, так как он должен просто вернуть False при первом вызове - не требуется проверка стека или заглядывание в будущее.

Затем мы снова вызываем expr(), и на этот раз оракул возвращает True, но вместо леворекурсивного вызова expr() мы подставляем сохранённый результат из предыдущего вызова. А так как ожидаемый оператор '+' и следующий подходящий токен также присутствуют, это даст нам дерево разбора для foo + bar.

Ещё раз повторим алгоритм, и снова всё получается: на этот раз мы получаем дерево разбора для полного выражения, и оно действительно леворекурсивно ((foo + bar) + baz).

Затем мы снова повторяем алгоритм. Но в этот раз оракул хоть и возвращает True, и сохранённый результат предыдущего вызова также доступен, но больше нет оператора '+', и первая альтернатива завершается ошибкой. Таким образом, мы пробуем второй вариант, который успешно выполняется, и находит только начальный термин ('foo'). Этот результат хуже, чем тот, который получился от первой альтернативы, поэтому на этом этапе мы останавливаемся и сохраняем самый длинный разбор (т.е. (foo + bar) + baz).

Чтобы превратить это в рабочий код, я сначала немного изменил алгоритм, чтобы объединить вызов oracle() с леворекурсивным вызовом expr(). Давайте назовем это oracle_expr(). Код:

def expr():
    if oracle_expr() and expect('+') and term():
        return True
    if term():
        return True
    return False

Далее мы напишем враппер, который реализует логику, описанную выше. Он использует глобальную переменную (не волнуйтесь, я от неё позже избавлюсь). Функция oracle_expr() будет читать глобальную переменную, а враппер управлять ею:

saved_result = None

def oracle_expr():
    if saved_result is None:
        return False
    return saved_result

def expr_wrapper():
    global saved_result
    saved_result = None
    parsed_length = 0

    while True:
        new_result = expr()
        if not new_result:
            break
        new_parsed_length = <calculate size of new_result>
        if new_parsed_length <= parsed_length:
            break
        saved_result = new_result
        parsed_length = new_parsed_length
    return saved_result

Код, конечно, ужасен, но он хотя бы передаёт суть алгоритма. Давайте отрефакторим его так, чтобы им можно было гордиться.

Важнейшее понимание (которое принадлежит мне, хотя я, вероятно, не первый, кто заметил это) заключается в том, что мы можем использовать кэш мемоизации вместо глобальной переменной. В нём мы будем хранить результат от вызова к вызову. Так мы избавимся от отдельной функции oracle_expr(), т.к. сможем генерировать стандартный вызов expr() независимо от того, находится ли он в рекурсивной позиции слева или справа.

Итак, нам нужен отдельный декоратор @memoize_left_rec, который используется только для леворекурсивных правил. Он вызывает функцию oracle_expr(), вытаскивая сохраненное значение из кэша мемоизации, и содержит цикл, который вызывает функцию expr() несколько раз, пока каждый новый результат сопоставим со всё более длинной частью входных данных, чем предыдущий. И, конечно же, поскольку кэшируется отдельно каждая позиция ввода и каждый метод синтаксического анализа, его не беспокоят обратное отслеживание или несколько рекурсивных правил (например, в игрушечной грамматике, которую я использовал, и expr, и term являются леворекурсивными).

Ещё один из плюсов прототипа, который я создал в третьей части, заключается в том, что он позволяет легко проверить, является ли новый результат длиннее старого: метод mark() возвращает индекс в массиве входных токенов, поэтому мы можем просто использовать его вместо parsed_length.

Я опускаю доказательство того, почему этот алгоритм работает всегда, независимо от того, насколько безумна грамматика. На самом деле я его даже не читал. Я вижу, что это работает для простых случаев, таких как expr в моей игрушечной грамматике, а также для несколько более сложных случаев (например, с использованием левой рекурсии, скрытой за необязательными элементами в альтернативе, или с использованием взаимной рекурсии между несколькими правилами). Самая сложная ситуация, которую я могу припомнить в грамматике Python, всё равно решается этим алгоритмом, так что я просто доверюсь теореме и людям, которые её доказали.

Давайте уже напишем боевой код.

Во-первых, генератор парсера должен определить, какие правила являются леворекурсивными. Это решённая проблема в теории графов. Я не собираюсь здесь показывать алгоритм, и на самом деле даже хочу ещё больше упростить его. Я исхожу из предположения, что единственные леворекурсивные правила в грамматике являются непосредственно леворекурсивными, как expr в нашей игрушечной грамматике. Тогда для проверки левой рекурсивности нужно просто искать альтернативу, которая будет начинаться с имени текущего правила:

def is_left_recursive(rule):
    for alt in rule.alts:
        if alt[0] == rule.name:
            return True
    return False

Теперь мы изменим генератор парсера так, чтобы для леворекурсивных правил он генерировал другой декоратор. Напомним, что в третьей части мы обернули все методы парсера в @memoize. Теперь мы сделаем одно небольшое изменение в генераторе, чтобы для леворекурсивных правил мы использовали @memoize_left_rec, а затем реализуем магию в декораторе memoize_left_rec. Остальной генератор и прочий код не нуждаются в изменениях! (Хотя мне пришлось повозиться с кодом для визуализации)

Для справки, вот снова оригинальный декоратор @memoize, скопированный из части 3. Помните, что self - это экземпляр Parser, у которого есть атрибут memo (инициализированный пустым словарем) и методы mark() и reset(), которые получают и устанавливают текущую позицию токенизатора:

def memoize(func):
    def memoize_wrapper(self, *args):
        pos = self.mark()
        memo = self.memos.get(pos)
        if memo is None:
            memo = self.memos[pos] = {}
        
        key = (func, args)
        if key in memo:
            res, endpos = memo[key]
            self.reset(endpos)
        else:
            res = func(self, *args)
            endpos = self.mark()
            memo[key] = res, endpos
        return res

    return memoize_wrapper

Декоратор @memoize запоминает предыдущие вызовы для каждой позиции во входном потоке - для каждой позиции в (ленивом) массиве входных токенов есть отдельный словарь memo. Первые четыре строки функции memoize_wrapper посвящены получению правильного словаря memo.

А вот и @memoize_left_rec. Только ветка else слегка отличается от реализации в @memoize выше:

def memoize_left_rec(func):
    def memoize_left_rec_wrapper(self, *args):
        pos = self.mark()
        memo = self.memos.get(pos)
        if memo is None:
            memo = self.memos[pos] = {}

        key = (func, args)
        if key in memo:
            res, endpos = memo[key]
            self.reset(endpos)
        else:
            # Prime the cache with a failure.
            memo[key] = lastres, lastpos = None, pos
            # Loop until no longer parse is obtained.
            while True:
                self.reset(pos)
                res = func(self, *args)
                endpos = self.mark()
                if endpos <= lastpos:
                    break
                memo[key] = lastres, lastpos = res, endpos
            res = lastres
            self.reset(lastpos)
        return res

    return memoize_left_rec_wrapper

Вероятно, интересно как это сработает для метода expr(). Давайте проследим как будет выполняться следующий код:

    @memoize_left_rec 
    def expr(self):
        pos = self.mark()
        if ((expr := self.expr()) and
            self.expect('+') and
            (term := self.term())):
            return Node('expr', [expr, term])
        self.reset(pos)
        if term := self.term():
            return Node('term', [term])
        self.reset(pos)
        return None

На примере парсинга foo + bar + baz.

Всякий раз, когда вы вызываете функцию expr(), вызов «перехватывается» декоратором, который ищет предыдущий вызов в текущей позиции. При первом вызове мы попадаем в ветку else, где неоднократно вызываем декорируемую функцию expr(). Очевидно, что мы снова попадём сначала в декоратор, но вот на сей раз в кэше уже есть некоторое значение, так что рекурсия прерывается.

Что происходит дальше? Начальное значение кэша вычисляется в этой строке:

            # Prime the cache with a failure.
            memo[key] = lastres, lastpos = None, pos

Это приводит к тому, что оформленный expr() возвращает None, после чего первый if в expr() падает (при expr: = self.expr()). То есть, мы переходим ко второму if, который успешно распознает term (в нашем примере 'foo') и expr возвращает экземпляр Node. Куда мы возвращаемся? К циклу while в декораторе. Обновляем кэш мемоизации новым результатом (тот экземпляр Node), а затем запускаем следующую итерацию.

expr() вызывается снова, и на этот раз перехваченный рекурсивный вызов возвращает кэшированный экземпляр Node (терм), а далее переходит к вызову expect('+'). Всё в порядке, так как мы сейчас на первом операторе '+'. После этого мы ищем терм, что также нам удаётся (нашли 'bar').

Так что теперь expr(), уже распознав foo + bar, возвращается к циклу while, который выполняет те же действия: он обновляет кэш мемоизации новым (более длинным) результатом и запускает следующую итерацию.

Эта игра повторяется снова. Опять же, перехваченный рекурсивный вызов expr() извлекает новый результат (на этот раз foo + bar) из кэша, и мы ожидаем встретить ещё один '+' (второй) и другой term ('baz'). Мы создаем Node, представляющий (foo + bar) + baz, и возвращаем его в цикл while, который помещает это в кэш и повторяет ещё раз.

Но теперь мы пойдём по другой ветке алгоритма. Мы ожидаем встретить ещё один '+', но не находим его! Таким образом, этот вызов expr() возвращается к своей второй альтернативе, и возвращает всего лишь term. Когда это всплывает до цикла while, оказывается, что этот результат короче, чем последний. Так что он прерывается и возвращает более длинный результат ((foo + bar) + baz) тому, кто инициировал вызов expr() (например, вызов statement() - здесь не показан).

Итак, на этом сегодняшняя история заканчивается: мы успешно реализовали левую рекурсию в PEG парсере. На следующей неделе я планирую обсудить добавление «действий» в грамматику, что позволит нам настроить результат, возвращаемый методом парсера для данной альтернативы (вместо того, чтобы всегда возвращать экземпляр Node).

Если вы хотите поиграть с кодом, посмотрите репозиторий GitHub. (Я также добавил код визуализации для левой рекурсии, но я не вполне им доволен, поэтому не буду здесь приводить на него ссылку.)

Лицензия на эту статью и приведенный код: CC BY-NC-SA 4.0