В статье исследуется исходный текст OTCC (Obfuscated Tiny C Compiler, Запутанный Крошечный Компилятор Си) [5], компилятора подмножества языка Си. Французский программист Fabrice Bellard (автор FFmpeg, QEMU) написал этот компилятор для конкурса International Obfuscated C Code Contest (Международный Конкурс Запутанного кода на Си). Позже, на основе OTCC начал разрабатываться известный проект TCC (Tiny C Compiler, Крошечный Компилятор Си) [4].

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

Исходный текст OTCC совместим с ANSI C компиляторами. Под Linux следует указать опцию «-ldl», поскольку компилятор использует функцию dlsym для разрешения внешних ссылок. Подробную информацию о подмножестве Си, реализованном в OTCC, а также примеры использования компилятора см. в [5].

В следующих разделах будет рассматриваться файл otccn.c. Это документированная версия компилятора, в которой имеются элементы контроля синтаксиса. К сожалению, данная версия не обладает возможностью самокомпиляции.

Для того, чтобы OTCC заработал под Windows в начало исходного текста компилятора достаточно вставить следующие строки (версия для компилятора mingw).

#if defined(__MINGW32__)
#include <windows.h>
#define dlsym(l, f) GetProcAddress(LoadLibrary("msvcrt.dll"), f)
#endif

В программах, предназначенных для OTCC под Windows, не следует использовать вызовы WinAPI, поскольку здесь требуется иной формат вызова процедур (stdcall против cdecl). Поэтому, в частности, под Windows самокомпиляция невозможна в любом из вариантов OTCC.Изучение незнакомой программы полезно начинать с главной функции. В файле otccn.c обнаруживается следующее.

606: main(n, t)
607: {
608:     file = stdin;
609:     if (n-- > 1) {
610:         t = t + 4;
611:         file = fopen(*(int *)t, "r");
612:     }

OTCC использует для объявления функций старый K&R-стиль. Здесь предполагается, что аргументы и результат имеют тип int.

Текст для компиляции может поступать из stdin или в виде файла, заданного в командной строке. Если используется последний вариант, возможные дополнительные аргументы будут переданы скомпилированному коду. Здесь видно, что конструкции Си += и [] (индексация в массиве) не поддерживаются, а указатели предполагаются 32-битными.

613:     dstk = strcpy(sym_stk = calloc(1, ALLOC_SIZE), 
614:                   " int if else while break return for define main ") +
     TOK_STR_SIZE;

Инициализируется буфер символов sym_stk. Изначально в нём находятся ключевые слова и «main», функция, имеющаяся в любой программе. Переменная dstk указывает на свободное место в sym_stk.

615:     glo = calloc(1, ALLOC_SIZE);
616:     ind = prog = calloc(1, ALLOC_SIZE);
617:     vars = calloc(1, ALLOC_SIZE);

Инициализируются область глобальных переменных (glo), область порождённого кода (prog) и таблица идентификаторов (vars). По указателю ind добавляется порождённый код в prog. Напомню, что функция calloc обнуляет выделенную память.

618:     inp();
619:     next();
620:     decl(0);

Функция inp читает символ, подготавливая вызов функции next, которая, в свою очередь, выделяет очередную лексему из текста. Вызов decl осуществляет всю остальную работу по компиляции.

630:     return (*(int (*)())*(int *)(vars + TOK_MAIN)) (n, t);

В завершение, происходит запуск порождённого кода. Из таблицы идентификаторов выбирается адрес скомпилированной функции main и выполняется её вызов.Для последовательного распознавания лексем (элементарных единиц языка) используется функция next. Эта функция распознает числа и идентификаторы, символьные константы и операторы, попутно обрабатывая команды препроцессора. На момент её вызова в переменной ch должен содержаться очередной символ входного потока. Результаты работы next возвращает в переменных tok, tokl и tokc.

098: next()
099: {
100:     int t, l, a;
101: 
102:     while (isspace(ch) | ch == '#') {
103:         if (ch == '#') {
104:             inp();
105:             next();
106:             if (tok == TOK_DEFINE) {
107:                 next();
108:                 pdef(TAG_TOK); /* fill last ident tag */
109:                 *(int *)tok = SYM_DEFINE;
110:                 *(int *)(tok + 4) = dstk; /* define stack */
111:             }
112:             /* well we always save the values ! */
113:             while (ch != '\n') {
114:                 pdef(ch);
115:                 inp();
116:             }
117:             pdef(ch);
118:             pdef(TAG_MACRO);
119:         }
120:         inp();
121:     }

В цикле (строка 102) пропускаются пробелы и обрабатываются команды препроцессора. В OTCC широко используется рекурсия, которая делает код более компактным. Первый рекурсивный вызов next возвращает в tok директиву препроцессора. Следующий next возвращает имя, определённое с помощью #define. В соответствующем поле таблицы идентификаторов устанавливается тип SYM_DEFINE и адрес замещающей строки.

Ниже представлены определения вспомогательных функций pdef и inp.

065: pdef(t)
066: {
067:     *(char *)dstk++ = t;
068: }

Функция pdef добавляет символы в буфер.

070: inp()
071: {
072:     if (dptr) {
073:         ch = *(char *)dptr++;
074:         if (ch == TAG_MACRO) {
075:             dptr = 0;
076:             ch = dch;
077:         }
078:     } else
079:         ch = fgetc(file);
080:     /*    printf("ch=%c 0x%x\n", ch, ch); */
081: }

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

Далее снова рассматривается функция next.

122:     tokl = 0;
123:     tok = ch;
124:     /* encode identifiers & numbers */
125:     if (isid()) {
126:         pdef(TAG_TOK);
127:         last_id = dstk;
128:         while (isid()) {
129:             pdef(ch);
130:             inp();
131:         }
132:         if (isdigit(tok)) {
133:             tokc = strtol(last_id, 0, 0);
134:             tok = TOK_NUM;

При обнаружении последовательности из букв или цифр (предикат isid), в буфер добавляются соответствующие символы.

Далее обрабатывается случай появления числового литерала (строка 132). С помощью функции strtol текст преобразуется в значение. Напомню, что strtol также поддерживает восьмеричную и шестнадацатиричную формы записи чисел.

135:         } else {
136:             *(char *)dstk = TAG_TOK; /* no need to mark end of string (we
137:                                         suppose data is initied to zero */
138:             tok = strstr(sym_stk, last_id - 1) - sym_stk;
139:             *(char *)dstk = 0;   /* mark real end of ident for dlsym() */
140:             tok = tok * 8 + TOK_IDENT;
141:             if (tok > TOK_DEFINE) {
142:                 tok = vars + tok;
143:                 /*        printf("tok=%s %x\n", last_id, tok); */
144:                 /* define handling */
145:                 if (*(int *)tok == SYM_DEFINE) {
146:                     dptr = *(int *)(tok + 4);
147:                     dch = ch;
148:                     inp();
149:                     next();
150:                 }
151:             }
152:         }

Рассматривается вариант, когда полученный текст оказался идентификатором. Обращу внимание на константу TAG_TOK, значение которой — пробел. В данном случае текст в буфере выделяется с обеих сторон символами TAG_TOK. Осуществляется поиск идентификатора в sym_stk (строка 138), точнее его смещения относительно начала буфера символов. Благодаря ограничивающим пробелам не допускается ложных срабатываний по strstr.

На следующем этапе смещение превращается в индекс для таблицы идентификаторов (строка 140). Умножение на восемь необходимо, так как элементы таблицы — пары целых. К результату добавляется TOK_IDENT (256), чтобы tok невозможно было спутать с ASCII-символом. Ключевым словам и main соответствуют заранее вычисленные константы, такие как TOK_WHILE и TOK_MAIN. Таблица идентификаторов глобальна, и, как следствие, в OTCC используется единственное глобальное пространство имён.

Условие в 141-й строке выполняется, если идентификатор не является ключевым словом. Проверяется, является ли значение из tok макроидентификатором, и если это так, то next переключается на макроподстановку.

153:     } else {
154:         inp();
155:         if (tok == '\'') {
156:             tok = TOK_NUM;
157:             getq();
158:             tokc = ch;
159:             inp();
160:             inp();

Здесь обрабатываются символьные константы. Функция getq распознает «экранирующие» символы.

161:         } else if (tok == '/' & ch == '*') {
162:             inp();
163:             while (ch) {
164:                 while (ch != '*')
165:                     inp();
166:                 inp();
167:                 if (ch == '/')
168:                     ch = 0;
169:             }
170:             inp();
171:             next();

Данный код пропускает комментарии.

172:         } else
173:         {
174:             t = "++#m--%am*@R<^1c/@%[_[H3c%@%[_[H3c+@.B#d-@%:_^BKd
     <<Z/03e>>`/03e<=0f>=/f<@.f>@1f==&g!=\'g&&k||#l&@.BCh^@.BSi|@.B+j~@/%Yd!@&d*@b";
175:             while (l = *(char *)t++) {
176:                 a = *(char *)t++;
177:                 tokc = 0;
178:                 while ((tokl = *(char *)t++ - 'b') < 0)
179:                     tokc = tokc * 64 + tokl + 64;
180:                 if (l == tok & (a == ch | a == '@')) {
185:                     if (a == ch) {
186:                         inp();
187:                         tok = TOK_DUMMY; /* dummy token for double tokens */
188:                     }
189:                     break;
190:                 }
191:             }
192:         }

Здесь распознаются операторы. Информацию о них содержит переменная t в закодированном виде по основанию 64. Поскольку OTCC не поддерживает литералы массива, автор использовал ASCII-представление двоичных данных.В таблице представлены расшифрованные данные из t. Символ @ используется как «заглушка» для односимвольных операторов.

Код функции next рассмотрен полностью. Строковые литералы распознаются отдельно, как будет показано далее.

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

Далее для описания грамматических правил будет использоваться EBNF-форма [3]. Квадратные скобки в этой форме обозначают необязательный элемент, а фигурные — некоторую, возможно пустую, последовательность из элементов данного вида. Примеры даются в следующих разделах.

Генератор кода использует всего два явно заданных регистра: eax и ecx (см. таблицу 1 предыдущего раздела). Конечные результаты сохраняются в eax, промежуточные — в стеке.

Функция decl обрабатывает локальные или глобальные объявления, в зависимости от значения переданного ей параметра l. Далее термины «объявление» и «определение» считаются синонимами, так как это соответствует действительности для подмножества Си, с которым OTCC имеет дело. Поддерживаются объявления целых и определения функций.

557: decl(l)
558: {
559:     int a;
560: 
561:     while (tok == TOK_INT | tok != -1 & !l) {
562:         if (tok == TOK_INT) {
563:             next();
564:             while (tok != ';') {
565:                 if (l) {
566:                     loc = loc + 4;
567:                     *(int *)tok = -loc;
568:                 } else {
569:                     *(int *)tok = glo;
570:                     glo = glo + 4;
571:                 }
572:                 next();
573:                 if (tok == ',') 
574:                     next();
575:             }
576:             skip(';');

Цикл while (строка 561) прекращает работу, если встретился EOF (-1), а также если в режиме локальных объявлений очередная лексема не совпала с int. Отмечу тот факт, что автор не использует конструкции вида && и ||. Очевидно, в первых версиях OTCC они ещё не поддерживались.

В EBNF-форме объявление целых будет выглядеть следующим образом.

int-decl = "int" { int-name [","] } ";".

Если объявляется локальная переменная, то её индекс в стеке заносится в соответствующее поле таблицы идентификаторов. В противном случае в таблицу заносится адрес в области глобальных переменных.

Функция skip это next с добавленной проверкой синтаксиса.

577:         } else {
578:             /* patch forward references (XXX: do not work for function
579:                pointers) */
580:             gsym(*(int *)(tok + 4));
581:             /* put function address */
582:             *(int *)tok = ind;

В первое поле таблицы идентификаторов заносится адрес определяемой функции (строка 582). Перед этим разрешаются все возможные ссылки вперёд на данную функцию. Список ссылок вперёд, который содержится во втором поле таблицы, подаётся на вход функции gsym. В таком списке каждый следующий элемент содержит адрес предыдущего. Ниже дано определение функции gsym.

252: /* output a symbol and patch all calls to it */
253: gsym(t)
254: {
255:     int n;
256:     while (t) {
257:         n = *(int *)t; /* next value */
258:         *(int *)t = ind - t - 4;
259:         t = n;
260:     }
261: }

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

583:             next();
584:             skip('(');
585:             a = 8;
586:             while (tok != ')') {
587:                 /* read param name and compute offset */
588:                 *(int *)tok = a;
589:                 a = a + 4;
590:                 next();
591:                 if (tok == ',')
592:                     next();
593:             }
594:             next(); /* skip ')' */

EBNF-форма определения функции следующая.

func-decl = func-name "(" { param-name [","] } ")" block.

В цикле while обрабатываются параметры функции. Для каждого из них в первое поле таблицы идентификаторов записывается соответствующий индекс в стеке.

На рисунке ниже показано распределение локальных переменных и параметров функции в стеке. Здесь a1 и a2 являются переданными параметрами, а loc1 и loc2 — локальными переменными. Серым цветом отмечены адрес возврата (ret) и сохранённое в прологе функции значение регистра ebp.

595:             rsym = loc = 0;
596:             o(0xe58955); /* push   %ebp, mov %esp, %ebp */
597:             a = oad(0xec81, 0); /* sub $xxx, %esp */
598:             block(0);
599:             gsym(rsym);
600:             o(0xc3c9); /* leave, ret */
601:             *(int *)a = loc; /* save local variables */
602:         }
603:     }
604: }

Далее порождается код для пролога и эпилога функции. Тело функции компилируется с помощью функции block, которая будет рассмотрена в следующем разделе. Ниже показаны новые вспомогательные функции.

243: o(n)
244: {
245:     /* cannot use unsigned, so we must do a hack */
246:     while (n && n != -1) {
247:         *(char *)ind++ = n;
248:         n = n >> 8;
249:     }
250: }

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

267: /* instruction + address */
268: oad(n, t)
269: {
270:     o(n);
271:     *(int *)ind = t;
272:     t = ind;
273:     ind = ind + 4;
274:     return t;
275: }

Функция oad генерирует опкод n с параметром t и возвращает место расположения этого параметра.

Далее снова рассматривается текст в строках 595–604. Код «sub esp, 0», порождённый в строке 597, модифицируется в строке 601, исходя из количества определённых локальных переменных.

После выполнения функции block в переменной rsym содержится список ссылок вперёд для операторов return. Разрешением этих ссылок занимается код в строке 599.

Таким образом, функция decl производит код по следующему шаблону.

    push ebp       ; пролог
    mov ebp, esp
    sub esp, n * 4 ; резервирование в стеке памяти для n локальных переменных
    ... block ...
    leave          ; эпилог
    retn

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

487: block(l)
488: {
489:     int a, n, t;
490: 
491:     if (tok == TOK_IF) {
492:         next();
493:         skip('(');
494:         a = test_expr();
495:         skip(')');
496:         block(l);
497:         if (tok == TOK_ELSE) {
498:             next();
499:             n = gjmp(0); /* jmp */
500:             gsym(a);
501:             block(l);
502:             gsym(n); /* patch else jmp */
503:         } else {
504:             gsym(a); /* patch if test */
505:         }

Конструкция if/else, которая здесь анализируется, представлена ниже в EBNF-форме.

if = "if" "(" test_expr ")" block [ "else" block ].

Функция test_expr (см. следующий раздел), имеет дело с выражением и, связанным с его результатом, условным переходом. Данная функция возвращает адрес операнда порождённой ей инструкции условного перехода. Значение по этому адресу модифицируется в строке 504, то есть имеет место условный переход за пределы блока, порождённого в строке 496.

Шаблон формируемого кода для if представлен ниже.

    ... expr ...  ; test_expr
    test eax, eax
    je label1
    ... block ...
label1:           ; gsym

Далее рассматривается случай else. Функция gjmp действует аналогично oad из предыдущего раздела. Она генерирует инструкцию безусловного перехода и возвращает адрес операнда этой инструкции. Таким образом, при выходе из блока в строке 496, управление передаётся за else-блок, по адресу, модифицированному в строке 502.

Ниже представлен шаблон кода для if/else.

    ... expr ...  ; test_expr
    test eax, eax
    je label1
    ... block ...
    jmp label2
label1:           ; gsym
    ... block ... ; else-блок
label2:           ; gsym

506:     } else if (tok == TOK_WHILE | tok == TOK_FOR) {
507:         t = tok;
508:         next();
509:         skip('(');
510:         if (t == TOK_WHILE) {
511:             n = ind;
512:             a = test_expr();
513:         } else {
514:             if (tok != ';')
515:                 expr();
516:             skip(';');
517:             n = ind;
518:             a = 0;
519:             if (tok != ';')
520:                 a = test_expr();
521:             skip(';');
522:             if (tok != ')') {
523:                 t = gjmp(0);
524:                 expr();
525:                 gjmp(n - ind - 5);
526:                 gsym(t);
527:                 n = t + 4;
528:             }
529:         }
530:         skip(')');
531:         block(&a);
532:         gjmp(n - ind - 5); /* jmp */
533:         gsym(a);

Здесь рассматриваются управляющие конструкции while и for. Далее даны их представления в EBNF-форме.

while = "while" "(" test_expr ")" block.
for = "for" "(" [expr] ";" [test_expr] ";" [expr] ")" block.

Функция expr (см. следующий раздел) отвечает за разбор выражений.

В случае while, после вызова функции block формируется безусловный переход (строка 532) на сохранённый в переменной n (строка 511) адрес, то есть на код test_expr.

Шаблон для while представлен ниже.

label1:
    ... expr ...  ; test_expr
    test eax, eax
    je label2
    ... block ...
    jmp label1
label2:           ; gsym

Код для конструкции for представлен следующим шаблоном.

    ... expr ...
label1:
    ... expr ...  ; test_expr
    test eax, eax
    je label4
    jmp label3
label2:
    ... expr ...
    jmp label1
label3:           ; gsym
    ... block ...
    jmp label2
label4:           ; gsym

534:     } else if (tok == '{') {
535:         next();
536:         /* declarations */
537:         decl(1);
538:         while(tok != '}')
539:             block(l);
540:         next();

Данный код должен быть понятен без пояснений.

541:     } else {
542:         if (tok == TOK_RETURN) {
543:             next();
544:             if (tok != ';')
545:                 expr();
546:             rsym = gjmp(rsym); /* jmp */
547:         } else if (tok == TOK_BREAK) {
548:             next();
549:             *(int *)l = gjmp(*(int *)l);
550:         } else if (tok != ';')
551:             expr();
552:         skip(';');
553:     }
554: }

В этом, завершающем функцию block, участке кода разбираются конструкции return, break и выражения.

Новые грамматические правила представлены ниже.

return = "return" [expr] ";".
break = "break" ";".

Каждый из операторов return пополняет список ссылок вперёд с помощью переменной rsym. Затем переменная rsym используется в функции decl (см. предыдущий раздел, строка 599).

В случае оператора break на основе параметра l формируется список ссылок вперёд, которые разрешаются в момент разбора конструкций while/for с помощью функции gsym (см. также строку 531).

Работу функции block в EBNF-виде с учётом введённых ранее правил можно представить следующим образом.

block = if | while | for | "{" decl {block} "}" | return | break | expr ";".

Функции expr и test_expr занимаются разбором выражений, выдавая соответствующий код.

475: expr()
476: {
477:     sum(11);
478: }
479: 
480: 
481: test_expr()
482: {
483:     expr();
484:     return gtst(0, 0);
485: }

Функция test_expr формирует условный переход, который зависит от результата выполнения кода, порождённого функцией expr. Функция gtst генерирует последовательность команд «test eax, eax, je/jne label» (см. шаблоны кода управляющих конструкций из предыдущего раздела) и возвращает адрес операнда label.

Вызов функции sum запускает процесс перевода инфиксного выражения в постфиксную форму с порождением соответствующего кода.

433: sum(l)
434: {
435:     int t, n, a;
436: 
437:     if (l-- == 1)
438:         unary(1);
439:     else {
440:         sum(l);
441:         a = 0;
442:         while (l == tokl) {
443:             n = tok;
444:             t = tokc;
445:             next();

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

Я переписал функции sum и unary таким образом, чтобы вместо порождения кода они выводили на экран арифметическое выражение в постфиксной форме.

unary()
{
  if(tok == '(') { /* "(" expr ")" */
    next();
    expr();
    skip(')');
  } else { /* число, идентификатор */
    printf("%s ", last_id);
    next();
  }
}

sum(l)
{
  int n;
  if(l-- == 1)
    unary();
  else {
    sum(l); /* первый аргумент, приоритет l - 1 */
    while(l == tokl) { /* операторы приоритета l */
      n = tok; /* символ оператора */
      next();
      sum(l); /* очередной аргумент, приоритет l - 1 */
      printf("%c ", n);
    }
  }
}

Функция sum рекурсивно вызывается для более низких приоритетов. Наконец, при l = 0, дело доходит до функции unary, рассматриваемой далее в статье. В данном «учебном» варианте она работает с выражениями в скобках, а также с числами и идентификаторами. Результат исполнения функции unary становится результатом вызова sum для первого аргумента. Далее, в цикле while обрабатываются операторы для l = 1 c последующими аргументами — результатами вызова функции sum при l = 0. Процесс повторяется для приоритетов более высоких уровней.

Символы, не являющиеся операторами, такие, например, как ")", обрабатываются функцией sum корректно, поскольку они имеют приоритет 0 (см. функцию next, строка 122).

Далее снова рассматривается функция sum из кода OTCC.

447:             if (l > 8) {
448:                 a = gtst(t, a); /* && and || output code generation */
449:                 sum(l);
450:             } else {
451:                 o(0x50); /* push %eax */
452:                 sum(l);
453:                 o(0x59); /* pop %ecx */
454:                 
455:                 if (l == 4 | l == 5) {
456:                     gcmp(t);
457:                 } else {
458:                     o(t);
459:                     if (n == '%')
460:                         o(0x92); /* xchg %edx, %eax */
461:                 }
462:             }
463:         }
464:         /* && and || output code generation */
465:         if (a && l > 8) {
466:             a = gtst(t, a);
467:             li(t ^ 1);
468:             gjmp(5); /* jmp $ + 5 */
469:             gsym(a);
470:             li(t);
471:         }
472:     }
473: }

Условие в строке 447 выполняется только для операторов && и ||, поскольку операторы ++ и – (приоритет 11) обрабатываются в функции unary. Каждый аргумент проверяется на истинность с помощью кода, за порождение которого отвечает функция gtst в строке 448. Формируется список ссылок вперёд для всех порождённых функцией gtst инструкций условного перехода. В строке 469 эти ссылки разрешаются. Функция li (строки 467, 470) производит код вида «mov eax, n».

Шаблон кода для оператора && представлен ниже. Код для оператора || формируется аналогичным образом.

    ... sum ...
    test eax, eax ; gtst
    je label1
    ... sum ...
    ...
    test eax, eax ; gtst
    je label1
    mov eax, 1    ; li
    jmp label2    ;
label1:           ; gsym
    mov eax, 0    ; li
label2:

Далее будет рассматриваться ветка else, начиная со строки 450. Для операторов с уровнем приоритета 4 и 5 с помощью функции gcmp (строка 456) порождается код следующего вида (в данном случае задействован оператор ==).

    ... sum ...
    ...
    push eax
    ... sum ...
    pop ecx
    cmp ecx, eax ; gcmp
    mov eax, 0
    sete al

Операторы / и % имеют одинаковый tokc (см. таблицу операторов), то есть порождают один и тот же код. Дополнительная инструкция для получения остатка появляется в строке 460.

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

310: /* l is one if '=' parsing wanted (quick hack) */
311: unary(l)
312: {
313:     int n, t, a, c;
314: 
315:     n = 1; /* type of expression 0 = forward, 1 = value, other =
316:               lvalue */
317:     if (tok == '\"') {
318:         li(glo);
319:         while (ch != '\"') {
320:             getq();
321:             *(char *)glo++ = ch;
322:             inp();
323:         }
324:         *(char *)glo = 0;
325:         glo = glo + 4 & -4; /* align heap */
326:         inp();
327:         next();

Параметр l регулирует, будет ли распознан оператор присваивания.

В данном участке кода производится лексический анализ на предмет строкового литерала. Строка записывается в область глобальных переменных, после чего указатель glo выравнивается на границу целого. Адрес строки используется функцией li.

328:     } else {
329:         c = tokl;
330:         a = tokc;
331:         t = tok;
332:         next();
333:         if (t == TOK_NUM) {
334:             li(a);

Данные о текущей лексеме сохраняются в соответствующих переменных, читается следующая лексема.

Если распознан числовой литерал, функция li генерирует для него код.

335:         } else if (c == 2) {
336:             /* -, +, !, ~ */
337:             unary(0);
338:             oad(0xb9, 0); /* movl $0, %ecx */
339:             if (t == '!')
340:                 gcmp(a);
341:             else
342:                 o(a);

Здесь рассматриваются префиксные операторы. Вызов функции unary возвращает аргумент оператора. Регистр ecx обнуляется в данном случае, так как унарные и бинарные операторы + и - производят один и тот же код (см. таблицу операторов).

343:         } else if (t == '(') {
344:             expr();
345:             skip(')');

Вышеприведённый код не отличается от аналогичного из «учебной» версии unary.

346:         } else if (t == '*') {
347:             /* parse cast */
348:             skip('(');
349:             t = tok; /* get type */
350:             next(); /* skip int/char/void */
351:             next(); /* skip '*' or '(' */
352:             if (tok == '*') {
353:                 /* function type */
354:                 skip('*');
355:                 skip(')');
356:                 skip('(');
357:                 skip(')');
358:                 t = 0;
359:             }
360:             skip(')');
361:             unary(0);
362:             if (tok == '=') {
363:                 next();
364:                 o(0x50); /* push %eax */
365:                 expr();
366:                 o(0x59); /* pop %ecx */
367:                 o(0x0188 + (t == TOK_INT)); /* movl %eax/%al, (%ecx) */
368:             } else if (t) {
369:                 if (t == TOK_INT)
370:                     o(0x8b); /* mov (%eax), %eax */
371:                 else 
372:                     o(0xbe0f); /* movsbl (%eax), %eax */
373:                 ind++; /* add zero in code */
374:             }

Далее рассматривается разыменовывание указателей с приведением типа. Анализируется две формы: «*(int *)» и «*(int (*)())». Вместо int могут быть использованы типы char или void. Разбирается аргумент данного преобразования с помощью функции unary в строке 361.

Если далее встретился оператор присваивания, порождается код, вычисляющий значение выражения справа от оператора присваивания (строка 365), и результат, с учётом типа указателя, записывается по адресу, ранее полученному с помощью функции unary.

В отсутствие оператора присваивания, формируется код для разыменовывания указателя, опять же, с учётом его типа.

375:         } else if (t == '&') {
376:             gmov(10, *(int *)tok); /* leal EA, %eax */
377:             next();

Здесь рассматривается операция взятия адреса. Из таблицы идентификаторов по первому полю извлекается нужный адрес. Далее формируется код, указанный в комментарии автора.

Ниже представлена функция gmov, которая обладает интересными свойствами.

304: gmov(l, t)
305: {
306:     o(l + 0x83);
307:     oad((t < LOCAL) << 7 | 5, t);
308: }

Константа LOCAL (0x200) задаёт предел для индексов локальных переменных. Благодаря манипуляциям с битовыми полями опкода возможна адресация двух видов, обычная косвенная и внутри стекового фрейма, относительно регистра ebp. Таким образом в одной функции поддерживается работа с локальными и глобальными переменными.

Далее продолжает рассматриваться функция unary.

378:         } else {
379:             n = *(int *)t;
380:             /* forward reference: try dlsym */
381:             if (!n)
382:                 n = dlsym(0, last_id);
383:             if (tok == '=' & l) {
384:                 /* assignment */
385:                 next();
386:                 expr();
387:                 gmov(6, n); /* mov %eax, EA */
388:             } else if (tok != '(') {
389:                 /* variable */
390:                 gmov(8, n); /* mov EA, %eax */
391:                 if (tokl == 11) {
392:                     gmov(0, n);
393:                     o(tokc);
394:                     next();
395:                 }
396:             }
397:         }
398:     }

На данном этапе предполагается, что обнаружен идентификатор. Его адрес n извлекается в строке 379.

Если оказывается, что адрес идентификатору ещё не присвоен (0), то делается попытка получить его с помощью функции dlsym, которая использует имя идентификатора last_id для поиска адреса в динамически подключаемой библиотеке libc.

Если после идентификатора встретился оператор присваивания, порождается код для вычисления выражения справа (строка 386) и загрузки результата по адресу n, полученному ранее.

Если оператора присваивания не оказалось, формируется код, использующий адрес n в качестве результата (см. строку 390). Здесь же рассматривается возможное появление постфиксных операторов ++ и – (см. строку 391).

В завершающей части функции unary рассматривается вызов функции.

400:     /* function call */
401:     if (tok == '(') {
402:         if (n == 1)
403:             o(0x50); /* push %eax */
404: 
405:         /* push args and invert order */
406:         a = oad(0xec81, 0); /* sub $xxx, %esp */
407:         next();
408:         l = 0;
409:         while(tok != ')') {
410:             expr();
411:             oad(0x248489, l); /* movl %eax, xxx(%esp) */
412:             if (tok == ',')
413:                 next();
414:             l = l + 4;
415:         }
416:         *(int *)a = l;
417:         next();

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

Производится разбор параметров функции, которые помещаются в стек в обратном порядке (см. рис. 1).

418:         if (!n) {
419:             /* forward reference */
420:             t = t + 4;
421:             *(int *)t = psym(0xe8, *(int *)t);
422:         } else if (n == 1) {
423:             oad(0x2494ff, l); /* call *xxx(%esp) */
424:             l = l + 4;
425:         } else {
426:             oad(0xe8, n - ind - 5); /* call xxx */
427:         }
428:         if (l)
429:             oad(0xc481, l); /* add $xxx, %esp */
430:     }
431: }

Наконец, рассматривается вид вызова функции. Имеется три случая.

1. Ссылка вперёд. Формируется команда вызова функции (строка 421) и список ссылок вперёд пополняется новым адресом для данного идентификатора.
2. Значение выражения. Формируется команда вида «call [esp + l]» (строка 423). Здесь индекс l указывает на ранее сохранённый адрес функции (строка 403).
3. Обычный вызов ранее определённой функции (строка 426).

После рассмотрения вызова функции порождается код, который освобождает стек от занесённых в него ранее параметров (строка 429).

В качестве примера, далее демонстрируется код, формируемый при разборе следующего текста на Си (функция main, строка 630).

(*(int (*)())*(int *)(vars + TOK_MAIN)) (n, t)

    mov eax, [vars]     ; vars
    push eax
    mov eax, TOK_MAIN   ; TOK_MAIN
    pop ecx
    add eax, ecx        ; +
    mov eax, [eax]      ; разыменовывание указателя
    push eax            ; сохранение адреса ф-ии в стеке
    sub esp, 8          ; стековая память под параметры
    mov eax, [ebp + 8]  ; n
    mov [esp + 0], eax
    mov eax, [ebp + 12] ; t
    mov [esp + 4], eax
    call [esp + 8]      ; вызов ф-ии
    add esp, 12         ; очистка стека

Прошу извинить меня, если изучение кода компилятора OTCC показалось кому-то из читателей слишком занудным. Большой объем данной статьи лишний раз показывает, как много талантливые программисты могут выразить в малом.

[1]	Брайан Керниган, Деннис Ритчи. Язык программирования C. — Вильямс, 2009.
[2]	Альфред Ахо, Рави Сети, Джеффри Ульман. Компиляторы. Принципы, технологии, инструменты. — Вильямс, 2003.
[3]	Никлаус Вирт. Построение компиляторов. — ДМК Пресс, 2010.
[4]	http://bellard.org/tcc/
[5]	http://bellard.org/otcc/

Подсветка синтаксиса кода сделана с помощью Colorer.