Простой компилятор

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

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

В этой статье рассмотрен компактный компилятор, исходный текст которого на собственном входном языке содержит меньше 1000 строк (если же не считать пустые строки, то меньше 800), а размер исполняемого файла меньше 6 Кбайт. Язык включает довольно мало элементов и в силу этого не очень удобен для написания ?обычных? программ, но при этом вполне достаточен для написания компилятора. Вы увидите, что для этого нужно совсем немного.

Скорее всего, данный компилятор проще первых ?настоящих? компиляторов. Это связано с намеренным упрощением языка и отсутствием существенных ограничений на доступные аппаратные ресурсы.

Следует отметить, что это далеко не первая программа такого рода. Достаточно упомянуть работы профессора Никлауса Вирта (ETH Zurich) — компактный компилятор PL/0 из книги [1] и систему Pascal-S из статьи [2]. Также известна упрощенная версия Pascal-S, опубликованная в книге [3]. Все эти компиляторы не могут компилировать себя, и это странно, ведь первый компилятор языка Паскаль был написан на подмножестве этого языка (это не совсем так — первый компилятор Паскаля был написан Э. Мармье в 1969 г. на Фортране, см. Богатырев Р. Летопись языков. Паскаль // Мир ПК. 2001. № 4. — прим. ред.) и в диалекте Pascal-S есть почти все необходимое. Соответствующая доработка последнего компилятора возможна, но он не так уж мал — около 2 тыс. строк текста.

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

Входной язык

Разработка языка программирования - задача гораздо более сложная, чем написание компилятора. В данном случае она упрощается тем, что будут использованы только самые простые и устоявшиеся элементы, обычные для императивных языков. Язык включает три типа данных (символы, байты и беззнаковые целые), глобальные переменные (простые переменные и одномерные массивы), функции без параметров и локальных переменных, функции преобразования типа. Внутри функций могут быть использованы операторы присваивания, вызовы функций, операторы возврата значения, условные операторы с одной ветвью, циклы с предусловием, а также вставки кода. Допускается прямая рекурсия — функция может вызывать себя. Выбор беззнакоых целых связан с целевой машиной (16-и разрядный процессор). Хотя целые со знаком и являются более общим типом, максимальное значение 2¹⁵-1 слишком мало.

Нет указателей и средств для работы со строками. Вставки кода будут использованы только для вызова функций операционной системы.

Дадим формальное описание языка. Оно представляет собой содержательные части заданий для генераторов лексических и синтаксических анализаторов LEX и YACC. Эти программы по описанию создают анализаторы, написанные на языке C, т.е. автоматически выполняют часть той работы, которая здесь выполнена путем ручного кодирования. Зачем делать вручную то, что можно сделать автоматически? Дело в том, что LEX и YACC тоже были как-то написаны и они больше и сложнее рассматриваемого компилятора. Описание LEX и YACC выходит за рамки этой статьи, но понять текст заданий для них несложно. Задание для LEX содержит перечень всех слов языка и правила образования таких объектов, как идентификаторы и константы. Задание для YACC содержит правила образования предложений языка и в конечном счете отвечает на вопрос, как выглядит программа. В данном случае программа (program) есть возможно пустой набор определений (definitions) и блок операторов. Подобная форма записи правил называется нормальной формой Бэкуса (BNF - Backus Normal Form). (см. Листинг 1)

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

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

Имеются только два оператора, управляющие исполнением программы - if и while. Доказано, что их достаточно для реализации любых алгоритмов, содержащих пересылки и преобразования данных, условные и безусловные переходы [4].

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

Предложенный автором язык не является подмножеством какого-либо распространенного языка программирования. В некотором смысле это смесь языков Modula-2 и Cи, но набор возможностей языка столь мал, что нельзя говорить о принадлежности к той или иной группе языков. Если язык вам не понравится, очень просто заменить его другим, например, Паскалем или Си.

Упрощения

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

Среда исполнения

Компилятор создает исполняемый файл COM-формата для процессора Intel 8086 и работает в среде MS-DOS. Данное операционное окружение устарело, но хорошо подходит для демонстрации устройства компилятора. Любой современный процессор архитектуры Intel 80x86 может исполнять код процессора Intel 8086, и программа в COM-формате может работать в среде Windows 95/NT. COM формат весьма прост — ничего кроме исполняемого кода в нем нет. Генерация одних лишь заголовков и секции импорта исполняемого файла PE-формата (Windows 95/NT) потребовала бы затрат, сопоставимых с затратами на весь компилятор. Очевидным недостатком выбранной среды исполнения является существенное ограничение на объем доступной оперативной памяти. Использование виртуальной машины, подобной интерпретатору Pascal-S, свободно от данного недостатка, исполняемый файл тоже прост - это может быть даже текстовый файл с кодами и мнемоническими обозначениями команд, но требуется еще один компонент — виртуальная машина.

Для понимания дальнейшего нужны некоторые сведения о логическом устройстве и командах процессора 8086. Он содержит четырнадцать шестнадцатиразрядных регистров - четыре регистра данных (AX, BX, CX и DX), четыре сегментных регистра (CS, SS, DS и ES), пять индексных регистов (IP, SP, BP, SI, DI) и регистр состояния PSW. Регистры IP и SP имеют специальное назначение - это указатели исполняемой команды и стека (области памяти, используемой для временного хранения данных). Регистры данных состоят из пар восьмиразрядных регистров, которые могут использоваться независимо. Например, регистр AX состоит из пары AL (младший байт) и AH (старший байт). Некоторые регистры являются комбинированными, в частности, регистр BX может использоваться как индексный регистр. Процессор может работать с оперативной памятью объемом до одного мегабайта, адрес байта или слова, к которому происходит обращение, формируется путем сложения умноженного на 16 значения в сегментном регистре и шестнадцатиразрядного смещения. Смещение может быть суммой значений в одном или двух индексных регистрах и значения, указанного в команде. В командах неявно указывается используемый сегментный регистр, при необходимости он может быть заменен, но здесь это не требуется. Команды имеют длину от одного до шести байт и состоят из кода операции (возможно, распределенного по первым двум байтам), набора полей, смещений и данных. Из достаточно обширного набора команд будут использованы лишь двадцать (см. таблицу).

Коды команд приведены в двоичной системе счисления, в тексте программы они переведены в шестнацатеричную. Поля REG, DST и SRC определяют регистр (000 - AX/AL, 001 - CX/CL, 010 - DX/DL, 011 - BX/BL, 100 - SP/AH, 101 - BP/CH, 110 - SI/DH, 111 - DI/BH), поле W - разрядность (0 байт, 1 - слово), COND - условие (всего условий шестнадцать, но будут использоваться только четыре - 0010 - если ниже, 0110 - если ниже или равно, 0100 - если равно и 0101 - если не равно, слово ниже подразумевает сравнение без учета знака операндов). Арифметические команды модифицируют отдельные биты слова состояния PSW и таким образом могут влиять на последующие команды условных переходов. Смещения в командах переходов и вызовов функций относительные, они равны разности смещений команды, к которой выполняется переход и команды, следующей за командой перехода. Для отрицательных смещений используется дополнительный код.

Исполняемый модуль формата *.com занимает один сегмент размером 64 килобайта, в первых 256 байтах размещается создаваемый операционной системой префикс программного сегмента (PSP), за ним следует образ файла. Перед началом исполнения программы все сегментные регистры указывают на начало PSP, указатель стека инициализирован максимально возможным значением (обычно 2¹⁶-2). Выполнение программы начинается с перехода по адресу PSP:256. Обычно глобальные переменные следуют непосредственно за кодом программы, здесь в целях упрощения они начинаются с фиксированного адреса PSP:16640 (256+16384).

Структуры данных

Поскольку в языке отсутствуют средства для работы со строками, их придется имитировать. Для этого используется массив Heap. В него будут записаны ключевые слова языка (для сокращения кода только некоторые), имена объектов и некоторые другие данные, такие как имена файлов. Все строки кроме используемой для преобразования чисел строки цифр оканчиваются символом с кодом 0. Заполнять массив придется по одному символу, поэтому, чтобы записать в него, скажем, слово ?begin?, потребуется шесть операторов присваивания:

Heap[31]:='b'; Heap[32]:='e'; Heap[33]:='g'; Heap[34]:='i'; Heap[35]:='n'; Heap[36]:= char(0);

Одна из основных структур данных компилятора - словарь, в него заносятся данные обо всех объектах компилируемой программы. Он может быть представлен как массив или список структур (записей). Поскольку в языке нет ни средств определения структур, ни средств для работы со списками остается использовать набор из нескольких массивов одинаковой длины. Массивы Name (имя объекта, точнее индекс имени в массиве Heap), Cls (класс объекта - тип, переменная, функция), Type (тип объекта - индекс в словаре), Size (для типов - размер, для простых переменных - единица, для массивов - число элементов, не равное единице) и Ofs (смещение объекта).

Массив Cls мог бы иметь тип ?перечисление?, элементами которого являются ?тип?, ?переменная? и ?функция?. Это позволило бы компилятору проверять корректность использования Cls. В крайнем случае для возможных значений следовало бы определить символические константы. Но язык не предоставляет таких возможностей, поэтому придется использовать числовые константы 1 (тип), 2 (переменная) и 3 (функция).

Структура кода

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

Вспомогательные функции

Поскольку компилятор предполагается малым, исходный текст из файла с именем с.prg будет целиком загружаться в массив Text. Для этого используются функций open, read и close. Код будет помещаться в массив Code, по окончании компиляции с помощью функций create, write и close он будет записываться в файл с именем c.com. Имена файлов фиксированы чтобы не заниматься разбором командной строки.

Функции ввода-вывода содержат смещения ряда переменных. Изменения в определениях переменных от начала файла до hFile включительно, а также изменение смещения данных (начального значения переменной nData) должны быть отражены в этих функциях.

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

Сканер

Задача сканера - разбить исходный текст компилируемой программы на слова и возвращать их по одному. Функции Read (считать текущий символ), Next (перейти к следующему символу) и Scan (считать слово) выполняют эту задачу. Слово помещается в массив Buff. Сканер заметно отличается от того, что обычно описывется в учебниках. Он почти ничего не анализирует, последовательность символов ?123$ABC? он посчитает ?словом?. Ошибочность таких ?слов? будет устанавливаться другими блоками компилятора. Сканер пропускает пустые символы всех видов (пробелы, символы табуляции, символы перевода строки и возврата каретки), затем, если встретилась буква, цифра или символ ?$?, считывает слово. В противном случае считывет один или два символа. Сканер также пропускает однострочные комментарии, начинающиеся с ?//?. Пропуск комментариев добавлен только для удобства публикации, для минимальной версии компилятора это не требуется.

Главная функция

Главная функция находится в конце программы и начинается с инициализации переменных. Затем текст компилируемой программы загружается в память и в цикле выполняется разбор определений переменных и функций. Функция отличается от переменной наличием круглой скобки после имени, главная функция начинается со слова ?begin?. Для поиска в словаре используется функция Find, для сравнения слова в массиве Buff с заданным словом (в данном случае со словом ?begin?) - функция Comp. Перед вызовом Comp необходима корректная инициализация переменной pHeap (в нее должен быть записан индекс слова в массиве Heap). Это потенциально ненадежное решение и чтобы избежать ошибок при доработке компилятора не следует модифицировать уже использованную часть Heap. Информация о переменных и функциях запоминается в словаре, код функций запоминается в массиве Code.

Компиляция функций выполняется с помощью функции Func. Вся ее работа сводится к двухкратному вызову функции Ctrl - компилятора управляющих конструкций и, при необходимости, формированию команды возврата. Первый вызов функции Ctrl отражает требование наличия хотя бы одного оператора в функции и выполняет инициализацию переменной pHeap индексом слова ?end?:

Scan(); Ctrl(); while Comp()!=0 do Ctrl(); end

Здесь больше подошел бы цикл с ппостусловием (repeat/until).

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

Компилятор управляющих конструкций

Функция Ctrl выполняет разбор и компиляцию одного оператора. Каждый оператор определяется по первому слову (?if?, ?while?, ?inline?, ?return? и имя переменной). Операторы if и while содержат логические условия, для их компиляции используется функция Cond, о ней немного позже. Операторы if и while содержат внутри себя другие операторы, их компиляция выполняется с помощью вызовов самой функции Ctrl так же, как компиляция всей функции.

Компиляция операторов if и while не может быть выполнена сразу. После компиляции условия нужно сформировать команду перехода вперед, а для этого требуется знать смещение команды, следующей за оператором. Необходимо запомнить смещение команды перехода и после компиляции вложенных операторов вернуться и завершить формирование команды. Поскольку при разборе вложенных друг в друга конструкций нужно помнить смещения нескольких команд, для их хранения можно было бы использовать локатьные переменные. Поскольку их нет, используется глобальный массив Stk с указателем pStk. При компиляции оператора цикла требуется также запоминать смещение его начала, чтобы в конце сформировать команду перехода назад.

Оператор присваивания состоит из левой и правой частей. В левой части может быть только имя переменной, возможно с индексом, в правой - произвольное выражние. Индекс также является выражением. Для компиляции выражений используется функция Expr. Эта функция также используется для компиляции оператора возврата значения (return).

Компилятор выражений

Компиляция выражений сложнее компиляции управляющих конструкций. Функция Expr формирует код загрузки в регистр AX значения операнда - константы, переменной или результата функции. Символы и байты сразу преобразуются в слова (в регистр AH записывается 0). Затем функция считывает следующее слово и, если это знак арифметической операции, генерирует команду записи значения из регистра AX в стек, после чего вызывает саму себя. В результате создается код загрузки в AX второго операнда. Наконец, генерируется команда извлечения первого операнда из стека в регистр BX и создается код предписанной операции. Распознавание кода операции по первому символу строки корректно, поскольку сканер считывает лишь строки определенного вида, строка типа ?+=? встретиться не может. Такой способ компиляции выражений не учитывает приоритеты операторов и вычисление происходит справа налево. Если выражение содержит лишь одну операцию, а в тексте компилятора только такие выражения и есть, проблем не возникает, но это существенный дефект и он должен быть исправлен. Сделать это можно не меняя выбранной схемы - компиляцию второго операнда нужно выполнять в цикле, выход из которого происходит при распознавании операции, приоритет которой меньше или равен приоритету предшествующей операции.(см. Листинг 2)

Чтобы это правильно работало, перед всеми прочими вызовами функции Expr в стек (Stk) нужно записывать значение 0, после вызова извлекать его из стека.

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

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

Вот и все. Что-то можно сделать лучше, что-то можно сократить. Например отказаться от лишних слов языка (is, then, do и точки с запятой), использовать числовые константы только с одним основанием (например 2, оно удобно для записи кодов операций), исключить различия между байтами и символами (т.е. исключить символьный тип), возможно что-то еще…

Как это реализовано

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

Сколько требуется ресурсов?

Из ресурсов нас интересуют оперативная память и время. Потребности в памяти относительно невелики - 6 Кбайт - код компилятора, около 4 Кбайт - все переменные кроме массивов с исходным текстом (Text) и создаваемым кодом (Code). Эти массивы занимают еще 32 Кбайта. Немного памяти нужно для стека, всего 42 Кбайта и эту цифру можно уменьшить. Поскольку исходный текст компилируемой программы просматривается последовательно и один раз, нет необходимости держать его весь в памяти. Соответственно, массив Text может быть значительно уменьшен, вплоть до размера сектора дискеты (512 байт, дальнейшее уменьшение очень отрицательно скажется на быстродействии). Создаваемый код тоже можно не держать в памяти целиком, но код одной функции держать в памяти удобно, массив Code можно уменьшить до 4 Кбайт. 16 Кбайт достаточно. Конечно, операционная система тоже требует памяти, но уместить все в 32-64 Кбайт возможно и при этом не надо идти на какие-то хитрости. Но надо учитывать, что по меркам первых компьютеров память такого объема весьма значительна и она достаточна только благодаря выбору очень ограниченного языка и отказу от оптимизации кода.

Второй необходимый ресурс - время. Хотя код компилятора и алгоритм поиска в словаре далеко не оптимальны, на компьютере с процессором Intel 8086 (4.77МГц) затраты времени тоже невелики компиляция самого компилятора занимает меньше 11 сек.

Для сравнения, первый компилятор языка Fortran был реализован на ЭВМ IBM 704 (1956 год). Эта машина комплектовалась оперативной памятью объемом 4-32 тыс. тридцатишестиразрядных слов и выполняла 83 тыс. операций в секунду, по-видимому это на порядок меньше быстродействия персонального компьютера IBM PC.

Литература

Вирт Н. Алгоритмы + структуры данных = программы. — М.: Мир, 1977.
Wirth N. Pascal-S: A Subset and its Implementation // ETH Zurich. Technical Report. 1972. http://www.moorecad.com/ standardpascal/pascals.txt
Snepscheut J. What Computing is All About. — Springer, 1993.
Bohm C., Jacopini G. Flow Diagrams, Turing Machines and Languages with only Two Formation Rules // Communications of the ACM, 1966, Volume 9, Number 5.