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

Упражнение 6.1. Haшa вepcия getword не обрабатывает должным образом знак подчеркивания, строковые константы, комментарии и управляющие строки препроцессора. Напишите более совершенный вариант программы.

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

Список ключевых слов Си (ANSI C):

auto break case char const continue default do double else enum extern float for goto if int long register return short signed sizeof static struct switch typedef union unsigned void volatile while

И где здесь подчеркивание? Правильно, его здесь нет, а задачи подсчитать идентификаторы Си нам не ставили. Однако, разные компиляторы могут добавлять к стандарту свои ключевые слова. Например, Borland C++ добавляет: __asm, _asm, asm. Кроме того, стандартом, насколько я понял, не запрещено вставлять символ подчеркивания и внутрь ключевых слов.

Вначале дополним getword() анализом символа подчеркивания. Для тренировки, работать будем лишь с небольшим подмножеством ключевых слов, в которые я еще и добавил кое-что от себя.

В результате, массив структур keytab имеет вид:

 struct key {
     char *word;
     int count;
 } keytab[] = {
     {"_asm", 0},
     {"as_m", 0},
     {"asm", 0},
     {"break", 0},
     {"case", 0},
     {"char", 0}
 };

Фигурные скобки вокруг элементов отдельных структур пришлось поставить, т. к. в отличие от того, что было у K&R, мой gcc ругается из-за отсутствия этих скобок.

Переделанная getword():

 /* getword: принимает следующее слово или символ из ввода */
 int getword (char *word, int lim)
 {
     int c, getch(void);
     void ungetch(int);
     char *w = word;

     while (isspace(c = getch()));
     if (c != EOF)
        *w++ = c;
     if (isalpha(c) || c == '_')
         for ( ; --lim > 0; w++)
             if (!isalnum(*w = getch()) && *w != '_') {
                 ungetch(*w);
                 break;
             }
     *w = '\0';
     return c;
 }

Даже стала короче.

Про директивы препроцессора я не понял задания. getword(), в ее нынешнем виде, игнорирует собственно директивы, но извлекает ключевые слова, стоящие за ними. Сами же директивы не являются ключевыми словами. Может я должен, вместо препроцессора, выполнить подстановку из директив? Короче говоря, оставил как есть.

Пропуск ключевых слов, находящихся внутри строковых констант осуществляется добавлением условия

 else if (c == '"') {
         while ((t = getch()) != c && t != EOF);
 }

Заметим, что это решение не застраховано от ложных срабатываний на экранированных двойных кавычках.

Удаление многострочных комментариев осуществляется условием:

 else if (c == '/') {
         if ((t = getch()) == '*') {
             while ((t = getch()) != EOF )
                 if (t == '*') {
                     if ((t = getch()) == '/')
                         break;
                     else
                         ungetch(t);
                 }
         }
         else 
             ungetch(t);
 }    

Однострочные комментарии мы обрабатывать не будем, но идея здесь та же, только начало комментария -- "//", а конец -- "\n".

Сходная задача по "уборке" комментариев решалась также в упражнении 1.24.

getword() полностью:

 int getword (char *word, int lim)
 {
     int c, t, getch(void);
     void ungetch(int);
     char *w = word;

     while (isspace(c = getch()));
     if (c != EOF)
         *w++ = c;
     if (isalpha(c) || c == '_') {
         for ( ; --lim > 0; w++)
             if (!isalnum(*w = getch()) && *w != '_') {
                 ungetch(*w);
                 break;
             }
     }
     else if (c == '"') {
         while ((t = getch()) != c && t != EOF);
     }
     else if (c == '/') {
         if ((t = getch()) == '*') {
             while ((t = getch()) != EOF )
                 if (t == '*') {
                     if ((t = getch()) == '/')
                         break;
                     else
                         ungetch(t);
                 }
         }
         else 
             ungetch(t);
     }    
     *w = '\0';
     return c;
 }

Упражнение 6.2. Напишите программу, которая читает текст Си-программы и печатает в алфавитном порядке все группы имен переменных, в которых совпадают первые 6 символов, но последующие в чем-то различаются. Не обрабатывайте внутренности закавыченных строк и комментариев. Число 6 сделайте параметром, задаваемым в командной строке.

Основа для программы находится в п. 6.5. Кроме того, нужно организовать считывание параметров командной строки (см. последние упражнения главы 5), функцию сравнения заданного числа символов (strncmp() из stdlib.h) и пропуск закавыченных строк и комментариев (упражнение 6.1). Все кубики уже готовы, соберем из них программу

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

 #define MAXWORD 100

 struct tnode {           /* узел дерева */
     char *word;          /* указатель на текст */
     int count;           /* число вхождений */ 
     struct tnode *left;  /* левый дочерний узел */
     struct tnode *right; /* правый дочерний узел */
 };

 struct tnode *addtree(struct tnode *, char *);
 void treeprint(struct tnode *);
 int getword(char *, int);

 int num;

 int main(int argc, char *argv[])
 {
     struct tnode *root;
     char word[MAXWORD];

     if (argc == 2)
         num = atoi(argv[1]);
     else if (argc < 2)
         num = 3; /* Значение длины сравнения по умолчанию */
     else {
         printf("usage: tree <number>\n");
         exit(-1);
     }      

     root = NULL;
     while (getword (word, MAXWORD) != EOF)
         if (isalpha(word[0]))
             root = addtree(root, word);
     treeprint(root);
     return 0;
 }

 struct tnode *talloc(void);
 char *mystrdup(char *);

 /* addtree: добавляет узел со словом w в р или ниже него */
 struct tnode *addtree(struct tnode *p, char *w)
 {
    int cond;

    if (p == NULL) {  /* слово встречается впервые */
        p = talloc(); /* создается новый узел */
        p->word = strdup(w);
        p->count = 1;
        p->left = p->right = NULL;
    } else if ((cond = strncmp(w, p->word, num)) == 0) 
        p->count++;           /* это слово уже встречалось */
    else if (cond < 0)        /* меньше корня левого поддерева */
        p->left = addtree(p->left, w);
    else                      /* больше корня правого поддерева */
        p->right = addtree(p->right, w);
    return p;
 }

addtree() подверглась, как видно, минимальной переработке. strdup() переименована в mystrdup(), чтобы не конфликтовать с библиотечной функцией.

Вот тестовая программа:

 #include <stdio.h>

 int main(void)
 {
     char test1[] = "This is a test";
     int test = 2;
     /* test for ex. 6.2 */
     printf("%s. Number is %d\n", test1, test);
     return 0;
 }

Если сравнивать первые 6 символов строк (установлено по умолчанию), то получим

tree0.png

test и test1, как и положено, различаются, а test'ы, стоящие в строках и комментариях пропускаются. Однако, как видно, директивы препроцессора не игнорируются. Словом, данная программа унаследовала все недостатки getword() из упражнения 6.1.

Если сравнивать слова по 3-м первым символам, получим:

tree1.png

Теперь test и test1 учитываются совместно.

Упражнение 6.3. Напишите программу печати таблицы "перекрестных ссылок", которая будет печатать все слова документа и указывать для каждого из них номера строк, где оно встретилось. Программа должна игнорировать "шумовые" слова, такие как "и", "или" и пр.

Нам нужно:

  1. ввести счетчик строк и научить getword() обновлять его значения
  2. ввести фильтр коротких слов
  3. изменить структуру так, чтобы в ней фиксировалось номера строк, в которых встречается слово.

Основой послужила программа из предыдущего упражнения. В структуру добавлен новый элемент -- массив для котором хранения информации о номерах строк. Бывший счетчик -- count -- стал индексом этого массива. Вообще говоря, удобнее было бы сделать контейнеров для хранения номеров строк не массив, а список (для чего понадобилось бы ввести ещё одну структуру), но я решил, что и так достаточно.

Изменившиеся части программы:

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

    #define MAXWORD 100
    #define MAXLINK 5

    struct tnode {           /* узел дерева */
        char *word;           /* указатель на текст */
        int nline[MAXLINK];   /* массив номеров строк */
        int count;            /* индекс в nline[] */ 
        struct tnode *left;  /* левый дочерний узел */
        struct tnode *right; /* правый дочерний узел */
    };

    struct tnode *addtree(struct tnode *, char *);
    void treeprint(struct tnode *);
    int getword(char *, int);

    int num;                  /* Максимальная длина "шумового" слова */
    int lnum = 0;             /* Инициализация счетчика строк */

    int main(int argc, char *argv[])
    {
        struct tnode *root;
        char word[MAXWORD];

        if (argc == 2)
            num = atoi(argv[1]);
        else if (argc < 2)
            num = 2;
        else {
            printf("usage: linktree <number>\n");
            exit(-1);
        }      

        root = NULL;
        while (getword (word, MAXWORD) != EOF)
            if (isalpha(word[0]) && strlen(word) > num)
                root = addtree(root, word);
        treeprint(root);
        return 0;
    }

    struct tnode *talloc(void);
    char *mystrdup(char *);

    /* addtree: добавляет узел со словом w в р или ниже него */
    struct tnode *addtree(struct tnode *p, char *w)
    {
        int cond;

        if (p == NULL) {  /* слово встречается впервые */
            p = talloc(); /* создается новый узел */
            p->word = strdup(w);
            p->nline[p->count] = lnum;
            p->count = 1;
            p->left = p->right = NULL;
        } else if ((cond = strcmp(w, p->word)) == 0) {
            p->nline[p->count++] = lnum; /* это слово уже встречалось */
        }
        else if (cond < 0)        /* меньше корня левого поддерева */
            p->left = addtree(p->left, w);
        else                      /* больше корня правого поддерева */
            p->right = addtree(p->right, w);
        return p;
    }

    /* treeprint: упорядоченная печать дерева р */
    void treeprint(struct tnode *p)
    {
        int i;

        if (p != NULL) {
            treeprint (p->left);
            printf("\n%s ", p->word);
            for (i = 0; i < MAXLINK; i++)
                printf("%2d ",p->nline[i]);
            treeprint(p->right);
        }
    }

    /* getword: принимает следующее слово или символ из ввода */
    int getword (char *word, int lim)
    {
        int c, t, getch(void);
        void ungetch(int);
        char *w = word;

        while (isspace(c = getch()) && c != '\n');
        if (c != EOF)
            *w++ = c;
        if (isalpha(c) || c == '_') {
            for ( ; --lim > 0; w++) {
                if (!isalnum(*w = getch()) && *w != '_') {
                    ungetch(*w);
                    break;
                }
                else if (*w == '\n') {
                    lnum++;
                    ungetch(*w);
                    break;
                }
            }
        }
        else if (c == '"') {
            while ((t = getch()) != c && t != EOF);
        }
        else if (c == '/') {
            if ((t = getch()) == '*') {
                while ((t = getch()) != EOF )
                    if (t == '*') {
                        if ((t = getch()) == '/')
                            break;
                        else
                            ungetch(t);
                    }
            }
            else 
                ungetch(t);
        }
        else if (c == '\n')
            lnum++;
        *w = '\0';
        return c;
    }

Результаты при длине "шумовой" строки num = 0:

 char  4  0  0  0  0 
 h  0  0  0  0  0 
 include  0  0  0  0  0 
 int  2  5  0  0  0 
 main  2  0  0  0  0 
 printf  7  0  0  0  0 
 return  8  0  0  0  0 
 stdio  0  0  0  0  0 
 test  5  7  0  0  0 
 test1  4  7  0  0  0 
 void  2  0  0  0  0 

А теперь длина "шумовой" строки num = 2:

 char  4  0  0  0  0 
 include  0  0  0  0  0 
 int  2  5  0  0  0 
 main  2  0  0  0  0 
 printf  7  0  0  0  0 
 return  8  0  0  0  0 
 stdio  0  0  0  0  0 
 test  5  7  0  0  0 
 test1  4  7  0  0  0 
 void  2  0  0  0  0 

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

Основой послужит программа из упражнения 6.1 (или та, что приведена в п. 6.5).

  1. Теперь вместо того, чтобы печатать узлы дерева (treeprint), мы создадим массив указателей на узлы (words[]), соотвественно функция treeprint будет переименована в tree2array.
  2. Затем полученный массив отсортируем. Здесь можно было использовать быструю сортировку или сортировку Шелла, рассмотренные в книге ранее, но так как пример учебный, я реализовал сортировку пузырьком (bubble_sort).
  3. Наконец, печатаем массив.

Модернизированный код:

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

 #define MAXWORD 100
 #define MAXWORDS 20

 struct tnode {           /* узел дерева */
     char *word;           /* указатель на текст */
     int count;            /* число вхождений */ 
     struct tnode *left;  /* левый дочерний узел */
     struct tnode *right; /* правый дочерний узел */
 }; 

 struct tnode *addtree(struct tnode *, char *);
 void tree2array(struct tnode *);
 void bubble_sort(struct tnode *[], int);
 void arrayprint(struct tnode *[]);
 int getword(char *, int);

 struct tnode *words[MAXWORDS];
 int nword = 0;

 int main(void)
 {
     struct tnode *root;
     char word[MAXWORD];

     root = NULL;
     while (getword (word, MAXWORD) != EOF)
         if (isalpha(word[0]))
             root = addtree(root, word);
     tree2array(root);
     printf("number of words = %d\n\n", nword);
     bubble_sort(words, nword);
     arrayprint(words);
     return 0;
 }

 /* tree2array: сохранение упорядоченного по алфавиту дерева в массиве */
 void tree2array(struct tnode *p)
 {
     if (p != NULL) {
         tree2array (p->left);
         if (nword < MAXWORDS)
             words[nword++] = p;
         tree2array(p->right);
     }
 }

 void swap(struct tnode *[], int, int);

 /* bubble_sort: сортировка *w[] пузырьком */
 void bubble_sort(struct tnode *w[], int n) {
     int j, t = 1;

     while (n-- && t)
         for (j = t = 0; j < n; j++) {
             if (w[j]->count >= w[j+1]->count) continue;
             swap(w, j, j+1);
             t = 1;
         }
 }

 /* swap: поменять местами w[i] и w[j] */
 void swap(struct tnode *w[], int i, int j)
 {
     struct tnode *temp;

     temp = w[i];
     w[i] = w[j];
     w[j] = temp;
 }

 /* arrayprint: печать массива структур */
 void arrayprint(struct tnode *w[])
 {
     int i;

     for (i = 0; i < nword; i++)
         printf("%4d %s\n", w[i]->count, w[i]->word);
 }

Пример работы:

freqtree.png

Упражнение 6.5. Напишите функцию undef, удаляющую имя и определение из таблицы, организация которой поддерживается функциями lookup и install.

Мне кажется, что для того чтобы удалять что-нибудь из таблицы, нужно вначале эту таблицу создать, иначе трудно будет проверить результат. А созданием таблицы занимается #define-npoцeccop. Поэтому решение этой задачи стало частью следующего упражнения.

Упражнение 6.6. Реализуйте простую версию #define-npoцeccopa (без аргументов), которая использовала бы программы этого параграфа и годилась бы для Си-программ. Вам могут помочь программы getch и ungetch.

Начнём с того, что покажем как препроцессор "видит" текст. Запишем программу, которая бы считывала код Си-программы по словам и выдавала на stdout.

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

 #define MAXWORD 100
 #define HASHSIZE 101

 struct nlist {           /* элемент таблицы */
     struct nlist *next;  /* указатель на следующий элемент */
      char *name;         /* определенное имя */
      char *defn;         /* замещающий текст */
 };

 static struct nlist *hashtab[HASHSIZE]; /* таблица указателей */

 struct nlist *install(char *, char *);
 int getword(char *, int);


 int main(void)
 {
     char word[MAXWORD];

     while (getword (word, MAXWORD) != EOF)
         printf("[%s]", word);

     return 0;
 }

 struct nlist *lookup(char *);
 char *mystrdup(char *);
 unsigned hash(char *);

 /* install: заносит имя и текст (name, defn) в таблицу */
 struct nlist *install(char *name, char *defn)
 {
     struct nlist *np;
     unsigned hashval;

     if ((np = lookup(name)) == NULL) { /* не найден */
         np = (struct nlist *) malloc(sizeof(*np));
         if (np == NULL || (np->name = strdup(name)) == NULL)
             return NULL;
         hashval = hash(name);
         np->next = hashtab[hashval];
         hashtab[hashval] = np;
     } else /* уже имеется */
         free((void *) np->defn); /* освобождаем прежний defn */
     if ((np->defn = mystrdup(defn)) == NULL)
         return NULL;
     return np;
 }

 /* lookup: ищет s */
 struct nlist *lookup(char *s)
 {
     struct nlist *np;

     for (np = hashtab[hash(s)]; np != NULL; np = np->next)
         if (strcmp(s, np->name) == 0)
             return np; /* нашли */
     return NULL; /* не нашли */
 }

 /* hash: получает хэш-код для строки s */
 unsigned hash(char *s)
 {
     unsigned hashval;

     for (hashval = 0; *s != '\0'; s++)
         hashval = *s + 31 * hashval;
     return hashval % HASHSIZE;
 }

В коде присутствуют install(), lookup() и hash() из п. 6.6, но пока не используются. Здесь не зватает getword() и пары getch/ungetch -- их можно взять из прошлых упражнений этой главы.

Вводим тестовую программу:

 #include <stdio.h>

 #define TWO 2

 int main(void)
 {
     char test1[] = "This is a test";
     int test = TWO;
     /* test for ex. 6.2 */
     printf("%s. Number is %d\n", test1, test);
     #undef TWO

     return 0;
 }

И получаем результат,

def0.png

где каждое слово взято в квадратные скобки.

Слово может являться признаком директивы, определением директивы -- их мы обрабатываем, или -- просто словом -- их мы пропускаем.

Признаком директивы является '#', за ним могут следовать как имя вида директивы (define, undef) -- то, что нам предстоит обрабатывать -- так и то, что мы пропускаем.

Скелет цикла получается таким:

    while (getword (word, MAXWORD) != EOF) {
        if (strcmp(word, "#") == 0) {
            ...
            getword (word, MAXWORD);
            if (strcmp(word, "define") == 0) {
            ...
            }
            else if (strcmp(word, "undef") == 0) {
            ... 
            }
        }
        else if ((np = lookup(word)) != NULL) {
        ... 
        }
        printf("[%s]", word);
     }

Далее, считываем имя конкретной директивы. В программе предполагается, что оно состоит только из прописных букв. Эта операция -- общая для define и undef. В случае define мы считываем также следующее слово и оно будет определением директивы. Мы не проверяем его на принадлежность к тому или иному виду символов и, наверное, зря.

Вот основная программа, в которой реализована ветка define и вставлены отладочные сообщения:

 int main(void)
 {
     char word[MAXWORD], tword[MAXWORD];
     struct nlist *np;

     while (getword (word, MAXWORD) != EOF) {
         if (strcmp(word, "#") == 0) {
             printf("<directive?>");
             printf("[%s]", word);
             getword (word, MAXWORD);
             if (strcmp(word, "define") == 0) {
                 printf("<define>");
                 if (isupper(getword (word, MAXWORD))) {
                     printf("<NAME>");
                     strcpy(tword, word);
                     if (isalnum(getword (word, MAXWORD))) {
                         printf("<<defn>>");
                         np = install(tword, word);
                     }
                     else
                         printf("error: incorrect definition.\n");
                 }
                 else {
                     printf("error: must be only UPPER LETTERS in directive.\n");
                 }
             }
             else if (strcmp(word, "undef") == 0) {
                 printf("<undef>");
             }
             else {
                 printf("<not>");
             }
         }
         else if ((np = lookup(word)) != NULL) {
             printf("<in table>");
             strcpy(word, np->defn);
         }
         printf("[%s]", word);
     }
     printf("\n");
     tableprint();

     return 0;
 }

причём tableprint() отвечает за печать хеш-таблицы:

 void tableprint(void)
 {
    int i;
    struct nlist *np;

    for (i=0; i < HASHSIZE; i++)
        for (np = hashtab[i]; np != NULL; np = np->next)
            printf("name=%s, defn=%s\n", np->name, np->defn);
 }

Применяя её к тестовой программе, получим:

def1.png

Как видно, программа успешно нашла define и undef, отделила их от директивы #include, однако имя при undef заменено на определение, т. к. эта директива пока не обрабатывается.

Добавим обработку undef в основную программу:

 int main(void)
 {
    char word[MAXWORD], tword[MAXWORD];
    struct nlist *np;

    while (getword (word, MAXWORD) != EOF) {
        if (strcmp(word, "#") == 0) {
            printf("<directive?>");
            printf("[%s]", word);
            getword (word, MAXWORD);
            if (strcmp(word, "define") == 0) {
                printf("<define>");
                if (isupper(getword (word, MAXWORD))) {
                    printf("<NAME>");
                    strcpy(tword, word);
                    if (isalnum(getword (word, MAXWORD))) {
                        printf("<<defn>>");
                        np = install(tword, word);
                    }
                    else
                        printf("error: incorrect definition.\n");
                }
                else {
                    printf("error: must be only UPPER LETTERS in directive.\n");
                }
            }
            else if (strcmp(word, "undef") == 0) {
                printf("<undef>");
                if (isupper(getword (word, MAXWORD))) {
                    printf("<NAME>");
                    undef(word);
                }
            }
            else {
                printf("<not>");
            }
        }
        else if ((np = lookup(word)) != NULL) {
            printf("<in table>");
            strcpy(word, np->defn);
        }
        printf("[%s]", word);
    }
    printf("\n");
    tableprint();

    return 0;
 }

Функция undef() (т. е. решение упражнения 6.5) имеет вид:

 /* undef: удаление записи из хэш-таблицы hashtab */
 void undef(char *s)
 {
    int i;
    struct nlist *np, *prev;

    prev = NULL;
    i = hash(s);
    for (np = hashtab[i]; np != NULL; np = np->next) {
        if (strcmp(s, np->name) == 0)
            break;
        prev = np;
    }
    if (np != NULL) {
        if (prev == NULL)
            hashtab[i] = np->next;
        else
            prev->next = np->next;
        free((void *) np->name);
        free((void *) np->defn);
        free((void *) np);
    }
 }

Опробуем это на тестовой программе:

def2.png

undef теперь обрабатывается, а хеш-таблица пуста после удаления из неё единственной записи.



Комментарии

comments powered by Disqus