1*48116Sbostic /*- 2*48116Sbostic * Copyright (c) 1980 The Regents of the University of California. 3*48116Sbostic * All rights reserved. 4*48116Sbostic * 5*48116Sbostic * %sccs.include.redist.c% 622214Sdist */ 7794Speter 814748Sthien #ifndef lint 9*48116Sbostic static char sccsid[] = "@(#)yyrecover.c 5.2 (Berkeley) 04/16/91"; 10*48116Sbostic #endif /* not lint */ 11794Speter 12794Speter #include "whoami.h" 13794Speter #include "0.h" 1414748Sthien #include "tree_ty.h" /* must be included for yy.h */ 15794Speter #include "yy.h" 16794Speter 17794Speter /* 18794Speter * Very simplified version of Graham-Rhodes error recovery 19794Speter * method for LALR parsers. Backward move is embodied in 20794Speter * default reductions of the yacc parser until an error condition 21794Speter * is reached. Forward move is over a small number of input tokens 22794Speter * and cannot "condense". The basic corrections are: 23794Speter * 24794Speter * 1) Delete the input token. 25794Speter * 26794Speter * 2) Replace the current input with a legal input. 27794Speter * 28794Speter * 3) Insert a legal token. 29794Speter * 30794Speter * All corrections are weighted, considered only if they allow 31794Speter * at least two shifts, and the cost of a correction increases if 32794Speter * it allows shifting over only a part of the lookahead. 33794Speter * 34794Speter * Another error situation is that which occurs when an identifier "fails" 35794Speter * a reduction because it is not the required "class". 36794Speter * In this case, we also consider replacing this identifier, which has 37794Speter * already been shifted over, with an identifier of the correct class. 38794Speter * 39794Speter * Another correction performed here is unique symbol insertion. 40794Speter * If the current state admits only one input, and no other alternative 41794Speter * correction presents itself, then that symbol will be inserted. 42794Speter * There is a danger in this of looping, and it is handled 43794Speter * by counting true shifts over input (see below). 44794Speter * 45794Speter * 46794Speter * A final class of corrections, considered only when the error 47794Speter * occurred immediately after a shift over a terminal, involves 48794Speter * the three basic corrections above, but with the point of error 49794Speter * considered to be before this terminal was shifted over, effectively 50794Speter * "unreading" this terminal. This is a feeble attempt at elimination 51794Speter * of the left-right bias and because "if" has a low weight and some 52794Speter * statements are quite simple i.e. 53794Speter * 54794Speter * cse ch of ... 55794Speter * 56794Speter * we can get a small number of errors. The major deficiency of 57794Speter * this is that we back up only one token, and that the forward 58794Speter * move is over a small number of tokens, often not enough to really 59794Speter * tell what the input should be, e.g. in 60794Speter * 61794Speter * a[i] > a[i - 1] ... 62794Speter * 63794Speter * In such cases a bad identifier (misspelled keyword) or omitted 64794Speter * keyword will be change or inserted as "if" as it has the lowest cost. 65794Speter * This is not terribly bad, as "if"s are most common. 66794Speter * This also allows the correction of other errors. 67794Speter * 68794Speter * This recovery depends on the default reductions which delay 69794Speter * noticing the error until the parse reaches a state where the 70794Speter * relevant "alternatives" are visible. Note that it does not 71794Speter * consider tokens which will cause reductions before being 72794Speter * shifted over. This requires the grammar to be written in a 73794Speter * certain way for the recovery to work correctly. 74794Speter * In some sense, also, the recovery suffers because we have 75794Speter * LALR(1) tables rather than LR(1) tables, e.g. in 76794Speter * 77794Speter * if rec.field < rec2,field2 then 78794Speter */ 79794Speter 80794Speter /* 81794Speter * Definitions of possible corrective actions 82794Speter */ 83794Speter #define CPANIC 0 84794Speter #define CDELETE 1 85794Speter #define CREPLACE 2 86794Speter #define CINSERT 3 87794Speter #define CUNIQUE 4 88794Speter #define CCHIDENT 5 89794Speter 90794Speter /* 91794Speter * Multiplicative cost factors for corrective actions. 92794Speter * 93794Speter * When an error occurs we take YCSIZ - 1 look-ahead tokens. 94794Speter * If a correction being considered will shift over only part of 95794Speter * that look-ahead, it is not completely discarded, but rather 96794Speter * "weighted", its cost being multiplied by a weighting factor. 97794Speter * For a correction to be considered its weighted cost must be less 98794Speter * than CLIMIT. 99794Speter * 100794Speter * Non-weighted costs are considered: 101794Speter * 102794Speter * LOW <= 3 103794Speter * MEDIUM 4,5 104794Speter * HIGH >= 6 105794Speter * 106794Speter * CURRENT WEIGHTING STRATEGY: Aug 20, 1977 107794Speter * 108794Speter * For all kinds of corrections we demand shifts over two symbols. 109794Speter * Corrections have high weight even after two symbol 110794Speter * shifts because the costs for deleting and inserting symbols are actually 111794Speter * quite low; we do not want to change weighty symbols 112794Speter * on inconclusive evidence. 113794Speter * 114794Speter * The weights are the same after the third look ahead. 115794Speter * This prevents later, unrelated errors from causing "funny" 116794Speter * biases of the weights toward one type of correction. 117794Speter * 118794Speter * Current look ahead is 5 symbols. 119794Speter */ 120794Speter 121794Speter /*** CLIMIT is defined in yy.h for yycosts ***/ 122794Speter #define CPRLIMIT 50 123794Speter #define CCHIDCOST 3 124794Speter 125794Speter char insmult[8] = {INFINITY, INFINITY, INFINITY, 15, 8, 6, 3, 1}; 126794Speter char repmult[7] = {INFINITY, INFINITY, INFINITY, 8, 6, 3, 1}; 127794Speter char delmult[6] = {INFINITY, INFINITY, INFINITY, 6, 3, 1}; 128794Speter 129794Speter #define NOCHAR -1 130794Speter 131794Speter #define Eprintf if (errtrace) printf 132794Speter #define Tprintf if (testtrace) printf 133794Speter 134794Speter /* 135794Speter * Action arrays of the parser needed here 136794Speter */ 13714748Sthien union semstack *yypv; 13814748Sthien int yyact[], yypact[]; 139794Speter 140794Speter /* 141794Speter * Yytips is the tip of the stack when using 142794Speter * the function loccor to check for local 143794Speter * syntactic correctness. As we don't want 144794Speter * to copy the whole parser stack, but want 145794Speter * to simulate parser moves, we "split" 146794Speter * the parser stack and keep the tip here. 147794Speter */ 148794Speter #define YYTIPSIZ 16 149794Speter int yytips[YYTIPSIZ], yytipct; 150794Speter int yytipv[YYTIPSIZ]; 151794Speter 152794Speter /* 153794Speter * The array YC saves the lookahead tokens for the 154794Speter * forward moves. 155794Speter * Yccnt is the number of tokens in the YC array. 156794Speter */ 157794Speter #define YCSIZ 6 158794Speter 159794Speter int yCcnt; 160794Speter struct yytok YC0[YCSIZ + 1]; 161794Speter struct yytok *YC; 162794Speter 163794Speter /* 164794Speter * YCps gives the top of stack at 165794Speter * the point of error. 166794Speter */ 167794Speter 16814748Sthien bool yyunique = TRUE; 169794Speter 170794Speter STATIC unsigned yyTshifts; 171794Speter 172794Speter /* 173794Speter * Cact is the corrective action we have decided on 174794Speter * so far, ccost its cost, and cchar the associated token. 175794Speter * Cflag tells if the correction is over the previous input token. 176794Speter */ 177794Speter int cact, ccost, cchar, cflag; 178794Speter 179794Speter /* 180794Speter * ACtok holds the token under 181794Speter * consideration when examining 182794Speter * the lookaheads in a state. 183794Speter */ 184794Speter struct yytok ACtok; 185794Speter 186794Speter #define acchar ACtok.Yychar 187794Speter #define aclval ACtok.Yylval 188794Speter 189794Speter /* 190794Speter * Make a correction to the current stack which has 191794Speter * top of stack pointer Ps. 192794Speter */ 193794Speter yyrecover(Ps0, idfail) 194794Speter int *Ps0, idfail; 195794Speter { 196794Speter register int c, i; 197794Speter int yyrwant, yyrhave; 198794Speter 199794Speter #ifdef PI 20014748Sthien Recovery = TRUE; 201794Speter #endif 202794Speter 203794Speter YC = &YC0[1]; 204794Speter #ifdef DEBUG 205794Speter if (errtrace) { 206794Speter setpfx('p'); 207794Speter yerror("Point of error"); 208794Speter printf("States %d %d ...", Ps0[0], Ps0[-1]); 209794Speter if (idfail) 210794Speter printf(" [Idfail]"); 21110732Smckusick #ifdef PXP 21210732Smckusick putchar('\n'); 21310732Smckusick #else 214794Speter pchr('\n'); 21510732Smckusick #endif 216794Speter printf("Input %s%s", tokname(&Y , 0) 217794Speter , tokname(&Y , 1)); 218794Speter } 219794Speter 220794Speter #endif 221794Speter /* 222794Speter * We first save the current input token 223794Speter * and its associated semantic information. 224794Speter */ 225794Speter if (yychar < 0) 226794Speter yychar = yylex(); 22714748Sthien copy((char *) (&YC[0]), (char *) (&Y), sizeof Y); 228794Speter 229794Speter /* 230794Speter * Set the default action and cost 231794Speter */ 232794Speter cact = CPANIC, ccost = CLIMIT, cflag = 0; 233794Speter 234794Speter /* 235794Speter * Peek ahead 236794Speter */ 237794Speter for (yCcnt = 1; yCcnt < YCSIZ; yCcnt++) { 238794Speter yychar = yylex(); 23914748Sthien copy((char *) (&YC[yCcnt]), (char *) (&Y), sizeof YC[0]); 240794Speter #ifdef DEBUG 241794Speter Eprintf(" | %s%s", tokname(&YC[yCcnt] , 0 ) 242794Speter , tokname(&YC[yCcnt] , 1 )); 243794Speter #endif 244794Speter } 245794Speter #ifdef DEBUG 246794Speter Eprintf("\n"); 247794Speter #endif 248794Speter 249794Speter /* 250794Speter * If we are here because a reduction failed, try 251794Speter * correcting that. 252794Speter */ 253794Speter if (idfail) { 254794Speter /* 255794Speter * Save the particulars about 256794Speter * the kind of identifier we want/have. 257794Speter */ 258794Speter yyrwant = yyidwant; 259794Speter yyrhave = yyidhave; 260794Speter #ifdef DEBUG 261794Speter Tprintf(" Try Replace %s identifier with %s identifier cost=%d\n", 262794Speter classes[yyidhave], classes[yyidwant], CCHIDCOST); 263794Speter #endif 264794Speter 265794Speter /* 266794Speter * Save the semantics of the ID on the 267794Speter * stack, and null them out to free 268794Speter * up the reduction in question. 269794Speter */ 27014748Sthien i = yypv[0].i_entry; 27114748Sthien yypv[0].i_entry = nullsem(YID); 27214748Sthien c = correct(NOCHAR, 0, CCHIDCOST, &repmult[2], Ps0, 27314748Sthien (int *) yypv); 27414748Sthien yypv[0].i_entry = i; 275794Speter #ifdef DEBUG 276794Speter if (c < CPRLIMIT || fulltrace) 277794Speter Eprintf("Cost %2d Replace %s identifier with %s identifier\n", c, classes[yyrhave], classes[yyrwant]); 278794Speter #endif 279794Speter if (c < ccost) 280794Speter cact = CCHIDENT, ccost = c, cchar = YID; 281794Speter } 282794Speter 283794Speter /* 284794Speter * First try correcting the state we are in 285794Speter */ 28614748Sthien trystate(Ps0, (int *) yypv, 0, &insmult[1], &delmult[1], &repmult[1]); 287794Speter 288794Speter /* 289794Speter * Now, if we just shifted over a terminal, try 290794Speter * correcting it. 291794Speter */ 292794Speter if (OY.Yychar != -1 && OY.Yylval != nullsem(OY.Yychar)) { 293794Speter YC--; 29414748Sthien copy((char *) (&YC[0]), (char *) (&OY), sizeof YC[0]); 29514748Sthien trystate(Ps0 - 1, (int *) (yypv - 1), 1, insmult, delmult, 29614748Sthien repmult); 297794Speter if (cflag == 0) 298794Speter YC++; 299794Speter else { 300794Speter yypv--; 301794Speter #ifdef PXP 302794Speter yypw--; 303794Speter #endif 304794Speter Ps0--; 305794Speter yCcnt++; 306794Speter } 307794Speter } 308794Speter 309794Speter /* 310794Speter * Restoring the first look ahead into 311794Speter * the scanner token allows the error message 312794Speter * routine to print the error message with the text 313794Speter * of the correct line. 314794Speter */ 31514748Sthien copy((char *) (&Y), (char *) (&YC[0]), sizeof Y); 316794Speter 317794Speter /* 318794Speter * Unique symbol insertion. 319794Speter * 320794Speter * If there was no reasonable correction found, 321794Speter * but only one input to the parser is acceptable 322794Speter * we report that, and try it. 323794Speter * 324794Speter * Special precautions here to prevent looping. 325794Speter * The number of true inputs shifted over at the point 326794Speter * of the last unique insertion is recorded in the 327794Speter * variable yyTshifts. If this is not less than 328794Speter * the current number in yytshifts, we do not insert. 329794Speter * Thus, after one unique insertion, no more unique 330794Speter * insertions will be made until an input is shifted 331794Speter * over. This guarantees termination. 332794Speter */ 333794Speter if (cact == CPANIC && !idfail) { 334794Speter register int *ap; 335794Speter 336794Speter ap = &yyact[yypact[*Ps0 + 1]]; 337794Speter if (*ap == -ERROR) 3383088Smckusic ap += 2; 339794Speter if (ap[0] <= 0 && ap[2] > 0) { 340794Speter cchar = -ap[0]; 341794Speter if (cchar == YEOF) 342794Speter yyexeof(); 343794Speter if (cchar != ERROR && yyTshifts < yytshifts) { 344794Speter cact = CUNIQUE; 345794Speter #ifdef DEBUG 346794Speter Eprintf("Unique symbol %s%s\n" 347794Speter , charname(cchar , 0 ) 348794Speter , charname(cchar , 1 )); 349794Speter #endif 350794Speter /* 351794Speter * Note that the inserted symbol 352794Speter * will not be counted as a true input 353794Speter * (i.e. the "yytshifts--" below) 354794Speter * so that a true shift will be needed 355794Speter * to make yytshifts > yyTshifts. 356794Speter */ 357794Speter yyTshifts = yytshifts; 358794Speter } 359794Speter } 360794Speter } 361794Speter 362794Speter /* 363794Speter * Set up to perform the correction. 364794Speter * Build a token appropriate for replacement 365794Speter * or insertion in the yytok structure ACchar 366794Speter * having the attributes of the input at the 367794Speter * point of error. 368794Speter */ 36914748Sthien copy((char *) (&ACtok), (char *) (&YC[0]), sizeof ACtok); 370794Speter acchar = cchar; 371794Speter aclval = nullsem(acchar); 372794Speter if (aclval != NIL) 373794Speter recovered(); 374794Speter switch (cact) { 375794Speter /* 376794Speter * Panic, just restore the 377794Speter * lookahead and return. 378794Speter */ 379794Speter case CPANIC: 380794Speter setpfx('E'); 381794Speter if (idfail) { 38214748Sthien copy((char *) (&Y), (char *) (&OY), sizeof Y); 383794Speter if (yyrhave == NIL) { 384794Speter #ifdef PI 38514748Sthien if (yybaduse(yypv[0].cptr, yyeline, ISUNDEF) == NIL) 386794Speter #endif 387794Speter yerror("Undefined identifier"); 388794Speter } else { 389794Speter yerror("Improper %s identifier", classes[yyrhave]); 390794Speter #ifdef PI 39114748Sthien (void) yybaduse(yypv[0].cptr, yyeline, NIL); 392794Speter #endif 393794Speter } 394794Speter /* 395794Speter * Suppress message from panic routine 396794Speter */ 397794Speter yyshifts = 1; 398794Speter } 399794Speter i = 0; 400794Speter /* Note that on one path we dont touch yyshifts ! */ 401794Speter break; 402794Speter /* 403794Speter * Delete the input. 404794Speter * Mark this as a shift over true input. 405794Speter * Restore the lookahead starting at 406794Speter * the second token. 407794Speter */ 408794Speter case CDELETE: 409794Speter if (ccost != 0) 410794Speter yerror("Deleted %s%s", tokname(&YC[0] , 0 ) 411794Speter , tokname(&YC[0] , 1 )); 412794Speter yytshifts++; 413794Speter i = 1; 414794Speter yyshifts = 0; 415794Speter break; 416794Speter /* 417794Speter * Replace the input with a new token. 418794Speter */ 419794Speter case CREPLACE: 420794Speter if (acchar == YEOF) 421794Speter yyexeof(); 422794Speter if (acchar == YEND) 423794Speter aclval = NIL; 424794Speter yerror("Replaced %s%s with a %s%s", 425794Speter tokname(&YC[0] , 0 ), 426794Speter tokname(&YC[0] , 1 ), 427794Speter tokname(&ACtok , 0 ), 428794Speter tokname(&ACtok , 1 )); 42914748Sthien copy((char *) (&YC[0]), (char *) (&ACtok), sizeof YC[0]); 430794Speter i = 0; 431794Speter yyshifts = 0; 432794Speter break; 433794Speter /* 434794Speter * Insert a token. 435794Speter * Don't count this token as a true input shift. 436794Speter * For inserted "end"s pas.y is responsible 437794Speter * for the error message later so suppress it. 438794Speter * Restore all the lookahead. 439794Speter */ 440794Speter case CINSERT: 441794Speter if (acchar == YEOF) 442794Speter yyexeof(); 443794Speter if (acchar != YEND) 444794Speter yerror("Inserted %s%s", 445794Speter tokname(&ACtok , 0 ), 446794Speter tokname(&ACtok , 1 )); 447794Speter yytshifts--; 448794Speter i = 0; 449794Speter yyshifts = 0; 450794Speter break; 451794Speter /* 452794Speter * Make a unique symbol correction. 453794Speter * Like an insertion but a different message. 454794Speter */ 455794Speter case CUNIQUE: 456794Speter setpfx('E'); 457794Speter yerror("Expected %s%s", 458794Speter tokname(&ACtok , 0 ), 459794Speter tokname(&ACtok , 1 )); 460794Speter yytshifts--; 461794Speter i = 0; 462794Speter if (ccost == 0 || yyunique) 463794Speter yyshifts = 0; 464794Speter else 465794Speter yyshifts = -1; 466794Speter break; 467794Speter /* 468794Speter * Change an identifier's type 469794Speter * to make it work. 470794Speter */ 471794Speter case CCHIDENT: 47214748Sthien copy((char *) (&Y), (char *) (&OY), sizeof Y); 473794Speter #ifdef PI 474794Speter i = 1 << yyrwant; 475794Speter #endif 476794Speter if (yyrhave == NIL) { 477794Speter yerror("Undefined %s", classes[yyrwant]); 478794Speter #ifdef PI 4793088Smckusic i |= ISUNDEF; 480794Speter #endif 481794Speter } else 482794Speter yerror("Replaced %s id with a %s id", classes[yyrhave], classes[yyrwant]); 483794Speter #ifdef PI 48414748Sthien (void) yybaduse(yypv[0].cptr, yyeline, i); 485794Speter #endif 48614748Sthien yypv[0].i_entry = nullsem(YID); 487794Speter i = 0; 488794Speter yyshifts = 0; 489794Speter break; 490794Speter } 491794Speter 492794Speter /* 493794Speter * Restore the desired portion of the lookahead, 494794Speter * and possibly the inserted or unique inserted token. 495794Speter */ 496794Speter for (yCcnt--; yCcnt >= i; yCcnt--) 497794Speter unyylex(&YC[yCcnt]); 498794Speter if (cact == CINSERT || cact == CUNIQUE) 499794Speter unyylex(&ACtok); 500794Speter 501794Speter /* 502794Speter * Put the scanner back in sync. 503794Speter */ 504794Speter yychar = yylex(); 505794Speter 506794Speter /* 507794Speter * We succeeded if we didn't "panic". 508794Speter */ 50914748Sthien Recovery = FALSE; 510794Speter Ps = Ps0; 511794Speter return (cact != CPANIC); 512794Speter } 513794Speter 514794Speter yyexeof() 515794Speter { 516794Speter 517794Speter yerror("End-of-file expected - QUIT"); 518794Speter pexit(ERRS); 519794Speter } 520794Speter 521794Speter yyunexeof() 522794Speter { 523794Speter 524794Speter yerror("Unexpected end-of-file - QUIT"); 525794Speter pexit(ERRS); 526794Speter } 527794Speter 528794Speter /* 529794Speter * Try corrections with the state at Ps0. 530794Speter * Flag is 0 if this is the top of stack state, 531794Speter * 1 if it is the state below. 532794Speter */ 533794Speter trystate(Ps0, Pv0, flag, insmult, delmult, repmult) 534794Speter int *Ps0, *Pv0, flag; 535794Speter char *insmult, *delmult, *repmult; 536794Speter { 537794Speter /* 538794Speter * C is a working cost, ap a pointer into the action 539794Speter * table for looking at feasible alternatives. 540794Speter */ 541794Speter register int c, *ap; 542794Speter 543794Speter #ifdef DEBUG 544794Speter Eprintf("Trying state %d\n", *Ps0); 545794Speter #endif 546794Speter /* 547794Speter * Try deletion. 548794Speter * Correct returns a cost. 549794Speter */ 550794Speter #ifdef DEBUG 551794Speter Tprintf(" Try Delete %s%s cost=%d\n", 552794Speter tokname(&YC[0] , 0 ), 553794Speter tokname(&YC[0] , 1 ), 554794Speter delcost(YC[0].Yychar)); 555794Speter #endif 556794Speter c = delcost(YC[0].Yychar); 557794Speter #ifndef DEBUG 558794Speter if (c < ccost) { 559794Speter #endif 560794Speter c = correct(NOCHAR, 1, c, delmult, Ps0, Pv0); 561794Speter #ifdef DEBUG 562794Speter if (c < CPRLIMIT || fulltrace) 563794Speter Eprintf("Cost %2d Delete %s%s\n", c, 564794Speter tokname(&YC[0] , 0 ), 565794Speter tokname(&YC[0] , 1 )); 566794Speter #endif 567794Speter if (c < ccost) 568794Speter cact = CDELETE, ccost = c, cflag = flag; 569794Speter #ifndef DEBUG 570794Speter } 571794Speter #endif 572794Speter 573794Speter /* 574794Speter * Look at the inputs to this state 575794Speter * which will cause parse action shift. 576794Speter */ 577794Speter aclval = NIL; 578794Speter ap = &yyact[yypact[*Ps0 + 1]]; 579794Speter 580794Speter /* 581794Speter * Skip action on error to 582794Speter * detect true unique inputs. 583794Speter * Error action is always first. 584794Speter */ 585794Speter if (*ap == -ERROR) 5863088Smckusic ap += 2; 587794Speter 588794Speter /* 589794Speter * Loop through the test actions 590794Speter * for this state. 591794Speter */ 59214748Sthien for (; *ap <= 0; ap += 2) { 593794Speter /* 594794Speter * Extract the token of this action 595794Speter */ 596794Speter acchar = -*ap; 597794Speter 598794Speter /* 599794Speter * Try insertion 600794Speter */ 601794Speter #ifdef DEBUG 602794Speter Tprintf(" Try Insert %s%s cost=%d\n" 603794Speter , charname(acchar , 0 ) 604794Speter , charname(acchar , 1 ) 60514748Sthien , inscost(acchar, YC[0].Yychar)); 606794Speter #endif 607794Speter c = inscost(acchar, YC[0].Yychar); 608794Speter #ifndef DEBUG 609794Speter if (c < ccost) { 610794Speter #endif 611794Speter if (c == 0) { 612794Speter c = correct(acchar, 0, 1, insmult + 1, Ps0, Pv0); 613794Speter #ifdef DEBUG 614794Speter Eprintf("Cost %2d Freebie %s%s\n", c 615794Speter , charname(acchar , 0 ) 616794Speter , charname(acchar , 1 )); 617794Speter #endif 618794Speter if (c < ccost) 619794Speter cact = CUNIQUE, ccost = 0, cchar = acchar, cflag = flag; 620794Speter } else { 621794Speter c = correct(acchar, 0, c, insmult, Ps0, Pv0); 622794Speter #ifdef DEBUG 623794Speter if (c < CPRLIMIT || fulltrace) 624794Speter Eprintf("Cost %2d Insert %s%s\n", c 625794Speter , charname(acchar , 0 ) 626794Speter , charname(acchar , 1 )); 627794Speter #endif 628794Speter if (c < ccost) 629794Speter cact = CINSERT, ccost = c, cchar = acchar, cflag = flag; 630794Speter } 631794Speter #ifndef DEBUG 632794Speter } 633794Speter #endif 634794Speter 635794Speter /* 636794Speter * Try replacement 637794Speter */ 638794Speter #ifdef DEBUG 639794Speter Tprintf(" Try Replace %s%s with %s%s cost=%d\n", 640794Speter tokname(&YC[0] , 0 ), 641794Speter tokname(&YC[0] , 1 ), 642794Speter charname(acchar , 0 ), 643794Speter charname(acchar , 1 ), 644794Speter repcost(YC[0].Yychar, acchar)); 645794Speter #endif 646794Speter c = repcost(YC[0].Yychar, acchar); 647794Speter #ifndef DEBUG 648794Speter if (c < ccost) { 649794Speter #endif 650794Speter c = correct(acchar, 1, repcost(YC[0].Yychar, acchar), repmult, Ps0, Pv0); 651794Speter #ifdef DEBUG 652794Speter if (c < CPRLIMIT || fulltrace) 653794Speter Eprintf("Cost %2d Replace %s%s with %s%s\n", 654794Speter c, 655794Speter tokname(&YC[0] , 0 ), 656794Speter tokname(&YC[0] , 1 ), 657794Speter tokname(&ACtok , 0 ), 658794Speter tokname(&ACtok , 1 )); 659794Speter #endif 660794Speter if (c < ccost) 661794Speter cact = CREPLACE, ccost = c, cchar = acchar, cflag = flag; 662794Speter #ifndef DEBUG 663794Speter } 664794Speter #endif 665794Speter } 666794Speter } 667794Speter 668794Speter int *yCpv; 669794Speter char yyredfail; 670794Speter 671794Speter /* 672794Speter * The ntok structure is used to build a 673794Speter * scanner structure for tokens inserted 674794Speter * from the argument "fchar" to "correct" below. 675794Speter */ 676794Speter static struct yytok ntok; 677794Speter 678794Speter /* 679794Speter * Compute the cost of a correction 680794Speter * C is the base cost for it. 681794Speter * Fchar is the first input character from 682794Speter * the current state, NOCHAR if none. 683794Speter * The rest of the inputs come from the array 684794Speter * YC, starting at origin and continuing to the 685794Speter * last character there, YC[yCcnt - 1].Yychar. 686794Speter * 687794Speter * The cost returned is INFINITE if this correction 688794Speter * allows no shifts, otherwise is weighted based 689794Speter * on the number of shifts this allows against the 690794Speter * maximum number possible with the available lookahead. 691794Speter */ 692794Speter correct(fchar, origin, c, multvec, Ps0, Pv0) 693794Speter register int fchar, c; 694794Speter int origin; 695794Speter char *multvec; 696794Speter int *Ps0, *Pv0; 697794Speter { 698794Speter register char *mv; 69914748Sthien extern int *loccor(); 700794Speter 701794Speter /* 702794Speter * Ps is the top of the parse stack after the most 703794Speter * recent local correctness check. Loccor returns 704794Speter * NIL when we cannot shift. 705794Speter */ 706794Speter register int *ps; 707794Speter 708794Speter yyredfail = 0; 709794Speter /* 710794Speter * Initialize the tip parse and semantic stacks. 711794Speter */ 712794Speter ps = Ps0; 713794Speter yytips[0] = *ps; 714794Speter ps--; 715794Speter yytipv[0] = Pv0[0]; 716794Speter yCpv = Pv0 - 1; 717794Speter yytipct = 1; 718794Speter 719794Speter /* 720794Speter * Shift while possible. 721794Speter * Adjust cost as necessary. 722794Speter */ 723794Speter mv = multvec; 724794Speter do { 725794Speter if (fchar != NOCHAR) { 72614748Sthien copy((char *) (&ntok), (char *) (&YC[0]), sizeof ntok); 727794Speter ntok.Yychar = fchar, ntok.Yylval = nullsem(fchar); 728794Speter fchar = NOCHAR; 729794Speter ps = loccor(ps, &ntok); 730794Speter } else 731794Speter ps = loccor(ps, &YC[origin++]); 732794Speter if (ps == NIL) { 733794Speter if (yyredfail && mv > multvec) 734794Speter mv--; 7353088Smckusic c *= *mv; 736794Speter break; 737794Speter } 738794Speter mv++; 739794Speter } while (*mv != 1); 740794Speter return (c); 741794Speter } 742794Speter 743794Speter extern int yygo[], yypgo[], yyr1[], yyr2[]; 744794Speter /* 745794Speter * Local syntactic correctness check. 746794Speter * The arguments to this routine are a 747794Speter * top of stack pointer, ps, and an input 748794Speter * token tok. Also, implicitly, the contents 749794Speter * of the yytips array which contains the tip 750794Speter * of the stack, and into which the new top 751794Speter * state on the stack will be placed if we shift. 752794Speter * 753794Speter * If we succeed, we return a new top of stack 754794Speter * pointer, else we return NIL. 755794Speter */ 75614748Sthien int * 757794Speter loccor(ps, ntok) 758794Speter int *ps; 759794Speter struct yytok *ntok; 760794Speter { 761794Speter register int *p, n; 762794Speter register int nchar; 763794Speter int i; 764794Speter 765794Speter if (ps == NIL) 766794Speter return (NIL); 767794Speter nchar = ntok->Yychar; 768794Speter yyeline = ntok->Yyeline; 769794Speter #ifdef DEBUG 770794Speter Tprintf(" Stack "); 771794Speter for (i = yytipct - 1; i >= 0; i--) 772794Speter Tprintf("%d ", yytips[i]); 773794Speter Tprintf("| %d, Input %s%s\n", *ps 774794Speter , charname(nchar , 0 ) 775794Speter , charname(nchar , 1 )); 776794Speter #endif 777794Speter /* 778794Speter * As in the yacc parser yyparse, 779794Speter * p traces through the action list 780794Speter * and "n" is the information associated 781794Speter * with the action. 782794Speter */ 783794Speter newstate: 784794Speter p = &yyact[ yypact[yytips[yytipct - 1]+1] ]; 785794Speter 786794Speter /* 787794Speter * Search the parse actions table 788794Speter * for something useful to do. 789794Speter * While n is non-positive, it is the 790794Speter * arithmetic inverse of the token to be tested. 791794Speter * This allows a fast check. 792794Speter */ 793794Speter while ((n = *p++) <= 0) 7943088Smckusic if ((n += nchar) != 0) 795794Speter p++; 796794Speter switch (n >> 12) { 797794Speter /* 798794Speter * SHIFT 799794Speter */ 80014748Sthien default: 80114748Sthien panic("loccor"); 802794Speter case 2: 8033088Smckusic n &= 07777; 804794Speter yyredfail = 0; 805794Speter if (nchar == YID) 806794Speter yyredfail++; 807794Speter if (yytipct == YYTIPSIZ) { 808794Speter tipover: 809794Speter #ifdef DEBUG 810794Speter Tprintf("\tTIP OVFLO\n"); 811794Speter #endif 812794Speter return (NIL); 813794Speter } 814794Speter yytips[yytipct] = n; 815794Speter yytipv[yytipct] = ntok->Yylval; 816794Speter yytipct++; 817794Speter #ifdef DEBUG 818794Speter Tprintf("\tShift to state %d\n", n); 819794Speter #endif 820794Speter return (ps); 821794Speter /* 822794Speter * REDUCE 823794Speter */ 824794Speter case 3: 8253088Smckusic n &= 07777; 82614748Sthien if (yyEactr(n, (char *) yytipv[yytipct - 1]) == 0) { 827794Speter #ifdef DEBUG 828794Speter Tprintf("\tYyEactr objects: have %s id, want %s id\n", classes[yyidhave], classes[yyidwant]); 829794Speter #endif 830794Speter return (NIL); 831794Speter } 832794Speter yyredfail = 0; 833794Speter i = yyr2[n]; 834794Speter #ifdef DEBUG 835794Speter Tprintf("\tReduce, length %d,", i); 836794Speter #endif 837794Speter if (i > yytipct) { 8383088Smckusic i -= yytipct; 839794Speter yytipct = 0; 8403088Smckusic ps -= i; 8413088Smckusic yCpv -= i; 842794Speter } else 8433088Smckusic yytipct -= i; 844794Speter if (yytipct >= YYTIPSIZ) 845794Speter goto tipover; 846794Speter /* 847794Speter * Use goto table to find next state 848794Speter */ 849794Speter p = &yygo[yypgo[yyr1[n]]]; 850794Speter i = yytipct ? yytips[yytipct - 1] : *ps; 851794Speter while (*p != i && *p >= 0) 8523088Smckusic p += 2; 853794Speter #ifdef DEBUG 854794Speter Tprintf(" new state %d\n", p[1]); 855794Speter #endif 856794Speter yytips[yytipct] = p[1]; 857794Speter yytipct++; 858794Speter goto newstate; 859794Speter /* 860794Speter * ACCEPT 861794Speter */ 862794Speter case 4: 863794Speter #ifdef DEBUG 864794Speter Tprintf("\tAccept\n"); 865794Speter #endif 866794Speter return (ps); 867794Speter /* 868794Speter * ERROR 869794Speter */ 870794Speter case 1: 871794Speter #ifdef DEBUG 872794Speter Tprintf("\tError\n"); 873794Speter #endif 874794Speter return (0); 875794Speter } 876794Speter } 877