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":""));
115 if(v >= tptr-1)return;
119 /* will not be CHAR RNULLS FINAL S1FINAL S2FINAL RCCL RNCCL */
121 if(tmpstat[p] == FALSE){
126 case STAR: case PLUS:
130 case BAR: case QUEST: case RNEWE:
135 if(nullstr[right[p]])
141 case RSCON: case CARAT:
146 warning("bad switch follow %d",p);
152 first(int v) /* calculate set of positions with v as root which can be active initially */
159 case 1: case RCCL: case RNCCL: case RNULLS: case FINAL: case S1FINAL: case S2FINAL:
160 if(tmpstat[v] == FALSE){
165 case BAR: case RNEWE:
175 p = (uchar *)right[v];
182 case STAR: case QUEST: case PLUS: case RSTR:
192 warning("bad switch first %d",v);
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;
212 if(tptr > 0)first(tptr-1);
217 print("%s:\n",sname[stnum/2]);
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++){
232 for(i=0;i<NCH;i++) symbol[i] = 0;
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]){
249 symbol[right[curpos]] = TRUE;
258 warning("bad switch cgoto %d state %d",curpos,s);
265 print("State %d transitions on:\n\t",s);
267 for(i = 1; i<NCH; i++){
268 if(symbol[i]) allprint(i);
269 if(charc > LINESIZE){
277 /* for each char, calculate next state */
279 for(i = 1; i<NCH; 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){
286 error("Too many states %s",(nstates == NSTATES ? "\nTry using %n num":""));
289 if(debug)pstate(stnum);
293 } else { /* xstate >= 0 ==> state exists */
301 /* pack transitions into permanent array */
302 if(n > 0) packtrans(s,tch,tst,n,tryit);
305 Bprint(&fout,"0};\n");
308 /* Beware -- 70% of total CPU time is spent in this subroutine -
309 if you don't believe me - try it yourself ! */
311 nextstate(int s, int c)
315 int *pos, i, *f, num, curpos, number;
316 /* state to goto from state s on char c */
320 for(i = 0; i<num; i++){
324 || j == RSTR && c == right[curpos]
325 || j == RCCL && member(c, ptr[curpos])){
329 for(j=0;j<number;j++)
347 { /* see if tmpstat occurs previously */
355 for(i=n;i>=0;i--){ /* for each state */
359 if(!temp[*j++])break;
368 packtrans(int st, uchar *tch, int *tst, int cnt, int tryit)
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 */
374 /* sfall[st] = t implies t is fall back state for st */
375 /* == -1 implies no fall back */
378 int cmin, cval, tcnt, diff, p, *ast;
380 int go[NCH], temp[NCH], c;
390 /* try to pack transitions using ccl's */
391 if(tryit){ /* ccl's used */
393 go[i] = temp[i] = -1;
402 if(go[c] != tst[i] || c == tch[i])
403 temp[tch[i]] = tst[i];
405 /* fill in error entries */
407 if(symbol[i]) temp[i] = -2; /* error trans */
411 if(temp[i] != -1)k++;
412 if(k <cnt){ /* compress by char */
414 if(debug) print("use compression %d, %d vs %d\n",st,k,cnt);
420 swork[k++] = (temp[i] == -2 ? -1 : temp[i]);
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;
437 if(p == -1) /* no transitions */ continue;
439 if(tcnt > cnt) continue;
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++;
455 if(p < upper)diff = NCH;
456 if(diff < cval && diff < tcnt){
462 /* cmin = state "most like" state st */
464 if(debug)print("select st %d for st %d diff %d\n",cmin,st,cval);
467 if(cmin != -1){ /* if we can use st cmin */
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]){
478 nchar[nptr] = ach[j];
479 nexts[++nptr] = ast[j];
482 if(nchar[p-1] == 0)break;
483 if(ach[j] > nchar[p-1]){
484 warning("bad transition %d %d",st,cmin);
487 /* ach[j] == nchar[p-1] */
488 if(ast[j] != nexts[p] || ast[j] == -1 || (cpackflg[st] && ach[j] != match[ach[j]])){
490 nchar[nptr] = ach[j];
491 nexts[++nptr] = ast[j];
497 nchar[nptr] = ach[j];
498 nexts[++nptr] = ast[j++];
501 nexts[gotof[st]] = cnt = k;
510 nchar[nptr] = ach[i];
511 nexts[++nptr] = ast[i];
522 error("Too many transitions %s",(ntrans==NTRANS?"\nTry using %a num":""));
530 print("State %d:\n",s);
535 for(j = 1; j<i; j++){
537 if(j%30 == 0)print("\n");
544 member(int d, uchar *t)
553 if(*s++ == c) return(1);
563 print("State %d:",i);
564 /* print actions, if any */
566 if(t != -1)print(" final");
568 if(cpackflg[i] == TRUE)print("backup char in use\n");
569 if(sfall[i] != -1)print("fall back state %d\n",sfall[i]);
572 print("(%d transitions)\n",nexts[p]);
576 print("%d\t",nexts[p+1]);
578 allprint(nchar[p++]);
579 while(nexts[p] == nexts[p+1] && nchar[p]){
580 if(charc > LINESIZE){
584 allprint(nchar[p++]);
593 acompute(int s) /* compute action list = set of poss. actions */
597 int temp[300], k, neg[300], n;
604 error("Too many positions for one state - acompute");
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");
610 } else if(name[*p] == S2FINAL)neg[n++] = left[*p];
614 if(k < 1 && n < 1) return;
616 if(debug) print("final %d actions:",s);
618 /* sort action list */
621 if(temp[j] < temp[i]){
628 if(temp[i] == temp[i+1]) temp[i] = 0;
629 /* copy to permanent quarters */
632 Bprint(&fout,"/* actions for state %d */",s);
637 Bprint(&fout,"%d,\n",temp[i]);
640 print("%d ",temp[i]);
644 for(i=0;i<n;i++){ /* copy fall back actions - all neg */
645 Bprint(&fout,"%d,\n",neg[i]);
648 if(debug)print("%d ",neg[i]);
652 if(debug)print("\n");
654 Bprint(&fout,"0,\n");
661 /* print character class sets */
664 print("char class intersection\n");
665 for(i=0; i< ccount; i++){
667 print("class %d:\n\t",i);
671 if(charc > LINESIZE){
682 if(charc > LINESIZE){
697 for(i=0; i<ccount; i++)
700 if(tab[cindex[i]] == 0)
702 /* tab[i] = principal char for new ccl i */
703 for(i = 1; i<NCH; i++)
704 match[i] = tab[cindex[i]];
710 /* format and output final program's tables */
712 int top, bot, startup, omin;
714 for(i=0; i<outsize;i++)
715 verify[i] = advance[i] = 0;
718 for(i=0; i<= stnum; i++){ /* for each state */
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");
737 while(verify[omin+NCH]) omin++;
740 if (debug) print("bot,top %d, %d startup begins %d\n",bot,top,startup);
744 if(startup > outsize - NCH)
745 error("output table overflow");
746 for(j = bot; j<= top; j++){
747 k = startup + nchar[j];
751 /* have found place */
753 if (debug) print(" startup going to be %d\n", startup);
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;
764 /* stoff[i] = offset into verify, advance for trans for state i */
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){
772 Bprint(&fout,"%d,%d,\t",verify[k],advance[k]);
774 Bprint(&fout,"0,0,\t");
778 Bprint(&fout,"0,0};\n");
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]);
788 Bprint(&fout,"yysvec+%d,\t", sfall[i]+1); /* state + 1 */
789 else Bprint(&fout,"0,\t\t");
791 Bprint(&fout,"yyvstop+%d,",atable[i]);
792 else Bprint(&fout,"0,\t");
794 Bprint(&fout,"\t\t/* state %d */",i);
798 Bprint(&fout,"0,\t0,\t0};\n");
800 /* put out yymatch */
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){
809 if(isprint(fbch) && fbch != '\'' && fbch != '\\')
810 Bprint(&fout,"'%c' ,",fbch);
811 else Bprint(&fout,"0%-3o,",fbch);
815 Bprint(&fout,"0};\n");
816 /* put out yyextra */
817 Bprint(&fout,"Uchar yyextra[] = {\n");
818 for(i=0;i<casecount;i+=8){
820 Bprint(&fout, "%d,", i+j<NACTIONS ?
824 Bprint(&fout,"0};\n");
829 padd(int **array, int n)
838 for(i=tptr-1;i>=0;i--){
840 if(j && *j++ == count){
842 if(!tmpstat[*j++])break;