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