PEG парсеры

Автор оригинала: 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

Похожие публикации

AdBlock похитил этот баннер, но баннеры не зубы — отрастут

Подробнее
Реклама

Комментарии 9

    0
    Не знаю что было раньше, но Гвидо активно обсуждает вещи в довольно интересном проекте Tatsu
      +1
      Он также позволяет создавать узлы с нуля и изменять существующие, а также компилировать части в байт-код. Последнее позволило создать целую индустрию языковых расширений для Python.
      Это что за расширения? Хотелось бы расширение позволящее писать в питоне на coffeescript!
        0
        Насколько я помню, в PyCharm до версии 3.6 дебаггер анализировал байт-код и переписывал его на лету, чтобы иметь возможность вставить свои управляющие конструкции. Доклад на Youtube.
        0
        Сейчас же я хочу объединить эти вещи и посмотреть, сможем ли мы создать новый парсер для CPython, который использует PEG и packrat для создания AST непосредственно во время синтаксического анализа.


        Так и не уловил почему раньше AST нельзя было создавать непосредственно.
        Объясните кто знает, плиз. Если пишешь руками рекурсивный спуск, то должны быть как кажется достаточно веские причины не генерить AST сразу. Я правильно понимаю что дерево разбора было просто следствием использования генератора парсеров (pgen)?
          0
          Именно так оно и было, но около 15 лет назад мы обнаружили, что компилятор переусложнён. Так что мы выделили отдельно AST и фазу трансформации AST из дерева разбора.

          Изначально так и было — AST генерировался в процессе парсинга. Но, видимо, поддерживать это стало проблематичным, так что генерацию AST вынесли отдельно.
            0
            Я имел ввиду непосредственное (без дерева разбора) создание AST.
            Мне непонятно было ли дерево разбора (как промежуточный этап) для чего-то нужно или это просто непреодолимая особенность pgen.

            Например если взглянуть на дерево разбора простейшего выражения, то видно насколько оно избыточно (питон плохо знаю если что):
            import parser
            import symbol
            import token
            from pprint import pprint
            
            x = parser.expr('1 + 2 * 3')
            y = x.tolist()
            
            def humanize(x):
                for i, y in enumerate(x):
                    if type(y) is int:
                       x[i] = symbol.sym_name.get(y) or token.tok_name.get(y) or y
                    try:
                        humanize(y)
                    except:
                        pass
            
            humanize(y)
            
            pprint(y)
            

            результат:
            ['eval_input',
             ['testlist',
              ['test',
               ['or_test',
                ['and_test',
                 ['not_test',
                  ['comparison',
                   ['expr',
                    ['xor_expr',
                     ['and_expr',
                      ['shift_expr',
                       ['arith_expr',
                        ['term',
                         ['factor', ['power', ['atom_expr', ['atom', ['NUMBER', '1']]]]]],
                        ['PLUS', '+'],
                        ['term',
                         ['factor', ['power', ['atom_expr', ['atom', ['NUMBER', '2']]]]],
                         ['STAR', '*'],
                         ['factor',
                          ['power', ['atom_expr', ['atom', ['NUMBER', '3']]]]]]]]]]]]]]]]],
             ['NEWLINE', ''],
             ['ENDMARKER', '']]
            


            В AST было бы только поддерево arith_expr, т.к. остальная вавилонская башня (выше) не несет никакой информации о разбираемом коде.
            И тут два варианта:
            1. Я чего-то недопонимаю и эта информация для чего-то нужна.
            2. Автоматический парсер pgen вынужден генерить узлы дерева на каждое синтаксическое правило и строить сразу AST технически невозможно.

            Если 2, то все понятно. Если 1, то хотелось бы пояснения от знающих.
              0
              Скорее всего 2. Вернее, технически возможно, но очень сложно стало со временем. В итоге Гвидо сделал промежуточное представление (интерфейс, абстракцию). Скорее всего смысл был в том, чтобы совсем не трогать генерацию AST при изменении работы парсера (добавлении нового синтаксиса). В итоге такого разбиения мы получаем 2 вещи попроще — одна константна, а меняется только парсинг.

              Видимо, сейчас он пробует всё-таки эти 2 модуля совместить обратно. Надеюсь, что получится.
            +1
            Я правильно понимаю что дерево разбора было просто следствием использования генератора парсеров (pgen)?

            По факту даже с использованием генератора парсеров дерево разбора можно не строить, если использовать Listener прямо во время парсинга. ANTLR позволяет такое делать. Обработка узлов усложняется, т.к. она становится восходящей и менее явной. Однако это дает сильную экономию памяти, т.к. "вавилонские башни" при этом можно сразу схлопывать и проводить другие оптимизации.


            В Positive Technologies мы работаем над статическими анализаторами кода, в которых на одном этапе деревья разбора конвертируются в универсальные AST. Однажды столкнулись с проблемой: дерево разбора PL/SQL файла в 1 млн. строк занимает в памяти примерно 2.5 Гб (используется огромная грамматика PL/SQL). Мы переписали старый код на новый, в котором универсальное AST строится сразу вообще без использования дерева разбора. Это дало уменьшение потребления памяти в 2.5 раза, а также увеличило производительность.

              0
              Ясно. Спасибо.

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

          Самое читаемое