Date Редакция Категория comp Теги C / K&R

Упражнение 5.1. Функция getint написана так, что знаки - или +, за которыми не следует цифра, она понимает как "правильное" представление нуля. Скорректируйте программу таким образом, чтобы в подобных случаях она возвращала прочитанный знак назад во ввод.

Вот getint(), что называется, "от классиков":

 /* getint: читает следующее целое из ввода в *pn */
 int getint(int *pn)
 {
     int c, sign;

     while (isspace(c = getch())); /* пропуск символов-разделителей */

     if (!isdigit(c) && c != EOF && c != ' && c != '-') {
         ungetch(c); /* не число */
         return 0;
     }
     sign = (c =='-') ? -1 : 1;
     if (c == ' || c == '-')
         c = getch();
     for (*pn = 0; isdigit(c); c = getch())
         *pn = 10 * *pn + (c - '0');
     *pn *= sign;
     if (c != EOF)
         ungetch(c);
     return c;
 }

Обратите внимание на ungetch(c) в условном операторе проверки на "не-число". Как только функция встречает символ, не являющийся числом, она возвращает его снова на ввод при помощи ungetch() и его придется обрабатывать вновь и вновь. Таким образом, если массив символов, например, начитается с нечислового символа, то чисел в итоге мы так и не дождемся:

mgetint00.png

Вывод: убираем этот ungetch().

Следующий шаг: если считанный символ является знаком, то нужно считать еще один символ. Если тот не является числом, то возвращаем в поток знак. Определить какой именно знак возвращать можно по переменной sign.

Теперь займемся собственно упражнением. Вот полный код:

#include <stdio.h>
#include <ctype.h>

#define SIZE 20  /* макс. размер строки ввода */

int main(void)
{
    int i, type, array[SIZE], getint(int *);

    for (i = 0; i < SIZE && (type = getint(&array[i])) != EOF; i++)
        printf("array[%d] = %d %s\n", i, type ? array[i] : type,
               type ? "" : "is not a number");

    return 0;
}

int getch (void);
void ungetch (int);

/* getint: читает следующее целое из ввода в *pn */
int getint(int *pn)
{
    int c, sign;

    while (isspace(c = getch())); /* пропуск символов-разделителей */

    if (!isdigit(c) && c != EOF && c != ' && c != '-') {
        /*  ungetch(c); */
        return 0;
    }
    sign = (c =='-') ? -1 : 1;
    if (c == ' || c == '-') {
    c = getch();
    if (!isdigit(c)) {
        ungetch(sign == 1 ? ' : '-');
        return 0;
    }
    }
    for (*pn = 0; isdigit(c); c = getch())
        *pn = 10 * *pn + (c - '0');
    *pn *= sign;
    if (c != EOF)
        ungetch(c);
    return c;
}

char buf[SIZE];       /* буфер для ungetch */
int bufp = 0;         /* след. свободная позиция в буфере */

int getch(void)       /* взять (возможно возвращенный) символ */
{
    return (bufp > 0) ? buf[--bufp] : getchar();
}

void ungetch(int c)   /* вернуть символ на ввод */
{
    if (bufp >= SIZE)
        printf("ungetch: слишком много символов\n");
    else
        buf[bufp++] = c;
}

и результат:

mgetint10.png

Упражнение 5.2. Напишите функцию getfloat — аналог getint для чисел с плавающей точкой. Какой тип будет иметь результирующее значение, задаваемое функцией getfloat?

В п. 4.2 приведена функция atof(), преобразующая строку в double. Заимствуя ее идею, получим:

#include <stdio.h>
#include <ctype.h>

#define SIZE 20  /* макс. размер строки ввода */

int main(void)
{
    int i, type, getfloat(double *);
    double array[SIZE];

    for (i = 0; i < SIZE && (type = getfloat(&array[i])) != EOF; i++)
        printf("array[%d] = %f %s\n", i, type ? array[i] : type, 
               type ? "" : "is not a number");

    return 0;
}

int getch (void);
void ungetch (int);

/* getfloat: читает следующее целое из ввода в *pn */
int getfloat(double *pn)
{
    int c, sign;
    float power;

    while (isspace(c = getch())); /* пропуск символов-разделителей */

    if (!isdigit(c) && c != EOF && c != ' && c != '-') {
        return 0;
    }
    sign = (c =='-') ? -1 : 1;
    if (c == ' || c == '-') {
    c = getch();
    if (!isdigit(c)) {
        ungetch(sign == 1 ? ' : '-');
        return 0;
    }
    }
    for (*pn = 0.0; isdigit(c); c = getch())
        *pn = 10.0 * *pn + (c - '0');
    if (c == '.')
        c = getch();
    for (power = 1.0; isdigit(c); c = getch()) {
        *pn = 10.0 * *pn + (c - '0');
        power *= 10.0;
    }
    *pn *= sign / power;
    if (c != EOF)
        ungetch(c);
    return c;
}

В результате:

mgetfloat0.png

В дополнительном вопросе говорится, по-видимому, о типе возвращаемого функцией значения. Оно может оставаться целым или становится вещественным. Это неважно, поскольку это — лишь признак числа, а само преобразованное вещественное число хранится в массиве array[].

Упражнение 4.2 показывает как справляться с обработкой экспоненциального представления действительных чисел.

Упражнение 5.3. Используя указатели, напишите функцию strcat, которую мы рассматривали в главе 2 (функция strcat(s,t) копирует строку t в конец строки s).

Вот оригинал:

 #include <stdio.h>

 void new_strcat(char s[], char t[]);

 int main()
 {
     char s[] = "Hello,";
     printf("s = %s\n", s);  

     char t[] = " world";
     printf("t = %s\n", t);

     new_strcat(s, t);

     printf("st = %s\n", s);

     return 0;
 }

 /* new_strcat: помещает t в конец s; s достаточно велика */
 void new_strcat(char s[], char t[])
 {
     int i, j;
     i = j = 0;
     while (s[i] != '\0') /* находим конец s */
         i++;
     while ((s[i++] = t[j++]) != '\0'); /* копируем t */
 }

mstrcat00.png

strcat переименована в new_strcat из-за совпадения имен с функцией из string.h. К ошибке это не приводит, но выдается предупреждение, а оно нам надо?

Кстати, вы заметили, что в конце всем знакомой строки нет восклицательного знака? Это потому, что иначе возникает ошибка: Stack smashing detected. Ее причины и способы преодоления. Я преодолел тем, что задал s[20].

Но — к делу. Примеры переработки функций, использующих массивы, в функции с указателями приведены в п. 5.5. Берем их за основу. Итак:

 #include <stdio.h>

 #define SIZE 20

 void new_strcat(char *, char *);

 int main()
 {
     char s[SIZE] = "Hello,";
     char t[SIZE] = " world!";

     printf("s = %s\n", s);  
     printf("t = %s\n", t);

     new_strcat(s, t);
     printf("s+t = %s\n", s);

     return 0;
 }

 /* new_strcat: помещает t в конец s; s достаточно велика */
 void new_strcat(char *ps, char *pt)
 {
     while (*ps) ps++; /* находим конец s */
     while ((*ps++ = *pt++)); /* копируем t */
 }

Упражнение 5.4. Напишите функцию strend(s,t), которая выдает 1, если строка t расположена в конце строки s, и нуль в противном случае.

 #include <stdio.h>
 #include <string.h>

 int strend(char *, char *);

 int main()
 {
     char s1[] = "test stri string\0";
     printf("s1 = %s\n", s1);  

     char s2[] = "ring\0";
     printf("s2 = %s\n", s2);

     printf("s2 is in the end of s1 = %s\n", strend(s1, s2) ? "yes" : "no");

     return 0;
 }

 /* strend: возвращает 1, если s2 находится в конце s1 */
 int strend(char *ps1, char *ps2)
 {   
     char *tmp;
     int n;

     while (*ps1) {
         while (*ps1++ != *ps2); /* прокручиваем s1 до 1-го элемента s2 */
         tmp = ps2;
         ps1--;
         for (n = 0; *tmp && *ps1++ == *tmp++; n++); /* n элементов совпадают */
         if (n == strlen(ps2)) 
             return 1;
     }
     return 0;
 }

Упражнение 5.5. Напишите варианты библиотечных функций strncpy, strncat и strncmp, которые оперируют с первыми символами своих аргументов, число которых не превышает n. Например, strncpy(t,s,n) копирует не более n символов t в s. Полные описания этих функций содержатся в приложении B.

 /* strncpy: копирует n символов из t в s */
 void strncpy(char *s, char *t, int n)
 {
     int i = 0;

     while (i++ < n && (*s++ = *t++));
 }

 /* strncat: помещает n символов из t в конец s */
 void strncat(char *ps, char *pt, int n)
 {
     int i = 0;

     while (*++ps); /* находим конец s */
     while (i++ < n && (*ps++ = *pt++)); /* копируем t */
 }

 /* strncmp: выдает < 0 при s < t, 0 при s == t, > 0 при s > t */
 int strncmp(char *s, char *t, int n)
 {
     int i = 0;

     while (i++ < n && *s++ == *t++)
         if (*(s-1) == '\0')
             return 0;

     return *(s-1) - *(t-1);
 }

Упражнение 5.6. Отберите подходящие программы из предыдущих глав и упражнений и перепишите их, используя вместо индексирования указатели. Подойдут, в частности, программы getline (главы 1 и 4), atoi, itoa и их варианты (главы 2, 3 и 4), reverse (глава 3), а также strindex и getop (глава 4).

getline() (у нас — getl()):

 #include <stdio.h>

 #define MAXLINE 50   /* максимальная длина строки ввода */

 int getl(char *, int);

 int main()
 {
     char line[MAXLINE]; /* текущая строка */
     int len = 0;

     while ((len = getl(line, MAXLINE)) > 0) {
         printf("len = %d; line = %s\n", len, line);
     }
     return 0;
 }

 /* getl: читает строку в s, возвращает длину */
 int getl(char *ps, int lim)
 {
     int c;
     char *start = ps;

     while (--lim > 0 && (c=getchar()) != EOF && c != '\n')
         *ps++ = c;
     if (c == '\n')
         *ps++ = c;
     *ps = '\0';
     return ps-- - start;
 }

atoi():

 #include <stdio.h>
 #include <ctype.h>

 int atoi(char *);

 int main()
 {
     char s[] = "    -1224";

     printf("string=%s, int=%d\n", s, atoi(s));

     return 0;
 }

 /* atoi: преобразование s в целое число; версия 3 */
 int atoi(char *s)
 {
     int sign;
     int n = 0;
                             /* игнорировать символы-разделители */
     while (isspace(*s++));
     sign = ( *--s == '-' ) ? -1 : 1;
     if (*s == ' || *s == '-') /* пропуск знака */
         *s++;
     while (isdigit(*s))
         n = 10 * n + (*s++ - '0');    
     return sign * n;
 }

itoa() и reverse():

 #include <stdio.h>
 #include <string.h>

 #define SIZE 20

 void itoa(int, char *);
 void reverse(char *);

 int main()
 {
     int n =-1224;
     char s[SIZE];

     itoa(n, s);

     printf("int=%d, string=%s\n", n, s);

     return 0;
 }

 /* itoa: преобразование целого n в строку s */
 void itoa(int n, char *s)
 {
     int sign;
     char *ps = s;

     if ((sign = n) < 0) /* сохраняем знак */
         n =-n;          /* делаем n положительным */

     do { /* генерируем цифры в обратном порядке */
         *ps++ = n % 10 + '0'; /* следующая цифра */
     } while ((n /= 10) > 0); /* исключить ее */
     if (sign < 0)
         *ps++ = '-';
     *ps = '\0';
     reverse(s);
 }

 /* reverse: переворачивает строку s (результат в s) */
 void reverse(char *s)
 {
     int c, i, j;

     for (i = 0, j = strlen(s)-1; i < j; i++, j--) {
         c = *(s+i);
         *(s+i) = *(s+j);
         *(s+j) = c;
     }
 }

strrindex():

 #include <stdio.h>

 #define MAXLINE 1000 /* максимальный размер вводимой строки */

 int getl(char *, int);
 int strrindex(char *, char *);

 char pattern[] ="ould"; /* образец для поиска */

 /* найти все строки, содержащие образец */
 int main()
 {
     char line[MAXLINE];
     int found = 0;
     int rind;

     while (getl(line, MAXLINE) > 0)
         if ((rind = strrindex(line, pattern)) >= 0) {
                 printf ("%d-%s", rind, line);
                 found++;
         }
     return found;
 }

 /* getl: читает строку в s, возвращает длину */
 int getl(char *s, int lim)
 {
     int c;
     char *ps = s;

     while (--lim > 0 && (c=getchar()) != EOF && c != '\n')
         *s++ = c;
     if (c == '\n')
         *s++ = c;
     *s = '\0';
     return s-- - ps;
 }

 /* strrindex: вычисляет выдает позицию самого правого вхождения t в s 
 * или выдает -1, если t нет в s                                      */
 int strrindex (char *s, char *t)
 {
     int i, tmp = -1;
     char *ps, *pt, *pstrbeg;

     pstrbeg = s;
     while (*s++) {
         for (ps = s, pt = t; *pt && *ps++ == *pt++;);
         i = &(*--ps) - pstrbeg;
         if (!*pt && i > tmp)
             tmp = i;
     }
     return tmp;
 }

getop() (остальные функции, включая main(), есть в решениях упражнений 4.2—4.10.):

 #include <ctype.h>

 /* getop: получает следующий оператор или операнд */
 int getop(char *s)
 {
     int c;
     while ((*s = c = getch()) == ' ' || c == '\t');
     *(s+1) = '\0';
     if (!isdigit(c) && c != '.')
         return c;   /* не число */
     if (isdigit(c)) /* накапливаем целую часть */
         while (isdigit(*++s = c = getch()));
     if (c =='.') /* накапливаем дробную часть */
         while (isdigit(*++s = c = getch()));
     *s = '\0';
     if (c != EOF)
         ungetch(c);
     return NUMBER;
 }

Упражнение 5.7. Напишите новую версию readlines, которая запоминала бы строки в массиве, определенном в main, а не запрашивала память посредством программы alloc. Насколько быстрее эта программа?

Переписанные функции:

 #include <stdio.h>
 #include <string.h>

 #define MAXLINES 5000 /* максимальное число строк */
 #define ALLOCSIZE 10000 /* размер доступного пространства */

 char *lineptr[MAXLINES]; /* указатели на строки */

 int readlines(char *lineptr[], int nlines, char *linestore);
 void writelines(char *lineptr[], int nlines);

 /* сортировка строк */
 int main()
 {
     char allocbuf[ALLOCSIZE]; /* массив для хранения строк */
     int nlines; /* количество прочитанных строк */

     if ((nlines = readlines(lineptr, MAXLINES, allocbuf)) >= 0) {
         printf("nlines=%d\n", nlines);
         writelines(lineptr, nlines);
         return 0;
     } else {
         printf("ошибка: слишком много строк\n");
         return 1;
     }
 }

 #define MAXLEN 1000 /* максимальная длина строки */
 int getl(char *, int);

 /* readlines: чтение строк */
 int readlines(char *lineptr[], int maxlines, char *linestore)
 {
     int len, nlines;
     char *p, line[MAXLEN];

     nlines = 0;
     p = linestore + strlen(linestore);
     while ((len = getl(line, MAXLEN)) > 0)
         if (nlines >= maxlines || (len + strlen(linestore)) >= ALLOCSIZE)
             return -1; 
         else {
             line[len-1] = '\0'; /* убираем символ \n */
             strcpy(p, line);
             lineptr[nlines++] = p;
             p += len;
         } 
     return nlines;
 }

readlines() пополнилась еще одним аргументом — массивом для хранения строк linestore. Непревышение размера этого массива проверяется условием (len + strlen(linestore)) >= ALLOCSIZE.

К сожалению, сравнить скорость работы обоих вариантов readlines() не получилось, т. к. даже прежний вариант функции работает достаточно быстро и clock() выдает время выполнения 0 секунд. Поэтому для проверки нужно либо вставлять большой кусок текста (сотни строк), либо прогонять функцию в цикле. Но последний вариант как раз для функции readlines() не удобен.

Техника проверки скорости работы программы с помощью функции clock():

до проверяемой функции:

start = clock()

после неё:

finish = (clock() - start)/CLOCKS_PER_SEC

и finish — на печать.

Упражнение 5.8. В функциях day_of_year и month_day нет никаких проверок правильности вводимых дат. Устраните этот недостаток.

Предположим, что проблемы могут быть только в диапазоне задаваемых дат (а не, например, в их типе данных). Тогда:

 #include <stdio.h>

 int day_of_year(int, int, int);
 int month_day(int, int, int *, int *);

 int main()
 {   
     int year = 2012, date = 60, month = 2, day = 29;
     int m, d;

     month_day(year, date, &m, &d);
     printf("%dth day in year %d -> month=%d, day=%d\n", 
                                             date, year, m, d);
     printf("month=%d, day=%d -> %dth day in year %d\n", 
                             month, day, day_of_year(year, month, day), year);

     year = 1917;
     if (month_day(year, date, &m, &d) !=-1) {
         printf("%dth day in year %d -> month=%d, day=%d\n", 
                                             date, year, m, d);
     }
     else {
         printf("error in month_day\n");
     }
     if (day_of_year(year, 2, 29) !=-1) {
         printf("month=%d, day=%d -> %dth day in year %d\n", 
                                 month, day, day_of_year(year, month, day), year);
     }
     else {
         printf("error in day_of_year\n");
     }


     return 0;
 }

 static char daytab[2][13] =  {
     {0, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31},
     {0, 31, 29, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31},
 };

 /* day_of_year: определяет день года по месяцу и дню */
 int day_of_year(int year, int month, int day)
 {
     int i, leap;

     // Отсчет начнем с 1918 -- года перехода на грегорианский календарь
     if (year < 1918 || month < 1 || month > 12 || day < 1)
         return -1;

     leap = (year % 4 == 0 && year % 100 !=0) || (year % 400 == 0);
     for (i = 1; i < month; i++)
         day += daytab[leap][i];
     return day;
 }

 /* month_day: определяет месяц и день по дню года */
 int month_day(int year, int yearday, int *pmonth, int *pday)
 {
     int i, leap;

     if (year < 1918 || yearday < 1 || yearday > 366)
         return -1;

     leap = (year % 4 == 0 && year % 100 != 0) || (year % 400 == 0);
     for (i = 1; yearday > daytab[leap][i]; i++)
         yearday -= daytab[leap][i];
     *pmonth = i;
     *pday = yearday;

     return 0;
 }

mdays10.png

Упражнение 5.9. Перепишите программы day_of_year и month_day, используя вместо индексов указатели.

 /* day_of_year: определяет день года по месяцу и дню */
 int day_of_year(int year, int month, int day)
 {
     int i, leap;
     char *tmp;

     // Отсчет начнем с 1918 -- года перехода на грегорианский календарь
     if (year < 1918 || month < 1 || month > 12 || day < 1)
         return -1;

     leap = (year % 4 == 0 && year % 100 !=0) || (year % 400 == 0);
     tmp = &daytab[leap][1];
     for (i = 1; i < month; i++)
         day += *tmp;
     return day;
 }

 /* month_day: определяет месяц и день по дню года */
 int month_day(int year, int yearday, int *pmonth, int *pday)
 {
     int i, leap;
     char *tmp;

     if (year < 1918 || yearday < 1 || yearday > 366)
         return -1;

     leap = (year % 4 == 0 && year % 100 != 0) || (year % 400 == 0);
     tmp = &daytab[leap][1];
     for (i = 1; yearday > *tmp; i++)
         yearday -= *tmp;
     *pmonth = i;
     *pday = yearday;

     return 0;
 }

Упражнение 5.10. Напишите программу expr, интерпретирующую обратную польскую запись выражения, задаваемого командной строкой, в которой каждый оператор и операнд представлены отдельным аргументом. Например,

expr 2 3 4 + * 

вычисляется так же, как выражение 2(3+4).*

Возьмем за основу программу calc.c, развивавшуюся в упражнениях 4.3-4.10 (ее простейший вариант, с целыми числами). Поскольку данные считываются из командной строки, то функции getch() и ungetch() нам больше не нужны. Задача функции getop() сводится к тому, чтобы определить, является ли очередной аргумент числом, что позволяет предельно ее упростить (не надо, в частности, заботиться об удалении лишних пробелов — это делает операционная система).

В результате получаем код, в котором без изменений остались push() pop():

 #include <stdio.h>
 #include <stdlib.h>

 #define MAXOP 100  /* макс. размер операнда или оператора */
 #define NUMBER '0' /* признак числа */

 int getop (char *);
 void push (int);
 int pop (void);


 /* калькулятор с обратной польской записью */
 int main(int argc, char *argv[])
 {
     int c;
     int op2;
     int err=0;
     char s[MAXOP];   

     while (--argc > 0 && (c = getop(*++argv))) {
         switch (c) {
         case NUMBER:
             push (atoi(*argv));
             break;
         case ':
             push (pop() + pop());
             break;
         case '*':
             push (pop() * pop());
             break;
         case '-':
             op2 = pop();
             push (pop() - op2);
             break;
         case '/':
             op2 = pop();
             if (op2 != 0)
                 push (pop() / op2);
             else
                 printf("ошибка: деление на нуль\n");
             break;
         default:
             err = 1;
             printf("ошибка: неизвестная операция %s\n", s);
             break;
         }
     }
     if (!err)
         printf("\t%d\n", pop());

     return 0;
 }


 #define MAXVAL 10  /* максимальная глубина стека */

 int sp = 0;         /* следующая свободная позиция в стеке */
 int val[MAXVAL]; /* стек */

 /* push: положить значение i в стек */ 
 void push(int i)
 {   
     if (sp < MAXVAL){
         val[sp++] = i;
     }
     else
         printf("ошибка: стек полон, %d не помещается\n", i);
 }

 /* pop: взять с вершины стека и выдать в качестве результата */
 int pop(void)
 {   
     if (sp > 0) {
         return val[--sp];
     }
     else {
         printf ("ошибка: стек пуст\n");
         return 0;
     }
 }

 #include <ctype.h>
 #include <string.h>

 /* getop: получает следующий оператор или операнд */
 int getop(char *s)
 {
     int c = strlen(s);
     int p = 0;
     char *tmp = s;

     while (isdigit(*tmp++))
         p++;
     if (p != c){
         return *s;    /* не число */
     }
     else {
         return NUMBER;
     }
 }

Однако это еще не все. Встретив в командной строке "звездочку" (операцию умножения) система, по-видимому, трактует ее как подстановочный символ. Поэтому приходится "звездочку" экранировать:

expr0.png

Упражнение 5.11. Усовершенствуйте программы entab и detab (см. упражнения 1.20 и 1.21) таким образом, чтобы через аргументы можно было задавать список "стопов" табуляции.

Традиционно позиции табуляции располагаются каждые 8 знакомест, в колонках 1, 9, 17, 25 и т. д. Эти номера колонок и являются теми "стопами", о которых говорится в задаче. Правда, чтобы понять, что K&R имеют в виду именно это, мне пришлось почитать книжку Тондо и Гимпела. Оказывается, что эти авторы позаимствовали идею решения... у самого Кернигана — в книге Кернигана и Плоджера "Software Tools in Pascal" (p. 20—33). Поскольку там все на паскале и на английском, то сначала реализуем функции detab и entab по Кернигану и Плоджеру, а затем добавим возможность обработки аргументов командной строки.

К тому же решений упражнений 1.20, 1.21 обнаружилась одна неприятная подробность — они неправильны, т. к. решают другую задачу: вместо стопов в заданных позициях они заменяют каждый символ табуляции заданным числом пробелов.

Создадим в файле sample.txt текст с табуляциями, и обработаем его detab'ом, преобразовав в файл detabbed.txt: ./detab < sample.txt > detabbed.txt

Вот что получается:

sample.png

Так что там у Кернигана с Плоджером? Задача функции detab — выводить пробелы. Кроме того вводятся еще две вспомогательные функции: инициализация массива стопов табуляции (settabs) и проверка, является ли данная позиция — стопом (tabpos).

Псевдокодом логика работы detab запишется так:

инициализировать массив стопов табуляции tabstops col = 1 while (getchar(c) != ENDFILE) if (c == TAB) печатать пробелы until (tabpos(col, tabstops)) else if (c == NEWLINE) putchar(c) col = 1 else putchar(c) col = col + 1

Запишем это на C:

 #include <stdio.h>

 #define MAXLINE 72   /* максимальный размер строки табуляций */
 #define TABSIZE 4    /* размер табуляции в пробелах */

 void detab(int []);
 void settabs(int []);

 int main()
 {
     int tabstops[MAXLINE];

     settabs(tabstops);
     detab(tabstops);

     return 0;
 }

 void settabs(int tabstops[])
 {
     int i;
     for (i=0; i < MAXLINE; i++)
         tabstops[i] = (i % TABSIZE == 0);
 }

 int tabpos(int, int []);

 /* detab: преобразует символы табуляции в пробелы */
 void detab(int tabstops[])
 {
     int col = 0;
     char c;

     while ((c = getchar()) != EOF) {
         if (c == '\t') {
             do
                 putchar(' ');
             while (!tabpos(++col, tabstops));
         }
         else if (c == '\n') {
             putchar(c);
             col = 0;
         }
         else {
             putchar(c);
             ++col;
         }
     }
 }

 int tabpos(int col, int tabstops[])
 {
     if (col > MAXLINE)
         return 1;
     else
         return tabstops[col];
 }

И здесь я влетел. Тесты в командной строке (и проверка логики программы) показывали, что все работает правильно, но файл с примером детабулировался некорректно. Всё дело было в русских буквах!

По умолчанию тип char или signed char интерпретируется как однобайтовая целая величина со знаком и с диапазоном значений от минус 128 до 127, хотя только значения в диапазоне 0 – 127 имеют символьные эквиваленты. Для представления символов русского алфавита модификатор типа идентификатора данных имеет вид unsigned char (от 0 до 255), так как коды русских букв превышают величину 127.

Англоязычный вариант сработал верно:

detab20.png

Этот код имеет смысл усовершенствовать, т.к. не дело detab'a разбираться закончилась строка или нет. У нас есть готовая функция getline (getl), которая будет предавать detab'у только строки:

 #include <stdio.h>

 #define MAXLINE 100 /* максимальный размер вводимой строки */

 int getl(char line[], int maxline);
 void detab(char to[], char from[]);

 int main()
 {
     int len; /* длина текущей строки */
     char line[MAXLINE]; /* текущая строка */
     char newline[MAXLINE]; /* новая строка */
     len = 0;

     while ((len = getl(line, MAXLINE)) > 0) {        
         detab(newline, line);
         printf("%s", newline);
     }
     return 0;
 }

 #define TABSIZE 8     /* размер табуляции в пробелах */

 void settabs(int []);
 int tabpos(int, int []);

 /* detab: преобразует символы табуляции из 'from' в пробелы 'to' */
 void detab(char to[], char from[])
 {
     int i, j;
     int tabstops[MAXLINE];

     settabs(tabstops);

     i = j = 0;
     while ((to[j] = from[i++])) {
         if (to[j] == '\t') {
             do {
                 to[j++] = ' ';
             } while (!tabpos(j, tabstops));
         }
         else
             ++j;
     }
 }

 void settabs(int tabstops[])
 {
     int i;
     for (i=0; i < MAXLINE; i++)
         tabstops[i] = (i % TABSIZE == 0);
 }

 int tabpos(int col, int tabstops[])
 {
     if (col > MAXLINE)
         return 1;
     else
         return tabstops[col];
 }

В этом случае удается ослабить связь между main и detab. Действительно, ведь основная функция не обязана ничего знать о размере табуляций или их позициях.

И, наконец, обработка аргументов командной строки. detab остается неизменной, модифицируется лишь начальная расстановка стопов и основная функция:

 #include <stdio.h>
 #include <stdlib.h>

 #define MAXLINE 72   /* максимальный размер строки табуляций */
 #define TABSIZE 8    /* размер табуляции в пробелах */

 void detab(int []);
 void settabs(int, char *[], int *);

 int main(int argc, char *argv[])
 {
     int tabstops[MAXLINE];

     settabs(argc, argv, tabstops);        
     detab(tabstops);

     return 0;
 }

 void settabs(int argc, char *argv[], int tabstops[])
 {
     int i, col;

     if (argc == 1)
         for (i=0; i < MAXLINE; i++)
             tabstops[i] = (i % TABSIZE == 0);
     else {
         for (i=0; i < MAXLINE; i++)
             tabstops[i] = 0;
         while (--argc > 0) {
             col = atoi(*++argv);
             if (col < MAXLINE)
                 tabstops[col] = 1;
         }
     }
 }

Предполагается, что вводятся корректные значения аргументов. Например: ./detab 0 8 16 24

Перейдем к entab. Вновь начнем с реализации без аргументов командной строки:

 #include <stdio.h>

 #define MAXLINE 72   /* максимальный размер строки табуляций */
 #define TABSIZE 8    /* размер табуляции в пробелах */

 void entab(int []);
 void settabs(int []);

 int main()
 {
     int tabstops[MAXLINE];

     settabs(tabstops);
     entab(tabstops);

     return 0;
 }

 int tabpos(int, int []);

 /* entab: заменяет пробелы символами табуляции и пробелами */
 void entab(int tabstops[])
 {
     int col = 0, newcol;
     char c;

     do {
         newcol = col;
         while ((c = getchar()) == ' ') {
             newcol++;
             if (tabpos(newcol, tabstops)) {
                 putchar('\t');
                 col = newcol;
             }
         }
         while (col < newcol) {
             putchar(' ');
             col++;
         }
         if (c != EOF) {
             putchar(c);
             if (c == '\n') {
                 col = 0;
             }
             else {
                 col++;
             }
         }
     } while (c != EOF);
 }

Сравнение "возвращенной табуляции" (tabbed.txt) с исходным файлом sampen.txt. Видно, что entab и detab не являются взаимно обратными, однако визуально результаты выглядят одинаково:

entab20.png

Обработку аргументов командной строки описывать не буду. entab и tabpos не изменяются, settabs — та же, что и в аналогичной версии detab. main также изменяется аналогично.

Упражнение 5.12. Расширьте возможности entab и detab таким образом, чтобы при обращении вида

entab -m +n

"стопы" табуляции начинались с m-й позиции и выполнялись через каждые n позиций. Разработайте удобный для пользователя вариант поведения программы по умолчанию (когда нет никаких аргументов).

Изменениям подвергнется только settabs():

 /* инициализация массива стопов табуляции tabstops */
 void settabs(int argc, char *argv[], int tabstops[])
 {
     int i, c;
     int tabstart = 0, tabsize = TABSIZE;

     while (--argc > 0 && (**++argv == '-' || **argv == ')) {
         switch (**argv)
         {
             case '-':
                 if ((c = atoi(*argv + 1)) > 0)
                     tabstart = c;
                 break;
             case ':
                 if ((c = atoi(*argv + 1)) > 0)
                     tabsize = c;
                 break;
         }
     }

     for (i=0; i < tabstart; i++)
         tabstops[i] = 0;

     for (i=tabstart; i < MAXLINE; i++)
         tabstops[i] = ((i - tabstart) % tabsize == 0);
 }

Упражнение 5.13. Напишите программу tail, печатающую n последних введенных строк. По умолчанию значение n равно 10, но при желании n можно задать с помощью аргумента. Обращение вида

tail -n

печатает n последних строк. Программа должна вести себя осмысленно при любых входных данных и любом значении n. Напишите программу так, чтобы наилучшим образом использовать память; запоминание строк организуйте, как в программе сортировки, описанной в параграфе 5.6, а не на основе двумерного массива с фиксированным размером строки.

Задача нашей программы (заметим, не функции, а программы):

  1. считать строки
  2. распечатать строки с соблюдением некоторых условий.

Основой послужит программа из п. 5.6. Функции readlines() и writelines() там уже реализованы, а используемая в коде функция alloc() реализована в п. 5.4.

writelines() станет основой tail(). Нам осталось:

  1. научиться распечатывать заданное число последних строк
  2. принимать из командной строки само это число (и обрабатывать возможные некорректности его задания)

Возникает вопрос: как выводить последние строки: от последней (n) к n-10 или наоборот. Я принимаю первый вариант.

Код новых функций и main:

 #include <stdio.h>
 #include <string.h>
 #include <stdlib.h>

 #define MAXLINES 50 /* максимальное число строк */
 #define NDEF 10 /* колчичество возвращаемых по умолчанию строк */

 char *lineptr[MAXLINES]; /* указатели на строки */

 int setnumlines(int, char *[]);
 int readlines(char *lineptr[], int nlines);
 void tail(char *lineptr[], int nlines, int n);


 int main(int argc, char *argv[])
 {
     int nlines; /* количество прочитанных строк */
     int n; /* количество строк, которые нужно распечатать */

     n = setnumlines(argc, argv);

     if ((nlines = readlines(lineptr, MAXLINES)) >= 0) {
         tail(lineptr, nlines, n);
         return 0;
     } else {
         printf("ошибка: слишком много строк\n");
         return 1;
     }
 }

 /* setnumlines: инициализация количества выводимых строк */
 int setnumlines(int argc, char *argv[])
 {
     int n;

     while (--argc > 0 && **++argv == '-') {
         if ((n = atoi(*argv + 1)) > 0)
             return n;
         else
             return 0;
         }
     return NDEF;    
 }

 /* tail: печать n строк с конца */
 void tail(char *lineptr[], int nlines, int n)
 {
     int i;

     if (n > nlines)
         n = nlines;
     for (i=1; i <= n; i++)
         printf("%s\n", lineptr[nlines-i]);
 }

Упражнение 5.14. Модифицируйте программу сортировки, чтобы она реагировала на параметр -r, указывающий, что объекты нужно сортировать в обратном порядке, т. е. в порядке убывания. Обеспечьте, чтобы -r работал и вместе с -n.

Идея заключается в том, чтобы не менять функции сортировки, а отсортированные по возрастанию данные, при необходимости, выводить в обратном порядке. Т. е., изменить функцию writelines.

Вот она main:

 #include <stdio.h>
 #include <string.h>
 #include <stdlib.h>

 #define MAXLINES 5000 /* максимальное число строк */

 char *lineptr[MAXLINES]; /* указатели на строки текста */

 int readlines(char *lineptr[], int nlines);
 void writelines(char *lineptr[], int nlines, int reverse);
 void quicksort(void *lineptr[], int left, int right,
      int (*comp)(void *, void *));
 int numcmp(char *, char *);

 /* сортировка строк */
 int main(int argc, char *argv[])
 {
     int nlines;        /* количество прочитанных строк */
     int numeric = 0;   /* 1, если сорт. по числ. знач. */
     int reverse = 0;   /* 1, если выводить по убыванию */
     int c;

     while (--argc > 0 && (*++argv)[0] == '-')
         while ((c = *++argv[0]))
           switch (c) {
           case 'n':
             numeric = 1;
             break;
           case 'r':
             reverse = 1;
             break;
           default:
             printf("sort: неверный параметр %c\n", c);
             argc = 0;
             break;
           }

     if ((nlines = readlines(lineptr, MAXLINES)) >= 0) {
         quicksort((void **) lineptr, 0, nlines-1,
           (int (*)(void*,void*))(numeric ? numcmp : strcmp));
         printf("SORTED:\n");
         writelines(lineptr, nlines, reverse);
         return 0;
     } else {
         printf("Bведено слишком много строк\n");
         return 1;
     }
 }

 /* writelines: печать строк */
 void writelines(char *lineptr[], int nlines, int reverse)
 {
     int i;

     if (reverse)
         for (i=1; i <= nlines; i++)
             printf("%s\n", lineptr[nlines-i]);
     else        
         while (nlines-- > 0)
             printf("%s\n", *lineptr++);
 }

qsort сменила название на quicksort, чтобы не пересекаться со встроенной функцией.

Проверим:

sort0.png

Правда, компилятор выдает предупреждение:

sort_warn.png

Вот это место:

sort_warn_text.png

Смысл очевиден: типы действительно не совпадают, так и должно быть.

Упражнение 5.15. Введите в программу необязательный параметр -f, задание которого делало бы неразличимыми символы нижнего и верхнего регистров (например, a и A должны оказаться при сравнении равными).

Примитивное решение заключается в том, чтобы перевести все символы в один регистр — нет различий, нет проблемы сортировки. Более изящное решение заключается в том, чтобы предложить еще одну функцию сравнения (вроде numcmp и strcmp), в которой при сравнении символы преобразуются к одинаковому регистру.

Примитив вот:

 #include <stdio.h>
 #include <string.h>
 #include <ctype.h>
 #include <stdlib.h>

 #define MAXLINES 5000 /* максимальное число строк */

 char *lineptr[MAXLINES]; /* указатели на строки текста */

 int readlines(char *lineptr[], int nlines);
 void setlower(char *lineptr[], int nlines);
 void writelines(char *lineptr[], int nlines, int reverse);
 void quicksort(void *lineptr[], int left, int right,
      int (*comp)(void *, void *));
 int numcmp(char *, char *);

 /* сортировка строк */
 int main(int argc, char *argv[])
 {
     int nlines;        /* количество прочитанных строк */
     int numeric = 0;   /* 1, если сорт. по числ. знач. */
     int reverse = 0;   /* 1, если выводить по убыванию */
     int case_insensetive = 0; /* 1, если сорт. нечувств. к регистру */
     int c;

     while (--argc > 0 && (*++argv)[0] == '-')
         while ((c = *++argv[0]))
           switch (c) {
           case 'n':
             numeric = 1;
             break;
           case 'r':
             reverse = 1;
             break;
           case 'f':
             case_insensetive = 1;
             break;            
           default:
             printf("sort: неверный параметр %c\n", c);
             argc = 0;
             break;
           }

     if ((nlines = readlines(lineptr, MAXLINES)) >= 0) {
         if (case_insensetive)
             setlower(lineptr, nlines);
         quicksort((void **) lineptr, 0, nlines-1,
           (int (*)(void*,void*))(numeric ? numcmp : strcmp));
         printf("SORTED:\n");
         writelines(lineptr, nlines, reverse);
         return 0;
     } else {
         printf("Bведено слишком много строк\n");
         return 1;
     }
 }

 /* setlower: преобразование символов к нижнему регистру */
 void setlower(char *lineptr[], int nlines)
 {
     int i, j;

     for (i=0; i < nlines; i++) {
         j = 0;
         while(lineptr[i][j]) {
             lineptr[i][j] = tolower(lineptr[i][j]);
             j++;
         }
     } 
 }

Образцом новой функции сравнения символов chcmp послужила функция strcmp из п. 5.5. В результате, переделке в main подвергся условный оператор:

    if ((nlines = readlines(lineptr, MAXLINES)) >= 0) {
        if (numeric)
            quicksort((void **) lineptr, 0, nlines-1, 
                    (int (*)(void *, void *)) numcmp);
        else if (case_insensetive)
            quicksort((void **) lineptr, 0, nlines-1, 
                    (int (*)(void *, void *)) chcmp);
        else    
            quicksort((void **) lineptr, 0, nlines-1, 
                    (int (*)(void *, void *)) strcmp);
        printf("SORTED:\n");
        writelines(lineptr, nlines, reverse);
        return 0;
    } else {
        printf("Bведено слишком много строк\n");
        return 1;
    }

и добавилась функция chcmp:

 /* chcmp: сравнивает s1 и s2, игнорируя разницу в регистре */
 int chcmp(char *s1, char *s2)
 {   
     for ( ; tolower(*s1) == tolower(*s2); s1++, s2++)
         if (*s1 == '\0')
             return 0;

     return tolower(*s1) - tolower(*s2);
 }

sortf.png

Упражнение 5.16. Предусмотрите в программе необязательный параметр -d, который заставит программу при сравнении учитывать только буквы, цифры и пробелы. Организуйте программу таким образом, чтобы этот параметр мог работать вместе с параметром -f.

Теперь при сравнении нам предлагается не замечать некоторых символов, например, пунктуации. Переработаем chcmp() из упражнения 5.15 в таком ключе:

  1. Пропустим нежелательные символы в начале строки
  2. Сравним строки, пропуская нежелательные символы

Изменения:

  • строки
 int directory = 0; /* 1, если сорт. игнорирует пунктуацию */
 int case_insensetive = 0; /* 1, если сорт. нечувств. к регистру */

вынесены из основной функции, чтобы эти переменные были видимы из chcmp.

  • в оператор switch основной функции добавлен блок:
  case 'd':
    directory = 1;
    break;                        
  • переработана функция chcmp(). Теперь она обрабатывает все лексикографические сравнения, а strcmp() не используется:
 /* chcmp: сравнивает s1 и s2, игнорируя разницу в регистре и/или 
  * символы пунктуации */
 int chcmp(char *s1, char *s2)
 {
     if(directory) {
         while(!isdigit(*s1) && !isalpha(*s1) && !isspace(*s1) && *s1)
             ++s1;
         while(!isdigit(*s2) && !isalpha(*s2) && !isspace(*s2) && *s2)
             ++s2;
     }
     while(case_insensetive ? (tolower(*s1) == tolower(*s2)) : (*s1 == *s2)) {
         if(*s1 == '\0')
             return 0;
         ++s1;
         ++s2;
         if(directory) {
             while(!isdigit(*s1) && !isalpha(*s1) && !isspace(*s1) && *s1)
                 ++s1;
             while(!isdigit(*s2) && !isalpha(*s2) && !isspace(*s2) && *s2)
                 ++s2;
         }
     }
     return case_insensetive ? (tolower(*s1) - tolower(*s2)) : (*s1 - *s2);
 }

В этом случае игнорируются все символы, кроме букв, цифр и пробелов. Если не игнорировать также непечатаемые символы, код будет короче, т. к. можно использовать не три функции is..., а одну — ispunct().

Упражнение 5.17. Реализуйте в программе возможность работы с полями: возможность сортировки по полям внутри строк. Для каждого поля предусмотрите свой набор параметров. Предметный указатель этой книги (Имеется в виду оригинал книги на английским языке. – Примеч. пер.) упорядочивался с параметрами: -df для терминов и -n для номеров страниц.

Надо сказать, что больше всего усилий я потратил на то, чтобы понять мысль авторов. Если бы передо мной стояла задача формирования предметного указателя, то я бы предусмотрел сортировку элементов внутри поля. Например, элементы поля номеров страниц отсортировал бы по возрастанию. Но — задание дано, и сверившись с оригиналом, приступаю.

Нам нужно:

  1. считывать начало и конец поля из командной строки
  2. выполнять сравнение в numcmp() полей, а не строк, для чего
  3. разработать функцию возвращающую поле — указанную пользователем часть строки
  4. внести изменения в chcmp(), чтобы "научить" ее работать с полями.

Ниже приведен код переработанных функций:

main()

#include <stdio.h>
#include <string.h>
#include <ctype.h>
#include <stdlib.h>

#define MAXLINES 5000 /* максимальное число строк */

char *lineptr[MAXLINES]; /* указатели на строки текста */

int readlines(char *lineptr[], int nlines);
void writelines(char *lineptr[], int nlines, int reverse);
void quicksort(void *lineptr[], int left, int right,
     int (*comp)(void *, void *));
int numcmp(char *, char *);
int chcmp(char *, char *);

int directory = 0; /* 1, если сорт. игнорирует пунктуацию */
int case_insensitive = 0; /* 1, если сорт. нечувств. к регистру */
int fs = 0, ff = 0; /* начальная и конечная позиции поля */

 /* сортировка строк */
 int main(int argc, char *argv[])
 {
     int nlines;        /* количество прочитанных строк */
     int numeric = 0;   /* 1, если сорт. по числ. знач. */
     int reverse = 0;   /* 1, если выводить по убыванию */
     int field = 0; /* 1, если определена начальная позиция поля */
     int c;

     while (--argc > 0 && ((c = (*++argv)[0]) == '-' || c == '))
         if (c == '-')
             while ((c = *++argv[0]))
                 switch (c) {
                 case 'n':
                     numeric = 1;
                     break;
                 case 'r':
                     reverse = 1;
                     break;
                 case 'f':
                     case_insensitive = 1;
                     break;
                 case 'd':
                     directory = 1;
                     break;
                 default:
                     printf("sort: неверный параметр %c\n", c);
                     argc = 0;
                     break;
                 }
         else if (c == ') {
             if (!fs && !field) {
                 fs = atoi(++argv[0]);
                 field = 1;
                 if (fs < 0) {
                     printf("sort: значение позиции должно быть неотрицательным\n");
                     fs = 0;
                 }
             }
             else if (!ff) {
                 ff = atoi(++argv[0]);
                 if (ff < fs) {
                     printf("sort: конечная позиция поля должна быть больше начальной\n");
                     ff = 0;
                 }
             }
         }
         else 
             printf("вызов: sort -nrfd +field_start +field_finish\n");

     if ((nlines = readlines(lineptr, MAXLINES)) >= 0) {
         if (numeric)
             quicksort((void **) lineptr, 0, nlines-1, 
                     (int (*)(void *, void *)) numcmp);
         else
             quicksort((void **) lineptr, 0, nlines-1, 
                     (int (*)(void *, void *)) chcmp);
         printf("SORTED:\n");
         writelines(lineptr, nlines, reverse);
         return 0;
     } else {
         printf("Bведено слишком много строк\n");
         return 1;
     }
 }

numcmp() и substr():

 #define MAXLENGTH 80 /* максимальная длина строки */

 void substr(char *, char *);

 /* numcmp: сравнивает s1 и s2 как числа */
 int numcmp(char *s1, char *s2)
 {
     double v1, v2;
     char sub[MAXLENGTH];

     substr(s1, sub);
     v1 = atof(sub);
     substr(s2, sub);
     v2 = atof(sub);
     if (v1 < v2)
         return -1;
     else if (v1 > v2)
         return 1;
     else
         return 0;
 }

 void substr(char *string, char *substring)
 {
     extern int fs, ff;
     int i, j, len;

     len = strlen(string);
     if (ff > 0 && ff < len)
         len = ff;
     else if (ff > 0 && ff > len)
         printf("sort: слишком короткая строка");
     for (i = fs, j = 0; i < len; i++, j++)
         substring[j] = string[i];
     substring[j] = '\0';
 }

 /* chcmp: сравнивает s1 и s2, игнорируя разницу в регистре и/или 
  * символы пунктуации */
 int chcmp(char *s1, char *s2)
 {
     extern int fs, ff;
     int i, j, len;

     i = j = fs;
     if (ff > 0)
         len = ff;
     else if ((len = strlen(s1)) > strlen(s2) )
         len = strlen(s2);
     if(directory) {
         while(i < len && !isdigit(s1[i]) && !isalpha(s1[i]) && !isspace(s1[i]) && s1[i])
             i++;
         while(j < len && !isdigit(s2[j]) && !isalpha(s2[j]) && !isspace(s2[j]) && s2[j])
             j++;
     }
     while(i < len && j < len && case_insensitive ? (tolower(s1[i]) == tolower(s2[j])) : (s1[i] == s2[j])) {
         if(s1[i] == '\0')
             return 0;
         i++;
         j++;
         if(directory) {
             while(i < len && !isdigit(s1[i]) && !isalpha(s1[i]) && !isspace(s1[i]) && s1[i])
                 i++;
             while(j < len && !isdigit(s2[j]) && !isalpha(s2[j]) && !isspace(s2[j]) && s2[j])
                 j++;
         }
     }
     return case_insensitive ? (tolower(s1[i]) - tolower(s2[j])) : (s1[i] - s2[j]);
 }

Пример сортировки:

sort_fields.png

Упражнение 5.18. Видоизмените dcl таким образом, чтобы она обрабатывала ошибки во входной информации.

Какие именно ошибки? Дадим слово авторам: "Лишние пробелы для нее опасны. Она не предпринимает никаких мер по выходу из ошибочной ситуации, и поэтому неправильные описания также ей противопоказаны".

Действительно, если поставить пробел внутри поля аргументов функции, получим ошибку исправить которую без перезапуска невозможно:

dcl.png

Заметьте, что вторая попытка синтаксически корректна, но также воспринимается как ошибка.

Необходимо научиться убирать лишние пробелы:

 int gettoken(void) /* возвращает следующую лексему */
 {
     int c;
     void ungetch(int);
     char *p = token;

     if ((c = getter()) == '(') {
         if ((c = getter()) == ')') {
             strcpy(token, "()");
             return tokentype = PARENS;
         } else {
             ungetch(c);
             return tokentype = '(';
         }
     } else if (c == '['){
         for (*p++ = c; (*p++ = getter()) != ']'; );
         *p = '\0';
         return tokentype = BRACKETS;
     } else if (isalpha(c)) {
         for (*p++ = c; isalnum(c = getch()); )
             *p++ = c;
         *p = '\0';
         ungetch(c);
         return tokentype = NAME;
     } else
         return tokentype = c;
 }

 int getter(void)
 { 
     int c;  
     while ((c = getch()) == ' ' || c == '\t');    
     return c;
 }

getter() — широко используемая в книге операция предварительного удаления пробелов и табуляций. Вынесена в функцию, потому что необходимо применить несколько раз.

Теперь — борьба с повторением ошибок. В такой простой программе логично выглядит такой подход: сообщить пользователю об ошибке и выйти из программы, давая ему шанс ее исправить.

Поэтому исходную функцию dirdcl() я дополнил сообщения об ошибках вызовом функций exit() из stdlib.h со статусом -1:

 /* dirdcl: разбор собственно объявителя */
 void dirdcl(void)
 {
     int type;

     if (tokentype == '(') {
         dcl();
         if (tokentype != ')') {
             printf("oшибкa: пропущена )\n");
             exit(-1);
         }
     } else if (tokentype == NAME) /* имя переменной */
         strcpy(name, token); 
     else {
         printf("ошибка: должно быть name или (dcl)\n");
         exit(-1);
     }

     while((type = gettoken()) == PARENS || type == BRACKETS)
         if (type == PARENS)
             strcat(out, "функц. возвр.");
         else {
             strcat(out, " массив ");
             strcat(out, token);
             strcat(out, " из ");
         }
 }

dcl1.png

Упражнение 5.19. Модифицируйте undcl так, чтобы она не генерировала лишних скобок.

Проблема лишних скобок возникает, когда после объявления указателя не идет больше скобок () или []:

undcl.png

Скобки во второй стоке не нужны. Поэтому мы добавим к программе функцию nexttoken(), которая будет проверять тип следующей лексемы и, если это PARENS или BRACKETS, то ставить скобки вокруг указателя. При этом gettoken() нужно "предупредить", что проверка следующей лексемы уже проведена и не нужно принимать новую. Для этого используется проверка в начале gettoken():

 if (prevtoken == YES) {
     prevtoken = NO;
     return tokentype;
 }

Получим, таким образом:

 #include <stdio.h>
 #include <string.h>
 #include <ctype.h>

 #define MAXTOKEN 100 

 enum {NAME, PARENS, BRACKETS};

 int gettoken(void);
 int nexttoken(void);
 int getter(void);
 int tokentype;           /* тип последней лексемы */
 char token[MAXTOKEN];    /* текст последней лексемы */ 
 char name[MAXTOKEN];     /* имя */
 char datatype[MAXTOKEN]; /* тип = char, int и т.д. */
 char out[1000];          /* выдаваемый текст */

 /* undcl: преобразует словесное описание в объявление */
 int main(void)
 {
     int type;
     char temp[MAXTOKEN];

     while (gettoken() != EOF) {
         strcpy(out, token); 
         while ((type = gettoken()) != '\n') 
             if (type == PARENS || type == BRACKETS)
                 strcat(out, token);
             else if (type == '*' ) {
                 if ((type = nexttoken()) == PARENS || type == BRACKETS)
                     sprintf(temp, "(*%s)", out);
                 else
                     sprintf(temp, "*%s", out);
                 strcpy(out, temp);
             } else if (type == NAME) {
                 sprintf(temp, "%s %s", token, out);
                 strcpy(out, temp);
             } else
                 printf("неверный элемент %s во фразе\n", token);
         printf("%s\n", out);
     }
     return 0;
 }

 enum {NO, YES};
 int prevtoken = NO;

 int nexttoken(void)
 {
     int type;
     type = gettoken();
     prevtoken = YES;
     return type;
 }

 int getch(void);

 int gettoken(void) /* возвращает следующую лексему */
 {
     int c;
     void ungetch(int);
     char *p = token;

     if (prevtoken == YES) {
         prevtoken = NO;
         return tokentype;
     }

     if ((c = getter()) == '(') {
         if ((c = getter()) == ')') {
             strcpy(token, "()");
             return tokentype = PARENS;
         } else {
             ungetch(c);
             return tokentype = '(';
         }
     } else if (c == '['){
         for (*p++ = c; (*p++ = getter()) != ']'; );
         *p = '\0';
         return tokentype = BRACKETS;
     } else if (isalpha(c)) {
         for (*p++ = c; isalnum(c = getch()); )
             *p++ = c;
         *p = '\0';
         ungetch(c);
         return tokentype = NAME;
     } else
         return tokentype = c;
 }

undcl1.png

Упражнение 5.20. Расширьте возможности dcl, чтобы dcl обрабатывала объявления с типами аргументов функции, квалификаторами вроде const и т. п.

Для того, чтобы расширить эти возможности нужно сперва расширить грамматику, описывающую объявитель (см. п. 5.12):

объявитель: необязательные * собственно-объявитель
собственно-объявитель: имя
(объявитель)
собственно-объявитель()
собственно-объявитель [необязательный размер]

Для этого заглянем в приложение А.8.5, где приведена полная грамматика объявителей, и дополним указанную выше грамматику.

объявитель: необязательные * собственно-объявитель
собственно-объявитель: имя
(объявитель)
собственно-объявитель(список-типов-параметров)
собственно-объявитель [необязательный размер]
список-типов-параметров: список-типов-параметров, объявитель

В таком виде она описывает список параметров функции, но пока (несмотря на название) — без объявлений типов.

Реализуем эту грамматику в программе. Для этого переделаем функцию dirdcl(), в частности, добавим в нее из прошлого упражнения prevtoken — для анализа уже введенной лексемы. Кроме того, добавим функцию params_dcl() — для анализа списка параметров.

 void dirdcl(void)
 {
     int type;
     void params_dcl(void);

     if (tokentype == '(') {
         dcl();
         if (tokentype != ')') {
             printf("oшибкa: пропущена )\n");
             exit(-1);
         }
     } else if (tokentype == NAME) {
         if (name[0] == '\0')
             strcpy(name, token);
     }
     else {
         prevtoken = YES;
     }

     while((type = gettoken()) == PARENS ||
                        type == BRACKETS || 
                        type == '(')
         if (type == PARENS)
             strcat(out, "функц. возвр.");
         else if (type == '(') {
             strcat(out, " функц. приним. ");
             params_dcl();
             strcat(out, " и возвр. ");            
         }
         else {
             strcat(out, " массив ");
             strcat(out, token);
             strcat(out, " из ");
         }
 }

 void params_dcl(void)
 {
     gettoken();
     do {
         dcl();
         printf("параметр: %s\n", token);
     } while (tokentype == ',');
     if (tokentype != ')')
         printf("oшибкa: пропущена ) в объявлении параметров\n");
 }

Пример использования:

dcl2.png

Список типов параметров функция пока не возвращает.

Снова дополним грамматику:

объявитель: необязательные * собственно-объявитель
собственно-объявитель: имя
(объявитель)
собственно-объявитель(список-типов-параметров)
собственно-объявитель [необязательный размер]
список-типов-параметров: список-типов-параметров, объявление-типа объявитель
объявление-типа: тип объявление-типа
квалификатор объявление-типа

Программная реализация модификации потребует создания новой функции type_dcl() для анализа объявлений типов, изменений в params_dcl(), а также введения функций для проверки объявлений имен типов (istypename) и квалификаторов типов (istypequal). Для примера, я взял несколько имена и квалификаторов.

Код:

 void params_dcl(void)
 {
     void type_dcl(void);

     do {
         type_dcl();
     } while (tokentype == ',');
     if (tokentype != ')') {
         printf("oшибкa: пропущена ) в объявлении параметров\n");
         prevtoken = YES;
     }
 }

 void type_dcl(void)
 {
     char t[MAXTOKEN];
     int istypename(char []);
     int istypequal(char []);

     t[0] = '\0';
     gettoken();

     do {
         if (tokentype != NAME) {
             prevtoken = YES;
             dcl();
         }
         else if (istypename(token)) {
             strcat(t, token);
             gettoken();
         }
         else if (istypequal(token)) {
             strcat(t, token);
             gettoken();
         }
         else {
             printf("ошибка: неизвестный параметр %s\n", token);
             prevtoken = YES;
         }
     } while (tokentype == ',' && tokentype == ')');
     strcat(out, t);
     if (tokentype == ',')
         strcat(out, ", ");
 }

 int istypename(char name[])
 {
     int i=0;
     char *types[] = {"char", "int", "float"};
     int ntypes = 3;

     while (ntypes--)
         if (strcmp(name, types[i++]) == 0)
             return 1;

     return 0;    
 }

 int istypequal(char qual[])
 {
     int i=0;
     char *quals[] = {"const", "volatile"};
     int nquals = 2;

     while (nquals--)
         if (strcmp(qual, quals[i++]) == 0)
             return 1;

     return 0;    
 }

Пример использования:

dcl3.png

Однако, имейте в виду: детального тестирования этой функции я не проводил.



Комментарии

comments powered by Disqus