Мета-грамматика для PEG парсера

Оригинал: ‘A Meta-Grammar for PEG Parsers’ by Guido van Rossum

На этой неделе мы делаем генератор парсеров «самостоятельным», то есть он будет генерировать свой собственный парсер.

Итак, у нас уже есть генератор парсера, часть которого является парсером грамматики. Мы могли бы назвать это мета-парсером. Мета-парсер работает аналогично сгенерированным: GrammarParser наследуется от Parser и использует тот же механизм mark() / reset() / hope(). Тем не менее, там всё это было написано вручную. Но правильно ли это?

При проектировании компилятора принято, чтобы компилятор был написан на языке, который он компилирует. Я с любовью вспоминаю, что компилятор Pascal, который я использовал, когда впервые научился программировать, был написан на самом Pascal, GCC написан на C, а компилятор Rust написан на Rust.

Как это сделать? В самом начале реализовать компилятор для подмножества или более ранней версии языка на другом языке. (Напомню, что первоначальный компилятор Pascal был написан на FORTRAN!) Затем новый компилятор пишется на целевом языке и компилируется с помощью bootstrap-компилятора, реализованного в самом начале. Как только новый компилятор начинает работать достаточно хорошо, bootstrap-компилятор удаляется, и каждая следующая версия языка или компилятора ограничивается тем, что может быть скомпилировано с помощью предыдущей версии компилятора.

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

Вот упрощенная версия метаграммы без экшенов:

start: rules ENDMARKER
rules: rule rules | rule
rule: NAME ":" alts NEWLINE
alts: alt "|" alts | alt
alt: items
items: item items | item
item: NAME | STRING

Я покажу как добавить экшены снизу вверх. Вспомните из части 3, что существуют объекты Rule, которые имеют атрибуты name и alts. Изначально alts представлял собой просто список списков строк (внешний список для альтернатив и внутренний для каждого элемента альтернативы), но для реализации экшенов я изменил его так, чтобы альтернативы представлялись объектами Alt с атрибутами items и action. Элементы по-прежнему представлены в виде простых строк. Для item мы получаем:

item: NAME { name.string } | STRING { string.string }

Это требует небольшого пояснения: когда анализатор обрабатывает токен, он возвращает объект TokenInfo, который имеет атрибуты type, string и другие. Мы не хотим, чтобы генератор имел дело с объектами TokenInfo, поэтому экшены здесь извлекают строку из токена. Обратите внимание, что для всех заглавных токенов, таких как NAME, сгенерированный парсер использует строчную версию (здесь name) в качестве имени переменной.

Далее идут items, которые должны возвращать список строк:

items: item items { [item] + items } | item { [item] }

Здесь я использую праворекурсивные правила, поэтому мы не зависим от обработки левой рекурсии, добавленной в части 5. (Почему бы и нет? Всегда хорошо держать вещи максимально простыми, а эта грамматика не сильно выиграет от изменения под левую рекурсию) Обратите внимание, что один item перечислен, но рекурсивно items - нет, так как он уже является списком.

Правило alt для создания объекта Alt:

alt: items { Alt(items) }

Я опущу экшены для rules и start, так как они определяются подобным образом.

Однако, есть два открытых вопроса. Во-первых, как найти определение классов Rule и Alt? Для этого нам нужно добавить несколько операторов import в сгенерированный код. Простейшим способом было бы передать флаг генератору, который говорит «это мета-грамматика», и позволить генератору вставить дополнительный import в начало сгенерированной программы. Но теперь, когда у нас есть экшены, многие другие парсеры также захотят настроить свой импорт, так почему бы нам не посмотреть, можем ли мы реализовать более общий подход.

Есть много способов реализации. Простой и общий механизм состоит в том, чтобы добавить раздел «определения переменных» в верхней части грамматики и позволить генератору использовать эти переменные для управления различными аспектами сгенерированного кода. Я решил использовать символ @, чтобы начать определение переменной, за которым следуют имя переменной (NAME) и значение (STRING). Например, мы можем поместить следующий блок кода в верхнюю часть мета-грамматики:

@subheader "from grammar import Rule, Alt"

Генератор парсера напечатает значение переменной subheader после стандартного импорта, который добавляется по умолчанию (например, для импорта memoize). Если вы хотите несколько элементов import, вы можете использовать строку с тройными кавычками, например,

@subheader """
from token import OP
from grammar import Rule, Alt
"""

Это легко добавить к мета-грамматике: мы разобьём правило start на следующие:

start: metas rules ENDMARKER | rules ENDMARKER
metas: meta metas | meta
meta: "@" NAME STRING NEWLINE

(Я не могу вспомнить, почему я назвал это «мета», но это имя я выбрал, когда писал код, и я буду придерживаться его. :-)

Мы должны добавить это и к bootstrap-метапарсеру. Теперь, когда грамматика - это не просто список правил, давайте добавим объект грамматики с атрибутами metas и rules. Мы можем задать следующие экшены:

start: metas rules ENDMARKER { Grammar(rules, metas) }
     | rules ENDMARKER { Grammar(rules, []) }
metas: meta metas { [meta] + metas }
     | meta { [meta] }
meta: "@" NAME STRING { (name.string, eval(string.string)) }

(Обратите внимание, что meta возвращает кортеж; а также, что он использует eval() для обработки строковых кавычек.)

Я не упоминал реализацию экшенов в правилах для alt! Причина в том, что они получаются немного неряшливыми. Но дальше откладывать смысла нет, так что вот:

alt: items action { Alt(items, action) }
   | items { Alt(items, None) }
action: "{" stuffs "}" { stuffs }
stuffs: stuff stuffs { stuff + " " + stuffs }
      | stuff { stuff }
stuff: "{" stuffs "}" { "{" + stuffs + "}" }
     | NAME { name.string }
     | NUMBER { number.string }
     | STRING { string.string }
     | OP { None if op.string in ("{", "}") else op.string }

Грязь в определении вызвана моим желанием сделать допустимым произвольный код на Python между фигурными скобками экшена, в том числе и вложенный в ещё одни фигурные скобки. Для этой цели мы используем специальный токен OP, который генерирует наш токенизатор для всех знаков препинания, распознаваемых Python (возвращая один токен с типом OP для многосимвольных операторов, таких как <= или **). Единственные другие токены, которые могут встречаться в выражениях Python - это имена, числа и строки. Таким образом, код между внешними фигурными скобками экшена, казалось бы, может быть выражен через повторения NAME | NUMBER | STRING | OP.

Увы, это не сработает, потому что OP также соответствует фигурным скобкам, и, поскольку анализатор PEG всегда жадный, это захватит закрывающую скобку, и мы никогда не увидим конца экшена. Поэтому мы добавляем небольшую подстройку, позволяя экшену выбросить ошибку выбора альтернативы, возвращая None. Я не знаю, является ли это стандартным явлением в других PEG-парсерах - я придумал это на месте, когда мне пришлось решить проблему распознавания закрывающей скобки (даже без вложенных пар). Кажется, что это работает хорошо, и я думаю, что это вписывается в общую философию PEG-анализа. Это можно рассматривать как особую форму предвидения (о которой я расскажу ниже).

Используя этот небольшой хак, мы можем сделать так, чтобы сравнение на OP сваливалось на фигурной скобке. Тогда сопоставление по stuff и action станет возможным.

С этими вещами мета-грамматика может быть проанализирована bootstrap-метапарсером, и генератор может превратить её в новый мета-парсер, который может анализировать себя. И, что важно, новый мета-парсер всё ещё может анализировать ту же мета-грамматику. Если мы скомпилируем мета-грамматику с новым мета-компилятором, результат будет таким же: это доказывает, что сгенерированный мета-парсер работает правильно.

Вот полная мета-грамматика с экшенами. Он может проанализировать себя, так как умеет объединять длинные строки:

@subheader """
from grammar import Grammar, Rule, Alt
from token import OP
"""

start: metas rules ENDMARKER { Grammar(rules, metas) }
     | rules ENDMARKER { Grammar(rules, []) }
metas: meta metas { [meta] + metas }
     | meta { [meta] }
meta: "@" NAME STRING NEWLINE { (name.string, eval(string.string)) }
rules: rule rules { [rule] + rules }
     | rule { [rule] }
rule: NAME ":" alts NEWLINE { Rule(name.string, alts) }
alts: alt "|" alts { [alt] + alts }
    | alt { [alt] }
alt: items action { Alt(items, action) }
   | items { Alt(items, None) }
items: item items { [item] + items }
     | item { [item] }
item: NAME { name.string }
    | STRING { string.string }
action: "{" stuffs "}" { stuffs }
stuffs: stuff stuffs { stuff + " " + stuffs }
      | stuff { stuff }
stuff: "{" stuffs "}" { "{" + stuffs + "}" }
     | NAME { name.string }
     | NUMBER { number.string }
     | STRING { string.string }
     | OP { None if op.string in ("{", "}") else op.string }

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

Но сначала надо немного подумать: пустые строки! Оказывается, модуль stdlib tokenize создаёт дополнительные токены для отслеживания незначимых переносов строк (токен NL) и комментариев (токен COMMENT). Вместо того, чтобы включать их в грамматику (я пробовал, удовольствия мало!), Есть очень простой фрагмент кода, который мы можем добавить в наш класс токенизатора, чтобы фильтровать их. Вот улучшенный метод peek_token:

    def peek_token(self):
        if self.pos == len(self.tokens):
            while True:
                token = next(self.tokengen)
                if token.type in (NL, COMMENT):
                    continue
                break
            self.tokens.append(token)
            self.report()
        return self.tokens[self.pos]

Это полностью убирает токены NL и COMMENT, поэтому нам больше не нужно беспокоиться о них в грамматике.

Наконец, давайте внесем улучшения в мета-грамматику! Они будут чисто косметическими: мне не нравится, когда меня заставляют писать все альтернативы в одну строку. Мета-грамматика, которую я показал выше, на самом деле не разбирает себя из-за таких вещей:

start: metas rules ENDMARKER { Grammar(rules, metas) }
     | rules ENDMARKER { Grammar(rules, []) }

Это связано с тем, что токенизатор создает токен NEWLINE в конце первой строки, и в этот момент мета-парсер будет считать, что это конец правила. Более того, за этой NEWLINE будет следовать токен INDENT, потому что следующая строка имеет отступ. До начала следующего правила также будет присутствовать токен DEDENT.

Вот как с этим справиться. Чтобы понять поведение модуля tokenize, мы можем взглянуть на последовательность токенов, сгенерированных для блоков с отступом, запустив модуль tokenize как скрипт и передав ему некоторый текст:

$ python -m tokenize
foo bar
    baz
    dah
dum
^D

Мы видим, что это производит следующую последовательность токенов (я немного упростил вывод из вышеприведённого кода):

NAME     'foo'
NAME     'bar'
NEWLINE
INDENT
NAME     'baz'
NEWLINE
NAME     'dah'
NEWLINE
DEDENT
NAME     'dum'
NEWLINE

Таким образом выделенная группа строк обозначена токенами INDENT и DEDENT. Теперь мы можем переписать правило мета-грамматики для rule следующим образом:

rule: NAME ":" alts NEWLINE INDENT more_alts DEDENT {
        Rule(name.string, alts + more_alts) }
    | NAME ":" alts NEWLINE { Rule(name.string, alts) }
    | NAME ":" NEWLINE INDENT more_alts DEDENT {
        Rule(name.string, more_alts) }
more_alts: "|" alts NEWLINE more_alts { alts + more_alts }
         | "|" alts NEWLINE { alts }

(Я разбиваю экшены по строкам, чтобы они нормально читались в узкой колонке текста. Это возможно, потому что токенизатор игнорирует разрывы строк внутри соответствующих фигурных скобок.)

Прелесть этого в том, что нам даже не нужно менять генератор: структура данных, создаваемая этой улучшенной мета-грамматикой, такая же, как и раньше. Также обратите внимание на третий вариант для rule: это позволяет нам писать:

start:
    | metas rules ENDMARKER { Grammar(rules, metas) }
    | rules ENDMARKER { Grammar(rules, []) }

что некоторым покажется чище, чем версия, которую я показал ранее. Легко разрешить обе формы, поэтому нам не нужно спорить о стиле.

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

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