По мотивам моего доклада на PyCon "Контейнеризация Python без боли". На своей практике я постоянно сталкиваюсь со спорами какой базовый образ лучше использовать для проектов: alpine или debian. Аргументы есть и у той, и у другой стороны, но мне это настолько надоело, что я решил сам разобраться и наконец-то поставить точку. В конце концов "В наше время верить нельзя никому, даже себе. Но мне - можно." (с)

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

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

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

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

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

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

Грамматика становится ещё лучше, если вы можете добавить (некоторую) семантику в соответствии с правилами. В частности, для анализатора Python, который я разрабатываю, мне нужно возвращать узел AST из каждой альтернативы, поскольку я хочу придерживаться текущей реализации AST в CPython.

Многие грамматики используют соглашение, позволяющее добавлять экшены к правилам — обычно это блок кода внутри {фигурных скобок}. Точнее, они привязаны к альтернативам. Код в этом блоке пишется на том же языке, что и остальной компилятор, например, на C, дополненный некоторой возможностью ссылки на элементы в альтернативе. В оригинальном pgen Python я не добавил этот функционал, но для нового проекта мне бы хотелось его реализовать.

Я упоминал о левой рекурсии как о камне преткновения несколько раз, и пришло время разобраться с этим. Основная проблема заключается в том, что парсер с лево-рекурсивным спуском мгновенно падает из-за переполнения стека.

Рассмотрим это гипотетическое правило грамматики:

expr: expr '+' term | term

В прошлый раз получился простой генератор парсера PEG. Сейчас же я покажу, что на самом деле делает сгенерированный парсер при разборе программы. Я погрузился в ретро-мир ASCII-арта, в частности, библиотеку с именем «curses», которая доступна в стандартной поставке Python для Linux и Mac, а также как дополнение для Windows.

<В конце статьи под спойлером приводится gif. Мне он показался более понятным, нежели статичная картинка>

Теперь, когда я набросал основу самописного парсера, давайте перейдём к генерации его методов из грамматики, как я и обещал. Также покажу как реализовать packrat-парсер с помощью декоратора @memoize.

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

Вдохновленный лишь частичным пониманием PEG, я решил попробовать его реализовать. Результат может получиться и не самым лучшим среди парсеров PEG общего назначения — их уже много (например, TatSu написан на Python и генерирует код Python) — но это хороший способ разобраться в PEG. В дальнейшем я хочу заменить им текущую реализацию парсера в CPython.

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

Несколько лет назад меня кто-то спросил имеет ли смысл превести Python на PEG-парсер (или на грамматику PEG; я не помню точно кто и когда это было). Тогда я немного посмотрел на него, но так и не пришёл к какому-либо выводу, а потому и отбросил эту тему. Недавно я узнал больше о PEG (Parsing Expression Grammars, грамматике по парсингу выражений), и теперь я думаю, что это интересная альтернатива самописному генератору парсеров, который был разработан 30 лет назад, когда только начинал работать над Python. Я назвал его «pgen», и это был, наверно, первым фрагментом кода, который я написал для Python.

Причина, по которой я сейчас заинтересован в парсере PEG, заключается в том, что меня несколько раздражают ограничения pgen. Он построен на собственной реализации LL(1), которая имеет ряд допущений. Например, мне не нравились грамматические правила, которые могли бы генерировать пустые строки, поэтому я запретил их. И тем самым упростил алгоритм для создания таблиц синтаксического анализа. Я также изобрёл свою собственную EBNF-подобную грамматическую нотацию, которая мне до сих пор очень нравится.