Реализация остальных возможностей PEG

После того, как я собрал все части генератора PEG-парсеров воедино в предыдущем посте, я готов показать как реализовать и некоторые другие интересные штуки.

Мы рассмотрим следующие фичи PEG:

• Именованные элементы: NAME=item (имя можно использовать в экшене)
• Lookaheads: &item (положительный) и !item (отрицательный)
• Группировка элементов в скобках: (item item ...)
• Опциональные элементы: [item item ...] и item?
• Повторяющиеся предметы: item* (ноль или более) и item+ (один или несколько)

Именованные аргументы

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

expr: term '+' term

Мы можем сосылаться на второй term, добавляя цифру 1 к имени переменной, чтобы в экшене получилось так:

expr: term '+' term { term + term1 }

Но это не всем нравится, и лично я предпочел бы написать что-то вроде такого:

expr: left=term '+' right=term { left + right }

Это легко поддержать в мета-грамматике, изменив правило для item следующим образом:

item:
    | NAME = atom { NamedItem(name.string, atom) }
    | atom { atom }
atom:
    | NAME { name.string }
    | STRING { string.string }

(Где atom это просто старый item)

Это требует от нас добавления определения класса NamedItem в grammar.py. Он является ещё одним из тех классов данных, о которых я уже говорил ранее — у него тоже есть атрибуты name и item.

Нам также нужно внести небольшие изменения в генератор кода, которые я оставлю в качестве упражнения для читателя (или вы можете заглянуть в мой репозиторий :-). Сгенерированный код теперь назначит результат сопоставления каждого элемента переменной с указанным именем, а не с именем, полученным из названия правила элемента. Это также сработает для элементов, которые являются токенами (либо формы NAME, либо строковых литералов, таких как ':=').

Lookahead

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

На самом деле, lookahead можно использовать в качестве более изящного способа устранения путаницы с исключениями парсера, о которых я писал в предыдущей статье. Вместо того, чтобы разрешать экшенам отклонять уже принятую альтернативу, возвращая None, мы можем добавить перед OP инструкцию для исключения "}". Старое правило выглядело так:

    | OP { None if op.string in ("{", "}") else op.string }

Новая версия выглядит так:

    | !"}" OP { op.string }

Это переносит обработку фигурной скобки из экшена в грамматику, где ей и место. Нам не нужно проверять "{", так как она соответствует более ранней альтернативе (на самом деле это верно и для старой версии, но я об этом забыл :-).

Мы добавляем грамматику для lookaheads в правило для item следующим образом:

item:
    | NAME = atom { NamedItem(name.string, atom) }
    | atom { atom }
    | "&" atom { Lookahead(atom, True) }
    | "!" atom { Lookahead(atom, False) }

Ещё раз, мы должны добавить датакласс Lookahead в grammar.py (и импортировать его в @subheader!) И немного изменить генератор, добавив в него следующий вспомогательный метод:

    def lookahead(self, positive, func, *args):
        mark = self.mark()
        ok = func(*args) is not None
        self.reset(mark)
        return ok == positive

В нашем случае сгенерированный код для этой альтернативы выглядит так:

        if (True
            and self.lookahead(False, self.expect, "}")
            and (op := self.expect(OP))
        ):
            return op . string

Как видно из приведённого выше фрагмента грамматики, lookahead не могут получить собственные имена. Это легко поправить, но я пока не представляю как бы это пригодилось. Кроме того, для негативных прогнозов значение всегда будет None.

Группировка в скобках

Теперь давайте реализуем группы со скобками. Лучшее место для добавления их в метаграмму — правило для atom:

atom:
    | NAME { name.string }
    | STRING { string.string }
    | "(" alts ")" { self.synthetic_rule(alts) }

Первые две альтернативы не изменились. Экшен для новой альтернативы использует хак (чья реализация останется необъяснённой), которая позволяет мета-парсеру добавлять новые правила в грамматику на лету. Эта вспомогательная функция (определённая в мета-парсере) возвращает имя нового объекта правила. Оно будет состоять из фиксированного префикса, за которым следует число, что делает его уникальным, например, _synthetic_rule_1.

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

Использование alts внутри скобок означает, что мы можем определить вертикальную черту как разделитель внутри группы. Например, что наше новое решение для экшена не будет случайно совпадать с {, мы могли бы изменить отрицание на такое:

    | !("{" | "}") OP { op.string }

Более того, группы также могут содержать экшены! Это не помогло бы при решении проблемы с экшенами, но в других ситуациях вполне может оказаться полезным. И поскольку мы в любом случае генерируем синтетическое правило, для его реализации не требуется никакой дополнительной работы (кроме реализации synthetic_rule :-).

Опциональные элементы

Как и в старом pgen, я использую квадратные скобки для обозначения группы необязательных токенов. Это много где оказывается полезным. Например, правило грамматики, описывающее цикл Python for, может использовать её, чтобы указать, что может существовать продолжение else. И мы снова можем расширить грамматику для atom следующим образом:

atom:
    | NAME { name.string }
    | STRING { string.string }
    | "(" alts ")" { self.synthetic_rule(alts) }
    | "[" alts "]" { Maybe(self.synthetic_rule(alts)) }

Здесь Maybe — другой класс данных, с единственным атрибутом item. Мы модифицируем генератор кода так, чтобы результат выполнения синтетической функции не завершается ошибкой, если это значение равно None. Для этого можно добавить or True в реализации. Например, для [term]:

if (True
    and ((term := self.term()) or True)
):
    return term

Повторяющиеся элементы

Переход к повторениям — ещё одна полезная функция PEG (нотация заимствована из регулярных выражений и также используется в pgen). Существует две формы: добавление * к атому означает «ноль или более повторений», в то время как добавление + — «одно или несколько повторений». По иным причинам мне пришлось переписать правила грамматики для item и atom, добавив промежуточное правило, которое я назвал molecule:

item:
    | NAME '=' molecule { NamedItem(name.string, molecule) }
    | "&" atom { Lookahead(atom) }
    | "!" atom { Lookahead(atom, False) }

    | molecule { molecule }
molecule:
    | atom "?" { Maybe(atom) }
    | atom "*" { Loop(atom, False) }
    | atom "+" { Loop(atom, True) }
    | atom { atom }
    | "[" alts "]" { Maybe(self.synthetic_rule(alts)) }
atom:
    | NAME { name.string }
    | STRING {string.string }
    | "(" alts ")" { self.synthetic_rule(alts) }

Заметьте, что это вводит альтернативный синтаксис для опциональных элементов (atom?). Он не требует дополнительных усилий по реализации, поскольку это просто ещё один способ создания узла Maybe.

Рефакторинг этих правил был необходим, потому что я не хочу делать допустимыми некоторые ситуации:

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

Однако, это всё ещё не идеальное решение, так как вы можете написать что-то вроде (foo?)*. В генератор парсера нужно будет добавить проверку и на эту ситуацию, но я сделаю это вне статьи.

Класс данных Loop имеет два атрибута: item и nonempty. Сгенерированный код будет использовать вспомогательный метод парсера loop(). Он весьма похож на метод lookahead(), показанный ранее:

    def loop(self, nonempty, func, *args):
        mark = self.mark()
        nodes = []
        while node := func(*args) is not None:
            nodes.append(node)
        if len(nodes) >= nonempty:
            return nodes
        self.reset(mark)
        return None

Если nonempty равно False (в смысле в грамматике была *), то это не приведёт к ошибке. Ни одного вхождения не будет найдено, и вернётся пустой список. Чтобы так получилось, мы реализуем генератор парсера таким образом, чтобы добавлялось is not None. Более мягкая проверка из предыдущего поста вернула бы False в случае пустого списка.

На сегодня всё! Я собирался обсудить оператор «вырезать» (~), присутствующий в TatSu, но мне пока не довелось с ним столкнутся. Я не готов даже пока его обсуждать — документация TatSu приводит только простой пример, который меня мало интересует. Я не нашёл его и в других генераторах PEG-парсеров, так что, возможно, эта фича есть только TatSu. Может быть, я когда-нибудь расскажу и про него. (Тем временем я его реализовал на всякий случай, мало ли. :-)

Я думаю, что следующая статья будет о моём опыте написания грамматики PEG, которая сможет анализировать грамматику Python. Я расскажу как прошёл спринт разработчиков ядра Python, который был на этой неделе в Лондоне при материально-технической поддержке Bloomberg и финансовой поддержке PSF и некоторых других компаний (например, Dropbox оплатил мне отель и перелёт). Особая благодарность Эмили Морхауз и Пабло Галиндо Сальгадо, которые очень помогли в реализации инструментов и тестов. Далее мы напишем тесты производительности, а потом собираемся добавить экшены к этой грамматике, чтобы она могла создавать деревья AST, которые могут быть скомпилированы компилятором байт-кода CPython. Впереди ещё столько всего интересного!

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