![[BACK]](/cvsweb/icons/back.gif){kind=icon}
Return to regex.c CVS log ![[TXT]](/cvsweb/icons/text.gif){kind=icon}
![[DIR]](/cvsweb/icons/dir.gif){kind=icon}
Up to [CSRG BSD Unix] / 40BSD / libc / gen|
Return to regex.c CVS log | Up to [CSRG BSD Unix] / 40BSD / libc / gen |
1.1 root 1: #
2:
3: /*
4: * routines to do regular expression matching
5: *
6: * Entry points:
7: *
8: * re_comp(s)
9: * char *s;
10: * ... returns 0 if the string s was compiled successfully,
11: * a pointer to an error message otherwise.
12: * If passed 0 or a null string returns without changing
13: * the currently compiled re (see note 11 below).
14: *
15: * re_exec(s)
16: * char *s;
17: * ... returns 1 if the string s matches the last compiled regular
18: * expression,
19: * 0 if the string s failed to match the last compiled
20: * regular expression, and
21: * -1 if the compiled regular expression was invalid
22: * (indicating an internal error).
23: *
24: * The strings passed to both re_comp and re_exec may have trailing or
25: * embedded newline characters; they are terminated by nulls.
26: *
27: * The identity of the author of these routines is lost in antiquity;
28: * this is essentially the same as the re code in the original V6 ed.
29: *
30: * The regular expressions recognized are described below. This description
31: * is essentially the same as that for ed.
32: *
33: * A regular expression specifies a set of strings of characters.
34: * A member of this set of strings is said to be matched by
35: * the regular expression. In the following specification for
36: * regular expressions the word `character' means any character but NUL.
37: *
38: * 1. Any character except a special character matches itself.
39: * Special characters are the regular expression delimiter plus
40: * \ [ . and sometimes ^ * $.
41: * 2. A . matches any character.
42: * 3. A \ followed by any character except a digit or ( )
43: * matches that character.
44: * 4. A nonempty string s bracketed [s] (or [^s]) matches any
45: * character in (or not in) s. In s, \ has no special meaning,
46: * and ] may only appear as the first letter. A substring
47: * a-b, with a and b in ascending ASCII order, stands for
48: * the inclusive range of ASCII characters.
49: * 5. A regular expression of form 1-4 followed by * matches a
50: * sequence of 0 or more matches of the regular expression.
51: * 6. A regular expression, x, of form 1-8, bracketed \(x\)
52: * matches what x matches.
53: * 7. A \ followed by a digit n matches a copy of the string that the
54: * bracketed regular expression beginning with the nth \( matched.
55: * 8. A regular expression of form 1-8, x, followed by a regular
56: * expression of form 1-7, y matches a match for x followed by
57: * a match for y, with the x match being as long as possible
58: * while still permitting a y match.
59: * 9. A regular expression of form 1-8 preceded by ^ (or followed
60: * by $), is constrained to matches that begin at the left
61: * (or end at the right) end of a line.
62: * 10. A regular expression of form 1-9 picks out the longest among
63: * the leftmost matches in a line.
64: * 11. An empty regular expression stands for a copy of the last
65: * regular expression encountered.
66: */
67:
68: /*
69: * constants for re's
70: */
71: #define CBRA 1
72: #define CCHR 2
73: #define CDOT 4
74: #define CCL 6
75: #define NCCL 8
76: #define CDOL 10
77: #define CEOF 11
78: #define CKET 12
79: #define CBACK 18
80:
81: #define CSTAR 01
82:
83: #define ESIZE 512
84: #define NBRA 9
85:
86: static char expbuf[ESIZE], *braslist[NBRA], *braelist[NBRA];
87: static char circf;
88:
89: /*
90: * compile the regular expression argument into a dfa
91: */
92: char *
93: re_comp(sp)
94: register char *sp;
95: {
96: register int c;
97: register char *ep = expbuf;
98: int cclcnt, numbra = 0;
99: char *lastep = 0;
100: char bracket[NBRA];
101: char *bracketp = &bracket[0];
102: static char *retoolong = "Regular expression too long";
103:
104: #define comerr(msg) {expbuf[0] = 0; numbra = 0; return(msg); }
105:
106: if (sp == 0 || *sp == '\0') {
107: if (*ep == 0)
108: return("No previous regular expression");
109: return(0);
110: }
111: if (*sp == '^') {
112: circf = 1;
113: sp++;
114: }
115: else
116: circf = 0;
117: for (;;) {
118: if (ep >= &expbuf[ESIZE])
119: comerr(retoolong);
120: if ((c = *sp++) == '\0') {
121: if (bracketp != bracket)
122: comerr("unmatched \\(");
123: *ep++ = CEOF;
124: *ep++ = 0;
125: return(0);
126: }
127: if (c != '*')
128: lastep = ep;
129: switch (c) {
130:
131: case '.':
132: *ep++ = CDOT;
133: continue;
134:
135: case '*':
136: if (lastep == 0 || *lastep == CBRA || *lastep == CKET)
137: goto defchar;
138: *lastep |= CSTAR;
139: continue;
140:
141: case '$':
142: if (*sp != '\0')
143: goto defchar;
144: *ep++ = CDOL;
145: continue;
146:
147: case '[':
148: *ep++ = CCL;
149: *ep++ = 0;
150: cclcnt = 1;
151: if ((c = *sp++) == '^') {
152: c = *sp++;
153: ep[-2] = NCCL;
154: }
155: do {
156: if (c == '\0')
157: comerr("missing ]");
158: if (c == '-' && ep [-1] != 0) {
159: if ((c = *sp++) == ']') {
160: *ep++ = '-';
161: cclcnt++;
162: break;
163: }
164: while (ep[-1] < c) {
165: *ep = ep[-1] + 1;
166: ep++;
167: cclcnt++;
168: if (ep >= &expbuf[ESIZE])
169: comerr(retoolong);
170: }
171: }
172: *ep++ = c;
173: cclcnt++;
174: if (ep >= &expbuf[ESIZE])
175: comerr(retoolong);
176: } while ((c = *sp++) != ']');
177: lastep[1] = cclcnt;
178: continue;
179:
180: case '\\':
181: if ((c = *sp++) == '(') {
182: if (numbra >= NBRA)
183: comerr("too many \\(\\) pairs");
184: *bracketp++ = numbra;
185: *ep++ = CBRA;
186: *ep++ = numbra++;
187: continue;
188: }
189: if (c == ')') {
190: if (bracketp <= bracket)
191: comerr("unmatched \\)");
192: *ep++ = CKET;
193: *ep++ = *--bracketp;
194: continue;
195: }
196: if (c >= '1' && c < ('1' + NBRA)) {
197: *ep++ = CBACK;
198: *ep++ = c - '1';
199: continue;
200: }
201: *ep++ = CCHR;
202: *ep++ = c;
203: continue;
204:
205: defchar:
206: default:
207: *ep++ = CCHR;
208: *ep++ = c;
209: }
210: }
211: }
212:
213: /*
214: * match the argument string against the compiled re
215: */
216: int
217: re_exec(p1)
218: register char *p1;
219: {
220: register char *p2 = expbuf;
221: register int c;
222: int rv;
223:
224: for (c = 0; c < NBRA; c++) {
225: braslist[c] = 0;
226: braelist[c] = 0;
227: }
228: if (circf)
229: return((advance(p1, p2)));
230: /*
231: * fast check for first character
232: */
233: if (*p2 == CCHR) {
234: c = p2[1];
235: do {
236: if (*p1 != c)
237: continue;
238: if (rv = advance(p1, p2))
239: return(rv);
240: } while (*p1++);
241: return(0);
242: }
243: /*
244: * regular algorithm
245: */
246: do
247: if (rv = advance(p1, p2))
248: return(rv);
249: while (*p1++);
250: return(0);
251: }
252:
253: /*
254: * try to match the next thing in the dfa
255: */
256: static int
257: advance(lp, ep)
258: register char *lp, *ep;
259: {
260: register char *curlp;
261: int ct, i;
262: int rv;
263:
264: for (;;)
265: switch (*ep++) {
266:
267: case CCHR:
268: if (*ep++ == *lp++)
269: continue;
270: return(0);
271:
272: case CDOT:
273: if (*lp++)
274: continue;
275: return(0);
276:
277: case CDOL:
278: if (*lp == '\0')
279: continue;
280: return(0);
281:
282: case CEOF:
283: return(1);
284:
285: case CCL:
286: if (cclass(ep, *lp++, 1)) {
287: ep += *ep;
288: continue;
289: }
290: return(0);
291:
292: case NCCL:
293: if (cclass(ep, *lp++, 0)) {
294: ep += *ep;
295: continue;
296: }
297: return(0);
298:
299: case CBRA:
300: braslist[*ep++] = lp;
301: continue;
302:
303: case CKET:
304: braelist[*ep++] = lp;
305: continue;
306:
307: case CBACK:
308: if (braelist[i = *ep++] == 0)
309: return(-1);
310: if (backref(i, lp)) {
311: lp += braelist[i] - braslist[i];
312: continue;
313: }
314: return(0);
315:
316: case CBACK|CSTAR:
317: if (braelist[i = *ep++] == 0)
318: return(-1);
319: curlp = lp;
320: ct = braelist[i] - braslist[i];
321: while (backref(i, lp))
322: lp += ct;
323: while (lp >= curlp) {
324: if (rv = advance(lp, ep))
325: return(rv);
326: lp -= ct;
327: }
328: continue;
329:
330: case CDOT|CSTAR:
331: curlp = lp;
332: while (*lp++)
333: ;
334: goto star;
335:
336: case CCHR|CSTAR:
337: curlp = lp;
338: while (*lp++ == *ep)
339: ;
340: ep++;
341: goto star;
342:
343: case CCL|CSTAR:
344: case NCCL|CSTAR:
345: curlp = lp;
346: while (cclass(ep, *lp++, ep[-1] == (CCL|CSTAR)))
347: ;
348: ep += *ep;
349: goto star;
350:
351: star:
352: do {
353: lp--;
354: if (rv = advance(lp, ep))
355: return(rv);
356: } while (lp > curlp);
357: return(0);
358:
359: default:
360: return(-1);
361: }
362: }
363:
364: backref(i, lp)
365: register int i;
366: register char *lp;
367: {
368: register char *bp;
369:
370: bp = braslist[i];
371: while (*bp++ == *lp++)
372: if (bp >= braelist[i])
373: return(1);
374: return(0);
375: }
376:
377: int
378: cclass(set, c, af)
379: register char *set, c;
380: int af;
381: {
382: register int n;
383:
384: if (c == 0)
385: return(0);
386: n = *set++;
387: while (--n)
388: if (*set++ == c)
389: return(af);
390: return(! af);
391: }
This archive runs on limited infrastructure. Preserving old code on modern bandwidth. Automated agents are requested to crawl responsibly.