Реализация PEG парсера

Вдохновленный лишь частичным пониманием PEG, я решил попробовать его реализовать. Результат может получиться и не самым лучшим среди парсеров PEG общего назначения — их уже много (например, TatSu написан на Python и генерирует код Python) — но это хороший способ разобраться в PEG. В дальнейшем я хочу заменить им текущую реализацию парсера в CPython.

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

(Между прочим, в качестве эксперимента я не расставляю ссылки в своём тексте. Если вы чего-то не понимаете, то можете просто погуглить. :-)

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

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

Супер-абстрактный парсер рекурсивного спуска для этого языка определит свою функцию для каждого правила, в которой будут разбираться альтернативы. Например, для statement у нас была бы эта функция:

def statement():
    if assignment():
        return True
    if expr():
        return True
    if if_statement():
        return True
    return False

Конечно, это слишком упрощённый пример: в нём пропущены важные детали, например, что подаётся на вход этой функции и что будет результатом её выполнения.

Давайте начнём с аргументов. Классические парсеры используют отдельный токенизатор, который разбивает ввод (текстовый файл или строку) на серию токенов, таких как ключевые слова, идентификаторы (имена), числа и операторы. Парсеры PEG (как и другие современные парсеры, такие как ANTLR) часто объединяют токенизацию и парсинг, но для своего проекта я решил оставить отдельный токенизатор.

Токенизация Python достаточно сложна, поэтому я не хочу реализовывать её на правилах PEG. Например, вы должны отслеживать отступы (для этого требуется стек внутри токенизатора); интересна также и обработка новых строк в Python (они значимы, кроме заключенных в соответствующие скобки). Многие типы строк также вызывают некоторую сложность. Короче говоря, у меня нет никаких претензий к уже существующему токенизатору Python, поэтому я хочу оставить его как есть. Кстати, у CPython есть два токенизатора: внутренний, который используется парсером, он написан на C, и стандартный библиотечный, который является точной копией, реализованной на чистом Python. Это пригодится в моём проекте.

В классическом токенизаторе обычно простой интерфейс, состоящий из одной функции get_token(). Она каждый раз возвращает следующий токен во входной последовательности, анализируя группу символов. Модуль tokenize в CPython не исключение: его базовый API — это генератор, который выдаёт один токен за раз. Каждый токен представляет собой объект типа TypeInfo, который имеет несколько полей, наиболее важные из которых это тип токена (например, NAME, NUMBER, STRING) и его строковое значение — набор символов, из которых он состоит (например, abc, 42 или "Hello, world"). Есть также дополнительные поля. Например, для индекса токена во входном потоке, что полезно в сообщениях об ошибках.

Специальным типом токена является ENDMARKER, который указывает, что достигнут конец входного файла. Генератор упадёт, если вы проигнорируете его и попытаетесь получить следующий токен.

Но я отвлёкся. Как мы реализуем неограниченный возврат? Откат по списку токенов требует, чтобы вы были в состоянии запомнить позицию в исходном коде и выполнить повторный анализ с этой точки. API токенизатора не позволяет нам передвинуть его указатель, но можно захватить поток токенов в массив и воспроизвести его оттуда, что мы и сделаем. Вы также можете повторить это с помощью itertools.tee(), но это, вероятно, менее эффективно в нашем случае, если обратить внимание на предупреждения в документации.

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

Базовый API очень прост. Объект Tokenizer инкапсулирует массив токенов и позицию в этом массиве. У него есть три основных метода:

• get_token() возвращает следующий токен, сдвигая указатель (или считывет следующий токен из источника, если мы находимся в конце буфера токенов);
• mark() возвращает текущую позицию в буфере;
• reset(pos) устанавливает позицию в буфере (аргумент должен быть получен из mark()).

Мы добавили одну вспомогательную функцию peek_token(), которая возвращает следующий токен без сдвига позиции в буфере.

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

class Tokenizer:
    def __init__(self, tokengen):
        """Call with tokenize.generate_tokens(...)."""
        self.tokengen = tokengen
        self.tokens = []
        self.pos = 0

    def mark(self):
        return self.pos

    def reset(self, pos):
        self.pos = pos

    def get_token(self):
        token = self.peek_token()
        self.pos += 1
        return token

    def peek_token(self):
        if self.pos == len(self.tokens):
            self.tokens.append(next(self.tokengen))
        return self.tokens[self.pos]

Тут кое-что опущено для простоты (например, имена методов и переменных экземпляра должны начинаться с подчеркивания), но это лишь прототип API Tokenizer.

Парсер также должен стать классом, чтобы statement(), expr() и т.д. могли быть реализованы как методы. Токенизатор станет переменной экземпляра, но я не хочу, чтобы методы парсера напрямую вызывали get_token() — вместо этого реализуем в классе Parser метод wait(), который может завершиться успешно или свалиться точно так же, как метод парсера. Аргумент для функции wait() — это ожидаемый токен: либо строка (например, +), либо тип токена (например, NAME). Тип возвращаемого значения пока не суть важен, я вернусь к нему после обсуждения результата работы синтаксического анализатора.

Пусть пока функции правил грамматики возвращают только True или False. Это хорошо для теоретической информатики (там парсер отвечает на вопрос «Является ли это допустимой строкой в ​​языке?»), но не для нас. Наша задача — создание AST. Итак, давайте перепишем этот код так, чтобы каждый метод анализа возвращал объект Node в случае успеха или None в случае ошибки.

Класс Node может быть очень простым:

class Node:
    def __init__(self, type, children):
        self.type = type
        self.children = children

Здесь type определяет тип узла AST (например, add или if), а потомки — это список узлов и токенов (экземпляры TokenInfo). Этого достаточно для компилятора, чтобы сгенерировать код или выполнить другой анализ, такой как линтинг или статическую проверку типов. Хотя в будущем я бы хотел изменить способ представления AST.

Чтобы вписаться в эту схему, метод expect() должен возвращать объект TokenInfo в случае успеха и None в случае ошибки. Чтобы иметь возможность откатиться к предыдущим токенам, я оборачиваю вызовы методов mark() и reset() токенизатора (здесь API не изменяется). Вот что получилось:

class Parser:
    def __init__(self, tokenizer):
        self.tokenizer = tokenizer

    def mark(self):
        return self.tokenizer.mark()

    def reset(self, pos):
        self.tokenizer.reset(pos)

    def expect(self, arg):
        token = self.tokenizer.peek_token()
        if token.type == arg or token.string == arg:
            return self.tokenizer.get_token()
        return None

Ещё раз: я опустил некоторые детали, но это уже рабочий код.

Теперь мне нужно ввести важное требование для методов парсера. Каждый должен либо возвращать Node, располагая токенизатор после последнего токена грамматического правила, которое он распознал; либо None и оставить позицию токенизатора без изменений. Если метод парсера считывает несколько токенов, а затем сваливается, он должен восстановить позицию токенизатора. Для этого предназначены mark() и reset(). Обратите внимание, что expect() также подчиняется этому правилу.

Итак, вот набросок фактического парсера. Тут я использую моржовый оператор из Python 3.8 (:=):

class ToyParser(Parser):
    def statement(self):
        if a := self.assignment():
            return a
        if e := self.expr():
            return e
        if i := self.if_statement():
            return i
        return None

    def expr(self):
        if t := self.term():
            pos = self.mark()
            if op := self.expect("+"):
                if e := self.expr():
                    return Node("add", [t, e])
            self.reset(pos)
            if op := self.expect("-"):
                if e := self.expr():
                    return Node("sub", [t, e])
            self.reset(pos)
            return t
        return None

    def term(self):
        # Very similar...

    def atom(self):
        if token := self.expect(NAME):
            return token
        if token := self.expect(NUMBER):
            return token
        pos = self.mark()
        if self.expect("("):
            if e := self.expr():
                if self.expect(")"):
                    return e
        self.reset(pos)
        return None

Я опустил реализацию некоторых методов, чтобы у читателя была возможность попрактиковаться самому. Это действительно лучше, чем просто читать о том, как реализовывается такой синтаксический анализатор. В конце концов, мы будем генерировать такой код автоматически из грамматики. Константы, такие как NAME и NUMBER, импортируются из модуля token стандартной библиотеки. Это дополнительно завязывает нас на текущую реализацию токенизатора Python. Если мы хотим создать обобщённый PEG парсер, то мы должны найти способы избежать этого.

Также обратите внимание, что я немного обманул. Метод expr должен быть леворекурсивным, но я сделал парсер праворекурсивным, потому что парсер рекурсивного спуска не работает с леворекурсивными грамматическими правилами. Это можно исправить, но это всё же тема некоторых научных исследований, и я хотел бы поговорить об этом отдельно. Просто имейте в виду, что эта реализация не на 100% соответствует нашей упрощённой грамматике.

Ключевые вещи, которые я хочу, чтобы вы пока поняли:

• Правила грамматики соответствуют методам парсера, и когда правило грамматики ссылается на другое, то оно будет вызывать метод другого правила.
• Когда последовательность токенов может трактоваться по-разному, соответствующие методы парсера вызываются друг за другом.
• Когда правило грамматики ссылается на токен, метод вызывает функцию expect().
• Если парсер успешно распознает своё правило грамматики в текущей позиции, он возвращает соответствующий узел AST; если он не может распознать своё правило грамматики, он возвращает None.
• Методы парсера должны явно сбрасывать позицию токенизатора, когда они прекращают анализ после использования одного или нескольких токенов (прямо или косвенно, вызывая другой успешный метод синтаксического анализа). Это применимо не только при отказе от одного из вариантов, чтобы перейти к следующему, но и при отказе от анализа в целом.

Если все методы синтаксического анализа подчиняются этим правилам, то нет необходимости оборачивать каждый в вызовы mark() и reset(). Это можно доказать с помощью индукции.

Кроме того, заманчиво попытаться избавиться от явных вызовов mark() и reset() с помощью диспетчера контекста и оператора with, но не получится: не следует вызывать reset()в случае успеха! В качестве дальнейшего исправления вы можете попытаться использовать исключения для потока управления, чтобы менеджер контекста знал, следует ли сбрасывать токенизатор (я думаю, что TatSu делает что-то подобное). Например, как-то так:

    def statement(self):
        with self.alt():
            return self.assignment()
        with self.alt():
            return self.expr()
        with self.alt():
            return self.if_statement()
        raise ParsingFailure

В частности, небольшая лестница операторов if в atom() для распознавания выражения в скобках может быть записана как:

        with self.alt():
            self.expect("(")
            e = self.expr()
            self.expect(")")
            return e

Но мне кажется это слишком "магическим" — при чтении такого кода вы должны помнить, что каждый метод синтаксического анализа (в том числе и wait()) может вызывать исключение. И что это исключение перехватывается и игнорируется менеджером контекста в операторе with. Это довольно необычно, хотя и реализуемо (с помощью возврата True из __exit__). Однако, моя конечная цель — генерировать код на C, а не Python, а в C нет оператора with для изменения потока управления.

В любом случае, вот несколько тем для следующих частей:

• генерация методов парсера из грамматики;
• packrat-парсинг (мемоизация);
• особенности EBNF, такие как (x | y), [x y ...], x*, x+;
• трассировка (для отладки парсера или грамматики);
• особенности PEG, такие как lookahead и «cut»;
• как обрабатывать лево-рекурсивные правила;
• генерация кода на C.

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