# include "ldefs.h"
void
cfoll(int v)
{
       int i,j,k;
       uchar *p;
       i = name[v];
       if(i < NCH) i = 1;      /* character */
       switch(i){
               case 1: case RSTR: case RCCL: case RNCCL: case RNULLS:
                       for(j=0;j<tptr;j++)
                               tmpstat[j] = FALSE;
                       count = 0;
                       follow(v);
# ifdef PP
                       padd(foll,v);           /* packing version */
# endif
# ifndef PP
                       add(foll,v);            /* no packing version */
# endif
                       if(i == RSTR) cfoll(left[v]);
                       else if(i == RCCL || i == RNCCL){       /* compress ccl list */
                               for(j=1; j<NCH;j++)
                                       symbol[j] = (i==RNCCL);
                               p = ptr[v];
                               while(*p)
                                       symbol[*p++] = (i == RCCL);
                               p = pcptr;
                               for(j=1;j<NCH;j++)
                                       if(symbol[j]){
                                               for(k=0;p+k < pcptr; k++)
                                                       if(cindex[j] == *(p+k))
                                                               break;
                                               if(p+k >= pcptr)*pcptr++ = cindex[j];
                                       }
                               *pcptr++ = 0;
                               if(pcptr > pchar + pchlen)
                                       error("Too many packed character classes");
                               ptr[v] = p;
                               name[v] = RCCL; /* RNCCL eliminated */
# ifdef DEBUG
                               if(debug && *p){
                                       print("ccl %d: %d",v,*p++);
                                       while(*p)
                                               print(", %d",*p++);
                                       print("\n");
                               }
# endif
                       }
                       break;
               case CARAT:
                       cfoll(left[v]);
                       break;
               case STAR: case PLUS: case QUEST: case RSCON:
                       cfoll(left[v]);
                       break;
               case BAR: case RCAT: case DIV: case RNEWE:
                       cfoll(left[v]);
                       cfoll(right[v]);
                       break;
# ifdef DEBUG
               case FINAL:
               case S1FINAL:
               case S2FINAL:
                       break;
               default:
                       warning("bad switch cfoll %d",v);
# endif
       }
}

# ifdef DEBUG
void
pfoll(void)
       {
       int i,k,*p;
       int j;
       /* print sets of chars which may follow positions */
       print("pos\tchars\n");
       for(i=0;i<tptr;i++)
               if(p=foll[i]){
                       j = *p++;
                       if(j >= 1){
                               print("%d:\t%d",i,*p++);
                               for(k=2;k<=j;k++)
                                       print(", %d",*p++);
                               print("\n");
                       }
               }
}
# endif

void
add(int **array, int n)
{
       int i, *temp;
       uchar *ctemp;

       temp = nxtpos;
       ctemp = tmpstat;
       array[n] = nxtpos;              /* note no packing is done in positions */
       *temp++ = count;
       for(i=0;i<tptr;i++)
               if(ctemp[i] == TRUE)
                       *temp++ = i;
       nxtpos = temp;
       if(nxtpos >= positions+maxpos)
               error("Too many positions %s",(maxpos== MAXPOS?"\nTry using %p num":""));
}

void
follow(int v)
{
       int p;
       if(v >= tptr-1)return;
       p = parent[v];
       if(p == 0) return;
       switch(name[p]){
                       /* will not be CHAR RNULLS FINAL S1FINAL S2FINAL RCCL RNCCL */
               case RSTR:
                       if(tmpstat[p] == FALSE){
                               count++;
                               tmpstat[p] = TRUE;
                       }
                       break;
               case STAR: case PLUS:
                       first(v);
                       follow(p);
                       break;
               case BAR: case QUEST: case RNEWE:
                       follow(p);
                       break;
               case RCAT: case DIV:
                       if(v == left[p]){
                               if(nullstr[right[p]])
                                       follow(p);
                               first(right[p]);
                       }
                       else follow(p);
                       break;
               case RSCON: case CARAT:
                       follow(p);
                       break;
# ifdef DEBUG
               default:
                       warning("bad switch follow %d",p);
# endif
       }
}

void
first(int v)    /* calculate set of positions with v as root which can be active initially */
{
       int i;
       uchar *p;
       i = name[v];
       if(i < NCH)i = 1;
       switch(i){
               case 1: case RCCL: case RNCCL: case RNULLS: case FINAL: case S1FINAL: case S2FINAL:
                       if(tmpstat[v] == FALSE){
                               count++;
                               tmpstat[v] = TRUE;
                       }
                       break;
               case BAR: case RNEWE:
                       first(left[v]);
                       first(right[v]);
                       break;
               case CARAT:
                       if(stnum % 2 == 1)
                               first(left[v]);
                       break;
               case RSCON:
                       i = stnum/2 +1;
                       p = (uchar *)right[v];
                       while(*p)
                               if(*p++ == i){
                                       first(left[v]);
                                       break;
                               }
                       break;
               case STAR: case QUEST: case PLUS:  case RSTR:
                       first(left[v]);
                       break;
               case RCAT: case DIV:
                       first(left[v]);
                       if(nullstr[left[v]])
                               first(right[v]);
                       break;
# ifdef DEBUG
               default:
                       warning("bad switch first %d",v);
# endif
       }
}

void
cgoto(void)
{
       int i, j, s;
       int npos, curpos, n;
       int tryit;
       uchar tch[NCH];
       int tst[NCH];
       uchar *q;

       /* generate initial state, for each start condition */
       Bprint(&fout,"int yyvstop[] = {\n0,\n");
       while(stnum < 2 || stnum/2 < sptr){
               for(i = 0; i<tptr; i++) tmpstat[i] = 0;
               count = 0;
               if(tptr > 0)first(tptr-1);
               add(state,stnum);
# ifdef DEBUG
               if(debug){
                       if(stnum > 1)
                               print("%s:\n",sname[stnum/2]);
                       pstate(stnum);
               }
# endif
               stnum++;
       }
       stnum--;
       /* even stnum = might not be at line begin */
       /* odd stnum  = must be at line begin */
       /* even states can occur anywhere, odd states only at line begin */
       for(s = 0; s <= stnum; s++){
               tryit = FALSE;
               cpackflg[s] = FALSE;
               sfall[s] = -1;
               acompute(s);
               for(i=0;i<NCH;i++) symbol[i] = 0;
               npos = *state[s];
               for(i = 1; i<=npos; i++){
                       curpos = *(state[s]+i);
                       if(name[curpos] < NCH) symbol[name[curpos]] = TRUE;
                       else switch(name[curpos]){
                       case RCCL:
                               tryit = TRUE;
                               q = ptr[curpos];
                               while(*q){
                                       for(j=1;j<NCH;j++)
                                               if(cindex[j] == *q)
                                                       symbol[j] = TRUE;
                                       q++;
                               }
                               break;
                       case RSTR:
                               symbol[right[curpos]] = TRUE;
                               break;
# ifdef DEBUG
                       case RNULLS:
                       case FINAL:
                       case S1FINAL:
                       case S2FINAL:
                               break;
                       default:
                               warning("bad switch cgoto %d state %d",curpos,s);
                               break;
# endif
                       }
               }
# ifdef DEBUG
               if(debug){
                       print("State %d transitions on:\n\t",s);
                       charc = 0;
                       for(i = 1; i<NCH; i++){
                               if(symbol[i]) allprint(i);
                               if(charc > LINESIZE){
                                       charc = 0;
                                       print("\n\t");
                               }
                       }
                       print("\n");
               }
# endif
               /* for each char, calculate next state */
               n = 0;
               for(i = 1; i<NCH; i++){
                       if(symbol[i]){
                               nextstate(s,i);         /* executed for each state, transition pair */
                               xstate = notin(stnum);
                               if(xstate == -2) warning("bad state  %d %o",s,i);
                               else if(xstate == -1){
                                       if(stnum >= nstates)
                                               error("Too many states %s",(nstates == NSTATES ? "\nTry using %n num":""));
                                       add(state,++stnum);
# ifdef DEBUG
                                       if(debug)pstate(stnum);
# endif
                                       tch[n] = i;
                                       tst[n++] = stnum;
                               } else {                /* xstate >= 0 ==> state exists */
                                       tch[n] = i;
                                       tst[n++] = xstate;
                               }
                       }
               }
               tch[n] = 0;
               tst[n] = -1;
               /* pack transitions into permanent array */
               if(n > 0) packtrans(s,tch,tst,n,tryit);
               else gotof[s] = -1;
       }
       Bprint(&fout,"0};\n");
}

/*      Beware -- 70% of total CPU time is spent in this subroutine -
       if you don't believe me - try it yourself ! */
void
nextstate(int s, int c)
{
       int j, *newpos;
       uchar *temp, *tz;
       int *pos, i, *f, num, curpos, number;
       /* state to goto from state s on char c */
       num = *state[s];
       temp = tmpstat;
       pos = state[s] + 1;
       for(i = 0; i<num; i++){
               curpos = *pos++;
               j = name[curpos];
               if(j < NCH && j == c
               || j == RSTR && c == right[curpos]
               || j == RCCL && member(c, ptr[curpos])){
                       f = foll[curpos];
                       number = *f;
                       newpos = f+1;
                       for(j=0;j<number;j++)
                               temp[*newpos++] = 2;
               }
       }
       j = 0;
       tz = temp + tptr;
       while(temp < tz){
               if(*temp == 2){
                       j++;
                       *temp++ = 1;
               }
               else *temp++ = 0;
       }
       count = j;
}

int
notin(int n)
{       /* see if tmpstat occurs previously */
       int *j,k;
       uchar *temp;
       int i;

       if(count == 0)
               return(-2);
       temp = tmpstat;
       for(i=n;i>=0;i--){      /* for each state */
               j = state[i];
               if(count == *j++){
                       for(k=0;k<count;k++)
                               if(!temp[*j++])break;
                       if(k >= count)
                               return(i);
               }
       }
       return(-1);
}

void
packtrans(int st, uchar *tch, int *tst, int cnt, int tryit)
{
       /* pack transitions into nchar, nexts */
       /* nchar is terminated by '\0', nexts uses cnt, followed by elements */
       /* gotof[st] = index into nchr, nexts for state st */

       /* sfall[st] =  t implies t is fall back state for st */
       /*              == -1 implies no fall back */

       int i,j,k;
       int cmin, cval, tcnt, diff, p, *ast;
       uchar *ach;
       int go[NCH], temp[NCH], c;
       int swork[NCH];
       uchar cwork[NCH];
       int upper;

       rcount += cnt;
       cmin = -1;
       cval = NCH;
       ast = tst;
       ach = tch;
       /* try to pack transitions using ccl's */
       if(tryit){      /* ccl's used */
               for(i=1;i<NCH;i++){
                       go[i] = temp[i] = -1;
                       symbol[i] = 1;
               }
               for(i=0;i<cnt;i++){
                       go[tch[i]] = tst[i];
                       symbol[tch[i]] = 0;
               }
               for(i=0; i<cnt;i++){
                       c = match[tch[i]];
                       if(go[c] != tst[i] || c == tch[i])
                               temp[tch[i]] = tst[i];
               }
               /* fill in error entries */
               for(i=1;i<NCH;i++)
                       if(symbol[i]) temp[i] = -2;     /* error trans */
               /* count them */
               k = 0;
               for(i=1;i<NCH;i++)
                       if(temp[i] != -1)k++;
               if(k <cnt){     /* compress by char */
# ifdef DEBUG
                       if(debug) print("use compression  %d,  %d vs %d\n",st,k,cnt);
# endif
                       k = 0;
                       for(i=1;i<NCH;i++)
                               if(temp[i] != -1){
                                       cwork[k] = i;
                                       swork[k++] = (temp[i] == -2 ? -1 : temp[i]);
                               }
                       cwork[k] = 0;
# ifdef PC
                       ach = cwork;
                       ast = swork;
                       cnt = k;
                       cpackflg[st] = TRUE;
# endif
               }
       }
       for(i=0; i<st; i++){    /* get most similar state */
                               /* reject state with more transitions, state already represented by a third state,
                                       and state which is compressed by char if ours is not to be */
               if(sfall[i] != -1) continue;
               if(cpackflg[st] == 1) if(!(cpackflg[i] == 1)) continue;
               p = gotof[i];
               if(p == -1) /* no transitions */ continue;
               tcnt = nexts[p];
               if(tcnt > cnt) continue;
               diff = 0;
               j = 0;
               upper = p + tcnt;
               while(ach[j] && p < upper){
                       while(ach[j] < nchar[p] && ach[j]){diff++; j++; }
                       if(ach[j] == 0)break;
                       if(ach[j] > nchar[p]){diff=NCH;break;}
                       /* ach[j] == nchar[p] */
                       if(ast[j] != nexts[++p] || ast[j] == -1 || (cpackflg[st] && ach[j] != match[ach[j]]))diff++;
                       j++;
               }
               while(ach[j]){
                       diff++;
                       j++;
               }
               if(p < upper)diff = NCH;
               if(diff < cval && diff < tcnt){
                       cval = diff;
                       cmin = i;
                       if(cval == 0)break;
               }
       }
       /* cmin = state "most like" state st */
# ifdef DEBUG
       if(debug)print("select st %d for st %d diff %d\n",cmin,st,cval);
# endif
# ifdef PS
       if(cmin != -1){ /* if we can use st cmin */
               gotof[st] = nptr;
               k = 0;
               sfall[st] = cmin;
               p = gotof[cmin]+1;
               j = 0;
               while(ach[j]){
                       /* if cmin has a transition on c, then so will st */
                       /* st may be "larger" than cmin, however */
                       while(ach[j] < nchar[p-1] && ach[j]){
                               k++;
                               nchar[nptr] = ach[j];
                               nexts[++nptr] = ast[j];
                               j++;
                       }
                       if(nchar[p-1] == 0)break;
                       if(ach[j] > nchar[p-1]){
                               warning("bad transition %d %d",st,cmin);
                               goto nopack;
                       }
                       /* ach[j] == nchar[p-1] */
                       if(ast[j] != nexts[p] || ast[j] == -1 || (cpackflg[st] && ach[j] != match[ach[j]])){
                               k++;
                               nchar[nptr] = ach[j];
                               nexts[++nptr] = ast[j];
                       }
                       p++;
                       j++;
               }
               while(ach[j]){
                       nchar[nptr] = ach[j];
                       nexts[++nptr] = ast[j++];
                       k++;
               }
               nexts[gotof[st]] = cnt = k;
               nchar[nptr++] = 0;
       } else {
# endif
nopack:
       /* stick it in */
               gotof[st] = nptr;
               nexts[nptr] = cnt;
               for(i=0;i<cnt;i++){
                       nchar[nptr] = ach[i];
                       nexts[++nptr] = ast[i];
               }
               nchar[nptr++] = 0;
# ifdef PS
       }
# endif
       if(cnt < 1){
               gotof[st] = -1;
               nptr--;
       } else
               if(nptr > ntrans)
                       error("Too many transitions %s",(ntrans==NTRANS?"\nTry using %a num":""));
}

# ifdef DEBUG
void
pstate(int s)
{
       int *p,i,j;
       print("State %d:\n",s);
       p = state[s];
       i = *p++;
       if(i == 0) return;
       print("%4d",*p++);
       for(j = 1; j<i; j++){
               print(", %4d",*p++);
               if(j%30 == 0)print("\n");
       }
       print("\n");
}
# endif

int
member(int d, uchar *t)
{
       int c;
       uchar *s;

       c = d;
       s = t;
       c = cindex[c];
       while(*s)
               if(*s++ == c) return(1);
       return(0);
}

# ifdef DEBUG
void
stprt(int i)
{
       int p, t;

       print("State %d:",i);
       /* print actions, if any */
       t = atable[i];
       if(t != -1)print(" final");
       print("\n");
       if(cpackflg[i] == TRUE)print("backup char in use\n");
       if(sfall[i] != -1)print("fall back state %d\n",sfall[i]);
       p = gotof[i];
       if(p == -1) return;
       print("(%d transitions)\n",nexts[p]);
       while(nchar[p]){
               charc = 0;
               if(nexts[p+1] >= 0)
                       print("%d\t",nexts[p+1]);
               else print("err\t");
               allprint(nchar[p++]);
               while(nexts[p] == nexts[p+1] && nchar[p]){
                       if(charc > LINESIZE){
                               charc = 0;
                               print("\n\t");
                       }
                       allprint(nchar[p++]);
               }
               print("\n");
       }
       print("\n");
}
# endif

void
acompute(int s) /* compute action list = set of poss. actions */
{
       int *p, i, j;
       int cnt, m;
       int temp[300], k, neg[300], n;

       k = 0;
       n = 0;
       p = state[s];
       cnt = *p++;
       if(cnt > 300)
               error("Too many positions for one state - acompute");
       for(i=0;i<cnt;i++){
               if(name[*p] == FINAL)temp[k++] = left[*p];
               else if(name[*p] == S1FINAL){temp[k++] = left[*p];
                       if (left[*p] >= NACTIONS) error("Too many right contexts");
                       extra[left[*p]] = 1;
               } else if(name[*p] == S2FINAL)neg[n++] = left[*p];
               p++;
       }
       atable[s] = -1;
       if(k < 1 && n < 1) return;
# ifdef DEBUG
       if(debug) print("final %d actions:",s);
# endif
       /* sort action list */
       for(i=0; i<k; i++)
               for(j=i+1;j<k;j++)
                       if(temp[j] < temp[i]){
                               m = temp[j];
                               temp[j] = temp[i];
                               temp[i] = m;
                       }
       /* remove dups */
       for(i=0;i<k-1;i++)
               if(temp[i] == temp[i+1]) temp[i] = 0;
       /* copy to permanent quarters */
       atable[s] = aptr;
# ifdef DEBUG
       Bprint(&fout,"/* actions for state %d */",s);
# endif
       Bputc(&fout, '\n');
       for(i=0;i<k;i++)
               if(temp[i] != 0){
                       Bprint(&fout,"%d,\n",temp[i]);
# ifdef DEBUG
                       if(debug)
                               print("%d ",temp[i]);
# endif
                       aptr++;
               }
       for(i=0;i<n;i++){               /* copy fall back actions - all neg */
               Bprint(&fout,"%d,\n",neg[i]);
               aptr++;
# ifdef DEBUG
               if(debug)print("%d ",neg[i]);
# endif
       }
# ifdef DEBUG
       if(debug)print("\n");
# endif
       Bprint(&fout,"0,\n");
       aptr++;
}

# ifdef DEBUG
void
pccl(void) {
       /* print character class sets */
       int i, j;

       print("char class intersection\n");
       for(i=0; i< ccount; i++){
               charc = 0;
               print("class %d:\n\t",i);
               for(j=1;j<NCH;j++)
                       if(cindex[j] == i){
                               allprint(j);
                               if(charc > LINESIZE){
                                       print("\n\t");
                                       charc = 0;
                               }
                       }
               print("\n");
       }
       charc = 0;
       print("match:\n");
       for(i=0;i<NCH;i++){
               allprint(match[i]);
               if(charc > LINESIZE){
                       print("\n");
                       charc = 0;
               }
       }
       print("\n");
}
# endif

void
mkmatch(void)
{
       int i;
       uchar tab[NCH];

       for(i=0; i<ccount; i++)
               tab[i] = 0;
       for(i=1;i<NCH;i++)
               if(tab[cindex[i]] == 0)
                       tab[cindex[i]] = i;
       /* tab[i] = principal char for new ccl i */
       for(i = 1; i<NCH; i++)
               match[i] = tab[cindex[i]];
}

void
layout(void)
{
       /* format and output final program's tables */
       int i, j, k;
       int  top, bot, startup, omin;

       for(i=0; i<outsize;i++)
               verify[i] = advance[i] = 0;
       omin = 0;
       yytop = 0;
       for(i=0; i<= stnum; i++){       /* for each state */
               j = gotof[i];
               if(j == -1){
                       stoff[i] = 0;
                       continue;
                       }
               bot = j;
               while(nchar[j])j++;
               top = j - 1;
# ifdef DEBUG
               if (debug) {
                       print("State %d: (layout)\n", i);
                       for(j=bot; j<=top;j++) {
                               print("  %o", nchar[j]);
                               if (j%10==0) print("\n");
                       }
                       print("\n");
               }
# endif
               while(verify[omin+NCH]) omin++;
               startup = omin;
# ifdef DEBUG
               if (debug) print("bot,top %d, %d startup begins %d\n",bot,top,startup);
# endif
               do {
                       startup += 1;
                       if(startup > outsize - NCH)
                               error("output table overflow");
                       for(j = bot; j<= top; j++){
                               k = startup + nchar[j];
                               if(verify[k])break;
                       }
               } while (j <= top);
               /* have found place */
# ifdef DEBUG
               if (debug) print(" startup going to be %d\n", startup);
# endif
               for(j = bot; j<= top; j++){
                       k = startup + nchar[j];
                       verify[k] = i+1;                        /* state number + 1*/
                       advance[k] = nexts[j+1]+1;              /* state number + 1*/
                       if(yytop < k) yytop = k;
               }
               stoff[i] = startup;
       }

       /* stoff[i] = offset into verify, advance for trans for state i */
       /* put out yywork */
       Bprint(&fout,"# define YYTYPE %s\n",stnum+1 >= NCH ? "int" : "Uchar");
       Bprint(&fout,"struct yywork { YYTYPE verify, advance; } yycrank[] = {\n");
       for(i=0;i<=yytop;i+=4){
               for(j=0;j<4;j++){
                       k = i+j;
                       if(verify[k])
                               Bprint(&fout,"%d,%d,\t",verify[k],advance[k]);
                       else
                               Bprint(&fout,"0,0,\t");
               }
               Bputc(&fout, '\n');
       }
       Bprint(&fout,"0,0};\n");

       /* put out yysvec */

       Bprint(&fout,"struct yysvf yysvec[] = {\n");
       Bprint(&fout,"0,\t0,\t0,\n");
       for(i=0;i<=stnum;i++){  /* for each state */
               if(cpackflg[i])stoff[i] = -stoff[i];
               Bprint(&fout,"yycrank+%d,\t",stoff[i]);
               if(sfall[i] != -1)
                       Bprint(&fout,"yysvec+%d,\t", sfall[i]+1);       /* state + 1 */
               else Bprint(&fout,"0,\t\t");
               if(atable[i] != -1)
                       Bprint(&fout,"yyvstop+%d,",atable[i]);
               else Bprint(&fout,"0,\t");
# ifdef DEBUG
               Bprint(&fout,"\t\t/* state %d */",i);
# endif
               Bputc(&fout, '\n');
       }
       Bprint(&fout,"0,\t0,\t0};\n");

       /* put out yymatch */

       Bprint(&fout,"struct yywork *yytop = yycrank+%d;\n",yytop);
       Bprint(&fout,"struct yysvf *yybgin = yysvec+1;\n");
       Bprint(&fout,"Uchar yymatch[] = {\n");
       for(i=0; i<NCH; i+=8){
               for(j=0; j<8; j++){
                       int fbch;
                       fbch = match[i+j];
                       if(isprint(fbch) && fbch != '\'' && fbch != '\\')
                               Bprint(&fout,"'%c' ,",fbch);
                       else Bprint(&fout,"0%-3o,",fbch);
               }
               Bputc(&fout, '\n');
       }
       Bprint(&fout,"0};\n");
       /* put out yyextra */
       Bprint(&fout,"Uchar yyextra[] = {\n");
       for(i=0;i<casecount;i+=8){
               for(j=0;j<8;j++)
                       Bprint(&fout, "%d,", i+j<NACTIONS ?
                               extra[i+j] : 0);
               Bputc(&fout, '\n');
       }
       Bprint(&fout,"0};\n");
}

# ifdef PP
void
padd(int **array, int n)
{
       int i, *j, k;

       array[n] = nxtpos;
       if(count == 0){
               *nxtpos++ = 0;
               return;
       }
       for(i=tptr-1;i>=0;i--){
               j = array[i];
               if(j && *j++ == count){
                       for(k=0;k<count;k++)
                               if(!tmpstat[*j++])break;
                       if(k >= count){
                               array[n] = array[i];
                               return;
                       }
               }
       }
       add(array,n);
}
# endif

You are viewing proxied material from sdf.org. The copyright of proxied material belongs to its original authors. Any comments or complaints in relation to proxied material should be directed to the original authors of the content concerned. Please see the disclaimer for more details.