8 if(i < NCH) i = 1; /* character */
10 case 1: case RSTR: case RCCL: case RNCCL: case RNULLS:
16 padd(foll,v); /* packing version */
19 add(foll,v); /* no packing version */
21 if(i == RSTR) cfoll(left[v]);
22 else if(i == RCCL || i == RNCCL){ /* compress ccl list */
24 symbol[j] = (i==RNCCL);
27 symbol[*p++] = (i == RCCL);
31 for(k=0;p+k < pcptr; k++)
32 if(cindex[j] == *(p+k))
34 if(p+k >= pcptr)*pcptr++ = cindex[j];
37 if(pcptr > pchar + pchlen)
38 error("Too many packed character classes");
40 name[v] = RCCL; /* RNCCL eliminated */
43 print("ccl %d: %d",v,*p++);
54 case STAR: case PLUS: case QUEST: case RSCON:
57 case BAR: case RCAT: case DIV: case RNEWE:
67 warning("bad switch cfoll %d",v);
78 /* print sets of chars which may follow positions */
79 print("pos\tchars\n");
84 print("%d:\t%d",i,*p++);
94 add(int **array, int n)
101 array[n] = nxtpos; /* note no packing is done in positions */
107 if(nxtpos >= positions+maxpos)
108 error("Too many positions %s",(maxpos== MAXPOS?"\nTry using %p num":""));
116 if(v >= tptr-1)return;
120 /* will not be CHAR RNULLS FINAL S1FINAL S2FINAL RCCL RNCCL */
122 if(tmpstat[p] == FALSE){
127 case STAR: case PLUS:
131 case BAR: case QUEST: case RNEWE:
136 if(nullstr[right[p]])
142 case RSCON: case CARAT:
147 warning("bad switch follow %d",p);
153 first(int v) /* calculate set of positions with v as root which can be active initially */
160 case 1: case RCCL: case RNCCL: case RNULLS: case FINAL: case S1FINAL: case S2FINAL:
161 if(tmpstat[v] == FALSE){
166 case BAR: case RNEWE:
176 p = (uchar*)right[v];
183 case STAR: case QUEST: case PLUS: case RSTR:
193 warning("bad switch first %d",v);
208 /* generate initial state, for each start condition */
209 Bprint(&fout,"int yyvstop[] = {\n0,\n");
210 while(stnum < 2 || stnum/2 < sptr){
211 for(i = 0; i<tptr; i++) tmpstat[i] = 0;
213 if(tptr > 0)first(tptr-1);
218 print("%s:\n",sname[stnum/2]);
225 /* even stnum = might not be at line begin */
226 /* odd stnum = must be at line begin */
227 /* even states can occur anywhere, odd states only at line begin */
228 for(s = 0; s <= stnum; s++){
233 for(i=0;i<NCH;i++) symbol[i] = 0;
235 for(i = 1; i<=npos; i++){
236 curpos = *(state[s]+i);
237 if(name[curpos] < NCH) symbol[name[curpos]] = TRUE;
238 else switch(name[curpos]){
250 symbol[right[curpos]] = TRUE;
259 warning("bad switch cgoto %d state %d",curpos,s);
266 print("State %d transitions on:\n\t",s);
268 for(i = 1; i<NCH; i++){
269 if(symbol[i]) allprint(i);
270 if(charc > LINESIZE){
278 /* for each char, calculate next state */
280 for(i = 1; i<NCH; i++){
282 nextstate(s,i); /* executed for each state, transition pair */
283 xstate = notin(stnum);
284 if(xstate == -2) warning("bad state %d %o",s,i);
285 else if(xstate == -1){
287 error("Too many states %s",(nstates == NSTATES ? "\nTry using %n num":""));
290 if(debug)pstate(stnum);
294 } else { /* xstate >= 0 ==> state exists */
302 /* pack transitions into permanent array */
303 if(n > 0) packtrans(s,tch,tst,n,tryit);
306 Bprint(&fout,"0};\n");
309 /* Beware -- 70% of total CPU time is spent in this subroutine -
310 if you don't believe me - try it yourself ! */
312 nextstate(int s, int c)
316 int *pos, i, *f, num, curpos, number;
317 /* state to goto from state s on char c */
321 for(i = 0; i<num; i++){
325 || j == RSTR && c == right[curpos]
326 || j == RCCL && member(c, ptr[curpos])){
330 for(j=0;j<number;j++)
348 { /* see if tmpstat occurs previously */
356 for(i=n;i>=0;i--){ /* for each state */
360 if(!temp[*j++])break;
369 packtrans(int st, uchar *tch, int *tst, int cnt, int tryit)
371 /* pack transitions into nchar, nexts */
372 /* nchar is terminated by '\0', nexts uses cnt, followed by elements */
373 /* gotof[st] = index into nchr, nexts for state st */
375 /* sfall[st] = t implies t is fall back state for st */
376 /* == -1 implies no fall back */
379 int cmin, cval, tcnt, diff, p, *ast;
381 int go[NCH], temp[NCH], c;
391 /* try to pack transitions using ccl's */
392 if(tryit){ /* ccl's used */
394 go[i] = temp[i] = -1;
403 if(go[c] != tst[i] || c == tch[i])
404 temp[tch[i]] = tst[i];
406 /* fill in error entries */
408 if(symbol[i]) temp[i] = -2; /* error trans */
412 if(temp[i] != -1)k++;
413 if(k <cnt){ /* compress by char */
415 if(debug) print("use compression %d, %d vs %d\n",st,k,cnt);
421 swork[k++] = (temp[i] == -2 ? -1 : temp[i]);
432 for(i=0; i<st; i++){ /* get most similar state */
433 /* reject state with more transitions, state already represented by a third state,
434 and state which is compressed by char if ours is not to be */
435 if(sfall[i] != -1) continue;
436 if(cpackflg[st] == 1) if(!(cpackflg[i] == 1)) continue;
438 if(p == -1) /* no transitions */ continue;
440 if(tcnt > cnt) continue;
444 while(ach[j] && p < upper){
445 while(ach[j] < nchar[p] && ach[j]){diff++; j++; }
446 if(ach[j] == 0)break;
447 if(ach[j] > nchar[p]){diff=NCH;break;}
448 /* ach[j] == nchar[p] */
449 if(ast[j] != nexts[++p] || ast[j] == -1 || (cpackflg[st] && ach[j] != match[ach[j]]))diff++;
456 if(p < upper)diff = NCH;
457 if(diff < cval && diff < tcnt){
463 /* cmin = state "most like" state st */
465 if(debug)print("select st %d for st %d diff %d\n",cmin,st,cval);
468 if(cmin != -1){ /* if we can use st cmin */
475 /* if cmin has a transition on c, then so will st */
476 /* st may be "larger" than cmin, however */
477 while(ach[j] < nchar[p-1] && ach[j]){
479 nchar[nptr] = ach[j];
480 nexts[++nptr] = ast[j];
483 if(nchar[p-1] == 0)break;
484 if(ach[j] > nchar[p-1]){
485 warning("bad transition %d %d",st,cmin);
488 /* ach[j] == nchar[p-1] */
489 if(ast[j] != nexts[p] || ast[j] == -1 || (cpackflg[st] && ach[j] != match[ach[j]])){
491 nchar[nptr] = ach[j];
492 nexts[++nptr] = ast[j];
498 nchar[nptr] = ach[j];
499 nexts[++nptr] = ast[j++];
502 nexts[gotof[st]] = cnt = k;
511 nchar[nptr] = ach[i];
512 nexts[++nptr] = ast[i];
523 error("Too many transitions %s",(ntrans==NTRANS?"\nTry using %a num":""));
531 print("State %d:\n",s);
536 for(j = 1; j<i; j++){
538 if(j%30 == 0)print("\n");
546 member(int d, uchar *t)
555 if(*s++ == c) return(1);
565 print("State %d:",i);
566 /* print actions, if any */
568 if(t != -1)print(" final");
570 if(cpackflg[i] == TRUE)print("backup char in use\n");
571 if(sfall[i] != -1)print("fall back state %d\n",sfall[i]);
574 print("(%d transitions)\n",nexts[p]);
578 print("%d\t",nexts[p+1]);
580 allprint(nchar[p++]);
581 while(nexts[p] == nexts[p+1] && nchar[p]){
582 if(charc > LINESIZE){
586 allprint(nchar[p++]);
595 acompute(int s) /* compute action list = set of poss. actions */
599 int temp[300], k, neg[300], n;
606 error("Too many positions for one state - acompute");
608 if(name[*p] == FINAL)temp[k++] = left[*p];
609 else if(name[*p] == S1FINAL){temp[k++] = left[*p];
610 if (left[*p] >= NACTIONS) error("Too many right contexts");
612 } else if(name[*p] == S2FINAL)neg[n++] = left[*p];
616 if(k < 1 && n < 1) return;
618 if(debug) print("final %d actions:",s);
620 /* sort action list */
623 if(temp[j] < temp[i]){
630 if(temp[i] == temp[i+1]) temp[i] = 0;
631 /* copy to permanent quarters */
634 Bprint(&fout,"/* actions for state %d */",s);
639 Bprint(&fout,"%d,\n",temp[i]);
642 print("%d ",temp[i]);
646 for(i=0;i<n;i++){ /* copy fall back actions - all neg */
647 Bprint(&fout,"%d,\n",neg[i]);
650 if(debug)print("%d ",neg[i]);
654 if(debug)print("\n");
656 Bprint(&fout,"0,\n");
664 /* print character class sets */
667 print("char class intersection\n");
668 for(i=0; i< ccount; i++){
670 print("class %d:\n\t",i);
674 if(charc > LINESIZE){
685 if(charc > LINESIZE){
701 for(i=0; i<ccount; i++)
704 if(tab[cindex[i]] == 0)
706 /* tab[i] = principal char for new ccl i */
707 for(i = 1; i<NCH; i++)
708 match[i] = tab[cindex[i]];
715 /* format and output final program's tables */
717 int top, bot, startup, omin;
719 for(i=0; i<outsize;i++)
720 verify[i] = advance[i] = 0;
723 for(i=0; i<= stnum; i++){ /* for each state */
734 print("State %d: (layout)\n", i);
735 for(j=bot; j<=top;j++) {
736 print(" %o", nchar[j]);
737 if (j%10==0) print("\n");
742 while(verify[omin+NCH]) omin++;
745 if (debug) print("bot,top %d, %d startup begins %d\n",bot,top,startup);
749 if(startup > outsize - NCH)
750 error("output table overflow");
751 for(j = bot; j<= top; j++){
752 k = startup + nchar[j];
756 /* have found place */
758 if (debug) print(" startup going to be %d\n", startup);
760 for(j = bot; j<= top; j++){
761 k = startup + nchar[j];
762 verify[k] = i+1; /* state number + 1*/
763 advance[k] = nexts[j+1]+1; /* state number + 1*/
764 if(yytop < k) yytop = k;
769 /* stoff[i] = offset into verify, advance for trans for state i */
771 Bprint(&fout,"# define YYTYPE %s\n",stnum+1 >= NCH ? "int" : "Uchar");
772 Bprint(&fout,"struct yywork { YYTYPE verify, advance; } yycrank[] = {\n");
773 for(i=0;i<=yytop;i+=4){
777 Bprint(&fout,"%d,%d,\t",verify[k],advance[k]);
779 Bprint(&fout,"0,0,\t");
783 Bprint(&fout,"0,0};\n");
787 Bprint(&fout,"struct yysvf yysvec[] = {\n");
788 Bprint(&fout,"0,\t0,\t0,\n");
789 for(i=0;i<=stnum;i++){ /* for each state */
790 if(cpackflg[i])stoff[i] = -stoff[i];
791 Bprint(&fout,"yycrank+%d,\t",stoff[i]);
793 Bprint(&fout,"yysvec+%d,\t", sfall[i]+1); /* state + 1 */
794 else Bprint(&fout,"0,\t\t");
796 Bprint(&fout,"yyvstop+%d,",atable[i]);
797 else Bprint(&fout,"0,\t");
799 Bprint(&fout,"\t\t/* state %d */",i);
803 Bprint(&fout,"0,\t0,\t0};\n");
805 /* put out yymatch */
807 Bprint(&fout,"struct yywork *yytop = yycrank+%d;\n",yytop);
808 Bprint(&fout,"struct yysvf *yybgin = yysvec+1;\n");
809 Bprint(&fout,"Uchar yymatch[] = {\n");
810 for(i=0; i<NCH; i+=8){
814 if(isprint(fbch) && fbch != '\'' && fbch != '\\')
815 Bprint(&fout,"'%c' ,",fbch);
816 else Bprint(&fout,"0%-3o,",fbch);
820 Bprint(&fout,"0};\n");
821 /* put out yyextra */
822 Bprint(&fout,"Uchar yyextra[] = {\n");
823 for(i=0;i<casecount;i+=8){
825 Bprint(&fout, "%d,", i+j<NACTIONS ?
829 Bprint(&fout,"0};\n");
834 padd(int **array, int n)
843 for(i=tptr-1;i>=0;i--){
845 if(j && *j++ == count){
847 if(!tmpstat[*j++])break;