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

Автор оригинала: Guido van Rossum
  • Перевод

После того, как я собрал все части генератора 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

Похожие публикации

AdBlock похитил этот баннер, но баннеры не зубы — отрастут

Подробнее
Реклама

Комментарии 5

    –1
    Кроме того, для негативных прогнозов значение всегда будет None.

    Непонятно, из чего это следует. Что мешает генератору возвращать результат сопоставления под lookahead?


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

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

    Странная логика. Т.е. реализовать оператор, который просто вообще нарушает саму логику PEG (отключая выбор альтернатив — см. описание) — это нормально, а то, что не нарушает, зато логично вписывается в концепцию — "не представляю как бы это пригодилось". Странная логика.


    Вообще, чувак занимается пилением велосипедов со странным подходом. То вместо использования повторений борется с левой рекурсией (вообще надуманная проблема — зачем тебе тут рекурсия, когда это повторение в чистом виде?). То для использования меток у правил генерирует их из имен правил. А если тебе нужна метка для не для куска правила, а для некоей группы, как здесь:


    start = ('a' 'b' 'с') { ??? }

    В этой статье он похоже заглянул в другие реализации и пришел к идее явных меток, но что мешало сделать это раньше?


    Как я понял, он собирается это использовать в проде. Ну посмотри тогда, как другие реализовали — pegjs, например. Стройная, красивая реализация. Можно написать плагин, чтобы генерил Python код. Да даже в качестве бутстрапа можно просто взять и вручную преобразовать сгенерированный JS в Python (я так делал, когда мне быстро понадобился парсер на питоне, т.к. это оказалось быстрее, чем написать новый плагин генерации. Грамматика была небольшая и развиваться не будет).
    Например, сразу начал использовать мемоизацию, а это может привести к тому, что сообщения об ошибках иногда будут некорректными — см. pegjs#612. Конечно, возможно, что в грамматике питона таких случаев нет, но тогда возникает вопрос — зачем писать свой генератор, когда готовых полно? В качестве упражнения нормально, но тащить в прод?

      0
      Упс, промахнулся веткой. Ответ ниже.
      0
      Для негативных прогнозов Гвидо всегда возвращает None, это одна из аксиом.

      Странная логика. Т.е. реализовать оператор, который просто вообще нарушает саму логику PEG (отключая выбор альтернатив — см. описание) — это нормально,
      Эм, ну вот как раз он и не реализовал оператор `cut` (который отключает альтернативы), т.к. пока нет необходимости.

      Более чем уверен, что автор посмотрел не одну реализацию PEG, прежде чем приступить к работе (по крайней мере он на них иногда ссылался). Тащить же js библиотеку в ядро python по мне так выглядит уж слишком безумным, но не отрицаю, что оттуда можно взять идеи. Тем более `PEG.js is still very much work in progress. There are no compatibility guarantees until version 1.0`.
        0
        Для негативных прогнозов Гвидо всегда возвращает None, это одна из аксиом.

        Аксиом чего? Прогнозы возвращают True или False. Сейчас технически это сделано через возврат значения или None, но никто не мешает сделать по-другому.


        Тащить же js библиотеку в ядро python по мне так выглядит уж слишком безумным, но не отрицаю, что оттуда можно взять идеи.

        Никто не предгалает тащить js. Можно было сгенерировать начальный парсер для питона этой библиотекой, а потом уже, имея на руках этот парсер, он сам себя бы смог генерировать. Так как писать плагин к JS-библиотеке ради единственного использования было бы глупо, то можно было бы сгенерировать код на JS а потом вручную перевести его на Python — там почти 1-в-1 получается.


        Тем более PEG.js is still very much work in progress. There are no compatibility guarantees until version 1.0.

        Вы не смотрите на это, она настолько stable, что мне не удалось пробить автора смерджить реализацию парсера повторений, хотя она готова уже лет 6. За это время автор уже успел потерять интерес к проекту, передал его другому мейнтейнеру и проект, к сожалению, окончательно слился.


        Более чем уверен, что автор посмотрел не одну реализацию PEG, прежде чем приступить к работе

        Ну вот не похоже по его статьям. В процессе написания — очень может быть. А до этого все статьи — жуткое велосипедостроение.


        Эм, ну вот как раз он и не реализовал оператор cut (который отключает альтернативы), т.к. пока нет необходимости.

        Ну он же прямо специально в скобках написал, а я процитировал, что


        (Тем временем я его реализовал на всякий случай, мало ли. :-)
          0
          Его статьи — лишь знакомство с темой PEG парсеров на примере некоего прототипа. Он сам не раз указывал, что использует «игрушечную грамматику». Это не финальный код, он служит лишь для демонстрации. Естественно, эта реализация должна походить на велосипед, чтобы облегчить понимание.

          Что же касается реальной смены парсера — давайте подождём хотя бы черновика PEP. Там и можно будет продолжить обсуждения. Мне же не удалось найти пока кода, который Гвидо хочет влить в CPython.

      Только полноправные пользователи могут оставлять комментарии. Войдите, пожалуйста.

      Самое читаемое