Пишем свой язык программирования, часть 2: промежуточное представление программ

Введение

Приветствую всех, кто заглянул почитать мою очередную статью.

Повторюсь, я описываю создание языка языка программирования, на основе проведенной ранее работы, результаты которой описал в этом посте.

В первой части (линк: habr.com/post/435202) я описал этапы проектирования и написания языковой ВМ, которая будет выполнять наши будущие приложения на нашем будущем языке.
В этой статье я планирую описать основные этапы создания промежуточного языка программирования, который будет собираться в абстрактный байткод для уже непосредственного выполнения на нашей ВМ.

Думаю, что не помешает сразу привести ссылки на сайт проекта и его репозиторий.

Сайт
Репозиторий

Сразу скажу, что весь код написан на FPC и примеры буду приводить на нем же.

Итак, начнем наше просветление.

Зачем нам сдался промежуточный ЯП?

Стоит понимать, что преобразовать программу с языка высокого уровня сразу с исполняемый байткод, который состоит из ограниченного набора инструкций — задача настолько тривиальная, что её лучше на порядок упростить, добавив в проект промежуточный язык. Гораздо лучше упрощать код постепенно, чем сразу представлять математические выражения, структуры и классы набором опкодов. К слову, именно таким образом работает большинство сторонних трансляторов и компиляторов.

В моей предыдущей статье я писал о том, как можно реализовать языковую ВМ. Сейчас нужно реализовать ассемблер-подобный ЯП для неё и функционал для дальнейшего написания транслятора. На этих этапах мы закладываем фундамент будущему проекту. Стоит понимать, чем лучше фундамент — тем круче здание.

Делаем первый шаг к реализации сего чуда

Для начала стоит поставить цель. Что мы собственно будем писать? Какими характеристиками должен обладать конечный код и что он должен делать?

Я могу сформировать список основных функциональных частей из которых должна состоять эта часть проекта:

• Простой ассемблер. Преобразует простые инструкции в набор опкодов для ВМ.
• Базовая реализация функционала для реализации переменных.
• Базовая реализация функционала для работы с константами.
• Функционал для поддержки точек входа в методы и вычисление их адресов на этапе трансляции.
• Возможно ещё пара функциональных плюшек.

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

Итак, цели поставлены, приступим к реализации.

Пишем простой ассемблер

Спрашиваем себя, что такое ассемблер?

По сути — это программа, выполняющая подстановку опкодов вместо их текстовых описаний.

Рассмотрим этот код:

push 0
push 1
add
peek 2
pop

После обработки кода ассемблером мы получим исполняемый код для ВМ.

Видим, что инструкции могут быть односложные и двусложные. Более сложных инструкций для стековой ВМ не требуется.

Нам нужен код, который мог бы выделить из строки токены (учитываем, что среди них могут быть строки).

Пишем его:

function Tk(s: string; w: word): string;
begin
  Result := '';
  while (length(s) > 0) and (w > 0) do
  begin
    if s[1] = '"' then
    begin
      Delete(s, 1, 1);
      Result := copy(s, 1, pos('"', s) - 1);
      Delete(s, 1, pos('"', s));
      s := trim(s);
    end
    else
    if Pos(' ', s) > 0 then
    begin
      Result := copy(s, 1, pos(' ', s) - 1);
      Delete(s, 1, pos(' ', s));
      s := trim(s);
    end
    else
    begin
      Result := s;
      s := '';
    end;
    Dec(w);
  end;
end;

Ок, теперь нужно реализовать что-то вроде switch-case конструкции для каждого оператора и наш простой ассемблер готов.

Переменные

Вспомним, что у нашей ВМ для поддержки переменных имеется массив указателей и соответственно — статичная адресация. Значит, что функционал для работы с переменными можно представить как TStringList, в котором строки — имена переменных, а их индексы — их статические адреса. Стоит понимать, что недопустимо дублирование имен переменных в этом списке. Думаю, что нужный код вы сможете представить себе и/или даже написать сами.

Если хотите взглянуть на готовую реализацию, то милости прошу: /lang/u_variables.pas

Константы

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

Реализация: /lang/u_consts.pas

Точки входа в методы

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

Рассмотрим пример кода:

Summ:
  peek 0
  pop
  peek 1
  pop
  push 0
  new
  peek 2
  mov
  push 2
  push 0
  add
jr

Выше описан пример трансляции метода Summ:

func Summ(a, b):
  return a + b
end

Стоит понимать, что опкоды для точек входа отсутствуют. Что вообще собой представляет точка входа в метод Summ? Это простое число — смещение следующего за точкой входа опкода. (смещение опкода — это номер опкода относительно начала исполняемого абстрактного байткода). Теперь перед нами стоит задача — нужно вычислить это смещение на этапе компиляции и, как вариант — объявить константу Summ этим числом.

Напишем для этого некий счетчик веса каждых операторов. У нас есть простые односложные операторы, например «pop». Они занимают 1 байт. Есть и более сложные, например «push 123» — они занимают 5 байт, 1 на опкод и 4 на unsigned int тип.

Суть кода для добавления поддержки точек входа ассемблером:

1. Имеем счетчик, допустим i = 0.
2. Пробегаемся по коду, если перед нами конструкция вида «push 123», то прибавляем к нему 5, если простой опкод — 1. Если перед нами точка входа, то удаляем её из кода и объявляем соответствующую константу со значением счетчика и именем точки входа.

Прочий функционал

Это, например, простое преобразование кода перед обработкой.

Итоги

Мы реализовали наш небольшой ассемблер. Он понадобится нам для реализации на его основе более сложного транслятора. Теперь можем писать небольшие программы для нашей ВМ. Соответственно, в дальнейших статьях будет описан процесс написания более сложного транслятора.

Спасибо, что дочитали до конца, если вы это сделали.

Если вам что-то не понятно, то я жду ваших комментариев.