О проектировании компиляторов написаны книги. Нижеследующий текст их не заменит,
но, надеюсь, позволит получить элементарное представление об устройстве
компиляторов. Чтобы разобраться в работе компилятора, я решил написать
его. Это удалось, но получившийся компилятор имел множество недостатков и позже
был полностью переписан. Второй компилятор был лучше организован, входной язык
был расширен в части поддержки ссылочных переменных (указателей) и контроля типов.
Несмотря на имевшиеся ошибки компилятор был довольно легко переведен с языка C++
на собственный входной язык (удивительно, но ни одна из ошибок не помешала этому).
Очень важно, чтобы компилятор мог компилировать себя - это позволяет в дальнейшем
развивать его используя его же в качестве инструмента. Как выяснилось, для
этого нужно совсем немного и первый мой компилятор мог быть использован для написания
другого компилятора, но не себя - его входной язык был ближе к C, чем к Turbo Pascal,
на котором он был написан. Более того, и он сильно избыточен. Но что сделано - то
сделано, получившийся компилятор больше и сложнее, чем ему следовало быть. Часть
сложностей связана с входным языком, другая часть - с процессором 8086 (80386 проще,
но тогда я этого не знал, да и 32-х разрядные операционные системы для IBM PC еще не
получили распространения). И многое можно было сделать лучше. Здесь кратко рассмотрена
структура компилятора Context 1.0 и представлен компилятор ограниченного подмножества
Context'а, его единственная цель - пояснить устройство настоящего.
К сожалению или к счастью, имевшиеся у меня книги в написании компилятора не
помогли и единственным руководством была короткая статья М.Черкашина "Компилятор
пишется так...". Это не означает, что книг нет. Компилятор простого, но очень
ограниченного языка PL/0 (ничего общего с PL/1 не имеющего) был рассмотрен в книге
создателя языка Pascal Н.Вирта "Алгоритмы+структуры данных=программы". Более сложный
компилятор подмножества Pascal был приведен в его же статье "Pascal-S: Subset and it's
implementation". В книге "What Computing is All About" (Jan van de Snepscheut) была
опубликована уменьшенная версия Pascal-S. Как ни странно, Pascal-S не согласован
с собой, при его написании использовалось возможностей языка больше, чем он
предоставлял и скомпилировать себя он не мог. И это при том, что почти все необходимое
в нем было!
Оба компилятора Н.Вирта создают код вымышленной стековой машины, которая проще
реальных процессоров (в ней нет регистров данных, все операции выполняются над
данными, находящимися на вершине стека). Приведенный ниже компилятор создает код
процессора 8086 фирмы Intel, правда в виде ассемблерного листинга. Чтобы получить
работающую программу нужен ассемблер. Это тоже упрощение, скорее всего неоправданное.
Также можно упомянуть компилятор Small-C. Он относительно мал и способен
скомпилировать себя, но с моей точки зрения это не самый подходящий образец
для изучения.
Прежде чем перейти к дальнейшему, нужно сделать два замечания. Задача компиляции
программы может быть решена различными способами. Здесь рассмотрена модификация
алгоритма рекурсивного спуска. Алгоритм подходит не для любых языков, но для
"простых" (точнее, разумно построенных) языков он подходит. И второе, компилятор
выполняет один просмотр текста и сразу создает код. Возможны и полезны более сложные
методы, предполагающие построение промежуточного представления программы и многократный
просмотр его.
Пpогpамма на языке ассемблеpа - это пpосто последовательность инстpукций, каждая из
котоpых пpеобpазуется в один или несколько байт кода, причем код большинства
инструкций не зависит от окружения и может быть получен немедленно. Пpогpамма
на языке высокого уровня имеет более сложную структуру и ее преобразование
в машинный код сложнее. Во-пеpвых, программа может содеpжать объявления новых
типов, пеpеменных и заголовков функций, котоpые не пpеобpазуются в код, но
используются пpи его создании. Во-втоpых, программа может вообще не содеpжать
меток и опеpатоpов пеpехода, вместо них используются несколько стpуктуpных
опеpатоpов. В тpетьих, программа может содеpжать сколь угодно сложные выpажения.
Как и ассемблерный листинг, программа на любом языке высокого уровня состоит из
слов (зарезервированных слов языка, идентификаторов, чисел, знаков) и для выделения
их из текста может быть использована функция Scan, похожая на одноименную функцию
ассемблеpа. В ней есть лишь два отличия - она должна также выделять из текста
многосимвольные опеpатоpы (в языке Context это <= - меньше или pавно, != - не
pавно и >= - больше или pавно) и пропускать многострочные комментарии
(в ассемблере комментарии были только однострочные). В целях упрощения от
комментариев тоже можно отказаться, но промышленный компилятор должен их
поддерживать. Сканер зависит от входного языка, сканер Fortran'а, например,
должен выделять слова .or. (логическое или) и .and. (логическое и), сканер
рассмотренного выше ассемблера посчитает любое из них тремя словами. Впрочем,
это не самая большая проблема сканера Fortran'а. Иногда приводится следующий
пример:
901 FORMAT (1X,'N = ',I2/)
N=0
10 DO 20 I=1.5
N=N+1
20 CONTINUE
WRITE(6,901) N
STOP
END
Заголовок цикла в строке с меткой 10 содержит опечатку (точка вместо запятой,
на клавиатуре они рядом), но Fortran посчитает, что это присваивание константы
1.5 переменной с именем DO20I. Соответственно, на печать будет будет выведено
число 1, а не 5.
Не только сканер, но и компилятор в целом зависит от входного языка, поэтому
лучше перейти к частному и рассмотреть конкретный язык - Context.
Программа на языке Context представляет собой последовательность определений:
констант
типов (структур)
глобальных переменных
функций
их взаимное расположение в программе ограничено только одним условием - каждый
объект должен быть определен до его использования, завершает программу главная
функция.
Определения константы, структуры и главной функции распознается по первому
слову (define, struct и begin соответственно), определения функции и глобальной
переменной начинаются с имени типа и друг от друга отличаются наличием и отсутствием
круглой скобки после имени. Т.е. после имени типа надо прочитать символы @ (если они
есть), само имя и следующее за ним слово. Если это слово - круглая скобка, то
должен выполняться разбор функции, иначе - разбор глобальной переменной. В ряде
других языков функция определяется по первому слову, в Pascal'е, например, функция
начинается со слова function, а список переменных со слова var.
Таким образом, на верхнем уровне компилятор может состоять из следующего цикла:
while TRUE do
Scan(@Buff);
select
case strcmp(@Buff,"begin") =0:
// Разбор главной функции
exit
case strcmp(@Buff,"define")=0:
// Разбор константы
case strcmp(@Buff,"struct")=0:
// Разбор структуры
default:
// Разбор глобальной переменной или функции
end
end
Разумеется, каждая из ветвей select'а должна содержать определенный код.
Разбор констант и структур достаточно прост (тем более, в Context'е структуры
нерекурсивны - в отличие от Pascal их определения не могут быть вложенными),
результатом разбора являются новые записи в таблице глобальных имен, никакого
кода не создается. Разбор функций сложнее. Он состоит из разбора заголовка
со списком параметров (что очень похоже на разбор структуры) и разбора входящих
в функцию операторов. Если написана функция Ctrl, компилирующая один оператор,
компиляция всей функции сводится к циклу из трех строк:
while strcmp(@Scan(@Buff),"end")!=0 do
Ctrl(@Buff);
end
Для дальнейшего, однако, нужно изменить этот цикл и функцию Ctrl:
//Scan(@Buff);
while strcmp(@Buff,"end")!=0 do
Ctrl(@Buff); // Ctrl должна считывать следующее за оператором слово
end
Такое изменение позволит выполнить разбор функции расширенной версии Context'а,
допускающей объявления заголовков функций (аналог в Pascal - forward):
word F();
word G()
F();
end
После закрывающей скобки может встретиться точка с запятой (F) или начало первого
оператора функции (G). После считывания закрывающей скобки необходимо считать
следующее слово и, если это не точка с запятой, запомнить его и перейти к
компиляции операторов, второй вариант цикла приспособлен для этого. За счет
изменения языка можно восстановить работоспособность первого варианта:
word F();
word G() is
F();
end
Здесь после закрывающей скобки всегда есть слово (точка с запятой или is).
Все операторы, которые могут встретиться в функции, распознаются по первому
слову, поэтому на верхнем уровне Ctrl может быть устроена так:
void Ctrl(char @Buff)
select
case strcmp(@Buff,"if")=0 | strcmp(@Buff,"select")=0:
// разбор условного оператора
case strcmp(@Buff,"while")=0:
// разбор цикла
case strcmp(@Buff,"loop")=0:
// разбор loop
case strcmp(@Buff,"exit")=0:
// разбор exit
case strcmp(@Buff,"inc")=0:
// разбор inc
case strcmp(@Buff,"dec")=0:
// разбор dec
default:
// Разбор объявления локальной переменной или присваивания
end
Scan(Buff);
end
Большинство операторов содержат выражения, их компиляция - наиболее сложная задача,
но она может быть решена аналогично задаче вычисления выражения. Пока отложим ее и
будем считать, что уже написана функция Expr, компилирующая любое выражение и
возвращающая тип и адрес результата (это может быть адрес памяти, регистр или
ссылка на элемент таблицы констант).
С помощью функции Expr разбор цикла while может быть выполнен так:
// Генеpация кода @A: nop; начало цикла
// Вызов функции Expr,
// загpузка pезультата в AL
// Генеpация кода or AL,AL
// jnz @B
// jmp ?
// @B: nop
while strcmp(@Buff,"end")!=0 do
Ctrl(@Buff);
end
// Генеpация кода jmp @A
@C: nop
// Корректировка перехода jmp ? (jmp @C)
Это не все необходимые действия, еще нужно выполнить подготовку к компиляции
операторов loop/exit и к разбору определенных внутри цикла локальных переменных.
Но это уже детали, главное здесь то, что цикл, как и функция, включает
последовательность операторов и для их компиляции может быть использована
сама функция Ctrl так же, как она используется для компиляции всей функции.
Условие цикла компилируется не лучшим образом. Как минимум, генерируются
излишние команды (or AL,AL ...), но сейчас простота важнее эффективности. Также
из приведенного фрагмента неясно, как будет скомпилировано сложное условие,
содержащее логические операторы И/ИЛИ, будет ли реализована полная или краткая
оценка условия. Этот вопрос должен быть решен при написании функции Expr.
По-видимому, полное вычисление с использованием регистра для хранения результата
является наиболее простым, в некоторых языках (например в оригинальном Pascal)
так и сделано. Так сделано и в Context'е, но это неправильное решение.
Компиляция фоpмул похожа на уже известное вычисление аpифметических выpажений.
Отличия лишь в том, что входящие в пpогpамму выpажения могут содеpжать не только
числа и знаки аpифметических опеpаций, но также идентификатоpы пеpеменных и
вызовы функций. Кpоме того, во вpемя компиляции ничего не вычисляется, а
создается машинный код. Все это может быть pеализовано в виде одной pекуpсивной
функции Expr. Эта функция должна вычислить адрес результата или значение (если
объект - константа).
void Expr(word Prty; char @Buff; OpInfo @Op1)
select
case strcmp(@Buff,"(")=0:
// вырадение в скобках
case strcmp(@Buff,"'")=0:
// символьная константа
case strcmp(@Buff,"#")=0:
// символьная константа
case isdigit(Buff)=0:
// числовая константа
default:
// Переменная, вызов функции
end
while TRUE do
word Sign;
word P2;
select
case strcmp(@Buff,"|")=0:
Sign=OR;
P2 =1;
case strcmp(@Buff,"&")=0:
Sign=AND;
P2 =1;
case strcmp(@Buff,"<")=0:
Sign=LT;
P2 =2;
...
case strcmp(@Buff,"%")=0:
Sign=MOD;
P2 =4;
default:
P2=0;
end
if P2<=P then
exit
end
Expr(P2,@Scan(@Buff),@Op2);
// Проверка совместности типов и компиляция оператора Sign
end
end
Нужно отметить, что так написанная функция Expr всегда считывает лишнее слово.
Это может быть точка с запятой, двоеточие, then, do.
Идеи сформулированы и вот как они реализованы в 'игрушечном' компиляторе.
Язык очень ограничен - только один тип данных - целое (но условия считаются
логическими), определение новых типов невозможно, только одномерные массивы,
нет функций и локальных переменных, нет ссылочных переменных. И никаких попыток
оптимизации. Пример был написан под влиянием клона PL/0 и несколько устарел.
Как выяснилось позже, настоящий компилятор может быть
не больше, но все же некоторый смысл в примере есть. Собственно компилятор
начинается с функции Read: