Напишите функцию 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). Это позволяет обрабатывать (в принципе) разные стили шаблонов имен.
Изучите раздел руководства man regexp и include-файл /usr/include/regexp.h, содержащий исходные тексты функций compile и step для регулярного выражения в стиле программ ed, lex, grep: одна буква C или заэкранированный спецсимвол
Напишите функцию 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;
}
}
}
Используя <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");
}
Составьте функцию поиска подстроки в строке. Используя ее, напишите программу поиска подстроки в текстовом файле. Программа должна выводить строки (либо номера строк) файла, в которых встретилась данная подстрока. Подстрока задается в качестве аргумента функции 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
*/
Напишите аналогичную программу, выдающую все строки, удовлетворяющие упрощенному регулярному выражению, задаваемому как аргумент для main(). Используйте функцию match, написанную нами ранее. Вы написали аналог программы grep из UNIX (но с другим типом регулярного выражения, нежели в оригинале).
© Copyright А. Богатырев, 1992-95
Си в UNIX
Назад | Содержание | Вперед