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