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

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

Anna | 15.06.2014 | нет комментариев
В предыдущих 3 частях мы сделали лексер, парсер и AST для нашего игрушечного языка IMP. Мы даже написали нашу собственную библиотеку парсеров комбинаторов. В этой, финальной статье мы напишем конечный компонент интерпретатора — исполнитель.

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

Дабы выполнить IMP-программу, нам необходимы три вещи:

  1. Точка контроля — мы обязаны знать следующее выражение для исполнения.
  2. Среда — нам необходимо смоделировать «метаморфоза состояния программы».
  3. Функции исполнения — нам необходимо знать, как состояние и точка контроля обязаны быть модифицированы для всякого выражения.

Самое примитивное — точка контроля, по крайней мере для IMP. Мы устроили наше промежуточное представление в виде древовидной конструкции. Мы будем легко вызывать функции исполнения (evaluation) для топ-левел выражений, которая будет рекурсивно вызывать функцию исполнения для выражений внутри. По сути, мы будем применять точку контроля Python в качестве нашей собственной. Это не было бы так легко, для языков с больше трудными конструкциями управления, как функций либо исключений, но мы можем сберечь его простым для IMP.

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

Функции исполнения — исключительная вещь, о которой мы обязаны думать. Всякий тип выражения будем иметь собственную функцию исполнения, которая использует актуальную среду и вернет значение. Арифметические выражения возвращают интеджеры, булевые — true либо false. Выражения не имеют никаких побочных результатов, так что среду не будет модифицирована. Всякий тип выражения также имеет функцию исполнения. Заявления действуют путем модифицирования среды, так что никакого итога не вернется.

Определяем функции исполнения

Мы определим их как способы на наших AST-классах. Это даст прямой доступ всякой функции к структуре, которую она исполняет. Вот арифметические функции:

class IntAexp(Aexp):
    ...
    def eval(self, env):
        return self.i

class VarAexp(Aexp):
    ...
    def eval(self, env):
        if self.name in env:
            return env[self.name]
        else:
            return 0

class BinopAexp(Aexp):
    ...
    def eval(self, env):
        left_value = self.left.eval(env)
        right_value = self.right.eval(env)
        if self.op == ' ':
            value = left_value   right_value
        elif self.op == '-':
            value = left_value - right_value
        elif self.op == '*':
            value = left_value * right_value
        elif self.op == '/':
            value = left_value / right_value
        else:
            raise RuntimeError('unknown operator: '   self.op)
        return value

Вы можете увидеть тут немножко экстра-логики в случае, где программист юзает переменную, которая не определена ранее (та, которая не определена в словаре среды). Для простоты и для того, Дабы избежать написание системы отлова ошибок, мы дадим каждому неопределенным переменным 0.

В BinopAexp мы обрабатываем случай «незнакомого оператора» путем выбрасывания RuntimeError. Парсер не может сделать AST из неведомых операторов, так что нам становится только легче. Но если кто-то делает свой личный AST, там необходимо будет рассматривать и это.

Вот функции булевых операций:

class RelopBexp(Bexp):
    ...
    def eval(self, env):
        left_value = self.left.eval(env)
        right_value = self.right.eval(env)
        if self.op == '<':
            value = left_value < right_value
        elif self.op == '<=':
            value = left_value <= right_value
        elif self.op == '>':
            value = left_value > right_value
        elif self.op == '>=':
            value = left_value >= right_value
        elif self.op == '=':
            value = left_value == right_value
        elif self.op == '!=':
            value = left_value != right_value
        else:
            raise RuntimeError('unknown operator: '   self.op)
        return value

class AndBexp(Bexp):
    ...
    def eval(self, env):
        left_value = self.left.eval(env)
        right_value = self.right.eval(env)
        return left_value and right_value

class OrBexp(Bexp):
    ...
    def eval(self, env):
        left_value = self.left.eval(env)
        right_value = self.right.eval(env)
        return left_value or right_value

class NotBexp(Bexp):
    ...
    def eval(self, env):
        value = self.exp.eval(env)
        return not value

Это достаточно легко. Мы используем питоньи реляционные и логические операторы.

А тут функции исполнения для всякого типа выражений:

class AssignStatement(Statement):
    ...
    def eval(self, env):
        value = self.aexp.eval(env)
        env[self.name] = value

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

class IfStatement(Statement):
    ...
    def eval(self, env):
        condition_value = self.condition.eval(env)
        if condition_value:
            self.true_stmt.eval(env)
        else:
            if self.false_stmt:
                self.false_stmt.eval(env)

class WhileStatement(Statement):
    ...
    def eval(self, env):
        condition_value = self.condition.eval(env)
        while condition_value:
            self.body.eval(env)
            condition_value = self.condition.eval(env)

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

CompoundStatement: мы исполняем всякое выражение, одно за иным. Запомните, что CompoundStatement разрешен всюду, где разрешено выражение, так что длинные цепи выражений раскодируются как вложенные.

IfStatement: вначале мы исполняем булевое условие выражения. Если true, мы исполняем true-выражение. Если false и false-выражение было определено, мы исполняем false-выражение.

WhileStatement: мы исполняем условие для проверки, должно ли тело цикла исполнится один раз. Условие исполняется всякую итерацию цикла, для проверки данные.

Собираем все в кучу

Ну что же, мы сделали основные компоненты нашего интерпретатора и сейчас остается только написать объединяющую программу:

#!/usr/bin/env python

import sys
from imp_parser import *
from imp_lexer import *

def usage():
    sys.stderr.write('Usage: imp filename\n')
    sys.exit(1)

if __name__ == '__main__':
    if len(sys.argv) != 2:
        usage()
    filename = sys.argv[1]
    text = open(filename).read()
    tokens = imp_lex(text)
    parse_result = imp_parse(tokens)
    if not parse_result:
        sys.stderr.write('Parse error!\n')
        sys.exit(1)
    ast = parse_result.value
    env = {}
    ast.eval(env)

    sys.stdout.write('Final variable values:\n')
    for name in env:
        sys.stdout.write('%s: %s\n' % (name, env[name]))

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

Каноничный пример вычисления факториала:

n := 5;
p := 1;
while n > 0 do
  p := p * n;
  n := n - 1
end

Само исполнение:

$ ./imp.py hello.imp
Final variable values:
p: 120
n: 0
Завершение

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

Я верю данный материал предоставит отличный старт для людей экспериментировать с дизайном языка. Немножко идей:

  • Сделать переменные локальными для неймспейса.
  • Добавить цикл for.
  • Добавить выражения для I/O (input/output).
  • Добавить функции.
 Источник: programmingmaster.ru
Оставить комментарий
Форум phpBB, русская поддержка форума phpBB
Рейтинг@Mail.ru 2008 - 2017 © BB3x.ru - русская поддержка форума phpBB