Хочу попробовать написать простенький компилятор языка типа паскаль/с — возможно даже компилируюший в "ассемблероподобные" ыбстрактные конструкции для абстрактной виртуальной машины (для простоты) что бы получше рщзобраться в процессе компиляции... Трудоёмко ли это и с чего бы начать и подъёмно ли это в обозримые сроки ?
Я, честно говоря, уже не помню, какие книги я читал. Вот помню точно, что Креншоу был и Драгон Бук был. Больше по лекциям, которые я, к сожалению, не записывал, но слушал.
В общем, это не сложно, если знаешь основные принципы построения компилятора, которые я тут вкратце изложу. Ну и конечно архитектуру тоже надо знать.
В канонической форме простой компилятор состоит из 5 основных частей:
1) Лексический анализатор
2) Синтаксический анализатор
3) Семантический анализатор
4) Генератор
5) Оптимизатор
1)
Лексическому анализатору (по-буржуйски
Scanner) на вход подается исходный текст компилируемой программы, после чего он разбивает его на поток лексем (
Token по-буржуйски). Лексема — неделимая, синтаксически правильная единица языка. Например — это идентификатор, константа, запятая, точка, ключевое слово, комментарий, оператор и т.д.
Основная задача его — дать каждой лексеме свой класс, подкласс, значение и др. Например у меня Token был
typedef enum {
T_UNKNOWN, //??
T_COMMENT, // /* sdsd */ or //dsfsdf
T_STRING, // "string"
T_CONTROLWORD, // if, else, for, while, ...
T_IDENTIFIER, // a, b, square, ...
T_ERROR, // error in token, f.e. 12321.e3
T_NUMBER, // 12, 43.23, 23e-5, 45.0989e10
T_MATH, // +, -, /, *, %, <, >, <=, >=, ==, !=, &&, ||, !
T_SEMICOLON, // ;
T_BOOL, // deprecated
T_ASSIGNMENT, // =
T_EOF, // end of file
T_DOT, // .
T_COMMA, // ,
T_BYREF, // &
T_RBRACEOPEN, // (
T_RBRACECLOSE, // )
T_CBRACEOPEN, // {
T_CBRACECLOSE, // }
T_SBRACEOPEN, // [
T_SBRACECLOSE // ]
} tokenclass;
class Token {
public:
Token(tokenclass c);
Token(tokenclass c, int i, float f, char *s);
tokenclass tClass;
int asInt;
float asFloat;
char *asString;
};
Тут используются такие штуки как конечные автоматы и т.п. Точно не помню, что это, но найти в сети можно. Основной смысл в том, что считывая символ из входного потока, анализатор переходит в новое состояние, причем набор состояний меняется в зависимости от считанного символа. Но лично я, как и многие другие, делал простой набор
switch'ей и
if'ов. Есть даже генераторы лексических анализаторов — flex, например.
Это твое личное дело, как ты организуешь разбиение на классы, и, возможно, подклассы. Хотя сразу тебе это будет тяжело сделать правильно. Вот когда ты напишешь свой компилятор и поставишь его на полку "Ну ни фига себе я тупаря выхватил!!!", то тогда ты будешь знать, что и как надо было делать. И не только в лексическом анализаторе. Например, относить ли
int и
float к идентификаторам, или к ключевым словам. Я отнес к идентификаторам. Почему? Потому что объявление переменной может быть и типом, определенным пользователем, который уж точно будет идентификатором. Иначе, надо будет вызывать разбор объявления переменной и после того, как ты встретишь идентификатор (если это тип), и после ключевого слова (если это
int, float).
Далее, как только ты разобрал идентификатор, то надо проверить, не является ли он ключевым словом. У тебя должен быть массив ключевых слов, в котором ты делаешь поиск (желательно не линейный, а, например, двоичный). Если нашел, то класс будет уже ключевое слово, а значение, например, индексом этого слова в массиве.
Еще проблема: считать ли
1e2 целой константой, или вещественной? Я считал вещественной для простоты.
Или как, допустим разобрать
a+++b? Вообще принято, что используется жадный алгоритм, т.е. в лексему стараются включить как можно больше символов, пока она синтаксически имеет смысл. В данном случае это будет разобрано как
a++ + b.
Определение самого анализатора:
class Scanner {
private:
iostream *stream;
int controlWordIndex(char *s); // cw search
int readDigits(char *s, int sind); // read all digits
int readAlphaNumeric(char *s, int sind); // read alph-num
Token *readToken(); // read token into t
Token *t;
int lineNum;
void eatwhite(); // discard all whites
public:
Scanner(iostream *s);
Token *getToken(); // last read token
Token *getNextToken(); // read next token
int getLineNumber(); // cur line number
int line(); // synonym for previous
};
2) В задачу
синтаксического анализатора (Parser) входит анализ потока лексем с точки зрения соответствия синтаксису языка и построение из этого потока некой структуры, удобной для дальнейшего анализа (обычно дерево).
На этом этапе сразу и безоговорочно отметаются всякие штуки вроде
a =-;.
С деревом выражений, я надеюсь, ты знаком. Например из
a*b + c*(d + e) строится как
+
/ \
* *
/ \ / \
a b c +
/ \
d e
Советую начать именно с разбора выражений, т.к. это, в общем – самое сложное (не по объему, а по мыслительным процессам в бестолковке). Тут надо учитывать приоритеты операций, скобки, унарность/бинарность... Делается все это простым методом рекурсивного спуска (поищи где-нибудь). Хотя я и недопетрил, что это такое, поэтому делал алгоритмом Дейкстры перевода выражения в обратную польскую нотацию (что, в принципе, то же самое, что и построение дерева), который использует два стека – для операндов и операторов (функции
parseExpression и
_popOperator). Про него можно почитать на
http://algolist.manual.ru/. Пусть он поначалу строит деревья для простых переменных, т.е. без всяких индексов, разыменований структур и пр. Остальное добавишь уже потом.
С операторами все проще. Например
if имеет три "дитя" – условие, тело, альтернативное тело (это, как понимаешь, может и отсутствовать).
for имеет четыре дитя: выражение инициализации, условие, выражение приращения и тело. Первые три могут отсутствовать. Функция имеет 3 дитя, из которых первое – тип возвращаемого значения, второе – тело функции, третье – таблица переменных. И т.д.
Тут отдельно надо отметить, что такое тело. Обычно тело – один оператор. Например:
a = a + b;. Соответственно вводится понятие составного оператора.
Небольшая ремарка: операция – это математическая, или иная операция (+, -, *, /, ...), что у буржуёв называется operator. Наш оператор – это ихний statement. Вот такой каламбур получается
. Составной оператор содержит в себе последовательность операторов (в т.ч. и составных). В Си он задается как
{ — }, а в Pascal как
begin – end.
Далее особо надо отметить переменные. Они бывают нескольких типов: глобальные, аргументы по значению, аргументы по ссылке, локальные. Для контроля их области видимости нужна такая штука, как таблица переменных, а точнее их стек. В начале стека (т.е. самый дальний элемент) будет таблица глобальных переменных, далее таблица переменных функции, и на вершине будут таблицы переменных составного оператора. В Си++, например, каждый блок (т.е. составной оператор) имеет свою таблицу переменных. То есть, если определить переменную внутри блока, то она перестанет формально существовать при его окончании. Я такой штуки не делал – у меня область действия переменной распространяется от объявления до конца тела функции. Т.е. всего две таблицы – глобальных переменных и локальных. Таким образом, изначально в стеке одна таблица – глобальных переменных. Как только ты входишь в функцию, то в этот стек толкаешь ссылку на таблицу переменных функции, которая уже содержит ее аргументы. Как только входишь в блок, то толкаешь туда ссылку на пустую таблицу этого блока. Таким образом, как только ты встречаешь объявление переменной, то записываешь его в таблицу, лежащую на вершине стека. Такой же механизм будет действовать и на следующих этапах с единственным отличием, что здесь ты эти таблицы строишь, а там будешь толкать и использовать уже готовые (эти таблицы должны быть сохранены как дети соответствующих элементов – функций, блоков). Соответственно, чтобы "найти" переменную, надо просматривать все таблицы в стеке, начиная от вершины, пока не найдешь искомую. Структура, по сути, представляет собой простую таблицу переменных. Только когда ее разыменовываешь, уже не смотришь весь стек, а только таблицу этой структуры.
Непосредственно определение переменной должно хранить имя переменной, ссылку на ее тип, размерность и длину каждой размерности (типа массивы
) и смещение. Если переменная – член структуры, то смещение – это смещение относительно начала структуры. Для локальной переменной хранятся смещения относительно регистра
ebp (это для генерации кода нужно). Отрицательное смещение говорит о том, что переменная – локальная, положительное – значит аргумент. Для глобальных смещение равно нулю. Таким образом, аргументы по значению, как и в Си — обычные переменные, значение которых можно менять. Сам аргумент является наследником переменной с одним дополнительным полем – типом передачи данных (по значению, по ссылке).
Идентификатор (т.е. использование переменной в коде) хранит ссылку на объект самой переменной а так же дерево выражения индексации (не только массива, но и разыменование структуры) и результирующий тип. Например:
struct {
float x;
float y;
} point;
point p[[10][[10];
В данном случае выражение индексации для
p[i][j].y будет
i*10 + j + 4. Результирующий тип для
p[i] будет
point[10], для
point[i][j] будет
point, и, наконец, для
point[i][j].y будет
float.
3) В задачу
семантического анализатора входит анализ корректности программы с точки зрения семантики языка. Сюда включается контроль/приведение типов, вывод сообщений типа "Ты че, офигел?!" на штуки вроде
a = i / 0; (конечно не в том случае, если вашему языку обработать бесконечность как два пальца обоссать
) и прочая специфическая для языка лабуда... Только в реальном объемном компиляторе эта стадия выделяется, а так она размазывается по синтаксическому анализу и генерации кода. Останавливаться на ней не буду.
4) И так, мы подошли к
генерации кода – тому, ради чего собственно компилятор и пишется. Вкупе с оптимизатором (а генератор очень тесно связан с ним, практически — это одно целое) – это главная часть компилятора. Самая творческая его часть (опять же вкупе с оптимизатором)! Генератор уже работает с конкретным представлением алгоритма, в принципе абстрагируясь от языка. Таким образом, у вас может быть несколько сканеров/парсеров на разные языки и, при условии, что эти языки представимы в таком виде, один генератор на них. Может быть, конечно, и несколько генераторов (на разные архитектуры) – тут простор для фантазий большой.
Как правило, генерируется ассемблерный код. Генерация в машинные коды – это редкость. Именно поэтому всю эту канитель будет правильнее назвать транслятором, т.к. он переводит программу на Языке в эквивалентную программу на языке ассемблера. Рассмотрим все это дело на языке ассемблера для архитектуры x86.
Итак, начнем с генерации кода для выражений. Самый простой способ – это использовать тот факт, что все завязано на стеке. Таким образом, можно сделать шаблон для операции
op:
pop ebx
pop eax
op eax, ebx
push eax
Соответственно для переменной/константы будет просто:
push var
Например для выражения a + b * c получим дерево:
+
/ \
a *
/ \
b c
И при его обходе его узлов "лэвий дочка -> правий дочка -> сам", получим:
push a ; a – левый сын +
; * - правый сын +
push b ; b – левый сын *
push c ; c – правый сын *
pop ebx ; сам *
pop eax
imul eax, ebx
push eax
pop ebx ; сам +
pop eax
add eax, ebx
push eax
В результате на вершине стека будет лежать значение выражения.
Для операции ++ код будет такой:
; i++ - сначала используем, потом увеличиваем
push i
inc i
; ++i – сначала увеличиваем, потом используем
inc i
push i
Целые числа – это конечно круто, но надо бы добавить и вещественные. В своем компиляторе я использовал 32-битные float для простоты. Основная загвоздка в том, что для разных чисел используются разные команды. Можно конечно складывать два целых числа сопроцом, но это глупо. Поэтому основной принцип такой – если хотя бы один операнд вещественный, то используем сопроцессор, иначе используем обычные команды. Как определить тип операнда? Очень просто – когда функция совершает рекурсивный обход дерева выражения, она должна вернуть этот тип. Соответственно, для переменной она возвращает ее тип – int, float или void (вызов функции void в выражении, это уже будет ошибкой). Для операции она возвращает тип, в зависимости от двух операндов, ей обработанных. Например:
case M_PLUS:
l = generateExpressionCode(op->getLeft(), b);
r = generateExpressionCode(op->getRight(), b);
if (l==_VOID || r==_VOID)
errout(0, "unexpected void", (char *)0);
if (l==_FLOAT || r==_FLOAT) {
if (l==_FLOAT)
b->addInstruction(new AsmInstr(FLD, new AsmOperand(mem32, ESP, 4)));
else
b->addInstruction(new AsmInstr(FILD, new AsmOperand(mem32, ESP, 4)));
if (r==_FLOAT)
b->addInstruction(new AsmInstr(FADD, new AsmOperand(mem32, ESP, 0)));
else
b->addInstruction(new AsmInstr(FIADD, new AsmOperand(mem32, ESP, 0)));
b->addInstruction(new AsmInstr(ADD, new AsmOperand(reg32, ESP), new AsmOperand(imm32, 4)));
b->addInstruction(new AsmInstr(FST, new AsmOperand(mem32, ESP, 0))); // это косяк – на самом деле тут стоит FSTP :)
return _FLOAT; // один из операндов вещественный, следовательно и результат вещественный
} else {
b->addInstruction(new AsmInstr(POP, new AsmOperand(reg32, EBX)));
b->addInstruction(new AsmInstr(POP, new AsmOperand(reg32, EAX)));
b->addInstruction(new AsmInstr(ADD, new AsmOperand(reg32, EAX), new AsmOperand(reg32, EBX)));
b->addInstruction(new AsmInstr(PUSH, new AsmOperand(reg32, EAX)));
return _INTEGER; // оба операнда целые
}
Шаблон op для вещественных операндов будет такой:
f(i)ld dword ptr [esp]+4 ; загрузить левый операнд, он располагается перед вершиной стека
; а стек растет в сторону уменьшения
f(i)op dword ptr [esp] ; сделать операцию с правым
add esp, 4 ; освободить один элемент стека
fstp dword ptr [esp] ; сохранить результат в вершину стека (на место левого операнда)
Если левый операнд целый, то ставится буква
i в первой строке (это значит, что загрузить надо целое число). Если правый операнд целый, то ставится
i во второй строке кода (выполнить операцию с целым). Ну а если оба вещественные, то никаких
i не ставится.
С логическими операциями над вещественными числами немного по-другому – там надо еще флаги сопроцессора сохранять в регистр ah, а оттуда загружать в регистр флагов процессора и только потом делать условный переход. В общем, тут надо почитать документацию по архитектуре x86, благо недостатка в ней нет. С целыми все куда проще. Реализация short circuit вычислений (например, для операции
&& второй операнд не вычисляется, если первый равен нулю) – задача довольно простая. Например, для операции && над целыми код будет такой:
; тут код для левого выражения
pop eax
test eax, eax
jz and_zero_1 ; левый операнд равен нулю, прекратить вычисления и вернуть 0
; тут код для правого выражения
pop eax
test eax, eax
jz and_zero_1 ; правый операнд равен нулю, вернуть 0
push dword ptr 1 ; оба операнда отличны от нуля, значит в результат заносим 1
jmp and_end_1
and_zero_1:
push dword ptr 0 ; один из операндов равен нулю, значит заносим в результат 0
and_end_1:
; ....
Конечно, это кривая реализация, но все же реализация.
С операторами
if, for, while, ..., думаю, проблем не возникнет.
Для функций шаблон такой:
func_name proc
push ebp ; сохраняем ebp
mov ebp, esp ; ebp становится базой для переменных в стеке
sub esp, n*4 ; выделяем место для n локальных переменных
; тело функции
func_name_return:
mov esp, ebp ; восстанавливаем регистр стека
pop ebp ; восстанавливаем значение ebp
ret k*4 ; возврат из функции с очищением стека от k аргументов
func_name endp
Аргументы в стек передаются в обратном порядке. Вызываемая функция очищает стек от аргументов.
В результате стек будет представлять собой следующее:
______________
| argument k | [[ebp]+k*4+8
|--------------|
| argument k-1 | [[ebp]+(k-1)*4+8
|--------------|
| argument ... | [[ebp]+...
|--------------|
| argument 1 | [[ebp]+8
|--------------|
| EIP | [[ebp]+4
|--------------|
| EBP | [[ebp]
|--------------|
| variable 1 | [[ebp]-4
|--------------|
| variable ... | [[ebp]-...
|--------------|
| variable n | [[ebp]-n*4
|--------------|
| ............ |
|______________|
Куда сложнее дело обстоит с переменными: там необходимо учитывать глобальная она, или нет, аргумент по ссылке, или по значению и плюс ко всему этому еще и индексацию навесить.
; На примере первого аргумента и первой переменной
; Для аргумента, переданного по ссылке значение можно получить так:
mov eax, [ebp]+8 ; в функцию передается адрес переменной. загружаем его в eax
mov eax, [eax] ; загружаем в eax значение, находящееся по адресу, содержащемуся в eax :)
push eax ; и толкаем в стек
; Адрес переменной, переданной по ссылке получают очень просто:
push [ebp]+8
; Значение локальной переменной тоже получается легко:
push [ebp]-4
; Адрес немного сложнее:
lea eax, [ebp]-4 ; загрузить в eax адрес
push eax ; и в стек
; С глобальными переменными все просто:
push global_var ; значение
push offset global_var ; адрес
; Если есть индексация, то толкаешь в стек базовый адрес переменной (см. выше)
; далее, генерируешь код выражения индексации (он будет на вершине стека), а потом:
pop esi ; смещение (индексация)
pop eax ; базовый адрес
; значение в стек
push [eax][esi]
; адрес в стек
add eax, esi
push eax
Короче, про генератор еще много можно писать, даже в таком убогом варианте как этот
Единственное, что генератор не должен генерировать текст. Потому как дальше надо будет оптимизировать сгенерированный код.
5)
Оптимизатор, и ежу понятно, оптимизирует весь код. Он происходит и после синтаксического анализа, и во время генерации кода, и после генерации кода.
До генерации кода делаются:
Вычисление констант (выражения типа 2*3 заменяются 6). Также могут заранее вычисляться вызовы функций с постоянными аргументами, если это возможно. Например:
int square(x) {
return x*x;
}
Оптимизатор может заменить
square(4) на
16. Конечно, тут необходим анализ зависимостей этой функции от глобальных переменных, от других функций и прочих внешних факторов.
Вынос инвариантов (т.е. не изменяющих свое значение в течение определенного промежутка времени) из выражений и циклов. Например:
int a = (b + c) * (b + c) * (b + c);
// трансформируется в:
int t = b + c;
int a = t * t * t;
// а вот такую хрень трансформировать не стоит:
int a = (b++ + c) * (b++ + c) * (b++ + c);
// вложенный цикл
for (int i=0; i<n; i++)
for (int j=0; j<n; j++)
a[[i][[j] = i*c;
// трансформируется в
int *t1;
int t2;
for (int i=0; i<n; i++) {
t1 = a[[i];
t2 = i*c;
for (int j=0; j<n; j++)
t1[[j] = t2;
}
Упрощение выражений – замена, например,
a * 2 на
a + a,
a * 16 на
a << 4,
a*b + c*b на
(a + c) * b
и т.п.
Во время генерации кода оптимизатор анализирует стратегии распределения регистров и выбирает оптимальную. Например, он может на некоторое время назначить переменной отдельный регистр, и только потом сохранить ее в память, если понадобится (очевидно, что индекс в цикле заслуживает отдельного регистра, но только на время цикла, память же под него может вообще не выделяться). Если выражение достаточно мало, то его вычисление может пройти вообще без использования стека – только регистры (в частности у FPU восемь регистров, так что вычисление вещественных выражений можно очень неплохо соптимизировать). Под разные переменные может выделяться одна и та же память, если время их использования не пересекается, или пересекается слабо. Сюда же входят inline-включения вызовов функций и т.д. Тут много чего можно и нужно соптимизить.
После генерации кода по нему проходят так называемым
скользящим окном (sliding window). Суть метода в том, что рассматриваются n (размер окна) последовательных команд и по возможности они заменяются чем-то более удачным. Если замена произошла, то происходит откат на n-1 позицию. Например для окна просто подарок следующие конструкции:
push ebx
pop eax
; заменяется на
mov eax, ebx
push eax
op
; заменяется на
op
push eax
; при условии, что op не работает со стеком, или регистром eax; происходит спуск всех pushей
; таким же образом все popы по возможности поднимаются наверх, чтобы встретить там push и сократить пару
mov ebx, 10
lea eax, [ebp]-80
add eax, ebx
;заменяется на
lea eax, [ebp]-70
; И т.п.
Очень простой оптимизацией является псевдо распределение регистров. В том шаблоне для выражений, что я приводил выше, можно чередовать пары регистров eax/ebx, ecx/edx, esi/edi. Таким образом увеличится плавучесть popов и pushей, и, следовательно, их сокращаемость (они могут вообще уйти).
Сгенерировал код, посмотрел, сделал пару окон, опять сгенерировал, посмотрел, добавил еще пару (не забывай следить за очередностью – новые окна найдут себе работу только после старых). Вкупе с псевдо распределением можно получить очень даже неплохой код.
Канец, карочи. Задолбался писать. Надеюсь поможет. Удачи!
Такие вот законы рынка 
