home *** CD-ROM | disk | FTP | other *** search
/ minnie.tuhs.org / unixen.tar / unixen / PDP-11 / Trees / V7 / usr / src / cmd / lex / sub2.c < prev   
Encoding:
C/C++ Source or Header  |  1979-01-10  |  20.0 KB  |  952 lines
  1. # include "ldefs.c"
  2. cfoll(v)
  3.     int v;
  4.     {
  5.     register int i,j,k;
  6.     char *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 = left[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.                 left[v] = p;
  40.                 name[v] = RCCL;    /* RNCCL eliminated */
  41. # ifdef DEBUG
  42.                 if(debug && *p){
  43.                     printf("ccl %d: %d",v,*p++);
  44.                     while(*p)
  45.                         printf(", %d",*p++);
  46.                     putchar('\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.     return;
  71.     }
  72. # ifdef DEBUG
  73. pfoll()
  74.     {
  75.     register int i,k,*p;
  76.     int j;
  77.     /* print sets of chars which may follow positions */
  78.     printf("pos\tchars\n");
  79.     for(i=0;i<tptr;i++)
  80.         if(p=foll[i]){
  81.             j = *p++;
  82.             if(j >= 1){
  83.                 printf("%d:\t%d",i,*p++);
  84.                 for(k=2;k<=j;k++)
  85.                     printf(", %d",*p++);
  86.                 putchar('\n');
  87.                 }
  88.             }
  89.     return;
  90.     }
  91. # endif
  92. add(array,n)
  93.   int **array;
  94.   int n; {
  95.     register int i, *temp;
  96.     register char *ctemp;
  97.     temp = nxtpos;
  98.     ctemp = tmpstat;
  99.     array[n] = nxtpos;        /* note no packing is done in positions */
  100.     *temp++ = count;
  101.     for(i=0;i<tptr;i++)
  102.         if(ctemp[i] == TRUE)
  103.             *temp++ = i;
  104.     nxtpos = temp;
  105.     if(nxtpos >= positions+maxpos)
  106.         error("Too many positions %s",(maxpos== MAXPOS?"\nTry using %p num":""));
  107.     return;
  108.     }
  109. follow(v)
  110.   int v;
  111.     {
  112.     register int p;
  113.     if(v >= tptr-1)return;
  114.     p = parent[v];
  115.     if(p == 0) return;
  116.     switch(name[p]){
  117.             /* will not be CHAR RNULLS FINAL S1FINAL S2FINAL RCCL RNCCL */
  118.         case RSTR:
  119.             if(tmpstat[p] == FALSE){
  120.                 count++;
  121.                 tmpstat[p] = TRUE;
  122.                 }
  123.             break;
  124.         case STAR: case PLUS:
  125.             first(v);
  126.             follow(p);
  127.             break;
  128.         case BAR: case QUEST: case RNEWE:
  129.             follow(p);
  130.             break;
  131.         case RCAT: case DIV: 
  132.             if(v == left[p]){
  133.                 if(nullstr[right[p]])
  134.                     follow(p);
  135.                 first(right[p]);
  136.                 }
  137.             else follow(p);
  138.             break;
  139.         case RSCON: case CARAT: 
  140.             follow(p);
  141.             break;
  142. # ifdef DEBUG
  143.         default:
  144.             warning("bad switch follow %d",p);
  145. # endif
  146.         }
  147.     return;
  148.     }
  149. first(v)    /* calculate set of positions with v as root which can be active initially */
  150.   int v; {
  151.     register int i;
  152.     register char *p;
  153.     i = name[v];
  154.     if(i < NCH)i = 1;
  155.     switch(i){
  156.         case 1: case RCCL: case RNCCL: case RNULLS: case FINAL: case S1FINAL: case S2FINAL:
  157.             if(tmpstat[v] == FALSE){
  158.                 count++;
  159.                 tmpstat[v] = TRUE;
  160.                 }
  161.             break;
  162.         case BAR: case RNEWE:
  163.             first(left[v]);
  164.             first(right[v]);
  165.             break;
  166.         case CARAT:
  167.             if(stnum % 2 == 1)
  168.                 first(left[v]);
  169.             break;
  170.         case RSCON:
  171.             i = stnum/2 +1;
  172.             p = right[v];
  173.             while(*p)
  174.                 if(*p++ == i){
  175.                     first(left[v]);
  176.                     break;
  177.                     }
  178.             break;
  179.         case STAR: case QUEST: case PLUS:  case RSTR:
  180.             first(left[v]);
  181.             break;
  182.         case RCAT: case DIV:
  183.             first(left[v]);
  184.             if(nullstr[left[v]])
  185.                 first(right[v]);
  186.             break;
  187. # ifdef DEBUG
  188.         default:
  189.             warning("bad switch first %d",v);
  190. # endif
  191.         }
  192.     return;
  193.     }
  194. cgoto(){
  195.     register int i, j, s;
  196.     int npos, curpos, n;
  197.     int tryit;
  198.     char tch[NCH];
  199.     int tst[NCH];
  200.     char *q;
  201.     /* generate initial state, for each start condition */
  202.     if(ratfor){
  203.         fprintf(fout,"blockdata\n");
  204.         fprintf(fout,"common /Lvstop/ vstop\n");
  205.         fprintf(fout,"define Svstop %d\n",nstates+1);
  206.         fprintf(fout,"integer vstop(Svstop)\n");
  207.         }
  208.     else fprintf(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.                 printf("%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 = left[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.             printf("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.                     printf("\n\t");
  272.                     }
  273.                 }
  274.             putchar('\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.                     }
  294.                 else {        /* xstate >= 0 ==> state exists */
  295.                     tch[n] = i;
  296.                     tst[n++] = xstate;
  297.                     }
  298.                 }
  299.             }
  300.         tch[n] = 0;
  301.         tst[n] = -1;
  302.         /* pack transitions into permanent array */
  303.         if(n > 0) packtrans(s,tch,tst,n,tryit);
  304.         else gotof[s] = -1;
  305.         }
  306.     ratfor ? fprintf(fout,"end\n") : fprintf(fout,"0};\n");
  307.     return;
  308.     }
  309.     /*    Beware -- 70% of total CPU time is spent in this subroutine -
  310.         if you don't believe me - try it yourself ! */
  311. nextstate(s,c)
  312.   int s,c; {
  313.     register int j, *newpos;
  314.     register char *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,left[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.     return;
  344.     }
  345. notin(n)
  346.   int n;    {    /* see if tmpstat occurs previously */
  347.     register int *j,k;
  348.     register char *temp;
  349.     int i;
  350.     if(count == 0)
  351.         return(-2);
  352.     temp = tmpstat;
  353.     for(i=n;i>=0;i--){    /* for each state */
  354.         j = state[i];
  355.         if(count == *j++){
  356.             for(k=0;k<count;k++)
  357.                 if(!temp[*j++])break;
  358.             if(k >= count)
  359.                 return(i);
  360.             }
  361.         }
  362.     return(-1);
  363.     }
  364. packtrans(st,tch,tst,cnt,tryit)
  365.   int st, *tst, cnt,tryit;
  366.   char *tch; {
  367.     /* pack transitions into nchar, nexts */
  368.     /* nchar is terminated by '\0', nexts uses cnt, followed by elements */
  369.     /* gotof[st] = index into nchr, nexts for state st */
  370.  
  371.     /* sfall[st] =  t implies t is fall back state for st */
  372.     /*            == -1 implies no fall back */
  373.  
  374.     int cmin, cval, tcnt, diff, p, *ast;
  375.     register int i,j,k;
  376.     char *ach;
  377.     int go[NCH], temp[NCH], c;
  378.     int swork[NCH];
  379.     char cwork[NCH];
  380.     int upper;
  381.  
  382.     rcount =+ cnt;
  383.     cmin = -1;
  384.     cval = NCH;
  385.     ast = tst;
  386.     ach = tch;
  387.     /* try to pack transitions using ccl's */
  388.     if(!optim)goto nopack;        /* skip all compaction */
  389.     if(tryit){    /* ccl's used */
  390.         for(i=1;i<NCH;i++){
  391.             go[i] = temp[i] = -1;
  392.             symbol[i] = 1;
  393.             }
  394.         for(i=0;i<cnt;i++){
  395.             go[tch[i]] = tst[i];
  396.             symbol[tch[i]] = 0;
  397.             }
  398.         for(i=0; i<cnt;i++){
  399.             c = match[tch[i]];
  400.             if(go[c] != tst[i] || c == tch[i])
  401.                 temp[tch[i]] = tst[i];
  402.             }
  403.         /* fill in error entries */
  404.         for(i=1;i<NCH;i++)
  405.             if(symbol[i]) temp[i] = -2;    /* error trans */
  406.         /* count them */
  407.         k = 0;
  408.         for(i=1;i<NCH;i++)
  409.             if(temp[i] != -1)k++;
  410.         if(k <cnt){    /* compress by char */
  411. # ifdef DEBUG
  412.             if(debug) printf("use compression  %d,  %d vs %d\n",st,k,cnt);
  413. # endif
  414.             k = 0;
  415.             for(i=1;i<NCH;i++)
  416.                 if(temp[i] != -1){
  417.                     cwork[k] = i;
  418.                     swork[k++] = (temp[i] == -2 ? -1 : temp[i]);
  419.                     }
  420.             cwork[k] = 0;
  421. # ifdef PC
  422.             ach = cwork;
  423.             ast = swork;
  424.             cnt = k;
  425.             cpackflg[st] = TRUE;
  426. # endif
  427.             }
  428.         }
  429.     for(i=0; i<st; i++){    /* get most similar state */
  430.                 /* reject state with more transitions, state already represented by a third state,
  431.                     and state which is compressed by char if ours is not to be */
  432.         if(sfall[i] != -1) continue;
  433.         if(cpackflg[st] == 1) if(!(cpackflg[i] == 1)) continue;
  434.         p = gotof[i];
  435.         if(p == -1) /* no transitions */ continue;
  436.         tcnt = nexts[p];
  437.         if(tcnt > cnt) continue;
  438.         diff = 0;
  439.         k = 0;
  440.         j = 0;
  441.         upper = p + tcnt;
  442.         while(ach[j] && p < upper){
  443.             while(ach[j] < nchar[p] && ach[j]){diff++; j++; }
  444.             if(ach[j] == 0)break;
  445.             if(ach[j] > nchar[p]){diff=NCH;break;}
  446.             /* ach[j] == nchar[p] */
  447.             if(ast[j] != nexts[++p] || ast[j] == -1 || (cpackflg[st] && ach[j] != match[ach[j]]))diff++;
  448.             j++;
  449.             }
  450.         while(ach[j]){
  451.             diff++;
  452.             j++;
  453.             }
  454.         if(p < upper)diff = NCH;
  455.         if(diff < cval && diff < tcnt){
  456.             cval = diff;
  457.             cmin = i;
  458.             if(cval == 0)break;
  459.             }
  460.         }
  461.     /* cmin = state "most like" state st */
  462. # ifdef DEBUG
  463.     if(debug)printf("select st %d for st %d diff %d\n",cmin,st,cval);
  464. # endif
  465. # ifdef PS
  466.     if(cmin != -1){ /* if we can use st cmin */
  467.         gotof[st] = nptr;
  468.         k = 0;
  469.         sfall[st] = cmin;
  470.         p = gotof[cmin]+1;
  471.         j = 0;
  472.         while(ach[j]){
  473.             /* if cmin has a transition on c, then so will st */
  474.             /* st may be "larger" than cmin, however */
  475.             while(ach[j] < nchar[p-1] && ach[j]){
  476.                 k++;
  477.                 nchar[nptr] = ach[j];
  478.                 nexts[++nptr] = ast[j];
  479.                 j++;
  480.                 }
  481.             if(nchar[p-1] == 0)break;
  482.             if(ach[j] > nchar[p-1]){
  483.                 warning("bad transition %d %d",st,cmin);
  484.                 goto nopack;
  485.                 }
  486.             /* ach[j] == nchar[p-1] */
  487.             if(ast[j] != nexts[p] || ast[j] == -1 || (cpackflg[st] && ach[j] != match[ach[j]])){
  488.                 k++;
  489.                 nchar[nptr] = ach[j];
  490.                 nexts[++nptr] = ast[j];
  491.                 }
  492.             p++;
  493.             j++;
  494.             }
  495.         while(ach[j]){
  496.             nchar[nptr] = ach[j];
  497.             nexts[++nptr] = ast[j++];
  498.             k++;
  499.             }
  500.         nexts[gotof[st]] = cnt = k;
  501.         nchar[nptr++] = 0;
  502.         }
  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.         }
  521.     else
  522.         if(nptr > ntrans)
  523.             error("Too many transitions %s",(ntrans==NTRANS?"\nTry using %a num":""));
  524.     return;
  525.     }
  526. # ifdef DEBUG
  527. pstate(s)
  528.   int s; {
  529.     register int *p,i,j;
  530.     printf("State %d:\n",s);
  531.     p = state[s];
  532.     i = *p++;
  533.     if(i == 0) return;
  534.     printf("%4d",*p++);
  535.     for(j = 1; j<i; j++){
  536.         printf(", %4d",*p++);
  537.         if(j%30 == 0)putchar('\n');
  538.         }
  539.     putchar('\n');
  540.     return;
  541.     }
  542. # endif
  543. member(d,t)
  544.   int d;
  545.   char *t;    {
  546.     register int c;
  547.     register char *s;
  548.     c = d;
  549.     s = t;
  550.     c = cindex[c];
  551.     while(*s)
  552.         if(*s++ == c) return(1);
  553.     return(0);
  554.     }
  555. # ifdef DEBUG
  556. stprt(i)
  557.   int i; {
  558.     register int p, t;
  559.     printf("State %d:",i);
  560.     /* print actions, if any */
  561.     t = atable[i];
  562.     if(t != -1)printf(" final");
  563.     putchar('\n');
  564.     if(cpackflg[i] == TRUE)printf("backup char in use\n");
  565.     if(sfall[i] != -1)printf("fall back state %d\n",sfall[i]);
  566.     p = gotof[i];
  567.     if(p == -1) return;
  568.     printf("(%d transitions)\n",nexts[p]);
  569.     while(nchar[p]){
  570.         charc = 0;
  571.         if(nexts[p+1] >= 0)
  572.             printf("%d\t",nexts[p+1]);
  573.         else printf("err\t");
  574.         allprint(nchar[p++]);
  575.         while(nexts[p] == nexts[p+1] && nchar[p]){
  576.             if(charc > LINESIZE){
  577.                 charc = 0;
  578.                 printf("\n\t");
  579.                 }
  580.             allprint(nchar[p++]);
  581.             }
  582.         putchar('\n');
  583.         }
  584.     putchar('\n');
  585.     return;
  586.     }
  587. # endif
  588. acompute(s)    /* compute action list = set of poss. actions */
  589.   int s; {
  590.     register int *p, i, j;
  591.     int cnt, m;
  592.     int temp[300], k, neg[300], n;
  593.     k = 0;
  594.     n = 0;
  595.     p = state[s];
  596.     cnt = *p++;
  597.     if(cnt > 300)
  598.         error("Too many positions for one state - acompute");
  599.     for(i=0;i<cnt;i++){
  600.         if(name[*p] == FINAL)temp[k++] = left[*p];
  601.         else if(name[*p] == S1FINAL){temp[k++] = left[*p];
  602.             if (left[*p] >NACTIONS) error("Too many right contexts");
  603.             extra[left[*p]] = 1;
  604.             }
  605.         else if(name[*p] == S2FINAL)neg[n++] = left[*p];
  606.         p++;
  607.         }
  608.     atable[s] = -1;
  609.     if(k < 1 && n < 1) return;
  610. # ifdef DEBUG
  611.     if(debug) printf("final %d actions:",s);
  612. # endif
  613.     /* sort action list */
  614.     for(i=0; i<k; i++)
  615.         for(j=i+1;j<k;j++)
  616.             if(temp[j] < temp[i]){
  617.                 m = temp[j];
  618.                 temp[j] = temp[i];
  619.                 temp[i] = m;
  620.                 }
  621.     /* remove dups */
  622.     for(i=0;i<k-1;i++)
  623.         if(temp[i] == temp[i+1]) temp[i] = 0;
  624.     /* copy to permanent quarters */
  625.     atable[s] = aptr;
  626. # ifdef DEBUG
  627.     if(!ratfor)fprintf(fout,"/* actions for state %d */",s);
  628. # endif
  629.     putc('\n',fout);
  630.     for(i=0;i<k;i++)
  631.         if(temp[i] != 0){
  632.             ratfor ? fprintf(fout,"data vstop(%d)/%d/\n",aptr,temp[i]) : fprintf(fout,"%d,\n",temp[i]);
  633. # ifdef DEBUG
  634.             if(debug)
  635.                 printf("%d ",temp[i]);
  636. # endif
  637.             aptr++;
  638.             }
  639.     for(i=0;i<n;i++){        /* copy fall back actions - all neg */
  640.         ratfor ? fprintf(fout,"data vstop(%d)/%d/\n",aptr,neg[i]) : fprintf(fout,"%d,\n",neg[i]);
  641.         aptr++;
  642. # ifdef DEBUG
  643.         if(debug)printf("%d ",neg[i]);
  644. # endif
  645.         }
  646. # ifdef DEBUG
  647.     if(debug)putchar('\n');
  648. # endif
  649.     ratfor ? fprintf(fout,"data vstop (%d)/0/\n",aptr) : fprintf(fout,"0,\n");
  650.     aptr++;
  651.     return;
  652.     }
  653. # ifdef DEBUG
  654. pccl() {
  655.     /* print character class sets */
  656.     register int i, j;
  657.     printf("char class intersection\n");
  658.     for(i=0; i< ccount; i++){
  659.         charc = 0;
  660.         printf("class %d:\n\t",i);
  661.         for(j=1;j<NCH;j++)
  662.             if(cindex[j] == i){
  663.                 allprint(j);
  664.                 if(charc > LINESIZE){
  665.                     printf("\n\t");
  666.                     charc = 0;
  667.                     }
  668.                 }
  669.         putchar('\n');
  670.         }
  671.     charc = 0;
  672.     printf("match:\n");
  673.     for(i=0;i<NCH;i++){
  674.         allprint(match[i]);
  675.         if(charc > LINESIZE){
  676.             putchar('\n');
  677.             charc = 0;
  678.             }
  679.         }
  680.     putchar('\n');
  681.     return;
  682.     }
  683. # endif
  684. mkmatch(){
  685.     register int i;
  686.     char tab[NCH];
  687.     for(i=0; i<ccount; i++)
  688.         tab[i] = 0;
  689.     for(i=1;i<NCH;i++)
  690.         if(tab[cindex[i]] == 0)
  691.             tab[cindex[i]] = i;
  692.     /* tab[i] = principal char for new ccl i */
  693.     for(i = 1; i<NCH; i++)
  694.         match[i] = tab[cindex[i]];
  695.     return;
  696.     }
  697. layout(){
  698.     /* format and output final program's tables */
  699.     register int i, j, k;
  700.     int  top, bot, startup, omin;
  701.     startup = 0;
  702.     for(i=0; i<outsize;i++)
  703.         verify[i] = advance[i] = 0;
  704.     omin = 0;
  705.     yytop = 0;
  706.     for(i=0; i<= stnum; i++){    /* for each state */
  707.         j = gotof[i];
  708.         if(j == -1){
  709.             stoff[i] = 0;
  710.             continue;
  711.             }
  712.         bot = j;
  713.         while(nchar[j])j++;
  714.         top = j - 1;
  715. # if DEBUG
  716.         if (debug)
  717.             {
  718.             printf("State %d: (layout)\n", i);
  719.             for(j=bot; j<=top;j++)
  720.                 {
  721.                 printf("  %o", nchar[j]);
  722.                 if (j%10==0) putchar('\n');
  723.                 }
  724.             putchar('\n');
  725.             }
  726. # endif
  727.         while(verify[omin+ZCH]) omin++;
  728.         startup = omin;
  729. # if DEBUG
  730.         if (debug) printf("bot,top %d, %d startup begins %d\n",bot,top,startup);
  731. # endif
  732.         if(chset){
  733.             do {
  734.                 startup =+ 1;
  735.                 if(startup > outsize - ZCH)
  736.                     error("output table overflow");
  737.                 for(j = bot; j<= top; j++){
  738.                     k=startup+ctable[nchar[j]];
  739.                     if(verify[k])break;
  740.                     }
  741.                 } while (j <= top);
  742. # if DEBUG
  743.             if (debug) printf(" startup will be %d\n",startup);
  744. # endif
  745.             /* have found place */
  746.             for(j = bot; j<= top; j++){
  747.                 k = startup + ctable[nchar[j]];
  748.                 if (ctable[nchar[j]]<=0)
  749.                  printf("j %d nchar %d ctable.nch %d\n",j,nchar[j],ctable[nchar[k]]);
  750.                 verify[k] = i+1;            /* state number + 1*/
  751.                 advance[k] = nexts[j+1]+1;        /* state number + 1*/
  752.                 if(yytop < k) yytop = k;
  753.                 }
  754.             }
  755.         else {
  756.             do {
  757.                 startup =+ 1;
  758.                 if(startup > outsize - ZCH)
  759.                     error("output table overflow");
  760.                 for(j = bot; j<= top; j++){
  761.                     k = startup + nchar[j];
  762.                     if(verify[k])break;
  763.                     }
  764.                 } while (j <= top);
  765.             /* have found place */
  766. # if DEBUG
  767.     if (debug) printf(" startup going to be %d\n", startup);
  768. # endif
  769.             for(j = bot; j<= top; j++){
  770.                 k = startup + nchar[j];
  771.                 verify[k] = i+1;            /* state number + 1*/
  772.                 advance[k] = nexts[j+1]+1;        /* state number + 1*/
  773.                 if(yytop < k) yytop = k;
  774.                 }
  775.             }
  776.         stoff[i] = startup;
  777.         }
  778.  
  779.     /* stoff[i] = offset into verify, advance for trans for state i */
  780.     /* put out yywork */
  781.     if(ratfor){
  782.         fprintf(fout, "define YYTOPVAL %d\n", yytop);
  783.         rprint(verify,"verif",yytop+1);
  784.         rprint(advance,"advan",yytop+1);
  785.          shiftr(stoff, stnum); 
  786.         rprint(stoff,"stoff",stnum+1);
  787.          shiftr(sfall, stnum); upone(sfall, stnum+1);
  788.         rprint(sfall,"sfall",stnum+1);
  789.         bprint(extra,"extra",casecount+1);
  790.         bprint(match,"match",NCH);
  791.          shiftr(atable, stnum);
  792.         rprint(atable,"atable",stnum+1);
  793.         return;
  794.         }
  795.     fprintf(fout,"# define YYTYPE %s\n",stnum+1 > NCH ? "int" : "char");
  796.     fprintf(fout,"struct yywork { YYTYPE verify, advance; } yycrank[] ={\n");
  797.     for(i=0;i<=yytop;i=+4){
  798.         for(j=0;j<4;j++){
  799.             k = i+j;
  800.             if(verify[k])
  801.                 fprintf(fout,"%d,%d,\t",verify[k],advance[k]);
  802.             else
  803.                 fprintf(fout,"0,0,\t");
  804.             }
  805.         putc('\n',fout);
  806.         }
  807.     fprintf(fout,"0,0};\n");
  808.  
  809.     /* put out yysvec */
  810.  
  811.     fprintf(fout,"struct yysvf yysvec[] ={\n");
  812.     fprintf(fout,"0,\t0,\t0,\n");
  813.     for(i=0;i<=stnum;i++){    /* for each state */
  814.         if(cpackflg[i])stoff[i] = -stoff[i];
  815.         fprintf(fout,"yycrank+%d,\t",stoff[i]);
  816.         if(sfall[i] != -1)
  817.             fprintf(fout,"yysvec+%d,\t", sfall[i]+1);    /* state + 1 */
  818.         else fprintf(fout,"0,\t\t");
  819.         if(atable[i] != -1)
  820.             fprintf(fout,"yyvstop+%d,",atable[i]);
  821.         else fprintf(fout,"0,\t");
  822. # ifdef DEBUG
  823.         fprintf(fout,"\t\t/* state %d */",i);
  824. # endif
  825.         putc('\n',fout);
  826.         }
  827.     fprintf(fout,"0,\t0,\t0};\n");
  828.  
  829.     /* put out yymatch */
  830.     
  831.     fprintf(fout,"struct yywork *yytop = yycrank+%d;\n",yytop);
  832.     fprintf(fout,"struct yysvf *yybgin = yysvec+1;\n");
  833.     if(optim){
  834.         fprintf(fout,"char yymatch[] ={\n");
  835.         if (chset==0) /* no chset, put out in normal order */
  836.             {
  837.             for(i=0; i<NCH; i=+8){
  838.                 for(j=0; j<8; j++){
  839.                     int fbch;
  840.                     fbch = match[i+j];
  841.                     if(printable(fbch) && fbch != '\'' && fbch != '\\')
  842.                         fprintf(fout,"'%c' ,",fbch);
  843.                     else fprintf(fout,"0%-3o,",fbch);
  844.                     }
  845.                 putc('\n',fout);
  846.                 }
  847.             }
  848.         else
  849.             {
  850.             int *fbarr;
  851.             fbarr = myalloc(2*NCH, sizeof(*fbarr));
  852.             if (fbarr==0)
  853.                 error("No space for char table reverse",0);
  854.             for(i=0; i<ZCH; i++)
  855.                 fbarr[i]=0;
  856.             for(i=0; i<NCH; i++)
  857.                 fbarr[ctable[i]] = ctable[match[i]];
  858.             for(i=0; i<ZCH; i+=8)
  859.                 {
  860.                 for(j=0; j<8; j++)
  861.                     fprintf(fout, "0%-3o,",fbarr[i+j]);
  862.                 putc('\n',fout);
  863.                 }
  864.             cfree(fbarr, 2*NCH, 1);
  865.             }
  866.         fprintf(fout,"0};\n");
  867.         }
  868.     /* put out yyextra */
  869.     fprintf(fout,"char yyextra[] ={\n");
  870.     for(i=0;i<casecount;i=+8){
  871.         for(j=0;j<8;j++)
  872.             fprintf(fout, "%d,", i+j<NACTIONS ?
  873.                 extra[i+j] : 0);
  874.         putc('\n',fout);
  875.         }
  876.     fprintf(fout,"0};\n");
  877.     return;
  878.     }
  879. rprint(a,s,n)
  880.   char *s;
  881.   int *a, n; {
  882.     register int i;
  883.     fprintf(fout,"block data\n");
  884.     fprintf(fout,"common /L%s/ %s\n",s,s);
  885.     fprintf(fout,"define S%s %d\n",s,n);
  886.     fprintf(fout,"integer %s (S%s)\n",s,s);
  887.     for(i=1; i<=n; i++)
  888.         {
  889.         if (i%8==1) fprintf(fout, "data ");
  890.         fprintf(fout, "%s (%d)/%d/",s,i,a[i]);
  891.         fprintf(fout, (i%8 && i<n) ? ", " : "\n");
  892.         }
  893.     fprintf(fout,"end\n");
  894.     }
  895. shiftr(a, n)
  896.     int *a;
  897. {
  898. int i;
  899. for(i=n; i>=0; i--)
  900.     a[i+1]=a[i];
  901. }
  902. upone(a,n)
  903.     int *a;
  904. {
  905. int i;
  906. for(i=0; i<=n ; i++)
  907.     a[i]++;
  908. }
  909. bprint(a,s,n)
  910.  char *s,  *a;
  911.  int  n; {
  912.     register int i, j, k;
  913.     fprintf(fout,"block data\n");
  914.     fprintf(fout,"common /L%s/ %s\n",s,s);
  915.     fprintf(fout,"define S%s %d\n",s,n);
  916.     fprintf(fout,"integer %s (S%s)\n",s,s);
  917.     for(i=1;i<n;i=+8){
  918.         fprintf(fout,"data %s (%d)/%d/",s,i,a[i]);
  919.         for(j=1;j<8;j++){
  920.             k = i+j;
  921.             if(k < n)fprintf(fout,", %s (%d)/%d/",s,k,a[k]);
  922.             }
  923.         putc('\n',fout);
  924.         }
  925.     fprintf(fout,"end\n");
  926.     }
  927. # ifdef PP
  928. padd(array,n)
  929.   int **array;
  930.   int n; {
  931.     register int i, *j, k;
  932.     array[n] = nxtpos;
  933.     if(count == 0){
  934.         *nxtpos++ = 0;
  935.         return;
  936.         }
  937.     for(i=tptr-1;i>=0;i--){
  938.         j = array[i];
  939.         if(j && *j++ == count){
  940.             for(k=0;k<count;k++)
  941.                 if(!tmpstat[*j++])break;
  942.             if(k >= count){
  943.                 array[n] = array[i];
  944.                 return;
  945.                 }
  946.             }
  947.         }
  948.     add(array,n);
  949.     return;
  950.     }
  951. # endif
  952.