Давайте построим простой интерпретатор. Часть 17

Материалы ОП

четверг, мая 8, 2025 | 11 минут чтения

Давайте построим простой интерпретатор. Часть 17

Материалы ОП

«Возможно, вам придется сражаться в битве не один раз, чтобы выиграть ее». — Маргарет Тэтчер

В 1968 году во время летних Олимпийских игр в Мехико марафонец по имени Джон Стивен Аквари оказался в тысячах миль от своей родины, Танзании, в Восточной Африке. Во время бега марафона на большой высоте в Мехико его сбили другие спортсмены, боровшиеся за позицию, и он упал на землю, сильно повредив колено и вызвав вывих. После оказания медицинской помощи, вместо того чтобы выйти из соревнований после такой серьезной травмы, он встал и продолжил гонку.

Мамо Волде из Эфиопии, пробежав 2:20:26, пересек финишную черту первым. Более чем через час, в 3:25:27, после захода солнца, Аквари, хромая, с окровавленной ногой и болтающимися на ветру бинтами, пересек финишную черту последним.

Когда небольшая толпа увидела, как Аквари пересекает финишную черту, они приветствовали его в недоумении, и немногие оставшиеся репортеры бросились на трассу, чтобы спросить его, почему он продолжал бежать с такими травмами. Его ответ вошел в историю: «Моя страна не посылала меня за 5000 миль, чтобы начать гонку. Они послали меня за 5000 миль, чтобы закончить гонку».

Эта история с тех пор вдохновила многих спортсменов и не спортсменов. Вы, возможно, думаете в этот момент: «Это здорово, это вдохновляющая история, но какое отношение она имеет ко мне?» Главное послание для вас и для меня: «Продолжайте двигаться!» Это была длинная серия, растянутая на длительный период времени, и временами может быть страшно продолжать ее, но мы приближаемся к важной вехе в серии, поэтому нам нужно продолжать двигаться.

У нас есть пара целей на сегодня:

  1. Реализовать новую систему памяти, которая может поддерживать программы, вызовы процедур и вызовы функций.
  2. Заменить текущую систему памяти интерпретатора, представленную словарем GLOBAL_MEMORY, новой системой памяти.

Давайте начнем с ответа на следующие вопросы:

  1. Что такое система памяти?
  2. Зачем нам нужна новая система памяти?
  3. Как выглядит новая система памяти?
  4. Почему мы хотим заменить словарь GLOBAL_MEMORY?

1. Что такое система памяти?

Проще говоря, это система для хранения и доступа к данным в памяти. На аппаратном уровне это физическая память (RAM), где значения хранятся по определенным физическим адресам. На уровне интерпретатора, поскольку наш интерпретатор хранит значения в соответствии с именами их переменных, а не физическими адресами, мы представляем память словарем, который сопоставляет имена со значениями. Вот простая демонстрация, где мы сохраняем значение 7 по имени переменной y, а затем немедленно получаем доступ к значению, связанному с именем y:

>>> GLOBAL_MEMORY = {}
>>>
>>> GLOBAL_MEMORY['y'] = 7   # store value by name
>>>
>>> GLOBAL_MEMORY['y']       # access value by name
7
>>>

Мы уже некоторое время используем этот словарный подход для представления глобальной памяти. Мы хранили и получали доступ к переменным на уровне PROGRAM (глобальном уровне) с помощью словаря GLOBAL_MEMORY. Вот части интерпретатора, связанные с созданием «памяти», обработкой присваиваний значений переменным в памяти и доступом к значениям по их именам:

class Interpreter(NodeVisitor):
    def __init__(self, tree):
        self.tree = tree
        self.GLOBAL_MEMORY = {}

    def visit_Assign(self, node):
        var_name = node.left.value
        var_value = self.visit(node.right)
        self.GLOBAL_MEMORY[var_name] = var_value

    def visit_Var(self, node):
        var_name = node.value
        var_value = self.GLOBAL_MEMORY.get(var_name)
        return var_value

Теперь, когда мы описали, как мы в настоящее время представляем память в нашем интерпретаторе, давайте найдем ответ на следующий вопрос.

2. Зачем нам нужна новая система памяти для нашего интерпретатора?

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

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

3. Как выглядит новая система памяти?

По своей сути новая система памяти — это структура данных стека, которая содержит объекты, похожие на словари, в качестве своих элементов. Этот стек называется «стеком вызовов», потому что он используется для отслеживания того, какой вызов процедуры/функции выполняется в данный момент. Стек вызовов также известен как стек времени выполнения, стек выполнения, стек программы или просто «стек». Объекты, похожие на словари, которые содержит стек вызовов, называются записями активации. Вы можете знать их под другим именем: «стековые фреймы» или просто «фреймы».

Давайте подробнее рассмотрим стек вызовов и записи активации.

Что такое стек? Стек — это структура данных, основанная на политике «последним пришел — первым ушел» (LIFO), что означает, что самый последний элемент, добавленный в стек, является первым, который выходит. Это как коллекция тарелок, где вы кладете («push») тарелку на верх стопки тарелок, и, если вам нужно взять тарелку, вы берете одну с верха стопки тарелок (вы «pop» тарелку):

Наша реализация стека будет иметь следующие методы:

  • push (для добавления элемента в стек)

  • pop (для извлечения элемента из стека)

  • peek (для возврата элемента на вершине стека без его удаления)

И по нашему соглашению наш стек будет расти вверх:

Как бы мы реализовали стек в коде? Очень базовая реализация может выглядеть так:

class Stack:
    def __init__(self):
        self.items = []

    def push(self, item):
        self.items.append(item)

    def pop(self):
        return self.items.pop()

    def peek(self):
        return self.items[-1]

Примерно так же будет выглядеть и наша реализация стека вызовов. Мы изменим некоторые имена переменных, чтобы отразить тот факт, что стек вызовов будет хранить записи активации, и добавим метод __str__(), чтобы распечатать содержимое стека:

class CallStack:
    def __init__(self):
        self._records = []

    def push(self, ar):
        self._records.append(ar)

    def pop(self):
        return self._records.pop()

    def peek(self):
        return self._records[-1]

    def __str__(self):
        s = '\n'.join(repr(ar) for ar in reversed(self._records))
        s = f'CALL STACK\n{s}\n'
        return s

    def __repr__(self):
        return self.__str__()

Метод __str__() генерирует строковое представление содержимого стека вызовов, перебирая записи активации в обратном порядке и объединяя строковое представление каждой записи для получения окончательного результата. Метод __str__() печатает содержимое в обратном порядке, чтобы стандартный вывод показывал, как растет наш стек.

Теперь, что такое запись активации? Для наших целей запись активации — это объект, похожий на словарь, для хранения информации о текущем выполняемом вызове процедуры или функции, а также самой программы. Запись активации для вызова процедуры, например, будет содержать текущие значения ее формальных параметров и ее локальных переменных.

Давайте посмотрим, как мы будем представлять записи активации в коде:

class ARType(Enum):
    PROGRAM   = 'PROGRAM'

class ActivationRecord:
    def __init__(self, name, type, nesting_level):
        self.name = name
        self.type = type
        self.nesting_level = nesting_level
        self.members = {}

    def __setitem__(self, key, value):
        self.members[key] = value

    def __getitem__(self, key):
        return self.members[key]

    def get(self, key):
        return self.members.get(key)

    def __str__(self):
        lines = [
            '{level}: {type} {name}'.format(
                level=self.nesting_level,
                type=self.type.value,
                name=self.name,
            )
        ]
        for name, val in self.members.items():
            lines.append(f'   {name:<20}: {val}')

        s = '\n'.join(lines)
        return s

    def __repr__(self):
        return self.__str__()

Есть несколько вещей, которые стоит упомянуть:

a. Конструктор класса ActivationRecord принимает три параметра:

  • имя записи активации (AR для краткости); мы будем использовать имя программы, а также имя процедуры/функции в качестве имени для соответствующей AR
  • тип записи активации (например, PROGRAM); они определены в отдельном классе перечисления под названием ARType (тип записи активации)
  • nesting_level записи активации; уровень вложенности AR соответствует уровню области видимости соответствующей процедуры или объявления функции плюс один; уровень вложенности всегда будет установлен в 1 для программ, что вы скоро увидите

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

c. Класс ActivationRecord реализует специальные методы __setitem__() и __getitem__(), чтобы предоставить объектам записи активации интерфейс, похожий на словарь, для хранения пар ключ-значение и для доступа к значениям по ключам: ar[‘x’] = 7 и ar[‘x’]

d. Метод get() — это еще один способ получить значение по ключу, но вместо того, чтобы вызывать исключение, метод вернет None, если ключ еще не существует в словаре members.

e. Метод __str__() возвращает строковое представление содержимого записи активации

Давайте посмотрим на стек вызовов и записи активации в действии, используя оболочку Python:

>>> from spi import CallStack, ActivationRecord, ARType
>>> stack = CallStack()
>>> stack
CALL STACK

>>> ar = ActivationRecord(name='Main', type=ARType.PROGRAM, nesting_level=1)
>>>
>>> ar
1: PROGRAM Main
>>>
>>> ar['y'] = 7
>>>
>>> ar
1: PROGRAM Main
   y                   : 7
>>>
>>> stack
CALL STACK

>>> stack.push(ar)
>>>
>>> stack
CALL STACK
1: PROGRAM Main
   y                   : 7

>>>

На рисунке ниже вы можете увидеть описание содержимого записи активации из интерактивного сеанса выше:

AR:Main1 обозначает запись активации для программы с именем Main на уровне вложенности 1.

Теперь, когда мы рассмотрели новую систему памяти, давайте ответим на следующий вопрос.

4. Почему мы хотим заменить словарь GLOBAL_MEMORY стеком вызовов?

Причина в том, чтобы упростить нашу реализацию и иметь унифицированный доступ к глобальным переменным, определенным на уровне PROGRAM, а также к параметрам процедур и функций и их локальным переменным.

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

Вот все изменения интерпретатора, которые мы собираемся внести сегодня:

1. Заменить словарь GLOBAL_MEMORY стеком вызовов

2. Обновить метод visit_Program, чтобы использовать стек вызовов для добавления и извлечения записи активации, которая будет содержать значения глобальных переменных

3. Обновить метод visit_Assign, чтобы сохранить пару ключ-значение в записи активации в верхней части стека вызовов

4. Обновить метод visit_Var, чтобы получить доступ к значению по его имени из записи активации в верхней части стека вызовов

5. Добавить метод log и обновить метод visit_Program, чтобы использовать его для печати содержимого стека вызовов при интерпретации программы

Давайте начнем, не так ли?

1. Прежде всего, давайте заменим словарь GLOBAL_MEMORY нашей реализацией стека вызовов. Все, что нам нужно сделать, это изменить конструктор Interpreter с этого:

class Interpreter(NodeVisitor):
    def __init__(self, tree):
        self.tree = tree
        self.GLOBAL_MEMORY = {}

на это:

class Interpreter(NodeVisitor):
    def __init__(self, tree):
        self.tree = tree
        self.call_stack = CallStack()

2. Теперь давайте обновим метод visit_Program:

Старый код:

def visit_Program(self, node):
    self.visit(node.block)

Новый код:

def visit_Program(self, node):
    program_name = node.name

    ar = ActivationRecord(
        name=program_name,
        type=ARType.PROGRAM,
        nesting_level=1,
    )
    self.call_stack.push(ar)

    self.visit(node.block)

    self.call_stack.pop()

Давайте разберем, что происходит в обновленном методе выше:

  • Сначала мы создаем запись активации, присваивая ей имя программы, тип PROGRAM и уровень вложенности 1
  • Затем мы помещаем запись активации в стек вызовов; мы делаем это раньше всего остального, чтобы остальная часть интерпретатора могла использовать стек вызовов с одной записью активации в верхней части стека для хранения и доступа к глобальным переменным
  • Затем мы оцениваем тело программы как обычно. Опять же, поскольку наш интерпретатор оценивает тело программы, он использует запись активации в верхней части стека вызовов для хранения и доступа к глобальным переменным
  • Затем, непосредственно перед выходом из метода visit_Program, мы извлекаем запись активации из стека вызовов; она нам больше не нужна, потому что на этом этапе выполнение программы интерпретатором завершено, и мы можем безопасно отбросить запись активации, которая больше не используется

3. Далее давайте обновим метод visit_Assign, чтобы сохранить пару ключ-значение в записи активации в верхней части стека вызовов:

Старый код:

def visit_Assign(self, node):
    var_name = node.left.value
    var_value = self.visit(node.right)
    self.GLOBAL_MEMORY[var_name] = var_value

Новый код:

def visit_Assign(self, node):
    var_name = node.left.value
    var_value = self.visit(node.right)

    ar = self.call_stack.peek()
    ar[var_name] = var_value

В приведенном выше коде мы используем метод peek(), чтобы получить запись активации в верхней части стека (ту, которая была помещена в стек методом visit_Program), а затем используем запись для хранения значения var_value, используя var_name в качестве ключа.

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

Старый код:

def visit_Var(self, node):
    var_name = node.value
    var_value = self.GLOBAL_MEMORY.get(var_name)
    return var_value

Новый код:

def visit_Var(self, node):
    var_name = node.value

    ar = self.call_stack.peek()
    var_value = ar.get(var_name)

    return var_value

Опять же, как вы можете видеть, мы используем метод peek(), чтобы получить верхнюю (и единственную) запись активации — ту, которая была помещена в стек методом visit_Program для хранения всех глобальных переменных и их значений, — а затем получаем значение, связанное с ключом var_name.

5. И последнее изменение в классе Interpreter, которое мы собираемся внести, — это добавить метод log и использовать метод log для печати содержимого стека вызовов, когда интерпретатор оценивает программу:

def log(self, msg):
    if _SHOULD_LOG_STACK:
        print(msg)

def visit_Program(self, node):
    program_name = node.name
    self.log(f'ENTER: PROGRAM {program_name}')

    ar = ActivationRecord(
        name=program_name,
        type=ARType.PROGRAM,
        nesting_level=1,
    )
    self.call_stack.push(ar)

    self.log(str(self.call_stack))

    self.visit(node.block)

    self.log(f'LEAVE: PROGRAM {program_name}')
    self.log(str(self.call_stack))

    self.call_stack.pop()

Сообщения будут регистрироваться только в том случае, если глобальная переменная _SHOULD_LOG_STACK установлена в true. Значение переменной будет контролироваться параметром командной строки «—stack». Сначала давайте обновим основную функцию и добавим параметр командной строки «—stack», чтобы включать и выключать ведение журнала содержимого стека вызовов:

def main():
    parser = argparse.ArgumentParser(
        description='SPI - Simple Pascal Interpreter'
    )
    parser.add_argument('inputfile', help='Pascal source file')
    parser.add_argument(
        '--scope',
        help='Print scope information',
        action='store_true',
    )
    parser.add_argument(
        '--stack',
        help='Print call stack',
        action='store_true',
    )
    args = parser.parse_args()

    global _SHOULD_LOG_SCOPE, _SHOULD_LOG_STACK

    _SHOULD_LOG_SCOPE, _SHOULD_LOG_STACK = args.scope, args.stack

Теперь давайте протестируем наш обновленный интерпретатор. Загрузите интерпретатор из GitHub и запустите его с параметром командной строки -h, чтобы увидеть доступные параметры командной строки:

$ python spi.py -h
usage: spi.py [-h] [--scope] [--stack] inputfile

SPI - Simple Pascal Interpreter

positional arguments:
  inputfile   Pascal source file

optional arguments:
  -h, --help  show this help message and exit
  --scope     Print scope information
  --stack     Print call stack

Загрузите следующую программу-пример из GitHub или сохраните ее в файл part17.pas

program Main;
var x, y : integer;
begin { Main }
   y := 7;
   x := (y + 3) * 3;
end.  { Main }

Запустите интерпретатор с файлом part17.pas в качестве входного файла и параметром командной строки «—stack», чтобы увидеть содержимое стека вызовов, когда интерпретатор выполняет исходную программу:

$ python spi.py part17.pas --stack
ENTER: PROGRAM Main
CALL STACK
1: PROGRAM Main

LEAVE: PROGRAM Main
CALL STACK
1: PROGRAM Main
   y                   : 7
   x                   : 30

Миссия выполнена! Мы реализовали новую систему памяти, которая может поддерживать программы, вызовы процедур и вызовы функций. И мы заменили текущую систему памяти интерпретатора, представленную словарем GLOBAL_MEMORY, новой системой, основанной на стеке вызовов и записях активации.

На сегодня все. В следующей статье мы расширим интерпретатор для выполнения вызовов процедур с использованием стека вызовов и записей активации. Это будет огромной вехой для нас. Так что следите за обновлениями и до встречи в следующий раз!

Литература

  1. Language Implementation Patterns: Create Your Own Domain-Specific and General Programming Languages (Pragmatic Programmers)
  2. Writing Compilers and Interpreters: A Software Engineering Approach
  3. Programming Language Pragmatics, Fourth Edition
  4. Lead with a Story
  5. A Wikipedia article on John Stephen Akhwari
Предыдущая Давайте построим простой интерпретатор. Часть 18
Следующая Давайте построим простой интерпретатор. Часть 16