Наши партнеры

UnixForum





Библиотека сайта rus-linux.net

Интерпретатор языка Python, написанный на языке Python

Оригинал: A Python Interpreter Written in Python
Автор: Allison Kaptur
Дата публикации: July 12, 2016
Перевод: Н.Ромоданов
Дата перевода: февраль 2017 г.

Это вторая часть статьи "Интерпретатор языка Python, написанный на языке Python".
Перейти к
началу.

Создание интерпретатора

Перед тем, как обратиться к коду интерпретатора Byterun, нам нужно будет рассмотреть структуру интерпретатора на более высоком уровне. Как работает интерпретатор языка Python?

Интерпретатор языка Python представляет собой виртуальную машину, а это значит, что это программное обеспечение, которое эмулирует физический компьютер. Эта специфическая виртуальная машина представляет собой стековую машину: чтобы выполнять свои операции, эта машина пользуется несколькими стеками (в противоположность регистровой машине, которая выполняет чтение данных из определенных ячеек памяти и записывает данные в ячейки памяти.

Интерпретатор языка Python является интерпретатором байт-кода: его входными данными будет набор инструкций, который называется байт-кодом. Когда вы пишете на языке Python, лексический анализатор, синтаксический анализатор и компилятор генерируют для интерпретатора объекты кода, с которыми он будет оперировать. Каждый объект кода содержит набор инструкций, которые должны выполняться, - это байт-код - плюс некоторая другая информация, которая потребуется интерпретатору. Байт-код является промежуточным представлением кода на языке Python: в нем представлен исходный код, который вы написали, в виде, понятном для интерпретатора. Здесь аналогия с тем, как язык ассемблера служит в качестве промежуточного представления между кодом на языке C и аппаратной частью компьютера.

Крошечный интерпретатор

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

LOAD_VALUE
ADD_TWO_VALUES
PRINT_ANSWER

Поскольку мы в этой главе никак не связаны с лексическим и синтаксическим анализаторами и компилятором, неважно каким образом эти наборы инструкций были созданы. Можно себе представить, что вы написали выражение 7 + 5 и потребовали от компилятора выдать комбинацию из этих трех команд. Либо, если у вас есть правильный компилятор, вы можете написать это же выражение в синтаксисе языка Lisp, которая превратится в ту же самую комбинацию инструкций. Для интерпретатора это неважно. Все, что важно, это то, что наш интерпретатор получит правильно сформированную последовательность инструкций.

Предположим, что из выражения/p>

7 + 5

будет создан следующий набор инструкций:

what_to_execute = {
    "instructions": [("LOAD_VALUE", 0),  # первое число
                     ("LOAD_VALUE", 1),  # второе число
                     ("ADD_TWO_VALUES", None),
                     ("PRINT_ANSWER", None)],
    "numbers": [7, 5] }

Интерпретатор языка Python является стековой машиной, поэтому для того, чтобы сложить два числа, он должен пользоваться стеками (рис 12.1.) Интерпретатор начнет с выполнения первой команды, LOAD_VALUE, и занесет первое число в стек. Далее он занесет в стек второе число. Что касается третьей инструкции, ADD_TWO_VALUES, то она вытолкнет из стека оба числа, сложит их вместе и поместит результат в стек. И, наконец, вытащит результат обратно из стека и распечатает его результат.

Стековая машина

Рис.12.1. Стековая машина

Инструкция LOAD_VALUE сообщает интерпретатору о том, что нужно поместить число в стек, но сама команда не указывает, какое число. Каждой команде нужна дополнительная часть информации, сообщающая интерпретатору, где найти число для загрузки. Таким образом, наш набор команд состоит из двух частей: самих инструкций, а также списка констант, которые необходимы инструкциям. В языке Python то, что мы называем "инструкциями", является байт-кодом, а тот объект, "с которым нужно что-то выполнить", является объектом кода.

Почему бы не просто помещать числа непосредственно в инструкцию? Представьте себе, если бы мы вместо чисел объединяли вместе строки. Нам бы не хотелось, чтобы строки были в инструкциях, поскольку они могут быть сколь угодно большими. Такая конструкция также означает, что у нас можем быть только по одной копии каждого объекта, который нам нужен, так, например, для того, чтобы сложить 7 + 7, "числами" может быть просто объект [7].

Возможно, вы удивитесь, зачем вообще нужны другие инструкции, кроме инструкции ADD_TWO_VALUES. Действительно, для простого случая сложения двух чисел, пример несколько надуманный. Тем не менее, эта команда представляет собой строительный блок для более сложных программ. Например, если пользоваться только теми инструкциями, которые до сих пор мы определили, то мы уже можем сложить три значения, или любое количество значений в случае, если укажем правильный набор этих инструкций. Стек предоставляет нам простой и понятный способ следить за состоянием интерпретатора, и он будет поддерживать работу с более сложными конструкциями.

Теперь давайте начнем писать сам интерпретатор. Объект интерпретатора имеет стек, который мы представим в виде списка. В объекте также есть метод, описывающий, как выполнять каждую инструкцию. Например, с помощью инструкции LOAD_VALUE интерпретатор будет помещать значение в стек.

lass Interpreter:
    def __init__(self):
        self.stack = []

    def LOAD_VALUE(self, number):
        self.stack.append(number)

    def PRINT_ANSWER(self):
        answer = self.stack.pop()
        print(answer)

    def ADD_TWO_VALUES(self):
        first_num = self.stack.pop()
        second_num = self.stack.pop()
        total = first_num + second_num
        self.stack.append(total)

С помощью этих трех функций реализованы три инструкции, которые понимает наш интерпретатор. Интерпретатору нужна еще способ, с помощью которого все это будет связано вместе и будет фактически выполнено. Этот метод run_code (запуск-кода), который берет в качестве аргумента словарь what_to_execute, (т.е. то, что нужно выполнить), определенный выше. Он выполняет цикл по всем инструкциям, обрабатывает аргументы в каждой инструкции, если таковые имеются, а затем вызывает соответствующий метод в объекте интерпретатора.

    def run_code(self, what_to_execute):
        instructions = what_to_execute["instructions"]
        numbers = what_to_execute["numbers"]
        for each_step in instructions:
            instruction, argument = each_step
            if instruction == "LOAD_VALUE":
                number = numbers[argument]
                self.LOAD_VALUE(number)
            elif instruction == "ADD_TWO_VALUES":
                self.ADD_TWO_VALUES()
            elif instruction == "PRINT_ANSWER":
                self.PRINT_ANSWER()

Чтобы это проверить, мы можем создать экземпляр объекта, а затем вызвать метод what_to_execute с набором инструкций, выполняющие сложение 7 + 5, которые определены выше.

    interpreter = Interpreter()
    interpreter.run_code(what_to_execute)

Конечно же, будет выдан ответ: 12.

Хотя этот интерпретатор весьма ограничен, процесс почти точно такой же, как в реальном интерпретаторе языка Python складываются числа. Есть несколько частностей, на которые даже в этом небольшом примере следует обратить внимание.

Во-первых, для некоторых инструкций нужны аргументы. В реальном байткоде языка Python, около половины инструкций имеют аргументы. Аргументы упаковываются вместе с инструкциями точно также, как и в нашем примере. Обратите внимание на то, что аргументы, предназначенные для инструкций, отличаются от аргументов, предназначенных для методов, которые вызываются./p>

Во-вторых, обратите внимание на то, что для инструкции ADD_TWO_VALUES не требуется никаких аргументов. Вместо этого все значения предварительно следует добавить в стек, а после выполнения инструкции они будут вытолкнуты из стека интерпретатора. Эта особенность является основополагающей для интерпретатора, использующего стек.

Вспомните, что в нашем интерпретаторе для данного набора инструкций можно сразу без каких-либо изменений складывать более двух чисел. Рассмотрим набор команд, который приведен ниже. Что, как вы ожидаете, произойдет? Если у вас удобный компилятор, то какой код вы могли бы написать для того, чтобы создать этот набор инструкций?

    what_to_execute = {
        "instructions": [("LOAD_VALUE", 0),
                         ("LOAD_VALUE", 1),
                         ("ADD_TWO_VALUES", None),
                         ("LOAD_VALUE", 2),
                         ("ADD_TWO_VALUES", None),
                         ("PRINT_ANSWER", None)],
        "numbers": [7, 5, 8] }

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

Переменные

Далее давайте в наш интерпретатор добавим переменные. Для переменных требуется инструкция STORE_NAME, позволяющая запоминать значение переменной, и инструкция LOAD_NAME, позволяющая извлекать это значение, а также средство отображения имен переменных в их значения. На данный момент мы игнорируем пространство имен и области видимости и, поэтому, можем хранить такой сресдтво отображения в самом объекте интерпретатор. Наконец, мы должны убедиться, что в what_to_execute кроме списка констант есть еще список имен переменных.

>>> def s():
...     a = 1
...     b = 2
...     print(a + b)
# дружественный компилятор преобразует `s` в:
    what_to_execute = {
        "instructions": [("LOAD_VALUE", 0),
                         ("STORE_NAME", 0),
                         ("LOAD_VALUE", 1),
                         ("STORE_NAME", 1),
                         ("LOAD_NAME", 0),
                         ("LOAD_NAME", 1),
                         ("ADD_TWO_VALUES", None),
                         ("PRINT_ANSWER", None)],
        "numbers": [1, 2],
        "names":   ["a", "b"] }

Наша новая реализация приведена ниже. Чтобы отслеживать, какие имена связаны с какими значениями, мы добавим к методу __init__ словарь environment. Мы также добавим методы STORE_NAME и LOAD_NAME. Эти методы сначала ищут в запросе имя переменной, а затем используют словарь для того, чтобы сохранить или получить его значение.

Аргументы инструкции теперь могут использовать в двух различных ситуациях: они могут быть либо индексами в списке "чисел", либо они могут быть индексами в списке "имен". Интерпретатор, когда он выполняет конкретную инструкцию, знает, что ему нужно проверять. Мы добавим эту логику, а также взаимосвязь между инструкциями и их аргументами, в отдельный метод.

class Interpreter:
    def __init__(self):
        self.stack = []
        self.environment = {}

    def STORE_NAME(self, name):
        val = self.stack.pop()
        self.environment[name] = val

    def LOAD_NAME(self, name):
        val = self.environment[name]
        self.stack.append(val)

    def parse_argument(self, instruction, argument, what_to_execute):
        """ Понятно, что означает аргумент в каждой инструкции."""
        numbers = ["LOAD_VALUE"]
        names = ["LOAD_NAME", "STORE_NAME"]

        if instruction in numbers:
            argument = what_to_execute["numbers"][argument]
        elif instruction in names:
            argument = what_to_execute["names"][argument]

        return argument

    def run_code(self, what_to_execute):
        instructions = what_to_execute["instructions"]
        for each_step in instructions:
            instruction, argument = each_step
            argument = self.parse_argument(instruction, argument, what_to_execute)

            if instruction == "LOAD_VALUE":
                self.LOAD_VALUE(argument)
            elif instruction == "ADD_TWO_VALUES":
                self.ADD_TWO_VALUES()
            elif instruction == "PRINT_ANSWER":
                self.PRINT_ANSWER()
            elif instruction == "STORE_NAME":
                self.STORE_NAME(argument)
            elif instruction == "LOAD_NAME":
                self.LOAD_NAME(argument)

Даже при наличии только пяти инструкций, метод run_code начинает становиться слишком запутанным. Если мы сохраним такую структуру, то нам для каждой инструкции потребуется отдельная ветка с выражением if. Здесь мы можем воспользоваться методом динамического поиска, который есть в языке Python. Вместо того, чтобы использовать большое выражение if, мы всегда для того, чтобы выполнить инструкцию под названием FOO, будем определять метод, называемый FOO, так что мы сможем при поиске на лету пользоваться функцией getattr языка Python. Тогда метод run_code будет выглядеть следующим образом:

    def execute(self, what_to_execute):
        instructions = what_to_execute["instructions"]
        for each_step in instructions:
            instruction, argument = each_step
            argument = self.parse_argument(instruction, argument, what_to_execute)
            bytecode_method = getattr(self, instruction)
            if argument is None:
                bytecode_method()
            else:
                bytecode_method(argument)

Перейти к следующей части статьи.

Перейти к началу статьи.