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 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 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 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 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 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 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 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 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 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 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 540 cmpmbchars(MBCLIT *p, MBCLIT *q) 541 { 542 /* Compare two MBLITs. */ 543 return ((p->character) - (q->character)); 544 } 545 546 static 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