Простой интерпретатор с нуля на Python #2

В предыдущей статье мы рассматривали сам язык IMP и основную структуру интерпретатора. Также, мы тщательно рассмотрели лексер. В этой статье мы будем писать небольшой парсер для нашего языка. Он будет извлекать AST (abstract syntax tree) из списка токенов, сгенерированных лексером. Библиотека комбинатора будет независимая, то есть с помощью нее можно будет написать парсер для любого языка.

Что такое комбинаторы парсеров?

Есть очень много способов написать парсер. Самым простым и быстрым способом сделать это являются комбинаторы.

Вы можете считать парсер функцией, которая принимает поток токенов. Если успешно, то парсер будет «съедать» немного токенов из потока. Функция вернет часть финального AST вместе с остальными токенами. Комбинатор — это функция, которая производит парсер, как его результат, обычно после приема одного или нескольких анализаторов (парсеров) в качестве входных данных, отсюда и название — «комбинатор». Вы можете использовать комбинаторы для создания законченного парсера для языка, как IMP, путем создания множества маленьких парсеров для каждой части языка.

Наш маленький комбинатор

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

Для начала, давайте создадим класс Result. Каждый парсер будет возвращать экземпляр класса Result (в случае успеха), или None в случае неудачи. Result включает в себя value (значение, часть AST) и позиция (индекс следующего токена в потоке).

class Result:
    def __init__(self, value, pos):
        self.value = value
        self.pos = pos

    def __repr__(self):
        return 'Result(%s, %d)' % (self.value, self.pos)

Дальше мы создадим основной класс Parser. Прежде, я говорил, что парсеры являются функциями, которые принимают поток токенов. На самом деле мы будем определять парсеры как объекты с методом __call__. Это значит, что объект парсера будет вести себя так, как будто это функция, но мы также можем предоставлять дополнительную функциональность путем создания операторов.

class Parser:
    def __call__(self, tokens, pos):
        return None  # subclasses will override this

    def __add__(self, other):
        return Concat(self, other)

    def __mul__(self, other):
        return Exp(self, other)

    def __or__(self, other):
        return Alternate(self, other)

    def __xor__(self, function):
        return Process(self, function)

Метод, который на самом деле выполняет парсинг — __call__. Входными данными является полный список токенов (созданный лексером) и индекс списка, с указанием следующего токена. Реализация по умолчанию всегда возвращает None (неудача). В подклассах будет собственный метод __call__.

Такие методы, как __add__, __mul__, __or__ и __xor__ определяют +, *, | и ^ операторы соответственно. Каждый оператор предоставляет шорткат для вызова определенного комбинатора. Мы рассмотрим каждый из них вкратце.

Теперь мы рассмотрим простой комбинатор под названием Reserved. Reserved будет использован для парсинга зарезервированных слов и операторов; он будет принимать токены с определенным значением и тег. Помните, что токены являются парой значение-тег. token[0] — значение, token[1] — тег.

class Reserved(Parser):
    def __init__(self, value, tag):
        self.value = value
        self.tag = tag

    def __call__(self, tokens, pos):
        if pos < len(tokens) and 
           tokens[pos][0] == self.value and 
           tokens[pos][1] is self.tag:
            return Result(tokens[pos][0], pos + 1)
        else:
            return None

Сейчас в можете сказать: «Я думал, что комбинаторы должны быть функциями, которые возвращают парсеры.» Подкласс совсем не выглядит как функция. Подкласс, это как функция, если вы думаете о конструкторе как о функции, возвращающей объект (который в этом случае является callable). Создание подклассов является простым путем определения новых комбинаторов, так как нам нужно всего лишь предоставить конструктор и метод __call__, и мы по-прежнему сохраняем остальную функциональность (например, перегрузку операторов).

Двигаемся дальше. Комбинатор Tag очень похож на Reserved. Он находит токены, соответствующие конкретному тегу. Значение может быть чем угодно.

class Tag(Parser):
    def __init__(self, tag):
        self.tag = tag

    def __call__(self, tokens, pos):
        if pos < len(tokens) and tokens[pos][1] is self.tag:
            return Result(tokens[pos][0], pos + 1)
        else:
            return None

Комбинаторы Tag и Reserved являются нашими примитивами. Все остальные комбинаторы будут построены от них на самом базовом уровне.

Комбинатор Concat берет два парсера в качестве инпута (left и right). При применении парсер Concat будет применять левый парсер, а затем правый [парсер]. Если оба успешны, результирующее значение будет содержать пару левых и правых результатов. Если хотя бы один не срабатывает, то вернется None.

class Concat(Parser):
    def __init__(self, left, right):
        self.left = left
        self.right = right

    def __call__(self, tokens, pos):
        left_result = self.left(tokens, pos)
        if left_result:
            right_result = self.right(tokens, left_result.pos)
            if right_result:
                combined_value = (left_result.value, right_result.value)
                return Result(combined_value, right_result.pos)
        return None

Concat полезен для разбора специфической последовательности токенов. Например, для разбора 1+2, вы можете написать

parser = Concat(Concat(Tag(INT), Reserved('+', RESERVED)), Tag(INT))

или более кратко, используя оператор стенографии

parser = Tag(INT) + Reserved('+', RESERVED) + Tag(INT)

Комбинатор Alternative тоже очень похож на предыдущие. Он также принимает left- и right-парсеры. Если успешно, то возвращается результат, иначе — он принимает right-парсер и возвращает его результат.

class Alternate(Parser):
    def __init__(self, left, right):
        self.left = left
        self.right = right

    def __call__(self, tokens, pos):
        left_result = self.left(tokens, pos)
        if left_result:
            return left_result
        else:
            right_result = self.right(tokens, pos)
            return right_result

Alternative полезен при выборе возможных парсеров. Для примера, если нам нужно разобрать бинарный оператор:

parser = Reserved('+', RESERVED) |
         Reserved('-', RESERVED) |
         Reserved('*', RESERVED) |
         Reserved('/', RESERVED)

Класс Opt полезен для дополнительного текста, например else. Он принимает один парсер. Если этот парсер успешен, то результат возращается нормально. Если нет, то успешный результат все-равно возвращается, но его значение равно None. Токены не потребляются в случае неудачи; позиция результата такая же, как и позиция инпута.

class Opt(Parser):
    def __init__(self, parser):
        self.parser = parser

    def __call__(self, tokens, pos):
        result = self.parser(tokens, pos)
        if result:
            return result
        else:
            return Result(None, pos)

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

class Rep(Parser):
    def __init__(self, parser):
        self.parser = parser

    def __call__(self, tokens, pos):
        results = []
        result = self.parser(tokens, pos)
        while result:
            results.append(result.value)
            pos = result.pos
            result = self.parser(tokens, pos)
        return Result(results, pos)

Комбинатор Process очень полезен нам для манипулирования значениями результатов. Его инпут — парсер и функция. Когда парсер успешен, результирующее значение отправляется в функцию вместо оригинального значения возвращается значение из функции. Мы будем использовать Process для постройки AST-узлов из пар и списков (возвращаемых Concat и Rep).

class Process(Parser):
    def __init__(self, parser, function):
        self.parser = parser
        self.function = function

    def __call__(self, tokens, pos):
        result = self.parser(tokens, pos)
        if result:
            result.value = self.function(result.value)
            return result

В качестве примера, рассмотрим парсер, который мы построили с помощью Concat. Когда он разбирает 1+1, результатом будет (('1', '+'), '2'), что не очень удобно. С Process мы можем изменить результат. Следующий код будет возвращать сумму этих двух чисел, например.

def process_func(parsed):
    ((l, _), r) = parsed
    return int(l) + int(r)

better_parser = parser ^ process_func

Lazy является менее очевидным комбинатором. Вместо того, чтобы взять на вход парсер, он берет функцию с нулевым аргументом, которая возвращает парсер. Комбинатор Lazy не будет вызывать функцию, чтобы получить парсер, пока он не применится. Это нужно для построения рекурсивных парсеров. Поскольку анализатор (парсер) относится к самому себе, мы не можем просто так взять, и определить его с помощью ссылки; в то время, как выражение парсера исполняется, он не продефинен. Нам это не нужно в таких языках, как Haskell или Scala, так как они используют ленивые выражения, но Python не такой.

class Lazy(Parser):
    def __init__(self, parser_func):
        self.parser = None
        self.parser_func = parser_func

    def __call__(self, tokens, pos):
        if not self.parser:
            self.parser = self.parser_func()
        return self.parser(tokens, pos)

Следующий комбинатор Phrase берет одиночный парсер на вход, применяет его, и возвращает его результат. Единственная загвоздка в том, что он не выполнится, если не поглотит все токены. Анализатором топового уровня будет как раз таки Phrase. Он не позволяет нам мэтчить программы, у которых есть мусор в конце.

class Phrase(Parser):
    def __init__(self, parser):
        self.parser = parser

    def __call__(self, tokens, pos):
        result = self.parser(tokens, pos)
        if result and result.pos == len(tokens):
            return result
        else:
            return None

Последний комбинатор, к сожалению, самый сложный. Смысл Exp очень прост; он используется для матчинга (match) выражения, которое состоит из списка элементов, разделенных чем-то. Вот пример составных операторов:

a := 10;
b := 20;
c := 30

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

def compound_stmt():
    return stmt() + Reserved(';', RESERVED) + stmt()

Создание stmt:

def stmt():
    return Lazy(compound_stmt) | assign_stmt()

Итак, stmt вызывает compound_stmt, который вызывает stmt. Они будут вызывать друг друга, пока мы не получим переполнение буфера. Такая проблема присуща не только составным операторам, и называется она left recursion.

Благо, Exp предоставлять возможность обойти left recursion, просто разбирая список (относительно также, как и Rep). Exp берет два парсера на вход. Первый парсер соответствует настоящим элементам списка, а второй разделителям. В случае успеха, второй парсер должен вернуть функцию, которая комбинирует разобранные элементы слева и справа в одном значении. Это значение накапливается со всего списка, слева направо, и в конечном счете возвращается.

Посмотрим на код:

class Exp(Parser):
    def __init__(self, parser, separator):
        self.parser = parser
        self.separator = separator

    def __call__(self, tokens, pos):
        result = self.parser(tokens, pos)

        def process_next(parsed):
            (sepfunc, right) = parsed
            return sepfunc(result.value, right)
        next_parser = self.separator + self.parser ^ process_next

        next_result = result
        while next_result:
            next_result = next_parser(tokens, result.pos)
            if next_result:
                result = next_result
        return result

result будет содержать все, что было отпарсено за все время. Функция process_next может быть использована с комбинатором Process. next_parser принимает separator, а затем parser, чтобы получить следующий элемент списка. process_next создаст новый результат путем принятия функции-сепаратора на текущий результат и на свежеспарсенный элемент. next_parser принимается в цикле, пока он будет в состоянии принимать элементы.

Давайте посмотрим, как Exp может быть использован для решения проблемы compound_stmt:

def assign_stmt():
    ...

def compound_sep():
    def process_sep(parsed):
        return lambda l, r: CompoundStmt(l, r)
    return Reserved(';', RESERVED) ^ process_sep

def compound_stmt():
    return Exp(assign_stmt(), compound_sep())

Мы можем написать даже так:

def compound_stmt():
    return assign_stmt() * compound_sep()

Мы углубимся в это, когда рассмотрим разбор арифметических выражений в следующей статье.

Скачать полный исходный код: imp-interpreter.tar.gz

Автор: duse

Источник