Учебный компилятор (для лекций по курсу "Разработка компиляторов")

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

Входной язык

Входным языком является ограниченное подмножество языка Си. Ограничения перечислены ниже.

• Нет структур.
• Базовые типы -- только void, int и char. Нет короткого целого числа short. Нет вещественных типов double и float, нет беззнаковых типов unsigned, тип char считается знаковым. Нет модификаторов типов (static, const, volatile и т.п.).
• Нет сложных описаний типов, например "int *(*a)[]" (указатель на массив указателей типа int). В операциях описания нельзя использовать скобки, указатели на указатель, массивы массивов и т.п. (Массивы указателей использовать можно.) Некоторые примеры допустимых описаний: int i, *a[100], b[], *c; char c, s[100], *p, *strs[10]; void f(int c, char *a[]);
• Нельзя использовать следующие управляющие конструкции Си:
  • goto (используйте break или continue);
  • цикл "for" (используйте "while");
  • "do ... while" (используйте нормальный "while" и "break", если необходимо);
  • "switch" (используйте if... else if... else...).

Отметим, что логические выражения реализованы полностью, как положено по стандарту (например, второй аргумент конъюнкции "&&" не вычисляется, если первый равен false).

Устройство компилятора

Поскольку целью является иллюстрация современных средств и методов разработки, то компилятор максимально использует стандартные средства. При этом используются только свободно распространяемые GNU-программы. Компилятор реализован в системе Linux и, конечно, может быть скомпилирован в любом Unix'е с установленным пакетом GNU, а также в Windows с пакетом Cygwin (Cygwin -- это GNU под Windows).

Компилятор считывает исходный текст Си-программы из файла и преобразует ее в программу на языке Ассемблера, которая записывается в выходной файл. Используется Аccемблер "as", входящий в пакет GNU, целевым процессором является Intel 80386. Машинно-зависимая чась компилятора, т.е. описание системы комманд процесора, локализована в одном файле (в одной таблице) и составляет его небольшую часть. Компилятор может быть легко адаптирован для любого другого процессора или Ассемблера.

• Сканер реализован с помощью утилиты FLEX (GNU-аналог LEX-а).
• Парсер реализован с помощью утилиты BISON (GNU-аналог YACC-а).
• Парсер предварительно компилирует каждое выражение в синтаксическое дерево. Затем, после построения дерева выражения, запускается RTL-генератор, который выдает фрагмент программы на языке RTL (Register Transfer Language), вычисляющий это выражение. RTL является основной формой внутреннего представления программы. RTL представление не зависит от системы команд процессора целевой машины и используемого Ассемблера.
• RTL код строится по отдельности для каждой функции. По окончании разбора функции выполняется оптимизация на уровне RTL (в настоящий момент не реализована), затем производится распределение регистров и, наконец, генерация ассемблерного кода функции.
• По окончании разбора исходного файла выполняется генерация ассемблерного кода для описаний глобальных переменных. Она основывается на информации, содержащейся в глобальной таблице символов, которая была получена в процессе разбора.

Компилятор называется "TinyCC" (по аналогии со SmallC). В нем использовались некоторые идеи мини-компилятора "Small-C" (Ron Cain) и учебного компилятора "TinyC", разработанного Д.В.Варсанофьевым и А.Г.Дымченко для поддержки аналогичного спецкурса в Московсом университе. Вместе с тем данный компилятор достаточно сильно отличается от "TinyC" (написан заново без использования кода TinyC, полностью реализует логические выражения, использует RTL в качестве машинно независитого внутреннего представления программы, что позволяет выполнять машинно независимую оптимизацию, и т.д.)

Исходный код компилятора:

• tar.gz-архив
• zip-архив

Для сборки компилятора выполните "make" без аргументов. Затем "tinycc --help".

Архив содержит 3 тестовых файла "tstgcd.c", "tstsum.c" и "tstchar.c", написанных с соблюдением ограничений на входной язык, накладываемых компилятором "tinycc". Чтобы скомпилировать и запустить, например, программу "tstgcd.c", выполните (в Unix'е или под Cygwin) следующую последовательность комманд:

Компиляция под Windows

Под Windows следует установить пакет Cygwin (это вообще-то полезно сделать безотносительно к "TinyCC") -- иначе откуда вы возьмете LEX и YACC (bison и flex)? Есть очень небольшие отличия в ассемблерах "as" для Linux'а и для Windows в пакете Cygwin. А именно, глобальные имена в Windos начинаются с символа подчеркивания "_", в Linux'е он не нужен. Также почему-то Cygwin-Ассемблер "as" не понимает директив ".type" и ".size" -- впрочем, как оказалось, они не обязательны, и ассемблерный текст отлично компилируется и без них. Все отличия между Linux и Windows-версиями TinyCC содержатся в файле "i80386.c", в котором применяется условная компиляция. При работе под Windows в пакете Cygwin компилятор gcc определяет переменную препроцессора "__CYGWIN__", которая используется в директивах условной компиляции, когда следует различать случаи Linux и Windows. Таких мест очень немного, и все они сосредоточены в файле "i80386.c". В этом файле, а также в файле "i80386.h" содержится вся машинно-зависимая часть компилятора, остальной код не зависит ни от процессора, ни от используемого Ассемблера.

Материалы к лекциям

• Более детальное описание учебного компилятора.
• Список задач.