Б. Керриган, Д. Ритчи Язык программирования C. Б. Керниган, Д. зык программирования и . Издание 3е, исправленное Перевод с английского под редакцией Вс. С. Штаркмана СанктПетербург 2003
 Скачать 31.48 Mb.
|
|
Глава 5. Указатели и массивы из возможностей сравнить две строки - передать указатели на них функ- ции st Чтобы поменять местами строки, достаточно будет поменять местами в массиве их указатели (а не сами строки). abc defghi jklmnopqrst abc Здесь снимаются сразу две проблемы: одна - связанная со сложностью управления памятью, а вторая - с большими накладными расходами при перестановках самих строк. Процесс сортировки распадается на три этапа: чтение всех строк из ввода сортировка введенных строк их по порядку Как обычно, выделим функции, соответствующие естественному де- лению задачи, и напишем главную программу управляющую этими функциями. Отложим на время реализацию этапа сортировки и сосредо- точимся на структуре данных и вводе-выводе. , Программа ввода должна прочитать и запомнить символы всех строк, а также построить массив указателей на строки. Она, кроме должна подсчитать число введенных строк - эта информация понадобится для сортировки и печати. Так как функция ввода работать только с конечным числом строк, то, если их введено слишком много, она будет выдавать некоторое значение, которое никогда не совпадет с количеством строк, например Программа вывода занимается только тем, что печатает строки, при- чем в том порядке, в котором расположены указатели на них в массиве. ttdefine 5000 /* максимальное число строк */ char /* указатели на строки */ int readlines(char *lineptr[], int nlines); void *lineptr[], int nlines); 5.6. Массивы указателей, указатели на указатели _ _ void qsort(char *lineptr[], int left, int right); /* сортировка строк */ { int nlines; /* количество прочитанных строк */ if = >= 0) { 0, nlines); return 0; } else { слишком много return tfdefine MAXLEN 1000 /* максимальная длина строки */ int getline(char *, int); char *alloc(int); /* readlines: чтение строк */ int readlines(char *lineptr[], int { int nlines; *p, nlines = 0; while = getline(line, > 0) if (nlines >= maxlines (p = == NULL) return else { line[len-1] = /* убираем символ \n strcpy(p, line); lineptr[nlines++] = p; > return nlines; /* writelines: печать строк */ void *lineptr[], int nlines) { int Глава 5. Указатели и массивы for (i = 0; i < nlines; i++) } Функция getline взята из параграфа 1.9. Основное новшество здесь - объявление inept г: char в котором сообщается, что linept г есть массив из элементов, каж- дый из которых представляет собой указатель на char. Иначе говоря, r[i] - указатель на символ, a r[i] - символ, на который он указывает (первый символ i-й строки текста). Так как lineptr - имя массива, его можно трактовать как указатель, т. е. так же, как мы это делали в предыдущих примерах, и пере- писать следующим образом: /* writelines: печать строк */ void writelines(char *lineptr[], int nlines) { while > 0) printf( *lineptr++); } Вначале г указывает на первую строку; каждое приращение ука- зателя приводит к тому, что указывает на следующую строку, и делается это до тех пор, пока nlines не станет нулем. Теперь, когда мы разобрались с вводом и выводом, можно приступить к сортировке. Быструю сортировку, описанную в главе 4, надо несколько модифицировать: нужно изменить объявления, а операцию сравнения заменить обращением к Алгоритм остался тем же, и это дает нам определенную уверенность в его правильности. /* qsort: сортирует по возрастанию */ void qsort(char *v[], int left, int right) { int i, last; void swap(char *v[], int i, int j); if (left >= right) /* ничего не делается, если в массиве */ return; /* менее двух элементов */ left, (left+ last = left; for (i = i <= right; 5.7. Многомерные массивы if < 0) ++last, i); left, last); left, qsort(v, right); } Небольшие поправки требуются и в программе перестановки. /* swap: поменять местами v[i] и v[j] */ void *v[], int i, int { char temp = v[i] = temp; Так как каждый элемент массива v (т. е. lineptr) является указателем на символ, temp должен иметь тот же что и v - тогда можно будет осуществлять пересылки между temp и элементами v. Упражнение 5.7. Напишите новую версию которая запоминала бы строки в массиве, определенном в main, а не запрашивала память посредством программы Насколько быстрее эта программа? 5.7. Многомерные массивы В Си имеется возможность задавать прямоугольные многомерные мас- сивы, правда, на практике по сравнению с массивами указателей они ис- пользуются значительно реже. В этом параграфе мы продемонстрируем некоторые их свойства. Рассмотрим задачу перевода даты "день-месяц" в "день года" и обратно. Например, 1 марта - это 60-й день невисокосного или 61-й день високос- ного года. Определим две функции для этих преобразований: функция day_of _уеаг будет преобразовывать месяц и день в день года, a - день года в месяц и день. Поскольку последняя функция вычисляет два значения, аргументы месяц и день будут указателями. Так вызов 1988, 60,- &m, &d) присваивает переменной т значение 2, a d - 29 (29 февраля). __ Глава 5. Указатели и массивы Нашим функциям нужна одна и та же информация, а именно таблица, содержащая числа дней каждого месяца. Так как для високосного и неви- сокосного годов эти таблицы будут проще иметь две отдель- ные строки в двумерном массиве, чем во вычислений отслеживать особый случай с февралем. Массив и функции, выполняющие преобразо- вания, имеют следующий вид: static char = { 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31, 29, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31} /* определяет день года по месяцу и дню */ day_of_year(int int month, int day) < int i, leap; leap = == 0 && != 0 i == 0; for (i = 1; i < month; i++) day += return day; } /* определяет месяц и день по дню года */ void year, int yearday, int int *pday) { int i, leap; leap = year%4 == 0 && year%100 != 0 i year%400 == 0; for (i = 1; yearday > i++) yearday -= = i; *pday = yearday; } Напоминаем, что арифметическое значение логического выражения (на- пример выражения, с помощью которого вычислялось leap) равно либо нулю (ложь), либо единице (истина), так что мы можем использовать его как индекс в массиве daytab. Массив daytab должен быть внешним по отношению к обеим функци- ям day_of _yea r и так как он нужен и той и другой. Мы сделали его типа чтобы проиллюстрировать законность применения типа cha r для малых целых без знака. 5.7. Многомерные массивы Массив daytab - это первый массив из числа двумерных, с которыми мы еще не имели дела. Строго говоря, в Си двумерный массив рассматри- вается как одномерный массив, каждый элемент которого - также мас- сив. Поэтому индексирование изображается так: /* [строка] [столбец] */ а не так: daytab[i,j] /* НЕВЕРНО */ Особенность двумерного массива в Си заключается лишь в форме запи- си, в остальном его можно трактовать почти так же, как в других языках. Элементы запоминаются строками, следовательно, при переборе их том порядке, как они расположены в памяти, чаще будет изменяться самый правый индекс. Массив инициализируется списком начальных значений, заключенным в фигурные скобки; каждая строка двумерного массива инициализирует- ся соответствующим подсписком. Нулевой столбец добавлен в начало daytab лишь для того, чтобы индексы, которыми мы будем пользоваться, совпадали с естественными номерами месяцев от 1 до 12. Экономить пару ячеек памяти здесь нет никакого смысла, а программа, в которой уже не надо корректировать индекс, выглядит более ясной. Если двумерный массив передается функции в качестве аргумента, то объявление соответствующего ему параметра должно содержать количество столбцов; количество строк в данном случае несущественно, поскольку, как и прежде, функции будет передан указатель на массив строк, каждая из ко- торых есть массив из 13 значений типа В нашем частном случае мы име- ем указатель на объекты, являющиеся массивами из 13 значений типа Таким образом, если массив daytab передается некоторой функции то эту функцию можно было бы определить следующим образом: f ( i n t { } Вместо этого можно записать { } поскольку число строк здесь не имеет значения, или f(int { ... } Последняя запись объявляет, что параметр есть указатель на массив из 13 значений типа int. Скобки здесь необходимы, так как квадратные скобки [ имеют более высокий приоритет, чем Без скобок объявление int *daytab[13] определяет массив из 13 указателей на В более общем случае только Глава 5. Указатели и массивы первое измерение (соответствующее первому индексу) можно не задавать, все другие специфицировать необходимо. В параграфе 5.12 мы продолжим рассмотрение сложных объявлений. 5.8. В функциях и нет никаких проверок правильности вводимых дат. Устраните этот недостаток. 5.8. Инициализация массивов указателей Напишем функцию которая возвращает указатель на строку символов, содержащий название n-го месяца. Эта функция иде- альна для демонстрации использования статического массива. Функция имеет в своем личном распоряжении массив строк, на одну из которых она и возвращает указатель. Ниже покажем, как инициализи- руется этот массив имен. Синтаксис задания начальных значений аналогичен синтаксису пре- дыдущих инициализаций: /* возвращает имя n-го месяца */ char n) { static char = { "Неверный месяц", "Январь", "Февраль", "Март", "Апрель", "Май", "Июнь", "Июль", "Август", "Сентябрь", "Ноябрь", "Декабрь" } ; return (а < 1 n > 12) ? : } Объявление name массивом указателей на символы такое же, как и объяв- ление inept r в программе сортировки. Инициализатором служит спи- сок строк, каждой из которых соответствует определенное место в масси- ве. Символы i-й строки где-то размещены, и указатель на них запомина- ется в Так как размер массива name не компи- лятор вычислит его по количеству заданных начальных значений. 5.9. Указатели против многомерных массивов Начинающие программировать на Си иногда не понимают, в чем раз- ница между двумерным массивом и массивом указателей вроде name из приведенного примера. Для двух следующих определений: 5.9. Указатели против многомерных массивов 149 int int записи будут синтаксически правильным обращением к некоторому значению типа int. Однако только а является истинно дву- мерным массивом: для двухсот элементов типа int будет выделена па- мять, а вычисление смещения элемента от начала массива будет вестись по формуле 20 х строка + столбец, учитывающей его прямоугольную природу. Для b же определено только указателей, причем без инициализации. Инициализация должна задаваться явно - либо статически, либо в программе. Предположим, что каждый элемент b указывает на массив, в результате где-то будут вы- делены пространство, в котором разместятся 200 значений типа и еще ячеек для указателей. Важное преимущество массива указателей в том, что строки такого могут иметь разные длины. Таким образом, каждый элемент массива b не обязательно указывает на двадцатиэлемент- ный вектор; один может указывать на два элемента, другой - на пятьде- сят, а некоторые и вовсе могут ни на что не указывать. Наши рассуждения здесь касались целых значений, однако чаще мас- сивы указателей используются для работы со строками символов, разли- чающимися по длине, как это было в функции Сравните опре- деление массива указателей и соответствующий ему рисунок: char = месяц", Янв\0 с объявлением и рисунком для двумерного массива: aname[][15] = месяц", "Янв", "Февр", Янв\0 Март\0 15 30 45 Упражнение 5.9. Перепишите программы и используя вместо индексов указатели. 150 Глава 5. Указатели и массивы 5.10. Аргументы командной строки В операционной среде, обеспечивающей поддержку Си, имеется воз- можность передать аргументы или параметры запускаемой программе с помощью командной строки. В момент вызова main получает два аргу- мента. В первом, обычно называемом (сокращение от argument count), стоит количество аргументов, задаваемых в командной строке. Второй, rgv (от argument vector), является указателем на массив символьных строк, содержащих сами аргументы. Для работы с этими строками обычно ис- пользуются указатели нескольких уровней. Простейший пример - программа echo ("эхо"), которая печатает аргу- менты своей командной строки в одной строчке, отделяя их друг от друга пробелами. Так, команда echo Здравствуй, мир! напечатает Здравствуй, мир! По соглашению argv[0] есть имя вызываемой программы, так что значе- ние никогда не бывает меньше Если равен 1, то в командной строке после имени программы никаких аргументов нет. В нашем приме- ре агдс равен 3, и соответственно argv[0], и argv[2] суть строки "echo", и Первый необязательный аргумент - это ], последний - ]. Кроме того, стандарт требует, чтобы a r g v [ a r g c ] всегда был пустым указателем. argv: 0 Здравствуй, \0 Первая версия программы echo трактует как массив символьных указателей. tfinclude /* эхо аргументов командной строки: версия 1 */ Аргументы командной строки int i; for (i = i < argc; i++) (i < ? : return 0; Так как - это указатель на массив указателей, мы можем работать с ним как с указателем, а не как с индексируемым массивом. Следующая программа основана на приращении он приращивается так, что его значение в каждый отдельный момент указывает на очередной указатель на перебор указателей заканчивается, когда исчерпан argc. /* эхо аргументов командной строки; версия 2 */ argc, char { while > 0) (argc > 1) ? return 0; Аргумент a rgv указатель на начало массива строк аргументов. Исполь- зование в ++а rgv префиксного оператора приведет к тому, что первым будет напечатан a rgv[ 1 а не a rgv[ Каждое очередное приращение ука- зателя дает нам следующий аргумент, на который указывает В это же время значение уменьшается на 1, и, когда оно станет нулем, все аргументы будут напечатаны. Инструкцию p r i n t f можно было бы написать и так: printf((argc > 1) ? : Как видим, формат в p r i n t f тоже может быть выражением. В качестве второго примера возьмем программу поиска образца, рас- смотренную в параграфе 4.1, и несколько усовершенствуем ее. Если вы помните, образец для поиска мы "вмонтировали" глубоко в программу, а это, очевидно, не лучшее решение. Построим нашу программу по ана- логии с grep из т. е. так, чтобы образец для поиска задавался аргументом в командной строке. Глава 5. Указатели и массивы h> 1000 int getline(char *line, int max); -/* find: печать строк с образцом, заданным 1-м аргументом */ argc, char { char line [MAXLINE], int found = 0; if (argc != 2) в find else while MAXLINE) > 0) • if (strstr(line, != NULL) { printf line); found++; } return found; } Стандартная функция возвращает указатель на первую встре- тившуюся строку t в строке s или NULL, если таковой в s не встретилось. Функция объявлена в заголовочном файле Эту модель можно развивать и дальше, чтобы проиллюстрировать дру- гие конструкции с указателями. Предположим, что мы вводим еще два необязательных аргумента. Один из них предписывает печатать все стро- ки, кроме тех, в которых встречается образец; второй - перед каждой вы- водимой строкой печатать ее порядковый номер. По общему соглашению для Си-программ в системе UNIX знак минус перед аргументом вводит необязательный признак или параметр. Так, если -х служит признаком слова "кроме", которое изменяет задание на положное, а указывает на потребность в нумерации строк, то команда find -х -п образец напечатает все строки, в которых не найден указанный образец, и, кроме того, перед каждой строкой укажет ее номер. Необязательные аргументы разрешается располагать в любом порядке, при этом лучше, чтобы остальная часть программы не зависела от числа представленных аргументов. Кроме того, пользователю было бы удобно, если бы он мог комбинировать необязательные аргументы, например так: find образец 5.10. Аргументы командной строки А теперь запишем нашу программу. 1000 int getline(char *line, int max); /* печать строк образцами из 1-го аргумента */ angc, char { char long lineno = 0; int c, except = 0, number = 0, found = 0; while > 0 && (*++argv)[0] == while (c = switch (c) { case - except = break; case ' : number = break; printf( "find: неверный параметр с); argc = 0; found = break; } (argc != 1) find -x -n else while (getline(line, MAXLINE) > 0) { lineno++; if *argv) != NULL) != except) { if (number) lineno); line); found++; return found; } Глава 5. Указатели и массивы Перед получением очередного аргумента уменьшается на 1, a argv "перемещается" на следующий аргумент. После завершения цикла при отсутствии ошибок а содержит количество еще не обработанных аргу- ментов, a указывает на первый из них. Таким образом, должен быть равен а rgv указывать на образец. Заметим, что rgv является указателем на аргумент-строку, a - первым символом, на который можно сослаться и другим способом: Поскольку оператор индексирования [ ] имеет более высокий приоритет, чем * и ++, круглые скобки здесь обязательны, без них выражение тракто- валось бы так же, как Именно такое выражение мы приме- ним во внутреннем цикле, где просматриваются символы конкретного ар- гумента. Во внутреннем цикле выражение приращивает ука- затель Потребность в более сложных выражениях для указателей возникает так уж часто. Но если такое случится, то разбивая процесс вычисления указателя на два или три шага, вы облегчите восприятие этого выражения. Упражнение 5.10. Напишите программу интерпретирующую обратную польскую запись выражения, задаваемого командной строкой, в которой каждый оператор и операнд представлены отдельным аргу- ментом. Например, • ехрг 2 3 4 + * вычисляется так же, как выражение 2 х (з + 4). Упражнение 5.11. Усовершенствуйте программы entab и (см. упражнения 1.20 и таким образом, чтобы через аргументы можно было задавать список табуляции. Упражнение 5.12. Расширьте возможности entab и detab таким образом, чтобы при обращении вида entab -т +п "стопы" табуляции начинались с позиции и выполнялись через каж- дые п позиций. Разработайте удобный для пользователя вариант поведе- ния программы по умолчанию (когда нет никаких аргументов). Упражнение 5.13. Напишите программу tail, печатающую п последних введенных строк. По умолчанию значение п равно но при желании п можно задать с помощью аргумента. Обращение вида tail -п Указатели на функции печатает п последних строк. Программа должна вести себя осмысленно при любых входных данных и любом значении п. Напишите программу так, чтобы наилучшим образом использовать память; запоминание строк организуйте, как в программе сортировки, описанной в параграфе 5.6, а не на основе двумерного массива с фиксированным размером строки. Указатели на функции В Си сама функция не является переменной, но можно определить ука- затель на функцию и работать с ним, как с обычной переменной: присва- размещать в массиве, передавать в качестве параметра функции, возвращать как результат из функции и т. д. Для иллюстрации этих воз- можностей воспользуемся программой сортировки, которая уже встре- чалась в настоящей главе. Изменим ее так, чтобы при задании необяза- тельного аргумента -п вводимые строки упорядочивались по их числово- му а не в лексикографическом порядке. Сортировка, как правило, распадается три части: на сравнение, опре- деляющее упорядоченность пары объектов; перестановку, меняющую местами пару объектов, и сортирующий алгоритм, который осуществля- ет сравнения и перестановки до тех пор, пока все объекты не будут упоря- дочены. Алгоритм сортировки не зависит от операций сравнения и пере- становки, так что передавая ему в качестве параметров различные функ- ции сравнения и перестановки, его можно настроить на различные крите- рии сортировки. Лексикографическое сравнение двух строк выполняется функцией st (мы уже использовали эту функцию в ранее рассмотренной про- грамме сортировки); нам также потребуется программа сравнива- ющая две строки как числовые значения и возвращающая результат срав- нения в том же виде, в каком его выдает st Эти функции объявляют- ся перед main, а указатель на одну из них передается функции Что- бы сосредоточиться на главном, мы упростили себе задачу, отказавшись от анализа возможных ошибок при задании аргументов. h> 5000 /* максимальное число строк */ char /* указатели на строки текста */ int int nlines); void *lineptr[], int nlines); __ _ Глава 5. Указатели и массивы void qsort(void *lineptr[], int left, int right, int *, void *)); int *, char *); /* сортировка строк */ main(int argc, char { int nlines; /* количество прочитанных строк */ int numeric = 0; /* 1, если по знач. */ if (argc > 1 && == 0) numeric = if = MAXLINES)) >= 0) { **) lineptr, 0, (int ? : strcmp)); nlines); return 0; } else { слишком много return В обращениях к функциям qsort, strcmp и numcmp их имена трактуются как адреса этих функций, поэтому оператор & перед ними не нужен, как он не был нужен и перед именем массива. Мы написали rt так, чтобы она могла обрабатывать данные любого типа, а не только строки символов. Как видно из прототипа, функция qso rt в качестве своих аргументов ожидает массив указателей, два целых значе- ния и функцию с двумя аргументами-указателями. В качестве аргумен- тов-указателей заданы указатели обобщенного типа void Любой указа- тель можно привести к типу void * и обратно без потери информации, по- этому мы можем обратиться к q s o r t , предварительно преобразовав аргументы в void*. Внутри функции сравнения ее аргументы будут при- ведены к нужному ей типу. На самом деле эти преобразования никакого влияния на представления аргументов не оказывают, они лишь обеспе- чивают согласованность типов для компилятора. /* qsort: сортирует по возрастанию */ void int left, int right, *, void *)) Указатели на функции _ i, last; void *v[], int, int); if (left >= right) ничего не делается, если */ return; /* в массиве менее двух элементов */ swap(v, left, (left + last = left; for (i = i <= right; i++) if < 0) ++last, i); swap(v, left, last); qsort(v, left, comp); qsort(v, right, comp); } Повнимательней приглядимся к объявлениям. Четвертый параметр функ- ции int *, void *) сообщает, что comp - это указатель на функцию, которая имеет два аргу- мента-указателя и выдает результат типа Использование comp в строке if < 0) согласуется с объявлением "comp - это указатель на функцию", и, следо- вательно, - это функция, а - обращение к ней. Скобки здесь чтобы обеспечить правильную трактовку объявления; без них объявление int *, void *) /* НЕВЕРНО */' говорило бы, что comp - это функция, возвращающая указатель на int, а это совсем не то, что требуется. Мы уже рассматривали функцию сравнивающую две строки. Ниже приведена функция которая сравнивает две строки, рассмат- ривая их как числа; предварительно они переводятся в числовые значе- ния функцией /* numcmp: сравнивает s1 и s2 как числа */ 158 Глава 5. Указатели и массивы int *s1, char *s2) { double v2; v1 = atof(s1); v2 = atof(s2); if (v1 < v2) return if (v1 > v2) return else return 0; } Функция swap, меняющая местами два указателя, идентична той, что мы привели ранее в этой главе за исключением того, что объявления ука- зателей заменены на void swap(void *v[], int i, int j) { void temp = v[i] = v[j] = temp; } Программу сортировки можно дополнить и множеством других возмож- ностей; реализовать некоторые из них предлагается в качестве упражнений. Упражнение 5.14. Модифицируйте программу сортировки, чтобы она ре- агировала на параметр указывающий, что объекты нужно сортировать в обратном порядке, т. е. в порядке убывания. Обеспечьте, чтобы работал и вместе с -п. Упражнение 5.15. Введите в программу необязательный параметр задание которого делало бы неразличимыми символы нижнего и верхнего регистров (например, а и А должны оказаться при сравнении равными). Упражнение 5.16. Предусмотритев программе необязательный параметр -d, который заставит программу при сравнении учитывать только буквы, цифры и пробелы. Организуйте программу таким образом, чтобы этот параметр мог работать вместе с параметром ' 5.12. Сложные объявления Упражнение 5.17. Реализуйте в программе возможность работы с полями: возможность сортировки по полям внутри строк. Для каждого поля предусмотрите свой набор параметров. Предметный указатель этой упорядочивался с параметрами: для терминов и для номеров страниц. Сложные объявления Иногда Си ругают за синтаксис объявлений, особенно тех, которые со- держат в себе указатели на функции. Таким синтаксис получился в ре- зультате нашей попытки сделать похожими объявления объектов и их использование. В простых случаях этот синтаксис хорош, однако в слож- ных ситуациях он вызывает затруднения, поскольку объявления перена- сыщены скобками и их невозможно читать слева направо. Проблему ил- люстрирует различие следующих двух объявлений: int /* f: функция, возвращающая ук-ль на int */ int (*pf)(); /* pf: ук-ль на ф-цию, возвращающую int */ Приоритет префиксного оператора * ниже, чем приоритет поэтому во втором случае скобки необходимы. Хотя на практике по-настоящему сложные объявления встречаются редко, все же важно знать, как их понимать, а если потребуется, и как их конструировать. Укажем хороший способ: объявления можно синтезировать, двигаясь небольшими шагами с помощью этот способ рассмотрен в пара- графе 6.7. В настоящем параграфе на примере двух программ, осуществ- ляющих преобразования правильных Си-объявлений в соответствующие им словесные описания и обратно, мы демонстрируем иной способ конст- руирования объявлений. Словесное описание читается слева Первая программа, - более сложная. Она преобразует Си-объяв- ления в словесные описания так, как показано в следующих примерах: char **argv argv: на на char int daytab: на из int int (*daytab)[13] daytab: из на int void ' Имеется в виду оригинал книги языке. — Примеч. пер. Глава 5. Указатели и массивы функц. возвр. на void void сотр: на функц. возвр. void char (*(*x())[])() х: функц. возвр. на из на функц. возвр. char char (*(*x[3])())[5] х: из на функц. возвр. на из char Функция в своей работе использует грамматику, специфициру- ющую объявитель. Эта грамматика строго изложена в параграфе 8.5 приложения А, а в упрощенном виде записывается так: необязательные * имя собственно-объявителъ Говоря простым языком, есть собственно-объявителъ, перед ко- торым может стоять * (т. е. одна или несколько звездочек), где собственно- объявителъ есть имя, или объявитель в скобках, или собственно-объя- вителъ с последующей парой скобок, или собственно-объявителъ с после- дующей парой квадратных скобок, внутри которых может быть помещен размер. Эту грамматику можно использовать для грамматического разбора объявлений. Рассмотрим, например, такой объявитель: (*pfa[])() Имя pf а будет классифицировано как имя и, следовательно, как собствен- но-объявителъ. Затем pf [ ] будет распознано как собственно-объявителъ, a *pf а[ ] - как и, следовательно, есть собственно-объя- вителъ. Далее, есть собственно-объявителъ и, таким образом, Этот грамматический разбор можно проиллюстрировать де- ревом разбора, приведенным на следующей странице (где собственно- объявителъ обозначен более коротко, а именно Сердцевиной программы обработки объявителя является пара функ- ций и осуществляющих грамматический разбор объявления согласно приведенной грамматике. Поскольку грамматика определена рекурсивно, эти функции обращаются друг к другу рекурсивно, по мере распознавания отдельных частей объявления. Метод, примененный в об- суждаемой программе для грамматического разбора, называется рекур- сивным спуском. Сложные объявления 161 pfa [] имя О объяв. /* разбор объявителя */ void dcl(void) int ns; for (ns = 0; gettoken() /* подсчет звездочек */ ns++; while > 0) /* разбор собственно объявителя */ void dlrdcl(void) int type; if (tokentype /* ( ) */ if (tokentype пропущена } else if (tokentype == NAME) /* имя переменной */ else должно быть name или while((type = == PARENS type == BRACKETS) if (type == PARENS) strcat(out, else { strcat(out, 1116 |