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