usr/src/cmd/sgs/yacc/common/y3.c

   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 }