Что за программа peg

Oct 17, 2019 09:36 · 1604 words · 8 minute read python peg

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

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

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

Парсинг пользовательского ввода с использованием PEG. Иван Лопатин

Вот некоторые проблемы с 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 здесь означает “это терм, за которым следует ноль или более повторений последовательности ”. Эта грамматика принимает тот же язык, что и первая версия, но она опять-таки не отражает намерения дизайна языка. В частности, она не показывает, что операторы привязаны слева, а это важно, когда вы пытаетесь генерировать код.

Основы Harmony. Урок 4. Слои. Что такое Peg?

Но есть ещё одна досадная проблема в этом примере (да и в 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

Источник: tyvik.ru

PEG ASPM — что это в биосе?

PEG ASPM — энергосберегающая технология, позволяет снизить потребление энергии шины PCI-E, при установленном устройстве PEG (видеокарта).

Сразу скажу — включать нет смысла, может вызвать микротормоза графического адаптера.

Разбираемся

1. Данная функция позволяет настроить режим ASPM для устройства, подключенного к шине привязки процессора. Этот пункт доступен только при активации опции Platform Power Management.
2. ASPM — функция активного энергосбережения, позволяет шине PCI-E использовать меньше энергии при отсутствии данных.
3. PEG расшифровывается как PCI Express Graphics, что значит видеокарта, установленная в разьем PCI-E. Соответственно активировав PEG ASPM — будет включен энергосберегающий режим, при условии что PEG является активным устройством. Как понимаю имеется ввиду при условии что установлена видеокарта в слот PCI-E, тогда для этого слота будет активирован энергосберегающий режим.

Значения функции

PEG ASPM может иметь следующие варианты:

1. Auto — автоматическая настройка.
2. Disabled — работа технологии отключена.
3. L0s — режим экономии энергии путем прекращения подачи пустых сигналов в одном направлении, если никаких данных нет. Когда появятся данные — производительность будет восстановлена быстро.
4. L1 — режим экономии в обеих направлениях, восстановление производительности занимает немного больше времени, чем при использовании L0s.
5. L0sL1 — разрешено использовать оба режима.

Опция биоса AsRock:

Как видим — присутствуют значения PEG0, PEG1, PEG2 — это скорее всего значит разьем #0, #1, #2. Функцию можно включить для каждого разьема.

Включать или нет? Эффект экономии — мизерный. Однако видеокарта требовательна к постоянно высокой пропускной способности шины PCI-E, поэтому при включении могут наблюдаться глюки, лучше не включать.

Источник: virtmachine.ru

PEG парсеры и 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, которому помогают очень строгие требования обратной совместимости и новая структура управления).

Поэтому я не волнуюсь.

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

• Овладей Python, создавая реальные приложения. Часть 1
• Переменная __name__ в Python
• Хитрости на Python

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

Источник: nuancesprog.ru