Работа над PEG на Core Developer Sprint

2019-11-04 в 3:46, admin, рубрики: packrat parsers, peg, pgen, python, алгоритм, Алгоритмы, Программирование

В этой статье я не буду рассказывать о новых фичах генератора парсера — я достаточно описал его в предыдущих частях. Вместо этого хочу рассказать что я делал на Core Developer Sprint на прошлой неделе, прежде чем всё сотрётся из моей памяти. Хотя большая часть материала так или иначе всё равно касается PEG. Так что мне придётся показать некоторый код, который задаёт направление в реализации PEG-парсера для Python 3.9.

Содержание серии статей о PEG-парсере в Python

Каждый год в течение последних четырёх лет группа разработчиков ядра Python собирается на недельный спринт в экзотическом месте. Эти спринты спонсируются принимающей стороной и PSF. Первые два года мы были у Facebook в Mountain View, в прошлом году была очередь Microsoft в Bellevue, а на этот спринт выбрали офис Bloomberg в Лондоне. (Должен сказать, что он выглядит довольно круто.) Слава core-разработчику Pablo Galindo Salgado за организацию!

В этот раз нас собралось более 30 разработчиков, а также два падавана. Люди работали над различными частями: от блокеров 3.8 до новых PEP. Я надеюсь, PSF напишет в блоге о наших достижениях. Одним из основных моментов было то, что количество открытых PR было меньше 1000, смерджено более 100 PR, которые ожидали своего ревьювера. Было даже соревнование с таблицей лидеров — 10 лучших участников, которые смерджили большее количество чужих PR.

Для меня всегда главная причина посещать подобные мероприятия — встреча с людьми, с которыми я сотрудничаю онлайн в течение всего года, но которых вижу только один или два раза в год. Этот спринт был в Европе, поэтому мы увидели немного иной состав, и это было особенно важно. Несмотря на это, я также довольно продуктивно поработал, о чём и расскажу.

Большую часть своего времени на спринте я работал с Пабло и Эмили Морхауз над генератором парсера на основе PEG, который, я надеюсь, когда-нибудь заменит текущий генератор парсера на основе pgen. Это не тот же код, что и генератор, о котором я писал, но он довольно похож. Пабло уже внёс свой вклад в эту версию.

Первый день спринта, понедельник, я работал в основном над 7 и 8 статьёй из этого цикла. Первоначально я планировал опубликовать их вместе, но не успел к концу дня. Так что разделил на две части и опубликовал первую половину, посвящённую созданию метаграммы. В пятницу после обеда я наконец нашёл немного времени, чтобы дописать часть 8. Однако, мне всё равно пришлось опустить рассказ про «cut», потому что у меня всё ещё не было хорошего примера.

Во вторник я начал работать над грамматикой PEG для Python. Она даже до добавления экшенов ближе к коду, нежели к абстрактной спецификации. Мы поняли, что нам нужно проверить разрабатываемую грамматику на реальном коде Python. Поэтому, пока я дописывал грамматику, Эмили занималась сценариями для пакетного тестирования. После этого мой рабочий процесс был примерно следующим:

Запустить скрипт для тестирования некоторого каталога с кодом на Python
Исследовать первую проблему, на которой он свалился
Исправить грамматику для решения этой проблемы
Повторять до тех пор, пока не останется проблем
Перейти к следующему каталогу

Я начал с собственного кода проекта pgen. В конце концов, моя грамматика смогла проанализировать все конструкции Python, используемые в pgen, и я перешёл к модулям стандартной библиотеки. Сначала сосредоточившись на Lib/test, затем на Lib/asyncio и, наконец, на Lib, то есть фактически на всей стандартной библиотеке (по крайней мере той, которая написана на Python). К концу недели я смог отпраздновать: единственные файлы в стандартной библиотеке, на которых валился новый анализатор, — файлы с плохими кодировками. Они существуют исключительно в качестве тестовых данных для проверки, что проблемы с кодировкой будут обработаны правильным способом; и некоторые файлы для Python 2 которые нужны в качестве тестовых случаев для lib2to3.

Потом я добавил некоторый код для вычисления времени работы парсера в сценарии Эмили, и похоже, что новый PEG-парсер немного быстрее старого pgen-парсера. Это ещё не значит, что дальше дела пойдут в гору! В грамматике уже более 100 правил (160 строк), и чтобы заставить её генерировать AST, нам нужно будет к каждому добавить ещё и экшен (см. Часть 6).

Чуть ранее я провёл некоторый эксперимент, чтобы посмотреть насколько увеличится размер файла после добавления экшенов. Пришёл к выводу, что он станет в 2-3 раза больше.Вот грамматика этого эксперимента:

start[mod_ty]: a=stmt* ENDMARKER{ Module(a, NULL, p->arena) }
stmt[stmt_ty]: compound_stmt | simple_stmt
compound_stmt[stmt_ty]: pass_stmt | if_stmt
pass_stmt[stmt_ty]: a='pass' NEWLINE { _Py_Pass(EXTRA(a, a)) }
if_stmt[stmt_ty]:
    | 'if' c=expr ':' t=suite e=[else_clause] {
          _Py_If(c, t, e, EXTRA(c, c)) }
else_clause[asdl_seq*]:
    | 'elif' c=expr ':' t=suite e=[else_clause] {
          singleton_seq(p, _Py_If(c, t, e, EXTRA(c, c))) }
    | 'else' ':' s=suite { s }
suite[asdl_seq*]:
    | a=simple_stmt { singleton_seq(p, a) }
    | NEWLINE INDENT b=stmt+ DEDENT { b }
simple_stmt[stmt_ty]: a=expr_stmt NEWLINE { a }
expr_stmt[stmt_ty]: a=expr { _Py_Expr(a, EXTRA(a, a)) }
expr[expr_ty]:
    | l=expr '+' r=term { _Py_BinOp(l, Add, r, EXTRA(l, r)) }
    | l=expr '-' r=term { _Py_BinOp(l, Sub, r, EXTRA(l, r)) }
    | term
term[expr_ty]:
    | l=term '*' r=factor { _Py_BinOp(l, Mult, r, EXTRA(l, r)) }
    | l=term '/' r=factor { _Py_BinOp(l, Div, r, EXTRA(l, r)) }
    | factor
factor[expr_ty]:
    | l=primary '**' r=factor { _Py_BinOp(l, Pow, r, EXTRA(l, r)) }
    | primary
primary[expr_ty]:
    | f=primary '(' e=expr ')' {
          _Py_Call(f, singleton_seq(p, e), NULL, EXTRA(f, e)) }
    | atom
atom[expr_ty]:
    | '(' e=expr ')' { e }
    | NAME
    | NUMBER
    | STRING

Здесь есть куча вещей, которые я должен объяснить.

Экшены написаны на C. Как и в генераторе Python из части 6, каждый из них является одним выражением.
Текст в квадратных скобках сразу после имени правила определяет тип результата для соответствующего метода правила. Например, atom[expr_ty] означает, что для atom будет возвращаться expr_ty. Если вы посмотрите файл Include/Python-ast.h в репозитории CPython, то увидите, что этот тип является структурой, используемой для представления выражений во внутреннем AST.
Если у альтернативы есть только один элемент, то экшен может быть опущен, так как поведение по умолчанию для него — просто вернуть получившийся узел AST. В противном случае экшен надо прописывать явно.
Сгенерированный код на C также нуждается в некоторой обработке. Например, предполагается, что будут подключены некоторые заголовочные файлы CPython. Например, где определён тип expr_ty, ну и многие другие необходимые вещи.
Переменная p содержит указатель на структуру Parser, используемую сгенерированным анализатором. (И да, это означает, что лучше не указывать ни одного элемента в правиле p — иначе сгенерированный код C не будет компилироваться!)
EXTRA(node1, node2) — это макрос, который разворачивается в набор дополнительных аргументов, которые необходимо передать каждой функции построения AST. Это экономит много времени на при написании экшена — в противном случае пришлось бы указывать начальный и конечный номер строки, смещение столбца, а также указатель на арену, используемую для распределения. (Узлы AST не являются объектами Python и используют более эффективную схему размещения.)
Из-за некоторого интересного поведения препроцессора C в EXTRA(), мы не можем использовать макросы для создания узла AST, а должны использовать базовые функции. Вот почему вы видите, например, _Py_Binop(...), а не Binop(...). В будущем я подумаю как решить это по-другому.
Для повторяющихся элементов (foo* или foo+) генератор кода создает вспомогательное правило, тип которого asdl_seq*. Это структура данных, которая используется в AST для представления повторений. В нескольких местах нам нужно создать такое повтороение только лишь из одного элемента, и для этого мы определили вспомогательную функцию singleton_seq().

Возможно, что-то из этого звучит странно, и я не буду спорить. Это прототип, и его основной целью является демонстрация того, что в принципе возможно генерировать работающий AST с использованием синтаксического анализатора, сгенерированного из грамматики PEG. Всё это работает без каких-либо изменений в существующем токенизаторе или компиляторе байт-кода. Прототип может компилировать простые выражения и операторы if, а результирующий AST может быть скомпилирован в байт-код и выполнен.

Другие вещи, которые я сделал в рамках этого спринта:

Убедил Лукаша Лангу изменить PEP 585 (его предложение о будущем type hinting), чтобы сосредоточиться на дженериках, а не на наборе идей, как это было раньше. Новый PEP выглядит намного лучше, и на typing-митапе несколько дней назад, где присутствовали представители разработчиков утилит проверки Python типов (mypy, pytype и Pyre), он получил общее одобрение. (Это не то же самое, что одобрение Руководящего совета!)
Помог Юрию Селиванову в разработке API для типа frozenmap, который он хотел добавить в stdlib. Несколько других участников также внесли свой вклад в дизайн — я думаю, мы закончили спринт с несколькими досками, полными примеров и фрагментов API. Результат — PEP 603, и в настоящее время он активно обсуждается. (Одно замечание: реализация предложенного типа данных уже существует в CPython, как часть реализации PEP 567, модуля contextvars. Это очень интересная структура данных, Hash Array Mapped Trie, которая объединяет хеш-таблицу с префиксным деревом)
Юрий, как всегда полон идей. Также он работал над группами исключений (идея из Trio) которые хочет реализовать в asyncio в Python 3.9. PEP вроде ещё не было, когда я в последний раз смотрел, но точно помню одну доску, полную диаграмм.
Мы активно обсуждали предложение Лукаша о более коротком цикле релизов Python. Это вылилось в PEP 602, в котором он предлагает делать их ежегодно, в октябре. (Для этого есть веская причина: это связано с типичным графиком конференций Python и core-спринтов.) Это всё ещё очень активно обсуждаться. Существует как минимум два встречных предложения: в PEP 598 Ник Коглан предлагает двухгодичные выпуски, допуская при этом новые фичи в патчах; Стив Дауэр хотел бы видеть так же двухгодичные выпуски, но без этой возможности (PEP пока не было).
Три члена Руководящего совета, которые присутствовали на спринте (Бретт Кэннон, Кэрол Уиллинг и я), собрались вместе и обсудили наше видение будущего развития ядра Python. (Я не хочу много говорить об этом, потому что планируем выступить с этим на следующем PyCon в США. Однако, мы, вероятно, предложим начать сбор средств, чтобы PSF мог нанять нескольких разработчиков для поддержки и ускорения разработки ядра).
У меня был интересный обеденный разговор с Джоанной Нанджеки — одной из тех, кто присутствовал на церемонии. Она рассказала историю о том, как узнала об интернете, когда ей было 8 лет, и повела своего младшего брата в интернет-кафе, пока их мама работала. Там она открыла для себя Google и электронную почту и зависала там всю первую неделю.
Главным алкогольным событием недели была пара коктейлей «Зомби-Апокалипсис», которые некоторые из нас заказали в баре «Алхимик». Поданный в 2х литровой колбе Эрленмейера с большим количеством фальшивого дыма, образующегося в результате обливания сухим льдом обычной спиртовой смеси, каждый напиток расчитан на четырех человек.
В пятницу вечером Лиза Роуч привела нас в хороший индийский ресторан возле своего отеля. Это было через четыре станции метро, что было настоящим приключением (это был час пик, и мы чуть не потеряли Кристиана Хаймса несколько раз). Еда того стоила!
В какой-то момент мы сделали групповое фото. Оно выглядит довольно футуристично, но это действительно лондонский пейзаж.