7.41.

Напишите функцию match(строка,шаблон); для проверки соответствия строки упрощенному регулярному выражению в стиле Шелл. Метасимволы шаблона:

        * - любое число любых символов (0 и более);
        ? - один любой символ.
                      Усложнение:
        [буквы]  - любая из перечисленных букв.
        [!буквы] - любая из букв, кроме перечисленных.
        [h-z]    - любая из букв от h до z включительно.

Указание: для проверки "остатка" строки используйте рекурсивный вызов этой же функции.

Используя эту функцию, напишите программу, которая выделяет из файла СЛОВА, удовлетворяющие заданному шаблону (например, "[Ии]*о*т"). Имеется в виду, что каждую строку надо сначала разбить на слова, а потом проверить каждое слово.

    #include <stdio.h>
    #include <string.h>
    #include <locale.h>
    #define  U(c) ((c) & 0377)  /* подавление расширения знака */
    #define  QUOT    '\\'       /* экранирующий символ         */
    #ifndef  MATCH_ERR
    # define MATCH_ERR printf("Нет ]\n")
    #endif
    /* s - сопоставляемая строка
     * p - шаблон. Символ \ отменяет спецзначение метасимвола.
     */
    int match (register char *s, register char *p)
    {
        register int    scc; /* текущий символ строки                 */
        int     c, cc, lc;   /* lc - предыдущий символ в [...] списке */
        int     ok, notflag;
        for (;;) {
            scc = U(*s++);          /* очередной символ строки  */
            switch (c = U (*p++)) { /* очередной символ шаблона */
                case QUOT:          /* a*\*b */
                    c = U (*p++);
                    if( c == 0 ) return(0); /* ошибка: pattern\ */
                    else goto def;
                case '[':   /* любой символ из списка */
                    ok = notflag = 0;
                    lc = 077777;      /* достаточно большое число */
                    if(*p == '!'){ notflag=1; p++; }
                    while (cc = U (*p++)) {
                        if (cc == ']') {    /* конец перечисления */
                            if (ok)
                                break;      /* сопоставилось      */
                            return (0);     /* не сопоставилось   */
                        }
                        if (cc == '-') {    /* интервал символов  */
                            if (notflag){
                                /* не из диапазона - OK */
                                if (!syinsy (lc, scc, U (*p++)))
                                    ok++;
                                /* из диапазона - неудача */
                                else return (0);
                            } else {
                                /* символ из диапазона - OK */
                                if (syinsy (lc, scc, U (*p++)))
                                    ok++;
                            }
                        }
                        else {
                            if (cc == QUOT){      /* [\[\]] */
                                cc = U(*p++);
                                if(!cc) return(0);/* ошибка */
                            }
                            if (notflag){
                                if (scc && scc != (lc = cc))
                                    ok++;          /* не входит в список */
                                else return (0);
                            } else {
                                if (scc == (lc = cc)) /* входит в список */
                                    ok++;
                            }
                        }
                    }
                    if (cc == 0){    /* конец строки */
                        MATCH_ERR;
                        return (0);        /* ошибка */
                    }
                    continue;
                case '*':   /* любое число любых символов */
                    if (!*p)
                        return (1);
                    for (s--; *s; s++)
                        if (match (s, p))
                            return (1);
                    return (0);
                case 0:
                    return (scc == 0);
                default: def:
                    if (c != scc)
                        return (0);
                    continue;
                case '?':   /* один любой символ */
                    if (scc == 0)
                        return (0);
                    continue;
            }
        }
    }
    /* Проверить, что smy лежит между smax и smin
     */
    int syinsy (unsigned smin, unsigned smy, unsigned smax)
    {
        char left   [2];
        char right  [2];
        char middle [2];
        left  [0]   = smin;  left  [1]   = '\0';
        right [0]   = smax;  right [1]   = '\0';
        middle[0]   = smy;   middle[1]   = '\0';
        return (strcoll(left, middle) <= 0 && strcoll(middle, right) <= 0);
    }

Обратите внимание на то, что в UNIX расширением шаблонов имен файлов, вроде *.c, занимается не операционная система (как в MS DOS), а программа-интерпретатор команд пользователя (shell: /bin/sh, /bin/csh, /bin/ksh). Это позволяет обрабатывать (в принципе) разные стили шаблонов имен.

7.42.

Изучите раздел руководства man regexp и include-файл /usr/include/regexp.h, содержащий исходные тексты функций compile и step для регулярного выражения в стиле программ ed, lex, grep: одна буква C или заэкранированный спецсимвол

\. \[ \* \$ \^ \\

означают сами себя;

.

означает один любой символ кроме \n;

[abc] или [a-b]

означает любой символ из перечисленных (из интервала);

[abc-]

минус в конце означает сам символ -;

[]abc]

внутри [] скобка ] на первом месте означает сама себя;

[^a-z]

крышка ^ означает отрицание, т.е. любой символ кроме перечисленных;

[a-z^]

крышка не на первом месте означает сама себя;

[\*.]

спецсимволы внутри [] не несут специального значения, а представляют сами себя;

C*

любое (0 и более) число символов C;

.*

любое число любых символов;

выражение*

любое число (0 и более) повторений выражения, например [0-9]* означает число (последовательность цифр) или пустое место. Ищется самое длинное прижатое

влево

подвыражение;

выражение\{n,m\}

повторение выражения от n до m раз (включительно), где числа не превосходят 255;

выражение\{n,\}

повторение по крайней мере n раз, например [0-9]\{1,\} означает число;

выражение\{n\}

повторение ровно n раз;

выражение$

строка, чей конец удовлетворяет выражению, например .*define.*\\$

^выражение

строка, чье начало удовлетворяет выражению;

\n

символ перевода строки;

\(.....\)

сегмент. Сопоставившаяся с ним подстрока будет запомнена;

\N

где N цифра. Данный участок образца должен совпадать с N-ым сегментом (нумерация с 1).

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

    #include <stdio.h>
    #include <ctype.h>
    #define INIT            register char *sp = instring;
    #define GETC()          (*sp++)
    #define PEEKC()         (*sp)
    #define UNGETC(c)       (--sp)
    #define RETURN(ptr)     return
    #define ERROR(code)  \
    {fprintf(stderr,"%s:ERR%d\n",instring,code);exit(177);}
    #               include <regexp.h>
    #define EOL             '\0'    /* end of line */
    #define ESIZE           512
    int matchReg(char *str, char *pattern){
      static char oldPattern[256];
      static char compiledExpr[ESIZE];
      if( strcmp(pattern, oldPattern)){  /* различны */
        /* compile regular expression */
          compile(pattern,
                  compiledExpr, &compiledExpr[ESIZE], EOL);
          strcpy(oldPattern, pattern);   /* запомнить   */
      }
      return step(str, compiledExpr);    /* сопоставить */
    }
    /* Пример вызова: reg '^int' 'int$' char | less */
    /* reg 'putchar.*(.*)' < reg.c | more */
    void main(int ac, char **av){
      char inputline[BUFSIZ]; register i;
      while(gets(inputline)){
        for(i=1; i < ac; i++)
          if(matchReg(inputline, av[i])){
      char *p; extern char *loc1, *loc2;
    /*printf("%s\n", inputline);*/
    /* Напечатать строку,
     * выделяя сопоставившуюся часть жирно */
      for(p=inputline; p != loc1; p++) putchar(*p);
      for(           ; p != loc2; p++)
         if(isspace((unsigned char) *p))
              putchar(*p);
         else printf("%c\b%c", *p, *p);
      for(           ; *p;        p++) putchar(*p);
      putchar('\n');
      break;
          }
        }
    }

7.43.

Используя <regexp.h> напишите программу, производящую контекстную замену во всех строках файла. Если строка не удовлетворяет регулярному выражению - она остается неизменной. Примеры вызова:

    $  regsub '\([0-9]\{1,\}\)'   '(\1)'
    $  regsub 'f(\(.*\),\(.*\))'  'f(\2,\1)'  < file

Вторая команда должна заменять все вхождения f(a,b) на f(b,a). Выражение, обозначенное в образце как \(...\), подставляется на место соответствующей конструкции \N во втором аргументе, где N - цифра, номер сегмента. Чтобы поместить в выход сам символ \, его надо удваивать: \\.

    /* Контекстная замена */
    #include <stdio.h>
    #include <ctype.h>
    #define INIT            register char *sp = instring;
    #define GETC()          (*sp++)
    #define PEEKC()         (*sp)
    #define UNGETC(c)       (--sp)
    #define RETURN(ptr)     return
    #define ERROR(code)     regerr(code)
    void regerr();
    #                include <regexp.h>
    #define EOL             '\0'    /* end of line */
    #define ESIZE           512
    short all = 0;
    /* ключ -a означает, что в строке надо заменить ВСЕ вхождения образца (global, all):
     *          regsub -a   int INT
     *          "aa int bbb int cccc" -> "aa INT bbb INT cccc"
     *
     * step() находит САМУЮ ДЛИННУЮ подстроку, удовлетворяющую выражению,
     * поэтому  regsub 'f(\(.*\),\(.*\))'  'f(\2,\1)'
     * заменит  "aa f(1,2) bb f(3,4) cc" -> "aa f(4,1,2) bb f(3) cc'
     *               |___________|_|             |_|___________|
     */
    char compiled[ESIZE], line[512];
    void main(int ac, char *av[]){
       register char *s, *p; register n;  extern int nbra;
       extern char *braslist[], *braelist[], *loc1, *loc2;
       if( ac > 1 && !strcmp(av[1], "-a")){ ac--; av++; all++; }
       if(ac != 3){
            fprintf(stderr, "Usage: %s [-a] pattern subst\n", av[0]);
            exit(1);
       }
       compile(av[1], compiled, compiled + sizeof compiled, EOL);
       while( gets(line) != NULL ){
           if( !step(s = line, compiled)){
               printf("%s\n", line); continue;
           }
           do{
             /* Печатаем начало строки */
             for( ; s != loc1; s++) putchar(*s);
             /* Делаем замену */
             for(s=av[2]; *s; s++)
               if(*s == '\\'){
                 if(isdigit(s[1])){ /* сегмент */
                    int num = *++s - '1';
                    if(num < 0 || num >= nbra){
                       fprintf(stderr, "Bad block number %d\n", num+1);
                       exit(2);
                    }
                    for(p=braslist[num]; p != braelist[num]; ++p)
                        putchar(*p);
                 } else if(s[1] == '&'){
                    ++s;  /* вся сопоставленная строка */
                    for(p=loc1; p != loc2; ++p)
                        putchar(*p);
                 } else putchar(*++s);
               } else putchar(*s);
           } while(all && step(s = loc2, compiled));
           /* Остаток строки */
           for(s=loc2; *s; s++) putchar(*s);
           putchar('\n');
       } /* endwhile */
    }
    void regerr(int code){ char *msg;
       switch(code){
       case 11: msg = "Range endpoint too large.";     break;
       case 16: msg = "Bad number.";                   break;
       case 25: msg = "\\digit out of range.";         break;
       case 36: msg = "Illegal or missing delimiter."; break;
       case 41: msg = "No remembered search string.";  break;
       case 42: msg = "\\(~\\) imbalance.";            break;
       case 43: msg = "Too many \\(.";                 break;
       case 44: msg = "More than 2 numbers given in \\{~\\\"}."; break;
       case 45: msg = "} expected after \\.";          break;
       case 46: msg = "First number exceeds second in \\{~\\}."; break;
       case 49: msg = "[ ] imbalance.";                break;
       case 50: msg = "Regular expression overflow.";  break;
       default: msg = "Unknown error";                 break;
       } fputs(msg, stderr); fputc('\n', stderr); exit(code);
    }
    void prfields(){
            int i;
            for(i=0; i < nbra; i++)
                    prfield(i);
    }
    void prfield(int n){
            char *fbeg = braslist[n], *fend = braelist[n];
            printf("\\%d='", n+1);
            for(; fbeg != fend; fbeg++)
                    putchar(*fbeg);
            printf("'\n");
    }

7.44.

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

    /* Алгоритм быстрого поиска подстроки.
     * Дж. Мур, Р. Бойер, 1976 Texas
     * Смотри: Communications of the ACM 20, 10 (Oct., 1977), 762-772
     *
     * Этот алгоритм выгоден при многократном поиске образца в
     * большом количестве строк, причем если они равной длины 
     * можно сэкономить еще и на операции strlen(str).
     * Алгоритм характерен тем, что при неудаче производит сдвиг не на
     * один, а сразу на несколько символов вправо.
     * В лучшем случае алгоритм делает slen/plen сравнений.
     */
    char *pattern;          /* образец (что искать) */
    static int plen;        /* длина образца */
    static int d[256];      /* таблица сдвигов; в алфавите ASCII 
                            * 256 букв. */
    /* расстояние от конца образца до позиции i в нем */
    #define DISTANCE(i)     ((plen-1) - (i))
    /* Поиск:
     * выдать индекс вхождения pattern в str,
     * либо -1, если не входит
     */
    int indexBM( str )  char *str;      /* в чем искать */
    {
        int slen = strlen(str); /* длина строки */
        register int pindx;  /* индекс сравниваемой буквы в образце */
        register int cmppos; /* индекс сравниваемой буквы в строке  */
        register int endpos; /* позиция в строке, к которой "приставляется"
                              * последняя буква образца */
        /* пока образец помещается в остаток строки */
        for( endpos = plen-1; endpos < slen ; ){
               /* Для отладки: pr(str, pattern, endpos - (plen-1), 0); /**/
               /* просмотр образца от конца к началу */
               for( cmppos = endpos, pindx = (plen - 1);
                                     pindx >= 0 ;
                                     cmppos--, pindx-- )
                  if( str[cmppos] != pattern[pindx] ){
                     /* Сдвиг, который ставит самый правый в образце
                      * символ str[endpos] как раз под endpos-тую
                      * позицию строки. Если же такой символ в образце не
                      * содержится (или содержится только на конце),
                      * то начало образца устанавливается в endpos+1 ую
                      * позицию
                      */
                     endpos += d[ str[endpos] & 0377 ];
                     break;    /* & 0377 подавляет расширение знака. Еще  */
                  }            /* можно сделать все char -> unsigned char */
               if( pindx < 0 ) return ( endpos - (plen-1));
               /* Нашел: весь образец вложился */
        }
        return( -1 );       /* Не найдено */
    }
    /* Разметка таблицы сдвигов */
    void compilePatternBM( ptrn ) char *ptrn; {
            register int c;
            pattern = ptrn; plen = strlen(ptrn);
            /* c - номер буквы алфавита */
            for(c = 0; c < 256; c++)
                    d[c] = plen;
                    /* сдвиг на длину всего образца */
            /* c - позиция в образце */
            for(c = 0; c < plen - 1; c++)
                    d[ pattern[c] & 0377 ] = DISTANCE(c);
            /* Сдвиг равен расстоянию от самого правого
             * (кроме последней буквы образца)
             * вхождения буквы в образец до конца образца.
             * Заметим, что если буква входит в образец несколько раз,
             * то цикл учитывает последнее (самое правое) вхождение.
             */
    }
    /* Печать найденных строк */
    void pr(s, p, n, nl) char *s, *p;
    {
            register i;
            printf("%4d\t%s\n", nl, s );
            printf("    \t");
            for(i = 0; i < n; i++ )
                    putchar( s[i] == '\t' ? '\t' : ' ' );
            printf( "%s\n", p );
    }
    /* Аналог программы fgrep */
    #include <stdio.h>
    char str[ 1024 ];        /* буфер для прочитанной строки */
    void main(ac, av) char **av;
    {
            int nline = 0;  /* номер строки файла */
            int ind;
            int retcode = 1;
            if(ac != 2){
                    fprintf(stderr, "Usage: %s 'pattern'\n", av[0] );
                    exit(33);
            }
            compilePatternBM( av[1] );
            while( gets(str) != NULL ){
                    nline++;
                    if((ind = indexBM(str)) >= 0 ){
                            retcode = 0;    /* O'KAY */
                            pr(str, pattern, ind, nline);
                    }
            }
            exit(retcode);
    }
    /* Пример работы алгоритма:
            peter piper picked a peck of pickled peppers.
            peck
            peter piper picked a peck of pickled peppers.
              peck
            peter piper picked a peck of pickled peppers.
                  peck
            peter piper picked a peck of pickled peppers.
                    peck
            peter piper picked a peck of pickled peppers.
                        peck
            peter piper picked a peck of pickled peppers.
                            peck
            peter piper picked a peck of pickled peppers.
                                peck
            peter piper picked a peck of pickled peppers.
                                 peck
    */

7.45.

Напишите аналогичную программу, выдающую все строки, удовлетворяющие упрощенному регулярному выражению, задаваемому как аргумент для main(). Используйте функцию match, написанную нами ранее. Вы написали аналог программы grep из UNIX (но с другим типом регулярного выражения, нежели в оригинале).

© Copyright А. Богатырев, 1992-95
Си в UNIX