xref: /illumos-gate/usr/src/cmd/sgs/yacc/common/y3.c (revision 1dd08564)
1 /*
2  * CDDL HEADER START
3  *
4  * The contents of this file are subject to the terms of the
5  * Common Development and Distribution License (the "License").
6  * You may not use this file except in compliance with the License.
7  *
8  * You can obtain a copy of the license at usr/src/OPENSOLARIS.LICENSE
9  * or http://www.opensolaris.org/os/licensing.
10  * See the License for the specific language governing permissions
11  * and limitations under the License.
12  *
13  * When distributing Covered Code, include this CDDL HEADER in each
14  * file and include the License file at usr/src/OPENSOLARIS.LICENSE.
15  * If applicable, add the following below this CDDL HEADER, with the
16  * fields enclosed by brackets "[]" replaced with your own identifying
17  * information: Portions Copyright [yyyy] [name of copyright owner]
18  *
19  * CDDL HEADER END
20  */
21 /*
22  * Copyright 2008 Sun Microsystems, Inc.  All rights reserved.
23  * Use is subject to license terms.
24  */
25 
26 /* Copyright (c) 1988 AT&T */
27 /* All Rights Reserved */
28 
29 #pragma ident	"%Z%%M%	%I%	%E% SMI"
30 
31 #include "dextern.h"
32 
33 static void go2gen(int);
34 static void precftn(int, int, int);
35 static void wract(int);
36 static void wrstate(int);
37 static void wdef(wchar_t *, int);
38 static void wrmbchars(void);
39 	/* important local variables */
40 static int lastred; /* number of the last reduction of a state */
41 int *defact;
42 extern int *toklev;
43 extern int cwp;
44 
45 /* print the output for the states */
46 void
output()47 output()
48 {
49 	int i, k, c;
50 	register WSET *u, *v;
51 
52 	(void) fprintf(ftable, "static YYCONST yytabelem yyexca[] ={\n");
53 
54 	SLOOP(i) { /* output the stuff for state i */
55 		nolook = !(tystate[i] == MUSTLOOKAHEAD);
56 		closure(i);
57 		/* output actions */
58 		nolook = 1;
59 		aryfil(temp1, ntoksz+nnontersz+1, 0);
60 		WSLOOP(wsets, u) {
61 			c = *(u->pitem);
62 			if (c > 1 && c < NTBASE && temp1[c] == 0) {
63 				WSLOOP(u, v) {
64 					if (c == *(v->pitem))
65 						putitem(v->pitem + 1,
66 						    (LOOKSETS *)0);
67 				}
68 				temp1[c] = state(c);
69 			} else if (c > NTBASE &&
70 			    temp1[(c -= NTBASE) + ntokens] == 0) {
71 				temp1[c + ntokens] = amem[indgo[i] + c];
72 			}
73 		}
74 		if (i == 1)
75 			temp1[1] = ACCEPTCODE;
76 		/* now, we have the shifts; look at the reductions */
77 		lastred = 0;
78 		WSLOOP(wsets, u) {
79 			c = *(u->pitem);
80 			if (c <= 0) { /* reduction */
81 				lastred = -c;
82 				TLOOP(k) {
83 					if (BIT(u->ws.lset, k)) {
84 						if (temp1[k] == 0)
85 							temp1[k] = c;
86 						else if (temp1[k] < 0) {
87 							/*
88 							 * reduce/reduce
89 							 * conflict
90 							 */
91 							/* BEGIN CSTYLED */
92 							if (foutput != NULL)
93 					(void) fprintf(foutput,
94 				WSFMT("\n%d: reduce/reduce conflict"
95 				" (red'ns %d and %d ) on %ws"),
96 							i, -temp1[k],
97 							lastred, symnam(k));
98 						    if (-temp1[k] > lastred)
99 							temp1[k] = -lastred;
100 						    ++zzrrconf;
101 							/* END CSTYLED */
102 						} else
103 							/*
104 							 * potentia
105 							 * shift/reduce
106 							 * conflict.
107 							 */
108 							precftn(lastred, k, i);
109 					}
110 				}
111 			}
112 		}
113 		wract(i);
114 	}
115 
116 	(void) fprintf(ftable, "\t};\n");
117 	wdef(L"YYNPROD", nprod);
118 	if (nmbchars > 0) {
119 		wrmbchars();
120 	}
121 }
122 
123 static int pkdebug = 0;
124 int
apack(p,n)125 apack(p, n)
126 int *p;
127 int n;
128 {
129 	/* pack state i from temp1 into amem */
130 	int off;
131 	int *pp, *qq;
132 	int *q, *rr;
133 	int diff;
134 
135 	/*
136 	 * we don't need to worry about checking because we
137 	 * we will only look up entries known to be there...
138 	 */
139 
140 	/* eliminate leading and trailing 0's */
141 
142 	q = p + n;
143 	for (pp = p, off = 0; *pp == 0 && pp <= q; ++pp, --off)
144 		/* NULL */;
145 	if (pp > q)
146 		return (0);  /* no actions */
147 	p = pp;
148 
149 	/* now, find a place for the elements from p to q, inclusive */
150 	/* for( rr=amem; rr<=r; ++rr,++off ){ */  /* try rr */
151 	rr = amem;
152 	for (; ; ++rr, ++off) {
153 		while (rr >= &amem[new_actsize-1])
154 			exp_act(&rr);
155 		qq = rr;
156 		for (pp = p; pp <= q; ++pp, ++qq) {
157 			if (*pp) {
158 				diff = qq - rr;
159 				while (qq >= &amem[new_actsize-1]) {
160 					exp_act(&rr);
161 					qq = diff + rr;
162 				}
163 				if (*pp != *qq && *qq != 0)
164 					goto nextk;
165 			}
166 		}
167 
168 		/* we have found an acceptable k */
169 
170 		if (pkdebug && foutput != NULL)
171 			(void) fprintf(foutput,
172 				"off = %d, k = %" PRIdPTR "\n", off, rr-amem);
173 
174 		qq = rr;
175 		for (pp = p; pp <= q; ++pp, ++qq) {
176 			if (*pp) {
177 				diff = qq - rr;
178 				while (qq >= &amem[new_actsize-1]) {
179 					exp_act(&rr);
180 					qq = diff + rr;
181 				}
182 				if (qq > memp)
183 					memp = qq;
184 				*qq = *pp;
185 			}
186 		}
187 		if (pkdebug && foutput != NULL) {
188 			for (pp = amem; pp <= memp; pp += 10) {
189 				(void) fprintf(foutput, "\t");
190 				for (qq = pp; qq <= pp + 9; ++qq)
191 					(void) fprintf(foutput, "%d ", *qq);
192 				(void) fprintf(foutput, "\n");
193 			}
194 		}
195 		return (off);
196 		nextk:;
197 	}
198 	/* error("no space in action table" ); */
199 	/* NOTREACHED */
200 }
201 
202 void
go2out()203 go2out()
204 {
205 	/* output the gotos for the nontermninals */
206 	int i, j, k, best, count, cbest, times;
207 
208 	(void) fprintf(ftemp, "$\n");  /* mark begining of gotos */
209 
210 	for (i = 1; i <= nnonter; ++i) {
211 		go2gen(i);
212 		/* find the best one to make default */
213 		best = -1;
214 		times = 0;
215 		for (j = 0; j < nstate; ++j) { /* is j the most frequent */
216 			if (tystate[j] == 0)
217 				continue;
218 			if (tystate[j] == best)
219 				continue;
220 			/* is tystate[j] the most frequent */
221 			count = 0;
222 			cbest = tystate[j];
223 			for (k = j; k < nstate; ++k)
224 				if (tystate[k] == cbest)
225 					++count;
226 			if (count > times) {
227 				best = cbest;
228 				times = count;
229 			}
230 		}
231 
232 		/* best is now the default entry */
233 		zzgobest += (times-1);
234 		for (j = 0; j < nstate; ++j) {
235 			if (tystate[j] != 0 && tystate[j] != best) {
236 				(void) fprintf(ftemp, "%d,%d,", j, tystate[j]);
237 				zzgoent += 1;
238 			}
239 		}
240 
241 		/* now, the default */
242 
243 		zzgoent += 1;
244 		(void) fprintf(ftemp, "%d\n", best);
245 
246 	}
247 }
248 
249 static int g2debug = 0;
go2gen(int c)250 static void go2gen(int c)
251 {
252 	/* output the gotos for nonterminal c */
253 	int i, work, cc;
254 	ITEM *p, *q;
255 
256 	/* first, find nonterminals with gotos on c */
257 	aryfil(temp1, nnonter + 1, 0);
258 	temp1[c] = 1;
259 
260 	work = 1;
261 	while (work) {
262 		work = 0;
263 		PLOOP(0, i) {
264 			if ((cc = prdptr[i][1] - NTBASE) >= 0) {
265 				/* cc is a nonterminal */
266 				if (temp1[cc] != 0) {
267 					/*
268 					 * cc has a goto on c
269 					 * thus, the left side of
270 					 * production i does too.
271 					 */
272 					cc = *prdptr[i] - NTBASE;
273 					if (temp1[cc] == 0) {
274 						work = 1;
275 						temp1[cc] = 1;
276 					}
277 				}
278 			}
279 		}
280 	}
281 
282 	/* now, we have temp1[c] = 1 if a goto on c in closure of cc */
283 
284 	if (g2debug && foutput != NULL) {
285 		(void) fprintf(foutput, WSFMT("%ws: gotos on "),
286 		    nontrst[c].name);
287 		NTLOOP(i) if (temp1[i])
288 			(void) fprintf(foutput, WSFMT("%ws "), nontrst[i].name);
289 		(void) fprintf(foutput, "\n");
290 	}
291 
292 	/* now, go through and put gotos into tystate */
293 	aryfil(tystate, nstate, 0);
294 	SLOOP(i) {
295 		ITMLOOP(i, p, q) {
296 			if ((cc = *p->pitem) >= NTBASE) {
297 				if (temp1[cc -= NTBASE]) {
298 					/* goto on c is possible */
299 					tystate[i] = amem[indgo[i] + c];
300 					break;
301 				}
302 			}
303 		}
304 	}
305 }
306 
307 /* decide a shift/reduce conflict by precedence.  */
308 static void
precftn(int r,int t,int s)309 precftn(int r, int t, int s)
310 {
311 
312 	/*
313 	 * r is a rule number, t a token number
314 	 * the conflict is in state s
315 	 * temp1[t] is changed to reflect the action
316 	 */
317 
318 	int lp, lt, action;
319 
320 	lp = levprd[r];
321 	lt = toklev[t];
322 	if (PLEVEL(lt) == 0 || PLEVEL(lp) == 0) {
323 		/* conflict */
324 		if (foutput != NULL)
325 			(void) fprintf(foutput,
326 			    WSFMT("\n%d: shift/reduce conflict"
327 			    " (shift %d, red'n %d) on %ws"),
328 			    s, temp1[t], r, symnam(t));
329 		++zzsrconf;
330 		return;
331 	}
332 	if (PLEVEL(lt) == PLEVEL(lp))
333 		action = ASSOC(lt) & ~04;
334 	else if (PLEVEL(lt) > PLEVEL(lp))
335 		action = RASC;  /* shift */
336 	else
337 		action = LASC;  /* reduce */
338 
339 	switch (action) {
340 	case BASC:  /* error action */
341 		temp1[t] = ERRCODE;
342 		return;
343 	case LASC:  /* reduce */
344 		temp1[t] = -r;
345 		return;
346 	}
347 }
348 
349 static void
wract(int i)350 wract(int i)
351 {
352 	/* output state i */
353 	/* temp1 has the actions, lastred the default */
354 	int p, p0, p1;
355 	int ntimes, tred, count, j;
356 	int flag;
357 
358 	/* find the best choice for lastred */
359 
360 	lastred = 0;
361 	ntimes = 0;
362 	TLOOP(j) {
363 		if (temp1[j] >= 0)
364 			continue;
365 		if (temp1[j] + lastred == 0)
366 			continue;
367 		/* count the number of appearances of temp1[j] */
368 		count = 0;
369 		tred = -temp1[j];
370 		levprd[tred] |= REDFLAG;
371 		TLOOP(p) {
372 			if (temp1[p] + tred == 0)
373 				++count;
374 		}
375 		if (count > ntimes) {
376 			lastred = tred;
377 			ntimes = count;
378 		}
379 	}
380 
381 	/*
382 	 * for error recovery, arrange that, if there is a shift on the
383 	 * error recovery token, `error', that the default be the error action
384 	 */
385 	if (temp1[2] > 0)
386 		lastred = 0;
387 
388 	/* clear out entries in temp1 which equal lastred */
389 	TLOOP(p) {
390 		if (temp1[p] + lastred == 0)
391 			temp1[p] = 0;
392 	}
393 
394 	wrstate(i);
395 	defact[i] = lastred;
396 
397 	flag = 0;
398 	TLOOP(p0) {
399 		if ((p1 = temp1[p0]) != 0) {
400 			if (p1 < 0) {
401 				p1 = -p1;
402 				goto exc;
403 			} else if (p1 == ACCEPTCODE) {
404 				p1 = -1;
405 				goto exc;
406 			} else if (p1 == ERRCODE) {
407 				p1 = 0;
408 				goto exc;
409 			exc:
410 				if (flag++ == 0)
411 					(void) fprintf(ftable, "-1, %d,\n", i);
412 				(void) fprintf(ftable,
413 				    "\t%d, %d,\n", tokset[p0].value, p1);
414 				++zzexcp;
415 			} else {
416 				(void) fprintf(ftemp,
417 				    "%d,%d,", tokset[p0].value, p1);
418 				++zzacent;
419 			}
420 		}
421 	}
422 	if (flag) {
423 		defact[i] = -2;
424 		(void) fprintf(ftable, "\t-2, %d,\n", lastred);
425 	}
426 	(void) fprintf(ftemp, "\n");
427 }
428 
429 static void
wrstate(int i)430 wrstate(int i)
431 {
432 	/* writes state i */
433 	int j0, j1;
434 	register ITEM *pp, *qq;
435 	register WSET *u;
436 
437 	if (foutput == NULL)
438 		return;
439 	(void) fprintf(foutput, "\nstate %d\n", i);
440 	ITMLOOP(i, pp, qq) {
441 		(void) fprintf(foutput, WSFMT("\t%ws\n"), writem(pp->pitem));
442 	}
443 	if (tystate[i] == MUSTLOOKAHEAD) {
444 		/* print out empty productions in closure */
445 		WSLOOP(wsets + (pstate[i + 1] - pstate[i]), u) {
446 			if (*(u->pitem) < 0)
447 				(void) fprintf(foutput,
448 				    WSFMT("\t%ws\n"), writem(u->pitem));
449 		}
450 	}
451 
452 	/* check for state equal to another */
453 	TLOOP(j0) if ((j1 = temp1[j0]) != 0) {
454 		(void) fprintf(foutput, WSFMT("\n\t%ws  "), symnam(j0));
455 		if (j1 > 0) { /* shift, error, or accept */
456 			if (j1 == ACCEPTCODE)
457 				(void) fprintf(foutput,  "accept");
458 			else if (j1 == ERRCODE)
459 				(void) fprintf(foutput, "error");
460 			else
461 				(void) fprintf(foutput, "shift %d", j1);
462 		}
463 		else
464 			(void) fprintf(foutput, "reduce %d", -j1);
465 	}
466 
467 	/* output the final production */
468 	if (lastred)
469 		(void) fprintf(foutput, "\n\t.  reduce %d\n\n", lastred);
470 	else
471 		(void) fprintf(foutput, "\n\t.  error\n\n");
472 
473 	/* now, output nonterminal actions */
474 	j1 = ntokens;
475 	for (j0 = 1; j0 <= nnonter; ++j0) {
476 		if (temp1[++j1])
477 			(void) fprintf(foutput,
478 			    WSFMT("\t%ws  goto %d\n"),
479 			    symnam(j0 + NTBASE), temp1[j1]);
480 	}
481 }
482 
483 static void
wdef(wchar_t * s,int n)484 wdef(wchar_t *s, int n)
485 {
486 	/* output a definition of s to the value n */
487 	(void) fprintf(ftable, WSFMT("# define %ws %d\n"), s, n);
488 }
489 
490 void
warray(s,v,n)491 warray(s, v, n)
492 wchar_t *s;
493 int *v, n;
494 {
495 	int i;
496 	(void) fprintf(ftable, WSFMT("static YYCONST yytabelem %ws[]={\n"), s);
497 	for (i = 0; i < n; ) {
498 		if (i % 10 == 0)
499 			(void) fprintf(ftable, "\n");
500 		(void) fprintf(ftable, "%6d", v[i]);
501 		if (++i == n)
502 			(void) fprintf(ftable, " };\n");
503 		else
504 			(void) fprintf(ftable, ",");
505 	}
506 }
507 
508 void
hideprod()509 hideprod()
510 {
511 	/*
512 	 * in order to free up the mem and amem arrays for the optimizer,
513 	 * and still be able to output yyr1, etc., after the sizes of
514 	 * the action array is known, we hide the nonterminals
515 	 * derived by productions in levprd.
516 	 */
517 
518 	int i, j;
519 
520 	j = 0;
521 	levprd[0] = 0;
522 	PLOOP(1, i) {
523 		if (!(levprd[i] & REDFLAG)) {
524 			++j;
525 			if (foutput != NULL) {
526 				(void) fprintf(foutput,
527 				    WSFMT("Rule not reduced:   %ws\n"),
528 				    writem(prdptr[i]));
529 			}
530 		}
531 		levprd[i] = *prdptr[i] - NTBASE;
532 	}
533 	if (j)
534 /*
535  * TRANSLATION_NOTE  -- This is a message from yacc.
536  *	Check how 'reduced' is translated in yacc man page/document.
537  */
538 		(void) fprintf(stderr,
539 		    gettext("%d rules never reduced\n"),
540 		    j);
541 }
542 
543 
544 static int
cmpmbchars(p,q)545 cmpmbchars(p, q)
546 MBCLIT *p, *q;
547 {
548 	/* Compare two MBLITs. */
549 	return ((p->character) - (q->character));
550 }
551 
552 static void
wrmbchars()553 wrmbchars()
554 {
555 	int i;
556 	wdef(L"YYNMBCHARS", nmbchars);
557 	qsort(mbchars, nmbchars, sizeof (*mbchars),
558 	    (int (*)(const void *, const void *))cmpmbchars);
559 	(void) fprintf(ftable,
560 	    "static struct{\n\twchar_t character;"
561 	    "\n\tint tvalue;\n}yymbchars[YYNMBCHARS]={\n");
562 	for (i = 0; i < nmbchars; ++i) {
563 		(void) fprintf(ftable, "\t{%#x,%d}",
564 		    (int)mbchars[i].character, mbchars[i].tvalue);
565 		if (i < nmbchars - 1) {
566 			/* Not the last. */
567 			(void) fprintf(ftable, ",\n");
568 		}
569 	}
570 	(void) fprintf(ftable, "\n};\n");
571 }
572