usr/src/cmd/sgs/yacc/common/y4.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 #define NOMORE -1000
  33
  34 static void gin(int);
  35 static void stin(int);
  36 static void osummary(void);
  37 static void aoutput(void);
  38 static void arout(wchar_t *, int *, int);
  39 static int nxti(void);
  40 static int gtnm(void);
  41
  42 static int *ggreed;
  43 static int *pgo;
  44 static int *yypgo;
  45
  46 static int maxspr = 0;  /* maximum spread of any entry */
  47 static int maxoff = 0;  /* maximum offset into an array */
  48 int *optimmem;
  49 static int *maxa;
  50
  51 static int nxdb = 0;
  52 static int adb = 0;
  53
  54 void
  55 callopt()
  56 {
  57         int i, *p, j, k, *q;
  58
  59         ggreed = (int *) malloc(sizeof (int) * size);
  60         pgo = (int *) malloc(sizeof (int) * size);
  61         yypgo = &nontrst[0].tvalue;
  62
  63         /* read the arrays from tempfile and set parameters */
  64
  65         if ((finput = fopen(TEMPNAME, "r")) == NULL)
  66 /*
  67  * TRANSLATION_NOTE  -- This is a message from yacc.
  68  *      This message is passed to error() function.
  69  *      tempfile can be translated as temporary file.
  70  */
  71                 error(gettext(
  72                     "optimizer cannot open tempfile"));
  73
  74         optimmem = tracemem;
  75         pgo[0] = 0;
  76         temp1[0] = 0;
  77         nstate = 0;
  78         nnonter = 0;
  79         for (;;) {
  80                 switch (gtnm()) {
  81
  82                 case L'\n':
  83                         temp1[++nstate] = (--optimmem) - tracemem;
  84                         /* FALLTHRU */
  85
  86                 case L',':
  87                         continue;
  88
  89                 case L'$':
  90                         break;
  91
  92                 default:
  93                         error("bad tempfile");
  94                 }
  95                 break;
  96         }
  97
  98         temp1[nstate] = yypgo[0] = (--optimmem) - tracemem;
  99
 100         for (;;) {
 101                 switch (gtnm()) {
 102
 103                 case L'\n':
 104                         yypgo[++nnonter] = optimmem-tracemem;
 105                         /* FALLTHRU */
 106                 case L',':
 107                         continue;
 108
 109                 case EOF:
 110                         break;
 111
 112                 default:
 113 /*
 114  * TRANSLATION_NOTE  -- This is a message from yacc.
 115  *      This message is passed to error() function.
 116  *      tempfile can be translated as 'temporary file'.
 117  */
 118                         error(gettext(
 119                         "bad tempfile"));
 120                 }
 121                 break;
 122         }
 123
 124         yypgo[nnonter--] = (--optimmem) - tracemem;
 125
 126         for (i = 0; i < nstate; ++i) {
 127                 k = 32000000;
 128                 j = 0;
 129                 q = tracemem + temp1[i+1];
 130                 for (p = tracemem + temp1[i]; p < q; p += 2) {
 131                         if (*p > j)
 132                                 j = *p;
 133                         if (*p < k)
 134                                 k = *p;
 135                 }
 136                 if (k <= j) {
 137                         /*
 138                          * nontrivial situation
 139                          * temporarily, kill this for compatibility
 140                          */
 141                         /* j -= k;  j is now the range */
 142                         if (k > maxoff)
 143                                 maxoff = k;
 144                 }
 145                 tystate[i] = (temp1[i+1] - temp1[i]) + 2*j;
 146                 if (j > maxspr)
 147                         maxspr = j;
 148         }
 149
 150         /* initialize ggreed table */
 151         for (i = 1; i <= nnonter; ++i) {
 152                 ggreed[i] = 1;
 153                 j = 0;
 154                 /* minimum entry index is always 0 */
 155                 q = tracemem + yypgo[i+1] -1;
 156                 for (p = tracemem + yypgo[i]; p < q; p += 2) {
 157                         ggreed[i] += 2;
 158                         if (*p > j)
 159                                 j = *p;
 160                 }
 161                 ggreed[i] = ggreed[i] + 2*j;
 162                 if (j > maxoff)
 163                         maxoff = j;
 164         }
 165
 166         /* now, prepare to put the shift actions into the amem array */
 167         for (i = 0; i < new_actsize; ++i)
 168                 amem[i] = 0;
 169         maxa = amem;
 170
 171         for (i = 0; i < nstate; ++i) {
 172                 if (tystate[i] == 0 && adb > 1)
 173                         (void) fprintf(ftable, "State %d: null\n", i);
 174                 indgo[i] = YYFLAG1;
 175         }
 176
 177         while ((i = nxti()) != NOMORE) {
 178                 if (i >= 0)
 179                         stin(i);
 180                 else
 181                         gin(-i);
 182         }
 183
 184         if (adb > 2) { /* print a array */
 185                 for (p = amem; p <= maxa; p += 10) {
 186                         (void) fprintf(ftable, "%4" PRIdPTR "  ", p-amem);
 187                         for (i = 0; i < 10; ++i)
 188                                 (void) fprintf(ftable, "%4d  ", p[i]);
 189                         (void) fprintf(ftable, "\n");
 190                 }
 191         }
 192         /* write out the output appropriate to the language */
 193         aoutput();
 194         osummary();
 195         ZAPFILE(TEMPNAME);
 196 }
 197
 198 static void
 199 gin(int i)
 200 {
 201         int *r, *s, *q1, *q2;
 202         int *p;
 203
 204         /* enter gotos on nonterminal i into array amem */
 205         ggreed[i] = 0;
 206
 207         q2 = tracemem + yypgo[i+1] - 1;
 208         q1 = tracemem + yypgo[i];
 209
 210         /* now, find a place for it */
 211
 212         /* for( p=amem; p < &amem[new_actsize]; ++p ){ */
 213         p = amem;
 214         for (;;) {
 215                 while (p >= &amem[new_actsize])
 216                         exp_act(&p);
 217                 if (*p)
 218                         goto nextgp;
 219                 for (r = q1; r < q2; r += 2) {
 220                         s = p + *r + 1;
 221                         /*
 222                          * Check if action table needs to
 223                          * be expanded or not. If so,
 224                          * expand it.
 225                          */
 226                         while (s >= &amem[new_actsize]) {
 227                                 exp_act(&p);
 228                                 s = p + *r + 1;
 229                         }
 230                         if (*s)
 231                                 goto nextgp;
 232                         if (s > maxa) {
 233                                 while ((maxa = s) >= &amem[new_actsize])
 234                                         /* error( "amem array overflow" ); */
 235                                         exp_act(&p);
 236                         }
 237                 }
 238                 /* we have found a spot */
 239                 *p = *q2;
 240                 if (p > maxa) {
 241                         while ((maxa = p) >= &amem[new_actsize])
 242                                 /* error("amem array overflow"); */
 243                                 exp_act(&p);
 244                 }
 245                 for (r = q1; r < q2; r += 2) {
 246                         s = p + *r + 1;
 247                         /*
 248                          * Check if action table needs to
 249                          * be expanded or not. If so,
 250                          * expand it.
 251                          */
 252                         while (s >= &amem[new_actsize]) {
 253                                 exp_act(&p);
 254                                 s = p + *r + 1;
 255                         }
 256                         *s = r[1];
 257                 }
 258
 259                 pgo[i] = p - amem;
 260                 if (adb > 1)
 261                         (void) fprintf(ftable,
 262                             "Nonterminal %d, entry at %d\n", i, pgo[i]);
 263                 goto nextgi;
 264
 265                 nextgp:
 266                         ++p;
 267         }
 268         /* error( "cannot place goto %d\n", i ); */
 269         nextgi:;
 270 }
 271
 272 static void
 273 stin(int i)
 274 {
 275         int *r, n, nn, flag, j, *q1, *q2;
 276         int *s;
 277
 278         tystate[i] = 0;
 279
 280         /* Enter state i into the amem array */
 281
 282         q2 = tracemem + temp1[i + 1];
 283         q1 = tracemem + temp1[i];
 284         /* Find an acceptable place */
 285
 286         nn = -maxoff;
 287         more:
 288         for (n = nn; n < new_actsize; ++n) {
 289                 flag = 0;
 290                 for (r = q1; r < q2; r += 2) {
 291                         s = *r + n + amem;
 292                         if (s < amem)
 293                                 goto nextn;
 294                         /*
 295                          * Check if action table needs to
 296                          * be expanded or not. If so,
 297                          * expand it.
 298                          */
 299                         while (s >= &amem[new_actsize]) {
 300                                 exp_act((int **)NULL);
 301                                 s = *r + n + amem;
 302                         }
 303                         if (*s == 0)
 304                                 ++flag;
 305                         else if (*s != r[1])
 306                                 goto nextn;
 307                 }
 308
 309                 /*
 310                  * check that the position equals another
 311                  * only if the states are identical
 312                  */
 313                 for (j = 0; j < nstate; ++j) {
 314                         if (indgo[j] == n) {
 315                                 if (flag)
 316                                         /*
 317                                          * we have some disagreement.
 318                                          */
 319                                         goto nextn;
 320                                 if (temp1[j+1] + temp1[i] ==
 321                                     temp1[j] + temp1[i+1]) {
 322                                         /* states are equal */
 323                                         indgo[i] = n;
 324                                         if (adb > 1)
 325                                                 (void) fprintf(ftable,
 326                                                     "State %d: entry at"
 327                                                     " %d equals state %d\n",
 328                                                     i, n, j);
 329                                         return;
 330                                 }
 331                                 goto nextn;  /* we have some disagreement */
 332                         }
 333                 }
 334
 335                 for (r = q1; r < q2; r += 2) {
 336                         while ((s = *r + n + amem) >= &amem[new_actsize]) {
 337                                 /*
 338                                  * error( "out of space");
 339                                  */
 340                                 exp_act((int **)NULL);
 341                         }
 342                         if (s > maxa)
 343                                 maxa = s;
 344                         if (*s != 0 && *s != r[1])
 345 /*
 346  * TRANSLATION_NOTE  -- This is a message from yacc.
 347  *      This message is passed to error() function.
 348  *      Leave this untrasnlated. Yacc internal error.
 349  */
 350                                 error(gettext(
 351                                     "clobber of amem array, pos'n %d, by %d"),
 352                                     s-amem, r[1]);
 353                         *s = r[1];
 354                 }
 355                 indgo[i] = n;
 356                 if (adb > 1)
 357                         (void) fprintf(ftable,
 358                             "State %d: entry at %d\n", i, indgo[i]);
 359                 return;
 360                 nextn:;
 361         }
 362
 363         /* error( "Error; failure to place state %d\n", i ); */
 364         exp_act((int **)NULL);
 365         nn = new_actsize - ACTSIZE;
 366         goto more;
 367         /* NOTREACHED */
 368 }
 369
 370 static int
 371 nxti()
 372 {
 373         /* finds the next i */
 374         int i, max, maxi;
 375         max = 0;
 376
 377         for (i = 1; i <= nnonter; ++i)
 378                 if (ggreed[i] >= max) {
 379                 max = ggreed[i];
 380                 maxi = -i;
 381                 }
 382
 383         for (i = 0; i < nstate; ++i)
 384                 if (tystate[i] >= max) {
 385                         max = tystate[i];
 386                         maxi = i;
 387                 }
 388         if (nxdb)
 389                 (void) fprintf(ftable, "nxti = %d, max = %d\n", maxi, max);
 390         if (max == 0)
 391                 return (NOMORE);
 392         else
 393                 return (maxi);
 394 }
 395
 396 static void
 397 osummary()
 398 {
 399         /* write summary */
 400         int i, *p;
 401
 402         if (foutput == NULL)
 403                 return;
 404         i = 0;
 405         for (p = maxa; p >= amem; --p) {
 406                 if (*p == 0)
 407                         ++i;
 408         }
 409
 410         (void) fprintf(foutput,
 411             "Optimizer space used: input %" PRIdPTR
 412             "/%d, output %" PRIdPTR "/%d\n",
 413             optimmem-tracemem + 1, new_memsize, maxa-amem + 1, new_actsize);
 414         (void) fprintf(foutput,
 415             "%" PRIdPTR " table entries, %d zero\n", (maxa-amem) + 1, i);
 416         (void) fprintf(foutput,
 417             "maximum spread: %d, maximum offset: %d\n", maxspr, maxoff);
 418
 419 }
 420
 421 static void
 422 aoutput()
 423 {
 424         /* this version is for C */
 425         /* write out the optimized parser */
 426
 427         (void) fprintf(ftable, "# define YYLAST %" PRIdPTR "\n", maxa-amem + 1);
 428         arout(L"yyact", amem, (maxa - amem) + 1);
 429         arout(L"yypact", indgo, nstate);
 430         arout(L"yypgo", pgo, nnonter + 1);
 431 }
 432
 433 static void
 434 arout(s, v, n)
 435 wchar_t *s;
 436 int *v, n;
 437 {
 438         int i;
 439
 440         (void) fprintf(ftable, WSFMT("static YYCONST yytabelem %ws[]={\n"), s);
 441         for (i = 0; i < n; ) {
 442                 if (i % 10 == 0)
 443                         (void) fprintf(ftable, "\n");
 444                 (void) fprintf(ftable, "%6d", v[i]);
 445                 if (++i == n)
 446                         (void) fprintf(ftable, " };\n");
 447                 else
 448                         (void) fprintf(ftable, ",");
 449         }
 450 }
 451
 452 static int
 453 gtnm()
 454 {
 455         int s, val, c;
 456
 457         /* read and convert an integer from the standard input */
 458         /* return the terminating character */
 459         /* blanks, tabs, and newlines are ignored */
 460
 461         s = 1;
 462         val = 0;
 463
 464         while ((c = getwc(finput)) != EOF) {
 465                 if (iswdigit(c))
 466                         val = val * 10 + c - L'0';
 467                 else if (c == L'-')
 468                         s = -1;
 469                 else
 470                         break;
 471         }
 472         *optimmem++ = s*val;
 473         if (optimmem >= &tracemem[new_memsize])
 474                 exp_mem(0);
 475         return (c);
 476 }
 477
 478 void
 479 exp_act(ptr)
 480 int **ptr;
 481 {
 482         static int *actbase;
 483         int i;
 484         new_actsize += ACTSIZE;
 485
 486         actbase = amem;
 487         amem = (int *) realloc((char *)amem, sizeof (int) * new_actsize);
 488         if (amem == NULL)
 489 /*
 490  * TRANSLATION_NOTE  -- This is a message from yacc.
 491  *      This message is passed to error() function.
 492  *
 493  *      You may just translate this as:
 494  *      'Could not allocate internally used memory.'
 495  */
 496                 error(gettext(
 497                 "couldn't expand action table"));
 498
 499         for (i = new_actsize-ACTSIZE; i < new_actsize; ++i)
 500                 amem[i] = 0;
 501         if (ptr != NULL)
 502                 *ptr = *ptr - actbase + amem;
 503         if (memp >= amem)
 504                 memp = memp - actbase + amem;
 505         if (maxa >= amem)
 506                 maxa = maxa - actbase + amem;
 507 }