Простой интерпретатор с нуля на Python (часть 3)

Таким образом, мы написали лексер библиотеку комбинатора парсеров для нашего интерпретатора. В этой части, мы создадим структурные данные абстрактного синтаксического дерева (AST), и напишем парсер, используя нашу библиотеку комбинаторов, которые переводят список токенов, возвращенных лексером, в абстрактное синтаксическое дерево (AST). После того, как мы распарсим AST, запустить программу будет очень просто.

Определяем AST

Прежде, чем мы начнём написание нашего парсера, нам нужно определить структуры данных, которые наш парсер будет возвращать. Определим их при помощи классов. Каждый синтаксический элемент IMP будет иметь соответствующий класс. Объекты этого класса будут отображать ноды в AST.

В нашем IMP всего три структуры: арифметические выражения (используемые для вычисления чисел), логические выражения (используемые для вычисления условий для if и while высказываний), и состояния. Начнём с арифметических выражений, так, как оставшиеся два зависят от него.
Арифметическое выражение может принимать одну из трёх форм:

• Буквенные числовые константы, такие как 42
• Переменные, такие как x
• Бинарные операции, такие как x + 42. Они образованны из других арифметических выражений

Мы также можем группировать выражения вместе скобками (как (x+2)*3). Это не сколько иной тип выражения, сколько иной способ разбора выражения.
Определим три класса для этих форм, плюс базовый класс для основных арифметических выражений. Пока классы не делают ничего кроме хранения информации. Опишем метод __repr__, позволит нам выводить на печать AST во время отладки. Все AST классы будут наследовать Equality, поэтому мы сможем сможем проверять одинаковость двух AST объектов, что тоже может пригодиться при тестировании.

from equality import *

class Aexp(Equality):
    pass

class IntAexp(Aexp):
    def __init__(self, i):
        self.i = i

    def __repr__(self):
        return 'IntAexp(%d)' % self.i

class VarAexp(Aexp):
    def __init__(self, name):
        self.name = name

    def __repr__(self):
        return 'VarAexp(%s)' % self.name

class BinopAexp(Aexp):
    def __init__(self, op, left, right):
        self.op = op
        self.left = left
        self.right = right

    def __repr__(self):
        return 'BinopAexp(%s, %s, %s)' % (self.op, self.left, self.right)

Логические выражения немного сложнее. Существует 4 типа логических выражений:

• Выражения отношений (такие как x < 10)
• And выражения (такие как x < 10 and y > 20)
• Or выражения
• Not выражения

Левые и правые части выражений отношений — это арифметические выражения. Левые и правые части and, or, или not выражений — логические выражения. Подобное разграничение типов помогает нам избегать бессмысленные выражения вроде x < 10 and 30.

class Bexp(Equality):
    pass

class RelopBexp(Bexp):
    def __init__(self, op, left, right):
        ...

class AndBexp(Bexp):
    def __init__(self, left, right):
        ...
class OrBexp(Bexp):
    def __init__(self, left, right):
        ...

class NotBexp(Bexp):
    def __init__(self, exp):
        ...

Утверждения (statements) могут содержать арифметические и логические выражения одновременно. Существует 4 типа выражений: присвоение, соединение, условия и циклы.

class Statement(Equality):
    pass

class AssignStatement(Statement):
    def __init__(self, name, aexp):
         ...

class CompoundStatement(Statement):
    def __init__(self, first, second):
        ...

class IfStatement(Statement):
    def __init__(self, condition, true_stmt, false_stmt):
        ...

class WhileStatement(Statement):
    def __init__(self, condition, body):
        ...

Примитивы

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

Первый парсер, который мы рассмотрим, это парсер keyword. Им является всего лишь специальная версия Reserved-комбинатора с использованием тэга RESERVED, которым помечены все ключевые слова. Запомните, Reserved соответствует одиночному токену, у которого значение и тэг такие же, как у переданных.

def keyword(kw):
    return Reserved(kw, RESERVED)

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

Парсер id используется для сопоставления именам переменных. Он использует комбинатор Tag, который сопоставляет токен с указанным тэгом.

id = Tag(ID)

Парсер num используется для сопоставления целых чисел. Он работает почти как и id, за исключением того, что мы использует комбинатор Process (точнее ^ оператор, который вызывает Process) для преобразования токена в конкретное целое число.

num = Tag(INT) ^ (lambda i: int(i))

Разбор арифметических выражений

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

Сперва мы определим парсер aexp_value, который будет конвертировать значения, возвращенные num и id в фактические выражения.

def aexp_value():
    return (num ^ (lambda i: IntAexp(i))) | 
           (id  ^ (lambda v: VarAexp(v)))

Мы использовали оператор |, который является сокращением для комбинатора Alternate. Это позволит разбирать выражения целых чисел первыми. Если они провалятся, будет произведена попытка разбора выражения с переменной.

Отметим, что мы определили aexp_value как функцию без аргументов вместо глобального значения, так же, как мы поступили и с id и num. Так же поступим и со всеми оставшимися парсерами. И сделали мы это потому, не хотим, чтобы код каждого парсера был вычислен сразу. Если бы мы определили каждый парсер как глобальный, каждый парсер не смог бы сослаться на другие парсеры, которые следуют далее в том же исходном файле, потому, как они ещё не были бы объявлены. Это сделало бы невозможным определить рекурсивные парсеры, и исходный код стал бы менее читабелен.

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

def process_group(parsed):
    ((_, p), _) = parsed
    return p

def aexp_group():
    return keyword('(') + Lazy(aexp) + keyword(')') ^ process_group

Функция process_group используется с комбинатором Process (^ оператор). Она просто отбрасывает токены скобок и возвращает выражение внутри. Фактически, aexp_group тоже является парсером. Запомните, оператор + это сокращение для комбинатора Concat. Так что она распарсит '(', следующую за арифметическим выражением (разобранным aexp, которое мы скоро определим), следующее за ')'. Необходимо избегать прямого вызова aexp, потому, как aexp вызывает aexp_group, что приведёт к бесконечной рекурсии. Используем комбинатор Lazy, который откладывает вызов aexp до тех пор, пока парсер не будет применён к каким-либо входным данным.

Далее, мы комбинируем aexp_value и aexp_group при помощи aexp_term. Выражение aexp_term — это любое простое самостоятельное выражение, в котором мы не должны заботиться о старшинстве операторов по отношению к другим выражениям.

def aexp_term():
    return aexp_value() | aexp_group()

Сейчас мы подходим к каверзной части: операторы и старшинство. Будет проще определить другой парсер для aexp и выбрасывать его совместно с aexp_term. Это приведёт выражение:

1 + 2 * 3

к такому неверному разбору:

(1 + 2) * 3

Парсер должен знать о старшинстве операторов, и он должен группировать друг с другом операторы с более высоким старшинством.

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

def process_binop(op):
    return lambda l, r: BinopAexp(op, l, r)

Функция process_binop — это то, что создаёт объект BinopAexp. Эта функция принимает любой арифметический оператор и возвращает функцию, которая комбинирует пары выражений, используя этот оператор…

Функция process_binop должна использоваться с комбинатором Exp (* оператор). Комбинатор Exp разбирает список выражений с разделителем между каждой парой выражений. Левый оператор Exp — парсер, который сопоставляет индивидуальные элементы списка (в нашем случае, арифметических выражений). Правый оператор — это парсер, который сопоставит разделители (операторы). Неважно, какой разделитель сопоставлен, правый парсер вернёт функцию, которая, учитывая соответствие операторов, возвращает функцию объединения. Функция объединения принимает разобранные выражения слева и справа от разделителя, и возвращаете единое, объединённое выражение. Ещё не запутались? Мы быстренько пройдём использование Exp. Функция process_binop — это то, что возвратит правый парсер.
Далее, мы определим наши уровни старшинства и комбинатор, помогающий нам с ними справляться.

def any_operator_in_list(ops):
    op_parsers = [keyword(op) for op in ops]
    parser = reduce(lambda l, r: l | r, op_parsers)
    return parser

aexp_precedence_levels = [
    ['*', '/'],
    ['+', '-'],
]

Функция any_operator_in_list принимает список строк ключевых слов и возвращает соответствующий им парсер. Определим aexp_precedence_levels, содержащий список операторов для каждого уровня старшинства (начиная с более высокого).

def precedence(value_parser, precedence_levels, combine):
    def op_parser(precedence_level):
        return any_operator_in_list(precedence_level) ^ combine
    parser = value_parser * op_parser(precedence_levels[0])
    for precedence_level in precedence_levels[1:]:
        parser = parser * op_parser(precedence_level)
    return parser

precedence — это фактическое содержание операции. Его первый аргумент, value_parser, это парсер, который может читать простые части выражения: числа, переменные и группы. Это будет aexp_term. Список precedence_levels содержит список операторов, по одному списку на каждый уровень. Для этого используем aexp_precedence_levels. combine будет принимать функцию, которая, переданная оператором, возвратит функцию для построения одного большого выражения из двух небольших. Это и будет process_binop

Внутри precedence, мы сначала определим op_parser, который, для данного уровня старшинства, читает только операторы с тем же уровнем и возвращает функцию, которая объединяет два выражения. op_parser может использоваться как правый аргумент Exp. Мы начинаем с вызова Exp с op_parser для наивысшего уровня старшинства, ибо эти операции должны группироваться первыми. Далее используем результирующий парсер как элемент парсера (левый аргумент Exp) на следующем уровне. После окончания цикла, результирующий парсер способен корректно разбирать арифметическое выражение.

Как это работает на практике? Давайте разберём.

E<sub>0</sub> = value_parser
E<sub>1</sub> = E<sub>0</sub> * op_parser(precedence_levels[0])
E<sub>2</sub> = E<sub>1</sub> * op_parser(precedence_levels[1])

E<sub>0</sub> является тем же, что и value_parser. Он может парсить числа, переменные и группы, но не операторы. E<sub>1</sub> моет парсить выражения, содержащие всё, что может совпадать с E<sub>0</sub>, разделённые операторами из первого уровня старшинства. Так E<sub>1</sub> может сопоставлять a * b / c, но должен вызвать ошибку как только столкнётся с оператором +. E<sub>2</sub> может сопоставлять выражения, разделённые операторами следующего уровня старшинства. Так как мы имеем только 2 уровня старшинства, E<sub>2</sub> может сопоставлять любые арифметические выражения, которые мы поддерживаем.

Давайте выполним пример. Возьмём сложное арифметическое выражение, и понемногу заменим каждую часть её сопоставлением.

4 * a + b / 2 - (6 + c)
E<sub>0(4)</sub> * E<sub>0</sub>(a) + E<sub>0</sub>(b) / E<sub>0</sub>(2) - E<sub>0</sub>(6+c)
E<sub>1</sub>(4*a) + E<sub>1</sub>(b/2) - E<sub>1</sub>(6+c)
E<sub>2</sub>((4*a)+(b/2)-(6+c))

Мы используем старшинство непосредственно для определения aexp:

def aexp():
    return precedence(aexp_term(),
                      aexp_precedence_levels,
                      process_binop)

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

Разбор логических выражений

Мы уже можем перейти от арифметических выражений к логическим. Логические выражения обычно проще арифметических, так что нам не понадобятся новые инструменты для их разбора. Начнём с самых простых логических выражений:

def process_relop(parsed):
    ((left, op), right) = parsed
    return RelopBexp(op, left, right)

def bexp_relop():
    relops = ['<', '<=', '>', '>=', '=', '!=']
    return aexp() + any_operator_in_list(relops) + aexp() ^ process_relop

Функцию process_relop мы используем с комбинатором Process. Он принимает три соединённых значения и создаёт из них RelopBexp. В bexp_relop мы разбираем два арифметических выражения (aexp), разделённых оператором отношения. И мы используем нашего старичка — функцию any_operator_in_list, так что нам не нужно писать случай для каждого оператора. Так же нет необходимости использовать комбинаторы вроде Exp или precedence, так как выражения отношений не могут соединяться друг с другом в IMP так, как они делается других языках.

Далее, определим выражение not. Выражение not является унарным оператором с высоким старшинством. Это делает его более простым для разбора чем and и or выражения.

def bexp_not():
    return keyword('not') + Lazy(bexp_term) ^ (lambda parsed: NotBexp(parsed[1]))

Здесь мы соединили ключевое слово not с названием логического выражения (которое мы определим далее). Так как bexp_not будет использоваться для определения bexp_term, нам необходимо использовать комбинатор Lazy для избегания бесконечной рекурсии.

def bexp_group():
    return keyword('(') + Lazy(bexp) + keyword(')') ^ process_group

def bexp_term():
    return bexp_not()   | 
           bexp_relop() | 
           bexp_group()

Определяем bexp_group и bexp_term таким же образом, как и для арифметических эквивалентов. В этом нет ничего нового.
Далее, нам нужно определить выражения, которые включают операторы and и or. Эти операторы на самом деле работают как и арифметические операторы; и те и другие выполняются с лева на право, и and имеет высший уровень старшинства.

bexp_precedence_levels = [
    ['and'],
    ['or'],
]

def process_logic(op):
    if op == 'and':
        return lambda l, r: AndBexp(l, r)
    elif op == 'or':
        return lambda l, r: OrBexp(l, r)
    else:
        raise RuntimeError('unknown logic operator: ' + op)

def bexp():
    return precedence(bexp_term(),
                      bexp_precedence_levels,
                      process_logic)

Так же как и process_binop, process_logic предназначен для использования с комбинатором Exp. Он принимает оператор и возвращает функцию, которая комбинирует два подвыражения в одно выражение, используя этот оператор. Мы подставляем это в соответствии со старшинством так же, как и в aexp. Написание общего кода здесь окупается, так как мы не должны повторять сложный код выражение обработки выражения.

Разбор утверждений

С окончанием aexp и bexp, мы можем начать разбор IMP утверждений. Начнём со скромного утверждения присваивания:

def assign_stmt():
    def process(parsed):
        ((name, _), exp) = parsed
        return AssignStatement(name, exp)
    return id + keyword(':=') + aexp() ^ process

Ничего особо интересного. Далее, мы посмотрим на stmt_list. Он будет разбирать серию утверждений, разделённых точкой с запятой.

def stmt_list():
    separator = keyword(';') ^ (lambda x: lambda l, r: CompoundStatement(l, r))
    return Exp(stmt(), separator)

Помните, нам нужно использовать комбинатор EXP здесь вместо чего-то более простого как stmt() + keyword(';') + stmt() для избегания левосторонней рекурсии.
Далее у нас утверждение if:

def if_stmt():
    def process(parsed):
        (((((_, condition), _), true_stmt), false_parsed), _) = parsed
        if false_parsed:
            (_, false_stmt) = false_parsed
        else:
            false_stmt = None
        return IfStatement(condition, true_stmt, false_stmt)
    return keyword('if') + bexp() + 
           keyword('then') + Lazy(stmt_list) + 
           Opt(keyword('else') + Lazy(stmt_list)) + 
           keyword('end') ^ process

Здесь сложность лишь в том, что пункт else необязательный. Это делает выполнение функции немного сложнее.
Наконец, у нас цикл while:

def while_stmt():
    def process(parsed):
        ((((_, condition), _), body), _) = parsed
        return WhileStatement(condition, body)
    return keyword('while') + bexp() + 
           keyword('do') + Lazy(stmt_list) + 
           keyword('end') ^ process

Мы обернём это при помощи stmt:

def stmt():
    return assign_stmt() | 
           if_stmt()     | 
           while_stmt()

Вы можете заметить, что в обоих утверждения if и while использование stmt_list в теле лучше чем stmt. stmt_list в действительности является нашим верхним уровнем определения. Мы не можем иметь stmt, напрямую зависимый от stmt_list, так как это приведёт к левосторонней рекурсии парсера, и так как мы хотим иметь необязательные утверждения в телах if и while, мы напрямую используем stmt_list.

Собираем всё вместе

Теперь у нас есть парсер для каждой части языка. Нам нужно лишь сделать немного высокоуровневых определений:

def parser():
    return Phrase(stmt_list())

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

def imp_parse(tokens):
    ast = parser()(tokens, 0)
    return ast

Функцию imp_parse клиент будет вызывать для разбора программы. Она принимает весь список токенов, вызывает parser, начинает с первого токена и возвращает результирующее Абстрактное Синтаксическое Дерево (AST).

Вот простая управляющая программа для проверки наших парсеров (в добавок к юнитестам):

import sys
from imp_parser import *

if __name__ == '__main__':
    if len(sys.argv) != 3:
        sys.stderr.write('usage: %s filename parsername' % sys.argv[0])
        sys.exit(1)
    filename = sys.argv[1]
    file = open(filename)
    characters = file.read()
    file.close()
    tokens = imp_lex(characters)
    parser = globals()[sys.argv[2]]()
    result = parser(tokens, 0)
    print result

Эта программа читает файл (первый аргумент) и разбирает его каким либо парсером из imp_parse.py (второй аргумент). Пример:

$ echo '1 + 2 * 3' >foo.imp
$ python imp_parser_driver.py foo.imp aexp
Result(BinopAexp(+, IntAexp(1), BinopAexp(*, IntAexp(2), IntAexp(3))), 5)

Это должно предоставить хорошую песочницу для экспериментов.

Заключение

В этой статье мы написали библиотеку комбинатор с нуля и использовали его для написания парсера для IMP. В следующей и последней из этой серии статье мы напишем исполнитель (Прим. перев.: не смог подобрать лучший перевод слова evaluator) для нашего разобранного Абстрактного Синтаксического Дерева (AST).

Автор оригинальной статьи — Jay Conrod

P.S. Вижу проблемы с тегом Sub. Есть предположение, что новичку ещё рано пользоваться таким тегом. Чем его заменить — не знаю. Оставлю до выяснения решения.

Автор: CJay

Источник