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

В предыдущих трех частях мы создали лексер, парсер и 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 filenamen')
    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: %sn' % (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).
• Добавить функции.

Автор: duse

Источник