sys/src/cmd/lex/sub2.c

   1 # include "ldefs.h"
   2 void
   3 cfoll(int v)
   4 {
   5         int i,j,k;
   6         uchar *p;
   7         i = name[v];
   8         if(i < NCH) i = 1;      /* character */
   9         switch(i){
  10                 case 1: case RSTR: case RCCL: case RNCCL: case RNULLS:
  11                         for(j=0;j<tptr;j++)
  12                                 tmpstat[j] = FALSE;
  13                         count = 0;
  14                         follow(v);
  15 # ifdef PP
  16                         padd(foll,v);           /* packing version */
  17 # endif
  18 # ifndef PP
  19                         add(foll,v);            /* no packing version */
  20 # endif
  21                         if(i == RSTR) cfoll(left[v]);
  22                         else if(i == RCCL || i == RNCCL){       /* compress ccl list */
  23                                 for(j=1; j<NCH;j++)
  24                                         symbol[j] = (i==RNCCL);
  25                                 p = ptr[v];
  26                                 while(*p)
  27                                         symbol[*p++] = (i == RCCL);
  28                                 p = pcptr;
  29                                 for(j=1;j<NCH;j++)
  30                                         if(symbol[j]){
  31                                                 for(k=0;p+k < pcptr; k++)
  32                                                         if(cindex[j] == *(p+k))
  33                                                                 break;
  34                                                 if(p+k >= pcptr)*pcptr++ = cindex[j];
  35                                         }
  36                                 *pcptr++ = 0;
  37                                 if(pcptr > pchar + pchlen)
  38                                         error("Too many packed character classes");
  39                                 ptr[v] = p;
  40                                 name[v] = RCCL; /* RNCCL eliminated */
  41 # ifdef DEBUG
  42                                 if(debug && *p){
  43                                         print("ccl %d: %d",v,*p++);
  44                                         while(*p)
  45                                                 print(", %d",*p++);
  46                                         print("\n");
  47                                 }
  48 # endif
  49                         }
  50                         break;
  51                 case CARAT:
  52                         cfoll(left[v]);
  53                         break;
  54                 case STAR: case PLUS: case QUEST: case RSCON:
  55                         cfoll(left[v]);
  56                         break;
  57                 case BAR: case RCAT: case DIV: case RNEWE:
  58                         cfoll(left[v]);
  59                         cfoll(right[v]);
  60                         break;
  61 # ifdef DEBUG
  62                 case FINAL:
  63                 case S1FINAL:
  64                 case S2FINAL:
  65                         break;
  66                 default:
  67                         warning("bad switch cfoll %d",v);
  68 # endif
  69         }
  70 }
  71
  72 # ifdef DEBUG
  73 void
  74 pfoll(void)
  75         {
  76         int i,k,*p;
  77         int j;
  78         /* print sets of chars which may follow positions */
  79         print("pos\tchars\n");
  80         for(i=0;i<tptr;i++)
  81                 if(p=foll[i]){
  82                         j = *p++;
  83                         if(j >= 1){
  84                                 print("%d:\t%d",i,*p++);
  85                                 for(k=2;k<=j;k++)
  86                                         print(", %d",*p++);
  87                                 print("\n");
  88                         }
  89                 }
  90 }
  91 # endif
  92
  93 void
  94 add(int **array, int n)
  95 {
  96         int i, *temp;
  97         uchar *ctemp;
  98
  99         temp = nxtpos;
 100         ctemp = tmpstat;
 101         array[n] = nxtpos;              /* note no packing is done in positions */
 102         *temp++ = count;
 103         for(i=0;i<tptr;i++)
 104                 if(ctemp[i] == TRUE)
 105                         *temp++ = i;
 106         nxtpos = temp;
 107         if(nxtpos >= positions+maxpos)
 108                 error("Too many positions %s",(maxpos== MAXPOS?"\nTry using %p num":""));
 109 }
 110
 111 void
 112 follow(int v)
 113 {
 114         int p;
 115         if(v >= tptr-1)return;
 116         p = parent[v];
 117         if(p == 0) return;
 118         switch(name[p]){
 119                         /* will not be CHAR RNULLS FINAL S1FINAL S2FINAL RCCL RNCCL */
 120                 case RSTR:
 121                         if(tmpstat[p] == FALSE){
 122                                 count++;
 123                                 tmpstat[p] = TRUE;
 124                         }
 125                         break;
 126                 case STAR: case PLUS:
 127                         first(v);
 128                         follow(p);
 129                         break;
 130                 case BAR: case QUEST: case RNEWE:
 131                         follow(p);
 132                         break;
 133                 case RCAT: case DIV:
 134                         if(v == left[p]){
 135                                 if(nullstr[right[p]])
 136                                         follow(p);
 137                                 first(right[p]);
 138                         }
 139                         else follow(p);
 140                         break;
 141                 case RSCON: case CARAT:
 142                         follow(p);
 143                         break;
 144 # ifdef DEBUG
 145                 default:
 146                         warning("bad switch follow %d",p);
 147 # endif
 148         }
 149 }
 150
 151 void
 152 first(int v)    /* calculate set of positions with v as root which can be active initially */
 153 {
 154         int i;
 155         uchar *p;
 156         i = name[v];
 157         if(i < NCH)i = 1;
 158         switch(i){
 159                 case 1: case RCCL: case RNCCL: case RNULLS: case FINAL: case S1FINAL: case S2FINAL:
 160                         if(tmpstat[v] == FALSE){
 161                                 count++;
 162                                 tmpstat[v] = TRUE;
 163                         }
 164                         break;
 165                 case BAR: case RNEWE:
 166                         first(left[v]);
 167                         first(right[v]);
 168                         break;
 169                 case CARAT:
 170                         if(stnum % 2 == 1)
 171                                 first(left[v]);
 172                         break;
 173                 case RSCON:
 174                         i = stnum/2 +1;
 175                         p = (uchar *)right[v];
 176                         while(*p)
 177                                 if(*p++ == i){
 178                                         first(left[v]);
 179                                         break;
 180                                 }
 181                         break;
 182                 case STAR: case QUEST: case PLUS:  case RSTR:
 183                         first(left[v]);
 184                         break;
 185                 case RCAT: case DIV:
 186                         first(left[v]);
 187                         if(nullstr[left[v]])
 188                                 first(right[v]);
 189                         break;
 190 # ifdef DEBUG
 191                 default:
 192                         warning("bad switch first %d",v);
 193 # endif
 194         }
 195 }
 196
 197 void
 198 cgoto(void)
 199 {
 200         int i, j, s;
 201         int npos, curpos, n;
 202         int tryit;
 203         uchar tch[NCH];
 204         int tst[NCH];
 205         uchar *q;
 206
 207         /* generate initial state, for each start condition */
 208         Bprint(&fout,"int yyvstop[] = {\n0,\n");
 209         while(stnum < 2 || stnum/2 < sptr){
 210                 for(i = 0; i<tptr; i++) tmpstat[i] = 0;
 211                 count = 0;
 212                 if(tptr > 0)first(tptr-1);
 213                 add(state,stnum);
 214 # ifdef DEBUG
 215                 if(debug){
 216                         if(stnum > 1)
 217                                 print("%s:\n",sname[stnum/2]);
 218                         pstate(stnum);
 219                 }
 220 # endif
 221                 stnum++;
 222         }
 223         stnum--;
 224         /* even stnum = might not be at line begin */
 225         /* odd stnum  = must be at line begin */
 226         /* even states can occur anywhere, odd states only at line begin */
 227         for(s = 0; s <= stnum; s++){
 228                 tryit = FALSE;
 229                 cpackflg[s] = FALSE;
 230                 sfall[s] = -1;
 231                 acompute(s);
 232                 for(i=0;i<NCH;i++) symbol[i] = 0;
 233                 npos = *state[s];
 234                 for(i = 1; i<=npos; i++){
 235                         curpos = *(state[s]+i);
 236                         if(name[curpos] < NCH) symbol[name[curpos]] = TRUE;
 237                         else switch(name[curpos]){
 238                         case RCCL:
 239                                 tryit = TRUE;
 240                                 q = ptr[curpos];
 241                                 while(*q){
 242                                         for(j=1;j<NCH;j++)
 243                                                 if(cindex[j] == *q)
 244                                                         symbol[j] = TRUE;
 245                                         q++;
 246                                 }
 247                                 break;
 248                         case RSTR:
 249                                 symbol[right[curpos]] = TRUE;
 250                                 break;
 251 # ifdef DEBUG
 252                         case RNULLS:
 253                         case FINAL:
 254                         case S1FINAL:
 255                         case S2FINAL:
 256                                 break;
 257                         default:
 258                                 warning("bad switch cgoto %d state %d",curpos,s);
 259                                 break;
 260 # endif
 261                         }
 262                 }
 263 # ifdef DEBUG
 264                 if(debug){
 265                         print("State %d transitions on:\n\t",s);
 266                         charc = 0;
 267                         for(i = 1; i<NCH; i++){
 268                                 if(symbol[i]) allprint(i);
 269                                 if(charc > LINESIZE){
 270                                         charc = 0;
 271                                         print("\n\t");
 272                                 }
 273                         }
 274                         print("\n");
 275                 }
 276 # endif
 277                 /* for each char, calculate next state */
 278                 n = 0;
 279                 for(i = 1; i<NCH; i++){
 280                         if(symbol[i]){
 281                                 nextstate(s,i);         /* executed for each state, transition pair */
 282                                 xstate = notin(stnum);
 283                                 if(xstate == -2) warning("bad state  %d %o",s,i);
 284                                 else if(xstate == -1){
 285                                         if(stnum >= nstates)
 286                                                 error("Too many states %s",(nstates == NSTATES ? "\nTry using %n num":""));
 287                                         add(state,++stnum);
 288 # ifdef DEBUG
 289                                         if(debug)pstate(stnum);
 290 # endif
 291                                         tch[n] = i;
 292                                         tst[n++] = stnum;
 293                                 } else {                /* xstate >= 0 ==> state exists */
 294                                         tch[n] = i;
 295                                         tst[n++] = xstate;
 296                                 }
 297                         }
 298                 }
 299                 tch[n] = 0;
 300                 tst[n] = -1;
 301                 /* pack transitions into permanent array */
 302                 if(n > 0) packtrans(s,tch,tst,n,tryit);
 303                 else gotof[s] = -1;
 304         }
 305         Bprint(&fout,"0};\n");
 306 }
 307
 308 /*      Beware -- 70% of total CPU time is spent in this subroutine -
 309         if you don't believe me - try it yourself ! */
 310 void
 311 nextstate(int s, int c)
 312 {
 313         int j, *newpos;
 314         uchar *temp, *tz;
 315         int *pos, i, *f, num, curpos, number;
 316         /* state to goto from state s on char c */
 317         num = *state[s];
 318         temp = tmpstat;
 319         pos = state[s] + 1;
 320         for(i = 0; i<num; i++){
 321                 curpos = *pos++;
 322                 j = name[curpos];
 323                 if(j < NCH && j == c
 324                 || j == RSTR && c == right[curpos]
 325                 || j == RCCL && member(c, ptr[curpos])){
 326                         f = foll[curpos];
 327                         number = *f;
 328                         newpos = f+1;
 329                         for(j=0;j<number;j++)
 330                                 temp[*newpos++] = 2;
 331                 }
 332         }
 333         j = 0;
 334         tz = temp + tptr;
 335         while(temp < tz){
 336                 if(*temp == 2){
 337                         j++;
 338                         *temp++ = 1;
 339                 }
 340                 else *temp++ = 0;
 341         }
 342         count = j;
 343 }
 344
 345 int
 346 notin(int n)
 347 {       /* see if tmpstat occurs previously */
 348         int *j,k;
 349         uchar *temp;
 350         int i;
 351
 352         if(count == 0)
 353                 return(-2);
 354         temp = tmpstat;
 355         for(i=n;i>=0;i--){      /* for each state */
 356                 j = state[i];
 357                 if(count == *j++){
 358                         for(k=0;k<count;k++)
 359                                 if(!temp[*j++])break;
 360                         if(k >= count)
 361                                 return(i);
 362                 }
 363         }
 364         return(-1);
 365 }
 366
 367 void
 368 packtrans(int st, uchar *tch, int *tst, int cnt, int tryit)
 369 {
 370         /* pack transitions into nchar, nexts */
 371         /* nchar is terminated by '\0', nexts uses cnt, followed by elements */
 372         /* gotof[st] = index into nchr, nexts for state st */
 373
 374         /* sfall[st] =  t implies t is fall back state for st */
 375         /*              == -1 implies no fall back */
 376
 377         int i,j,k;
 378         int cmin, cval, tcnt, diff, p, *ast;
 379         uchar *ach;
 380         int go[NCH], temp[NCH], c;
 381         int swork[NCH];
 382         uchar cwork[NCH];
 383         int upper;
 384
 385         rcount += cnt;
 386         cmin = -1;
 387         cval = NCH;
 388         ast = tst;
 389         ach = tch;
 390         /* try to pack transitions using ccl's */
 391         if(tryit){      /* ccl's used */
 392                 for(i=1;i<NCH;i++){
 393                         go[i] = temp[i] = -1;
 394                         symbol[i] = 1;
 395                 }
 396                 for(i=0;i<cnt;i++){
 397                         go[tch[i]] = tst[i];
 398                         symbol[tch[i]] = 0;
 399                 }
 400                 for(i=0; i<cnt;i++){
 401                         c = match[tch[i]];
 402                         if(go[c] != tst[i] || c == tch[i])
 403                                 temp[tch[i]] = tst[i];
 404                 }
 405                 /* fill in error entries */
 406                 for(i=1;i<NCH;i++)
 407                         if(symbol[i]) temp[i] = -2;     /* error trans */
 408                 /* count them */
 409                 k = 0;
 410                 for(i=1;i<NCH;i++)
 411                         if(temp[i] != -1)k++;
 412                 if(k <cnt){     /* compress by char */
 413 # ifdef DEBUG
 414                         if(debug) print("use compression  %d,  %d vs %d\n",st,k,cnt);
 415 # endif
 416                         k = 0;
 417                         for(i=1;i<NCH;i++)
 418                                 if(temp[i] != -1){
 419                                         cwork[k] = i;
 420                                         swork[k++] = (temp[i] == -2 ? -1 : temp[i]);
 421                                 }
 422                         cwork[k] = 0;
 423 # ifdef PC
 424                         ach = cwork;
 425                         ast = swork;
 426                         cnt = k;
 427                         cpackflg[st] = TRUE;
 428 # endif
 429                 }
 430         }
 431         for(i=0; i<st; i++){    /* get most similar state */
 432                                 /* reject state with more transitions, state already represented by a third state,
 433                                         and state which is compressed by char if ours is not to be */
 434                 if(sfall[i] != -1) continue;
 435                 if(cpackflg[st] == 1) if(!(cpackflg[i] == 1)) continue;
 436                 p = gotof[i];
 437                 if(p == -1) /* no transitions */ continue;
 438                 tcnt = nexts[p];
 439                 if(tcnt > cnt) continue;
 440                 diff = 0;
 441                 j = 0;
 442                 upper = p + tcnt;
 443                 while(ach[j] && p < upper){
 444                         while(ach[j] < nchar[p] && ach[j]){diff++; j++; }
 445                         if(ach[j] == 0)break;
 446                         if(ach[j] > nchar[p]){diff=NCH;break;}
 447                         /* ach[j] == nchar[p] */
 448                         if(ast[j] != nexts[++p] || ast[j] == -1 || (cpackflg[st] && ach[j] != match[ach[j]]))diff++;
 449                         j++;
 450                 }
 451                 while(ach[j]){
 452                         diff++;
 453                         j++;
 454                 }
 455                 if(p < upper)diff = NCH;
 456                 if(diff < cval && diff < tcnt){
 457                         cval = diff;
 458                         cmin = i;
 459                         if(cval == 0)break;
 460                 }
 461         }
 462         /* cmin = state "most like" state st */
 463 # ifdef DEBUG
 464         if(debug)print("select st %d for st %d diff %d\n",cmin,st,cval);
 465 # endif
 466 # ifdef PS
 467         if(cmin != -1){ /* if we can use st cmin */
 468                 gotof[st] = nptr;
 469                 k = 0;
 470                 sfall[st] = cmin;
 471                 p = gotof[cmin]+1;
 472                 j = 0;
 473                 while(ach[j]){
 474                         /* if cmin has a transition on c, then so will st */
 475                         /* st may be "larger" than cmin, however */
 476                         while(ach[j] < nchar[p-1] && ach[j]){
 477                                 k++;
 478                                 nchar[nptr] = ach[j];
 479                                 nexts[++nptr] = ast[j];
 480                                 j++;
 481                         }
 482                         if(nchar[p-1] == 0)break;
 483                         if(ach[j] > nchar[p-1]){
 484                                 warning("bad transition %d %d",st,cmin);
 485                                 goto nopack;
 486                         }
 487                         /* ach[j] == nchar[p-1] */
 488                         if(ast[j] != nexts[p] || ast[j] == -1 || (cpackflg[st] && ach[j] != match[ach[j]])){
 489                                 k++;
 490                                 nchar[nptr] = ach[j];
 491                                 nexts[++nptr] = ast[j];
 492                         }
 493                         p++;
 494                         j++;
 495                 }
 496                 while(ach[j]){
 497                         nchar[nptr] = ach[j];
 498                         nexts[++nptr] = ast[j++];
 499                         k++;
 500                 }
 501                 nexts[gotof[st]] = cnt = k;
 502                 nchar[nptr++] = 0;
 503         } else {
 504 # endif
 505 nopack:
 506         /* stick it in */
 507                 gotof[st] = nptr;
 508                 nexts[nptr] = cnt;
 509                 for(i=0;i<cnt;i++){
 510                         nchar[nptr] = ach[i];
 511                         nexts[++nptr] = ast[i];
 512                 }
 513                 nchar[nptr++] = 0;
 514 # ifdef PS
 515         }
 516 # endif
 517         if(cnt < 1){
 518                 gotof[st] = -1;
 519                 nptr--;
 520         } else
 521                 if(nptr > ntrans)
 522                         error("Too many transitions %s",(ntrans==NTRANS?"\nTry using %a num":""));
 523 }
 524
 525 # ifdef DEBUG
 526 void
 527 pstate(int s)
 528 {
 529         int *p,i,j;
 530         print("State %d:\n",s);
 531         p = state[s];
 532         i = *p++;
 533         if(i == 0) return;
 534         print("%4d",*p++);
 535         for(j = 1; j<i; j++){
 536                 print(", %4d",*p++);
 537                 if(j%30 == 0)print("\n");
 538         }
 539         print("\n");
 540 }
 541 # endif
 542
 543 int
 544 member(int d, uchar *t)
 545 {
 546         int c;
 547         uchar *s;
 548
 549         c = d;
 550         s = t;
 551         c = cindex[c];
 552         while(*s)
 553                 if(*s++ == c) return(1);
 554         return(0);
 555 }
 556
 557 # ifdef DEBUG
 558 void
 559 stprt(int i)
 560 {
 561         int p, t;
 562
 563         print("State %d:",i);
 564         /* print actions, if any */
 565         t = atable[i];
 566         if(t != -1)print(" final");
 567         print("\n");
 568         if(cpackflg[i] == TRUE)print("backup char in use\n");
 569         if(sfall[i] != -1)print("fall back state %d\n",sfall[i]);
 570         p = gotof[i];
 571         if(p == -1) return;
 572         print("(%d transitions)\n",nexts[p]);
 573         while(nchar[p]){
 574                 charc = 0;
 575                 if(nexts[p+1] >= 0)
 576                         print("%d\t",nexts[p+1]);
 577                 else print("err\t");
 578                 allprint(nchar[p++]);
 579                 while(nexts[p] == nexts[p+1] && nchar[p]){
 580                         if(charc > LINESIZE){
 581                                 charc = 0;
 582                                 print("\n\t");
 583                         }
 584                         allprint(nchar[p++]);
 585                 }
 586                 print("\n");
 587         }
 588         print("\n");
 589 }
 590 # endif
 591
 592 void
 593 acompute(int s) /* compute action list = set of poss. actions */
 594 {
 595         int *p, i, j;
 596         int cnt, m;
 597         int temp[300], k, neg[300], n;
 598
 599         k = 0;
 600         n = 0;
 601         p = state[s];
 602         cnt = *p++;
 603         if(cnt > 300)
 604                 error("Too many positions for one state - acompute");
 605         for(i=0;i<cnt;i++){
 606                 if(name[*p] == FINAL)temp[k++] = left[*p];
 607                 else if(name[*p] == S1FINAL){temp[k++] = left[*p];
 608                         if (left[*p] >= NACTIONS) error("Too many right contexts");
 609                         extra[left[*p]] = 1;
 610                 } else if(name[*p] == S2FINAL)neg[n++] = left[*p];
 611                 p++;
 612         }
 613         atable[s] = -1;
 614         if(k < 1 && n < 1) return;
 615 # ifdef DEBUG
 616         if(debug) print("final %d actions:",s);
 617 # endif
 618         /* sort action list */
 619         for(i=0; i<k; i++)
 620                 for(j=i+1;j<k;j++)
 621                         if(temp[j] < temp[i]){
 622                                 m = temp[j];
 623                                 temp[j] = temp[i];
 624                                 temp[i] = m;
 625                         }
 626         /* remove dups */
 627         for(i=0;i<k-1;i++)
 628                 if(temp[i] == temp[i+1]) temp[i] = 0;
 629         /* copy to permanent quarters */
 630         atable[s] = aptr;
 631 # ifdef DEBUG
 632         Bprint(&fout,"/* actions for state %d */",s);
 633 # endif
 634         Bputc(&fout, '\n');
 635         for(i=0;i<k;i++)
 636                 if(temp[i] != 0){
 637                         Bprint(&fout,"%d,\n",temp[i]);
 638 # ifdef DEBUG
 639                         if(debug)
 640                                 print("%d ",temp[i]);
 641 # endif
 642                         aptr++;
 643                 }
 644         for(i=0;i<n;i++){               /* copy fall back actions - all neg */
 645                 Bprint(&fout,"%d,\n",neg[i]);
 646                 aptr++;
 647 # ifdef DEBUG
 648                 if(debug)print("%d ",neg[i]);
 649 # endif
 650         }
 651 # ifdef DEBUG
 652         if(debug)print("\n");
 653 # endif
 654         Bprint(&fout,"0,\n");
 655         aptr++;
 656 }
 657
 658 # ifdef DEBUG
 659 void
 660 pccl(void) {
 661         /* print character class sets */
 662         int i, j;
 663
 664         print("char class intersection\n");
 665         for(i=0; i< ccount; i++){
 666                 charc = 0;
 667                 print("class %d:\n\t",i);
 668                 for(j=1;j<NCH;j++)
 669                         if(cindex[j] == i){
 670                                 allprint(j);
 671                                 if(charc > LINESIZE){
 672                                         print("\n\t");
 673                                         charc = 0;
 674                                 }
 675                         }
 676                 print("\n");
 677         }
 678         charc = 0;
 679         print("match:\n");
 680         for(i=0;i<NCH;i++){
 681                 allprint(match[i]);
 682                 if(charc > LINESIZE){
 683                         print("\n");
 684                         charc = 0;
 685                 }
 686         }
 687         print("\n");
 688 }
 689 # endif
 690
 691 void
 692 mkmatch(void)
 693 {
 694         int i;
 695         uchar tab[NCH];
 696
 697         for(i=0; i<ccount; i++)
 698                 tab[i] = 0;
 699         for(i=1;i<NCH;i++)
 700                 if(tab[cindex[i]] == 0)
 701                         tab[cindex[i]] = i;
 702         /* tab[i] = principal char for new ccl i */
 703         for(i = 1; i<NCH; i++)
 704                 match[i] = tab[cindex[i]];
 705 }
 706
 707 void
 708 layout(void)
 709 {
 710         /* format and output final program's tables */
 711         int i, j, k;
 712         int  top, bot, startup, omin;
 713
 714         for(i=0; i<outsize;i++)
 715                 verify[i] = advance[i] = 0;
 716         omin = 0;
 717         yytop = 0;
 718         for(i=0; i<= stnum; i++){       /* for each state */
 719                 j = gotof[i];
 720                 if(j == -1){
 721                         stoff[i] = 0;
 722                         continue;
 723                         }
 724                 bot = j;
 725                 while(nchar[j])j++;
 726                 top = j - 1;
 727 # ifdef DEBUG
 728                 if (debug) {
 729                         print("State %d: (layout)\n", i);
 730                         for(j=bot; j<=top;j++) {
 731                                 print("  %o", nchar[j]);
 732                                 if (j%10==0) print("\n");
 733                         }
 734                         print("\n");
 735                 }
 736 # endif
 737                 while(verify[omin+NCH]) omin++;
 738                 startup = omin;
 739 # ifdef DEBUG
 740                 if (debug) print("bot,top %d, %d startup begins %d\n",bot,top,startup);
 741 # endif
 742                 do {
 743                         startup += 1;
 744                         if(startup > outsize - NCH)
 745                                 error("output table overflow");
 746                         for(j = bot; j<= top; j++){
 747                                 k = startup + nchar[j];
 748                                 if(verify[k])break;
 749                         }
 750                 } while (j <= top);
 751                 /* have found place */
 752 # ifdef DEBUG
 753                 if (debug) print(" startup going to be %d\n", startup);
 754 # endif
 755                 for(j = bot; j<= top; j++){
 756                         k = startup + nchar[j];
 757                         verify[k] = i+1;                        /* state number + 1*/
 758                         advance[k] = nexts[j+1]+1;              /* state number + 1*/
 759                         if(yytop < k) yytop = k;
 760                 }
 761                 stoff[i] = startup;
 762         }
 763
 764         /* stoff[i] = offset into verify, advance for trans for state i */
 765         /* put out yywork */
 766         Bprint(&fout,"# define YYTYPE %s\n",stnum+1 >= NCH ? "int" : "Uchar");
 767         Bprint(&fout,"struct yywork { YYTYPE verify, advance; } yycrank[] = {\n");
 768         for(i=0;i<=yytop;i+=4){
 769                 for(j=0;j<4;j++){
 770                         k = i+j;
 771                         if(verify[k])
 772                                 Bprint(&fout,"%d,%d,\t",verify[k],advance[k]);
 773                         else
 774                                 Bprint(&fout,"0,0,\t");
 775                 }
 776                 Bputc(&fout, '\n');
 777         }
 778         Bprint(&fout,"0,0};\n");
 779
 780         /* put out yysvec */
 781
 782         Bprint(&fout,"struct yysvf yysvec[] = {\n");
 783         Bprint(&fout,"0,\t0,\t0,\n");
 784         for(i=0;i<=stnum;i++){  /* for each state */
 785                 if(cpackflg[i])stoff[i] = -stoff[i];
 786                 Bprint(&fout,"yycrank+%d,\t",stoff[i]);
 787                 if(sfall[i] != -1)
 788                         Bprint(&fout,"yysvec+%d,\t", sfall[i]+1);       /* state + 1 */
 789                 else Bprint(&fout,"0,\t\t");
 790                 if(atable[i] != -1)
 791                         Bprint(&fout,"yyvstop+%d,",atable[i]);
 792                 else Bprint(&fout,"0,\t");
 793 # ifdef DEBUG
 794                 Bprint(&fout,"\t\t/* state %d */",i);
 795 # endif
 796                 Bputc(&fout, '\n');
 797         }
 798         Bprint(&fout,"0,\t0,\t0};\n");
 799
 800         /* put out yymatch */
 801
 802         Bprint(&fout,"struct yywork *yytop = yycrank+%d;\n",yytop);
 803         Bprint(&fout,"struct yysvf *yybgin = yysvec+1;\n");
 804         Bprint(&fout,"Uchar yymatch[] = {\n");
 805         for(i=0; i<NCH; i+=8){
 806                 for(j=0; j<8; j++){
 807                         int fbch;
 808                         fbch = match[i+j];
 809                         if(isprint(fbch) && fbch != '\'' && fbch != '\\')
 810                                 Bprint(&fout,"'%c' ,",fbch);
 811                         else Bprint(&fout,"0%-3o,",fbch);
 812                 }
 813                 Bputc(&fout, '\n');
 814         }
 815         Bprint(&fout,"0};\n");
 816         /* put out yyextra */
 817         Bprint(&fout,"Uchar yyextra[] = {\n");
 818         for(i=0;i<casecount;i+=8){
 819                 for(j=0;j<8;j++)
 820                         Bprint(&fout, "%d,", i+j<NACTIONS ?
 821                                 extra[i+j] : 0);
 822                 Bputc(&fout, '\n');
 823         }
 824         Bprint(&fout,"0};\n");
 825 }
 826
 827 # ifdef PP
 828 void
 829 padd(int **array, int n)
 830 {
 831         int i, *j, k;
 832
 833         array[n] = nxtpos;
 834         if(count == 0){
 835                 *nxtpos++ = 0;
 836                 return;
 837         }
 838         for(i=tptr-1;i>=0;i--){
 839                 j = array[i];
 840                 if(j && *j++ == count){
 841                         for(k=0;k<count;k++)
 842                                 if(!tmpstat[*j++])break;
 843                         if(k >= count){
 844                                 array[n] = array[i];
 845                                 return;
 846                         }
 847                 }
 848         }
 849         add(array,n);
 850 }
 851 # endif