Re[9]: Создать новый компилятор
От: ansi Россия  
Дата: 12.02.05 09:03
Оценка: 67 (12)
Я, честно говоря, уже не помню, какие книги я читал. Вот помню точно, что Креншоу был и Драгон Бук был. Больше по лекциям, которые я, к сожалению, не записывал, но слушал.

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

В канонической форме простой компилятор состоит из 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ей, и, следовательно, их сокращаемость (они могут вообще уйти).

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

Канец, карочи. Задолбался писать. Надеюсь поможет. Удачи!
 
Подождите ...
Wait...
Пока на собственное сообщение не было ответов, его можно удалить.