ла в байтах */ if( (fpnew = fopen( "inv.out", "w" ))== NULL ){ printf("Can not create file\n"); exit(3); } while( fgets( buffer, sizeof buffer, fp ) != NULL ){ lgt = strlen( buffer ); fseek(fpnew, len - lgt , 0); /* Помните, что смещение у lseek и fseek - * это число типа long, а не int. * Поэтому лучше всегда писать * lseek(fd, (long) off, whence); */ len -= lgt; fprintf( fpnew, "%s", buffer ); /* или лучше fputs(buffer, fpnew); */ } fclose( fp ); fclose( fpnew ); } 7.34. Напишите программу, которая читает файл, состоящий из "блоков" текста, разде- ленных пустыми строками. Размер "блока" ограничен. Программа готовит файл для печати на принтер так, чтобы ни один блок не разбивался на части: А. Богатырев, 1992-95 - 298 - Си в UNIX ----------- ----------- |###### A | |###### A | лист1 |#### A | превращать |#### A | |##### A | в |##### A | | | | | |###### B | | | ----------- ----------- |#### B | |###### B | лист2 | | |#### B | ... | | то есть если блок не умещается на остатке листа, он должен быть перенесен на следую- щий лист. Блоки следует разделять одной пустой строкой (но первая строка листа не должна быть пустой!). Если блок длиннее страницы - не переносите его. /* Решение задачи о переносе блоков текста, * если они не умещаются на остатке листа */ #include <stdio.h> #include <ctype.h> extern void *malloc(unsigned); extern int atoi(char *); FILE *fpin = stdin, *fpout = stdout; /* Спасти строку в динамически выделенной памяти */ char *strdup (const char *s) { char *ptr = (char *) malloc (strlen (s) + 1); if( ptr ) strcpy (ptr, s); return ptr; } int page_length = 66; /* длина страницы */ int current_line; /* текущая строка на странице (с нуля) */ int numbered = 0; /* нумеровать строки листа ? */ #define MAXLINES 256 /* макс. длина блока */ int stored = 0; /* запомнено строк */ char *lines[MAXLINES]; /* запомненные строки */ /* Запомнить строку блока в буфер строк */ void remember (char *s) { if (stored >= MAXLINES) { fprintf (stderr, "Слишком длинный блок.\n"); return; } else if((lines[stored++] = strdup (s)) == NULL ){ fprintf (stderr, "Мало памяти (Out of memory).\n"); exit(13); } } /* Переход на следующую страницу */ void newpage () { current_line = 0; putc('\f', fpout); } А. Богатырев, 1992-95 - 299 - Си в UNIX /* Перевод строки или листа */ void newline (void) { if (current_line == page_length - 1) newpage (); /* начать новый лист */ else { current_line++; if( numbered ) fprintf(fpout, "%02d\n", current_line); else putc ('\n', fpout); } } /* Переход на следующую страницу вставкой пустых строк */ void nextpage () { while (current_line != 0) newline (); } /* Выдать спасенный блок */ void throwout () { register i; for (i = 0; i < stored; i++) { if( numbered ) fprintf(fpout, "%02d %s", current_line, lines[i]); else fputs (lines[i], fpout); newline (); free (lines[i]); } stored = 0; } /* Выдать блок, перенося на следующий лист если надо */ void flush () { int rest_of_page = page_length - current_line; /* осталось пустых строк на странице */ if ((stored > page_length && rest_of_page < page_length / 4) || rest_of_page < stored) nextpage (); throwout (); if (current_line) /* не первая строка листа */ newline (); /* разделитель блоков */ } /* Обработать входной файл */ void process () { char buffer[512]; int l; while (fgets (buffer, sizeof buffer, fpin) != NULL) { if ((l = strlen (buffer)) && buffer[l - 1] == '\n') buffer[ --l] = '\0'; if (l) remember (buffer); /* а по пустой строке - выдать блок */ else if (stored) flush (); } if (stored) flush (); nextpage(); } А. Богатырев, 1992-95 - 300 - Си в UNIX void main (int argc, char *argv[]) { argc--; argv++; while (*argv) { if (**argv == '-') { char *key = *argv + 1, *arg; switch (*key) { case 'l': if (! key[1]) { if( argv[1] ){ arg = argv[1]; argv++; argc--; } else arg = ""; } else arg = key+1; if( isdigit(*arg) ){ page_length = atoi(arg); fprintf (stderr, "Длина страницы: %d строк\n", page_length); } else fprintf(stderr, "-l ЧИСЛО\n"); break; case 'n': numbered++; break; default: fprintf (stderr, "Неизвестный ключ %s\n", key); break; } } argv++; argc--; } process (); exit(0); } 7.35. Составьте программу вывода строк файла в инверсном отображении, причем порядок символов в строках также следует инвертировать. Например, abcdef ... oklmn 987654321 ..... превращать в ..... 123456789 nmlko ... fedcba Программа должна быть составлена двумя способами: при помощи обратного чтения файла и рекурсивным вызовом самой функции инвертирования. Указание: при обратном чтении надо читать файл большими кусками (блоками). 7.36. Напишите программу, читающую файл построчно и размещающую строки в отсортиро- ванное двоичное дерево. По концу файла - распечатайте это дерево. Указание: исполь- зуйте динамическую память и рекурсию. А. Богатырев, 1992-95 - 301 - Си в UNIX /* Двоичная сортировка строк при помощи дерева */ #include <stdio.h> char buf[240]; /* буфер ввода */ int lines; /* номер строки файла */ typedef struct node{ struct _data{ /* ДАННЫЕ */ char *key; /* ключ - строка */ int line; /* номер строки */ } data; /* СЛУЖЕБНАЯ ИНФОРМАЦИЯ */ struct node *l, /* левое поддерево */ *r; /* правое поддерево */ } Node; Node *root = NULL; /* корень дерева (ссылка на верхний узел) */ /* Отведение памяти и инициализация нового узла */ Node *newNode(s) char *s; /* строка */ { Node *tmp; extern char *malloc(); /* выделитель памяти */ tmp = (Node *) malloc(sizeof(Node)); if( tmp == NULL ){ fprintf( stderr, "Нет памяти.\n"); exit(1); } tmp -> l = tmp -> r = NULL; /* нет поддеревьев */ tmp -> data.line = lines; /* номер строки файла */ tmp -> data.key = malloc( strlen(s) + 1 ); /* +1 - под байт '\0' в конце строки */ strcpy(tmp -> data.key, s); /* копируем ключ в узел */ return tmp; } int i; /* Вынесено в статическую память, чтобы при каждом * рекурсивном вызове не создавалась новая auto-переменная, * а использовалась одна и та же статическая */ А. Богатырев, 1992-95 - 302 - Си в UNIX /* Рекурсивная печать дерева */ void printtree(root, tree, level, c) Node *root; /* корень дерева */ Node *tree; /* дерево */ int level; /* уровень */ char c; /* имя поддерева */ { if( root == NULL ){ printf("Дерево пусто.\n"); return; } if( tree == NULL ) return; /* если есть - распечатать левое поддерево */ printtree (root, tree -> l, level + 1, '/'); /* 'L' */ /* распечатать ключ узла */ for( i=0; i < level; i++ ) printf(" "); printf("%c%3d--\"%s\"\n", c, tree-> data.line, tree -> data.key); /* если есть - распечатать правое поддерево */ printtree(root, tree -> r, level + 1, '\\'); /* 'R' */ } void prTree(tree) Node *tree; { printtree(tree, tree, 0, '*'); } /* Добавить узел с ключом key в дерево tree */ void addnode(tree, key) Node **tree; /* в какое дерево добавлять: адрес переменной, * содержащей ссылку на корневой узел */ char *key; /* ключ узла */ { #define TREE (*tree) if( TREE == NULL ){ /* дерево пока пусто */ TREE = newNode( key ); return; } /* иначе есть хоть один узел */ if ( strcmp (key, TREE -> data.key) < 0 ) { /* добавить в левое поддерево */ if ( TREE -> l == NULL ){ /* нет левого дерева */ TREE -> l = newNode(key); return; } else addnode( & TREE ->l , key); } А. Богатырев, 1992-95 - 303 - Си в UNIX else{ /* добавить в правое дерево */ if ( TREE -> r == NULL ){ /* нет правого поддерева */ TREE -> r = newNode(key); return; } else addnode ( & TREE ->r, key) ; } } /* Процедура удаления из дерева по ключу. */ typedef struct node *NodePtr; static NodePtr delNode; /* удаляемая вершина */ void delete(key, tree) char *key; /* ключ удаляемого элемента */ NodePtr *tree; /* из какого дерева удалять */ { extern void doDelete(); if(*tree == NULL){ printf( "%s не найдено\n", key ); return; } /* поиск ключа */ else if(strcmp(key, (*tree)->data.key) < 0) delete( key, &(*tree)->l ); else if(strcmp(key, (*tree)->data.key) > 0) delete( key, &(*tree)->r ); else{ /* ключ найден */ delNode = *tree; /* указатель на удаляемый узел */ if(delNode->r == NULL) *tree = delNode->l; else if(delNode->l == NULL) *tree = delNode->r; else doDelete( & delNode->l ); free(delNode); } } static void doDelete(rt) NodePtr *rt; { if( (*rt)->r != NULL ) /* спуск по правой ветви */ doDelete( &(*rt)->r ); else{ /* перенос данных в другой узел */ delNode->data = (*rt)->data; delNode = *rt; /* для free() */ *rt = (*rt)->l; } } А. Богатырев, 1992-95 - 304 - Си в UNIX void main(){ extern char *gets(); char *s; while (gets(buf) != NULL){ /* пока не конец файла */ lines++; addnode( & root, buf ); } prTree(root); /* удалим строку */ freopen("/dev/tty", "r", stdin); do{ printf( "что удалить ? " ); if((s = gets(buf)) == NULL) break; delete(buf, &root); prTree( root ); } while( s && root ); printf("Bye-bye.\n"); exit(0); } 7.37. Напишите программу, которая читает со стандартного ввода 10 чисел либо слов, а затем распечатывает их. Для хранения введенных данных используйте объединение. #include <stdio.h> #include <ctype.h> #define INT 'i' #define STR 's' struct data { char tag; /* тэг, пометка. Код типа данных. */ union { int i; char *s; } value; } a[10]; int counter = 0; /* счетчик */ void main(){ char word[128]; int i; char *malloc(unsigned); /* Чтение: */ for(counter=0; counter < 10; counter++){ if( gets(word) == NULL ) break; if( isdigit((unsigned char) *word)){ a[counter].value.i = atoi(word); a[counter].tag = INT; } else { a[counter].value.s = malloc(strlen(word)+1); strcpy(a[counter].value.s, word); a[counter].tag = STR; } } /* Распечатка: */ for(i=0; i < counter; i++) switch(a[i].tag){ case INT: printf("число %d\n", a[i].value.i); break; case STR: printf("слово %s\n", a[i].value.s); free(a[i].value.s); break; } А. Богатырев, 1992-95 - 305 - Си в UNIX } 7.38. Рассмотрим задачу написания функции, которая обрабатывает переменное число аргументов, например функцию-генератор меню. В такую функцию надо подавать строки меню и адреса функций, вызываемых при выборе каждой из строк. Собственно проблема, которую мы тут обсуждаем - как передавать переменное число аргументов в подобные функции? Мы приведем три программы использующие три различных подхода. Предпочтение не отдано ни одному из них - каждый из них может оказаться эффективнее других в опре- деленных ситуациях. Думайте сами! 7.38.1. Массив /* Передача аргументов в функцию как МАССИВА. * Следует явно указать число аргументов в массиве. */ #include <stdio.h> /* printf(), NULL */ #include <string.h> /* strdup() */ #include <stdlib.h> /* malloc() */ #define A_INT 1 #define A_STR 2 #define A_NULL 0 typedef struct arg { int type; union jack { char *s; int d; } data; struct arg *next; } Arg; void doit(Arg args[], int n){ int i; for(i=0; i < n; i++) switch(args[i].type){ case A_INT: printf("%d", args[i].data.d); break; case A_STR: printf("%s", args[i].data.s); break; default: fprintf(stderr, "Unknown type!\n"); break; } } А. Богатырев, 1992-95 - 306 - Си в UNIX /* При инициализации union надо использовать тип * первого из перечисленных значений. */ Arg sample[] = { { A_INT, (char *) 123 }, { A_STR, (char *) " hello, " }, { A_INT, (char *) 456 }, { A_STR, (char *) " world\n" } }; int main(int ac, char *av[]){ doit(sample, sizeof sample / sizeof sample[0]); return 0; } 7.38.2. Список /* Передача аргументов в функцию как СПИСКА. * Достоинство: список можно модифицировать * во время выполнения программы: добавлять и * удалять элементы. Недостаток тот же: список надо * построить динамически во время выполнения, * заранее этого сделать нельзя. * Недостатком данной программы является также то, * что список не уничтожается после использования. * В C++ эта проблема решается при помощи использования * автоматически вызываемых деструкторов. */ #include <stdio.h> /* printf(), NULL */ #include <string.h> /* strdup() */ #include <stdlib.h> /* malloc() */ #define A_INT 1 #define A_STR 2 #define A_NULL 0 typedef struct arg { int type; union jack { char *s; int d; } data; struct arg *next; } Arg; А. Богатырев, 1992-95 - 307 - Си в UNIX void doit(Arg *arglist){ for( ; arglist; arglist=arglist->next) switch(arglist->type){ case A_INT: printf("%d", arglist->data.d); break; case A_STR: printf("%s", arglist->data.s); break; default: fprintf(stderr, "Unknown type!\n"); break; } } Arg *new_int(int n, Arg *next){ Arg *ptr = (Arg *) malloc(sizeof(Arg)); ptr->type = A_INT; ptr->data.d = n; ptr->next = next; return ptr; } Arg *new_str(char *s, Arg *next){ Arg *ptr = (Arg *) malloc(sizeof(Arg)); ptr->type = A_STR; ptr->data.s = strdup(s); ptr->next = next; return ptr; } int main(int ac, char *av[]){ doit( new_int(123, new_str(" hello, ", new_int(456, new_str(" world\n", NULL)))) ); return 0; } 7.38.3. Функция с переменным числом параметров /* Передача аргументов в функцию как СПИСКА АРГУМЕНТОВ * ФУНКЦИИ с признаком конца списка. */ #include <stdio.h> /* printf(), NULL */ #include <stdarg.h> /* va_... */ #define A_INT 1 #define A_STR 2 #define A_NULL 0 А. Богатырев, 1992-95 - 308 - Си в UNIX void doit(...){ /* переменное число аргументов */ va_list args; /* второй параметр - аргумент, предшествующий ... * Если такого нет - ставим запятую и пустое место! */ va_start(args, ); for(;;){ switch(va_arg(args, int)){ case A_INT: printf("%d", va_arg(args, int)); break; case A_STR: printf("%s", va_arg(args, char *)); break; case A_NULL: goto breakloop; default: fprintf(stderr, "Unknown type!\n"); break; } } breakloop: va_end(args); } int main(int ac, char *av[]){ doit( A_INT, 123, A_STR, " hello, ", A_INT, 456, A_STR, " world\n", A_NULL ); return 0; } 7.39. Напишите несколько функций для работы с упрощенной базой данных. Запись в базе данных содержит ключ - целое, и строку фиксированной длины: struct data { int b_key; /* ключ */ char b_data[ DATALEN ]; /* информация */ }; Напишите: - добавление записи - уничтожение по ключу - поиск по ключу (и печать строки) - обновление по ключу. Файл организован как несортированный массив записей без дубликатов (т.е. ключи не могут повторяться). Поиск производить линейно. Используйте функции fread, fwrite, fseek. Последняя функция позволяет вам позиционироваться к n-ой записи файла: fseek( fp, (long) n * sizeof(struct data), 0 ); Перепишите эту программу, объявив ключ как строку, например А. Богатырев, 1992-95 - 309 - Си в UNIX char b_key[ KEYLEN ]; Если строка-ключ короче KEYLEN символов, она должна оканчиваться '\0', иначе - используются все KEYLEN букв и '\0' на конце отсутствует (так же устроено поле d_name в каталогах файловой системы). Усовершенствуйте алгоритм доступа, используя хеширо- вание по ключу (hash - перемешивание, см. пример в приложении). Вынесите ключи в отдельный файл. Этот файл ключей состоит из структур struct record_header { int b_key ; /* ключ */ long b_offset; /* адрес записи в файле данных */ int b_length; /* длина записи (необязательно) */ }; то есть организован аналогично нашей первой базе данных. Сначала вы ищете нужный ключ в файле ключей. Поле b_offset у найденного ключа задает адрес данного в другом файле. Чтобы прочитать его, надо сделать fseek на расстояние b_offset в файле данных и прочесть b_length байт. 7.40. Организуйте базу данных в файле как список записей. В каждой записи вместо ключа должен храниться номер очередной записи (ссылка). Напишите функции: поиска дан- ных в списке (по значению), добавления данных в список в алфавитном порядке, (они просто приписываются к концу файла, но в нужных местах переставляются ссылки), распе- чатки списка в порядке ссылок, удалению элементов из списка (из самого файла они не удаляются!). Ссылка (номер) первой записи (головы списка) хранится в первых двух байтах файла, рассматриваемых как short. Введите оптимизацию: напишите функцию для сортировки файла (превращению переме- шанного списка в линейный) и вычеркивания из него удаленных записей. При этом файл будет перезаписан. Если файл отсортирован, то поиск в нем можно производить более эффективно, чем прослеживание цепочки ссылок: просто линейным просмотром. Третий байт файла используйте как признак: 1 - файл был отсортирован, 0 - после сортировки в него было что-то добавлено и линейный порядок нарушен. 7.41. Напишите функцию match(строка,шаблон); для проверки соответствия строки упро- щенному регулярному выражению в стиле Шелл. Метасимволы шаблона: * - любое число любых символов (0 и более); ? - один любой символ. Усложнение: [буквы] - любая из перечисленных букв. [!буквы] - любая из букв, кроме перечисленных. [h-z] - любая из букв от h до z включительно. Указание: для проверки "остатка" строки используйте рекурсивный вызов этой же функ- ции. Используя эту функцию, напишите программу, которая выделяет из файла СЛОВА, удовлетворяющие заданному шаблону (например, "[Ии]*о*т"). Имеется в виду, что каждую строку надо сначала разбить на слова, а потом проверить каждое слово. А. Богатырев, 1992-95 - 310 - Си в UNIX #include <stdio.h> #include <string.h> #include <locale.h> #define U(c) ((c) & 0377) /* подавление расширения знака */ #define QUOT '\\' /* экранирующий символ */ #ifndef MATCH_ERR # define MATCH_ERR printf("Нет ]\n") #endif /* s - сопоставляемая строка * p - шаблон. Символ \ отменяет спецзначение метасимвола. */ int match (register char *s, register char *p) { register int scc; /* текущий символ строки */ int c, cc, lc; /* lc - предыдущий символ в [...] списке */ int ok, notflag; for (;;) { scc = U(*s++); /* очередной символ строки */ switch (c = U (*p++)) { /* очередной символ шаблона */ case QUOT: /* a*\*b */ c = U (*p++); if( c == 0 ) return(0); /* ошибка: pattern\ */ else goto def; case '[': /* любой символ из списка */ ok = notflag = 0; lc = 077777; /* достаточно большое число */ if(*p == '!'){ notflag=1; p++; } while (cc = U (*p++)) { if (cc == ']') { /* конец перечисления */ if (ok) break; /* сопоставилось */ return (0); /* не сопоставилось */ } if (cc == '-') { /* интервал символов */ if (notflag){ /* не из диапазона - OK */ if (!syinsy (lc, scc, U (*p++))) ok++; /* из диапазона - неудача */ else return (0); } else { /* символ из диапазона - OK */ if (syinsy (lc, scc, U (*p++))) ok++; } } else { if (cc == QUOT){ /* [\[\]] */ cc = U(*p++); if(!cc) return(0);/* ошибка */ } if (notflag){ if (scc && scc != (lc = cc)) ok++; /* не входит в список */ else return (0); } else { А. Богатырев, 1992-95 - 311 - Си в UNIX if (scc == (lc = cc)) /* входит в список */ ok++; } } } if (cc == 0){ /* конец строки */ MATCH_ERR; return (0); /* ошибка */ } continue; case '*': /* любое число любых символов */ if (!*p) return (1); for (s--; *s; s++) if (match (s, p)) return (1); return (0); case 0: return (scc == 0); default: def: if (c != scc) return (0); continue; case '?': /* один любой символ */ if (scc == 0) return (0); continue; } } } /* Проверить, что smy лежит между smax и smin */ int syinsy (unsigned smin, unsigned smy, unsigned smax) { char left [2]; char right [2]; char middle [2]; left [0] = smin; left [1] = '\0'; right [0] = smax; right [1] = '\0'; middle[0] = smy; middle[1] = '\0'; return (strcoll(left, middle) <= 0 && strcoll(middle, right) <= 0); } Обратите внимание на то, что в UNIX расширением шаблонов имен файлов, вроде *.c, занимается не операционная система (как в MS DOS), а программа-интерпретатор команд пользователя (shell: /bin/sh, /bin/csh, /bin/ksh). Это позволяет обрабатывать (в принципе) разные стили шаблонов имен. 7.42. Изучите раздел руководства man regexp и include-файл /usr/include/regexp.h, содержащий исходные тексты функций compile и step для регулярного выражения в стиле программ ed, lex, grep: одна буква C или заэкранированный спецсимвол \. \[ \* \$ \^ \\ означают сами себя; А. Богатырев, 1992-95 - 312 - Си в UNIX . означает один любой символ кроме \n; [abc] или [a-b] означает любой символ из перечисленных (из интервала); [abc-] минус в конце означает сам символ -; []abc] внутри [] скобка ] на первом месте означает сама себя; [^a-z] крышка ^ означает отрицание, т.е. любой символ кроме перечисленных; [a-z^] крышка не на первом месте означает сама себя; [\*.] спецсимволы внутри [] не несут специального значения, а представляют сами себя; C* любое (0 и более) число символов C; .* любое число любых символов; выражение* любое число (0 и более) повторений выражения, например [0-9]* означает число (последовательность цифр) или пустое место. Ищется самое длинное прижатое влево подвыражение; выражение\{n,m\} повторение выражения от n до m раз (включительно), где числа не превосходят 255; выражение\{n,\} повторение по крайней мере n раз, например [0-9]\{1,\} означает число; выражение\{n\} повторение ровно n раз; выражение$ строка, чей конец удовлетворяет выражению, например .*define.*\\$ ^выражение строка, чье начало удовлетворяет выражению; \n символ перевода строки; \(.....\) сегмент. Сопоставившаяся с ним подстрока будет запомнена; \N где N цифра. Данный участок образца должен совпадать с N-ым сегментом (нумерация с 1). Напишите функцию matchReg, использующую этот стиль регулярных выражений. Сохраняйте шаблон, при вызове matchReg сравнивайте старый шаблон с новым. Перекомпиляцию следует производить только если шаблон изменился: #include <stdio.h> #include <ctype.h> #define INIT register char *sp = instring; #define GETC() (*sp++) #define PEEKC() (*sp) #define UNGETC(c) (--sp) #define RETURN(ptr) return #define ERROR(code) \ {fprintf(stderr,"%s:ERR%d\n",instring,code);exit(177);} # include <regexp.h> #define EOL '\0' /* end of line */ #define ESIZE 512 int matchReg(char *str, char *pattern){ static char oldPattern[256]; static char compiledExpr[ESIZE]; if( strcmp(pattern, oldPattern)){ /* различны */ /* compile regular expression */ compile(pattern, compiledExpr, &compiledExpr[ESIZE], EOL); А. Богатырев, 1992-95 - 313 - Си в UNIX strcpy(oldPattern, pattern); /* запомнить */ } return step(str, compiledExpr); /* сопоставить */ } /* Пример вызова: reg '^int' 'int$' char | less */ /* reg 'putchar.*(.*)' < reg.c | more */ void main(int ac, char **av){ char inputline[BUFSIZ]; register i; while(gets(inputline)){ for(i=1; i < ac; i++) if(matchReg(inputline, av[i])){ char *p; extern char *loc1, *loc2; /*printf("%s\n", inputline);*/ /* Напечатать строку, * выделяя сопоставившуюся часть жирно */ for(p=inputline; p != loc1; p++) putchar(*p); for( ; p != loc2; p++) if(isspace((unsigned char) *p)) putchar(*p); else printf("%c\b%c", *p, *p); for( ; *p; p++) putchar(*p); putchar('\n'); break; } } } 7.43. Используя <regexp.h> напишите программу, производящую контекстную замену во всех строках файла. Если строка не удовлетворяет регулярному выражению - она остается неизменной. Примеры вызова: $ regsub '\([0-9]\{1,\}\)' '(\1)' $ regsub 'f(\(.*\),\(.*\))' 'f(\2,\1)' < file Вторая команда должна заменять все вхождения f(a,b) на f(b,a). Выражение, обозначен- ное в образце как \(...\), подставляется на место соответствующей конструкции \N во втором аргументе, где N - цифра, номер сегмента. Чтобы поместить в выход сам символ \, его надо удваивать: \\. А. Богатырев, 1992-95 - 314 - Си в UNIX /* Контекстная замена */ #include <stdio.h> #include <ctype.h> #define INIT register char *sp = instring; #define GETC() (*sp++) #define PEEKC() (*sp) #define UNGETC(c) (--sp) #define RETURN(ptr) return #define ERROR(code) regerr(code) void regerr(); # include <regexp.h> #define EOL '\0' /* end of line */ #define ESIZE 512 short all = 0; /* ключ -a означает, что в строке надо заменить ВСЕ вхождения образца (global, all): * regsub -a int INT * "aa int bbb int cccc" -> "aa INT bbb INT cccc" * * step() находит САМУЮ ДЛИННУЮ подстроку, удовлетворяющую выражению, * поэтому regsub 'f(\(.*\),\(.*\))' 'f(\2,\1)' * заменит "aa f(1,2) bb f(3,4) cc" -> "aa f(4,1,2) bb f(3) cc' * |___________|_| |_|___________| */ char compiled[ESIZE], line[512]; А. Богатырев, 1992-95 - 315 - Си в UNIX void main(int ac, char *av[]){ register char *s, *p; register n; extern int nbra; extern char *braslist[], *braelist[], *loc1, *loc2; if( ac > 1 && !strcmp(av[1], "-a")){ ac--; av++; all++; } if(ac != 3){ fprintf(stderr, "Usage: %s [-a] pattern subst\n", av[0]); exit(1); } compile(av[1], compiled, compiled + sizeof compiled, EOL); while( gets(line) != NULL ){ if( !step(s = line, compiled)){ printf("%s\n", line); continue; } do{ /* Печатаем начало строки */ for( ; s != loc1; s++) putchar(*s); /* Делаем замену */ for(s=av[2]; *s; s++) if(*s == '\\'){ if(isdigit(s[1])){ /* сегмент */ int num = *++s - '1'; if(num < 0 || num >= nbra){ fprintf(stderr, "Bad block number %d\n", num+1); exit(2); } for(p=braslist[num]; p != braelist[num]; ++p) putchar(*p); } else if(s[1] == '&'){ ++s; /* вся сопоставленная строка */ for(p=loc1; p != loc2; ++p) putchar(*p); } else putchar(*++s); } else putchar(*s); } while(all && step(s = loc2, compiled)); /* Остаток строки */ for(s=loc2; *s; s++) putchar(*s); putchar('\n'); } /* endwhile */ } А. Богатырев, 1992-95 - 316 - Си в UNIX void regerr(int code){ char *msg; switch(code){ case 11: msg = "Range endpoint too large."; break; case 16: msg = "Bad number."; break; case 25: msg = "\\digit out of range."; break; case 36: msg = "Illegal or missing delimiter."; break; case 41: msg = "No remembered search string."; break; case 42: msg = "\\(~\\) imbalance."; break; case 43: msg = "Too many \\(."; break; case 44: msg = "More than 2 numbers given in \\{~\\\"}."; break; case 45: msg = "} expected after \\."; break; case 46: msg = "First number exceeds second in \\{~\\}."; break; case 49: msg = "[ ] imbalance."; break; case 50: msg = "Regular expression overflow."; break; default: msg = "Unknown error"; break; } fputs(msg, stderr); fputc('\n', stderr); exit(code); } void prfields(){ int i; for(i=0; i < nbra; i++) prfield(i); } void prfield(int n){ char *fbeg = braslist[n], *fend = braelist[n]; printf("\\%d='", n+1); for(; fbeg != fend; fbeg++) putchar(*fbeg); printf("'\n"); } 7.44. Составьте функцию поиска подстроки в строке. Используя ее, напишите программу поиска подстроки в текстовом файле. Программа должна выводить строки (либо номера строк) файла, в которых встретилась данная подстрока. Подстрока задается в качестве аргумента функции main(). /* Алгоритм быстрого поиска подстроки. * Дж. Мур, Р. Бойер, 1976 Texas * Смотри: Communications of the ACM 20, 10 (Oct., 1977), 762-772 * * Этот алгоритм выгоден при многократном поиске образца в * большом количестве строк, причем если они равной длины - * можно сэкономить еще и на операции strlen(str). * Алгоритм характерен тем, что при неудаче производит сдвиг не на * один, а сразу на несколько символов вправо. * В лучшем случае алгоритм делает slen/plen сравнений. */ char *pattern; /* образец (что искать) */ static int plen; /* длина образца */ static int d[256]; /* таблица сдвигов; в алфавите ASCII - * 256 букв. */ /* расстояние от конца образца до позиции i в нем */ #define DISTANCE(i) ((plen-1) - (i)) А. Богатырев, 1992-95 - 317 - Си в UNIX /* Поиск: * выдать индекс вхождения pattern в str, * либо -1, если не входит */ int indexBM( str ) char *str; /* в чем искать */ { int slen = strlen(str); /* длина строки */ register int pindx; /* индекс сравниваемой буквы в образце */ register int cmppos; /* индекс сравниваемой буквы в строке */ register int endpos; /* позиция в строке, к которой "приставляется" * последняя буква образца */ /* пока образец помещается в остаток строки */ for( endpos = plen-1; endpos < slen ; ){ /* Для отладки: pr(str, pattern, endpos - (plen-1), 0); /**/ /* просмотр образца от конца к началу */ for( cmppos = endpos, pindx = (plen - 1); pindx >= 0 ; cmppos--, pindx-- ) if( str[cmppos] != pattern[pindx] ){ /* Сдвиг, который ставит самый правый в образце * символ str[endpos] как раз под endpos-тую * позицию строки. Если же такой символ в образце не * содержится (или содержится только на конце), * то начало образца устанавливается в endpos+1 ую * позицию */ endpos += d[ str[endpos] & 0377 ]; break; /* & 0377 подавляет расширение знака. Еще */ } /* можно сделать все char -> unsigned char */ if( pindx < 0 ) return ( endpos - (plen-1)); /* Нашел: весь образец вложился */ } return( -1 ); /* Не найдено */ } А. Богатырев, 1992-95 - 318 - Си в UNIX /* Разметка таблицы сдвигов */ void compilePatternBM( ptrn ) char *ptrn; { register int c; pattern = ptrn; plen = strlen(ptrn); /* c - номер буквы алфавита */ for(c = 0; c < 256; c++) d[c] = plen; /* сдвиг на длину всего образца */ /* c - позиция в образце */ for(c = 0; c < plen - 1; c++) d[ pattern[c] & 0377 ] = DISTANCE(c); /* Сдвиг равен расстоянию от самого правого * (кроме последней буквы образца) * вхождения буквы в образец до конца образца. * Заметим, что если буква входит в образец несколько раз, * то цикл учитывает последнее (самое правое) вхождение. */ } /* Печать найденных строк */ void pr(s, p, n, nl) char *s, *p; { register i; printf("%4d\t%s\n", nl, s ); printf(" \t"); for(i = 0; i < n; i++ ) putchar( s[i] == '\t' ? '\t' : ' ' ); printf( "%s\n", p ); } /* Аналог программы fgrep */ #include <stdio.h> char str[ 1024 ]; /* буфер для прочитанной строки */ void main(ac, av) char **av; { int nline = 0; /* номер строки файла */ int ind; int retcode = 1; if(ac != 2){ fprintf(stderr, "Usage: %s 'pattern'\n", av[0] ); exit(33); } compilePatternBM( av[1] ); while( gets(str) != NULL ){ nline++; if((ind = indexBM(str)) >= 0 ){ retcode = 0; /* O'KAY */ pr(str, pattern, ind, nline); } } exit(retcode); } А. Богатырев, 1992-95 - 319 - Си в UNIX /* Пример работы алгоритма: peter piper picked a peck of pickled peppers. peck peter piper picked a peck of pickled peppers. peck peter piper picked a peck of pickled peppers. peck peter piper picked a peck of pickled peppers. peck peter piper picked a peck of pickled peppers. peck peter piper picked a peck of pickled peppers. peck peter piper picked a peck of pickled peppers. peck peter piper picked a peck of pickled peppers. peck */ 7.45. Напишите аналогичную программу, выдающую все строки, удовлетворяющие упрощен- ному регулярному выражению, задаваемому как аргумент для main(). Используйте функцию match, написанную нами ранее. Вы написали аналог программы grep из UNIX (но с другим типом регулярного выражения, нежели в оригинале). 7.46. Составьте функцию expand(s1, s2), которая расширяет сокращенные обозначения вида a-z строки s1 в эквивалентный полный список abcd...xyz в строке s2. Допускаются сокращения для строчных и прописных букв и цифр. Учтите случаи типа a-b-c, a-z0-9 и -a-g (соглашение состоит в том, что символ "-", стоящий в начале или в конце, воспри- нимается буквально). 7.47. Напишите программу, читающую файл и заменяющую строки вида |<1 и более пробелов и табуляций><текст> на пары строк |.pp |<текст> (здесь | обозначает левый край файла, a <> - метасимволы). Это - простейший препро- цессор, готовящий текст в формате nroff (это форматтер текстов в UNIX). Усложнения: - строки, начинающиеся с точки или с апострофа, заменять на \&<текст, начинающийся с точки или '> - строки, начинающиеся с цифры, заменять на .ip <число> <текст> - символ \ заменять на последовательность \e. - удалять пробелы перед символами .,;:!?) и вставлять после них пробел (знак пре- пинания должен быть приклеен к концу слова, иначе он может быть перенесен на следующую строку. Вы когда-нибудь видели строку, начинающуюся с запятой?). - склеивать перенесенные слова, поскольку nroff делает переносы сам: ....xxxx начало- => ....xxxx началоконец конец yyyy...... yyyy................ А. Богатырев, 1992-95 - 320 - Си в UNIX Вызывайте этот препроцессор разметки текста так: $ prep файлы... | nroff -me > text.lp 7.48. Составьте программу преобразования прописных букв из файла ввода в строчные, используя при этом функцию, в которой необходимо организовать анализ символа (дейст- вительно ли это буква). Строчные буквы выдавать без изменения. Указание: используйте макросы из <ctype.h>. Ответ: #include <ctype.h> #include <stdio.h> main(){ int c; while( (c = getchar()) != EOF ) putchar( isalpha( c ) ? (isupper( c ) ? tolower( c ) : c) : c); } либо ... putchar( isalpha(c) && isupper(c) ? tolower(c) : c ); либо даже putchar( isupper(c) ? tolower(c) : c ); В последнем случае под isupper и islower должны пониматься только буквы (увы, не во всех реализациях это так!). 7.49. Обратите внимание, что если мы выделяем класс символов при помощи сравнения, например: char ch; if( 0300 <= ch && ch < 0340 ) ...; (в кодировке КОИ-8 это маленькие русские буквы), то мы можем натолкнуться на следую- щий сюрприз: перед сравнением с целым значение ch приводится к типу int (приведение также делается при использовании char в качестве аргумента функции). При этом, если у ch был установлен старший бит (0200), произойдет расширение его во весь старший байт (расширение знакового бита). Результатом будет отрицательное целое число! Опыт: char c = '\201'; /* = 129 */ printf( "%d\n", c ); печатается -127. Таким образом, наше сравнение не сработает, т.к. оказывается что ch < 0. Следует подавлять расширение знака: if( 0300 <= (ch & 0377) && (ch & 0377) < 0340) ...; (0377 - маска из 8 бит, она же 0xFF, весь байт), либо объявить unsigned char ch; что означает, что при приведении к int знаковый бит не расширяется. 7.50. Рассмотрим еще один пример: А. Богатырев, 1992-95 - 321 - Си в UNIX main(){ char ch; /* 0377 - код последнего символа алфавита ASCII */ for (ch = 0100; ch <= 0377; ch++ ) printf( "%03o %s\n", ch & 0377, ch >= 0300 && ch < 0340 ? "yes" : "no" ); } Какие неприятности ждут нас здесь? - во-первых, когда бит 0200 у ch установлен, в сравнении ch выступает как отрица- тельное целое число (т.к. приведение к int делается расширением знакового бита), то есть у нас всегда печатается "no". Это мы можем исправить, написав unsigned char ch, либо используя ch в виде (ch & 0377) или ((unsigned) ch) - во-вторых, рассмотрим сам цикл. Пусть сейчас ch =='\377'. Условие ch <= 0377 истинно. Выполняется оператор ch++. Но ch - это байт, поэтому операции над ним производятся по модулю 0400 (0377 - это максимальное значение, которое можно хранить в байте - все биты единицы). То есть теперь значением ch станет 0. Но 0 < 0377 и условие цикла верно! Цикл продолжается; т.е. происходит зациклива- ние. Избежать этого можно только описав int ch; чтобы 0377+1 было равно 0400, а не 0 (или unsigned int, лишь бы длины переменной хватало, чтобы вместить число больше 0377). 7.51. Составьте программу, преобразующую текст, состоящий только из строчных букв в текст, состоящий из прописных и строчных букв. Первая буква и буква после каждой точки - прописные, остальные - строчные. слово один. слово два. --> Слово один. Слово два. Эта программа может оказаться полезной для преобразования текста, набранного в одном регистре, в текст, содержащий буквы обоих регистров. 7.52. Напишите программу, исправляющую опечатки в словах (spell check): программе задан список слов; она проверяет - является ли введенное вами слово словом из списка. Если нет - пытается найти наиболее похожее слово из списка, причем если есть нес- колько похожих - выдает все варианты. Отлавливайте случаи: - две соседние буквы переставлены местами: ножинцы=>ножницы; - удвоенная буква (буквы): ккаррандаш=>карандаш; - потеряна буква: бот=>болт; - измененная буква: бинт=>бант; - лишняя буква: морда=>мода; - буквы не в том регистре - сравните с каждым словом из списка, приводя все буквы к маленьким: сОВОк=>совок; Надо проверять каждую букву слова. Возможно вам будет удобно использовать рекурсию. Подсказка: для некоторых проверок вам может помочь функция match: слово_таблицы = "дом"; if(strlen(входное_слово) <= strlen(слово_таблицы)+1 && match(входное_слово, "*д*о*м*") ... /* похоже */ *о*м* ?дом дом? *д*м* д?ом *д*о* до?м Приведем вариант решения этой задачи: А. Богатырев, 1992-95 - 322 - Си в UNIX #include <stdio.h> #include <ctype.h> #include <locale.h> typedef unsigned char uchar; #define ANYCHAR '*' /* символ, сопоставляющийся с одной любой буквой */ static uchar version[120]; /* буфер для генерации вариантов */ static uchar vv; /* буква, сопоставившаяся с ANYCHAR */ /* привести все буквы к одному регистру */ static uchar icase(uchar c){ return isupper(c) ? tolower(c) : c; } /* сравнение строк с игнорированием регистра */ static int eqi(uchar *s1, uchar *s2 ) { while( *s1 && *s2 ){ if( icase( *s1 ) != icase( *s2 )) break; s1++; s2++; } return ( ! *s1 && ! *s2 ) ? 1 : 0 ; /* OK : FAIL */ } /* сравнение строк с игнорированием ANYCHAR */ static strok(register uchar *word, register uchar *pat) { while( *word && *pat ){ if( *word == ANYCHAR){ /* Неважно, что есть *pat, но запомним */ vv= *pat; } else { if( icase(*pat) != icase(*word) ) break; } word++; pat++; } /* если слова кончились одновременно ... */ return ( !*word && !*pat) ? 1 : 0; /* OK : FAIL */ } А. Богатырев, 1992-95 - 323 - Си в UNIX /* ЛИШНЯЯ БУКВА */ static int superfluous( uchar *word /* слово для коррекции */ , uchar *s /* эталон */ ){ register int i,j,k; int reply; register len = strlen(word); for(i=0 ; i < len ; i++){ /* генерим слова , получающиеся удалением одной буквы */ k=0; for(j=0 ; j < i ; j++) version[k++]=word[j]; for(j=i+1 ; j < len ; j++) version[k++]=word[j]; version[k]='\0'; if( eqi( version, s )) return 1; /* OK */ } return 0; /* FAIL */ } /* ПОТЕРЯНА БУКВА */ static int hole; /* место, где вставлена ANYCHAR */ static int lost(uchar *word, uchar *s) { register int i,j,k; register len = strlen(word); hole= (-1); for(i=0 ; i < len+1 ; i++){ k=0; for(j=0 ; j < i ; j++) version[k++]=word[j]; version[k++]=ANYCHAR; for(j=i ; j < len ; j++) version[k++]=word[j]; version[k]='\0'; if( strok( version, s )){ hole=i; return 1; /* OK */ } } return 0; /* FAIL */ } А. Богатырев, 1992-95 - 324 - Си в UNIX /* ИЗМЕНИЛАСЬ ОДНА БУКВА (включает случай ошибки регистра) */ static int changed(uchar *word, uchar *s) { register int i,j,k; register len = strlen(word); hole = (-1); for(i=0 ; i < len ; i++){ k=0; for( j=0 ; j < i ; j++) version[k++]=word[j]; version[k++]=ANYCHAR; for( j=i+1 ; j < len ; j++) version[k++]=word[j]; version[k]='\0'; if( strok( version,s)){ hole=i; return 1; /* OK */ } } return 0; /* FAIL */ } /* УДВОЕННАЯ БУКВА */ static int duplicates(uchar *word, uchar *s, int leng) { register int i,j,k; uchar tmp[80]; if( eqi( word, s )) return 1; /* OK */ for(i=0;i < leng - 1; i++) /* ищем парные буквы */ if( word[i]==word[i+1]){ k=0; for(j=0 ; j < i ; j++) tmp[k++]=word[j]; for(j=i+1 ; j < leng ; j++) tmp[k++]=word[j]; tmp[k]='\0'; if( duplicates( tmp, s, leng-1) == 1) return 1; /* OK */ } return 0; /* FAIL */ } А. Богатырев, 1992-95 - 325 - Си в UNIX /* ПЕРЕСТАВЛЕНЫ СОСЕДНИЕ БУКВЫ */ static int swapped(uchar *word, uchar *s) { register int i,j,k; register len = strlen(word); for(i=0;i < len-1;i++){ k=0; for(j=0 ; j < i ; j++) version[k++]=word[j]; version[k++]=word[i+1]; version[k++]=word[i]; for(j=i+2 ; j < len ; j++) version[k++]=word[j]; version[k]='\0'; if( eqi( version, s)) return 1; /* OK */ } return 0; /* FAIL */ } uchar *words[] = { (uchar *) "bag", (uchar *) "bags", (uchar *) "cook", (uchar *) "cool", (uchar *) "bug", (uchar *) "buy", (uchar *) "cock", NULL }; #define Bcase(x, operators) case x: { operators; } break; char *cname[5] = { "переставлены буквы", "удвоены буквы ", "потеряна буква ", "ошибочная буква ", "лишняя буква " }; А. Богатырев, 1992-95 - 326 - Си в UNIX static int spellmatch( uchar *word /* IN слово для коррекции */ , uchar *words[] /* IN таблица допустимых слов */ , uchar **indx /* OUT ответ */ ){ int i, code, total = (-1); uchar **ptr; if(!*word) return -1; for(ptr = words; *ptr; ++ptr) if(eqi(word, *ptr)){ if(indx) *indx = *ptr; return 0; } /* Нет в таблице, нужен подбор похожих */ for(ptr = words; *ptr; ++ptr){ uchar *s = *ptr; int max = 5; for(i=0; i < max; i++){ switch( i ){ Bcase(0,code = swapped(word, s) ) Bcase(1,code = duplicates(word, s, strlen(word)) ) Bcase(2,code = lost(word, s) ) Bcase(3,code = changed(word, s) ) Bcase(4,code = superfluous(word, s) ) } if(code){ total++; printf("?\t%s\t%s\n", cname[i], s); if(indx) *indx = s; /* В случае с дубликатами не рассматривать * на наличие лишних букв */ if(i==1) max = 4; } } } return total; } А. Богатырев, 1992-95 - 327 - Си в UNIX void main(){ uchar inpbuf[BUFSIZ]; int n; uchar *reply, **ptr; setlocale(LC_ALL, ""); for(ptr = words; *ptr; ptr++) printf("#\t%s\n", *ptr); do{ printf("> "); fflush(stdout); if(gets((char *)inpbuf) == NULL) break; switch(spellmatch(inpbuf, words, &reply)){ case -1: printf("Нет такого слова\n"); break; case 0: printf("Слово '%s'\n", reply); break; default: printf("Неоднозначно\n"); } } while(1); } 7.53. Пока я сам писал эту программу, я сделал две ошибки, которые должны быть весьма характерны для новичков. Про них надо бы говорить раньше, в главе про строки и в самой первой главе, но тут они пришлись как раз к месту. Вопрос: что печатает сле- дующая программа? #include <stdio.h> char *strings[] = { "Первая строка" "Вторая строка" "Третяя строка", "Четвертая строка", NULL }; void main(){ char **p; for(p=strings;*p;++p) printf("%s\n", *p); } А печатает она вот что: Первая строкаВторая строкаТретяя строка Четвертая строка Дело в том, что ANSI компилятор Си склеивает строки: "начало строки" "и ее конец" если они разделены пробелами в смысле isspace, в том числе и пустыми строками. А в нашем объявлении массива строк strings мы потеряли несколько разделительных запятых! Вторая ошибка касается того, что можно забыть поставить слово break в операторе switch, и долго после этого гадать о непредсказуемом поведении любого поступающего на вход значения. Дело просто: пробегаются все случаи, управление проваливается из case в следующий case, и так много раз подряд! Это и есть причина того, что в предыдущем А. Богатырев, 1992-95 - 328 - Си в UNIX примере все case оформлены нетривиальным макросом Bcase. 7.54. Составьте программу кодировки и раскодировки файлов по заданному ключу (строке символов). 7.55. Составьте программу, которая запрашивает анкетные данные типа фамилии, имени, отчества, даты рождения и формирует файл. Программа должна отлавливать ошибки ввода несимвольной и нецифровой информации, выхода составляющих даты рождения за допустимые границы с выдачей сообщений об ошибках. Программа должна давать возможность корректи- ровать вводимые данные. Все данные об одном человеке записываются в одну строку файла через пробел. Вот возможный пример части диалога (ответы пользователя выделены жирно): Введите месяц рождения [1-12]: 14 <ENTER> *** Неправильный номер месяца (14). Введите месяц рождения [1-12]: март <ENTER> *** Номер месяца содержит букву 'м'. Введите месяц рождения [1-12]: <ENTER> Вы хотите закончить ввод ? n Введите месяц рождения [1-12]: 11 <ENTER> Ноябрь Введите дату рождения [1-30]: _ В таких программах обычно ответ пользователя вводится как строка: printf("Введите месяц рождения [1-12]: "); fflush(stdout); gets(input_string); затем (если надо) отбрасываются лишние пробелы в начале и в конце строки, затем вве- денный текст input_string анализируется на допустимость символов (нет ли в нем не цифр?), затем строка преобразуется к нужному типу (например, при помощи функции atoi переводится в целое) и проверяется допустимость полученного значения, и.т.д. Вводимую информацию сначала заносите в структуру; затем записывайте содержимое полей структуры в файл в текстовом виде (используйте функцию fprintf, а не fwrite). 7.56. Составьте программу, осуществляющую выборку информации из файла, сформирован- ного в предыдущей задаче, и ее распечатку в табличном виде. Выборка должна осуществ- ляться по значению любого заданного поля (т.е. вы выбираете поле, задаете его значе- ние и получаете те строки, в которых значение указанного поля совпадает с заказанным вами значением). Усложнение: используйте функцию сравнения строки с регулярным выра- жением для выборки по шаблону поля (т.е. отбираются только те строки, в которых зна- чение заданного поля удовлетворяет шаблону). Для чтения файла используйте fscanf, либо fgets и затем sscanf. Второй способ лучше тем, что позволяет проверить по шаб- лону значение любого поля - не только текстового, но и числового: так 1234 (строка - изображение числа) удовлетворяет шаблону "12*". 7.57. Составьте вариант программы подсчета служебных слов языка Си, не учитывающий появление этих слов, заключенных в кавычки. 7.58. Составьте программу удаления из программы на языке Си всех комментариев. Обра- тите внимание на особые случаи со строками в кавычках и символьными константами; так строка char s[] = "/*"; не является началом комментария! Комментарии записывайте в отдельный файл. 7.59. Составьте программу выдачи перекрестных ссылок, т.е. программу, которая выво- дит список всех идентификаторов переменных, используемых в программе, и для каждого из идентификаторов выводит список номеров строк, в которые он входит. А. Богатырев, 1992-95 - 329 - Си в UNIX 7.60. Разработайте простую версию препроцессора для обработки операторов #include. В качестве прототипа такой программы можно рассматривать такую (она понимает дирек- тивы вида #include имяфайла - без <> или ""). #include <stdio.h> #include <string.h> #include <errno.h> char KEYWORD[] = "#include "; /* with a trailing space char */ void process(char *name, char *from){ FILE *fp; char buf[4096]; if((fp = fopen(name, "r")) == NULL){ fprintf(stderr, "%s: cannot read \"%s\", %s\n", from, name, strerror(errno)); return; } while(fgets(buf, sizeof buf, fp) != NULL){ if(!strncmp(buf, KEYWORD, sizeof KEYWORD - 1)){ char *s; if((s = strchr(buf, '\n')) != NULL) *s = '\0'; fprintf(stderr, "%s: including %s\n", name, s = buf + sizeof KEYWORD - 1); process(s, name); } else fputs(buf, stdout); } fclose(fp); } int main(int ac, char *av[]){ int i; for(i=1; i < ac; i++) process(av[i], "MAIN"); return 0; } 7.61. Разработайте простую версию препроцессора для обработки операторов #define. Сначала реализуйте макросы без аргументов. Напишите обработчик макросов вида #macro имя(аргу,менты) тело макроса - можно несколько строк #endm 7.62. Напишите программу, обрабатывающую определения #ifdef, #else, #endif. Учтите, что эти директивы могут быть вложенными: #ifdef A # ifdef B ... /* defined(A) && defined(B) */ # endif /*B*/ ... /* defined(A) */ #else /*not A*/ ... /* !defined(A) */ # ifdef C ... /* !defined(A) && defined(C) */ # endif /*C*/ А. Богатырев, 1992-95 - 330 - Си в UNIX #endif /*A*/ 7.63. Составьте программу моделирования простейшего калькулятора, который считывает в каждой строчке по одному числу (возможно со знаком) или по одной операции сложения или умножения, осуществляет операцию и выдает результат. 7.64. Составьте программу-калькулятор, которая производит операции сложения, вычита- ния, умножения, деления; операнды и знак арифметической операции являются строковыми аргументами функции main. 7.65. Составьте программу, вычисляющую значение командной строки, представляющей собой обратную польскую запись арифметического выражения. Например, 20 10 5 + * вычисляется как 20 * (10 + 5) . 7.66. Составьте функции работы со стеком: - добавление в стек - удаление вершины стека (с возвратом удаленного значения) Используйте два варианта: стек-массив и стек-список. 7.67. Составьте программу, которая использует функции работы со стеком для перевода арифметических выражений языка Си в обратную польскую запись. /*#!/bin/cc $* -lm * Калькулятор. Иллюстрация алгоритма превращения выражений * в польскую запись по методу приоритетов. */ #include <stdio.h> #include <stdlib.h> /* extern double atof(); */ #include <math.h> /* extern double sin(), ... */ #include <ctype.h> /* isdigit(), isalpha(), ... */ #include <setjmp.h> /* jmp_buf */ jmp_buf AGAIN; /* контрольная точка */ err(n){ longjmp(AGAIN,n);} /* прыгнуть в контрольную точку */ А. Богатырев, 1992-95 - 331 - Си в UNIX /* ВЫЧИСЛИТЕЛЬ --------------------------------------- */ /* Если вместо помещения операндов в стек stk[] просто * печатать операнды, а вместо выполнения операций над * стеком просто печатать операции, мы получим "польскую" * запись выражения: * a+b -> a b + * (a+b)*c -> a b + c * * a + b*c -> a b c * + */ /* стек вычислений */ #define MAXDEPTH 20 /* глубина стеков */ int sp; /* указатель стека (stack pointer) */ double stk[MAXDEPTH]; double dpush(d) double d; /* занести число в стек */ { if( sp == MAXDEPTH ){ printf("Стек операндов полон\n");err(1);} else return( stk[sp++] = d ); } double dpop(){ /* взять вершину стека */ if( !sp ){ printf("Стек операндов пуст\n"); err(2); } else return stk[--sp]; } static double r,p; /* вспомогательные регистры */ void add() { dpush( dpop() + dpop()); } void mult() { dpush( dpop() * dpop()); } void sub() { r = dpop(); dpush( dpop() - r); } void divide() { r = dpop(); if(r == 0.0){ printf("Деление на 0\n"); err(3); } dpush( dpop() / r ); } void pwr() { r = dpop(); dpush( pow( dpop(), r )); } void dup() { dpush( dpush( dpop())); } void xchg(){ r = dpop(); p = dpop(); dpush(r); dpush(p); } void neg() { dpush( - dpop()); } void dsin(){ dpush( sin( dpop())); } void dcos(){ dpush( cos( dpop())); } void dexp(){ dpush( exp( dpop())); } void dlog(){ dpush( log( dpop())); } void dsqrt(){ dpush( sqrt( dpop())); } void dsqr(){ dup(); mult(); } /* M_PI и M_E определены в <math.h> */ void pi() { dpush( M_PI /* число пи */ ); } void e() { dpush( M_E /* число e */ ); } void prn() { printf("%g\n", dpush( dpop())); } void printstk(){ if( !sp ){ printf("Стек операндов пуст\n"); err(4);} while(sp) printf("%g ", dpop()); putchar('\n'); } А. Богатырев, 1992-95 - 332 - Си в UNIX /* КОМПИЛЯТОР ---------------------------------------- */ /* номера лексем */ #define END (-3) /* = */ #define NUMBER (-2) /* число */ #define BOTTOM 0 /* псевдолексема "дно стека" */ #define OPENBRACKET 1 /* ( */ #define FUNC 2 /* f( */ #define CLOSEBRACKET 3 /* ) */ #define COMMA 4 /* , */ #define PLUS 5 /* + */ #define MINUS 6 /* - */ #define MULT 7 /* * */ #define DIV 8 /* / */ #define POWER 9 /* ** */ /* Приоритеты */ #define NOTDEF 333 /* не определен */ #define INFINITY 3000 /* бесконечность */ /* Стек транслятора */ typedef struct _opstack { int cop; /* код операции */ void (*f)(); /* "отложенное" действие */ } opstack; int osp; /* operations stack pointer */ opstack ost[MAXDEPTH]; void push(n, func) void (*func)(); { if(osp == MAXDEPTH){ printf("Стек операций полон\n");err(5);} ost[osp].cop = n; ost[osp++].f = func; } int pop(){ if( !osp ){ printf("Стек операций пуст\n"); err(6); } return ost[--osp].cop; } int top(){ if( !osp ){ printf("Стек операций пуст\n"); err(7); } return ost[osp-1].cop; } void (*topf())(){ return ost[osp-1].f; } #define drop() (void)pop() void nop(){ printf( "???\n" ); } /* no operation */ void obr_err(){ printf( "Не хватает )\n" ); err(8); } А. Богатырев, 1992-95 - 333 - Си в UNIX /* Таблица приоритетов */ struct synt{ int inp_prt; /* входной приоритет */ int stk_prt; /* стековый приоритет */ void (*op)(); /* действие над стеком вычислений */ } ops[] = { /* BOTTOM */ {NOTDEF, -1, nop }, /* OPENBRACKET */ {INFINITY, 0, obr_err}, /* FUNC */ {INFINITY, 0, obr_err}, /* CLOSEBRACKET */ {1, NOTDEF, nop }, /* NOPUSH */ /* COMMA */ {1, NOTDEF, nop }, /* NOPUSH */ /* PLUS */ {1, 1, add }, /* MINUS */ {1, 1, sub }, /* MULT */ {2, 2, mult }, /* DIV */ {2, 2, divide }, /* POWER */ {3, 3, pwr } }; #define stkprt(i) ops[i].stk_prt #define inpprt(i) ops[i].inp_prt #define perform(i) (*ops[i].op)() /* значения, заполняемые лексическим анализатором */ double value; void (*fvalue)(); int tprev; /* предыдущая лексема */ А. Богатырев, 1992-95 - 334 - Си в UNIX /* Транслятор в польскую запись + интерпретатор */ void reset(){ sp = osp = 0; push(BOTTOM, NULL); tprev = END;} void calc(){ int t; do{ if( setjmp(AGAIN)) printf( "Стеки после ошибки сброшены\n" ); reset(); while((t = token()) != EOF && t != END){ if(t == NUMBER){ if(tprev == NUMBER){ printf("%g:Два числа подряд\n",value); err(9); } /* любое число просто заносится в стек */ tprev = t; dpush(value); continue; } /* иначе - оператор */ tprev = t; /* Выталкивание и выполнение операций со стека */ while(inpprt(t) <= stkprt( top()) ) perform( pop()); /* Сокращение или подмена скобок */ if(t == CLOSEBRACKET){ if( top() == OPENBRACKET || top() == FUNC ){ void (*ff)() = topf(); drop(); /* схлопнуть скобки */ /* обработка функции */ if(ff) (*ff)(); }else{ printf( "Не хватает (\n"); err(10); } } /* Занесение операций в стек (кроме NOPUSH-операций) */ if(t != CLOSEBRACKET && t != COMMA) push(t, t == FUNC ? fvalue : NULL ); } if( t != EOF ){ /* Довыполнить оставшиеся операции */ while( top() != BOTTOM ) perform( pop()); printstk(); /* печать стека вычислений (ответ) */ } } while (t != EOF); } /* Лексический анализатор ---------------------------- */ extern void getn(), getid(), getbrack(); int token(){ /* прочесть лексему */ int c; while((c = getchar())!= EOF && (isspace(c) || c == '\n')); if(c == EOF) return EOF; ungetc(c, stdin); if(isdigit(c)){ getn(); return NUMBER; } if(isalpha(c)){ getid(); getbrack(); return FUNC; } return getop(); } А. Богатырев, 1992-95 - 335 - Си в UNIX /* Прочесть число (с точкой) */ void getn(){ int c, i; char s[80]; s[0] = getchar(); for(i=1; isdigit(c = getchar()); i++ ) s[i] = c; if(c == '.'){ /* дробная часть */ s[i] = c; for(i++; isdigit(c = getchar()); i++) s[i] = c; } s[i] = '\0'; ungetc(c, stdin); value = atof(s); } /* Прочесть операцию */ int getop(){ int c; switch( c = getchar()){ case EOF: return EOF; case '=': return END; case '+': return PLUS; case '-': return MINUS; case '/': return DIV; case '*': c = getchar(); if(c == '*') return POWER; else{ ungetc(c, stdin); return MULT; } case '(': return OPENBRACKET; case ')': return CLOSEBRACKET; case ',': return COMMA; default: printf( "Ошибочная операция %c\n", c); return token(); } } struct funcs{ /* Таблица имен функций */ char *fname; void (*fcall)(); } tbl[] = { { "sin", dsin }, { "cos", dcos }, { "exp", dexp }, { "sqrt", dsqrt }, { "sqr", dsqr }, { "pi", pi }, { "sum", add }, { "ln", dlog }, { "e", e }, { NULL, NULL } }; char *lastf; /* имя найденной функции */ /* Прочесть имя функции */ void getid(){ struct funcs *ptr = tbl; char name[80]; int c, i; *name = getchar(); for(i=1; isalpha(c = getchar()); i++) name[i] = c; name[i] = '\0'; ungetc(c, stdin); /* поиск в таблице */ for( ; ptr->fname; ptr++ ) if( !strcmp(ptr->fname, name)){ fvalue = ptr->fcall; lastf = ptr->fname; return; } printf( "Функция \"%s\" неизвестна\n", name ); err(11); } А. Богатырев, 1992-95 - 336 - Си в UNIX /* прочесть открывающую скобку после имени функции */ void getbrack(){ int c; while((c = getchar()) != EOF && c != '(' ) if( !isspace(c) && c != '\n' ){ printf("Между именем функции %s и ( символ %c\n", lastf, c); ungetc(c, stdin); err(12); } } void main(){ calc();} /* Примеры: ( sin( pi() / 4 + 0.1 ) + sum(2, 4 + 1)) * (5 - 4/2) = ответ: 23.3225 (14 + 2 ** 3 * 7 + 2 * cos(0)) / ( 7 - 4 ) = ответ: 24 */ 7.68. Приведем еще один арифметический вычислитель, использующий классический рекур- сивный подход: /* Калькулятор на основе рекурсивного грамматического разбора. * По мотивам арифметической части программы csh (СиШелл). * csh написан Биллом Джоем (Bill Joy). : var1 = (x = 1+3) * (y=x + x++) 36 : s = s + 1 ошибка : y 9 : s = (1 + 1 << 2) == 1 + (1<<2) 0 : var1 + 3 + -77 -38 : a1 = 3; a2 = (a4=a3 = 2; a1++)+a4+2 8 : sum(a=2;b=3, a++, a*3-b) 12 */ #include <stdio.h> #include <ctype.h> #include <setjmp.h> typedef enum { NUM, ID, OP, OPEN, CLOSE, UNKNOWN, COMMA, SMC } TokenType; char *toknames[] = { "number", "identifier", "operation", "open_paren", "close_paren", "unknown", "comma", "semicolon" }; typedef struct _Token { char *token; /* лексема (слово) */ struct _Token *next; /* ссылка на следующую */ TokenType type; /* тип лексемы */ } Token; extern void *malloc(unsigned); extern char *strchr(char *, char); char *strdup(const char *s){ char *p = (char *)malloc(strlen(s)+1); if(p) strcpy(p,s); return p; } А. Богатырев, 1992-95 - 337 - Си в UNIX /* Лексический разбор ------------------------------------------*/ /* Очистить цепочку токенов */ void freelex(Token **p){ Token *thisTok = *p; while( thisTok ){ Token *nextTok = thisTok->next; free((char *) thisTok->token); free((char *) thisTok); thisTok = nextTok; } *p = NULL; } /* Добавить токен в хвост списка */ void addtoken(Token **hd, Token **tl, char s[], TokenType t){ Token *newTok = (Token *) malloc(sizeof(Token)); newTok->next = (Token *) NULL; newTok->token = strdup(s); newTok->type = t; if(*hd == NULL) *hd = *tl = newTok; else{ (*tl)->next = newTok; *tl = newTok; } } /* Разобрать строку в список лексем (токенов) */ #define opsym(c) ((c) && strchr("+-=!~^|&*/%<>", (c))) #define is_alpha(c) (isalpha(c) || (c) == '_') #define is_alnum(c) (isalnum(c) || (c) == '_') void lex(Token **hd, Token **tl, register char *s){ char *p, csave; TokenType type; while(*s){ while( isspace(*s)) ++s; p = s; if( !*s ) break; if(isdigit (*s)){ type = NUM; while(isdigit (*s))s++; } else if(is_alpha(*s)){ type = ID; while(is_alnum(*s))s++; } else if(*s == '('){ type = OPEN; s++; } else if(*s == ')'){ type = CLOSE; s++; } else if(*s == ','){ type = COMMA; s++; } else if(*s == ';'){ type = SMC; s++; } else if(opsym(*s)){ type = OP; while(opsym(*s)) s++; } else { type = UNKNOWN; s++; } csave = *s; *s = '\0'; addtoken(hd, tl, p, type); *s = csave; } } /* Распечатка списка лексем */ void printlex(char *msg, Token *t){ if(msg && *msg) printf("%s: ", msg); for(; t != NULL; t = t->next) printf("%s`%s' ", toknames[(int)t->type], t->token); putchar('\n'); } А. Богатырев, 1992-95 - 338 - Си в UNIX /* Система переменных ----------------------------------------- */ #define NEXT(v) *v = (*v)->next #define TOKEN(v) (*v)->token #define TYPE(v) (*v)->type #define eq(str1, str2) (!strcmp(str1, str2)) jmp_buf breakpoint; #define ERR(msg,val) { printf("%s\n", msg);longjmp(breakpoint, val+1);} typedef struct { char *name; /* Имя переменной */ int value; /* Значение переменной */ int isset; /* Получила ли значение ? */ } Var; #define MAXV 40 Var vars[MAXV]; /* Получить значение переменной */ int getVar(char *name){ Var *ptr; for(ptr=vars; ptr->name; ptr++) if(eq(name, ptr->name)){ if(ptr->isset) return ptr->value; printf("%s: ", name); ERR("variable is unbound yet", 0); } printf("%s: ", name); ERR("undefined variable", 0); } /* Создать новую переменную */ Var *internVar(char *name){ Var *ptr; for(ptr=vars; ptr->name; ptr++) if(eq(name, ptr->name)) return ptr; ptr->name = strdup(name); ptr->isset = 0; ptr->value = 0; return ptr; } /* Установить значение переменной */ void setVar(Var *ptr, int val){ ptr->isset = 1; ptr->value = val; } /* Распечатать значения переменных */ void printVars(){ Var *ptr; for(ptr=vars; ptr->name; ++ptr) printf("\t%s %s %d\n", ptr->isset ? "BOUND ":"UNBOUND", ptr->name, ptr->value); } А. Богатырев, 1992-95 - 339 - Си в UNIX /* Синтаксический разбор и одновременное вычисление ----------- */ /* Вычисление встроенных функций */ int apply(char *name, int args[], int nargs){ if(eq(name, "power2")){ if(nargs != 1) ERR("power2: wrong argument count", 0); return (1 << args[0]); } else if(eq(name, "min")){ if(nargs != 2) ERR("min: wrong argument count", 0); return (args[0] < args[1] ? args[0] : args[1]); } else if(eq(name, "max")){ if(nargs != 2) ERR("max: wrong argument count", 0); return (args[0] < args[1] ? args[1] : args[0]); } else if(eq(name, "sum")){ register i, sum; for(i=0, sum=0; i < nargs; sum += args[i++]); return sum; } else if(eq(name, "rand")){ switch(nargs){ case 0: return rand(); case 1: return rand() % args[0]; case 2: return args[0] + rand() % (args[1] - args[0] + 1); default: ERR("rand: wrong argument count", 0); } } ERR("Unknown function", args[0]); } /* Вычислить выражение из списка лексем. */ /* Синтаксис задан праворекурсивной грамматикой */ int expr(Token *t){ int val = 0; if(val = setjmp(breakpoint)) return val - 1; val = expression(&t); if(t){ printlex(NULL, t); ERR("Extra tokens", val); } return val; } /* <EXPRESSION> = <EXPASS> | <EXPASS> ";" <EXPRESSION> */ int expression(Token **v){ int arg = expass(v); if(*v && TYPE(v) == SMC ){ NEXT(v); return expression(v); } else return arg; } /* <EXPASS> = <ПЕРЕМЕННАЯ> "=" <EXPASS> | <EXP0> */ int expass(Token **v){ int arg; if(*v && (*v)->next && (*v)->next->type == OP && eq((*v)->next->token, "=")){ Var *ptr; /* присваивание (assignment) */ if( TYPE(v) != ID ) /* слева нужна переменная */ ERR("Lvalue needed", 0); ptr = internVar(TOKEN(v)); NEXT(v); NEXT(v); setVar(ptr, arg = expass(v)); return arg; } return exp0(v); } А. Богатырев, 1992-95 - 340 - Си в UNIX /* <EXP0> = <EXP1> | <EXP1> "||" <EXP0> */ int exp0(Token **v){ int arg = exp1(v); if(*v && TYPE(v) == OP && eq(TOKEN(v), "||")){ NEXT(v); return(exp0(v) || arg ); /* помещаем arg ВТОРЫМ, чтобы второй операнд вычислялся * ВСЕГДА (иначе не будет исчерпан список токенов и * возникнет ошибка в expr(); Это не совсем по правилам Си. */ } else return arg; } /* <EXP1> = <EXP2> | <EXP2> "&&" <EXP1> */ int exp1(Token **v){ int arg = exp2(v); if(*v && TYPE(v) == OP && eq(TOKEN(v), "&&")){ NEXT(v); return(exp1(v) && arg); } else return arg; } /* <EXP2> = <EXP2A> | <EXP2A> "|" <EXP2> */ int exp2(Token **v){ int arg = exp2a(v); if(*v && TYPE(v) == OP && eq(TOKEN(v), "|")){ NEXT(v); return( arg | exp2(v)); } else return arg; } /* <EXP2A> = <EXP2B> | <EXP2B> "^" <EXP2A> */ int exp2a(Token **v){ int arg = exp2b(v); if(*v && TYPE(v) == OP && eq(TOKEN(v), "^")){ NEXT(v); return( arg ^ exp2a(v)); } else return arg; } /* <EXP2B> = <EXP2C> | <EXP2C> "&" <EXP2B> */ int exp2b(Token **v){ int arg = exp2c(v); if(*v && TYPE(v) == OP && eq(TOKEN(v), "&")){ NEXT(v); return( arg & exp2b(v)); } else return arg; } /* <EXP2C> = <EXP3> | <EXP3> "==" <EXP3> | <EXP3> "!=" <EXP3> */ int exp2c(Token **v){ int arg = exp3(v); if(*v && TYPE(v) == OP && eq(TOKEN(v), "==")){ NEXT(v); return( arg == exp3(v)); } else if(*v && TYPE(v) == OP && eq(TOKEN(v), "!=")){ NEXT(v); return( arg != exp3(v)); } else return arg; } А. Богатырев, 1992-95 - 341 - Си в UNIX /* <EXP3> = <EXP3A> | <EXP3A> ">" <EXP3> | <EXP3A> "<" <EXP3> | <EXP3A> ">=" <EXP3> | <EXP3A> "<=" <EXP3> */ int exp3(Token **v){ int arg = exp3a(v); if(*v && TYPE(v) == OP && eq(TOKEN(v), ">")){ NEXT(v); return( arg && exp3(v)); }else if(*v && TYPE(v) == OP && eq(TOKEN(v), "<")){ NEXT(v); return( arg && exp3(v)); }else if(*v && TYPE(v) == OP && eq(TOKEN(v), ">=")){ NEXT(v); return( arg && exp3(v)); }else if(*v && TYPE(v) == OP && eq(TOKEN(v), "<=")){ NEXT(v); return( arg && exp3(v)); } else return arg; } /* <EXP3A> = <EXP4> | <EXP4> "<<" <EXP3A> | <EXP4> ">>" <EXP3A> */ int exp3a(Token **v){ int arg = exp4(v); if(*v && TYPE(v) == OP && eq(TOKEN(v), "<<")){ NEXT(v); return( arg << exp3a(v)); }else if(*v && TYPE(v) == OP && eq(TOKEN(v), ">>")){ NEXT(v); return( arg && exp3a(v)); } else return arg; } /* <EXP4> = <EXP5> | <EXP5> "+" <EXP4> | <EXP5> "-" <EXP4> */ int exp4(Token **v){ int arg = exp5(v); if(*v && TYPE(v) == OP && eq(TOKEN(v), "+")){ NEXT(v); return( arg + exp4(v)); }else if(*v && TYPE(v) == OP && eq(TOKEN(v), "-")){ NEXT(v); return( arg - exp4(v)); } else return arg; } /* <EXP5> = <EXP6> | <EXP6> "*" <EXP5> | <EXP6> "/" <EXP5> | <EXP6> "%" <EXP5> */ int exp5(Token **v){ int arg = exp6(v), arg1; if(*v && TYPE(v) == OP && eq(TOKEN(v), "*")){ NEXT(v); return( arg * exp5(v)); }else if(*v && TYPE(v) == OP && eq(TOKEN(v), "/")){ NEXT(v); if((arg1 = exp5(v)) == 0) ERR("Zero divide", arg); return( arg / arg1); }else if(*v && TYPE(v) == OP && eq(TOKEN(v), "%")){ NEXT(v); if((arg1 = exp5(v)) == 0) ERR("Zero module", arg); return( arg % arg1); } else return arg; } А. Богатырев, 1992-95 - 342 - Си в UNIX /* <EXP6> = "!"<EXP6> | "~"<EXP6> | "-"<EXP6> | "(" <EXPRESSION> ")" | <ИМЯФУНКЦИИ> "(" [ <EXPRESSION> [ "," <EXPRESSION> ]... ] ")" | <ЧИСЛО> | <CH_ПЕРЕМЕННАЯ> */ int exp6(Token **v){ int arg; if( !*v) ERR("Lost token", 0); if(TYPE(v) == OP && eq(TOKEN(v), "!")){ NEXT(v); return !exp6(v); } if(TYPE(v) == OP && eq(TOKEN(v), "~")){ NEXT(v); return ~exp6(v); } if(TYPE(v) == OP && eq(TOKEN(v), "-")){ NEXT(v); return -exp6(v); /* унарный минус */ } if(TYPE(v) == OPEN){ NEXT(v); arg = expression(v); if( !*v || TYPE(v) != CLOSE) ERR("Lost ')'", arg); NEXT(v); return arg; } if(TYPE(v) == NUM){ /* изображение числа */ arg = atoi(TOKEN(v)); NEXT(v); return arg; } if(TYPE(v) == ID){ char *name = (*v)->token; int args[20], nargs = 0; NEXT(v); if(! (*v && TYPE(v) == OPEN)){ /* Переменная */ return expvar(v, name); } /* Функция */ args[0] = 0; do{ NEXT(v); if( *v && TYPE(v) == CLOSE ) break; /* f() */ args[nargs++] = expression(v); } while( *v && TYPE(v) == COMMA); if(! (*v && TYPE(v) == CLOSE)) ERR("Error in '()'", args[0]); NEXT(v); return apply(name, args, nargs); } printlex(TOKEN(v), *v); ERR("Unknown token type", 0); } /* <CH_ПЕРЕМЕННАЯ> = <ПЕРЕМЕННАЯ> | <ПЕРЕМЕННАЯ> "++" | <ПЕРЕМЕННАЯ> "--" Наши операции ++ и -- соответствуют ++x и --x из Си */ int expvar(Token **v, char *name){ int arg = getVar(name); Var *ptr = internVar(name); if(*v && TYPE(v) == OP){ if(eq(TOKEN(v), "++")){ NEXT(v); setVar(ptr, ++arg); return arg; } if(eq(TOKEN(v), "--")){ NEXT(v); setVar(ptr, --arg); return arg; } } return arg; } А. Богатырев, 1992-95 - 343 - Си в UNIX /* Головная функция ------------------------------------------- */ char input[256]; Token *head, *tail; void main(){ do{ printf(": "); fflush(stdout); if( !gets(input)) break; if(!*input){ printVars(); continue; } if(eq(input, "!!")) ; /* ничего не делать, т.е. повторить */ else{ if(head) freelex(&head); lex(&head, &tail, input); } printf("Result: %d\n", expr(head)); } while(1); putchar('\n'); } 7.69. Напишите программу, выделяющую n-ое поле из каждой строки файла. Поля разделя- ются двоеточиями. Предусмотрите задание символа-разделителя из аргументов программы. Используйте эту программу для выделения поля "домашний каталог" из файла /etc/passwd. Для выделения очередного поля можно использовать следующую процедуру: main(){ char c, *next, *strchr(); int nfield; char *s = "11111:222222222:333333:444444"; for(nfield=0;;nfield++){ if(next = strchr(s, ':')){ c= *next; *next= '\0'; } printf( "Поле #%d: '%s'\n", nfield, s); /* можно сделать с полем s что-то еще */ if(next){ *next= c; s= next+1; continue; } else { break; /* последнее поле */ } } } 7.70. Разработайте архитектуру и систему команд учебной машины и напишите интерпре- татор учебного ассемблера, отрабатывающего по крайней мере такие команды: mov пересылка (:=) add сложение sub вычитание cmp сравнение и выработка признака jmp переход jeq переход, если == jlt переход, если < jle переход, если <= neg изменение знака not инвертирование признака 7.71. Напишите программу, преобразующую определения функций Си в "старом" стиле в "новый" стиль стандарта ANSI ("прототипы" функций). f(x, y, s, v) int x; char *s; struct elem *v; { ... } преобразуется в int f(int x, int y, char *s, struct elem *v) { ... } (обратите внимание, что переменная y и сама функция f описаны по умолчанию как int). А. Богатырев, 1992-95 - 344 - Си в UNIX Еще пример: char *ff() { ... } заменяется на char *ff(void){ ... } В данной задаче вам возможно придется использовать программу lex. В списке аргументов прототипа должны быть явно указаны типы всех аргументов - описатель int нельзя опускать. Так q(x, s) char *s; { ... } // не прототип, допустимо. // x - int по умолчанию. q(x, char *s); // недопустимо. q(int x, char *s); // верно. Собственно под "прототипом" понимают предварительное описание функции в новом стиле - где вместо тела {...} сразу после заголовка стоит точка с запятой. long f(long x, long y); /* прототип */ ... long f(long x, long y){ return x+y; } /* реализация */ В прототипе имена аргументов можно опускать: long f(long, long); /* прототип */ char *strchr(char *, char); Это предварительное описание помещают где-нибудь в начале программы, до первого вызова функции. В современном Си прототипы заменяют описания вида extern long f(); о которых мы говорили раньше. Прототипы предоставляют программисту механизм для автоматического контроля формата вызова функции. Так, если функция имеет прототип double f( double ); и вызывается как double x = f( 12 ); то компилятор автоматически превратит это в double x = f( (double) 12 ); (поскольку существует приведение типа от int к double); если же написано f( "привет" ); то компилятор сообщит об ошибке (так как нет преобразования типа (char *) в double). Прототип принуждает компилятор проверять: a) соответствие ТИПОВ фактических параметров (при вызове) типам формальных парамет- ров (в прототипе); b) соответствие КОЛИЧЕСТВА фактических и формальных параметров; c) тип возвращаемого функцией значения. Прототипы обычно помещают в include-файлы. Так в ANSI стандарте Си предусмотрен файл, подключаемый #include <stdlib.h> А. Богатырев, 1992-95 - 345 - Си в UNIX в котором определены прототипы функций из стандартной библиотеки языка Си. Черезвы- чайно полезно писать эту директиву include, чтобы компилятор проверял, верно ли вы вызываете стандартные функции. Заметим, что если вы определили прототипы каких-то функций, но в своей программе используете не все из этих функций, то функции, соответствующие "лишним" прототипам, НЕ будут добавляться к вашей программе из библиотеки. Т.е. прототипы - это указание компилятору; ни в какие машинные команды они не транслируются. То же самое касается описаний внешних переменных и функций в виде extern int x; extern char *func(); Если вы не используете переменную или функцию с таким именем, то эти строки не имеют никакого эффекта (как бы вообще отсутствуют). 7.72. Обратная задача: напишите преобразователь из нового стиля в старый. int f( int x, char *y ){ ... } переводить в int f( x, y ) int x; char *y; { ... } 7.73. Довольно легко использовать прототипы таким образом, что они потеряют всякий смысл. Для этого надо написать программу, состоящую из нескольких файлов, и в каждом файле использовать свои прототипы для одной и той же функции. Так бывает, когда вы поменяли функцию и прототип в одном файле, быть может во втором, но забыли сделать это в остальных. -------- файл a.c -------- void g(void); void h(void); int x = 0, y = 13; void f(int arg){ printf("f(%d)\n", arg); x = arg; x++; } int main(int ac, char *av[]){ h(); f(1); g(); printf("x=%d y=%d\n", x, y); return 0; } А. Богатырев, 1992-95 - 346 - Си в UNIX -------- файл b.c -------- extern int x, y; int f(int); void g(){ y = f(5); } -------- файл c.c -------- void f(); void h(){ f(); } Выдача программы: abs@wizard$ cc a.c b.c c.c -o aaa a.c: b.c: c.c: abs@wizard$ aaa f(-277792360) f(1) f(5) x=6 y=5 abs@wizard$ Обратите внимание, что во всех трех файлах f() имеет разные прототипы! Поэтому прог- рамма печатает нечто, что довольно-таки бессмысленно! Решение таково: стараться вынести прототипы в include-файл, чтобы все файлы программы включали одни и те же прототипы. Стараться, чтобы этот include-файл вклю- чался также в файл с самим определением функции. В таком случае изменение только заголовка функции или только прототипа вызовет ругань компилятора о несоответствии. Вот как должен выглядеть наш проект: ------------- файл header.h ------------- extern int x, y; void f(int arg); int main(int ac, char *av[]); void g(void); void h(void); А. Богатырев, 1992-95 - 347 - Си в UNIX -------- файл a.c -------- #include "header.h" int x = 0, y = 13; void f(int arg){ printf(