На этой неделе мы делаем генератор парсеров «самостоятельным», то есть он будет генерировать свой собственный парсер.
Итак, у нас уже есть генератор парсера, часть которого является парсером грамматики. Мы могли бы назвать это мета-парсером. Мета-парсер работает аналогично сгенерированным: 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