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