Упражнение 7-7. Напишите процедуру, которая будет удалять имя и определение из таблицы, управляемой функциями lookup и install.
Упражнение 7-8. Разработайте простую, основанную на функциях этого раздела, версию процессора для обработки конструкций #define, пригодную для использования с «C»-программами. Вам могут также оказаться полезными функции getchar и ungetch.
Когда вопрос экономии памяти становится очень существенным, то может оказаться необходимым помещать в одно машинное слово несколько различных объектов; одно из особенно распространенных употреблений - набор однобитовых признаков в применениях, подобных символьным таблицам компилятора. внешне обусловленные форматы данных, такие как интерфейсы аппаратных средств также зачастую предполагают возможность получения слова по частям.
Представьте себе фрагмент компилятора, который работает с символьной таблицей. С каждым идентификатором программы связана определенная информация, например, является он или нет ключевым словом, является ли он или нет внешним и/или статическим и т.д. Самый компактный способ закодировать такую информацию – поместить набор однобитовых признаков в отдельную переменную типа char или int.
Обычный способ, которым это делается, состоит в определении набора «масок», отвечающих соответствущим битовым позициям, как в:
#define keyword 01
#define external 02
#define static 04
(числа должны быть степенями двойки). Тогда обработка битов сведется к «жонглированию битами» с помощью операций сдвига, маскирования и дополнения, описанных нами в главе 3.
Некоторые часто встречающиеся идиомы:
flags |= external | static;
включает биты external и static в flags, в то время как:
flags &= ~( external | static);
их выключает, а:
if ((flags & (external | static)) == 0) ...
истинно, если оба бита выключены.
Хотя этими идиомами легко овладеть, язык «C» в качестве альтернативы предлагает возможность определения и обработки полей внутри слова непосредственно, а не посредством побитовых логических операций. Поле – это набор смежных битов внутри одной переменной типа int. Синтаксис определения и обработки полей основывается на структурах. Например, символьную таблицу конструкций #define, приведенную выше, можно бы было заменить определением трех полей:
struct
{
unsigned is_keyword : 1;
unsigned is_extern : 1;
unsigned is_static : 1;
} flags;
Здесь определяется переменная с именем flags, которая содержит три однобитовых поля поля. Следующее за двоеточием число задает ширину поля в битах. Поля описаны как unsigned, чтобы подчеркнуть, что они действительно будут величинами без знака.
На отдельные поля можно ссылаться, как:
· flags.is_statie,
· flags.is_extern,
· flags.is_keyword
и т.д., то есть точно так же, как на другие члены структуры. Поля ведут себя подобно небольшим целым без знака и могут участвовать в арифметических выражениях точно так же, как и другие целые. Таким образом, предыдущие примеры более естественно переписать так:
· для включения битов
flags.is_extern = flags.is_static = 1;
· для выключения битов
flags.is_extern = flags.is_static = 0;
· для их проверки
if(flags.is_extern == 0 && flags.is_static == 0)...
Поле не может перекрывать границу int; если указанная ширина такова, что это должно случиться, то поле выравнивается по границе следующего int. Полям можно не присваивать имена; неименованные поля (только двоеточие и ширина) используются для заполнения свободного места. Чтобы вынудить выравнивание на границу следующего int, можно использовать специальную ширину 0.
При работе с полями имеется ряд моментов, на которые следует обратить внимание. По-видимому, наиболее существенным является то, что, отражая природу различных аппаратных средств, распределение полей на некоторых машинах осуществляется слева направо, а на некоторых справа налево. Это означает, что хотя поля очень полезны для работы с внутренне определенными структурами данных, при разделении внешне определяемых данных следует тщательно рассматривать вопрос о том, какой конец поступает первым.
Другие ограничения, которые следует иметь в виду: поля не имеют знака; они могут храниться только в переменных типа int (или, что эквивалентно, типа unsigned); они не являются массивами; они не имеют адресов, так что к ним не применима операция &.
Объединение – это переменная, которая в различные моменты времени может содержать объекты разных типов и размеров, причем компилятор берет на себя отслеживание размера и требований выравнивания. Объединения предоставляют возможность работать с различными видами данных в одной области памяти, не вводя в программу никакой машинно-зависимой информации.
В качестве примера, снова из символьной таблицы компилятора, предположим, что константы могут быть типа int, float или быть указателями на символы. значение каждой конкретной константы должно храниться в переменной соответствующего типа, но все же для управления таблицей самым удобным было бы, если это значение занимало бы один и тот же объем памяти и хранилось в том же самом месте независимо от его типа. Это и является назначением объединения – выделить отдельную переменную, в которой можно законно хранить любую одну из переменных нескольких типов. Как и в случае полей, синтаксис основывается на структурах:
union u_tag
{
int ival;
float fval;
char *pval;
} uval;
Переменная uval будет иметь достаточно большой размер, чтобы хранить наибольший из трех типов, независимо от машины, на которой осуществляется компиляция, – программа не будет зависеть от характеристик аппаратных средств. Любой из этих трех типов может быть присвоен uval и затем использован в выражениях, пока такое использование совместимо: извлекаемый тип должен совпадать с последним помещенным типом. Дело программиста – следить за тем, какой тип хранится в объединении в данный момент; если что-либо хранится как один тип, а извлекается как другой, то результаты будут зависеть от используемой машины.
Синтаксически доступ к элементам (членам) объединения осуществляется следующим образом:
· Имя_объединения.элемент ,
· Указатель_объединения->элемент ,
то есть точно так же, как и в случае структур. Если для отслеживания типа, хранимого в данный момент в uval, используется переменная utype, то можно встретить такой участок программы:
if (utype == int)
printf("%d\n", uval.ival);
else if (utype == float)
printf("%f\n", uval.fval);
else if (utype == string)
printf("%s\n", uval.pval);
else
printf("bad type %d in utype\n", utype);
Объединения могут появляться внутри структур и массивов и наоборот. Запись для обращения к члену объединения в структуре (или наоборот) совершенно идентична той, которая используется во вложенных структурах. Например, в массиве структур, определенным следующим образом:
struct
{
char *name;
int flags;
int utype;
union
{
int ival;
float fval;
char *pval;
} uval;
} symtab[nsym];
на переменную ival можно сослаться как:
symtab[i].uval.ival ,
а на первый символ строки pval как
*symtab[i].uval.pval .
В сущности объединение является структурой, в которой все элементы имеют нулевое смещение. Сама структура достаточно велика, чтобы хранить «самый широкий» элемент, и выравнивание пригодно для всех типов, входящих в объединение.
Как и в случае структур, единственными операциями, которые в настоящее время можно проводить с объединениями, являются доступ к элементу и извлечение адреса; объединения не могут быть присвоены, переданы функциям или возвращены ими. Указатели объединений можно использовать в точно такой же манере, как и указатели структур.
7.9. Определение «нового» типа данных
В языке «C» предусмотрена возможность, называемая typedef, для введения новых имен для типов данных. Например, описание:
typedef int length;
делает имя length синонимом для int. «Тип» length может быть использован в описаниях, переводов типов и т.д. Точно таким же образом, как и тип int:
length len, maxlen;
length *lengths[];
Аналогично описанию:
typedef char *string;
делает string синонимом для char*, то есть для указателя на символы, что затем можно использовать в описаниях вида:
string p, lineptr[lines], alloc();
Обратите внимание, что объявляемый в конструкции typedef тип появляется в позиции имени переменной, а не сразу за словом typedef. Синтаксически конструкция typedef подобна описаниям класса памяти extern, static и т. Д. мы также использовали прописные буквы, чтобы яснее выделить имена.
В качестве более сложного примера мы используем конструкцию typedef для описания узлов дерева, рассмотренных ранее в этой главе:
typedef struct tnode // Узел дерева
{
char *word; // Указатель на текст
int count; // Число вхождений
struct tnode *left; // Левый «сын»
struct tnode *right; // Правый «сын»
} treenode, *treeptr;
В результате получаем два новых ключевых слова: treenode (структура) и treeptr (указатель на структуру). Тогда функцию talloc можно записать в виде:
treeptr talloc()
{
char *alloc();
return((treeptr) alloc(sizeof(treenode)));
}
Необходимо подчеркнуть, что описание typedef не приводит к созданию нового в каком-либо смысле типа; оно только добавляет новое имя для некоторого существующего типа. При этом не возникает и никакой новой семантики: описанные таким способом переменные обладают точно теми же свойствами, что и переменные, описанные явным образом. По существу конструкция typedef сходна с #define за исключением того, что она интерпретируется компилятором и потому может осуществлять подстановки текста, которые выходят за пределы возможностей макропроцессора языка «C». Например,
typedef int (*pfi) ();
создает тип pfi для «указателя функции, возвращающей значение типа int», который затем можно было бы использовать в программе сортировки из главы 6 в контексте вида:
pfi strcmp, numcmp, swap;
Имеются две основные причины применения описаний typedef. Первая причина связана с параметризацией программы, чтобы облегчить решение проблемы переносимости. Если для типов данных, которые могут быть машинно-зависимыми, использовать описание typedef, то при переносе программы на другую машину придется изменить только эти описания. Одна из типичных ситуаций состоит в использовании определяемых с помощью typedef имен для различных целых величин и в последующем подходящем выборе типов short, int и long для каждой имеющейся машины. Второе назначение typedef состоит в обеспечении лучшей документации для программы – тип с именем treeptr может оказаться более удобным для восприятия, чем тип, который описан только как указатель сложной структуры. И, наконец, всегда существует вероятность, что в будущем компилятор или некоторая другая программа, такая как lint, сможет использовать содержащуюся в описаниях typedef информацию для проведения некоторой дополнительной проверки программы.