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, Version 1.0 only 6 * (the "License"). You may not use this file except in compliance 7 * with the License. 8 * 9 * You can obtain a copy of the license at usr/src/OPENSOLARIS.LICENSE 10 * or http://www.opensolaris.org/os/licensing. 11 * See the License for the specific language governing permissions 12 * and limitations under the License. 13 * 14 * When distributing Covered Code, include this CDDL HEADER in each 15 * file and include the License file at usr/src/OPENSOLARIS.LICENSE. 16 * If applicable, add the following below this CDDL HEADER, with the 17 * fields enclosed by brackets "[]" replaced with your own identifying 18 * information: Portions Copyright [yyyy] [name of copyright owner] 19 * 20 * CDDL HEADER END 21 */ 22 /* 23 * Copyright 1990 Sun Microsystems, Inc. All rights reserved. 24 * Use is subject to license terms. 25 */ 26 27 /* Copyright (c) 1988 AT&T */ 28 /* All Rights Reserved */ 29 30 #pragma ident "%Z%%M% %I% %E% SMI" 31 32 #include "dextern" 33 34 static void go2gen(int); 35 static void precftn(int, int, int); 36 static void wract(int); 37 static void wrstate(int); 38 static void wdef(wchar_t *, int); 39 #ifndef NOLIBW 40 static void wrmbchars(void); 41 #endif /* !NOLIBW */ 42 /* important local variables */ 43 static int lastred; /* number of the last reduction of a state */ 44 int *defact; 45 extern int *toklev; 46 extern int cwp; 47 48 /* print the output for the states */ 49 void 50 output() 51 { 52 int i, k, c; 53 register WSET *u, *v; 54 55 (void) fprintf(ftable, "static YYCONST yytabelem yyexca[] ={\n"); 56 57 SLOOP(i) { /* output the stuff for state i */ 58 nolook = !(tystate[i] == MUSTLOOKAHEAD); 59 closure(i); 60 /* output actions */ 61 nolook = 1; 62 aryfil(temp1, ntoksz+nnontersz+1, 0); 63 WSLOOP(wsets, u) { 64 c = *(u->pitem); 65 if (c > 1 && c < NTBASE && temp1[c] == 0) { 66 WSLOOP(u, v) { 67 if (c == *(v->pitem)) 68 putitem(v->pitem + 1, 69 (LOOKSETS *)0); 70 } 71 temp1[c] = state(c); 72 } else if (c > NTBASE && 73 temp1[(c -= NTBASE) + ntokens] == 0) { 74 temp1[c + ntokens] = amem[indgo[i] + c]; 75 } 76 } 77 if (i == 1) 78 temp1[1] = ACCEPTCODE; 79 /* now, we have the shifts; look at the reductions */ 80 lastred = 0; 81 WSLOOP(wsets, u) { 82 c = *(u->pitem); 83 if (c <= 0) { /* reduction */ 84 lastred = -c; 85 TLOOP(k) { 86 if (BIT(u->ws.lset, k)) { 87 if (temp1[k] == 0) 88 temp1[k] = c; 89 else if (temp1[k] < 0) { 90 /* 91 * reduce/reduce 92 * conflict 93 */ 94 if (foutput != NULL) 95 (void) fprintf(foutput, 96 "\n%d: reduce/reduce conflict" 97 " (red'ns %d and %d ) on %ws", 98 i, -temp1[k], 99 lastred, symnam(k)); 100 if (-temp1[k] > lastred) 101 temp1[k] = -lastred; 102 ++zzrrconf; 103 } else 104 /* 105 * potentia 106 * shift/reduce 107 * conflict. 108 */ 109 precftn(lastred, k, i); 110 } 111 } 112 } 113 } 114 wract(i); 115 } 116 117 (void) fprintf(ftable, "\t};\n"); 118 wdef(L"YYNPROD", nprod); 119 #ifndef NOLIBW 120 if (nmbchars > 0) { 121 wrmbchars(); 122 } 123 #endif /* !NOLIBW */ 124 } 125 126 static int pkdebug = 0; 127 apack(p, n) 128 int *p; 129 { 130 /* pack state i from temp1 into amem */ 131 int off; 132 register *pp, *qq; 133 int *q, *r, *rr; 134 int diff; 135 136 /* 137 * we don't need to worry about checking because we 138 * we will only look up entries known to be there... 139 */ 140 141 /* eliminate leading and trailing 0's */ 142 143 q = p + n; 144 for (pp = p, off = 0; *pp == 0 && pp <= q; ++pp, --off) 145 /* EMPTY */; 146 if (pp > q) 147 return (0); /* no actions */ 148 p = pp; 149 150 /* now, find a place for the elements from p to q, inclusive */ 151 /* for( rr=amem; rr<=r; ++rr,++off ){ */ /* try rr */ 152 rr = amem; 153 for (; ; ++rr, ++off) { 154 while (rr >= &amem[new_actsize-1]) 155 exp_act(&rr); 156 qq = rr; 157 for (pp = p; pp <= q; ++pp, ++qq) { 158 if (*pp) { 159 diff = qq - rr; 160 while (qq >= &amem[new_actsize-1]) { 161 exp_act(&rr); 162 qq = diff + rr; 163 } 164 if (*pp != *qq && *qq != 0) 165 goto nextk; 166 } 167 } 168 169 /* we have found an acceptable k */ 170 171 if (pkdebug && foutput != NULL) 172 (void) fprintf(foutput, 173 "off = %d, k = %d\n", off, rr-amem); 174 175 qq = rr; 176 for (pp = p; pp <= q; ++pp, ++qq) { 177 if (*pp) { 178 diff = qq - rr; 179 while (qq >= &amem[new_actsize-1]) { 180 exp_act(&rr); 181 qq = diff + rr; 182 } 183 if (qq > memp) 184 memp = qq; 185 *qq = *pp; 186 } 187 } 188 if (pkdebug && foutput != NULL) { 189 for (pp = amem; pp <= memp; pp += 10) { 190 (void) fprintf(foutput, "\t"); 191 for (qq = pp; qq <= pp + 9; ++qq) 192 (void) fprintf(foutput, "%d ", *qq); 193 (void) fprintf(foutput, "\n"); 194 } 195 } 196 return (off); 197 nextk:; 198 } 199 /* error("no space in action table" ); */ 200 /* NOTREACHED */ 201 } 202 203 void 204 go2out() 205 { 206 /* output the gotos for the nontermninals */ 207 int i, j, k, best, count, cbest, times; 208 209 (void) fprintf(ftemp, "$\n"); /* mark begining of gotos */ 210 211 for (i = 1; i <= nnonter; ++i) { 212 go2gen(i); 213 /* find the best one to make default */ 214 best = -1; 215 times = 0; 216 for (j = 0; j < nstate; ++j) { /* is j the most frequent */ 217 if (tystate[j] == 0) 218 continue; 219 if (tystate[j] == best) 220 continue; 221 /* is tystate[j] the most frequent */ 222 count = 0; 223 cbest = tystate[j]; 224 for (k = j; k < nstate; ++k) 225 if (tystate[k] == cbest) 226 ++count; 227 if (count > times) { 228 best = cbest; 229 times = count; 230 } 231 } 232 233 /* best is now the default entry */ 234 zzgobest += (times-1); 235 for (j = 0; j < nstate; ++j) { 236 if (tystate[j] != 0 && tystate[j] != best) { 237 (void) fprintf(ftemp, "%d,%d,", j, tystate[j]); 238 zzgoent += 1; 239 } 240 } 241 242 /* now, the default */ 243 244 zzgoent += 1; 245 (void) fprintf(ftemp, "%d\n", best); 246 247 } 248 } 249 250 static int g2debug = 0; 251 static void go2gen(c) 252 { 253 /* output the gotos for nonterminal c */ 254 int i, work, cc; 255 ITEM *p, *q; 256 257 /* first, find nonterminals with gotos on c */ 258 aryfil(temp1, nnonter + 1, 0); 259 temp1[c] = 1; 260 261 work = 1; 262 while (work) { 263 work = 0; 264 PLOOP(0, i) { 265 if ((cc = prdptr[i][1] - NTBASE) >= 0) { 266 /* cc is a nonterminal */ 267 if (temp1[cc] != 0) { 268 /* 269 * cc has a goto on c 270 * thus, the left side of 271 * production i does too. 272 */ 273 cc = *prdptr[i] - NTBASE; 274 if (temp1[cc] == 0) { 275 work = 1; 276 temp1[cc] = 1; 277 } 278 } 279 } 280 } 281 } 282 283 /* now, we have temp1[c] = 1 if a goto on c in closure of cc */ 284 285 if (g2debug && foutput != NULL) { 286 (void) fprintf(foutput, "%ws: gotos on ", nontrst[c].name); 287 NTLOOP(i) if (temp1[i]) 288 (void) fprintf(foutput, "%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(r, t, 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 "\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(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(i) 431 { 432 /* writes state i */ 433 register 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, "\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 "\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, "\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 "\t%ws goto %d\n", 479 symnam(j0 + NTBASE), temp1[j1]); 480 } 481 } 482 483 static void 484 wdef(s, n) 485 wchar_t *s; 486 { 487 /* output a definition of s to the value n */ 488 (void) fprintf(ftable, "# define %ws %d\n", s, n); 489 } 490 491 void 492 warray(s, v, n) 493 wchar_t *s; 494 int *v, n; 495 { 496 register i; 497 (void) fprintf(ftable, "static YYCONST yytabelem %ws[]={\n", s); 498 for (i = 0; i < n; ) { 499 if (i % 10 == 0) 500 (void) fprintf(ftable, "\n"); 501 (void) fprintf(ftable, "%6d", v[i]); 502 if (++i == n) 503 (void) fprintf(ftable, " };\n"); 504 else 505 (void) fprintf(ftable, ","); 506 } 507 } 508 509 void 510 hideprod() 511 { 512 /* 513 * in order to free up the mem and amem arrays for the optimizer, 514 * and still be able to output yyr1, etc., after the sizes of 515 * the action array is known, we hide the nonterminals 516 * derived by productions in levprd. 517 */ 518 519 register i, j; 520 521 j = 0; 522 levprd[0] = 0; 523 PLOOP(1, i) { 524 if (!(levprd[i] & REDFLAG)) { 525 ++j; 526 if (foutput != NULL) { 527 (void) fprintf(foutput, 528 "Rule not reduced: %ws\n", 529 writem(prdptr[i])); 530 } 531 } 532 levprd[i] = *prdptr[i] - NTBASE; 533 } 534 if (j) 535 /* 536 * TRANSLATION_NOTE -- This is a message from yacc. 537 * Check how 'reduced' is translated in yacc man page/document. 538 */ 539 (void) fprintf(stderr, gettext( 540 "%d rules never reduced\n"), 541 j); 542 } 543 544 545 #ifndef NOLIBW 546 static int 547 cmpmbchars(p, q) 548 MBCLIT *p, *q; 549 { 550 /* Compare two MBLITs. */ 551 return ((p->character) - (q->character)); 552 } 553 554 static void 555 wrmbchars() 556 { 557 int i; 558 wdef(L"YYNMBCHARS", nmbchars); 559 qsort(mbchars, nmbchars, sizeof (*mbchars), 560 (int (*)(const void *, const void *))cmpmbchars); 561 (void) fprintf(ftable, 562 "static struct{\n\twchar_t character;" 563 "\n\tint tvalue;\n}yymbchars[YYNMBCHARS]={\n"); 564 for (i = 0; i < nmbchars; ++i) { 565 (void) fprintf(ftable, "\t{%#x,%d}", 566 mbchars[i].character, mbchars[i].tvalue); 567 if (i < nmbchars - 1) { 568 /* Not the last. */ 569 (void) fprintf(ftable, ",\n"); 570 } 571 } 572 (void) fprintf(ftable, "\n};\n"); 573 } 574 #endif /* !NOLIBW */ 575