![[BACK]](/cvsweb/icons/back.gif){kind=icon}
Return to walker.c CVS log ![[TXT]](/cvsweb/icons/text.gif){kind=icon}
![[DIR]](/cvsweb/icons/dir.gif){kind=icon}
Up to [Research Unix] / researchv10no / cmd / twig / examples|
Return to walker.c CVS log | Up to [Research Unix] / researchv10no / cmd / twig / examples |
1.1 root 1:
2: # line 1 "prefix.mt"
3:
4: #include <stdio.h>
5: #include <ctype.h>
6: typedef struct node * NODEPTR;
7: #define COST int
8: #define INFINITY 1000000
9: #define DEFAULT_COST 0
10: #define COSTLESS(x,y) ((x)<(y))
11:
12: NODEPTR Root;
13: struct node {
14: char op; /* '\0' if node is a leaf */
15: NODEPTR left, right;
16: char id;
17: int mark;
18: };
19:
20: # line 1 "/usr/tjiang/twig/walker.c1"
21: /*
22: * The machine is laid out as a sequence of integers in the walker.
23: * The form described above is only used inside the preprocessor.
24: * Each machine state is one of the following sequence:
25: *
26: * TABLE <value_1><index_1>...<value_n><index_n> -1 [FAIL <fail_index>] -1
27: * or
28: * TABLE2 <value_1><index_1>...<value_n><index_n> -1 [FAIL <fail_index>] -1
29: * or
30: * ACCEPT <accept table index> -1
31: *
32: * The accept table is in the form:
33: *
34: * <tree index_1> ...<tree_index_m> -1
35: *
36: */
37: /* Keutzer - all "short int"'s have been changed to "short" for
38: portability to UTS. */
39: #include "symbols.h"
40: /* Keutzer 1/88- _mtG now uses varargs for portability to SUN4 etc.*/
41: #include <varargs.h>
42:
43: #ifndef FILE
44: #include <stdio.h>
45: #endif
46: #include <assert.h>
47:
48: /* These constants must be the same as the ones in machine.c */
49: #define FASTLIM 0
50: #define TABLE 1
51: #define FAIL 2
52: #define ACCEPT 3
53: #define TABLE2 4
54: #define EOT -1
55:
56: /* special machine state */
57: #define HANG -1
58:
59: /* used by the evaluator to interpret path table */
60: #define eSTOP 0
61: #define ePOP -1
62: #define eEVAL -2
63: #define eNEXT -3
64: #define ePUSH -4
65:
66: /* Tags that indicate the type of a value */
67: #define M_BRANCH 010000
68: #define M_NODE 0
69: #define M_LABEL 01000
70: #define MAX_NODE_VALUE 00777
71: #define MTAG_SHIFT 9
72: #define M_DETAG(x) ((x)&~(M_BRANCH|M_LABEL|M_NODE))
73:
74: /* predicates to tell whether a value x is of type NODE, BRANCH, or LABEL */
75: #define MI_NODE(x) (((x)&(M_BRANCH|M_LABEL))==0)
76: #define MI_DEFINED(x) ((x)!=-1)
77: #define MI_LABEL(x) (((x)&M_LABEL)!=0)
78: #define MI_BRANCH(x) (((x)&M_BRANCH)!=0)
79:
80: /* build a tagged value */
81: #define MV_NODE(x) (x)
82: #define MV_BRANCH(x) ((x)|M_BRANCH)
83: #define MV_LABEL(x) ((x)|M_LABEL)
84:
85: /* limits */
86: /*
87: * The depth of a pattern must be 7 or less. Otherwise the type of he
88: * partial mask in skeleton must be changed
89: */
90: #define MAXDEPTH 7
91:
92: /* modes */
93: #define xTOPDOWN 3
94: #define xABORT 2
95: #define xREWRITE 1
96: #define xDEFER 0
97:
98: /* macros */
99: #define tDO(m) _do((m)->skel, (m), 1)
100: #define REWRITE return(_m->cost = cost, xREWRITE)
101: #define TOPDOWN return(_m->cost = cost, xTOPDOWN)
102: #define ABORT return(xABORT)
103:
104: /*
105: * REORDER macro allows a knowledgeable user to change the order
106: * of evaluation of the leaves.
107: */
108: #ifndef REORDER
109: #define REORDER(list) _evalleaves(list)
110: #endif
111: #define EVAL REORDER(_ll)
112:
113: #define mpush(s,m) (m)->next = s, s = m
114:
115: /* skeleton structure */
116: typedef struct skeleton skeleton;
117: typedef struct __match __match;
118: typedef struct __partial __partial;
119: typedef struct __hshcls __hshcls; /* a hashed closure entry */
120: typedef int labelset; /* a bit vector of labels */
121:
122: struct __partial {
123: unsigned char treeno;
124: char bits;
125: };
126:
127: struct __hshcls {
128: __hshcls *next;
129: labelset labels;
130: int treecnt; /* number of partial matches */
131: __partial partial[MAXTREES];
132: };
133:
134: struct skeleton {
135: skeleton *sibling;
136: skeleton *leftchild; /* leftmost child */
137: skeleton *rightchild; /* rightmost child */
138: NODEPTR root;
139: NODEPTR parent; /* our parent */
140: int nson;
141: int treecnt;
142: __match *succ[MAXLABELS];
143: __partial *partial;
144: __match *winner;
145: COST mincost;
146: };
147:
148: struct __match {
149: __match **lleaves; /* labelled leaves */
150: skeleton *skel; /* back pointer to associated skeleton node */
151: COST cost;
152: short tree;
153: short mode;
154: };
155:
156: struct freeb {
157: struct freeb *next;
158: };
159:
160: struct _mem {
161: struct _mem *next;
162: int size; /* size of individual elements in bytes */
163: int blkf; /* blocking factor */
164: int bsize; /* block size */
165: char *block; /* block */
166: int cnt; /* count of free elem in block */
167: char *freelist; /* free list */
168: int totelem; /* total number elements we have */
169: int freecnt; /* number of times mem_free was called */
170: };
171:
172: /* turn this flag on if your machine has a fast byte string zero operation */
173: /*#define BZERO 1*/
174: int mtDebug = 0;
175: int treedebug = 0;
176: extern int _machstep();
177: extern short mtStart;
178: extern short mtTable[], mtAccept[], mtMap[], mtPaths[], mtPathStart[];
179: #ifdef LINE_XREF
180: extern short mtLine[];
181: #endif
182:
183: #ifndef MPBSIZE
184: #define MPBSIZE 8000
185: #endif
186:
187: #ifdef ADDCOST
188: #define DEFAULT_COST sumleaves(_ll)
189: COST sumleaves(list) __match **list;
190: {COST cost;
191: cost=ZEROCOST;
192: for(; *list; list++)
193: {ADDCOST((cost),(*list)->cost);
194: }
195: return cost;
196: }
197: #endif
198:
199: extern NODEPTR mtGetNodes(), mtAction();
200: extern skeleton *_allocskel();
201: extern __match *_allocmatch();
202: extern __partial *_allocpartial();
203:
204: __match *_mpblock[MPBSIZE], **_mpbtop;
205:
206: __match **
207: _getleaves (mp, skp)
208: register __match *mp; register skeleton *skp;
209: {
210: skeleton *stack[MAXDEPTH];
211: skeleton **stp = stack;
212: register short *sip = &mtPaths[mtPathStart[mp->tree]];
213: register __match **mmp = _mpbtop;
214: __match **mmp2 = mmp;
215: if((_mpbtop += *sip++ + 1) > &_mpblock[MPBSIZE]) {
216: printf("Tree too large: make MPBSIZE larger.\n\
217: (i.e. cc -c -DMPBSIZE=%d walker.c)\n",MPBSIZE*2);
218: assert(0);
219: }
220:
221: for(;;)
222: switch(*sip++) {
223: case ePUSH:
224: *stp++ = skp;
225: skp = skp->leftchild;
226: break;
227:
228: case eNEXT:
229: skp = skp->sibling;
230: break;
231:
232: case eEVAL:
233: if ((mp = skp->succ[M_DETAG(*sip++)])==NULL) abort();
234: *mmp++ = mp;
235: break;
236:
237: case ePOP:
238: skp = *--stp;
239: break;
240:
241: case eSTOP:
242: *mmp = NULL;
243: return (mmp2);
244: }
245: }
246:
247: _evalleaves (mpp)
248: register __match **mpp;
249: {
250: for (; *mpp!=NULL; mpp++) {
251: register __match *mp = *mpp;
252: _do (mp->skel, mp, 1);
253: }
254: }
255:
256:
257: _do(sp, winner, evalall)
258: skeleton *sp; register __match *winner; int evalall;
259: {
260: register __match **mpp;
261: register skeleton *skel = winner->skel;
262: if(winner==NULL) {
263: _nowin(sp);
264: return;
265: }
266: if(winner->mode==xDEFER || (evalall && winner->mode!=xTOPDOWN))
267: REORDER(winner->lleaves);
268: mtSetNodes (skel->parent, skel->nson,
269: skel->root=mtAction (winner->tree, winner->lleaves, sp));
270: }
271:
272: skeleton *
273: _walk(sp, ostate)
274: register skeleton *sp;
275: int ostate;
276: {
277: int state, nstate, nson;
278: register __partial *pp;
279: register __match *mp, *mp2;
280: register skeleton *nsp, *lastchild = NULL;
281: NODEPTR son, root;
282:
283: root = sp->root;
284: nson = 1; sp->mincost = INFINITY;
285: state = _machstep (ostate, root, mtValue(root));
286:
287: while((son = mtGetNodes(root, nson))!=NULL) {
288: nstate = _machstep (state, NULL, MV_BRANCH(nson));
289: nsp = _allocskel();
290: nsp->root = son;
291: nsp->parent = root;
292: nsp->nson = nson;
293: _walk(nsp, nstate);
294: if(COSTLESS(nsp->mincost,INFINITY)) {
295: assert (nsp->winner->mode==xREWRITE);
296: _do(nsp, nsp->winner, 0);
297: _freeskel(nsp);
298: continue;
299: }
300: _merge (sp, nsp);
301: if (lastchild==NULL) sp->leftchild = nsp;
302: else lastchild->sibling = nsp;
303: lastchild = nsp;
304: nson++;
305: }
306:
307: for (pp = sp->partial; pp < &sp->partial[sp->treecnt]; pp++)
308: if (pp->bits&01==1) {
309: mp = _allocmatch();
310: mp->tree = pp->treeno;
311: _addmatches (ostate, sp, mp);
312: }
313: if(son==NULL && nson==1)
314: _closure (state, ostate, sp);
315:
316: sp->rightchild = lastchild;
317: if (root==NULL) {
318: COST c; __match *win; int i; nsp = sp->leftchild;
319: c = INFINITY;
320: win = NULL;
321: for (i = 0; i < MAXLABELS; i++) {
322: mp = nsp->succ[i];
323: if (mp!=NULL && COSTLESS (mp->cost, c))
324: { c = mp->cost; win = mp; }
325: }
326: _do (nsp, win, 0);
327: }
328: return(sp);
329: }
330:
331: /*
332: * Convert the start state which has a large branching factor into
333: * a index table. This must be called before the matcher is used.
334: */
335: static short _nodetab[MAXNDVAL], _labeltab[MAXLABELS];
336: _matchinit()
337: {
338: short *sp;
339: /* Keutzer - this syntax doesn't work on UTS
340: struct pair { short val, where } *pp;
341: */
342: struct pair { short val; short where; } *pp;
343: for (sp=_nodetab; sp < &_nodetab[MAXNDVAL]; sp++) *sp = HANG;
344: for (sp=_labeltab; sp < &_labeltab[MAXLABELS]; sp++) *sp = HANG;
345: sp = &mtTable[mtStart];
346: assert (*sp==TABLE);
347: for (pp = (struct pair *) ++sp; pp->val!=EOF; pp++) {
348: if (MI_NODE(pp->val))
349: _nodetab[M_DETAG(pp->val)] = pp->where;
350: else if (MI_LABEL(pp->val))
351: _labeltab[M_DETAG(pp->val)] = pp->where;
352: }
353: }
354:
355: int
356: _machstep(state, root, input)
357: short state, input;
358: NODEPTR root;
359: {
360: register short *stp = &mtTable[state];
361: int start = 0;
362: if (state==HANG)
363: return (input==(MV_BRANCH(1)) ? mtStart : HANG);
364: rescan:
365: if (stp==&mtTable[mtStart]) {
366: if (MI_NODE(input)) return(_nodetab[M_DETAG(input)]);
367: if (MI_LABEL(input)) return(_labeltab[M_DETAG(input)]);
368: }
369:
370: for(;;) {
371: if(*stp==ACCEPT) stp += 2;
372:
373: if(*stp==TABLE) {
374: stp++;
375: while(*stp!=EOT) {
376: if(input==*stp) {
377: return(*++stp);
378: }
379: stp += 2;
380: }
381: stp++;
382: }
383: if(*stp!=FAIL) {
384: if (start) return (HANG);
385: else { stp = &mtTable[mtStart]; start = 1; goto rescan;}
386: } else {
387: stp++;
388: stp = &mtTable[*stp];
389: goto rescan;
390: }
391: }
392: }
393:
394: _addmatches(ostate, sp, np)
395: int ostate;
396: register skeleton *sp;
397: register __match *np;
398: {
399: int label;
400: int state;
401: register __match *mp;
402:
403: label = mtMap[np->tree];
404:
405: /*
406: * this is a very poor substitute for good design of the DFA.
407: * What we need is a special case that allows any label to be accepted
408: * by the start state but we don't want the start state to recognize
409: * them after a failure.
410: */
411: state = _machstep(ostate, NULL, MV_LABEL(label));
412: if (ostate!=mtStart && state==HANG) {
413: _freematch(np);
414: return;
415: }
416:
417: np->lleaves = _getleaves (np, sp);
418: np->skel = sp;
419: if((np->mode = mtEvalCost(np, np->lleaves, sp))==xABORT)
420: {
421: _freematch(np);
422: return;
423: }
424:
425: /*
426: if(np->mode==xREWRITE && COSTLESS(np->cost, sp->mincost)) {
427: sp->mincost = np->cost;
428: sp->winner = np;
429: }
430: */
431: if ((mp = sp->succ[label])!=NULL) {
432: if (!COSTLESS (np->cost, mp->cost))
433: { _freematch(np); return; }
434: else _freematch(mp);
435: }
436: if(COSTLESS(np->cost,sp->mincost)) {
437: if(np->mode==xREWRITE) {
438: sp->mincost = np->cost; sp->winner = np; }
439: else { sp->mincost = INFINITY; sp->winner = NULL; }
440: }
441: sp->succ[label] = np;
442: _closure(state, ostate, sp);
443: }
444:
445: _closure(state, ostate, skp)
446: int state, ostate;
447: skeleton *skp;
448: {
449: register struct ap { short tree, depth; } *ap;
450: short *sp = &mtTable[state];
451: register __match *mp;
452:
453: if(state==HANG || *sp!=ACCEPT) return(NULL);
454:
455: for(ap = (struct ap *) &mtAccept[*++sp]; ap->tree!=-1; ap++)
456: if (ap->depth==0) {
457: mp = _allocmatch();
458: mp->tree = ap->tree;
459: _addmatches (ostate, skp, mp);
460: } else {
461: register __partial *pp, *lim = &skp->partial[skp->treecnt];
462: for(pp=skp->partial; pp < lim; pp++)
463: if(pp->treeno==ap->tree)
464: break;
465: if(pp==lim) {
466: skp->treecnt++;
467: pp->treeno = ap->tree;
468: pp->bits = (1<<(ap->depth));
469: } else pp->bits |= (1<<(ap->depth));
470: }
471: }
472:
473: _merge (old, new)
474: skeleton *old, *new;
475: {
476: register __partial *op = old->partial, *np = new->partial;
477: int nson = new->nson;
478: register __partial *lim = np + new->treecnt;
479: if (nson==1) {
480: old->treecnt = new->treecnt;
481: for(; np < lim; op++, np++) {
482: op->treeno = np->treeno;
483: op->bits = np->bits/2;
484: }
485: } else {
486: __partial *newer = _allocpartial();
487: register __partial *newerp = newer;
488: register int cnt;
489: lim = op+old->treecnt;
490: for(cnt=new->treecnt; cnt-- ; np++) {
491: for(op = old->partial; op < lim; op++)
492: if (op->treeno == np->treeno) {
493: newerp->treeno = op->treeno;
494: newerp++->bits = op->bits & (np->bits/2);
495: break;
496: }
497: }
498: _freepartial(old->partial);
499: old->partial = newer;
500: old->treecnt = newerp-newer;
501: }
502: }
503:
504: /* Save and Allocate Matches */
505: #define BLKF 100
506: __match *freep = NULL;
507: static int _count = 0;
508: static __match *_blockp = NULL;
509: #ifdef CHECKMEM
510: int x_matches, f_matches;
511: #endif
512:
513: __match *
514: _allocmatch()
515: {
516: __match *mp;
517:
518: if(freep!=NULL) {
519: mp = freep;
520: freep = ((__match *)((struct freeb *) freep)->next);
521: #ifdef CHECKMEM
522: f_matches--;
523: #endif
524: } else {
525: if(_count==0) {
526: _blockp = (__match *) malloc (BLKF*sizeof (__match));
527: _count = BLKF;
528: #ifdef CHECKMEM
529: x_matches += BLKF;
530: #endif
531: }
532: mp = _blockp++;
533: _count--;
534: }
535: return(mp);
536: }
537:
538: _freematch(mp)
539: __match *mp;
540: {
541: ((struct freeb *) mp)->next = (struct freeb *) freep;
542: freep = mp;
543: #ifdef CHECKMEM
544: f_matches++;
545: #endif
546: }
547:
548: static __partial *pfreep = NULL;
549: static int pcount = 0;
550: static __partial *pblock = NULL;
551: #ifdef CHECKMEM
552: static int x_partials, f_partials;
553: #endif
554:
555: __partial *
556: _allocpartial()
557: {
558: __partial *pp;
559: if (pfreep!=NULL) {
560: pp = pfreep;
561: pfreep = *(__partial **) pp;
562: #ifdef CHECKMEM
563: f_partials--;
564: #endif
565: } else {
566: if (pcount==0) {
567: pblock=(__partial *)malloc(BLKF*MAXTREES*sizeof(__partial));
568: pcount = BLKF;
569: #ifdef CHECKMEM
570: x_partials += BLKF;
571: #endif
572: }
573: pp = pblock;
574: pblock += MAXTREES;
575: pcount--;
576: }
577: return(pp);
578: }
579:
580: _freepartial(pp)
581: __partial *pp;
582: {
583: * (__partial **)pp = pfreep;
584: pfreep = pp;
585: #ifdef CHECKMEM
586: f_partials++;
587: #endif
588: }
589:
590:
591: /* storage management */
592: static skeleton *sfreep = NULL;
593: static int scount = 0;
594: static skeleton * sblock = NULL;
595:
596: skeleton *
597: _allocskel()
598: {
599: skeleton *sp;
600: int i;
601: if(sfreep!=NULL) {
602: sp = sfreep;
603: sfreep = sp->sibling;
604: } else {
605: if(scount==0) {
606: sblock = (skeleton *) malloc (BLKF * sizeof (skeleton));
607: scount = BLKF;
608: }
609: sp = sblock++;
610: scount--;
611: }
612: sp->sibling = NULL; sp->leftchild = NULL;
613: for (i=0; i < MAXLABELS; sp->succ[i++] = NULL);
614: sp->treecnt = 0;
615: sp->partial = _allocpartial();
616: return(sp);
617: }
618:
619: _freeskel(sp)
620: skeleton *sp;
621: {
622: int i;
623: __match *mp;
624: if(sp==NULL) return;
625: _freeskel (sp->leftchild);
626: _freeskel (sp->sibling);
627: _freepartial (sp->partial);
628: for (i=0; i < MAXLABELS; i++)
629: if ((mp = sp->succ[i])!=NULL) _freematch (mp);
630: sp->sibling = sfreep;
631: sfreep = sp;
632: }
633:
634: _match()
635: {
636: skeleton *sp;
637: sp = _allocskel();
638: sp->root = NULL;
639: _mpbtop = _mpblock;
640: _freeskel(_walk(sp, HANG));
641: #ifdef CHECKMEM
642: if(f_matches+_count!=x_matches) {
643: printf(";#m %d %d %d\n", f_matches, _count, x_matches);
644: assert(0);
645: }
646: if(f_partials+pcount!=x_partials) {
647: printf(";#p %d %d %d\n", f_partials, pcount, x_partials);
648: assert(0);
649: }
650: #endif
651: }
652:
653: /* Keutzer 1/88- _mtG now uses varargs for portability to SUN4 etc.*/
654: NODEPTR _mtG(va_alist)
655: va_dcl
656: {
657: NODEPTR root;
658: int i=0;
659: va_list p_var;
660: va_start(p_var);
661: root = va_arg(p_var,NODEPTR);
662: while( (i = va_arg(p_var,int)) != -1){
663: root = mtGetNodes(root, i);
664: }
665: va_end(p_var);
666: return(root);
667: }
668:
669: /* diagnostic routines */
670:
671: markIfNoMatch(skp,mark) skeleton *skp; int mark;
672: {skeleton *child; int i; int found=0;
673: for(i=0; i<MAXLABELS; i++)
674: if (skp->succ[i]) found=1;
675: if (!found) skp->root->mark=mark;
676: for(child=skp->leftchild; child; child=child->sibling)
677: markIfNoMatch(child,mark);
678: }
679:
680: _nowin(skp) skeleton *skp;
681: {
682: markIfNoMatch(skp,1);
683: printf("# No match was found for the nodes printed in lowercase\n");
684: printTree(skp->root);
685: markIfNoMatch(skp,0);
686: }
687: short int mtTable[] = {
688: 3,0,-1,3,3,-1,1,01000,3,-1
689: ,-1,3,6,-1,1,01000,11,-1,-1,1
690: ,010001,6,010002,14,-1,-1,1,01,0,00
691: ,19,-1,-1};
692: short int mtAccept[] = {
693: 0,0,-1,1,1,-1,1,1,-1};
694: short int mtStart = 26;
695: short int mtMap[] = {
696: 00,00};
697: short int mtPaths[] = {
698: 2,-4,-2,01000,-3,-2,01000,-1,0,0
699: ,0 };
700: short int mtPathStart[] = {
701: 9,0};
702: NODEPTR
703: mtAction (_t, _ll, _s)
704: int _t; __match **_ll; skeleton *_s;
705: { NODEPTR root = _s->root;
706: switch (_t) {
707: case 0:{
708:
709: # line 24 "prefix.mt"
710: putchar(root->id); } break;
711: case 1:{
712:
713: # line 28 "prefix.mt"
714:
715: putchar(root->op);
716: tDO(_ll[(1)-1]); tDO(_ll[(2)-1]);
717: } break;
718: } return(_s->root);}
719: mtEvalCost(_m, _ll, _s)
720: __match **_ll; __match *_m; skeleton *_s;
721: { NODEPTR root = _s->root;
722: COST cost; cost = DEFAULT_COST;
723: switch(_m->tree) {
724: case 1:{
725:
726: # line 27 "prefix.mt"
727: TOPDOWN; } break;
728: }
729: _m->cost = cost; return(xDEFER);}
730:
731: # line 33 "prefix.mt"
732:
733:
734: mtValue(root)
735: NODEPTR root;
736: {
737: if(root==NULL)
738: return(0);
739: if(root->op==0)
740: return(nIdent);
741: else
742: return(nOp);
743: }
744:
745: NODEPTR
746: mtGetNodes(r,n)
747: NODEPTR r;
748: int n;
749: {
750: if(r==NULL)
751: if(n==1)
752: return(Root);
753: else
754: return(NULL);
755: if(n==1)
756: return(r->left);
757: else if(n==2)
758: return(r->right);
759: else return(NULL);
760: }
761:
762: mtSetNodes(r,n,c)
763: NODEPTR r,c;
764: int n;
765: {
766: if(r==NULL && n==1) {
767: Root = c;
768: return;
769: }
770: if(n==1)
771: r->left = c;
772: else if(n==2)
773: r->right = c;
774: }
775:
776: syntax_error()
777: {
778: printf("syntax error\n");
779: exit(1);
780: }
781:
782: /* allocated a node */
783: NODEPTR
784: getnode(op,id)
785: char op,id;
786: {
787: NODEPTR n;
788: n = (NODEPTR) malloc(sizeof(struct node));
789: n->op = op;
790: n->left = n->right = NULL;
791: n->id = id;
792: return(n);
793: }
794:
795: NODEPTR
796: gettree()
797: {
798: char c;
799: NODEPTR n = NULL;
800:
801: c = getchar();
802: if(c==EOF)
803: syntax_error();
804:
805: n = getnode(0,0);
806:
807: /* build node for left operand */
808: if(c=='(')
809: n->left = gettree();
810: else
811: n->left = getnode(0,c);
812:
813: c = getchar();
814: if(strchr("+-*/",c)==NULL)
815: syntax_error();
816: n->op = c;
817:
818: c = getchar();
819: /* build node for right operand */
820: if(c=='(')
821: n->right = gettree();
822: else
823: n->right = getnode(0,c);
824:
825: c = getchar();
826: if(c!=')')
827: syntax_error();
828:
829: return(n);
830: }
831:
832: main()
833: {
834: char c;
835: _matchinit(); /* initialize the matcher */
836:
837: /* get the initial ( */
838: c = getchar();
839: if(c!='(')
840: syntax_error();
841:
842: Root = gettree();
843: _match();
844: putchar('\n');
845: }
846: printTree(x)
847: {}
848:
849:
This archive runs on limited infrastructure. Preserving old code on modern bandwidth. Automated agents are requested to crawl responsibly.