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