PEG парсеры и Python.

Python

Несколько лет назад кто-то спросил, имеет ли смысл переключать Python на парсер PEG. Или на грамматику PEG. Не помню точно. Тогда я ещё не знал, что и думать и отбросил тему. Но недавно узнал о PEG  —  разбивающей выражение грамматике  —  больше. Оказалось, это интересная альтернатива доморощенному генератору синтаксических анализаторов, который я написал 30 лет назад. Тогда началась работа над Python. pgen  —  примерно первый фрагмент его кода.

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

Вот некоторые проблемы pgen. Название LL(1) подразумевает, что он использует только один сканируемый токен. Это ограничивает возможности. Например, оператор может быть выражением или присваиванием. Или чем-то другим. Но все операторы начинаются с ключевого слова, например, 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' — тоже токены. Правила начинаются с имени, за которым следует:, затем альтернативы, разделённые |.

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

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

Открывается несколько возможностей: вы можете вкладывать альтернативы в круглые скобки и создавать повторения, помещая * после элемента. Правило для expr означает, что это “правило, за которым следует ноль или более повторений плюса и этого же правила или минуса и этого же правила”. Грамматика принимает тот же язык, что и первая версия, но она не отражает намерения дизайнера языка. Точнее, не показывает, что операторы привязаны слева. Это важно при генерации кода.

Есть еще одна досадная проблема в нашем игрушечном языке. И в Python. pgen не может определить, что именно просматривает: начало выражения или присваивание. В начале оператора анализатор должен решить, какую альтернативу он предполагает по первому видимому токену. Почему? Так работает автомат разбора pgen:

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

Технически это не совсем верно: грамматика сама по себе однозначна. Но я не знаю, есть ли лучшее слово. Как pgen решает эту проблему? Он вычисляет нечто, называемое набором FIRST для каждого правила грамматики. И оно жалуется, если FIRST наборы перекрываются.

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

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 решает эти проблемы? Используя бесконечный резервный буфер! Типичная реализация PEG использует так называемый packrat. Он не только загружает всю программу в память перед анализом, но позволяет произвольно откатывать анализатор.

Правило PEG в первую очередь ссылается на грамматические нотации. Но парсеры PEG  —  это обычно анализаторы с рекурсивным спуском и неограниченным возвратом назад. И анализатор packrat делает это эффективно  —  мемоизацией правил.

Всё упрощается. Цена простоты  —  память. Тридцать лет назад была веская причина использовать технологию синтаксического анализа с одним токеном. Память была дорогой. Синтаксический анализ LL(1) и другие технологии, такие как LALR(1), известные благодаря YACC, используют автомат с магазинной памятью для эффективного построения дерева разбора.

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

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

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

С AST также проще работать стороннему коду, проверяющему код на Python и доступному через модуль ast. Этот модуль позволяет создавать узлы AST с нуля и изменять существующие. Также вы можете компилировать новые узлы в байткод. ast создал индустрию языковых расширений Python. Дерево разбора тоже доступно через модуль синтаксического анализа, но работать с ним гораздо сложнее. И оно вышло из моды.

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

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

Возможно Вам также будет интересно:

А ещё у нас есть тест:

Специально для сайта ITWORLD.UZ. Новость взята с сайта NOP::Nuances of programming