usr/src/cmd/sgs/yacc/common/y1.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 #include <sys/param.h>
  33 #include <sys/errno.h>
  34 #include <unistd.h>
  35 #include <locale.h>
  36 #include <stdarg.h>     /* For error() */
  37
  38 static void mktbls(void);
  39 static void others(void);
  40 static void summary(void);
  41 static wchar_t *chcopy(wchar_t *, wchar_t *);
  42 static int setunion(int *, int *);
  43 static void prlook(LOOKSETS *);
  44 static void cpres(void);
  45 static void cpfir(void);
  46 static void cempty(void);
  47 static void stagen(void);
  48 static LOOKSETS *flset(LOOKSETS *);
  49 static void exp_lkst(void);
  50 static void exp_wsets(void);
  51 static void exp_states(void);
  52 static void exp_psmem(void);
  53
  54         /* lookahead computations */
  55
  56 int TBITSET;
  57 static int tbitset;     /* size of lookahead sets */
  58 LOOKSETS *lkst;
  59 static int lsetsize;
  60
  61 static int nlset = 0;   /* next lookahead set index */
  62 int nolook = 0;         /* flag to suppress lookahead computations */
  63 static LOOKSETS clset;  /* temporary storage for lookahead computations */
  64
  65 static ITEM *psmem, *zzmemsz;
  66 static int new_pstsize = PSTSIZE;
  67
  68         /* working set computations */
  69
  70 WSET *wsets;
  71 int cwp;
  72 static int wsetsz = 0;          /* number of WSET items in wsets block */
  73
  74         /* state information */
  75
  76 int nstate = 0;                 /* number of states */
  77 static int nstatesz = NSTATES;  /* number of state space allocated      */
  78 ITEM **pstate;                  /* ptr to descriptions of the states    */
  79 int *tystate;                   /* contains type info about the states  */
  80 int *indgo;                     /* index to the stored goto table       */
  81 static int *tmp_lset;
  82 static int *tstates;            /* states generated by terminal gotos   */
  83 static int *ntstates;           /* states generated by non-term gotos   */
  84 static int *mstates;            /* chain of overflows of term/nonterm   */
  85                                 /* generation lists                     */
  86
  87         /* storage for the actions in the parser */
  88
  89 int *amem, *memp;               /* next free action table position */
  90 int new_actsize = ACTSIZE;
  91
  92         /* other storage areas */
  93
  94 int *temp1;             /* temp storate, indexed by terms+ntokens or states */
  95 int lineno = 0;         /* current input line number */
  96 int size;
  97 static int fatfl = 1;   /* if on, error is fatal */
  98 static int nerrors = 0; /* number of errors */
  99
 100         /* storage for information about the nonterminals */
 101
 102 static int ***pres;             /* vector of pointers to productions    */
 103                                 /* yielding each nonterminal            */
 104 static LOOKSETS **pfirst;       /* vector of pointers to first sets for */
 105                                 /* each nonterminal                     */
 106 static int *pempty;             /* vector of nonterminals nontrivially  */
 107                                 /* deriving e                           */
 108 extern int nprodsz;
 109
 110 int
 111 main(int argc, char *argv[])
 112 {
 113         (void) setlocale(LC_ALL, "");
 114 #if !defined(TEXT_DOMAIN)       /* Should be defined by cc -D */
 115 #define TEXT_DOMAIN "SYS_TEST"  /* Use this only if it weren't */
 116 #endif
 117         (void) textdomain(TEXT_DOMAIN);
 118
 119         setup(argc, argv);              /* initialize and read productions */
 120         TBITSET = NWORDS(ntoksz*LKFACTOR);
 121         tbitset = NWORDS(ntokens*LKFACTOR);
 122         mktbls();
 123         cpres();        /* make table of which productions yield a */
 124                         /* given nonterminal */
 125         cempty();       /* make a table of which nonterminals can match */
 126                         /* the empty string */
 127         cpfir();        /* make a table of firsts of nonterminals */
 128         stagen();       /* generate the states  */
 129         output();       /* write the states and the tables */
 130         go2out();
 131         hideprod();
 132         summary();
 133         callopt();
 134         others();
 135         return (0);
 136 }
 137
 138
 139 static void
 140 mktbls()
 141 {
 142         int i;
 143
 144         size = ntoksz + nnontersz +1;
 145         if (size < nstatesz)
 146                 size = nstatesz;
 147         if (size < new_memsize)
 148                 size = new_memsize;
 149
 150         amem = (int *) malloc(sizeof (int) * new_actsize);
 151         psmem = (ITEM *) malloc(sizeof (ITEM) * new_pstsize);
 152         if ((psmem == NULL) || (amem == NULL))
 153 /*
 154  * TRANSLATION_NOTE  -- This is a message from yacc.
 155  *      This message is passed to error() function.
 156  *      This error happens when yacc could not allocate
 157  *      initial memory to be used for internal tables.
 158  *
 159  *      You may just translate this as:
 160  *      'Could not allocate internally used memory.'
 161  */
 162                 error(gettext(
 163                 "couldn't allocate initial table"));
 164         zzmemsz = psmem;
 165         memp = amem;
 166
 167         /*
 168          * For lkst
 169          */
 170 #define INIT_LSIZE      nnontersz*LKFACTOR
 171         tmp_lset = (int *)
 172             calloc((size_t)(TBITSET * (INIT_LSIZE+1)), sizeof (int));
 173         if (tmp_lset == NULL)
 174 /*
 175  * TRANSLATION_NOTE  -- This is a message from yacc.
 176  *      This message is passed to error() function.
 177  *      Yacc could not allocate memory for table named lookset.
 178  *      Do not translate 'lookset'.
 179  *
 180  *      You may just translate this as:
 181  *      'Could not allocate internally used memory.'
 182  */
 183                 error(gettext(
 184                 "could not allocate lookset array"));
 185         lkst = (LOOKSETS *) malloc(sizeof (LOOKSETS) * (INIT_LSIZE + 1));
 186         for (i = 0; i <= INIT_LSIZE; ++i)
 187                 lkst[i].lset = tmp_lset + TBITSET * i;
 188         tmp_lset = NULL;
 189
 190         /*
 191          * For wsets
 192          */
 193         tmp_lset = (int *)
 194             calloc((size_t)(TBITSET * (nnontersz+1)), sizeof (int));
 195         if (tmp_lset == NULL)
 196                 error(gettext(
 197                 "could not allocate lookset array"));
 198         wsets = (WSET *) malloc(sizeof (WSET) * (nnontersz + 1));
 199         for (i = 0; i <= nnontersz; ++i)
 200                 wsets[i].ws.lset = tmp_lset + TBITSET * i;
 201         tmp_lset = NULL;
 202
 203         clset.lset = (int *)malloc(sizeof (int)*TBITSET);
 204         tstates = (int *)malloc(sizeof (int)*(ntoksz + 1));
 205         ntstates = (int *)malloc(sizeof (int)*(nnontersz + 1));
 206         temp1 = (int *)malloc(sizeof (int)*size);
 207         pres = (int ***)malloc(sizeof (int **)*(nnontersz + 2));
 208         pfirst = (LOOKSETS **)malloc(sizeof (LOOKSETS *)*(nnontersz + 2));
 209         pempty = (int *)malloc(sizeof (int)*(nnontersz + 1));
 210
 211         pstate = (ITEM **)malloc(sizeof (ITEM *)*(nstatesz+2));
 212         tystate = (int *)malloc(sizeof (int)*nstatesz);
 213         indgo = (int *)malloc(sizeof (int)*nstatesz);
 214         mstates = (int *)malloc(sizeof (int)*nstatesz);
 215         defact = (int *)malloc(sizeof (int)*nstatesz);
 216
 217         if ((lkst == NULL) || (wsets == NULL) || (tstates == NULL) ||
 218             (ntstates == NULL) || (temp1 == NULL) || (pres == NULL) ||
 219             (pfirst == NULL) || (pempty == NULL) || (pstate == NULL) ||
 220             (tystate == NULL) || (indgo == NULL) || (mstates == NULL) ||
 221             (defact == NULL) || (clset.lset == NULL))
 222 /*
 223  * TRANSLATION_NOTE  -- This is a message from yacc.
 224  *      This message is passed to error() function.
 225  *      Do not translate mktbls(). It is a function name.
 226  *
 227  *      You may just translate this as:
 228  *      'Could not allocate internally used memory.'
 229  */
 230                         error(gettext(
 231                         "cannot allocate tables in mktbls()"));
 232
 233         aryfil(ntstates, nnontersz+1, 0);
 234         aryfil(tstates, ntoksz+1, 0);
 235         wsetsz = nnontersz + 1;
 236         lsetsize = INIT_LSIZE + 1;
 237 }
 238
 239 /* put out other arrays, copy the parsers */
 240 static void
 241 others()
 242 {
 243         extern int gen_lines;
 244         int c, i, j;
 245         int tmpline;
 246
 247         finput = fopen(parser, "r");
 248         if (finput == NULL)
 249 /*
 250  * TRANSLATION_NOTE  -- This is a message from yacc.
 251  *      This message is passed to error() function.
 252  *      This error message is issued when yacc can not find
 253  *      the parser to be copied.
 254  */
 255                 error(gettext(
 256                 "cannot find parser %s"),
 257                     parser);
 258
 259         warray(L"yyr1", levprd, nprod);
 260
 261         aryfil(temp1, nprod, 0);
 262                                         /* had_act[i] is either 1 or 0 */
 263         PLOOP(1, i)
 264                 temp1[i] = ((prdptr[i+1] - prdptr[i]-2) << 1) | had_act[i];
 265         warray(L"yyr2", temp1, nprod);
 266
 267         aryfil(temp1, nstate, -10000000);
 268         TLOOP(i)
 269                 for (j = tstates[i]; j != 0; j = mstates[j])
 270                         temp1[j] = tokset[i].value;
 271         NTLOOP(i)
 272                 for (j = ntstates[i]; j != 0; j = mstates[j])
 273                         temp1[j] = -i;
 274         warray(L"yychk", temp1, nstate);
 275
 276         warray(L"yydef", defact, nstate);
 277
 278         if ((fdebug = fopen(DEBUGNAME, "r")) == NULL)
 279                 error("cannot open yacc.debug");
 280         while ((c = getwc(fdebug)) != EOF)
 281                 (void) putwc(c, ftable);
 282         (void) fclose(fdebug);
 283         ZAPFILE(DEBUGNAME);
 284
 285         if (gen_lines)
 286                 (void) fprintf(ftable, "# line\t1 \"%s\"\n", parser);
 287         tmpline = 1;
 288         /* copy parser text */
 289         while ((c = getwc(finput)) != EOF) {
 290                 if (c == '\n')
 291                         tmpline++;
 292                 if (c == L'$') {
 293                         if ((c = getwc(finput)) != L'A')
 294                                 (void) putwc(L'$', ftable);
 295                         else { /* copy actions */
 296                                 tmpline++;
 297                                 faction = fopen(ACTNAME, "r");
 298                                 if (faction == NULL)
 299 /*
 300  * TRANSLATION_NOTE  -- This is a message from yacc.
 301  *      This message is passed to error() function.
 302  *      This error is issued when yacc can not open a
 303  *      temporary file to be used. You do not need to
 304  *      use the word 'tempfile'. You can translate it to
 305  *      mean 'temporary file'.
 306  */
 307                                         error(gettext(
 308                                         "cannot open action tempfile"));
 309                                 while ((c = getwc(faction)) != EOF)
 310                                         (void) putwc(c, ftable);
 311                                 (void) fclose(faction);
 312                                 if (gen_lines)
 313                                         (void) fprintf(ftable,
 314                                             "\n# line\t%d \"%s\"",
 315                                             tmpline,
 316                                             parser);
 317                                 ZAPFILE(ACTNAME);
 318                                 c = getwc(finput);
 319                         }
 320                 }
 321                 (void) putwc(c, ftable);
 322         }
 323         (void) fclose(ftable);
 324 }
 325
 326
 327 /* copies string q into p, returning next free char ptr */
 328 static wchar_t *
 329 chcopy(p, q)
 330 wchar_t *p, *q;
 331 {
 332         while (*p = *q++)
 333                 ++p;
 334         return (p);
 335 }
 336
 337 #define ISIZE 400
 338 /* creates output string for item pointed to by pp */
 339 wchar_t *
 340 writem(pp)
 341 int *pp;
 342 {
 343         int i, *p;
 344         static int isize = ISIZE;
 345         static wchar_t *sarr = NULL;
 346         wchar_t *q;
 347
 348         if (sarr == NULL) {
 349                 sarr = (wchar_t *)malloc(sizeof (wchar_t) * isize);
 350                 if (sarr == NULL)
 351 /*
 352  * TRANSLATION_NOTE  -- This is a message from yacc.
 353  *      This message is passed to error() function.
 354  *      This error is issued when yacc could not allocate
 355  *      memory for internally used array.
 356  *
 357  *      You may just translate this as:
 358  *      'Could not allocate internally used memory.'
 359  */
 360                         error(gettext(
 361                         "could not allocate output string array"));
 362                 for (i = 0; i < isize; ++i)
 363                         sarr[i] = L' ';
 364         }
 365         for (p = pp; *p > 0; ++p) /* NULL */;
 366         p = prdptr[-*p];
 367         q = chcopy(sarr, nontrst[*p-NTBASE].name);
 368         q = chcopy(q, L" : ");
 369
 370         for (;;) {
 371                 *q++ = ++p == pp ? L'_' : L' ';
 372                 *q = 0;
 373                 if ((i = *p) <= 0)
 374                         break;
 375                 q = chcopy(q, symnam(i));
 376                 while (q > &sarr[isize-30]) {
 377                         static wchar_t *sarrbase;
 378
 379                         sarrbase = sarr;
 380                         isize += ISIZE;
 381                         sarr = (wchar_t *)
 382                                 realloc((char *)sarr, sizeof (*sarr) * isize);
 383                         if (sarr == NULL)
 384 /*
 385  * TRANSLATION_NOTE  -- This is a message from yacc.
 386  *      This message is passed to error() function.
 387  *      This error is issued when yacc could not allocate
 388  *      memory for internally used array.
 389  *
 390  *      You may just translate this as:
 391  *      'Could not allocate internally used memory.'
 392  */
 393                                 error(gettext(
 394                                 "cannot expand sarr arrays"));
 395                         q = q - sarrbase + sarr;
 396                 }
 397         }
 398
 399         /* an item calling for a reduction */
 400         if ((i = *pp) < 0) {
 401                 q = chcopy(q, L"    (");
 402                 (void) wsprintf(q, "%d)", -i);
 403         }
 404         return (sarr);
 405 }
 406
 407 /* return a pointer to the name of symbol i */
 408 wchar_t *
 409 symnam(int i)
 410 {
 411         wchar_t *cp;
 412
 413         cp = (i >= NTBASE) ? nontrst[i-NTBASE].name : tokset[i].name;
 414         if (*cp == L' ')
 415                 ++cp;
 416         return (cp);
 417 }
 418
 419 static int zzcwp = 0;
 420 static int zzclose = 0;
 421 int zzgoent = 0;
 422 int zzgobest = 0;
 423 int zzacent = 0;
 424 int zzexcp = 0;
 425 int zzsrconf = 0;
 426 int zzrrconf = 0;
 427
 428 /* output the summary on the tty */
 429 static void
 430 summary()
 431 {
 432         if (foutput != NULL) {
 433                 (void) fprintf(foutput,
 434                     "\n%d/%d terminals, %d/%d nonterminals\n",
 435                     ntokens, ntoksz, nnonter, nnontersz);
 436                 (void) fprintf(foutput,
 437                     "%d/%d grammar rules, %d/%d states\n",
 438                     nprod, nprodsz, nstate, nstatesz);
 439                 (void) fprintf(foutput,
 440                 "%d shift/reduce, %d reduce/reduce conflicts reported\n",
 441                     zzsrconf, zzrrconf);
 442                 (void) fprintf(foutput,
 443                     "%d/%d working sets used\n", zzcwp, wsetsz);
 444                 (void) fprintf(foutput,
 445                     "memory: states,etc. %" PRIdPTR
 446                     "/%d, parser %" PRIdPTR "/%d\n",
 447                     mem-tracemem, new_memsize,
 448                     memp-amem, new_actsize);
 449                 (void) fprintf(foutput,
 450                     "%d/%d distinct lookahead sets\n", nlset, lsetsize);
 451                 (void) fprintf(foutput,
 452                     "%d extra closures\n", zzclose - 2*nstate);
 453                 (void) fprintf(foutput,
 454                     "%d shift entries, %d exceptions\n", zzacent, zzexcp);
 455                 (void) fprintf(foutput,
 456                     "%d goto entries\n", zzgoent);
 457                 (void) fprintf(foutput,
 458                     "%d entries saved by goto default\n", zzgobest);
 459         }
 460         if (zzsrconf != 0 || zzrrconf != 0) {
 461 /*
 462  * TRANSLATION_NOTE  -- This is a message from yacc.
 463  *      You may just leave this message un-translated.
 464  *      This message only makes sense to those who knows
 465  *      how yacc works, and the person should know what
 466  *      this message means in English.
 467  */
 468                 (void) fprintf(stderr, gettext(
 469                     "\nconflicts: "));
 470                 if (zzsrconf)
 471                         (void) fprintf(stderr, "%d shift/reduce", zzsrconf);
 472                 if (zzsrconf && zzrrconf)
 473                         (void) fprintf(stderr, ", ");
 474                 if (zzrrconf)
 475                         (void) fprintf(stderr, "%d reduce/reduce", zzrrconf);
 476                 (void) fprintf(stderr, "\n");
 477         }
 478
 479         if (ftemp != NULL)
 480                 (void) fclose(ftemp);
 481         if (fdefine != NULL)
 482                 (void) fclose(fdefine);
 483 }
 484
 485 /* write out error comment */
 486 /*PRINTFLIKE1*/
 487 void
 488 error(char *s, ...)
 489 {
 490         extern char *infile;
 491         va_list ap;
 492
 493         va_start(ap, s);
 494
 495         ++nerrors;
 496         if (!lineno)
 497 /*
 498  * TRANSLATION_NOTE  -- This is a message from yacc.
 499  *      This message is a prefix to the error messages
 500  *      passed to error() function.
 501  */
 502                 (void) fprintf(stderr, gettext(
 503                     "command line: fatal: "));
 504         else {
 505                 (void) fprintf(stderr, "\"%s\", ", infile);
 506 /*
 507  * TRANSLATION_NOTE  -- This is a message from yacc.
 508  *      This message is a prefix to the error messages
 509  *      passed to error() function.
 510  */
 511                 (void) fprintf(stderr, gettext(
 512                     "line %d: fatal: "),
 513                     lineno);
 514         }
 515         (void) vfprintf(stderr, s, ap);
 516         (void) fprintf(stderr, "\n");
 517         va_end(ap);
 518         if (!fatfl)
 519                 return;
 520         summary();
 521         exit(1);
 522 }
 523
 524 /*
 525  * Print out a warning message.
 526  */
 527 /*PRINTFLIKE2*/
 528 void
 529 warning(int flag, char *s, ...)
 530 {
 531         extern char *infile;
 532         va_list ap;
 533         va_start(ap, s);
 534
 535         (void) fprintf(stderr, "\"%s\", ", infile);
 536         /*
 537          * If flag, print lineno as well.
 538          */
 539         if (flag == 0)
 540 /*
 541  * TRANSLATION_NOTE  -- This is a message from yacc.
 542  *      This message is a prefix to the warning messages
 543  *      passed to warning() function.
 544  */
 545                 (void) fprintf(stderr, gettext(
 546                     "warning: "));
 547         else
 548 /*
 549  * TRANSLATION_NOTE  -- This is a message from yacc.
 550  *      This message is a prefix to the warning messages
 551  *      passed to warning() function.
 552  */
 553                 (void) fprintf(stderr, gettext(
 554                     "line %d: warning: "),
 555                     lineno);
 556         (void) vfprintf(stderr, s, ap);
 557         (void) fprintf(stderr, "\n");
 558         va_end(ap);
 559 }
 560
 561 /* set elements 0 through n-1 to c */
 562 void
 563 aryfil(v, n, c)
 564 int *v, n, c;
 565 {
 566         int i;
 567         for (i = 0; i < n; ++i)
 568                 v[i] = c;
 569 }
 570
 571 /* set a to the union of a and b */
 572 /* return 1 if b is not a subset of a, 0 otherwise */
 573 static int
 574 setunion(a, b)
 575 int *a, *b;
 576 {
 577         int i, x, sub;
 578
 579         sub = 0;
 580         SETLOOP(i) {
 581                 *a = (x = *a) | *b++;
 582                 if (*a++ != x)
 583                         sub = 1;
 584         }
 585         return (sub);
 586 }
 587
 588 static void
 589 prlook(p)
 590 LOOKSETS *p;
 591 {
 592         int j, *pp;
 593         pp = p->lset;
 594         if (pp == 0)
 595                 (void) fprintf(foutput, "\tNULL");
 596         else {
 597                 (void) fprintf(foutput, " { ");
 598                 TLOOP(j) {
 599                         if (BIT(pp, j))
 600                                 (void) fprintf(foutput,  WSFMT("%ws "),
 601                                     symnam(j));
 602                 }
 603                 (void) fprintf(foutput,  "}");
 604         }
 605 }
 606
 607 /*
 608  * compute an array with the beginnings of  productions yielding
 609  * given nonterminals
 610  * The array pres points to these lists
 611  * the array pyield has the lists: the total size is only NPROD+1
 612  */
 613 static void
 614 cpres()
 615 {
 616         int **ptrpy;
 617         int **pyield;
 618         int c, j, i;
 619
 620         /*
 621          * 2/29/88 -
 622          * nprodsz is the size of the tables describing the productions.
 623          * Normally this will be NPROD unless the production tables have
 624          * been expanded, in which case the tables will be NPROD * N(where
 625          * N is the number of times the tables had to be expanded.)
 626          */
 627         if ((pyield = (int **) malloc(sizeof (int *) * nprodsz)) == NULL)
 628 /*
 629  * TRANSLATION_NOTE  -- This is a message from yacc.
 630  *      This message is passed to error() function.
 631  *      This error is issued when yacc could not allocate
 632  *      memory for internally used array.
 633  *
 634  *      pyield is name of an array. You should not try to translate
 635  *      this word.
 636  *
 637  *      You may just translate this as:
 638  *      'Could not allocate internally used memory.'
 639  */
 640                 error(gettext(
 641                 "cannot allocate space for pyield array"));
 642
 643         ptrpy = pyield;
 644
 645         NTLOOP(i) {
 646                 c = i+NTBASE;
 647                 pres[i] = ptrpy;
 648                 fatfl = 0;  /* make undefined  symbols  nonfatal */
 649                 PLOOP(0, j) {
 650                         if (*prdptr[j] == c)    /* linear search for all c's */
 651                                 *ptrpy++ =  prdptr[j] + 1;
 652                 }
 653                 if (pres[i] == ptrpy) {                 /* c not found */
 654 /*
 655  * TRANSLATION_NOTE  -- This is a message from yacc.
 656  *      This message is passed to error() function.
 657  *      Ask somebody who knows yacc how to translate nonterminal or
 658  *      look at translated yacc document.
 659  */
 660                         error(gettext(
 661                         "undefined nonterminal: %ws"),
 662                             nontrst[i].name);
 663                 }
 664         }
 665         pres[i] = ptrpy;
 666         fatfl = 1;
 667         if (nerrors) {
 668                 summary();
 669                 exit(1);
 670         }
 671         if (ptrpy != &pyield[nprod])
 672 /*
 673  * TRANSLATION_NOTE  -- This is a message from yacc.
 674  *      This message is passed to error() function.
 675  *      This is an internal error message.
 676  *      Very little use to user. You may leave it
 677  *      un-translated.
 678  *
 679  *      pyied is name of an array. Do not translate it.
 680  */
 681                 error(gettext(
 682                 "internal Yacc error: pyield %d"),
 683                     ptrpy-&pyield[nprod]);
 684 }
 685
 686 static int indebug = 0;
 687 /* compute an array with the first of nonterminals */
 688 static void
 689 cpfir()
 690 {
 691         int *p, **s, i, **t, ch, changes;
 692
 693         zzcwp = nnonter;
 694         NTLOOP(i) {
 695                 aryfil(wsets[i].ws.lset, tbitset, 0);
 696                 t = pres[i+1];
 697                 /* initially fill the sets */
 698                 for (s = pres[i]; s < t; ++s) {
 699                         /* check if ch is non-terminal */
 700                         for (p = *s; (ch = *p) > 0; ++p) {
 701                                 if (ch < NTBASE) {      /* should be token */
 702                                         SETBIT(wsets[i].ws.lset, ch);
 703                                         break;
 704                                 } else if (!pempty[ch-NTBASE])
 705                                         break;
 706                         }
 707                 }
 708         }
 709
 710         /* now, reflect transitivity */
 711
 712         changes = 1;
 713         while (changes) {
 714                 changes = 0;
 715                 NTLOOP(i) {
 716                         t = pres[i+1];
 717                         for (s = pres[i]; s < t; ++s) {
 718                                 for (p = *s; (ch = (*p-NTBASE)) >= 0; ++p) {
 719                                         changes |= setunion(wsets[i].ws.lset,
 720                                             wsets[ch].ws.lset);
 721                                         if (!pempty[ch])
 722                                                 break;
 723                                 }
 724                         }
 725                 }
 726         }
 727
 728         NTLOOP(i)
 729                 pfirst[i] = flset(&wsets[i].ws);
 730         if (!indebug)
 731                 return;
 732         if ((foutput != NULL)) {
 733                 NTLOOP(i) {
 734                         (void) fprintf(foutput, WSFMT("\n%ws: "),
 735                             nontrst[i].name);
 736                         prlook(pfirst[i]);
 737                         (void) fprintf(foutput, " %d\n", pempty[i]);
 738                 }
 739         }
 740 }
 741
 742 /* sorts last state,and sees if it equals earlier ones. returns state number */
 743 int
 744 state(int c)
 745 {
 746         int size1, size2;
 747         int i;
 748         ITEM *p1, *p2, *k, *l, *q1, *q2;
 749         p1 = pstate[nstate];
 750         p2 = pstate[nstate+1];
 751         if (p1 == p2)
 752                 return (0); /* null state */
 753         /* sort the items */
 754         for (k = p2 - 1; k > p1; k--) { /* make k the biggest */
 755                 for (l = k-1; l >= p1; --l)
 756                         if (l->pitem > k->pitem) {
 757                                 int *s;
 758                                 LOOKSETS *ss;
 759                                 s = k->pitem;
 760                                 k->pitem = l->pitem;
 761                                 l->pitem = s;
 762                                 ss = k->look;
 763                                 k->look = l->look;
 764                                 l->look = ss;
 765                         }
 766         }
 767         size1 = p2 - p1; /* size of state */
 768
 769         for (i = (c >= NTBASE) ? ntstates[c-NTBASE] : tstates[c];
 770             i != 0; i = mstates[i]) {
 771                 /* get ith state */
 772                 q1 = pstate[i];
 773                 q2 = pstate[i+1];
 774                 size2 = q2 - q1;
 775                 if (size1 != size2)
 776                         continue;
 777                 k = p1;
 778                 for (l = q1; l < q2; l++) {
 779                         if (l->pitem != k->pitem)
 780                                 break;
 781                         ++k;
 782                 }
 783                 if (l != q2)
 784                         continue;
 785                 /* found it */
 786                 pstate[nstate+1] = pstate[nstate]; /* delete last state */
 787                 /* fix up lookaheads */
 788                 if (nolook)
 789                         return (i);
 790                 for (l = q1, k = p1; l < q2; ++l, ++k) {
 791                         int s;
 792                         SETLOOP(s)
 793                                 clset.lset[s] = l->look->lset[s];
 794                         if (setunion(clset.lset, k->look->lset)) {
 795                                 tystate[i] = MUSTDO;
 796                                 /* register the new set */
 797                                 l->look = flset(&clset);
 798                         }
 799                 }
 800                 return (i);
 801         }
 802         /* state is new */
 803         if (nolook)
 804 /*
 805  * TRANSLATION_NOTE  -- This is a message from yacc.
 806  *      This message is passed to error() function.
 807  *      You may leave this untranslated. Leave
 808  *      state/nolook un-translated.
 809  */
 810                 error(gettext(
 811                 "yacc state/nolook error"));
 812         pstate[nstate+2] = p2;
 813         if (nstate+1 >= nstatesz)
 814                 exp_states();
 815         if (c >= NTBASE) {
 816                 mstates[nstate] = ntstates[c - NTBASE];
 817                 ntstates[c - NTBASE] = nstate;
 818         } else {
 819                 mstates[nstate] = tstates[c];
 820                 tstates[c] = nstate;
 821         }
 822         tystate[nstate] = MUSTDO;
 823         return (nstate++);
 824 }
 825
 826 static int pidebug = 0;
 827
 828 void
 829 putitem(ptr, lptr)
 830 int *ptr;
 831 LOOKSETS *lptr;
 832 {
 833         register ITEM *j;
 834
 835         if (pidebug && (foutput != NULL))
 836                 (void) fprintf(foutput,
 837                         WSFMT("putitem(%ws), state %d\n"), writem(ptr), nstate);
 838         j = pstate[nstate+1];
 839         j->pitem = ptr;
 840         if (!nolook)
 841                 j->look = flset(lptr);
 842         pstate[nstate+1] = ++j;
 843         if (j > zzmemsz) {
 844                 zzmemsz = j;
 845                 if (zzmemsz >=  &psmem[new_pstsize])
 846                         exp_psmem();
 847                         /* error("out of state space"); */
 848         }
 849 }
 850
 851 /*
 852  * mark nonterminals which derive the empty string
 853  * also, look for nonterminals which don't derive any token strings
 854  */
 855 static void
 856 cempty()
 857 {
 858 #define EMPTY 1
 859 #define WHOKNOWS 0
 860 #define OK 1
 861         int i, *p;
 862
 863         /*
 864          * first, use the array pempty to detect productions
 865          * that can never be reduced
 866          */
 867
 868         /* set pempty to WHONOWS */
 869         aryfil(pempty, nnonter+1, WHOKNOWS);
 870
 871         /*
 872          * now, look at productions, marking nonterminals which
 873          * derive something
 874          */
 875         more:
 876         PLOOP(0, i) {
 877                 if (pempty[*prdptr[i] - NTBASE])
 878                         continue;
 879                 for (p = prdptr[i] + 1; *p >= 0; ++p)
 880                         if (*p >= NTBASE && pempty[*p-NTBASE] == WHOKNOWS)
 881                                 break;
 882                 if (*p < 0) { /* production can be derived */
 883                         pempty[*prdptr[i]-NTBASE] = OK;
 884                         goto more;
 885                 }
 886         }
 887
 888         /* now, look at the nonterminals, to see if they are all OK */
 889
 890         NTLOOP(i) {
 891                 /*
 892                  * the added production rises or falls as the
 893                  * start symbol ...
 894                  */
 895                 if (i == 0)
 896                         continue;
 897                 if (pempty[i] != OK) {
 898                         fatfl = 0;
 899 /*
 900  * TRANSLATION_NOTE  -- This is a message from yacc.
 901  *      This message is passed to error() function.
 902  *      Ask somebody who knows yacc how to translate nonterminal or
 903  *      look at translated yacc document. Check how 'derive' is
 904  *      translated in these documents also.
 905  */
 906                         error(gettext(
 907                         "nonterminal %ws never derives any token string"),
 908                             nontrst[i].name);
 909                 }
 910         }
 911
 912         if (nerrors) {
 913                 summary();
 914                 exit(1);
 915         }
 916
 917         /*
 918          * now, compute the pempty array, to see which nonterminals
 919          * derive the empty string
 920          */
 921
 922         /* set pempty to WHOKNOWS */
 923
 924         aryfil(pempty, nnonter+1, WHOKNOWS);
 925
 926         /* loop as long as we keep finding empty nonterminals */
 927
 928 again:
 929         PLOOP(1, i) {
 930                 /* not known to be empty */
 931                 if (pempty[*prdptr[i]-NTBASE] == WHOKNOWS) {
 932                         for (p = prdptr[i]+1;
 933                             *p >= NTBASE && pempty[*p-NTBASE] == EMPTY; ++p)
 934                                 ;
 935                         /* we have a nontrivially empty nonterminal */
 936                         if (*p < 0) {
 937                                 pempty[*prdptr[i]-NTBASE] = EMPTY;
 938                                 goto again; /* got one ... try for another */
 939                         }
 940                 }
 941         }
 942 }
 943
 944 /* generate the states */
 945 static int gsdebug = 0;
 946 static void
 947 stagen()
 948 {
 949         int i, j;
 950         int c;
 951         register WSET *p, *q;
 952
 953         /* initialize */
 954
 955         nstate = 0;
 956
 957         pstate[0] = pstate[1] = psmem;
 958         aryfil(clset.lset, tbitset, 0);
 959         putitem(prdptr[0] + 1, &clset);
 960         tystate[0] = MUSTDO;
 961         nstate = 1;
 962         pstate[2] = pstate[1];
 963
 964         aryfil(amem, new_actsize, 0);
 965
 966         /* now, the main state generation loop */
 967
 968         more:
 969         SLOOP(i) {
 970                 if (tystate[i] != MUSTDO)
 971                         continue;
 972                 tystate[i] = DONE;
 973                 aryfil(temp1, nnonter + 1, 0);
 974                 /* take state i, close it, and do gotos */
 975                 closure(i);
 976                 WSLOOP(wsets, p) { /* generate goto's */
 977                         if (p->flag)
 978                                 continue;
 979                         p->flag = 1;
 980                         c = *(p->pitem);
 981                         if (c <= 1) {
 982                                 if (pstate[i+1]-pstate[i] <= p-wsets)
 983                                         tystate[i] = MUSTLOOKAHEAD;
 984                                 continue;
 985                         }
 986                         /* do a goto on c */
 987                         WSLOOP(p, q) {
 988                                 /* this item contributes to the goto */
 989                                 if (c == *(q->pitem)) {
 990                                         putitem(q->pitem + 1, &q->ws);
 991                                         q->flag = 1;
 992                                 }
 993                         }
 994                         if (c < NTBASE)
 995                                 (void) state(c);  /* register new state */
 996                         else temp1[c-NTBASE] = state(c);
 997                 }
 998                 if (gsdebug && (foutput != NULL)) {
 999                         (void) fprintf(foutput,  "%d: ", i);
1000                         NTLOOP(j) {
1001                                 if (temp1[j])
1002                                         (void) fprintf(foutput,
1003                                             WSFMT("%ws %d, "), nontrst[j].name,
1004                                             temp1[j]);
1005                         }
1006                         (void) fprintf(foutput, "\n");
1007                 }
1008                 indgo[i] = apack(&temp1[1], nnonter - 1) - 1;
1009                 goto more; /* we have done one goto; do some more */
1010         }
1011         /* no more to do... stop */
1012 }
1013
1014 /* generate the closure of state i */
1015 static int cldebug = 0; /* debugging flag for closure */
1016
1017 void
1018 closure(int i)
1019 {
1020         int c, ch, work, k;
1021         register WSET *u, *v;
1022         int *pi;
1023         int **s, **t;
1024         ITEM *q;
1025         register ITEM *p;
1026         int idx1 = 0;
1027
1028         ++zzclose;
1029
1030         /* first, copy kernel of state i to wsets */
1031         cwp = 0;
1032         ITMLOOP(i, p, q) {
1033                 wsets[cwp].pitem = p->pitem;
1034                 wsets[cwp].flag = 1;    /* this item must get closed */
1035                 SETLOOP(k)
1036                         wsets[cwp].ws.lset[k] = p->look->lset[k];
1037                 WSBUMP(cwp);
1038         }
1039
1040         /* now, go through the loop, closing each item */
1041
1042         work = 1;
1043         while (work) {
1044                 work = 0;
1045                 /*
1046                  * WSLOOP(wsets, u) {
1047                  */
1048                 for (idx1 = 0; idx1 < cwp; idx1++) {
1049                         u = &wsets[idx1];
1050                         if (u->flag == 0)
1051                                 continue;
1052                         c = *(u->pitem);  /* dot is before c */
1053                         if (c < NTBASE) {
1054                                 u->flag = 0;
1055                                 /*
1056                                  * only interesting case is where . is
1057                                  * before nonterminal
1058                                  */
1059                                 continue;
1060                         }
1061
1062                         /* compute the lookahead */
1063                         aryfil(clset.lset, tbitset, 0);
1064
1065                         /* find items involving c */
1066
1067                         WSLOOP(u, v) {
1068                                 if (v->flag == 1 && *(pi = v->pitem) == c) {
1069                                         v->flag = 0;
1070                                         if (nolook)
1071                                                 continue;
1072                                         while ((ch = *++pi) > 0) {
1073                                                 /* terminal symbol */
1074                                                 if (ch < NTBASE) {
1075                                                         SETBIT(clset.lset, ch);
1076                                                         break;
1077                                                 }
1078                                                 /* nonterminal symbol */
1079                                                 (void) setunion(clset.lset,
1080                                                     pfirst[ch-NTBASE]->lset);
1081                                                 if (!pempty[ch-NTBASE])
1082                                                         break;
1083                                         }
1084                                         if (ch <= 0)
1085                                                 (void) setunion(clset.lset,
1086                                                     v->ws.lset);
1087                                 }
1088                         }
1089
1090                         /*  now loop over productions derived from c */
1091
1092                         c -= NTBASE; /* c is now nonterminal number */
1093
1094                         t = pres[c+1];
1095                         for (s = pres[c]; s < t; ++s) {
1096                                 /* put these items into the closure */
1097                                 WSLOOP(wsets, v) { /* is the item there */
1098                                         /* yes, it is there */
1099                                         if (v->pitem == *s) {
1100                                                 if (nolook)
1101                                                         goto nexts;
1102                                                 if (setunion(v->ws.lset,
1103                                                     clset.lset))
1104                                                         v->flag = work = 1;
1105                                                 goto nexts;
1106                                         }
1107                                 }
1108
1109                                 /*  not there; make a new entry */
1110                                 if (cwp + 1 >= wsetsz)
1111                                         exp_wsets();
1112
1113                                 wsets[cwp].pitem = *s;
1114                                 wsets[cwp].flag = 1;
1115                                 if (!nolook) {
1116                                         work = 1;
1117                                         SETLOOP(k)
1118                                                 wsets[cwp].ws.lset[k] =
1119                                                     clset.lset[k];
1120                                 }
1121                                 WSBUMP(cwp);
1122                                 nexts:;
1123                         }
1124                 }
1125         }
1126
1127         /* have computed closure; flags are reset; return */
1128
1129         if (&wsets[cwp] > &wsets[zzcwp])
1130                 zzcwp = cwp;
1131         if (cldebug && (foutput != NULL)) {
1132                 (void) fprintf(foutput, "\nState %d, nolook = %d\n", i, nolook);
1133                 WSLOOP(wsets, u) {
1134                         if (u->flag)
1135                                 (void) fprintf(foutput, "flag set!\n");
1136                         u->flag = 0;
1137                         (void) fprintf(foutput, WSFMT("\t%ws"),
1138                             writem(u->pitem));
1139                         prlook(&u->ws);
1140                         (void) fprintf(foutput,  "\n");
1141                 }
1142         }
1143 }
1144
1145 static LOOKSETS *
1146 flset(p)
1147 LOOKSETS *p;
1148 {
1149         /* decide if the lookahead set pointed to by p is known */
1150         /* return pointer to a perminent location for the set */
1151
1152         int j, *w;
1153         int *u, *v;
1154         register LOOKSETS *q;
1155
1156         for (q = &lkst[nlset]; q-- > lkst; ) {
1157                 u = p->lset;
1158                 v = q->lset;
1159                 w = & v[tbitset];
1160                 while (v < w)
1161                         if (*u++ != *v++)
1162                                 goto more;
1163                 /* we have matched */
1164                 return (q);
1165                 more:;
1166         }
1167         /* add a new one */
1168         q = &lkst[nlset++];
1169         if (nlset >= lsetsize) {
1170                 exp_lkst();
1171                 q = &lkst[nlset++];
1172         }
1173         SETLOOP(j) q->lset[j] = p->lset[j];
1174         return (q);
1175 }
1176
1177 static void
1178 exp_lkst()
1179 {
1180         int i, j;
1181         static LOOKSETS *lookbase;
1182
1183         lookbase = lkst;
1184         lsetsize += LSETSIZE;
1185         tmp_lset = (int *)
1186             calloc((size_t)(TBITSET * (lsetsize-LSETSIZE)), sizeof (int));
1187         if (tmp_lset == NULL)
1188 /*
1189  * TRANSLATION_NOTE  -- This is a message from yacc.
1190  *      This message is passed to error() function.
1191  *      Memory allocation error. Do not translate lookset.
1192  *
1193  *      You may just translate this as:
1194  *      'Could not allocate internally used memory.'
1195  */
1196                 error(gettext(
1197                 "could not expand lookset array"));
1198         lkst = (LOOKSETS *) realloc((char *)lkst, sizeof (LOOKSETS) * lsetsize);
1199         for (i = lsetsize-LSETSIZE, j = 0; i < lsetsize; ++i, ++j)
1200                 lkst[i].lset = tmp_lset + TBITSET * j;
1201         tmp_lset = NULL;
1202         if (lkst == NULL)
1203 /*
1204  * TRANSLATION_NOTE  -- This is a message from yacc.
1205  *      This message is passed to error() function.
1206  *      Memory allocation error. Do not translate lookset.
1207  *
1208  *      You may just translate this as:
1209  *      'Could not allocate internally used memory.'
1210  */
1211                 error(gettext(
1212                 "could not expand lookahead sets"));
1213         for (i = 0; i <= nnonter; ++i)
1214                 pfirst[i] = pfirst[i] - lookbase + lkst;
1215         for (i = 0; i <= nstate+1; ++i) {
1216                 if (psmem[i].look)
1217                         psmem[i].look = psmem[i].look - lookbase + lkst;
1218                 if (pstate[i]->look)
1219                         pstate[i]->look = pstate[i]->look - lookbase + lkst;
1220         }
1221 }
1222
1223 static void
1224 exp_wsets()
1225 {
1226         int i, j;
1227
1228         wsetsz += WSETSIZE;
1229         tmp_lset = (int *)
1230             calloc((size_t)(TBITSET * (wsetsz-WSETSIZE)), sizeof (int));
1231         if (tmp_lset == NULL)
1232 /*
1233  * TRANSLATION_NOTE  -- This is a message from yacc.
1234  *      This message is passed to error() function.
1235  *      Memory allocation error. Do not translate lookset.
1236  *
1237  *      You may just translate this as:
1238  *      'Could not allocate internally used memory.'
1239  */
1240                 error(gettext(
1241                 "could not expand lookset array"));
1242         wsets = (WSET *) realloc((char *)wsets, sizeof (WSET) * wsetsz);
1243         for (i = wsetsz-WSETSIZE, j = 0; i < wsetsz; ++i, ++j)
1244                 wsets[i].ws.lset = tmp_lset + TBITSET * j;
1245         tmp_lset = NULL;
1246         if (wsets == NULL)
1247 /*
1248  * TRANSLATION_NOTE  -- This is a message from yacc.
1249  *      This message is passed to error() function.
1250  *      Memory allocation error. You may just transltate
1251  *      this as 'Could not allocate internally used memory.'
1252  *
1253  *      You may just translate this as:
1254  *      'Could not allocate internally used memory.'
1255  */
1256                 error(gettext(
1257                 "could not expand working sets"));
1258 }
1259
1260 static void
1261 exp_states()
1262 {
1263         nstatesz += NSTATES;
1264
1265         pstate = (ITEM **)
1266             realloc((char *)pstate, sizeof (ITEM *)*(nstatesz+2));
1267         mstates = (int *)realloc((char *)mstates, sizeof (int)*nstatesz);
1268         defact = (int *)realloc((char *)defact, sizeof (int)*nstatesz);
1269         tystate = (int *)realloc((char *)tystate, sizeof (int)*nstatesz);
1270         indgo = (int *)realloc((char *)indgo, sizeof (int)*nstatesz);
1271
1272         if ((*pstate == NULL) || (tystate == NULL) || (defact == NULL) ||
1273             (indgo == NULL) || (mstates == NULL))
1274 /*
1275  * TRANSLATION_NOTE  -- This is a message from yacc.
1276  *      This message is passed to error() function.
1277  *      Memory allocation error.
1278  *
1279  *      You may just translate this as:
1280  *      'Could not allocate internally used memory.'
1281  */
1282                 error(gettext(
1283                 "cannot expand table of states"));
1284 }
1285
1286 static void
1287 exp_psmem()
1288 {
1289         int i;
1290
1291         new_pstsize += PSTSIZE;
1292         psmem = (ITEM *) realloc((char *)psmem, sizeof (ITEM) * new_pstsize);
1293         if (psmem == NULL)
1294 /*
1295  * TRANSLATION_NOTE  -- This is a message from yacc.
1296  *      This message is passed to error() function.
1297  *      Memory allocation error.
1298  *
1299  *      You may just translate this as:
1300  *      'Could not allocate internally used memory.'
1301  */
1302                 error(gettext(
1303                 "cannot expand pstate memory"));
1304
1305         zzmemsz = zzmemsz - pstate[0] + psmem;
1306         for (i = 1; i <= nstate+1; ++i)
1307                 pstate[i] = pstate[i] - pstate[0] + psmem;
1308         pstate[0] = psmem;
1309 }