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