Использование учебного компилятора в курсе
"Формальные языки и основы компиляции"
Why Tiny-C.
Курс основ компиляции, имеющий практическую направленность,
должен включать в себя значительное количество разобранных при-
меров. Весьма привлекательно привести в качестве крупного при-
мера законченный компилятор. Он может служить источником боль-
шого количества задач на модификацию и усовершенствование ре-
ального, достаточно большого проекта. Выбор компилятора для та-
кой цели (начиная с выбора входного и выходного языка) не явля-
ется тривиальной задачей. Компилятор реального языка программи-
рования в коды реального процессора - слишком большая для учеб-
ных целей программа. Она окажется неизбежно перегруженной дета-
лями, связанными с особенностями языка, системы команд, опера-
ционной системы и т.д. С другой стороны, компилятор "игрушечно-
го" языка в коды виртуальной машины обычно не содержит многих
важных компонент настоящего компилятора. Такой "игрушечный"
пример не позволяет продемонстрировать проблемы, возникающие,
например, при организации таблиц символов или генерации кода.
В качестве компромиссного решения был выбран написанный спе-
циально для учебных целей компилятор с подмножества языка C в
язык ассемблера машины PDP11. Реализованное подмножество C
близко языку, который воспринимает компилятор Small-C [1]. Пар-
сер этого компилятора реализован методом рекурсивного спуска. В
процессе разбора немедлeнно порождается выходной текст на ас-
семблере процессора i8080. Реализация компилятора содержит око-
ло 2000 строк на собственном входном языке, таким образом, выб-
ранное подмножество C достаточно богато. Познакомиться с этим
компилятором можно в более доступной книге [2]. Приведенный там
текст компилятора RatC на 90% совпадает с текстом Small-C.
Исходный компилятор не подходил для наших целей по следующим
причинам:
1. Этот весьма компактный компилятор написан "одним куском"
и плохо приспособлен для изучения и модификации.
2. Генерация кода для выражения сводится, фактически, к пе-
реводу его в постфиксную запись и реализации "стекового кальку-
лятора" на аппаратном стеке микропроцессора.
В результате, был написан компилятор, названный TinyC. Из
[1] был позаимствован только исходный язык. Для реализации ска-
нера и парсера компилятора применены LEX и YACC соответственно,
что позволило сделать компилятор весьма компактным и обозримым.
Некоторое влияние на структуру компилятора оказал Portable C
Compiler операционной системы UNIX.
Описание языка
Small-C является подмножеством C. С целью дать представление
об этом подмножестве здесь лишь перечислены элементы C, вклю-
ченные в (или исключенные из) этого подмножества. Более подроб-
ные сведения о языке C можно почерпнуть в [3].
Единицей компиляции является файл - возможности сборки прог-
раммы из нескольких файлов и раздельной компиляции обеспечива-
ются соответствующими ассемблером и загрузчиком.
Средства препроцессора обеспечивают только простую (без па-
раметров) подстановку имен, определяемых оператором #define.
Можно описывать переменные только следующих типов: целые
(int), символы (char), одномерные массивы символов или целых,
указатели на символы или целые.
Отсутствует инициализация переменных.
Имеется только два класса памяти: статическая, доступная во
всей программе (если переменная описана вне функции), и автома-
тическая, локализованная в пределах функции (если имя описано
внутри функции).
Нельзя специфицировать тип результата функции - всегда
возвращается целое. Однако язык позволяет свободно смешивать
указатели и целые.
Из управляющих конструкций реализованы условный оператор if,
if else, цикл пока while, а также операторы break, continue,
return и return .
В выражениях можно употреблять только следующие операции,
перечисленные в порядке убывания приоритета:
[] (индексация) () (вызов функции)
++ -- (префиксные и постфиксные)
* (значение) & (адрес) - (унарный минус)
* / %
+ -
<< >>
< <= > >=
== !=
&
^
|
=
Таким образом, не реализованы операции языка C:
? : || && sizeof (имя типа) ~ ! -> . ,
Не производится свертка константных выражений - размерность
массива должна быть константой. Для формальных параметров она
может опускаться, например int a[];
Архитектура компилятора
Компилятор построен по классической однопроходной схеме. Он
содержит следующие исполнители: Сканер, Парсер, Таблица симво-
лов, Дерево, Генератор кода. В начале работы открываются вход-
ной и выходной файлы, выполняется инициализация и запускается
парсер - все остальное делают его семантические подпрограммы.
Для получения очередной лексемы парсер вызывает сканер. Встре-
ченные в исходном тексте имена переменных заносятся сканером в
таблицу символов. Для всех элементов языка кроме выражений
(т.е. для описаний переменных, функций, управляющих конструк-
ций) выходной ассемблерный код порождается немедленно в процес-
се их разбора. В процессе разбора выражения парсер строит его
дерево. Построение осуществляется с помощью исполнителя "Дере-
во", который также проверяет соответствие типов операндов и вы-
числяет тип каждого узла дерева. После того, как выражение ра-
зобрано целиком, вызывается генератор кода, строящий код для
выражения по его дереву. Генерация кода состоит из двух этапов.
Вначале вычисляется "сложность" (количество регистров, необхо-
димое для вычисления) каждого поддерева. На втором этапе в про-
цессе обхода дерева генерируется собственно код.
Рассмотрим каждый из исполнителей более подробно.
Сканер (файл scaner.l)
Задача, решаемая сканером, довольна проста - выделение лек-
сем из последовательности символов входного файла. Сканер ре-
ализован с помощью программы LEX. Конечный автомат может нахо-
дится в следующих метасостояниях:
S - исходное (нормальное) состояние,
COM - внутри комментария: поиск конца комментария "*/",
STR - внутри строки, заключенной в кавычки или апострофы,
DEF1, DEF2 - обработка предложения препроцессора #define.
Распознавание лексемы завершается возвратом из функции yylex.
При этом возвращается код лексемы, а переменной yylval присва-
ивается ее значение. Для уменьшения объема парсера многие син-
таксически эквивалентные лексемы имеют однаковый код, различа-
ясь лишь значениями. Например, ключевые слова int и char соот-
ветствуют одной лексеме TYPE, но имеют различные значения - INT
и CHAR соответственно. Значениями операторов + * и т.д. являют-
ся сами коды лексем.
Выделенный сканером идентификатор немедленно заносится в
таблицу символов с помощью функции nameenter. Возвращаемое этой
функцией значение лексемы NAME является указателем на запись в
таблице символов, соответствующую данному идентификатору. Обра-
тите внимание на то, что для правильного распознавания ключевых
слов регулярное выражение для идентификатора должно быть распо-
ложено после выражений, описывающих ключевые слова.
Выделение обработки комментария в отдельное состояние поз-
воляет обрабатывать комментарии любой длины, не ограниченной
размером буфера сканера yytext.
Обработка текстовых констант производится в отдельном состо-
янии. Символы строки, включая преобразованные последовательнос-
ти вида \x или \nnn, накапливаются в буфере strbuf. После раз-
бора символьный константы (в одиночных кавычках) ей присваива-
ется код ICON (целая константа) и возвращается целое значение.
Строчная константа (в двойных кавычках) немедленно заносится в
секцию строчных констант с помощью функции strenter. Возвраща-
емое этой функцией число - значение лексемы STRING - номер мет-
ки, присвоенной строке.
Функции простейшего препроцессора реализованы непосредствен-
но в сканере. При разборе строки вида # define <имя> ..., имя
(точнее не более NAMLEN первых его символов) копируется в буфер
defname. Определение имени копируется в буфер strbuf, при этом
из него удаляются лишние пробелы, табуляции и комментарии. За-
тем имя и его определение заносится в таблицу функцией
defenter.
После выделения каждого имени проверяется, не содержится ли
его определение в таблице макро. Если определение найдено (в
этом случае функция deflookup возвращает указатель на значе-
ние), то значение возвращается в входной поток с помощью
функции unput, а само имя игнорируется. Такой трюк обеспечивает
повторное сканирование значения макро.
Построенный с помощью LEX'а сканер считывает исходный файл
из потока yyin и содержит в переменной yylineno номер текущей
строки, который используется компилятором при выдаче сообщений
об ошибках.
Упражнения:
1. Что произойдет при сканировании следующего оператора?
#define four 2 /* комментарий 1 */ * /* комментарий 2 */ 2
Исправьте эту ошибку.
2. Если определение макро содержит прямую или косвенную ре-
курсию, то сканер зациклится при попытке его расширения. (Из-за
ограниченного размера стека возвращенных символов этот цикл
быстро завершится терминацией компилятора с диагностикой типа
memory protect violation). Сделайте диагностику таких ошибок
более разумной.
3. Добавьте в препроцессор оператор #include "имя файла".
Для решения этой задачи будет полезна функция yywrap LEX'a.
4. Добавьте в препроцессор операторы условной компиляции:
#ifdef <имя>, #else, #endif.
5. Сделайте так, чтобы текст после символов // до конца
строки рассматривался как комментарий. (Такой способ записи
комментария имеется в языке C++.)
6. Обеспечьте обработку вложенных комментариев, т.е. выраже-
ние /* /* */ */ должно восприниматься как один комментарий.
7. Сканер TinyC воспринимает только десятичные константы.
Обеспечьте возможность записи восьмеричных и шестнадцатеричных
констант как в "настоящем" C.
8. Добавьте в язык оператор asm { последовательность команд
ассемблера } для вставки в C-программу фрагментов на ассембле-
ре.
9. Разделители строк в C игнорируются везде кроме оператора
препроцессора #define и строчных констант. Чтобы игнорировать
их и в этих случаях надо в конце строки записать "\". Добавьте
эту возможность в TinyC.
10*. Реализуйте сканер, не используя LEX. Насколько изменился
объем сканера в строчках исходного текста и в байтах скомпили-
рованной программы? Насколько быстрее он стал работать?
Парсер (файл parser.y)
Парсер реализован с использованием программы YACC. Ес-
тественная грамматика языка TinyC оказалась подходящей для раз-
бора методом LALR(1). (Она содержит один конфликт в случае
if(e)if(e)s_else s, который правильно разрешается по умолчанию
предпочтением сдвига свертке). Она была дополнена правилами для
восстановления после синтаксических ошибок и преобразована в
правилах, описывающих условный оператор, так, чтобы метку для
перехода вперед можно было хранить в семантическом стеке.
Семантический стек состоит из элементов типа YYSTYPE, опре-
деленного как int для pdp11. Этот тип должен быть целым размера
достаточного для хранения указателя, так как в стеке и перемен-
ной yylval могут хранится целые числа, указатели на элемент
таблицы символов и на узел дерева выражений. Средства YACC'a
для спецификации типа терминалов и нетерминалов (и объявление
типа YYSTYPE как union) не использовались, так как некоторые
компиляторы (например, decus C) не умеют присваивать структуры.
Описания переменных компилируются непосредственно. Для гло-
бальной переменной генерируется метка с ее именем и резервиру-
ется память. При описании локальной переменной ей отводится
место в кадре стека текущей функции, в результате чего locptr
становится равным смещению переменной относительно fp. Смещение
формального параметра определяется при его появлении в списке.
Описание формального параметра не обязательно, по умолчанию он
имеет тип int. Описание формального параметра - массива преоб-
разуется в описание указателя. Порождаемый код для параметров и
локальных переменных состоит из комментария.
Соглашения о связях компилятора TinyC совпадают с соглашени-
ями, принятыми в компиляторе decus C, что позволяет использо-
вать его библиотеки при выполнения программ. Параметры функции
передаются через стек, первым в стек проталкивается самый пра-
вый параметр. Функция вызывается командой jsr pc, при выполне-
нии которой в стек помещается адрес возврата. В начале каждой
функции командой jsr r5, csv~ вызывается подпрограмма, сохраня-
ющая регистры и устанавливающая новое значение fp (frame
pointer, указатель кадра), в качестве которого используется ре-
гистр r5. После этого на стеке отводится место для локальных
переменных. Функция обязана восстановить содержимое регистров
r2-r5 при возврате. Это осуществляется переходом jmp cret~ на
соответствующую подпрограмму. Кадр стека функции имеет имеет
следующую структуру:
...
1 параметр 4 = SPARAM
адрес возврата 2
r5 (старый fp) 0 <- fp
r4 -2
r3 -4
r2 -6
1 лок. переменная -8 = SAUTO = sp после возврата из csv~
...
Порожденный компилятором код размещается в трех секциях. В
секции c~code содержаться выполняемые команды процессора, в
секции c~data - глобальные (статические) переменные и в секции
c~strn - строчные константы. Так как описания глобальных пере-
менных могут появляться только между функциями, то для правиль-
ного размещения кода достаточно в начале каждой функции делать
текущей секцию c~code, а в конце - c~data. При появлении строч-
ной константы в тексте, сканер вызывает предписание strenter,
которое делает текущей секцию c~strn, печатает константу и де-
лает текущей снова секцию c~code. (Строчные константы могут по-
являться только внутри функций).
Для получения уникальных меток служит макро newlab, выдающее
при каждом новом обращении очередное натуральное число. В конце
каждой функции имеется метка, содержащаяся в переменной retlab.
Оператор return компилируется в переход на эту метку.
Управляющие конструкции компилируются обычным образом:
e e labcont:
if( e ) bxx lab1 if( e ) bxx lab1 e
stmt ... stmt ... while( e ) bxx labbrk
lab1: br lab2 stmt ...
else lab1: br labcont
stmt ... labbrk:
lab2:
Для хранения меток условного оператора используется семантичес-
кий стек парсера: lab1 приписывается к нетерминалу ifh, lab2 -
к нетерминалу ihelh. Для хранения меток операторов цикла ис-
пользуется отдельный стек wstack, указатель wptr указывает на
вершину этого стека. Это решение связано с тем, что метки цикла
используются операторами break и continue, при обработке кото-
рых нетерминалы цикла могут оказаться на разной глубине семан-
тического стека. В стеке wstack хранится только метка labcont
(на нее осуществляется переход по оператору continue). Так как
эта пара меток получена двумя последовательными вызовами
newlab, метка labbrk (на нее переходят по оператору break)
всегда равна labcont+1.
В процессе разбора выражения строится его дерево. Нетермина-
лам e (выражение), term, elist (список фактических параметров),
elist2 приписывается семантическая информация - указатель на
корень дерева, описывающего соответствующее нетерминалу выраже-
ние. При свертке правила грамматики вызывается функция tree,
которая добавляет к дереву новый корень для унарных операций
или объединяет два дерева в одно для бинарных операций. При
создании листьев дерева, которые соответствуют именам перемен-
ных и целым и строчным константам, их значения, занесенные ска-
нером в переменную yylval, передаются исполнителю "дерево" че-
рез переменные trnval (указатель на элемент таблицы имен) или
trival (значение целой константы или номер метки строчной
константы).
Операция индексации массива a[i] при построении дерева пере-
водится в форму *(a+i). Коды унарных операций - * & получаются
из кодов лексем совпадающих с ними бинарных операций прибавле-
нием константы UNARY, а коды префиксных операций ++ -- - из ко-
дов постфиксных операций прибавлением константы PREFIX. Опера-
ция "," имеет семантику "протолкнуть результат вычисления лево-
го поддерева в стек параметров". Для правильного порядка вычис-
ления фактических параметров нетерминал elist2 (непустой список
параметров) задан с помощью правой рекурсии.
При свертке правила, содержащего выражение в правой части,
вызывается генератор кода для выражения. В качестве параметра
ему передается элемент семантического стека, содержащий указа-
тель на построенное к данному моменту дерево выражения.
При синтаксической ошибке парсер, построенный с помощью
YACC'а выдает только малоинформативную диагностику "Syntax
error in line ...". Восстановление после ошибки происходит сле-
дующим образом. Если ошибка обнаружена внутри оператора, то
пропускаются все лексемы до ближайшей точки с запятой или зак-
рывающейся фигурной скобки. Фрагмент текста от начала операто-
ра, при разборе которого была обнаружена ошибка, до точки запя-
той или скобки, включая последние, сворачивается в нетерминал
stmt (оператор). Если ошибка обнаружена вне оператора, то пар-
сер "вываливается" на внешний уровень, пытаясь начать разбор
описания глобальной переменной или функции.
Упражнения:
1. Добавьте в язык возможность инициализации глобальных пе-
ременных целыми константами.
int i = 3;
char text[4] = { 'd', 'a', 't', 'a' } ;
2. Добавьте в язык альтернативный синтаксис описания фор-
мальных параметров функции:
strncpy( d, s, n ) char *d, *s; int n;
strcpy( char *d, *s; int n )
3. Добавьте в язык цикл DO stmt WHILE( e ) CM.
4. Добавьте в язык цикл for. Обратите внимание на правильную
работу операторов break и continue.
5. Добавьте в язык метки и оператор goto.
6. Добавьте в язык оператор switch.
0*. Исследуйте эффективность реализованных средств восста-
новления после ошибок. Проверьте по-крайней мере поведение ком-
пилятора при типичных ошибках - несбалансированных круглых или
фигурных скобках. Усовершенствуйте восстановление после ошибок
и сделайте их диагностику более информативной.
Таблица символов (файл symtab.c)
Исполнитель "таблица символов" содержит реализацию двух таб-
лиц - таблицы обозначений, введенных оператором #define и таб-
лицы имен C-программы.
Элемент таблицы #define, описываемый структурой dnd, имеет
переменный размер и состоит из указателя на следующий, поля
имени обозначения фиксированной длины и поля определения пере-
менной длины. Обе строки терминированы нулем. Таблица состоит
из DEFMAX односвязных списков. Указатели на списки собраны в
массив defhdr. Определение добавляется/ищется в списке с индек-
сом равным значению hash-функции, принимающей значения в диапа-
зоне 0..DEFMAX-1. В качестве такой функции выбрана сумма симво-
лов имени по модулю DEFMAX.
Таблица имен C-программы имеет несколько более сложную
структуру, так как должна обеспечивать хранение локальных для
каждой функции и глобальных переменных. Записи всех переменных
провязаны в один односвязный список, указатель на который хра-
нится в переменной stbhdr. Так как указатель на следующий эле-
мент списка stnext является первым в среди полей записи, то
stbhdr может выполнять роль NULL-элемента, что делает операцию
удаления первого элемента списка однородной.
Локальные переменные текущей функции находятся в начале это-
го списка, раньше всех глобальных переменных. Для их разделения
используется указатель stbloc, ссыающийся на описание первой в
списке глобальной переменной. В начале каждой функции парсер
вызывает функцию openlocal, устанавливающую этот указатель на
первый элемент списка. В конце каждой функции парсер вызывает
функцию closelocal, которая удаляет из списка все локальные пе-
ременные, занесенные сканером в процессе разбора, и устанавли-
вает указатель stbloc в конец списка. Это обеспечивает правиль-
ное разделение локальных и глобальных переменных, так как впер-
вые встреченная сканером переменная добавляется в начало спис-
ка, а любая переменная в C должна быть описана до ее использо-
вания.
Исключение из этого правила составляют функции, т.е. пере-
менная, впервые встреченная в контексте f( ... ), неявно описы-
вается как функция. Поэтому в closelocal не удаляются из табли-
цы переменные - функции. Так как используемый ассемблер требует
обязательного описания всех имен (но не обязательно перед упот-
реблением), в конце работы компилятора вызывается функция
stogbl. В результате ее работы в директивах ассемблера .globl
перечисляются все имена, находящиеся в данный момент в таблице
символов. Эта директива объявляет глобальными уже определенные
символы (т.е. имена глобальных переменных и функций) и внешними
неопределенные имена функций (библиотечных или отдельно скомпи-
лированных функций).
Для получения/освобождения памяти для элементов таблицы сим-
волов используется стандартные функции C-библиотеки malloc и
free.
Упражнения:
1. Реализуйте таблицу имен hash-методом.
2. Реализуйте таблицу имен в виде двоичного дерева.
Изменилась ли общая эффективность компилятора?
3. Насколько хороша используемая в таблице #define
hash-функция? Проведите эксперименты с другими функциями.
4. Реализуйте свою систему распределения динамической памя-
ти. Она должна быть более простой и эффективнной чем стан-
дартная, так как блоки переменной длины #define таблицы не ос-
вобождаются, а освобождаемые блоки таблицы символов имеют фик-
сированную длину.
Дерево (файл tree.c)
Память для дерева выражений выделяется из массива trebuf.
Так как дерево удаляется целиком после генерации кода для него,
то выделение памяти тривиально - указатель trefre указывает на
первый свободный узел дерева. Функция tralloc возвращает указа-
тель на новый узел дерева, занеся в него код операции и указа-
тели на левое и правое поддерево. Функция tone, возвращает де-
рево, соответствующее целой константе 1, функция trfree осво-
бождает всю память, занимаемую деревом.
Основная функция tree аналогична tralloc, но кроме добавле-
ния еще одного узла к дереву, она проверяет соответствие типов
операндов для данной операции и вычисляет тип результата. Этот
тип определяется комбинацией битов поля trtag:
бит 1 0
-------------------------------------------
TLVAL l-значение значение
TPTR указатель переменная
TCHAR char int
Кроме вычисления типа результата, функция определяет, ис-
пользуется ли аргументы в качестве значения или l-значения.
Для упрощения программы проверки и тип результата закодиро-
ваны в векторе trops, индексируемым кодами операций. По умолча-
нию тип результата равен типу левого операнда. Биты:
OLV - левый аргумент используется как значение.
Если этот бит равен нулю, то левый аргумент должен быть
l-значением, а тип результата равен типу левого аргумен-
та, но не является l-значением. Если тип левого аргумента
- char, то тип результата будет int.
ORV - правый аргумент используется как значение.
OLI - левый аргумент не должен быть указателем
ORI - правый аргумент не должен быть указателем
OINT - результат операции целый
OCMP - операция отношения: если хотя бы один из операндов ука-
затель, то требуется беззнаковое сравнение
OSPC - предыдущих проверок недостаточно, код обрабатывается
отдельно оператором switch.
Специальные действия требуются для всех листьев дерева - оп-
ределяется их тип, а в в поле trval заносится их значение (но-
мер метки строки, ссылка в таблицу символов для имен). Проверя-
ется, что используемая в выражении переменная описана.
Для операций сложения и вычитания отдельно обрабатываются
случаи (указатель +- целое) и (указатель-указатель). Для ука-
зателей на целое в дерево вставляется операция сдвига, реали-
зующая умножение/деление на 2 (размер целой переменной в бай-
тах).
Специальные действия требуются также и для унарных операций
& и *, преобразующих <тип> в указатель на <тип> и наоборот.
Запрещение применения операции & к указателю позволяет обойтись
конечным числом типов для промежуточных результатов.
Упражнения:
1. Добавьте в компилятор вычисление простейших константных
выражений: "а=2+2;" должно компилироваться в "mov $4,a".
2. Введите в язык унарные операции "!" и "~".
3. Добавьте в язык операцию ",".
4. Добавьте в язык операцию ? :.
5. Добавьте в язык операцию sizeof( тип )
sizeof( переменная )
6. Добавьте в язык операции || и &&.
Генератор кода (файл expr.c)
Имеется несколько функций, генерирующих код для выражения,
заданного деревом, указатель на которое передается им в ка-
честве аргумента:
aeval - поместить результат выражения в r0 ( RETURN e CM )
eeval - результат не используется ( е CM )
leval - результат в кодах в CC. ( if( e ) ... )
После небольшого изменения корня дерева каждая из этих функций
обращается к общей функции geval.
Перед непосредственной генерацией кода функция pregen опре-
деляет количество регистров, необходимое для вычисления каждого
поддерева. Предполагается, что все промежуточные результаты
хранятся в регистрах. Такая разметка дерева поможет затем поро-
дить более оптимальный по число используемых регистров код, ис-
пользуя весьма простую идею, известную как алгоритм Сети-Ульма-
на. Он заключается в том, что при вычислении выражения, задан-
ного деревом, следует вначале вычислять более дорогое поддере-
во.
Функция pregen вычисляет стоимость каждого поддерева обходя
дерево снизу вверх. Это число, помещаемое в поле trcost каждого
узла, является функцией от самого узла и стоимостей его прямых
потомков. Для упрощения функции pregen (так же как и в функции
функции tree) используется вектор trops, индексируемый кодом
операции. Биты, выделяемые маской CMSK, задают одну из 8
функций, встречающихся для различных операций. Естественно, не-
которые операции не подходят ни под одно из этих правил. Такие
операцие помечены битом CSPC и обрабатываются отдельно.
Генерация кода для выражения осуществляется в функции gen,
также в процессе обхода дерева снизу вверх. Вместе с генерацией
кода для узла дерева, функция gen заносит в поля trmode и trreg
местоположение результата операции. В зависимости от значения
trmode результат операции находится:
REG - в регистре trreg
IREG - в памяти косвенно по адресу в регистре trreg
IMMED - непосредственное значение, описываемое полем trval
MEM - в памяти по адресу, задаваемым полем trval
LMEM - на стеке,смещение относительно fp определяется trval
IMEM - то же, что и MEM, плюс еще одна косвенность
ILMEM - то же, что и LMEM, плюс еще одна косвенность
CC - в кодах условия, trreg содержит индекс команды ус-
ловного перехода для проверки: ne eq ge gt le lt
his hi los lo
Некоторые биты из поля trtag, используются для генерации ко-
да:
NOUSE - значение, вырабатываемое операцией, не используется;
в случаях "a=b; f(); i++; i--;" можно порождать более эффектив-
ный код, чем в случаях "c=a=b; c=f(); c=i++; c=i--;". Для опе-
раций сравнения этот бит означает, что результат операции дол-
жен быть оставлен в кодах условий, а не преобразован в целое
число, равное 0 или 1.
TUNSIGN - операнды операции сравнения - беззнаковые числа,
иначе они рассматриваются как целые со знаком. Этим битом также
помечена операция сдвига для масштабирования результата вычита-
ния двух целых указателей.
Содержимое поля trval определяется комбинацией следующих
двух битов:
TNAME - trval.n указывает на элемент таблицы символов,
TSTRING - trval.i содержит номер метки строчной константы,
иначе (оба бита равны нулю) trval.i - содержит значение це-
лой константы.
Перед генерацией кода данной операции, порождается код для
ее левого и правого операндов, рекурсивно вызывая функцию gen.
(Вначале порождается код для более сложного поддерева). В ре-
зультате порожденного кода будут вычислены операнды, а информа-
ция о том, где они находятся, будет занесена в соответствующие
им узлы дерева. Собственно генерация кода выполняется интерпре-
татором - функцией o. Аргумент этой функции - текстовая строка,
содержащая как обычные символы, так и интерпретируемые команды
- они закодированы большими латинскими буквами. Обычные символы
просто копируются в выходной файл, начиная с новой строки и та-
булятора при каждом вызове интерпретатора. С каждой командой
связано определенное действие интерпретатора, например, подста-
новка вместо него текстового представления аргумента. Такой
прием позволяет сократить объем кодогенератора и сделать его
более понятным по сравнению с разбором всех частных случаев ге-
нерации кода с помощью многочисленных if и else.
Для вычисления многих операций и хранения промежуточных ре-
зультатов используются регистры общего назначения r0-r4, ре-
гистр r5 используется в качестве указателя кадра стека. Инфор-
мация о незанятых регистрах хранится в массиве regs. Если ре-
гистр i свободен, то regs[i] содержит NULL. Для получения сво-
бодного регистра служит функция regalloc, для освобождения -
regfree. Для получения для команды MUL нечетного регистра, а
для команды DIV - пары регистров, служит переменная rreq. Ре-
гистр, используемый для хранения промежуточного результата, ос-
вобождается при использовании этого результата, если его новое
содержимое не является результатом выполняемой операции. Если
выражение оказалось слишком сложным и для промежуточных резуль-
татов не хватило регистров, то кодогенератор выдают отказ. Так
как регистры r0 и r1 не сохраняются при вызове функции, при вы-
делении регистра отдается предпочтение регистру с большим номе-
ром.
Упражнения:
1. Выражения "a>0" и "а=0" компилируются в команды "cmp a,
$0" и "mov $0, a" соответственно. Сделайте так, чтобы в этом
случае генерились более короткие и быстрые команды "tst a" и
"clr a" соответсвенно.
2. Используйте для увеличения/уменьшения операнда на 1 ко-
манды inc, dec.
3. Операция ip++ для целого указателя компилируется в две
команды "inc ip". Сделайте код для этого случая более опти-
мальным.
4. Устраните лишнюю операцию пересылки в коде для "return
a+1" - "mov a, r4; add $1, r4; mov r4, r0"
5. Обеспечьте генерацию кода для выражения любой сложности.
Один из способов: при отсутствии свободного регистра освободите
один (или несколько) регистров, занятых промежуточными резуль-
татами, сохранив их значения в стеке. Когда сохраненные в стеке
результаты потребуются, их можно будет возвратить обратно в ре-
гистры или использовать непосредственно в команде с режимом ад-
ресации (sp)+. Для правильной работы этого алгоритма следует
первыми сохранять результаты, находящиеся ближе к корню дерева.
6. Обеспечьте более эффективный код при обращению к масси-
вам: "a[1]=i" может быть скомпилировано в "mov i, a+2", если a
описан как статический массив целых.
Запускач и средства отладки (tinyc.c и debug.c)
В rt-11 компилятор запускается так:
run tc
argv: [-s] [-t] [filnam]
Ключи вызывают вывод на терминал отладочных печатей: s - со-
держимого локальной таблицы символов по окончанию каждой
функции и глобальной таблицы символов в конце работы; t - пе-
чать дерева для каждого выражения. Если входной файл имеет рас-
ширение .C, то его можно не указывать. Выходной файл имеет то
же имя, что и входной, но расширение .S. Если входной файл не
указан, то исходная программа будет вводится из stdin, а ре-
зультат компиляции выводится на stdout.
Русско-английский бестолковый словарик
К сожалению, большинство компиляторов не допускает кириллицы
в именах переменных, поэтому в качестве имен переменных и
констант использованы идентификаторы с англоязычной мнемоникой.
Здесь сделана попытка расшифровать некоторые из них.
addname
addstr
aeval
AND /* & */
ASG /* = */
BREAK /* break */
C0 /* 0 */
C00 /* CL==0 && CR==0 ? 0 : CSU */
C01 /* CL==0 && CR==1 ? 2 : CSU */
C10 /* CL==1 && CR==0 ? 2 : CSU */
CC /* cc */
CCMP /* Операции сравнения */
ccs
CDIV /* Для div и mod */
CHAR
chkgarb
CL
closelocal
CM /* ; */
CMAX /* max( CL, CR ) */
CMSK
COM
CONTINUE/* continue */
cpl
CR
CSPC /* Требуется отдельная обработка */
CSU /* CL==CR ? CL+1 : max( CL, CR ) */
CSU2 /* max( CSU, 2 ) */
cv
data_def
dcl
dcldim
dclfnct
dclprm
dcls
dcltype
dclvar
DEBUG При определении этого символа в текст компилятора
включаются отладочные средства.
debugs
debugt
DECR
DEF1
DEF2
def
defenter
defhdr
deflookup
DEFMAX Размер hash-таблицы для #define
defname
defs
deref
dhash
DIGIT
dim
DIV
DIVOP /* DIV MOD */
dnd
dnname
dnnext
dnval
e
ea
eeval
efnct
elist
slist2
ELSE /* else */
EQ
EQUOP /* EQ NE */
ERRMAX Прекращение работы после ERRMAX ошибок
error
esize
FCALL
fatal
filnam
fnct_def
free
GE
gen
geval
GT
i2oct
ICON /* Целое 123, 'а' */
ICOP /* ICR DECR */
ICR
IDENT
IF /* if */
ifelh
ifh
ILL
IMEM /* *name */
IMMED /* &name */
ILMEM /* *name(fp) */
IREG /* (reg) */
INT
LB /* [ */
LC /* { */
ldefs
LE
LETTER
leval
LMEM /* name(fp) */
LOAD
loadreg
loclab
locptr
LP /* ( */
LS
LT
malloc
MEM /* name */
MINUS /* - */
MOD
MUL /* * */
NAME /* Имя */
nameenter
NAMLEN Значимы только первые NAMLEN символов
NE
nerr
nest
newlab
NOLETTER
NREGS
ntags
NUMBER
o
obra
obxx
OCMP /* Если надо, то беззнак. сравнение */
OINT /* Результат - целое */
olab
OLI /* Левый аргумент - не указатель */
OLV /* Левый аргумент - значение */
oparam
openlocal
oprolog
OR /* | */
ORI /* Правый аргумент - не указатель */
ORV /* Правый аргумент - значение */
OSPC /* Требуется специальная обработка */
ot
pars
pars1
parser.c
parser.h
parser.y
pdefs
PLUS /* + */
PREDECR
PREFIX
pregen
PREICR
ref
REG /* reg */
regalloc
regfree
regs
retlab
RB /* ] */
RC /* } */
RELOP /* LT LE GT GE */
RETURN /* return */
RP /* ) */
rreq
RRORD
RRODD
RRPAIR
RS
S
SAUTO Смещение первой локальной переменной
scaner.c
scaner.h
scaner.l
SHIFTOP /* LS RS */
SM /* ; */
SPARAM Смещение параметров относительно fp
STACHAR /* массив символов */
STAINT /* массив целых */
stb
stbhdr
stbloc
STCHAR /* символ */
stdio.h
stinit
STINT /* целое */
STFUNC /* функция, возвращающая целое */
STLOCAL /* локальная (auto) переменная */
stlonly
STMASK /* маска для выделения типа */
stmt
stmts
stname
stnext
stogbl
STPARAM /* не описанный явно форм. параметр */
STPCHAR /* указатель на символ */
STPINT /* указатель на целое */
STR
stradd
strbuf
strcmp
strcpy
strend
strenter
streq
STRING /* Строка "abc" */
STRMAX Максимальная длина строки или #define
strptr
stsize
sttype
STUNDEF /* не определено */
term
TEST
TCHAR /* Char (Int otherwise) */
tinyc.h
TLVAL /* Lvalue (Value otherwise) */
TNAME /* Значение - имя */
TNOUSE /* Результат операции не используется*/
tone
TPTR /* Pointer (Variable otherwise) */
tralloc
trcost
tre
trebuf
tree
trefre
TREMAX Макс. число узлов в дереве выражений
trfree
tright
trival
trleft
trmode
trnval
trop
trops[]; /* Индексируется кодом операции */
trreg
trtag
trval
TSTRING /* Значение - строка */
TUNSIGN /* Сравнение беззнаковое */
TYPE /* INT CHAR */
UMINUS
UAND
UMUL
UNARY
WHILE /* while */
WHISP
WHISP1
WMAX Максимальная вложенность while
wptr
wstack
XOR /* ^ */
yyerror
yyin
yylineno
yylval
yyout
YYSTYPE
yytext
yywrap
Литература
1. Ron Cain. A Small C compiler for the 8080's. Dr. Dobbs
Journal, April-May,1981.
2. Р.Берри, Б.Микинз. Язык СИ: Введение для программистов. -
М.:Финансы и статистика,1988.
3. Б.Керниган, Д.Ритчи. Язык программирования Си. - М.:Фи-
нансы и статистика, 1985.
4. UNIX: PCC, LEX, YACC
5. Decus C
6. Д.Хендрикс. Компилятор языка Си для микроЭВМ. М.:Радио и
связь, 1989.