![[BACK]](/cvsweb/icons/back.gif){kind=icon}
Return to regcomp.c CVS log ![[TXT]](/cvsweb/icons/text.gif){kind=icon}
![[DIR]](/cvsweb/icons/dir.gif){kind=icon}
Up to [Research Unix] / researchv8dc / libc / gen|
Return to regcomp.c CVS log | Up to [Research Unix] / researchv8dc / libc / gen |
1.1 root 1: #include "regprog.h"
2:
3: /*
4: * Parser Information
5: */
6: typedef struct Node{
7: Inst *first;
8: Inst *last;
9: }Node;
10: #define NSTACK 20
11: static Node andstack[NSTACK];
12: static Node *andp;
13: static int atorstack[NSTACK];
14: static int *atorp;
15: static int cursubid; /* id of current subexpression */
16: static int subidstack[NSTACK]; /* parallel to atorstack */
17: static int *subidp;
18: static int lastwasand; /* Last token was operand */
19: static int nbra;
20: static char *exprp; /* pointer to next character in source expression */
21: static int nclass;
22: static Class *classp;
23: static Inst *freep;
24: static int errors;
25:
26: /* predeclared crap */
27: static void operator();
28: static void pushand();
29: static void pushator();
30: static void evaluntil();
31: static void bldcclass();
32:
33: static void
34: rcerror(s)
35: char *s;
36: {
37: errors++;
38: regerror(s);
39: }
40:
41: static Inst *
42: newinst(t)
43: int t;
44: {
45: freep->type=t;
46: freep->left=0;
47: freep->right=0;
48: return freep++;
49: }
50:
51: static void
52: operand(t)
53: int t;
54: {
55: register Inst *i;
56: if(lastwasand)
57: operator(CAT); /* catenate is implicit */
58: i=newinst(t);
59: if(t==CCLASS) /* ugh */
60: i->right=(Inst *)&(classp[nclass-1]); /* UGH! */
61: pushand(i, i);
62: lastwasand=TRUE;
63: }
64:
65: static void
66: operator(t)
67: int t;
68: {
69: if(t==RBRA && --nbra<0)
70: rcerror("unmatched right paren");
71: if(t==LBRA) {
72: if (++cursubid >= NSUBEXP)
73: rcerror ("too many subexpressions");
74: nbra++;
75: if (lastwasand)
76: operator(CAT);
77: } else
78: evaluntil(t);
79: if(t!=RBRA)
80: pushator(t);
81: lastwasand=FALSE;
82: if(t==STAR || t==QUEST || t==PLUS || t==RBRA)
83: lastwasand=TRUE; /* these look like operands */
84: }
85:
86: static void
87: regerr2(s, c)
88: char *s;
89: {
90: char buf[100];
91: char *cp = buf;
92: while(*s)
93: *cp++ = *s++;
94: *cp++ = c;
95: *cp = '\0';
96: rcerror(buf);
97: }
98:
99: static void
100: cant(s)
101: char *s;
102: {
103: char buf[100];
104: strcpy(buf, "can't happen: ");
105: strcat(buf, s);
106: rcerror(buf);
107: }
108:
109: static void
110: pushand(f, l)
111: Inst *f, *l;
112: {
113: if(andp >= &andstack[NSTACK])
114: cant("operand stack overflow");
115: andp->first=f;
116: andp->last=l;
117: andp++;
118: }
119:
120: static void
121: pushator(t)
122: int t;
123: {
124: if(atorp >= &atorstack[NSTACK])
125: cant("operator stack overflow");
126: *atorp++=t;
127: *subidp++=cursubid;
128: }
129:
130: static Node *
131: popand(op)
132: {
133: if(andp <= &andstack[0])
134: regerr2("missing operand for", op);
135: return --andp;
136: }
137:
138: static int
139: popator()
140: {
141: if(atorp <= &atorstack[0])
142: cant("operator stack underflow");
143: --subidp;
144: return *--atorp;
145: }
146:
147: static void
148: evaluntil(pri)
149: register pri;
150: {
151: register Node *op1, *op2;
152: register Inst *inst1, *inst2;
153:
154: while(pri==RBRA || atorp[-1]>=pri){
155: switch(popator()){
156: default:
157: rcerror("unknown operator in evaluntil");
158: break;
159: case LBRA: /* must have been RBRA */
160: op1=popand(0);
161: inst2=newinst(RBRA);
162: inst2->subid = *subidp;
163: op1->last->next = inst2;
164: inst1=newinst(LBRA);
165: inst1->subid = *subidp;
166: inst1->next=op1->first;
167: pushand(inst1, inst2);
168: return;
169: case OR:
170: op2=popand('|');
171: op1=popand('|');
172: inst2=newinst(NOP);
173: op2->last->next=inst2;
174: op1->last->next=inst2;
175: inst1=newinst(OR);
176: inst1->right=op1->first;
177: inst1->left=op2->first;
178: pushand(inst1, inst2);
179: break;
180: case CAT:
181: op2=popand(0);
182: op1=popand(0);
183: op1->last->next=op2->first;
184: pushand(op1->first, op2->last);
185: break;
186: case STAR:
187: op2=popand('*');
188: inst1=newinst(OR);
189: op2->last->next=inst1;
190: inst1->right=op2->first;
191: pushand(inst1, inst1);
192: break;
193: case PLUS:
194: op2=popand('+');
195: inst1=newinst(OR);
196: op2->last->next=inst1;
197: inst1->right=op2->first;
198: pushand(op2->first, inst1);
199: break;
200: case QUEST:
201: op2=popand('?');
202: inst1=newinst(OR);
203: inst2=newinst(NOP);
204: inst1->left=inst2;
205: inst1->right=op2->first;
206: op2->last->next=inst2;
207: pushand(inst1, inst2);
208: break;
209: }
210: }
211: }
212:
213: static void
214: optimize(pp)
215: Prog *pp;
216: {
217: register Inst *inst, *target;
218:
219: for(inst=pp->firstinst; inst->type!=END; inst++){
220: target=inst->next;
221: while(target->type == NOP)
222: target=target->next;
223: inst->next=target;
224: }
225: }
226:
227: #ifdef DEBUG
228: static void
229: dumpstack(){
230: Node *stk;
231: int *ip;
232:
233: printf("operators\n");
234: for(ip=atorstack; ip<atorp; ip++)
235: printf("0%o\n", *ip);
236: printf("operands\n");
237: for(stk=andstack; stk<andp; stk++)
238: printf("0%o\t0%o\n", stk->first->type, stk->last->type);
239: }
240:
241: static void
242: dump(pp)
243: Prog *pp;
244: {
245: Inst *l;
246:
247: l=pp->firstinst;
248: do{
249: printf("%d:\t0%o\t%d\t%d\n", l-pp->firstinst, l->type,
250: l->left-pp->firstinst, l->right-pp->firstinst);
251: }while(l++->type);
252: }
253: #endif
254:
255: static void
256: startlex(s)
257: char *s;
258: {
259: exprp=s;
260: nclass=0;
261: nbra=0;
262: }
263:
264: static Class *
265: newclass(){
266: register Class *p;
267: register n;
268:
269: if(nclass >= NCLASS)
270: regerr2("too many character classes; limit", NCLASS+'0');
271: p=&(classp[nclass++]);
272: for(n=0; n<16; n++)
273: p->map[n]=0;
274: return p;
275: }
276:
277: static int
278: lex(){
279: register c= *exprp++;
280:
281: switch(c){
282: case '\\':
283: if(*exprp)
284: c= *exprp++;
285: break;
286: case 0:
287: c=END;
288: --exprp; /* In case we come here again */
289: break;
290: case '*':
291: c=STAR;
292: break;
293: case '?':
294: c=QUEST;
295: break;
296: case '+':
297: c=PLUS;
298: break;
299: case '|':
300: c=OR;
301: break;
302: case '.':
303: c=ANY;
304: break;
305: case '(':
306: c=LBRA;
307: break;
308: case ')':
309: c=RBRA;
310: break;
311: case '^':
312: c=BOL;
313: break;
314: case '$':
315: c=EOL;
316: break;
317: case '[':
318: c=CCLASS;
319: bldcclass();
320: break;
321: }
322: return c;
323: }
324:
325: static int
326: nextc(){
327: if(exprp[0]==0 || (exprp[0]=='\\' && exprp[1]==0))
328: rcerror("malformed '[]'");
329: if(exprp[0]=='\\'){
330: exprp++;
331: return *exprp++|0200;
332: }
333: return *exprp++;
334: }
335:
336: static void
337: bldcclass(){
338: register c1, c2;
339: register Class *classp;
340: register negate=FALSE;
341:
342: classp=newclass();
343: /* we have already seen the '[' */
344: if(*exprp=='^'){
345: negate=TRUE;
346: exprp++;
347: }
348: while((c1=c2=nextc()) != ']'){
349: if(*exprp=='-'){
350: exprp++; /* eat '-' */
351: if((c2=nextc()) == ']')
352: rcerror("malformed '[]'");
353: }
354: for((c1&=0177), (c2&=0177); c1<=c2; c1++)
355: classp->map[c1/8] |= 1<<(c1&07);
356: }
357: if(negate)
358: for(c1=0; c1<16; c1++)
359: classp->map[c1]^=0377;
360: classp->map[0]&=376; /* exclude NUL */
361: }
362:
363: extern char *
364: regcomp(s)
365: char *s;
366: {
367: register token;
368: Prog *pp;
369:
370: /* get memory for the program */
371: pp = (Prog *)malloc(sizeof(Prog) + sizeof(Inst)*strlen(s));
372: if (pp == NULL) {
373: rcerror("out of memory");
374: return NULL;
375: }
376: freep = pp->firstinst;
377: classp = pp->class;
378: errors = 0;
379:
380: /* go compile the sucker */
381: startlex(s);
382: atorp=atorstack;
383: andp=andstack;
384: subidp=subidstack;
385: lastwasand=FALSE;
386: cursubid=0;
387:
388: /* Start with a low priority operator to prime parser */
389: pushator(START-1);
390: while((token=lex()) != END){
391: if((token&0300) == OPERATOR)
392: operator(token);
393: else
394: operand(token);
395: }
396:
397: /* Close with a low priority operator */
398: evaluntil(START);
399:
400: /* Force END */
401: operand(END);
402: evaluntil(START);
403: #ifdef DEBUG
404: dumpstack();
405: #endif
406: if(nbra)
407: rcerror("unmatched left paren");
408: --andp; /* points to first and only operand */
409: pp->startinst=andp->first;
410: #ifdef DEBUG
411: dump(pp);
412: #endif
413: optimize(pp);
414: #ifdef DEBUG
415: printf("start: %d\n", andp->first-pp->firstinst);
416: dump(pp);
417: #endif
418: if (errors) {
419: free(pp);
420: pp = NULL;
421: }
422: return (char *)pp;
423: }
This archive runs on limited infrastructure. Preserving old code on modern bandwidth. Automated agents are requested to crawl responsibly.