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