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