usr/src/cmd/sgs/lex/common/sub2.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 "ldefs.h"
  32
  33 static void add(int **array, int n);
  34 static void follow(int v);
  35 static void first(int v);
  36 static void nextstate(int s, int c);
  37 static void packtrans(int st, CHR *tch, int *tst, int cnt, int tryit);
  38 static void acompute(int s);
  39 static void rprint(int *a, char *s, int n);
  40 static void shiftr(int *a, int n);
  41 static void upone(int *a, int n);
  42 static void bprint(char *a, char *s, int n);
  43 static int notin(int n);
  44 static int member(int d, CHR *t);
  45
  46 #ifdef PP
  47 static void padd(int **array, int n);
  48 #endif
  49
  50 void
  51 cfoll(int v)
  52 {
  53         int i, j, k;
  54         CHR *p;
  55         i = name[v];
  56         if (!ISOPERATOR(i))
  57                 i = 1;
  58         switch (i) {
  59                 case 1: case RSTR: case RCCL: case RNCCL: case RNULLS:
  60                         for (j = 0; j < tptr; j++)
  61                                 tmpstat[j] = FALSE;
  62                         count = 0;
  63                         follow(v);
  64 #ifdef PP
  65                         padd(foll, v); /* packing version */
  66 #else
  67                         add(foll, v); /* no packing version */
  68 #endif
  69                         if (i == RSTR)
  70                                 cfoll(left[v]);
  71                         else if (i == RCCL || i == RNCCL) {
  72                                 for (j = 1; j < ncg; j++)
  73                                         symbol[j] = (i == RNCCL);
  74                                 p = (CHR *) left[v];
  75                                 while (*p)
  76                                         symbol[*p++] = (i == RCCL);
  77                                 p = pcptr;
  78                                 for (j = 1; j < ncg; j++)
  79                                         if (symbol[j]) {
  80                                                 for (k = 0; p + k < pcptr; k++)
  81                                                         if (cindex[j] ==
  82                                                             *(p + k))
  83                                                                 break;
  84                                                 if (p + k >= pcptr)
  85                                                         *pcptr++ = cindex[j];
  86                                         }
  87                                 *pcptr++ = 0;
  88                                 if (pcptr > pchar + pchlen)
  89                                         error(
  90                                         "Too many packed character classes");
  91                                 left[v] = (int)p;
  92                                 name[v] = RCCL; /* RNCCL eliminated */
  93 #ifdef DEBUG
  94                                 if (debug && *p) {
  95                                         (void) printf("ccl %d: %d", v, *p++);
  96                                         while (*p)
  97                                                 (void) printf(", %d", *p++);
  98                                         (void) putchar('\n');
  99                                 }
 100 #endif
 101                         }
 102                         break;
 103                 case CARAT:
 104                         cfoll(left[v]);
 105                         break;
 106
 107                 /* XCU4: add RXSCON */
 108                 case RXSCON:
 109
 110                 case STAR: case PLUS: case QUEST: case RSCON:
 111                         cfoll(left[v]);
 112                         break;
 113                 case BAR: case RCAT: case DIV: case RNEWE:
 114                         cfoll(left[v]);
 115                         cfoll(right[v]);
 116                         break;
 117 #ifdef DEBUG
 118                 case FINAL:
 119                 case S1FINAL:
 120                 case S2FINAL:
 121                         break;
 122                 default:
 123                         warning("bad switch cfoll %d", v);
 124 #endif
 125         }
 126 }
 127
 128 #ifdef DEBUG
 129 void
 130 pfoll(void)
 131 {
 132         int i, k, *p;
 133         int j;
 134         /* print sets of chars which may follow positions */
 135         (void) printf("pos\tchars\n");
 136         for (i = 0; i < tptr; i++)
 137                 if (p = foll[i]) {
 138                         j = *p++;
 139                         if (j >= 1) {
 140                                 (void) printf("%d:\t%d", i, *p++);
 141                                 for (k = 2; k <= j; k++)
 142                                         (void) printf(", %d", *p++);
 143                                 (void) putchar('\n');
 144                         }
 145                 }
 146 }
 147 #endif
 148
 149 static void
 150 add(int **array, int n)
 151 {
 152         int i, *temp;
 153         CHR *ctemp;
 154         temp = nxtpos;
 155         ctemp = tmpstat;
 156         array[n] = nxtpos;      /* note no packing is done in positions */
 157         *temp++ = count;
 158         for (i = 0; i < tptr; i++)
 159                 if (ctemp[i] == TRUE)
 160                         *temp++ = i;
 161         nxtpos = temp;
 162         if (nxtpos >= positions+maxpos)
 163                 error(
 164                 "Too many positions %s",
 165                     (maxpos == MAXPOS ? "\nTry using %p num" : ""));
 166 }
 167
 168 static void
 169 follow(int v)
 170 {
 171         int p;
 172         if (v >= tptr-1)
 173                 return;
 174         p = parent[v];
 175         if (p == 0)
 176                 return;
 177         switch (name[p]) {
 178         /* will not be CHAR RNULLS FINAL S1FINAL S2FINAL RCCL RNCCL */
 179         case RSTR:
 180                 if (tmpstat[p] == FALSE) {
 181                         count++;
 182                         tmpstat[p] = TRUE;
 183                 }
 184                 break;
 185         case STAR: case PLUS:
 186                 first(v);
 187                 follow(p);
 188                 break;
 189         case BAR: case QUEST: case RNEWE:
 190                 follow(p);
 191                 break;
 192         case RCAT: case DIV:
 193                 if (v == left[p]) {
 194                         if (nullstr[right[p]])
 195                                 follow(p);
 196                         first(right[p]);
 197                 }
 198                 else
 199                         follow(p);
 200                 break;
 201         /* XCU4: add RXSCON */
 202         case RXSCON:
 203         case RSCON: case CARAT:
 204                 follow(p);
 205                 break;
 206 #ifdef DEBUG
 207         default:
 208                 warning("bad switch follow %d", p);
 209 #endif
 210         }
 211 }
 212
 213 /*
 214  * Check if I have a RXSCON in my upper node
 215  */
 216 static int
 217 check_me(int v)
 218 {
 219         int tmp = parent[v];
 220
 221         while (name[tmp] != RNEWE) {
 222                 if (name[tmp] == RXSCON)
 223                         return (1);
 224                 tmp = parent[tmp];
 225         }
 226         return (0);
 227 }
 228
 229 /* calculate set of positions with v as root which can be active initially */
 230 static void
 231 first(int v)
 232 {
 233         int i;
 234         CHR *p;
 235         i = name[v];
 236         if (!ISOPERATOR(i))
 237                 i = 1;
 238         switch (i) {
 239         case 1: case RCCL: case RNCCL:
 240         case RNULLS: case FINAL:
 241         case S1FINAL: case S2FINAL:
 242         /*
 243          * XCU4: if we are working on an exclusive start state and
 244          * the parent of this position is not RXSCON or RSTR this
 245          * is not an active position.
 246          *
 247          * (There is a possibility that RSXCON appreas as the
 248          *  (parent)* node. Check it by check_me().)
 249          */
 250                 if ((exclusive[stnum/2]) &&
 251                     ISOPERATOR(name[parent[v]]) &&
 252                     (name[parent[v]] != RXSCON) &&
 253                     (name[parent[v]] != RSTR) &&
 254                     (check_me(v) == 0)) {
 255                                 break;
 256                 }
 257                 if (tmpstat[v] == FALSE) {
 258                         count++;
 259                         tmpstat[v] = TRUE;
 260                 }
 261                 break;
 262         case BAR: case RNEWE:
 263                 first(left[v]);
 264                 first(right[v]);
 265                 break;
 266         case CARAT:
 267                 if (stnum % 2 == 1)
 268                         first(left[v]);
 269                 break;
 270         /* XCU4: add RXSCON */
 271         case RXSCON:
 272         case RSCON:
 273                 i = stnum/2 +1;
 274                 p = (CHR *) right[v];
 275                 while (*p)
 276                         if (*p++ == i) {
 277                                 first(left[v]);
 278                                 break;
 279                         }
 280                 break;
 281         case STAR: case QUEST:
 282         case PLUS:  case RSTR:
 283         /*
 284          * XCU4: if we are working on an exclusive start state and
 285          * the parent of this position is not RXSCON or RSTR this
 286          * is not an active position.
 287          *
 288          * (There is a possibility that RSXCON appreas as the
 289          *  (parent)* node. Check it by check_me().)
 290          */
 291                 if ((exclusive[stnum/2]) &&
 292                     ISOPERATOR(name[parent[v]]) &&
 293                     (name[parent[v]] != RXSCON) &&
 294                     (name[parent[v]] != RSTR) &&
 295                     (check_me(v) == 0)) {
 296                                 break;
 297                 }
 298                 first(left[v]);
 299                 break;
 300         case RCAT: case DIV:
 301                 first(left[v]);
 302                 if (nullstr[left[v]])
 303                         first(right[v]);
 304                 break;
 305 #ifdef DEBUG
 306         default:
 307                 warning("bad switch first %d", v);
 308 #endif
 309         }
 310 }
 311
 312 void
 313 cgoto(void)
 314 {
 315         int i, j;
 316         static int s;
 317         int npos, curpos, n;
 318         int tryit;
 319         CHR tch[MAXNCG];
 320         int tst[MAXNCG];
 321         CHR *q;
 322         /* generate initial state, for each start condition */
 323         if (ratfor) {
 324                 (void) fprintf(fout, "blockdata\n");
 325                 (void) fprintf(fout, "common /Lvstop/ vstop\n");
 326                 (void) fprintf(fout, "define Svstop %d\n", nstates+1);
 327                 (void) fprintf(fout, "integer vstop(Svstop)\n");
 328         } else
 329                 (void) fprintf(fout, "int yyvstop[] = {\n0,\n");
 330         while (stnum < 2 || stnum/2 < sptr) {
 331                 for (i = 0; i < tptr; i++)
 332                         tmpstat[i] = 0;
 333                 count = 0;
 334                 if (tptr > 0)
 335                         first(tptr-1);
 336                 add(state, stnum);
 337 #ifdef DEBUG
 338                 if (debug) {
 339                         if (stnum > 1)
 340                                 (void) printf("%ws:\n", sname[stnum/2]);
 341                         pstate(stnum);
 342                 }
 343 #endif
 344                 stnum++;
 345         }
 346         stnum--;
 347         /* even stnum = might not be at line begin */
 348         /* odd stnum  = must be at line begin */
 349         /* even states can occur anywhere, odd states only at line begin */
 350         for (s = 0; s <= stnum; s++) {
 351                 tryit = FALSE;
 352                 cpackflg[s] = FALSE;
 353                 sfall[s] = -1;
 354                 acompute(s);
 355                 for (i = 0; i < ncg; i++)
 356                         symbol[i] = 0;
 357                 npos = *state[s];
 358                 for (i = 1; i <= npos; i++) {
 359                         curpos = *(state[s]+i);
 360                         if (!ISOPERATOR(name[curpos]))
 361                                 symbol[name[curpos]] = TRUE;
 362                         else {
 363                                 switch (name[curpos]) {
 364                                 case RCCL:
 365                                         tryit = TRUE;
 366                                         q = (CHR *)left[curpos];
 367                                         while (*q) {
 368                                                 for (j = 1; j < ncg; j++)
 369                                                         if (cindex[j] == *q)
 370                                                                 symbol[j] =
 371                                                                     TRUE;
 372                                                 q++;
 373                                         }
 374                                         break;
 375                                 case RSTR:
 376                                         symbol[right[curpos]] = TRUE;
 377                                         break;
 378 #ifdef DEBUG
 379                                 case RNULLS:
 380                                 case FINAL:
 381                                 case S1FINAL:
 382                                 case S2FINAL:
 383                                         break;
 384                                 default:
 385                                         warning(
 386                                         "bad switch cgoto %d state %d",
 387                                             curpos, s);
 388                                         break;
 389 #endif
 390                                 }
 391                         }
 392                 }
 393 #ifdef DEBUG
 394                 if (debug) {
 395                         printf("State %d transitions on char-group {", s);
 396                         charc = 0;
 397                         for (i = 1; i < ncg; i++) {
 398                                 if (symbol[i]) {
 399                                         printf("%d,", i);
 400                                 }
 401                                 if (i == ncg-1)
 402                                         printf("}\n");
 403                                 if (charc > LINESIZE/4) {
 404                                         charc = 0;
 405                                         printf("\n\t");
 406                                 }
 407                         }
 408                 }
 409 #endif
 410                 /* for each char, calculate next state */
 411                 n = 0;
 412                 for (i = 1; i < ncg; i++) {
 413                         if (symbol[i]) {
 414                                 /* executed for each state, transition pair */
 415                                 nextstate(s, i);
 416                                 xstate = notin(stnum);
 417                                 if (xstate == -2)
 418                                         warning("bad state  %d %o", s, i);
 419                                 else if (xstate == -1) {
 420                                         if (stnum+1 >= nstates) {
 421                                                 stnum++;
 422                                                 error("Too many states %s",
 423                                                     (nstates == NSTATES ?
 424                                                     "\nTry using %n num":""));
 425                                         }
 426                                         add(state, ++stnum);
 427 #ifdef DEBUG
 428                                         if (debug)
 429                                                 pstate(stnum);
 430 #endif
 431                                         tch[n] = i;
 432                                         tst[n++] = stnum;
 433                                 } else { /* xstate >= 0 ==> state exists */
 434                                         tch[n] = i;
 435                                         tst[n++] = xstate;
 436                                 }
 437                         }
 438                 }
 439                 tch[n] = 0;
 440                 tst[n] = -1;
 441                 /* pack transitions into permanent array */
 442                 if (n > 0)
 443                         packtrans(s, tch, tst, n, tryit);
 444                 else
 445                         gotof[s] = -1;
 446         }
 447         (void) (ratfor ? fprintf(fout, "end\n") : fprintf(fout, "0};\n"));
 448 }
 449
 450 /*
 451  * Beware -- 70% of total CPU time is spent in this subroutine -
 452  * if you don't believe me - try it yourself !
 453  */
 454 static void
 455 nextstate(int s, int c)
 456 {
 457         int j, *newpos;
 458         CHR *temp, *tz;
 459         int *pos, i, *f, num, curpos, number;
 460         /* state to goto from state s on char c */
 461         num = *state[s];
 462         temp = tmpstat;
 463         pos = state[s] + 1;
 464         for (i = 0; i < num; i++) {
 465                 curpos = *pos++;
 466                 j = name[curpos];
 467                 if ((!ISOPERATOR(j)) && j == c ||
 468                     j == RSTR && c == right[curpos] ||
 469                     j == RCCL && member(c, (CHR *) left[curpos])) {
 470                         f = foll[curpos];
 471                         number = *f;
 472                         newpos = f+1;
 473                         for (j = 0; j < number; j++)
 474                                 temp[*newpos++] = 2;
 475                 }
 476         }
 477         j = 0;
 478         tz = temp + tptr;
 479         while (temp < tz) {
 480                 if (*temp == 2) {
 481                         j++;
 482                         *temp++ = 1;
 483                 }
 484                 else
 485                         *temp++ = 0;
 486         }
 487         count = j;
 488 }
 489
 490 static int
 491 notin(int n)
 492 {       /* see if tmpstat occurs previously */
 493         int *j, k;
 494         CHR *temp;
 495         int i;
 496         if (count == 0)
 497                 return (-2);
 498         temp = tmpstat;
 499         for (i = n; i >= 0; i--) { /* for each state */
 500                 j = state[i];
 501                 if (count == *j++) {
 502                         for (k = 0; k < count; k++)
 503                                 if (!temp[*j++])
 504                                         break;
 505                         if (k >= count)
 506                                 return (i);
 507                 }
 508         }
 509         return (-1);
 510 }
 511
 512 static void
 513 packtrans(int st, CHR *tch, int *tst, int cnt, int tryit)
 514 {
 515         /*
 516          * pack transitions into nchar, nexts
 517          * nchar is terminated by '\0', nexts uses cnt, followed by elements
 518          * gotof[st] = index into nchr, nexts for state st
 519          * sfall[st] =  t implies t is fall back state for st
 520          * == -1 implies no fall back
 521          */
 522
 523         int cmin, cval, tcnt, diff, p, *ast;
 524         int i, j, k;
 525         CHR *ach;
 526         int go[MAXNCG], temp[MAXNCG], index, c;
 527         int swork[MAXNCG];
 528         CHR cwork[MAXNCG];
 529         int upper;
 530
 531         rcount += (long)cnt;
 532         cmin = -1;
 533         cval = ncg;
 534         ast = tst;
 535         ach = tch;
 536         /* try to pack transitions using ccl's */
 537         if (!optim)
 538                 goto nopack; /* skip all compaction */
 539         if (tryit) { /* ccl's used */
 540                 for (i = 1; i < ncg; i++) {
 541                         go[i] = temp[i] = -1;
 542                         symbol[i] = 1;
 543                 }
 544                 for (i = 0; i < cnt; i++) {
 545                         index = (unsigned char) tch[i];
 546                         if ((index >= 0) && (index < NCH)) {
 547                                 go[index] = tst[i];
 548                                 symbol[index] = 0;
 549                         } else {
 550                                 (void) fprintf(stderr,
 551 "lex`sub2`packtran: tch[%d] out of bounds (%d)\n",
 552                                     i, (int)tch[i]);
 553                         }
 554                 }
 555                 for (i = 0; i < cnt; i++) {
 556                         c = match[tch[i]];
 557                         if (go[c] != tst[i] || c == tch[i])
 558                                 temp[tch[i]] = tst[i];
 559                 }
 560                 /* fill in error entries */
 561                 for (i = 1; i < ncg; i++)
 562                         if (symbol[i])
 563                                 temp[i] = -2;   /* error trans */
 564                 /* count them */
 565                 k = 0;
 566                 for (i = 1; i < ncg; i++)
 567                         if (temp[i] != -1)
 568                                 k++;
 569                 if (k < cnt) { /* compress by char */
 570 #ifdef DEBUG
 571                         if (debug)
 572                                 (void) printf(
 573                                 "use compression  %d,  %d vs %d\n", st, k, cnt);
 574 #endif
 575                         k = 0;
 576                         for (i = 1; i < ncg; i++)
 577                                 if (temp[i] != -1) {
 578                                         cwork[k] = i;
 579                                         swork[k++] =
 580                                             (temp[i] == -2 ? -1 : temp[i]);
 581                                 }
 582                         cwork[k] = 0;
 583 #ifdef PC
 584                         ach = cwork;
 585                         ast = swork;
 586                         cnt = k;
 587                         cpackflg[st] = TRUE;
 588 #endif
 589                 }
 590         }
 591         /*
 592          * get most similar state
 593          * reject state with more transitions,
 594          * state already represented by a third state,
 595          * and state which is compressed by char if ours is not to be
 596          */
 597         for (i = 0; i < st; i++) {
 598                 if (sfall[i] != -1)
 599                         continue;
 600                 if (cpackflg[st] == 1)
 601                         if (!(cpackflg[i] == 1))
 602                                 continue;
 603                 p = gotof[i];
 604                 if (p == -1) /* no transitions */
 605                         continue;
 606                 tcnt = nexts[p];
 607                 if (tcnt > cnt)
 608                         continue;
 609                 diff = 0;
 610                 k = 0;
 611                 j = 0;
 612                 upper = p + tcnt;
 613                 while (ach[j] && p < upper) {
 614                         while (ach[j] < nchar[p] && ach[j]) {
 615                                 diff++;
 616                                 j++;
 617                         }
 618                         if (ach[j] == 0)
 619                                 break;
 620                         if (ach[j] > nchar[p]) {
 621                                 diff = ncg;
 622                                 break;
 623                         }
 624                         /* ach[j] == nchar[p] */
 625                         if (ast[j] != nexts[++p] ||
 626                             ast[j] == -1 ||
 627                             (cpackflg[st] && ach[j] != match[ach[j]]))
 628                                 diff++;
 629                         j++;
 630                 }
 631                 while (ach[j]) {
 632                         diff++;
 633                         j++;
 634                 }
 635                 if (p < upper)
 636                         diff = ncg;
 637                 if (diff < cval && diff < tcnt) {
 638                         cval = diff;
 639                         cmin = i;
 640                         if (cval == 0)
 641                                 break;
 642                 }
 643         }
 644         /* cmin = state "most like" state st */
 645 #ifdef DEBUG
 646         if (debug)
 647                 (void) printf("select st %d for st %d diff %d\n",
 648                     cmin, st, cval);
 649 #endif
 650 #ifdef PS
 651         if (cmin != -1) { /* if we can use st cmin */
 652                 gotof[st] = nptr;
 653                 k = 0;
 654                 sfall[st] = cmin;
 655                 p = gotof[cmin] + 1;
 656                 j = 0;
 657                 while (ach[j]) {
 658                         /* if cmin has a transition on c, then so will st */
 659                         /* st may be "larger" than cmin, however */
 660                         while (ach[j] < nchar[p-1] && ach[j]) {
 661                                 k++;
 662                                 nchar[nptr] = ach[j];
 663                                 nexts[++nptr] = ast[j];
 664                                 j++;
 665                         }
 666                         if (nchar[p-1] == 0)
 667                                 break;
 668                         if (ach[j] > nchar[p-1]) {
 669                                 warning("bad transition %d %d", st, cmin);
 670                                 goto nopack;
 671                         }
 672                         /* ach[j] == nchar[p-1] */
 673                         if (ast[j] != nexts[p] ||
 674                             ast[j] == -1 ||
 675                             (cpackflg[st] && ach[j] != match[ach[j]])) {
 676                                 k++;
 677                                 nchar[nptr] = ach[j];
 678                                 nexts[++nptr] = ast[j];
 679                         }
 680                         p++;
 681                         j++;
 682                 }
 683                 while (ach[j]) {
 684                         nchar[nptr] = ach[j];
 685                         nexts[++nptr] = ast[j++];
 686                         k++;
 687                 }
 688                 nexts[gotof[st]] = cnt = k;
 689                 nchar[nptr++] = 0;
 690         } else {
 691 #endif
 692 nopack:
 693         /* stick it in */
 694                 gotof[st] = nptr;
 695                 nexts[nptr] = cnt;
 696                 for (i = 0; i < cnt; i++) {
 697                         nchar[nptr] = ach[i];
 698                         nexts[++nptr] = ast[i];
 699                 }
 700                 nchar[nptr++] = 0;
 701 #ifdef PS
 702         }
 703 #endif
 704         if (cnt < 1) {
 705                 gotof[st] = -1;
 706                 nptr--;
 707         } else
 708                 if (nptr > ntrans)
 709                         error(
 710                         "Too many transitions %s",
 711                             (ntrans == NTRANS ? "\nTry using %a num" : ""));
 712 }
 713
 714 #ifdef DEBUG
 715 void
 716 pstate(int s)
 717 {
 718         int *p, i, j;
 719         (void) printf("State %d:\n", s);
 720         p = state[s];
 721         i = *p++;
 722         if (i == 0)
 723                 return;
 724         (void) printf("%4d", *p++);
 725         for (j = 1; j < i; j++) {
 726                 (void) printf(", %4d", *p++);
 727                 if (j%30 == 0)
 728                         (void) putchar('\n');
 729         }
 730         (void) putchar('\n');
 731 }
 732 #endif
 733
 734 static int
 735 member(int d, CHR *t)
 736 {
 737         int c;
 738         CHR *s;
 739         c = d;
 740         s = t;
 741         c = cindex[c];
 742         while (*s)
 743                 if (*s++ == c)
 744                         return (1);
 745         return (0);
 746 }
 747
 748 #ifdef DEBUG
 749 void
 750 stprt(int i)
 751 {
 752         int p, t;
 753         (void) printf("State %d:", i);
 754         /* print actions, if any */
 755         t = atable[i];
 756         if (t != -1)
 757                 (void) printf(" final");
 758         (void) putchar('\n');
 759         if (cpackflg[i] == TRUE)
 760                 (void) printf("backup char in use\n");
 761         if (sfall[i] != -1)
 762                 (void) printf("fall back state %d\n", sfall[i]);
 763         p = gotof[i];
 764         if (p == -1)
 765                 return;
 766         (void) printf("(%d transitions)\n", nexts[p]);
 767         while (nchar[p]) {
 768                 charc = 0;
 769                 if (nexts[p+1] >= 0)
 770                         (void) printf("%d\t", nexts[p+1]);
 771                 else
 772                         (void) printf("err\t");
 773                 allprint(nchar[p++]);
 774                 while (nexts[p] == nexts[p+1] && nchar[p]) {
 775                         if (charc > LINESIZE) {
 776                                 charc = 0;
 777                                 (void) printf("\n\t");
 778                         }
 779                         allprint(nchar[p++]);
 780                 }
 781                 (void) putchar('\n');
 782         }
 783         (void) putchar('\n');
 784 }
 785 #endif
 786
 787 /* compute action list = set of poss. actions */
 788 static void
 789 acompute(int s)
 790 {
 791         int *p, i, j;
 792         int q, r;
 793         int cnt, m;
 794         int temp[MAXPOSSTATE], k, neg[MAXPOSSTATE], n;
 795         k = 0;
 796         n = 0;
 797         p = state[s];
 798         cnt = *p++;
 799         if (cnt > MAXPOSSTATE)
 800                 error("Too many positions for one state - acompute");
 801         for (i = 0; i < cnt; i++) {
 802                 q = *p;
 803                 if (name[q] == FINAL)
 804                         temp[k++] = left[q];
 805                 else if (name[q] == S1FINAL) {
 806                         temp[k++] = left[q];
 807                         if ((r = left[q]) >= NACTIONS)
 808                                 error(
 809                                 "INTERNAL ERROR:left[%d]==%d>=NACTIONS", q, r);
 810                         extra[r] = 1;
 811                 } else if (name[q] == S2FINAL)
 812                         neg[n++] = left[q];
 813                 p++;
 814         }
 815         atable[s] = -1;
 816         if (k < 1 && n < 1)
 817                 return;
 818 #ifdef DEBUG
 819         if (debug)
 820                 (void) printf("final %d actions:", s);
 821 #endif
 822         /* sort action list */
 823         for (i = 0; i < k; i++)
 824                 for (j = i+1; j < k; j++)
 825                         if (temp[j] < temp[i]) {
 826                                 m = temp[j];
 827                                 temp[j] = temp[i];
 828                                 temp[i] = m;
 829                         }
 830         /* remove dups */
 831         for (i = 0; i < k-1; i++)
 832                 if (temp[i] == temp[i+1])
 833                         temp[i] = 0;
 834         /* copy to permanent quarters */
 835         atable[s] = aptr;
 836 #ifdef DEBUG
 837         if (!ratfor)
 838                 (void) fprintf(fout, "/* actions for state %d */", s);
 839 #endif
 840         (void) putc('\n', fout);
 841         for (i = 0; i < k; i++)
 842                 if (temp[i] != 0) {
 843                         (void) (ratfor ?
 844                             fprintf(fout, "data vstop(%d)/%d/\n",
 845                             aptr, temp[i]) :
 846                             fprintf(fout, "%d,\n", temp[i]));
 847 #ifdef DEBUG
 848                         if (debug)
 849                                 (void) printf("%d ", temp[i]);
 850 #endif
 851                         aptr++;
 852                 }
 853         for (i = 0; i < n; i++) { /* copy fall back actions - all neg */
 854                 ratfor ?
 855                     (void) fprintf(fout, "data vstop(%d)/%d/\n", aptr, neg[i]) :
 856                     (void) fprintf(fout, "%d,\n", neg[i]);
 857                 aptr++;
 858 #ifdef DEBUG
 859                 if (debug)
 860                         (void) printf("%d ", neg[i]);
 861 #endif
 862                 }
 863 #ifdef DEBUG
 864         if (debug)
 865                 (void) putchar('\n');
 866 #endif
 867         (void) (ratfor ? fprintf(fout, "data vstop (%d)/0/\n", aptr) :
 868             fprintf(fout, "0, \n"));
 869         aptr++;
 870 }
 871
 872 #ifdef DEBUG
 873 void
 874 pccl(void)
 875 {
 876         /* print character class sets */
 877         int i, j;
 878         (void) printf("char class intersection\n");
 879         for (i = 0; i < ccount; i++) {
 880                 charc = 0;
 881                 (void) printf("class %d:\n\t", i);
 882                 for (j = 1; j < ncg; j++)
 883                         if (cindex[j] == i) {
 884                                 allprint(j);
 885                                 if (charc > LINESIZE) {
 886                                         (void) printf("\n\t");
 887                                         charc = 0;
 888                                 }
 889                         }
 890                 (void) putchar('\n');
 891         }
 892         charc = 0;
 893         (void) printf("match:\n");
 894         for (i = 0; i < ncg; i++) {
 895                 allprint(match[i]);
 896                 if (charc > LINESIZE) {
 897                         (void) putchar('\n');
 898                         charc = 0;
 899                 }
 900         }
 901         (void) putchar('\n');
 902 }
 903 #endif
 904
 905 void
 906 mkmatch(void)
 907 {
 908         int i;
 909         CHR tab[MAXNCG];
 910         for (i = 0; i < ccount; i++)
 911                 tab[i] = 0;
 912         for (i = 1; i < ncg; i++)
 913                 if (tab[cindex[i]] == 0)
 914                         tab[cindex[i]] = i;
 915         /* tab[i] = principal char for new ccl i */
 916         for (i = 1; i < ncg; i++)
 917                 match[i] = tab[cindex[i]];
 918 }
 919
 920 void
 921 layout(void)
 922 {
 923         /* format and output final program's tables */
 924         int i, j, k;
 925         int  top, bot, startup, omin;
 926         startup = 0;
 927         for (i = 0; i < outsize; i++)
 928                 verify[i] = advance[i] = 0;
 929         omin = 0;
 930         yytop = 0;
 931         for (i = 0; i <= stnum; i++) { /* for each state */
 932                 j = gotof[i];
 933                 if (j == -1) {
 934                         stoff[i] = 0;
 935                         continue;
 936                 }
 937                 bot = j;
 938                 while (nchar[j])
 939                         j++;
 940                 top = j - 1;
 941 #if DEBUG
 942                 if (debug) {
 943                         (void) printf("State %d: (layout)\n", i);
 944                         for (j = bot; j <= top; j++) {
 945                                 (void) printf("  %o", nchar[j]);
 946                                 if (j % 10 == 0)
 947                                         (void) putchar('\n');
 948                         }
 949                         (void) putchar('\n');
 950                 }
 951 #endif
 952                 while (verify[omin+ZCH])
 953                         omin++;
 954                 startup = omin;
 955 #if DEBUG
 956                 if (debug)
 957                         (void) printf(
 958                         "bot,top %d, %d startup begins %d\n",
 959                             bot, top, startup);
 960 #endif
 961                 if (chset) {
 962                         do {
 963                                 startup += 1;
 964                                 if (startup > outsize - ZCH)
 965                                         error("output table overflow");
 966                                 for (j = bot; j <= top; j++) {
 967                                         k = startup+ctable[nchar[j]];
 968                                         if (verify[k])
 969                                                 break;
 970                                 }
 971                         } while (j <= top);
 972 #if DEBUG
 973                         if (debug)
 974                                 (void) printf(" startup will be %d\n",
 975                                     startup);
 976 #endif
 977                         /* have found place */
 978                         for (j = bot; j <= top; j++) {
 979                                 k = startup + ctable[nchar[j]];
 980                                 if (ctable[nchar[j]] <= 0)
 981                                         (void) printf(
 982                                         "j %d nchar %d ctable.nch %d\n",
 983                                             j, (int)nchar[j], ctable[nchar[k]]);
 984                                 verify[k] = i + 1;      /* state number + 1 */
 985                                 advance[k] = nexts[j+1]+1;
 986                                 if (yytop < k)
 987                                         yytop = k;
 988                         }
 989                 } else {
 990                         do {
 991                                 startup += 1;
 992                                 if (startup > outsize - ZCH)
 993                                         error("output table overflow");
 994                                 for (j = bot; j <= top; j++) {
 995                                         k = startup + nchar[j];
 996                                         if (verify[k])
 997                                                 break;
 998                                 }
 999                         } while (j <= top);
1000                         /* have found place */
1001 #if DEBUG
1002         if (debug)
1003                 (void) printf(" startup going to be %d\n", startup);
1004 #endif
1005                         for (j = bot; j <= top; j++) {
1006                                 k = startup + nchar[j];
1007                                 verify[k] = i+1; /* state number + 1 */
1008                                 advance[k] = nexts[j+1] + 1;
1009                                 if (yytop < k)
1010                                         yytop = k;
1011                         }
1012                 }
1013                 stoff[i] = startup;
1014         }
1015
1016         /* stoff[i] = offset into verify, advance for trans for state i */
1017         /* put out yywork */
1018         if (ratfor) {
1019                 (void) fprintf(fout, "define YYTOPVAL %d\n", yytop);
1020                 rprint(verify, "verif", yytop+1);
1021                 rprint(advance, "advan", yytop+1);
1022                 shiftr(stoff, stnum);
1023                 rprint(stoff, "stoff", stnum+1);
1024                 shiftr(sfall, stnum);
1025                 upone(sfall, stnum+1);
1026                 rprint(sfall, "fall", stnum+1);
1027                 bprint(extra, "extra", casecount+1);
1028                 bprint((char *)match, "match", ncg);
1029                 shiftr(atable, stnum);
1030                 rprint(atable, "atable", stnum+1);
1031         }
1032         (void) fprintf(fout,
1033         "# define YYTYPE %s\n", stnum+1 >= NCH ? "int" : "unsigned char");
1034         (void) fprintf(fout,
1035         "struct yywork { YYTYPE verify, advance; } yycrank[] = {\n");
1036         for (i = 0; i <= yytop; i += 4) {
1037                 for (j = 0; j < 4; j++) {
1038                         k = i+j;
1039                         if (verify[k])
1040                                 (void) fprintf(fout,
1041                                 "%d,%d,\t", verify[k], advance[k]);
1042                         else
1043                                 (void) fprintf(fout, "0,0,\t");
1044                 }
1045                 (void) putc('\n', fout);
1046         }
1047         (void) fprintf(fout, "0,0};\n");
1048
1049         /* put out yysvec */
1050
1051         (void) fprintf(fout, "struct yysvf yysvec[] = {\n");
1052         (void) fprintf(fout, "0,\t0,\t0,\n");
1053         for (i = 0; i <= stnum; i++) {  /* for each state */
1054                 if (cpackflg[i])
1055                         stoff[i] = -stoff[i];
1056                 (void) fprintf(fout, "yycrank+%d,\t", stoff[i]);
1057                 if (sfall[i] != -1)
1058                         (void) fprintf(fout,
1059                         "yysvec+%d,\t", sfall[i]+1); /* state + 1 */
1060                 else
1061                         (void) fprintf(fout, "0,\t\t");
1062                 if (atable[i] != -1)
1063                         (void) fprintf(fout, "yyvstop+%d,", atable[i]);
1064                 else
1065                         (void) fprintf(fout, "0,\t");
1066 #ifdef DEBUG
1067                 (void) fprintf(fout, "\t\t/* state %d */", i);
1068 #endif
1069                 (void) putc('\n', fout);
1070         }
1071         (void) fprintf(fout, "0,\t0,\t0};\n");
1072
1073         /* put out yymatch */
1074
1075         (void) fprintf(fout, "struct yywork *yytop = yycrank+%d;\n", yytop);
1076         (void) fprintf(fout, "struct yysvf *yybgin = yysvec+1;\n");
1077         if (optim) {
1078                 if (handleeuc) {
1079                         (void) fprintf(fout, "int yymatch[] = {\n");
1080                 } else {
1081                         (void) fprintf(fout, "char yymatch[] = {\n");
1082                 }
1083                 if (chset == 0) { /* no chset, put out in normal order */
1084                         for (i = 0; i < ncg; i += 8) {
1085                                 for (j = 0; j < 8; j++) {
1086                                         int fbch;
1087                                         fbch = match[i+j];
1088                                         (void) fprintf(fout, "%3d, ", fbch);
1089                                 }
1090                                 (void) putc('\n', fout);
1091                         }
1092                 } else {
1093                         int *fbarr;
1094                         /*LINTED: E_BAD_PTR_CAST_ALIGN*/
1095                         fbarr = (int *)myalloc(2*MAXNCG, sizeof (*fbarr));
1096                         if (fbarr == 0)
1097                                 error("No space for char table reverse", 0);
1098                         for (i = 0; i < MAXNCG; i++)
1099                                 fbarr[i] = 0;
1100                         for (i = 0; i < ncg; i++)
1101                                 fbarr[ctable[i]] = ctable[match[i]];
1102                         for (i = 0; i < ncg; i += 8) {
1103                                 for (j = 0; j < 8; j++)
1104                                         (void) fprintf(fout, "0%-3o,",
1105                                             fbarr[i+j]);
1106                                 (void) putc('\n', fout);
1107                         }
1108                         free(fbarr);
1109                 }
1110                 (void) fprintf(fout, "0};\n");
1111         }
1112         /* put out yyextra */
1113         (void) fprintf(fout, "char yyextra[] = {\n");
1114         for (i = 0; i < casecount; i += 8) {
1115                 for (j = 0; j < 8; j++)
1116                         (void) fprintf(fout, "%d,", i+j < NACTIONS ?
1117                             extra[i+j] : 0);
1118                 (void) putc('\n', fout);
1119         }
1120         (void) fprintf(fout, "0};\n");
1121         if (handleeuc) {
1122                 /* Put out yycgidtbl */
1123                 (void) fprintf(fout, "#define YYNCGIDTBL %d\n", ncgidtbl);
1124                 (void) fprintf(fout, "\tunsigned long yycgidtbl[]={");
1125                 /*
1126                  * Use "unsigned long" instead of "lchar" to minimize
1127                  * the name-space polution for the application program.
1128                  */
1129                 for (i = 0; i < ncgidtbl; ++i) {
1130                         if (i%8 == 0)
1131                                 (void) fprintf(fout, "\n\t\t");
1132                         (void) fprintf(fout, "0x%08x, ",  (int)yycgidtbl[i]);
1133                 }
1134                 (void) fprintf(fout, "\n\t0};\n");
1135         }
1136 }
1137
1138 static void
1139 rprint(int *a, char *s, int n)
1140 {
1141         int i;
1142         (void) fprintf(fout, "block data\n");
1143         (void) fprintf(fout, "common /L%s/ %s\n", s, s);
1144         (void) fprintf(fout, "define S%s %d\n", s, n);
1145         (void) fprintf(fout, "integer %s (S%s)\n", s, s);
1146         for (i = 1; i <= n; i++) {
1147                 if (i%8 == 1)
1148                         (void) fprintf(fout, "data ");
1149                 (void) fprintf(fout, "%s (%d)/%d/", s, i, a[i]);
1150                 (void) fprintf(fout, (i%8 && i < n) ? ", " : "\n");
1151         }
1152         (void) fprintf(fout, "end\n");
1153 }
1154
1155 static void
1156 shiftr(int *a, int n)
1157 {
1158         int i;
1159         for (i = n; i >= 0; i--)
1160                 a[i+1] = a[i];
1161 }
1162
1163 static void
1164 upone(int *a, int n)
1165 {
1166         int i;
1167         for (i = 0; i <= n; i++)
1168                 a[i]++;
1169 }
1170
1171 static void
1172 bprint(char *a, char *s, int n)
1173 {
1174         int i, j, k;
1175         (void) fprintf(fout, "block data\n");
1176         (void) fprintf(fout, "common /L%s/ %s\n", s, s);
1177         (void) fprintf(fout, "define S%s %d\n", s, n);
1178         (void) fprintf(fout, "integer %s (S%s)\n", s, s);
1179         for (i = 1; i < n; i += 8) {
1180                 (void) fprintf(fout, "data %s (%d)/%d/", s, i, a[i]);
1181                 for (j = 1; j < 8; j++) {
1182                         k = i+j;
1183                         if (k < n)
1184                                 (void) fprintf(fout,
1185                                     ", %s (%d)/%d/", s, k, a[k]);
1186                 }
1187                 (void) putc('\n', fout);
1188         }
1189         (void) fprintf(fout, "end\n");
1190 }
1191
1192 #ifdef PP
1193 static void
1194 padd(int **array, int n)
1195 {
1196         int i, *j, k;
1197         array[n] = nxtpos;
1198         if (count == 0) {
1199                 *nxtpos++ = 0;
1200                 return;
1201         }
1202         for (i = tptr-1; i >= 0; i--) {
1203                 j = array[i];
1204                 if (j && *j++ == count) {
1205                         for (k = 0; k < count; k++)
1206                                 if (!tmpstat[*j++])
1207                                         break;
1208                         if (k >= count) {
1209                                 array[n] = array[i];
1210                                 return;
1211                         }
1212                 }
1213         }
1214         add(array, n);
1215 }
1216 #endif