Находки в опенсорсе: “Кто парсит парсер? Метаграмматики Звучит как название нового фильма Ма…”

Кто парсит парсер? Метаграмматики

Звучит как название нового фильма Марвел, но на самом деле – перед нами достаточно интересная задача.

В CPython с недавних пор (вспоминаем проект Guido van Rossum по внедрению PEG парсера) грамматика описана вот так (ссылка):


lambdef[expr_ty]:
    | 'lambda' a=[lambda_params] ':' b=expression {
        _PyAST_Lambda((a) ? a : CHECK(arguments_ty, _PyPegen_empty_arguments(p)), b, EXTRA) }

lambda_params[arguments_ty]:
    | invalid_lambda_parameters
    | lambda_parameters

На данном примере – грамматика для описания lambda функций.

Что здесь что?
- lambdef и lambda_params обозначают названия правил
- [expr_ty] и [arguments_ty] – метаинформация, которая будет использована парсером позже. Тут буквально куски C кода написаны
- У правил есть варианты: описаны через |, сначала пробуем первое, потом второе и тд
- Правила "складываются" в более сложные правила. Напимер lambdadef содержит в себе: a=[lambda_params] (что конечно же обозначает парсинг параметров lambda функции)
- 'lambda' – обозначает ключевое слово lambda, а ':' - физический символ : в коде
- Внутри {} у нас снова идет C код: данная часть называется "действием", она буквально описывает, какой C код вызывать при успешном парсинге данного правила. _PyAST_Lambda((a) ? a : CHECK(arguments_ty, _PyPegen_empty_arguments(p)), b, EXTRA) – в нашем случае вызывает функцию _PyAST_Lambda

И так мы маленькими кусочками описываем всю большую грамматику Python. Разобрались.

Команда make regen-pegen позволит вам автоматически сгенерировать C парсер из грамматики выше. И получится вот такое:


if (
    (_keyword = _PyPegen_expect_token(p, 609))  // token='lambda'
    && (a = lambda_params_rule(p), !p->error_indicator)  // lambda_params?
    && (_literal = _PyPegen_expect_token(p, 11))  // token=':'
    && (b = expression_rule(p))  // expression
)
{
    Token *_token = _PyPegen_get_last_nonnwhitespace_token(p);

    _res = _PyAST_Lambda(
        (a) ? a : CHECK(arguments_ty, _PyPegen_empty_arguments(p)), 
        b, EXTRA);
    goto done;
}

И уже данный парсер будет вызван, чтобы превратить lambda x, y: ... в AST при работе питона. Подводка закончена.

Что за метаграмматики?

Ключевой вопрос: а кто парсит файл с грамматикой? Кто определяет, что такое "правило", "варианты", "действие"?

Оказывается, что в питоне есть еще один уровень грамматик. Грамматика, которая определяет правила основной грамматики. Мы её так и называем – метаграмматика.

Выглядит она вот так:


rule[Rule]:
    | rulename memoflag? ":" alts NEWLINE INDENT more_alts DEDENT {
          Rule(rulename[0], rulename[1], Rhs(alts.alts + more_alts.alts), memo=opt) }
    | rulename memoflag? ":" NEWLINE INDENT more_alts DEDENT {
          Rule(rulename[0], rulename[1], more_alts, memo=opt) }
    | rulename memoflag? ":" alts NEWLINE { Rule(rulename[0], rulename[1], alts, memo=opt) }

Здесь мы как раз видим в похожем синтаксисе определение, что такое "правило": с "именем" правила и "альтернативами".

Здесь тоже есть куски кода: [Rule] и Rule(rulename[0], rulename[1], Rhs(alts.alts + more_alts.alts), memo=opt), но они уже на питоне. Потому что метаграмматика генерирует парсер для грамматики на питоне:


@memoize
def rule(self) -> Optional[Rule]:
    # rule: rulename memoflag? ":" alts NEWLINE INDENT more_alts DEDENT | rulename memoflag? ":" NEWLINE INDENT more_alts DEDENT | rulename memoflag? ":" alts NEWLINE
    mark = self._mark()
    if (
        (rulename := self.rulename())
        and (opt := self.memoflag(),)
        and (literal := self.expect(":"))
        and (alts := self.alts())
        and (_newline := self.expect('NEWLINE'))
        and (_indent := self.expect('INDENT'))
        and (more_alts := self.more_alts())
        and (_dedent := self.expect('DEDENT'))
    ):
        return Rule(rulename[0], rulename[1], 
                    Rhs(alts.alts + more_alts.alts), memo=opt)

Запускаем make regen-pegen-metaparser, и получаем на выходе питоновский парсер для грамматик.