Главная
Блог разработчиков phpBB
 
+ 17 предустановленных модов
+ SEO-оптимизация форума
+ авторизация через соц. сети
+ защита от спама

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

Anna | 15.06.2014 | нет комментариев
Оглавление

Примитивный интерпретатор с нуля на Python #1
Примитивный интерпретатор с нуля на Python #2
Примитивный интерпретатор с нуля на Python #3
Примитивный интерпретатор с нуля на Python #4

В предыдущей статье мы рассматривали сам язык 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 будет удачно соответствовать пустому списку и не будет поглощать токены, если парсер потерпит неудачу в 1-й раз.

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 мы можем изменить итог. Дальнейший код будет возвращать сумму этих 2-х чисел, скажем.

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 берет два парсера на вход. 1-й парсер соответствует настоящим элементам списка, а 2-й разделителям. В случае триумфа, 2-й парсер должен воротить функцию, которая сочетает разобранные элементы слева и справа в одном значении. Это значение накапливается со каждого списка, слева направо, и в финальном счете возвращается.

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

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 может быть использована с комбинатором Processnext_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

Источник: programmingmaster.ru

Оставить комментарий
Форум phpBB, русская поддержка форума phpBB
Рейтинг@Mail.ru 2008 - 2017 © BB3x.ru - русская поддержка форума phpBB