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 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 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 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; 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 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 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 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 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 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 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 545 cmpmbchars(p, q) 546 MBCLIT *p, *q; 547 { 548 /* Compare two MBLITs. */ 549 return ((p->character) - (q->character)); 550 } 551 552 static void 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