Язык программирования Си Брайан Керниган, Деннис Ритчи 3е издание Версия 1 Table of Contents
 Скачать 2.33 Mb.
|
Упражнение 6.2. Напишите программу, которая читает текст Си-программы и печатает в алфавитном порядке все группы имен переменных, в которых совпадают первые 6 символов, но последующие в чем-то различаются. Не обрабатывайте внутренности закавыченных строк и комментариев. Число 6 сделайте параметром, задаваемым в командной строке. в таблице и возвращающая указатель на место, где имя s было найдено, или NULL , если s в таблице не оказалось. Алгоритм основан на хэш-поиске: поступающее имя свертывается в неотрицательное число (хэш-код), которое затем используется в качестве индекса в массиве указателей. Каждый элемент этого массива является указателем на начало связанного списка блоков, описывающих имена с данным хэш-кодом. Если элемент массива равен NULL , это значит, что имен с соответствующим хэш-кодом нет. Блок в списке — это структура, содержащая указатели на имя, на замещающий текст и на следующий блок в списке; значение NULL в указателе на следующий блок означает конец списка. struct nlist { /* элемент таблицы */ struct nlist *next; /* указатель на следующий элемент */ char *name; /* определенное имя */ char *defn; /* замещающий текст */ }; А вот как записывается определение массива указателей: #define HASHSIZE 101 static struct nlist *hashtab[HASHSIZE]; /* таблица указателей */ Функция хэширования, используемая в lookup и install , суммирует коды символов в строке и в качестве результата выдает остаток от деления полученной суммы на размер массива указателей. Это не самая лучшая функция хэширования, но достаточно лаконичная и эффективная. /* hash: получает хэш-код для строки s */ unsigned hash(char *s) { unsigned hashval; for (hashval = 0; *s != '\0'; s++) hashval = *s + 31 * hashval; return hashval % HASHSIZE; } Беззнаковая арифметика гарантирует, что хэш-код будет неотрицательным. Хэширование порождает стартовый индекс для массива hashtab ; если соответствующая строка в таблице есть, она может быть обнаружена только в списке блоков, на начало которого указывает элемент массива hashtab с этим индексом. Поиск осуществляется с помощью lookup . Если lookup находит элемент с заданной строкой, то возвращает указатель на нее, если не находит, то возвращает NULL /* lookup: ищет s */ struct nlist *lookup(char *s) { struct nlist *np; } В for -цикле функции lookup для просмотра списка используется стандартная конструкция for (ptr = head; ptr != NULL; ptr = ptr->next) Функция install обращается к lookup , чтобы определить, имеется ли уже вставляемое имя. Если это так, то старое определение будет заменено новым. В противном случае будет образован новый элемент. Если запрос памяти для нового элемента не может быть удовлетворен, функция install выдает NULL struct nlist *lookup(char *); char *strdup(char *); /* install: заносит имя и текст (name, defn) в таблицу */ struct nlist *install(char *name, char *defn) { struct nlist *np; unsigned hashval; if ((np = lookup(name)) == NULL) { /* не найден */ np = (struct nlist *) malloc(sizeof(*np)); if (np == NULL || (np->name = strdup(name)) == NULL) return NULL; hashval = hash(name); np->next = hashtab[hashval]; hashtab[hashval] = np; } else /* уже имеется */ free((void *) np->defn); /* освобождаем прежний defn */ if ((np->defn = strdup(defn)) == NULL) return NULL; return np; } Упражнение 6.5. Напишите функцию undef , удаляющую имя и определение из таблицы, организация которой поддерживается функциями lookup и install Упражнение 6.6. Реализуйте простую версию #define -процессора (без аргументов), которая использовала бы программы этого параграфа и годилась бы для Си-программ. Вам могут помочь программы getch и ungetch 6.7. Средство typedef Язык Си предоставляет средство, называемое typedef , которое позволяет давать типам данных новые имена. Например, объявление typedef int Length; делает имя Length синонимом int . С этого момента тип Length можно применять в объявлениях, в операторе приведения и т. д. точно так же, как тип int : Length len, maxlen; Length *lengths[]; } u; } symtab[NSYM]; к ival обращаются следующим образом: symtab[i].u.ival а к первому символу строки sval можно обратиться любым из следующих двух способов: *symtab[i].u.sval symtab[i].u.sval[0] Фактически объединение — это структура, все элементы которой имеют нулевое смещение относительно ее базового адреса и размер которой позволяет поместиться в ней самому большому ее элементу, а выравнивание этой структуры удовлетворяет всем типам объединения. Операции, применимые к структурам, годятся и для объединений, т. е. законны присваивание объединения и копирование его как единого целого, взятие адреса от объединения и доступ к отдельным его элементам. Инициализировать объединение можно только значением, имеющим тип его первого элемента; таким образом, упомянутую выше переменную u можно инициализировать лишь значением типа int В главе 8 (на примере программы, заведующей выделением памяти) мы покажем, как, применяя объединение, можно добиться, чтобы расположение переменной было выровнено по соответствующей границе в памяти. 6.9. Битовые поля При дефиците памяти может возникнуть необходимость запаковать несколько объектов в одно слово машины. Одна из обычных ситуаций, встречающаяся в задачах обработки таблиц символов для компиляторов, — это объединение групп однобитовых флажков. Форматы некоторых данных могут от нас вообще не зависеть и диктоваться, например, интерфейсами с аппаратурой внешних устройств; здесь также возникает потребность адресоваться к частям слова. Вообразим себе фрагмент компилятора, который заведует таблицей символов. Каждый идентификатор программы имеет некоторую связанную с ним информацию: например, представляет ли он собой ключевое слово и, если это переменная, к какому классу принадлежит: внешняя и/или статическая и т. д. Самый компактный способ кодирования такой информации — расположить однобитовые флажки в одном слове типа char или int Один из распространенных приемов работы с битами основан на определении набора "масок", соответствующих позициям этих битов, как, например, в #define KEYWORD 01 /* ключевое слово */ #define EXTERNAL 02 /* внешний */ #define STATIC 04 /* статический */ или в Числа должны быть степенями двойки. Тогда доступ к битам становится делом "побитовых операций", описанных в главе 2 (сдвиг, маскирование, взятие дополнения). Некоторые виды записи выражений встречаются довольно часто. Так, flags |= EXTERNAL | STATIC; устанавливает 1 в соответствующих битах переменной flags, flags &= (EXTERNAL | STATIC); обнуляет их, а if ((flags & (EXTERNAL | STATIC)) ==0) ... оценивает условие как истинное, если оба бита нулевые. Хотя научиться писать такого рода выражения не составляет труда, вместо побитовых логических операций можно пользоваться предоставляемым Си другим способом прямого определения и доступа к полям внутри слова. Битовое поле (или для краткости просто поле) — это некоторое множество битов, лежащих рядом внутри одной, зависящей от реализации единицы памяти, которую мы будем называть "словом". Синтаксис определения полей и доступа к ним базируется на синтаксисе структур. Например, строки #define , фигурировавшие выше при задании таблицы символов, можно заменить на определение трех полей: struct { unsigned int is_keyword : 1; unsigned int is_extern : 1; unsigned int is_static : 1; } flags; Эта запись определяет переменную flags , которая содержит три однобитовых поля. Число, следующее за двоеточием, задает ширину поля. Поля объявлены как unsigned int , чтобы они воспринимались как беззнаковые величины. На отдельные поля ссылаются так же, как и на элементы обычных структур: flags.is_keyword , flags.is_extern и т.д. Поля "ведут себя" как малые целые и могут участвовать в арифметических выражениях точно так же, как и другие целые. Таким образом, предыдущие примеры можно написать более естественно: flags.is_extern = flags.is_static = 1; устанавливает 1 в соответствующие биты; flags.is_extern = flags.is_static = 0; их обнуляет, а if (flags.is_extern == 0 && flags.is_static == 0) проверяет их. Почти все технические детали, касающиеся полей, в частности, возможность поля перейти границу слова, зависят от реализации. Поля могут не иметь имени; с помощью безымянного поля (задаваемого только двоеточием и шириной) организуется пропуск нужного количества разрядов. Особая ширина, равная нулю, используется, когда требуется выйти на границу следующего слова. отправляет символ c в стандартный вывод, под которым по умолчанию подразумевается экран. Функция putchar в качестве результата возвращает посланный символ или, в случае ошибки, EOF . To же и в отношении вывода: с помощью записи вида > имя-файла вывод можно перенаправить в файл. Например, если prog использует для вывода функцию putchar , то prog > outfile будет направлять стандартный вывод не на экран, а в outfile. А командная строка prog | anotherprog соединит стандартный вывод программы prog со стандартным вводом программы anotherprog Вывод, осуществляемый функцией printf , также отправляется в стандартный выходной поток. Вызовы putchar и printf могут как угодно чередоваться, при этом вывод будет формироваться в той последовательности, в которой происходили вызовы этих функций. Любой исходный Си-файл, использующий хотя бы одну функцию библиотеки ввода-вывода, должен содержать в себе строку #include < и > , это значит, что поиск заголовочного файла ведется в стандартном месте (например, в системе UNIX это обычно директорий /usr/include ). Многие программы читают только из одного входного потока и пишут только в один выходной поток. Для организации ввода-вывода таким программам вполне хватит функций getchar , putchar и printf , а для начального обучения уж точно достаточно ознакомления с этими функциями. В частности, перечисленных функций достаточно, когда требуется вывод одной программы соединить с вводом следующей. В качестве примера рассмотрим программу lower , переводящую свой ввод на нижний регистр: «include «include { int с; while ((с = getchar()) != EOF) putchar(tolower(c)); return 0; } Функция tolower определена в . Она переводит буквы верхнего регистра в буквы нижнего регистра, а остальные символы возвращает без изменений. Как мы уже упоминали, "функции" вроде getchar и putchar из библиотеки и функция tolower из библиотеки часто реализуются в виде макросов, чтобы исключить накладные расходы от вызова функции на каждый отдельный символ. В параграфе 8.5 мы покажем, как это делается. Независимо от того, как на той или иной машине реализованы функции библиотеки , использующие их программы могут ничего не знать о кодировке символов. |