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

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

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

Примитивный интерпретатор с нуля на Python #1
Примитивный интерпретатор с нуля на Python #2
Примитивный интерпретатор с нуля на Python #3
Примитивный интерпретатор с нуля на Python #4
Разъяснение к публикации

Пользователь duse ранее выкладывал переводы 2-х предыдущих статей, очевидно намереваясь перевести всю серию. Так как тема меня дюже волнует, а новых переводов нет, обратился к первоисточнику. С английским не дюже силён, Дабы не терять суть, стал переводить на русский. Так и родился данный перевод. Умоляю помилования у duse в случае, если мне стоило ещё чуточку потерпеть. Но для сообщества в любом случае должна быть польза.

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

Определяем AST

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

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

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

Мы также можем группировать выражения совместно скобками (как (x 2)*3). Это не сколько другой тип выражения, сколько другой метод разбора выражения.
Определим три класса для этих форм, плюс базовый класс для основных арифметических выражений. Пока классы не делают ничего помимо хранения информации. Опишем способ __repr__, дозволит нам выводить на печать AST во время отладки. Все AST классы будут наследовать Equality, следственно мы сумеем сумеем проверять одинаковость 2-х 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 классы и подходящий комплект комбинаторов — самое время написать наш парсер. При написании парсера, легче начать с базовых конструкций языка, понемногу переходя к больше трудным вещам.

1-й парсер, тот, что мы разглядим, это парсер 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 — это фактическое оглавление операции. Его 1-й довод, value_parser, это парсер, тот, что может читать примитивные части выражения: числа, переменные и группы. Это будет aexp_term. Списокprecedence_levels содержит список операторов, по одному списку на всякий ярус. Для этого используемaexp_precedence_levelscombine будет принимать функцию, которая, переданная оператором, возвратит функцию для построения одного большого выражения из 2-х маленьких. Это и будет 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_binopprocess_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

Эта программа читает файл (1-й довод) и разбирает его каким либо парсером из imp_parse.py (2-й довод). Пример:

$ 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. Есть предположение, что новичку ещё рано пользоваться таким тегом. Чем его заменить — не знаю. Оставлю до выяснения решения.

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

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