Теперь, когда я набросал основу самописного парсера, давайте перейдём к генерации его методов из грамматики, как я и обещал. Также покажу как реализовать packrat-парсер с помощью декоратора @memoize.

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

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

Итак, мы создаем простой компилятор компилятора. Я немного упрощу грамматическую нотацию до такой степени, чтобы у нас остались только правила и альтернативы; этого на самом деле достаточно для той игрушечной грамматики, которую я использовал в предыдущих частях:

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

Используя полную запись, мы можем описать грамматику как:

grammar: rule+ ENDMARKER
rule: NAME ':' alternative ('|' alternative)* NEWLINE
alternative: item+
item: NAME | STRING

Это наша первая мета-грамматика (грамматика для грамматик), и нашим генератором синтаксического анализатора будет мета-компилятор (компилятор — это программа, которая переводит программы с одного языка на другой; мета-компилятор — это компилятор, где на входе — грамматика, а на выходе — парсер).

Простой способ описать мета-грамматику — использовать только встроенные типы данных: правая часть правила — список списков элементов, каждый из которых может быть просто строкой. (Кстати, мы можем разделить NAME и STRING, проверив, является ли первый символ кавычкой)

Для правил я использую простой класс Rule, и вся грамматика представляет собой список таких объектов. Вот класс Rule, исключая __repr__ и __eq__:

class Rule:
    def __init__(self, name, alts):
        self.name = name
        self.alts = alts

А вот класс GrammarParser, который его использует:

class GrammarParser(Parser):
    def grammar(self):
        pos = self.mark()
        if rule := self.rule():
            rules = [rule]
            while rule := self.rule():
                rules.append(rule)
            if self.expect(ENDMARKER):
                return rules    # <------------- final result
        self.reset(pos)
        return None

    def rule(self):
        pos = self.mark()
        if name := self.expect(NAME):
            if self.expect(":"):
                if alt := self.alternative():
                    alts = [alt]
                    apos = self.mark()
                    while (self.expect("|")
                           and (alt := self.alternative())):
                        alts.append(alt)
                        apos = self.mark()
                    self.reset(apos)
                    if self.expect(NEWLINE):
                        return Rule(name.string, alts)
        self.reset(pos)
        return None

    def alternative(self):
        items = []
        while item := self.item():
            items.append(item)
        return items

    def item(self):
        if name := self.expect(NAME):
            return name.string
        if string := self.expect(STRING):
            return string.string
        return None

Обратите внимание на использование ENDMARKER. Там я убеждаюсь, что после последнего правила ничего не осталось (а это может случиться, если в грамматике есть опечатка). Также я указал на место, где метод grammar() возвращает список правил. Всё остальное очень похоже на класс ToyParser из прошлой статьи, поэтому я не буду на нём останавливаться. Просто обратите внимание, что item() возвращает строку, alternative() возвращает список строк, а переменная alts внутри rule() собирает список списков строк. Затем метод rule() объединяет имя правила (строку) и преобразует его в объект Rule.

Если мы применим этот алгоритм к нашей игрушечной грамматике, то метод grammar() вернёт следующий список правил:

[
  Rule('statement', [['assignment'], ['expr'], ['if_statement']]),
  Rule('expr', [['term', "'+'", 'expr'],
                ['term', "'-'", 'term'],
                ['term']]),
  Rule('term', [['atom', "'*'", 'term'],
                ['atom', "'/'", 'atom'],
                ['atom']]),
  Rule('atom', [['NAME'], ['NUMBER'], ["'('", 'expr', "')'"]]),
  Rule('assignment', [['target', "'='", 'expr']]),
  Rule('target', [['NAME']]),
  Rule('if_statement', [["'if'", 'expr', "':'", 'statement']]),
]

Теперь, когда у нас есть часть синтаксического анализа нашего мета-компилятора, давайте сделаем генератор кода. Вместе они образуют элементарный мета-компилятор:

def generate_parser_class(rules):
    print(f"class ToyParser(Parser):")
    for rule in rules:
        print()
        print(f"    @memoize")
        print(f"    def {rule.name}(self):")
        print(f"        pos = self.mark()")
        for alt in rule.alts:
            items = []
            print(f"        if (True")
            for item in alt:
                if item[0] in ('"', "'"):
                    print(f"            and self.expect({item})")
                else:
                    var = item.lower()
                    if var in items:
                        var += str(len(items))
                    items.append(var)
                    if item.isupper():
                        print("            " +
                              f"and ({var} := self.expect({item}))")
                    else:
                        print(f"            " +
                              f"and ({var} := self.{item}())")
            print(f"        ):")
            print(f"            " +
              f"return Node({rule.name!r}, [{', '.join(items)}])")
            print(f"        self.reset(pos)")
        print(f"        return None")

Этот код довольно уродливый, но он работает (вроде), и в будущем я в любом случае его перепишу.

Некоторые строки внутри цикла for alt in rule.alts могут потребовать объяснения: для каждого элемента в альтернативе мы выбираем один из 3х вариантов:

• если элемент является строковым литералом, например '+', мы генерируем self.expect('+')
• если элемент полностью в верхнем регистре, например NAME, мы генерируем (name := self.expect(NAME))
• в противном случае, например если это expr, мы генерируем (expr := self.expr())

Если существует несколько элементов с одним и тем же именем в одном варианте (например, term '-' term), то мы добавляем цифру ко второму. Здесь также есть небольшая ошибка, которую я исправлю в следующем эпизоде.

Вот немного результата его работы (весь класс был бы очень скучным). Не беспокойтесь об избыточном коде if (True and...), который необходим, чтобы каждое сгенерированное условие могло начинаться с and. Компилятор байт-кода Python оптимизирует это.

class ToyParser(Parser):
    @memoize
    def statement(self):
        pos = self.mark()
        if (True
            and (assignment := self.assignment())
        ):
            return Node('statement', [assignment])
        self.reset(pos)
        if (True
            and (expr := self.expr())
        ):
            return Node('statement', [expr])
        self.reset(pos)
        if (True
            and (if_statement := self.if_statement())
        ):
            return Node('statement', [if_statement])
        self.reset(pos)
        return None
    ...

Обратите внимание на декоратор @memoize: я ввёл его, чтобы перейти к другой теме: использование мемоизации, чтобы сделать сгенерированный парсер достаточно быстрым.

Вот функция memoize(), реализующая этот декоратор:

def memoize(func):
    def memoize_wrapper(self, *args):
        pos = self.mark()
        memo = self.memos.get(pos)
        if memo is None:
            memo = self.memos[pos] = {}
        key = (func, args)
        if key in memo:
            res, endpos = memo[key]
            self.reset(endpos)
        else:
            res = func(self, *args)
            endpos = self.mark()
            memo[key] = res, endpos
        return res

    return memoize_wrapper

Как и в других декораторах, она содержит вложенную функцию, которая заменит (или обернёт) декорируемую, например, метод statement() класса ToyParser. Поскольку оборачиваемая функция является методом, враппер также фактически является методом: его первый аргумент называется self и ссылается на экземпляр ToyParser, для которого вызывается декорированный метод.

Враппер кэширует результат вызова метода для каждой входной позиции — вот почему он называется packrat-парсер! [прим. пер. packrat — "воришка", однако в рускоязычных источниках этот термин не переводится] Кэш — это словарь словарей, который хранится в экземпляре Parser. Ключ внешнего словаря — позиция в потоке входных данных; я добавил также self.memos = {} в Parser .__ init__() для его инициализации. Внутренние словари добавляются по мере необходимости; их ключи состоят из метода и его аргументов. (В текущем дизайне нет аргументов, но мы могли бы мемоизировать функцию expect(), у которой он есть, весьма тривиально)

Результат работы метода парсера представляется в виде кортежа, поскольку там действительно два значения: собственно результат (для наших сгенерированных методов это Node для совпавшего правила) и указатель на текущую позицию во входном потоке, которую мы получаем из self.mark(). Таким образом, мы кэшируем как возвращаемое значение (res), так и новую позицию (endpos) во внутреннем словаре с мемоизированными значениями. При последующих вызовах того же метода синтаксического анализа с теми же аргументами в той же позиции входных данных мы будем брать их из кэша. Для этого достаточно всего лишь перевести указатель на позицию ввода с помощью self.reset() и посмотреть в кэш.

Также важно кэшировать и отрицательные результаты — на самом деле большинство вызовов будут негативными. В этом случае возвращаемое значение равно None, а позиция ввода не изменяется. Вы можете добавить assert, чтобы проверить это.

Примечание. В Python принято реализовывать кэш в локальной переменной в функции memoize(). В нашем случае так не получится: как я выяснил в самом конце отладки, каждый экземпляр Parser обязан иметь свой собственный кэш. Тем не менее, вы можете избавиться от вложенных словарей, используя (pos, func, args) в качестве ключа.

На следующей неделе я подготовлю код и трейсы, чтобы показать, как всё это на самом деле собирается и выполняется при разборе примера программы. Я всё еще в поисках лучшего способа визуализации совместной работы буфера токенизации, парсера и кэша. Возможно, мне удастся создать анимированный gif в ASCII вместо того, чтобы просто выводить листинги трассировки в виде текста.

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