PEG парсеры

Оригинал: ‘PEG parsers’ by Guido van Rossum

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

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

Вот некоторые проблемы с pgen, которые меня раздражают. «1» в названии LL(1) подразумевает, что он анализирует только следующий токен, и это ограничивает нашу возможность создавать хорошие грамматические правила. Например, оператор Python может быть выражением или присваиванием (или чем-то другим, но все они начинаются с выделенного ключевого слова, например, if или def). Хотелось бы описывать синтаксис с использованием нотации pgen. Обратите внимание, что это лишь упрощённый пример, представляющий собой подмножество Python, как это обычно делается при описании языкового дизайна. Это будет игрушечная грамматика, которая пригодится для дальнейшей демонстрации.

statement: assignment | expr | if_statement
expr: expr '+' term | expr '-' term | term
term: term '*' atom | term '/' atom | atom
atom: NAME | NUMBER | '(' expr ')'
assignment: target '=' expr
target: NAME
if_statement: 'if' expr ':' statement

Несколько слов о нотации: NAME и NUMBER являются токенами и предопределены вне грамматики. Строки в кавычках типа '+' или 'if' также являются токенами. (Давайте отложим разговор о них на следующий раз) Правила грамматики начинаются с имени правила, за которым следует :, а далее одна или несколько альтернатив, разделенных |.

Проблема в том, что если вы опишете грамматику таким образом, то pgen не будет работать. Всё из-за того, что некоторые правила (expr и term) являются леворекурсивными, а он недостаточно умён, чтобы правильно обрабатывать такие ситуации. Обычно это решается переписыванием только этих правил, оставляя другие правила без изменений. Например:

expr: term ('+' term | '-' term)*
term: atom ('*' atom | '/' atom)*

Это раскрывает несколько возможностей EBNF в pgen: вы можете вкладывать альтернативы в круглые скобки и создавать повторения, помещая * после элемента. Так что правило для выражения expr здесь означает “это терм, за которым следует ноль или более повторений последовательности <терм плюс или минус, за которым следует терм>”. Эта грамматика принимает тот же язык, что и первая версия, но она опять-таки не отражает намерения дизайна языка. В частности, она не показывает, что операторы привязаны слева, а это важно, когда вы пытаетесь генерировать код.

Но есть ещё одна досадная проблема в этом примере (да и в Python тоже). Из-за разбора только одного токена анализатор не может определить, что именно он просматривает - начало выражения или присваивания. В самом начале обработки оператора синтаксический анализатор должен решить по одному лишь первому токену, какую альтернативу он разбирает. (Почему? Так работает реализация синтаксического анализа в pgen) Допустим, наша программа такова:

answer = 42

Эта программа представляется тремя токенами: NAME (со значением answer), = и NUMBER (со значением 42). Единственное, о чём мы знаем в самом начале разбора - это первый токен NAME. Правило, которое мы пытаемся разобрать на данном этапе, это statement (начальный символ грамматики). Для него определены 3 альтернативы: expr, assignment и if_statement. Мы можем сразу исключить if_statement, потому что предыдущий токен не if. Но и expr, и assignment могут начинаться с токена NAME, и из-за этого pgen отклоняет нашу грамматику как неоднозначную.

Это не совсем правильно, так как технически грамматика сама по себе таковой не является; я не могу подобрать более точной формулировки, так что давайте остановимся на этой. И как pgen решает это? Он вычисляет нечто, называемое FIRST-набором для каждого правила грамматики, и если они пересекаются, то лишь тогда выбрасывает исключение.

Так разве мы не можем решить эту проблему, предоставив парсеру больший буфер просмотра? Для нашего примера достаточно второго токена предпросмотра, поскольку в этой грамматике вторым токеном присваивания должен быть =. Но в более реалистичном языке, таком как Python, вам может понадобиться неограниченный буфер, поскольку содержимое слева от токена = может быть произвольно сложным, например:

table[index + 1].name.first = 'Steven'

В этом случае придётся разобрать уже десять токенов, прежде чем мы встретим =. Но уверяю, могут быть и более длинные выражения. Чтобы решить эту проблему в pgen, мы изменили грамматический анализатор так, чтобы он принимал и некоторые некорректные выражения, добавив дополнительную проверку в последующем проходе. Она сгенерирует ошибку SyntaxError, если не сможет сопоставить левую и правую часть. Для нашего игрушечного языка это сводится к написанию следующего:

statement: assignment_or_expr | if_statement
assignment_or_expr: expr ['=' expr]

Квадратные скобки указывают на необязательную часть. И затем на следующем проходе компилятора (скажем, при генерации байт-кода) мы проверяем, есть ли = или нет, и, если есть, мы проверяем, что левая часть соответствует синтаксису target.

Существует аналогичная проблема и для аргументов вызовов функций. Мы хотели бы написать что-то вроде этого (опять же, в упрощённой версии синтаксиса Python):

call: atom '(' arguments ')'
arguments: arg (',' arg) *
arg: posarg | kwarg
posarg: expr
kwarg: NAME '=' expr

Но алгоритм разбора, который бы учитывал лишь следующий токен, не может сказать парсеру, является ли NAME в начале аргументов началом posarg (поскольку expr может начинаться с NAME) или началом kwarg. Опять же, текущий анализатор Python решает эту проблему путем определения:

arg: expr ['=' expr]

и затем доуточняет альтернативу в последующем проходе компилятора. (Мы даже немного ошиблись и разбирали foo((a) = 1) также, как и foo(a = 1). Это исправлено лишь в Python 3.8)

Итак, как PEG-парсер решает эти проблемы? Используя бесконечный резервный буфер! Типичная его реализация использует так называемый packrat-парсер, который не только загружает всю программу в память перед её синтаксическим анализом, но и позволяет откатывать анализатор на произвольное количество токенов назад. Хотя термин PEG в первую очередь относится к грамматической нотации, синтаксические анализаторы, сгенерированные из грамматик PEG, обычно представляют собой синтаксические анализаторы с рекурсивным спуском и неограниченным возвратом. packrat-парсер делает эго эффективным, запоминая правила, уже разобранные для определённых позиций.

Это упрощает алгоритм, но, конечно, есть цена: память. Тридцать лет назад у меня была веская причина использовать LL(1): память была дорогой. Он (как и другие технологии, такие как LALR(1), ставшие известными благодаря YACC) используют конечный автомат и стек для эффективного построения дерева разбора.

К счастью, компьютеры, на которых работает CPython, имеют намного больше памяти, чем 30 лет назад, и хранение всего файла в памяти больше не является проблемой. Например, самый большой не тестовый файл в stdlib, который я смог найти, это _pydecimal.py, который занимает около 223kb. В мире гигабайтов это по сути ничего, что и заставило меня по-другому взглянуть на синтаксические анализаторы.

Но есть ещё одна вещь в текущем парсере CPython, которая меня беспокоит. Компиляторы являются сложными вещами, и реализация для CPython не является исключением. Хотя результат работы парсера pgen и является деревом синтаксического анализа, однако оно непосредственно не используется в качестве входных данных для генератора байт-кода: сначала оно преобразуется в абстрактное синтаксическое дерево (AST), а лишь затем этот AST компилируется в байт-код. (На самом деле там ещё сложнее, но пока не будем вдаваться в детали)

Почему бы сразу не компилировать из дерева разбора? Именно так оно и было, но около 15 лет назад мы обнаружили, что компилятор переусложнён. Так что мы выделили отдельно AST и фазу трансформации AST из дерева разбора. По мере развития Python, AST оставался более стабильным, чем парсинг, что уменьшало вероятность ошибок в компиляторе.

С AST также легче работать сторонним библиотекам, которые хотят проверять код Python. Его можно получить с помощью популярного модуля ast. Он также позволяет создавать узлы с нуля и изменять существующие, а также компилировать части в байт-код. Последнее позволило создать целую индустрию языковых расширений для Python. (Дерево разбора также доступно пользователям Python через модуль синтаксического анализа, но работать с ним гораздо сложнее; поэтому оно не так популярно)

Сейчас же я хочу объединить эти вещи и посмотреть, сможем ли мы создать новый парсер для CPython, который использует PEG и packrat для создания AST непосредственно во время синтаксического анализа. Таким образом получится опустить генерацию промежуточного дерева синтаксического анализа, что может сэкономить нам память, даже несмотря на использование бесконечного буфера для токенов. Я ещё в процессе реализации, но у меня уже есть прототип, который может скомпилировать подмножество Python в AST примерно с той же скоростью, что и текущий синтаксический анализатор CPython. Однако, он использует больше памяти, и мне кажется, что расширение подмножества на полный язык замедлит парсер PEG. Но пока я и не думал о каких-либо оптимизациях, так что продолжу работу.

Последнее преимущество перехода на PEG заключается в том, что он обеспечивает большую гибкость для дальнейшей эволюции языка. В прошлом было сказано, что ограничения LL(1) в pgen помогали грамматике Python оставаться простой. Это вполне может быть так, но у нас есть множество других процессов, чтобы предотвратить неконтролируемый рост языка (в основном процесс PEP, которому помогают очень строгие требования обратной совместимости и новая структура управления). Так что я не беспокоюсь за это.

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

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