![[BACK]](/cvsweb/icons/back.gif){kind=icon}
Return to grep2.c CVS log ![[TXT]](/cvsweb/icons/text.gif){kind=icon}
![[DIR]](/cvsweb/icons/dir.gif){kind=icon}
Up to [MW Coherent from dump] / coherent / d / bin / grep|
Return to grep2.c CVS log | Up to [MW Coherent from dump] / coherent / d / bin / grep |
1.1 root 1: /*
2: * Regular expression routines.
3: * These routines are currently used by grep but
4: * they are somewhat general and thus could be
5: * used elsewhere.
6: */
7:
8: #include <stdio.h>
9: #include <ctype.h>
10: #include "grep.h"
11:
12: char *newcc();
13: char *e_exec();
14:
15:
16: static char repri[] = {
17: 0 /* REEND */, 2 /* STEND */,
18: 3 /* OR */, 6 /* LPAR */,
19: 1 /* RPAR */, 5 /* CLOS */,
20: 5 /* NECLOS */, 5 /* ZORO */,
21: 4 /* CONC */
22: };
23:
24: RE **rebuild();
25: RE *renode();
26: static union rebit relval;
27: static char cc[NCLASS];
28: static (*reinf)();
29: static (*reunf)();
30: static char *rein;
31:
32: static char resyn[] = "Regular expression syntax error";
33: static char reoflo[] = "Regular expression overflow";
34: static char nospace[] = "Out of space";
35:
36: char *reerror; /* Erro code */
37: int redual; /* Set for dual-case comparisons */
38: int refull; /* Full expressions accepted */
39:
40: /*
41: * Lexical token reader for
42: * regular expressions.
43: */
44: static
45: relex(ec)
46: {
47: register c;
48:
49: if ((c = (*reinf)()) == ec)
50: return (REEND);
51: switch (c) {
52: case EOF:
53: case '\n':
54: reerror = "Non-terminated regular expression";
55: return (REEND);
56:
57: case '[':
58: return (cclass(ec));
59:
60: case '^':
61: return (BOL);
62:
63: case '$':
64: return (EOL);
65:
66: case '(':
67: if (!refull)
68: goto def;
69: return (LPAR);
70:
71: case ')':
72: if (!refull)
73: goto def;
74: return (RPAR);
75:
76: case '.':
77: return (ANY);
78:
79: case '|':
80: if (!refull)
81: goto def;
82: return (OR);
83:
84: case '*':
85: return (CLOS);
86:
87: case '?':
88: if (!refull)
89: goto def;
90: return (ZORO);
91:
92: case '+':
93: if (!refull)
94: goto def;
95: return (NECLOS);
96:
97: case '\\':
98: c = (*reinf)();
99: default:
100: def:
101: relval.u_ival = c;
102: return (redual ? DCONC : CONC);
103: }
104: }
105:
106: /*
107: * Read in a character class from
108: * an RE (called from relex).
109: */
110: static
111: cclass(ec)
112: int ec;
113: {
114: register c, i, pc;
115: int comp;
116:
117: for (i=0; i<sizeof cc; i++)
118: cc[i] = 0;
119: if ((c = (*reinf)()) != '^') {
120: comp = 0;
121: (*reunf)(c);
122: } else
123: comp = 1;
124: pc = ec;
125: while ((c = (*reinf)()) != ']') {
126: if (c == ec) {
127: reerror = "Non-terminated character class";
128: return (REEND);
129: }
130: if (c=='-' && pc!=ec) {
131: if ((c = (*reinf)()) == ']')
132: break;
133: for (i=pc; i<=c; i++)
134: cc[i/NBPC] |= 1<<(i%NBPC);
135: pc = ec;
136: } else {
137: cc[c/NBPC] |= 1<<(c%NBPC);
138: pc = c;
139: }
140: }
141: if (comp)
142: for (i=0; i<sizeof cc; i++)
143: cc[i] ^= -1;
144: if ((relval.u_cptr = newcc(cc)) == NULL)
145: return (REEND);
146: return (redual ? DCCLASS : CCLASS);
147: }
148:
149: /*
150: * Allocate space for a new character class
151: * and copy into it.
152: */
153: static char *
154: newcc(occ)
155: register char *occ;
156: {
157: register char *ncc;
158: register unsigned n;
159: char *rcc;
160:
161: n = NCLASS;
162: if ((rcc = ncc = malloc(n)) == NULL) {
163: reerror = nospace;
164: return (NULL);
165: }
166: do {
167: *ncc++ = *occ++;
168: } while (--n);
169: return (rcc);
170: }
171:
172: /*
173: * Parse a regular expression.
174: * The arguments are an input string to parse (`in'),
175: * the end character to terminated the expression (`ec'),
176: * and (if `in' is NULL) functions to get and unget characters,
177: * getf and ungetf, respectively.
178: */
179: RE *
180: reparse(in, ec, getf, ungetf)
181: char *in;
182: int (*getf)(), (*ungetf)();
183: {
184: RE *restk[NRE];
185: struct opstk {
186: char o_op;
187: char o_pri;
188: } opstk[NRE];
189: register struct opstk *osp;
190: register op;
191: register RE **rsp;
192: int concflg, op1, pri;
193:
194: if ((rein = in) != NULL) {
195: reinf = reget;
196: reunf = reunget;
197: } else {
198: reinf = getf;
199: reunf = ungetf;
200: }
201: reerror = NULL;
202: concflg = 0;
203: osp = opstk;
204: osp->o_op = STEND;
205: osp->o_pri = repri[STEND];
206: rsp = restk;
207: *rsp++ = NULL;
208:
209: for (;;) {
210: if (termop(op = relex(ec))) {
211: if ((*rsp++ = renode(op, relval.u_cptr, NULL)) == NULL)
212: return (NULL);
213: if (rsp >= &restk[NRE-1]) {
214: reerror = reoflo;
215: return (NULL);
216: }
217: if (!concflg) {
218: concflg++;
219: continue;
220: } else
221: op = CONC;
222: } else if (op == OR) {
223: if (!concflg) {
224: reerror = resyn;
225: return (NULL);
226: }
227: concflg = 0;
228: } else if (op==CLOS || op==NECLOS || op==ZORO) {
229: if (!concflg) {
230: reerror = resyn;
231: return (NULL);
232: }
233: } else if (op == LPAR) {
234: if (concflg) {
235: (++osp)->o_op = CONC;
236: osp->o_pri = repri[CONC];
237: concflg = 0;
238: }
239: }
240: pri = repri[op];
241: for (;;) {
242: if (reerror != NULL)
243: return (NULL);
244: if (pri>osp->o_pri || (op==CONC && osp->o_op==CONC)) {
245: if (op == LPAR)
246: pri = repri[RPAR];
247: if (osp >= &opstk[NRE-1]) {
248: reerror = reoflo;
249: return (NULL);
250: }
251: (++osp)->o_op = op;
252: osp->o_pri = pri;
253: if (!postop(op))
254: break;
255: else
256: pri = repri[REEND];
257: }
258: switch (op1 = (osp--)->o_op) {
259: case STEND:
260: if (op == REEND)
261: return (*--rsp);
262: osp++;
263: break;
264:
265: case LPAR:
266: if (op != RPAR) {
267: reerror = "Unbalanced parentheses";
268: return (NULL);
269: }
270: break;
271:
272: default:
273: rsp = rebuild(rsp, op1);
274: continue;
275: }
276: break;
277: }
278: }
279: }
280:
281:
282: static RE **
283: rebuild(rsp, op)
284: register RE **rsp;
285: {
286: register RE *left, *right;
287:
288: switch (op) {
289: case OR:
290: right = *--rsp;
291: left = *--rsp;
292: break;
293:
294: case CLOS:
295: case NECLOS:
296: case ZORO:
297: left = *--rsp;
298: right = NULL;
299: break;
300:
301: case CONC:
302: right = *--rsp;
303: left = *--rsp;
304: if (left->r_next == NULL)
305: left->r_next = right;
306: else {
307: for (; left->r_next->r_next!=NULL; left = left->r_next)
308: ;
309: left->r_next->r_next = right;
310: }
311: return (++rsp);
312:
313: default:
314: reerror = "RE botch in rebuild";
315: }
316: *rsp++ = renode(op, left, right);
317: return (rsp);
318: }
319:
320: /*
321: * Build regular expression node.
322: */
323: static RE *
324: renode(op, left, right)
325: RE *left, *right;
326: {
327: register RE *rep;
328:
329: if ((rep = (RE *)malloc(sizeof (RE))) == NULL) {
330: reerror = nospace;
331: return (NULL);
332: }
333: rep->r_next = (RE*)NULL;
334: rep->r_op = op;
335: rep->r_left.u_re = left;
336: rep->r_right.u_re = right;
337: return (rep);
338: }
339:
340: static char *sb; /* string beginning */
341:
342: /*
343: * User-callable driver for regular expression
344: * execution. Called with regular expression code and
345: * text string.
346: */
347: reinterp(rep, s)
348: RE *rep;
349: register char *s;
350: {
351: sb = s;
352: if (rep!=NULL && rep->r_op==BOL)
353: return(e_exec(rep, s) != NULL);
354: for (; *s!='\0'; s++)
355: if (e_exec(rep, s) != NULL)
356: return (1);
357: return (0);
358: }
359:
360: /*
361: * Internal regular expression
362: * execution routines
363: */
364: static char *
365: e_exec(rep, s)
366: register RE *rep;
367: register char *s;
368: {
369: register c;
370: char *ss, *es;
371:
372: for ( ; rep!=NULL; rep = rep->r_next)
373: switch (rep->r_op) {
374: case BOL:
375: if (s != sb)
376: return (NULL);
377: break;
378:
379: case EOL:
380: if (*s != '\0')
381: return (NULL);
382: break;
383:
384: case ANY:
385: if (*s++ == '\0')
386: return (NULL);
387: break;
388:
389: case CONC:
390: if (*s++ != rep->r_left.u_ival)
391: return (NULL);
392: break;
393:
394: case DCONC:
395: if (islower(rep->r_left.u_ival)) {
396: if (isupper(c = *s++))
397: c = tolower(c);
398: if (c != rep->r_left.u_ival)
399: return (NULL);
400: } else
401: if (*s++ != rep->r_left.u_ival)
402: return (NULL);
403: break;
404:
405: case CCLASS:
406: c = *s++;
407: if ((rep->r_left.u_cptr[c/NBPC] & (1<<(c%NBPC))) == 0)
408: return (NULL);
409: break;
410:
411: case DCCLASS:
412: if ((c = *s++)>='A' && c<='Z')
413: c |= 'a'-'A';
414: if ((rep->r_left.u_cptr[c/NBPC] & (1<<(c%NBPC))) == 0)
415: return (NULL);
416: break;
417:
418: case OR:
419: ss = s;
420: if ((s = e_exec(rep->r_left.u_re, s)) == NULL)
421: if ((s = e_exec(rep->r_right.u_re, ss))==NULL)
422: return (NULL);
423: break;
424:
425: case CLOS:
426: ss = s;
427: while ((es = e_exec(rep->r_left.u_re, s)) != NULL)
428: s = es;
429: while (s >= ss)
430: if ((es = e_exec(rep->r_next, s--))!=NULL)
431: return(es);
432: return (NULL);
433:
434: case NECLOS:
435: ss = s;
436: while ((es = e_exec(rep->r_left.u_re, s)) != NULL)
437: s = es;
438: while (s > ss)
439: if ((es = e_exec(rep->r_next, s--))!=NULL)
440: return (es);
441: return (NULL);
442:
443: case ZORO:
444: ss = s;
445: if ((es = e_exec(rep->r_left.u_re, s)) != NULL)
446: s = es;
447: while (s >= ss)
448: if ((es = e_exec(rep->r_next, s--))!=NULL)
449: return (es);
450: return (NULL);
451:
452: default:
453: fprintf(stderr, "Regular expression botch\n");
454: exit(2);
455: }
456: return (s);
457: }
458:
459: /*
460: * Default functions to get and unget
461: * characters from the regular expression.
462: */
463: static
464: reget()
465: {
466: return (*rein++);
467: }
468:
469: static
470: reunget(c)
471: {
472: --rein;
473: }
This archive runs on limited infrastructure. Preserving old code on modern bandwidth. Automated agents are requested to crawl responsibly.