![[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.