![[BACK]](/cvsweb/icons/back.gif){kind=icon}
Return to yyrecover.c CVS log ![[TXT]](/cvsweb/icons/text.gif){kind=icon}
![[DIR]](/cvsweb/icons/dir.gif){kind=icon}
Up to [CSRG BSD Unix] / 42BSD / ucb / pascal / src|
Return to yyrecover.c CVS log | Up to [CSRG BSD Unix] / 42BSD / ucb / pascal / src |
1.1 ! root 1: /* Copyright (c) 1979 Regents of the University of California */ ! 2: ! 3: static char sccsid[] = "@(#)yyrecover.c 1.3 2/5/83"; ! 4: ! 5: #include "whoami.h" ! 6: #include "0.h" ! 7: #include "yy.h" ! 8: ! 9: /* ! 10: * Very simplified version of Graham-Rhodes error recovery ! 11: * method for LALR parsers. Backward move is embodied in ! 12: * default reductions of the yacc parser until an error condition ! 13: * is reached. Forward move is over a small number of input tokens ! 14: * and cannot "condense". The basic corrections are: ! 15: * ! 16: * 1) Delete the input token. ! 17: * ! 18: * 2) Replace the current input with a legal input. ! 19: * ! 20: * 3) Insert a legal token. ! 21: * ! 22: * All corrections are weighted, considered only if they allow ! 23: * at least two shifts, and the cost of a correction increases if ! 24: * it allows shifting over only a part of the lookahead. ! 25: * ! 26: * Another error situation is that which occurs when an identifier "fails" ! 27: * a reduction because it is not the required "class". ! 28: * In this case, we also consider replacing this identifier, which has ! 29: * already been shifted over, with an identifier of the correct class. ! 30: * ! 31: * Another correction performed here is unique symbol insertion. ! 32: * If the current state admits only one input, and no other alternative ! 33: * correction presents itself, then that symbol will be inserted. ! 34: * There is a danger in this of looping, and it is handled ! 35: * by counting true shifts over input (see below). ! 36: * ! 37: * ! 38: * A final class of corrections, considered only when the error ! 39: * occurred immediately after a shift over a terminal, involves ! 40: * the three basic corrections above, but with the point of error ! 41: * considered to be before this terminal was shifted over, effectively ! 42: * "unreading" this terminal. This is a feeble attempt at elimination ! 43: * of the left-right bias and because "if" has a low weight and some ! 44: * statements are quite simple i.e. ! 45: * ! 46: * cse ch of ... ! 47: * ! 48: * we can get a small number of errors. The major deficiency of ! 49: * this is that we back up only one token, and that the forward ! 50: * move is over a small number of tokens, often not enough to really ! 51: * tell what the input should be, e.g. in ! 52: * ! 53: * a[i] > a[i - 1] ... ! 54: * ! 55: * In such cases a bad identifier (misspelled keyword) or omitted ! 56: * keyword will be change or inserted as "if" as it has the lowest cost. ! 57: * This is not terribly bad, as "if"s are most common. ! 58: * This also allows the correction of other errors. ! 59: * ! 60: * This recovery depends on the default reductions which delay ! 61: * noticing the error until the parse reaches a state where the ! 62: * relevant "alternatives" are visible. Note that it does not ! 63: * consider tokens which will cause reductions before being ! 64: * shifted over. This requires the grammar to be written in a ! 65: * certain way for the recovery to work correctly. ! 66: * In some sense, also, the recovery suffers because we have ! 67: * LALR(1) tables rather than LR(1) tables, e.g. in ! 68: * ! 69: * if rec.field < rec2,field2 then ! 70: */ ! 71: ! 72: /* ! 73: * Definitions of possible corrective actions ! 74: */ ! 75: #define CPANIC 0 ! 76: #define CDELETE 1 ! 77: #define CREPLACE 2 ! 78: #define CINSERT 3 ! 79: #define CUNIQUE 4 ! 80: #define CCHIDENT 5 ! 81: ! 82: /* ! 83: * Multiplicative cost factors for corrective actions. ! 84: * ! 85: * When an error occurs we take YCSIZ - 1 look-ahead tokens. ! 86: * If a correction being considered will shift over only part of ! 87: * that look-ahead, it is not completely discarded, but rather ! 88: * "weighted", its cost being multiplied by a weighting factor. ! 89: * For a correction to be considered its weighted cost must be less ! 90: * than CLIMIT. ! 91: * ! 92: * Non-weighted costs are considered: ! 93: * ! 94: * LOW <= 3 ! 95: * MEDIUM 4,5 ! 96: * HIGH >= 6 ! 97: * ! 98: * CURRENT WEIGHTING STRATEGY: Aug 20, 1977 ! 99: * ! 100: * For all kinds of corrections we demand shifts over two symbols. ! 101: * Corrections have high weight even after two symbol ! 102: * shifts because the costs for deleting and inserting symbols are actually ! 103: * quite low; we do not want to change weighty symbols ! 104: * on inconclusive evidence. ! 105: * ! 106: * The weights are the same after the third look ahead. ! 107: * This prevents later, unrelated errors from causing "funny" ! 108: * biases of the weights toward one type of correction. ! 109: * ! 110: * Current look ahead is 5 symbols. ! 111: */ ! 112: ! 113: /*** CLIMIT is defined in yy.h for yycosts ***/ ! 114: #define CPRLIMIT 50 ! 115: #define CCHIDCOST 3 ! 116: ! 117: char insmult[8] = {INFINITY, INFINITY, INFINITY, 15, 8, 6, 3, 1}; ! 118: char repmult[7] = {INFINITY, INFINITY, INFINITY, 8, 6, 3, 1}; ! 119: char delmult[6] = {INFINITY, INFINITY, INFINITY, 6, 3, 1}; ! 120: ! 121: #define NOCHAR -1 ! 122: ! 123: #define Eprintf if (errtrace) printf ! 124: #define Tprintf if (testtrace) printf ! 125: ! 126: /* ! 127: * Action arrays of the parser needed here ! 128: */ ! 129: int yyact[], yypact[], *yypv; ! 130: ! 131: /* ! 132: * Yytips is the tip of the stack when using ! 133: * the function loccor to check for local ! 134: * syntactic correctness. As we don't want ! 135: * to copy the whole parser stack, but want ! 136: * to simulate parser moves, we "split" ! 137: * the parser stack and keep the tip here. ! 138: */ ! 139: #define YYTIPSIZ 16 ! 140: int yytips[YYTIPSIZ], yytipct; ! 141: int yytipv[YYTIPSIZ]; ! 142: ! 143: /* ! 144: * The array YC saves the lookahead tokens for the ! 145: * forward moves. ! 146: * Yccnt is the number of tokens in the YC array. ! 147: */ ! 148: #define YCSIZ 6 ! 149: ! 150: int yCcnt; ! 151: struct yytok YC0[YCSIZ + 1]; ! 152: struct yytok *YC; ! 153: ! 154: /* ! 155: * YCps gives the top of stack at ! 156: * the point of error. ! 157: */ ! 158: ! 159: bool yyunique = 1; ! 160: ! 161: STATIC unsigned yyTshifts; ! 162: ! 163: /* ! 164: * Cact is the corrective action we have decided on ! 165: * so far, ccost its cost, and cchar the associated token. ! 166: * Cflag tells if the correction is over the previous input token. ! 167: */ ! 168: int cact, ccost, cchar, cflag; ! 169: ! 170: /* ! 171: * ACtok holds the token under ! 172: * consideration when examining ! 173: * the lookaheads in a state. ! 174: */ ! 175: struct yytok ACtok; ! 176: ! 177: #define acchar ACtok.Yychar ! 178: #define aclval ACtok.Yylval ! 179: ! 180: /* ! 181: * Make a correction to the current stack which has ! 182: * top of stack pointer Ps. ! 183: */ ! 184: yyrecover(Ps0, idfail) ! 185: int *Ps0, idfail; ! 186: { ! 187: register int c, i; ! 188: int yyrwant, yyrhave; ! 189: ! 190: #ifdef PI ! 191: Recovery = 1; ! 192: #endif ! 193: ! 194: YC = &YC0[1]; ! 195: #ifdef DEBUG ! 196: if (errtrace) { ! 197: setpfx('p'); ! 198: yerror("Point of error"); ! 199: printf("States %d %d ...", Ps0[0], Ps0[-1]); ! 200: if (idfail) ! 201: printf(" [Idfail]"); ! 202: #ifdef PXP ! 203: putchar('\n'); ! 204: #else ! 205: pchr('\n'); ! 206: #endif ! 207: printf("Input %s%s", tokname(&Y , 0) ! 208: , tokname(&Y , 1)); ! 209: } ! 210: ! 211: #endif ! 212: /* ! 213: * We first save the current input token ! 214: * and its associated semantic information. ! 215: */ ! 216: if (yychar < 0) ! 217: yychar = yylex(); ! 218: copy(&YC[0], &Y, sizeof Y); ! 219: ! 220: /* ! 221: * Set the default action and cost ! 222: */ ! 223: cact = CPANIC, ccost = CLIMIT, cflag = 0; ! 224: ! 225: /* ! 226: * Peek ahead ! 227: */ ! 228: for (yCcnt = 1; yCcnt < YCSIZ; yCcnt++) { ! 229: yychar = yylex(); ! 230: copy(&YC[yCcnt], &Y, sizeof YC[0]); ! 231: #ifdef DEBUG ! 232: Eprintf(" | %s%s", tokname(&YC[yCcnt] , 0 ) ! 233: , tokname(&YC[yCcnt] , 1 )); ! 234: #endif ! 235: } ! 236: #ifdef DEBUG ! 237: Eprintf("\n"); ! 238: #endif ! 239: ! 240: /* ! 241: * If we are here because a reduction failed, try ! 242: * correcting that. ! 243: */ ! 244: if (idfail) { ! 245: /* ! 246: * Save the particulars about ! 247: * the kind of identifier we want/have. ! 248: */ ! 249: yyrwant = yyidwant; ! 250: yyrhave = yyidhave; ! 251: #ifdef DEBUG ! 252: Tprintf(" Try Replace %s identifier with %s identifier cost=%d\n", ! 253: classes[yyidhave], classes[yyidwant], CCHIDCOST); ! 254: #endif ! 255: ! 256: /* ! 257: * Save the semantics of the ID on the ! 258: * stack, and null them out to free ! 259: * up the reduction in question. ! 260: */ ! 261: i = yypv[0]; ! 262: yypv[0] = nullsem(YID); ! 263: c = correct(NOCHAR, 0, CCHIDCOST, &repmult[2], Ps0, yypv); ! 264: yypv[0] = i; ! 265: #ifdef DEBUG ! 266: if (c < CPRLIMIT || fulltrace) ! 267: Eprintf("Cost %2d Replace %s identifier with %s identifier\n", c, classes[yyrhave], classes[yyrwant]); ! 268: #endif ! 269: if (c < ccost) ! 270: cact = CCHIDENT, ccost = c, cchar = YID; ! 271: } ! 272: ! 273: /* ! 274: * First try correcting the state we are in ! 275: */ ! 276: trystate(Ps0, yypv, 0, &insmult[1], &delmult[1], &repmult[1]); ! 277: ! 278: /* ! 279: * Now, if we just shifted over a terminal, try ! 280: * correcting it. ! 281: */ ! 282: if (OY.Yychar != -1 && OY.Yylval != nullsem(OY.Yychar)) { ! 283: YC--; ! 284: copy(&YC[0], &OY, sizeof YC[0]); ! 285: trystate(Ps0 - 1, yypv - 1, 1, insmult, delmult, repmult); ! 286: if (cflag == 0) ! 287: YC++; ! 288: else { ! 289: yypv--; ! 290: #ifdef PXP ! 291: yypw--; ! 292: #endif ! 293: Ps0--; ! 294: yCcnt++; ! 295: } ! 296: } ! 297: ! 298: /* ! 299: * Restoring the first look ahead into ! 300: * the scanner token allows the error message ! 301: * routine to print the error message with the text ! 302: * of the correct line. ! 303: */ ! 304: copy(&Y, &YC[0], sizeof Y); ! 305: ! 306: /* ! 307: * Unique symbol insertion. ! 308: * ! 309: * If there was no reasonable correction found, ! 310: * but only one input to the parser is acceptable ! 311: * we report that, and try it. ! 312: * ! 313: * Special precautions here to prevent looping. ! 314: * The number of true inputs shifted over at the point ! 315: * of the last unique insertion is recorded in the ! 316: * variable yyTshifts. If this is not less than ! 317: * the current number in yytshifts, we do not insert. ! 318: * Thus, after one unique insertion, no more unique ! 319: * insertions will be made until an input is shifted ! 320: * over. This guarantees termination. ! 321: */ ! 322: if (cact == CPANIC && !idfail) { ! 323: register int *ap; ! 324: ! 325: ap = &yyact[yypact[*Ps0 + 1]]; ! 326: if (*ap == -ERROR) ! 327: ap += 2; ! 328: if (ap[0] <= 0 && ap[2] > 0) { ! 329: cchar = -ap[0]; ! 330: if (cchar == YEOF) ! 331: yyexeof(); ! 332: if (cchar != ERROR && yyTshifts < yytshifts) { ! 333: cact = CUNIQUE; ! 334: #ifdef DEBUG ! 335: Eprintf("Unique symbol %s%s\n" ! 336: , charname(cchar , 0 ) ! 337: , charname(cchar , 1 )); ! 338: #endif ! 339: /* ! 340: * Note that the inserted symbol ! 341: * will not be counted as a true input ! 342: * (i.e. the "yytshifts--" below) ! 343: * so that a true shift will be needed ! 344: * to make yytshifts > yyTshifts. ! 345: */ ! 346: yyTshifts = yytshifts; ! 347: } ! 348: } ! 349: } ! 350: ! 351: /* ! 352: * Set up to perform the correction. ! 353: * Build a token appropriate for replacement ! 354: * or insertion in the yytok structure ACchar ! 355: * having the attributes of the input at the ! 356: * point of error. ! 357: */ ! 358: copy(&ACtok, &YC[0], sizeof ACtok); ! 359: acchar = cchar; ! 360: aclval = nullsem(acchar); ! 361: if (aclval != NIL) ! 362: recovered(); ! 363: switch (cact) { ! 364: /* ! 365: * Panic, just restore the ! 366: * lookahead and return. ! 367: */ ! 368: case CPANIC: ! 369: setpfx('E'); ! 370: if (idfail) { ! 371: copy(&Y, &OY, sizeof Y); ! 372: if (yyrhave == NIL) { ! 373: #ifdef PI ! 374: if (yybaduse(yypv[0], yyeline, ISUNDEF) == NIL) ! 375: #endif ! 376: yerror("Undefined identifier"); ! 377: } else { ! 378: yerror("Improper %s identifier", classes[yyrhave]); ! 379: #ifdef PI ! 380: yybaduse(yypv[0], yyeline, NIL); ! 381: #endif ! 382: } ! 383: /* ! 384: * Suppress message from panic routine ! 385: */ ! 386: yyshifts = 1; ! 387: } ! 388: i = 0; ! 389: /* Note that on one path we dont touch yyshifts ! */ ! 390: break; ! 391: /* ! 392: * Delete the input. ! 393: * Mark this as a shift over true input. ! 394: * Restore the lookahead starting at ! 395: * the second token. ! 396: */ ! 397: case CDELETE: ! 398: if (ccost != 0) ! 399: yerror("Deleted %s%s", tokname(&YC[0] , 0 ) ! 400: , tokname(&YC[0] , 1 )); ! 401: yytshifts++; ! 402: i = 1; ! 403: yyshifts = 0; ! 404: break; ! 405: /* ! 406: * Replace the input with a new token. ! 407: */ ! 408: case CREPLACE: ! 409: if (acchar == YEOF) ! 410: yyexeof(); ! 411: if (acchar == YEND) ! 412: aclval = NIL; ! 413: yerror("Replaced %s%s with a %s%s", ! 414: tokname(&YC[0] , 0 ), ! 415: tokname(&YC[0] , 1 ), ! 416: tokname(&ACtok , 0 ), ! 417: tokname(&ACtok , 1 )); ! 418: copy(&YC[0], &ACtok, sizeof YC[0]); ! 419: i = 0; ! 420: yyshifts = 0; ! 421: break; ! 422: /* ! 423: * Insert a token. ! 424: * Don't count this token as a true input shift. ! 425: * For inserted "end"s pas.y is responsible ! 426: * for the error message later so suppress it. ! 427: * Restore all the lookahead. ! 428: */ ! 429: case CINSERT: ! 430: if (acchar == YEOF) ! 431: yyexeof(); ! 432: if (acchar != YEND) ! 433: yerror("Inserted %s%s", ! 434: tokname(&ACtok , 0 ), ! 435: tokname(&ACtok , 1 )); ! 436: yytshifts--; ! 437: i = 0; ! 438: yyshifts = 0; ! 439: break; ! 440: /* ! 441: * Make a unique symbol correction. ! 442: * Like an insertion but a different message. ! 443: */ ! 444: case CUNIQUE: ! 445: setpfx('E'); ! 446: yerror("Expected %s%s", ! 447: tokname(&ACtok , 0 ), ! 448: tokname(&ACtok , 1 )); ! 449: yytshifts--; ! 450: i = 0; ! 451: if (ccost == 0 || yyunique) ! 452: yyshifts = 0; ! 453: else ! 454: yyshifts = -1; ! 455: break; ! 456: /* ! 457: * Change an identifier's type ! 458: * to make it work. ! 459: */ ! 460: case CCHIDENT: ! 461: copy(&Y, &OY, sizeof Y); ! 462: #ifdef PI ! 463: i = 1 << yyrwant; ! 464: #endif ! 465: if (yyrhave == NIL) { ! 466: yerror("Undefined %s", classes[yyrwant]); ! 467: #ifdef PI ! 468: i |= ISUNDEF; ! 469: #endif ! 470: } else ! 471: yerror("Replaced %s id with a %s id", classes[yyrhave], classes[yyrwant]); ! 472: #ifdef PI ! 473: yybaduse(yypv[0], yyeline, i); ! 474: #endif ! 475: yypv[0] = nullsem(YID); ! 476: i = 0; ! 477: yyshifts = 0; ! 478: break; ! 479: } ! 480: ! 481: /* ! 482: * Restore the desired portion of the lookahead, ! 483: * and possibly the inserted or unique inserted token. ! 484: */ ! 485: for (yCcnt--; yCcnt >= i; yCcnt--) ! 486: unyylex(&YC[yCcnt]); ! 487: if (cact == CINSERT || cact == CUNIQUE) ! 488: unyylex(&ACtok); ! 489: ! 490: /* ! 491: * Put the scanner back in sync. ! 492: */ ! 493: yychar = yylex(); ! 494: ! 495: /* ! 496: * We succeeded if we didn't "panic". ! 497: */ ! 498: Recovery = 0; ! 499: Ps = Ps0; ! 500: return (cact != CPANIC); ! 501: } ! 502: ! 503: yyexeof() ! 504: { ! 505: ! 506: yerror("End-of-file expected - QUIT"); ! 507: pexit(ERRS); ! 508: } ! 509: ! 510: yyunexeof() ! 511: { ! 512: ! 513: yerror("Unexpected end-of-file - QUIT"); ! 514: pexit(ERRS); ! 515: } ! 516: ! 517: /* ! 518: * Try corrections with the state at Ps0. ! 519: * Flag is 0 if this is the top of stack state, ! 520: * 1 if it is the state below. ! 521: */ ! 522: trystate(Ps0, Pv0, flag, insmult, delmult, repmult) ! 523: int *Ps0, *Pv0, flag; ! 524: char *insmult, *delmult, *repmult; ! 525: { ! 526: /* ! 527: * C is a working cost, ap a pointer into the action ! 528: * table for looking at feasible alternatives. ! 529: */ ! 530: register int c, *ap; ! 531: int i, *actions; ! 532: ! 533: #ifdef DEBUG ! 534: Eprintf("Trying state %d\n", *Ps0); ! 535: #endif ! 536: /* ! 537: * Try deletion. ! 538: * Correct returns a cost. ! 539: */ ! 540: #ifdef DEBUG ! 541: Tprintf(" Try Delete %s%s cost=%d\n", ! 542: tokname(&YC[0] , 0 ), ! 543: tokname(&YC[0] , 1 ), ! 544: delcost(YC[0].Yychar)); ! 545: #endif ! 546: c = delcost(YC[0].Yychar); ! 547: #ifndef DEBUG ! 548: if (c < ccost) { ! 549: #endif ! 550: c = correct(NOCHAR, 1, c, delmult, Ps0, Pv0); ! 551: #ifdef DEBUG ! 552: if (c < CPRLIMIT || fulltrace) ! 553: Eprintf("Cost %2d Delete %s%s\n", c, ! 554: tokname(&YC[0] , 0 ), ! 555: tokname(&YC[0] , 1 )); ! 556: #endif ! 557: if (c < ccost) ! 558: cact = CDELETE, ccost = c, cflag = flag; ! 559: #ifndef DEBUG ! 560: } ! 561: #endif ! 562: ! 563: /* ! 564: * Look at the inputs to this state ! 565: * which will cause parse action shift. ! 566: */ ! 567: aclval = NIL; ! 568: ap = &yyact[yypact[*Ps0 + 1]]; ! 569: ! 570: /* ! 571: * Skip action on error to ! 572: * detect true unique inputs. ! 573: * Error action is always first. ! 574: */ ! 575: if (*ap == -ERROR) ! 576: ap += 2; ! 577: ! 578: /* ! 579: * Loop through the test actions ! 580: * for this state. ! 581: */ ! 582: for (actions = ap; *ap <= 0; ap += 2) { ! 583: /* ! 584: * Extract the token of this action ! 585: */ ! 586: acchar = -*ap; ! 587: ! 588: /* ! 589: * Try insertion ! 590: */ ! 591: #ifdef DEBUG ! 592: Tprintf(" Try Insert %s%s cost=%d\n" ! 593: , charname(acchar , 0 ) ! 594: , charname(acchar , 1 ) ! 595: , inscost(acchar)); ! 596: #endif ! 597: c = inscost(acchar, YC[0].Yychar); ! 598: #ifndef DEBUG ! 599: if (c < ccost) { ! 600: #endif ! 601: if (c == 0) { ! 602: c = correct(acchar, 0, 1, insmult + 1, Ps0, Pv0); ! 603: #ifdef DEBUG ! 604: Eprintf("Cost %2d Freebie %s%s\n", c ! 605: , charname(acchar , 0 ) ! 606: , charname(acchar , 1 )); ! 607: #endif ! 608: if (c < ccost) ! 609: cact = CUNIQUE, ccost = 0, cchar = acchar, cflag = flag; ! 610: } else { ! 611: c = correct(acchar, 0, c, insmult, Ps0, Pv0); ! 612: #ifdef DEBUG ! 613: if (c < CPRLIMIT || fulltrace) ! 614: Eprintf("Cost %2d Insert %s%s\n", c ! 615: , charname(acchar , 0 ) ! 616: , charname(acchar , 1 )); ! 617: #endif ! 618: if (c < ccost) ! 619: cact = CINSERT, ccost = c, cchar = acchar, cflag = flag; ! 620: } ! 621: #ifndef DEBUG ! 622: } ! 623: #endif ! 624: ! 625: /* ! 626: * Try replacement ! 627: */ ! 628: #ifdef DEBUG ! 629: Tprintf(" Try Replace %s%s with %s%s cost=%d\n", ! 630: tokname(&YC[0] , 0 ), ! 631: tokname(&YC[0] , 1 ), ! 632: charname(acchar , 0 ), ! 633: charname(acchar , 1 ), ! 634: repcost(YC[0].Yychar, acchar)); ! 635: #endif ! 636: c = repcost(YC[0].Yychar, acchar); ! 637: #ifndef DEBUG ! 638: if (c < ccost) { ! 639: #endif ! 640: c = correct(acchar, 1, repcost(YC[0].Yychar, acchar), repmult, Ps0, Pv0); ! 641: #ifdef DEBUG ! 642: if (c < CPRLIMIT || fulltrace) ! 643: Eprintf("Cost %2d Replace %s%s with %s%s\n", ! 644: c, ! 645: tokname(&YC[0] , 0 ), ! 646: tokname(&YC[0] , 1 ), ! 647: tokname(&ACtok , 0 ), ! 648: tokname(&ACtok , 1 )); ! 649: #endif ! 650: if (c < ccost) ! 651: cact = CREPLACE, ccost = c, cchar = acchar, cflag = flag; ! 652: #ifndef DEBUG ! 653: } ! 654: #endif ! 655: } ! 656: } ! 657: ! 658: int *yCpv; ! 659: char yyredfail; ! 660: ! 661: /* ! 662: * The ntok structure is used to build a ! 663: * scanner structure for tokens inserted ! 664: * from the argument "fchar" to "correct" below. ! 665: */ ! 666: static struct yytok ntok; ! 667: ! 668: /* ! 669: * Compute the cost of a correction ! 670: * C is the base cost for it. ! 671: * Fchar is the first input character from ! 672: * the current state, NOCHAR if none. ! 673: * The rest of the inputs come from the array ! 674: * YC, starting at origin and continuing to the ! 675: * last character there, YC[yCcnt - 1].Yychar. ! 676: * ! 677: * The cost returned is INFINITE if this correction ! 678: * allows no shifts, otherwise is weighted based ! 679: * on the number of shifts this allows against the ! 680: * maximum number possible with the available lookahead. ! 681: */ ! 682: correct(fchar, origin, c, multvec, Ps0, Pv0) ! 683: register int fchar, c; ! 684: int origin; ! 685: char *multvec; ! 686: int *Ps0, *Pv0; ! 687: { ! 688: register char *mv; ! 689: ! 690: /* ! 691: * Ps is the top of the parse stack after the most ! 692: * recent local correctness check. Loccor returns ! 693: * NIL when we cannot shift. ! 694: */ ! 695: register int *ps; ! 696: ! 697: yyredfail = 0; ! 698: /* ! 699: * Initialize the tip parse and semantic stacks. ! 700: */ ! 701: ps = Ps0; ! 702: yytips[0] = *ps; ! 703: ps--; ! 704: yytipv[0] = Pv0[0]; ! 705: yCpv = Pv0 - 1; ! 706: yytipct = 1; ! 707: ! 708: /* ! 709: * Shift while possible. ! 710: * Adjust cost as necessary. ! 711: */ ! 712: mv = multvec; ! 713: do { ! 714: if (fchar != NOCHAR) { ! 715: copy(&ntok, &YC[0], sizeof ntok); ! 716: ntok.Yychar = fchar, ntok.Yylval = nullsem(fchar); ! 717: fchar = NOCHAR; ! 718: ps = loccor(ps, &ntok); ! 719: } else ! 720: ps = loccor(ps, &YC[origin++]); ! 721: if (ps == NIL) { ! 722: if (yyredfail && mv > multvec) ! 723: mv--; ! 724: c *= *mv; ! 725: break; ! 726: } ! 727: mv++; ! 728: } while (*mv != 1); ! 729: return (c); ! 730: } ! 731: ! 732: extern int yygo[], yypgo[], yyr1[], yyr2[]; ! 733: /* ! 734: * Local syntactic correctness check. ! 735: * The arguments to this routine are a ! 736: * top of stack pointer, ps, and an input ! 737: * token tok. Also, implicitly, the contents ! 738: * of the yytips array which contains the tip ! 739: * of the stack, and into which the new top ! 740: * state on the stack will be placed if we shift. ! 741: * ! 742: * If we succeed, we return a new top of stack ! 743: * pointer, else we return NIL. ! 744: */ ! 745: loccor(ps, ntok) ! 746: int *ps; ! 747: struct yytok *ntok; ! 748: { ! 749: register int *p, n; ! 750: register int nchar; ! 751: int i; ! 752: ! 753: if (ps == NIL) ! 754: return (NIL); ! 755: nchar = ntok->Yychar; ! 756: yyeline = ntok->Yyeline; ! 757: #ifdef DEBUG ! 758: Tprintf(" Stack "); ! 759: for (i = yytipct - 1; i >= 0; i--) ! 760: Tprintf("%d ", yytips[i]); ! 761: Tprintf("| %d, Input %s%s\n", *ps ! 762: , charname(nchar , 0 ) ! 763: , charname(nchar , 1 )); ! 764: #endif ! 765: /* ! 766: * As in the yacc parser yyparse, ! 767: * p traces through the action list ! 768: * and "n" is the information associated ! 769: * with the action. ! 770: */ ! 771: newstate: ! 772: p = &yyact[ yypact[yytips[yytipct - 1]+1] ]; ! 773: ! 774: actn: ! 775: /* ! 776: * Search the parse actions table ! 777: * for something useful to do. ! 778: * While n is non-positive, it is the ! 779: * arithmetic inverse of the token to be tested. ! 780: * This allows a fast check. ! 781: */ ! 782: while ((n = *p++) <= 0) ! 783: if ((n += nchar) != 0) ! 784: p++; ! 785: switch (n >> 12) { ! 786: /* ! 787: * SHIFT ! 788: */ ! 789: case 2: ! 790: n &= 07777; ! 791: yyredfail = 0; ! 792: if (nchar == YID) ! 793: yyredfail++; ! 794: if (yytipct == YYTIPSIZ) { ! 795: tipover: ! 796: #ifdef DEBUG ! 797: Tprintf("\tTIP OVFLO\n"); ! 798: #endif ! 799: return (NIL); ! 800: } ! 801: yytips[yytipct] = n; ! 802: yytipv[yytipct] = ntok->Yylval; ! 803: yytipct++; ! 804: #ifdef DEBUG ! 805: Tprintf("\tShift to state %d\n", n); ! 806: #endif ! 807: return (ps); ! 808: /* ! 809: * REDUCE ! 810: */ ! 811: case 3: ! 812: n &= 07777; ! 813: if (yyEactr(n, yytipv[yytipct - 1]) == 0) { ! 814: #ifdef DEBUG ! 815: Tprintf("\tYyEactr objects: have %s id, want %s id\n", classes[yyidhave], classes[yyidwant]); ! 816: #endif ! 817: return (NIL); ! 818: } ! 819: yyredfail = 0; ! 820: i = yyr2[n]; ! 821: #ifdef DEBUG ! 822: Tprintf("\tReduce, length %d,", i); ! 823: #endif ! 824: if (i > yytipct) { ! 825: i -= yytipct; ! 826: yytipct = 0; ! 827: ps -= i; ! 828: yCpv -= i; ! 829: } else ! 830: yytipct -= i; ! 831: if (yytipct >= YYTIPSIZ) ! 832: goto tipover; ! 833: /* ! 834: * Use goto table to find next state ! 835: */ ! 836: p = &yygo[yypgo[yyr1[n]]]; ! 837: i = yytipct ? yytips[yytipct - 1] : *ps; ! 838: while (*p != i && *p >= 0) ! 839: p += 2; ! 840: #ifdef DEBUG ! 841: Tprintf(" new state %d\n", p[1]); ! 842: #endif ! 843: yytips[yytipct] = p[1]; ! 844: yytipct++; ! 845: goto newstate; ! 846: /* ! 847: * ACCEPT ! 848: */ ! 849: case 4: ! 850: #ifdef DEBUG ! 851: Tprintf("\tAccept\n"); ! 852: #endif ! 853: return (ps); ! 854: /* ! 855: * ERROR ! 856: */ ! 857: case 1: ! 858: #ifdef DEBUG ! 859: Tprintf("\tError\n"); ! 860: #endif ! 861: return (0); ! 862: } ! 863: panic("loccor"); ! 864: }
This archive runs on limited infrastructure. Preserving old code on modern bandwidth. Automated agents are requested to crawl responsibly.