ref: a3f2d6d23ed1be69fee607bdedadc0438fd01305
dir: /sys/src/cmd/lex/sub2.c/
# 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