![[BACK]](/cvsweb/icons/back.gif){kind=icon}
Return to regexp.c CVS log ![[TXT]](/cvsweb/icons/text.gif){kind=icon}
![[DIR]](/cvsweb/icons/dir.gif){kind=icon}
Up to [CSRG BSD Unix] / 43BSD / ucb / vgrind|
Return to regexp.c CVS log | Up to [CSRG BSD Unix] / 43BSD / ucb / vgrind |
1.1 root 1: /*
2: * Copyright (c) 1980 Regents of the University of California.
3: * All rights reserved. The Berkeley software License Agreement
4: * specifies the terms and conditions for redistribution.
5: */
6:
7: #ifndef lint
8: static char sccsid[] = "@(#)regexp.c 5.1 (Berkeley) 6/5/85";
9: #endif not lint
10:
11: #include <ctype.h>
12:
13: typedef int boolean;
14: #define TRUE 1
15: #define FALSE 0
16: #define NIL 0
17:
18: boolean l_onecase; /* true if upper and lower equivalent */
19:
20: #define makelower(c) (isupper((c)) ? tolower((c)) : (c))
21:
22: /* STRNCMP - like strncmp except that we convert the
23: * first string to lower case before comparing
24: * if l_onecase is set.
25: */
26:
27: STRNCMP(s1, s2, len)
28: register char *s1,*s2;
29: register int len;
30: {
31: if (l_onecase) {
32: do
33: if (*s2 - makelower(*s1))
34: return (*s2 - makelower(*s1));
35: else {
36: s2++;
37: s1++;
38: }
39: while (--len);
40: } else {
41: do
42: if (*s2 - *s1)
43: return (*s2 - *s1);
44: else {
45: s2++;
46: s1++;
47: }
48: while (--len);
49: }
50: return(0);
51: }
52:
53: /* The following routine converts an irregular expression to
54: * internal format.
55: *
56: * Either meta symbols (\a \d or \p) or character strings or
57: * operations ( alternation or perenthesizing ) can be
58: * specified. Each starts with a descriptor byte. The descriptor
59: * byte has STR set for strings, META set for meta symbols
60: * and OPER set for operations.
61: * The descriptor byte can also have the OPT bit set if the object
62: * defined is optional. Also ALT can be set to indicate an alternation.
63: *
64: * For metasymbols the byte following the descriptor byte identities
65: * the meta symbol (containing an ascii 'a', 'd', 'p', '|', or '('). For
66: * strings the byte after the descriptor is a character count for
67: * the string:
68: *
69: * meta symbols := descriptor
70: * symbol
71: *
72: * strings := descriptor
73: * character count
74: * the string
75: *
76: * operatins := descriptor
77: * symbol
78: * character count
79: */
80:
81: /*
82: * handy macros for accessing parts of match blocks
83: */
84: #define MSYM(A) (*(A+1)) /* symbol in a meta symbol block */
85: #define MNEXT(A) (A+2) /* character following a metasymbol block */
86:
87: #define OSYM(A) (*(A+1)) /* symbol in an operation block */
88: #define OCNT(A) (*(A+2)) /* character count */
89: #define ONEXT(A) (A+3) /* next character after the operation */
90: #define OPTR(A) (A+*(A+2)) /* place pointed to by the operator */
91:
92: #define SCNT(A) (*(A+1)) /* byte count of a string */
93: #define SSTR(A) (A+2) /* address of the string */
94: #define SNEXT(A) (A+2+*(A+1)) /* character following the string */
95:
96: /*
97: * bit flags in the descriptor
98: */
99: #define OPT 1
100: #define STR 2
101: #define META 4
102: #define ALT 8
103: #define OPER 16
104:
105: char *ure; /* pointer current position in unconverted exp */
106: char *ccre; /* pointer to current position in converted exp*/
107: char *malloc();
108:
109: char *
110: convexp(re)
111: char *re; /* unconverted irregular expression */
112: {
113: register char *cre; /* pointer to converted regular expression */
114:
115: /* allocate room for the converted expression */
116: if (re == NIL)
117: return (NIL);
118: if (*re == '\0')
119: return (NIL);
120: cre = malloc (4 * strlen(re) + 3);
121: ccre = cre;
122: ure = re;
123:
124: /* start the conversion with a \a */
125: *cre = META | OPT;
126: MSYM(cre) = 'a';
127: ccre = MNEXT(cre);
128:
129: /* start the conversion (its recursive) */
130: expconv ();
131: *ccre = 0;
132: return (cre);
133: }
134:
135: expconv()
136: {
137: register char *cs; /* pointer to current symbol in converted exp */
138: register char c; /* character being processed */
139: register char *acs; /* pinter to last alternate */
140: register int temp;
141:
142: /* let the conversion begin */
143: acs = NIL;
144: cs = NIL;
145: while (*ure != NIL) {
146: switch (c = *ure++) {
147:
148: case '\\':
149: switch (c = *ure++) {
150:
151: /* escaped characters are just characters */
152: default:
153: if (cs == NIL || (*cs & STR) == 0) {
154: cs = ccre;
155: *cs = STR;
156: SCNT(cs) = 1;
157: ccre += 2;
158: } else
159: SCNT(cs)++;
160: *ccre++ = c;
161: break;
162:
163: /* normal(?) metacharacters */
164: case 'a':
165: case 'd':
166: case 'e':
167: case 'p':
168: if (acs != NIL && acs != cs) {
169: do {
170: temp = OCNT(acs);
171: OCNT(acs) = ccre - acs;
172: acs -= temp;
173: } while (temp != 0);
174: acs = NIL;
175: }
176: cs = ccre;
177: *cs = META;
178: MSYM(cs) = c;
179: ccre = MNEXT(cs);
180: break;
181: }
182: break;
183:
184: /* just put the symbol in */
185: case '^':
186: case '$':
187: if (acs != NIL && acs != cs) {
188: do {
189: temp = OCNT(acs);
190: OCNT(acs) = ccre - acs;
191: acs -= temp;
192: } while (temp != 0);
193: acs = NIL;
194: }
195: cs = ccre;
196: *cs = META;
197: MSYM(cs) = c;
198: ccre = MNEXT(cs);
199: break;
200:
201: /* mark the last match sequence as optional */
202: case '?':
203: if (cs)
204: *cs = *cs | OPT;
205: break;
206:
207: /* recurse and define a subexpression */
208: case '(':
209: if (acs != NIL && acs != cs) {
210: do {
211: temp = OCNT(acs);
212: OCNT(acs) = ccre - acs;
213: acs -= temp;
214: } while (temp != 0);
215: acs = NIL;
216: }
217: cs = ccre;
218: *cs = OPER;
219: OSYM(cs) = '(';
220: ccre = ONEXT(cs);
221: expconv ();
222: OCNT(cs) = ccre - cs; /* offset to next symbol */
223: break;
224:
225: /* return from a recursion */
226: case ')':
227: if (acs != NIL) {
228: do {
229: temp = OCNT(acs);
230: OCNT(acs) = ccre - acs;
231: acs -= temp;
232: } while (temp != 0);
233: acs = NIL;
234: }
235: cs = ccre;
236: *cs = META;
237: MSYM(cs) = c;
238: ccre = MNEXT(cs);
239: return;
240:
241: /* mark the last match sequence as having an alternate */
242: /* the third byte will contain an offset to jump over the */
243: /* alternate match in case the first did not fail */
244: case '|':
245: if (acs != NIL && acs != cs)
246: OCNT(ccre) = ccre - acs; /* make a back pointer */
247: else
248: OCNT(ccre) = 0;
249: *cs |= ALT;
250: cs = ccre;
251: *cs = OPER;
252: OSYM(cs) = '|';
253: ccre = ONEXT(cs);
254: acs = cs; /* remember that the pointer is to be filles */
255: break;
256:
257: /* if its not a metasymbol just build a scharacter string */
258: default:
259: if (cs == NIL || (*cs & STR) == 0) {
260: cs = ccre;
261: *cs = STR;
262: SCNT(cs) = 1;
263: ccre = SSTR(cs);
264: } else
265: SCNT(cs)++;
266: *ccre++ = c;
267: break;
268: }
269: }
270: if (acs != NIL) {
271: do {
272: temp = OCNT(acs);
273: OCNT(acs) = ccre - acs;
274: acs -= temp;
275: } while (temp != 0);
276: acs = NIL;
277: }
278: return;
279: }
280: /* end of convertre */
281:
282:
283: /*
284: * The following routine recognises an irregular expresion
285: * with the following special characters:
286: *
287: * \? - means last match was optional
288: * \a - matches any number of characters
289: * \d - matches any number of spaces and tabs
290: * \p - matches any number of alphanumeric
291: * characters. The
292: * characters matched will be copied into
293: * the area pointed to by 'name'.
294: * \| - alternation
295: * \( \) - grouping used mostly for alternation and
296: * optionality
297: *
298: * The irregular expression must be translated to internal form
299: * prior to calling this routine
300: *
301: * The value returned is the pointer to the first non \a
302: * character matched.
303: */
304:
305: boolean _escaped; /* true if we are currently _escaped */
306: char *_start; /* start of string */
307:
308: char *
309: expmatch (s, re, mstring)
310: register char *s; /* string to check for a match in */
311: register char *re; /* a converted irregular expression */
312: register char *mstring; /* where to put whatever matches a \p */
313: {
314: register char *cs; /* the current symbol */
315: register char *ptr,*s1; /* temporary pointer */
316: boolean matched; /* a temporary boolean */
317:
318: /* initial conditions */
319: if (re == NIL)
320: return (NIL);
321: cs = re;
322: matched = FALSE;
323:
324: /* loop till expression string is exhausted (or at least pretty tired) */
325: while (*cs) {
326: switch (*cs & (OPER | STR | META)) {
327:
328: /* try to match a string */
329: case STR:
330: matched = !STRNCMP (s, SSTR(cs), SCNT(cs));
331: if (matched) {
332:
333: /* hoorah it matches */
334: s += SCNT(cs);
335: cs = SNEXT(cs);
336: } else if (*cs & ALT) {
337:
338: /* alternation, skip to next expression */
339: cs = SNEXT(cs);
340: } else if (*cs & OPT) {
341:
342: /* the match is optional */
343: cs = SNEXT(cs);
344: matched = 1; /* indicate a successful match */
345: } else {
346:
347: /* no match, error return */
348: return (NIL);
349: }
350: break;
351:
352: /* an operator, do something fancy */
353: case OPER:
354: switch (OSYM(cs)) {
355:
356: /* this is an alternation */
357: case '|':
358: if (matched)
359:
360: /* last thing in the alternation was a match, skip ahead */
361: cs = OPTR(cs);
362: else
363:
364: /* no match, keep trying */
365: cs = ONEXT(cs);
366: break;
367:
368: /* this is a grouping, recurse */
369: case '(':
370: ptr = expmatch (s, ONEXT(cs), mstring);
371: if (ptr != NIL) {
372:
373: /* the subexpression matched */
374: matched = 1;
375: s = ptr;
376: } else if (*cs & ALT) {
377:
378: /* alternation, skip to next expression */
379: matched = 0;
380: } else if (*cs & OPT) {
381:
382: /* the match is optional */
383: matched = 1; /* indicate a successful match */
384: } else {
385:
386: /* no match, error return */
387: return (NIL);
388: }
389: cs = OPTR(cs);
390: break;
391: }
392: break;
393:
394: /* try to match a metasymbol */
395: case META:
396: switch (MSYM(cs)) {
397:
398: /* try to match anything and remember what was matched */
399: case 'p':
400: /*
401: * This is really the same as trying the match the
402: * remaining parts of the expression to any subset
403: * of the string.
404: */
405: s1 = s;
406: do {
407: ptr = expmatch (s1, MNEXT(cs), mstring);
408: if (ptr != NIL && s1 != s) {
409:
410: /* we have a match, remember the match */
411: strncpy (mstring, s, s1 - s);
412: mstring[s1 - s] = '\0';
413: return (ptr);
414: } else if (ptr != NIL && (*cs & OPT)) {
415:
416: /* it was aoptional so no match is ok */
417: return (ptr);
418: } else if (ptr != NIL) {
419:
420: /* not optional and we still matched */
421: return (NIL);
422: }
423: if (!isalnum(*s1) && *s1 != '_')
424: return (NIL);
425: if (*s1 == '\\')
426: _escaped = _escaped ? FALSE : TRUE;
427: else
428: _escaped = FALSE;
429: } while (*s1++);
430: return (NIL);
431:
432: /* try to match anything */
433: case 'a':
434: /*
435: * This is really the same as trying the match the
436: * remaining parts of the expression to any subset
437: * of the string.
438: */
439: s1 = s;
440: do {
441: ptr = expmatch (s1, MNEXT(cs), mstring);
442: if (ptr != NIL && s1 != s) {
443:
444: /* we have a match */
445: return (ptr);
446: } else if (ptr != NIL && (*cs & OPT)) {
447:
448: /* it was aoptional so no match is ok */
449: return (ptr);
450: } else if (ptr != NIL) {
451:
452: /* not optional and we still matched */
453: return (NIL);
454: }
455: if (*s1 == '\\')
456: _escaped = _escaped ? FALSE : TRUE;
457: else
458: _escaped = FALSE;
459: } while (*s1++);
460: return (NIL);
461:
462: /* fail if we are currently _escaped */
463: case 'e':
464: if (_escaped)
465: return(NIL);
466: cs = MNEXT(cs);
467: break;
468:
469: /* match any number of tabs and spaces */
470: case 'd':
471: ptr = s;
472: while (*s == ' ' || *s == '\t')
473: s++;
474: if (s != ptr || s == _start) {
475:
476: /* match, be happy */
477: matched = 1;
478: cs = MNEXT(cs);
479: } else if (*s == '\n' || *s == '\0') {
480:
481: /* match, be happy */
482: matched = 1;
483: cs = MNEXT(cs);
484: } else if (*cs & ALT) {
485:
486: /* try the next part */
487: matched = 0;
488: cs = MNEXT(cs);
489: } else if (*cs & OPT) {
490:
491: /* doesn't matter */
492: matched = 1;
493: cs = MNEXT(cs);
494: } else
495:
496: /* no match, error return */
497: return (NIL);
498: break;
499:
500: /* check for end of line */
501: case '$':
502: if (*s == '\0' || *s == '\n') {
503:
504: /* match, be happy */
505: s++;
506: matched = 1;
507: cs = MNEXT(cs);
508: } else if (*cs & ALT) {
509:
510: /* try the next part */
511: matched = 0;
512: cs = MNEXT(cs);
513: } else if (*cs & OPT) {
514:
515: /* doesn't matter */
516: matched = 1;
517: cs = MNEXT(cs);
518: } else
519:
520: /* no match, error return */
521: return (NIL);
522: break;
523:
524: /* check for start of line */
525: case '^':
526: if (s == _start) {
527:
528: /* match, be happy */
529: matched = 1;
530: cs = MNEXT(cs);
531: } else if (*cs & ALT) {
532:
533: /* try the next part */
534: matched = 0;
535: cs = MNEXT(cs);
536: } else if (*cs & OPT) {
537:
538: /* doesn't matter */
539: matched = 1;
540: cs = MNEXT(cs);
541: } else
542:
543: /* no match, error return */
544: return (NIL);
545: break;
546:
547: /* end of a subexpression, return success */
548: case ')':
549: return (s);
550: }
551: break;
552: }
553: }
554: return (s);
555: }
This archive runs on limited infrastructure. Preserving old code on modern bandwidth. Automated agents are requested to crawl responsibly.