Subversion Repositories planix.SVN

Rev

Details | Last modification | View Log | RSS feed

Rev Author Line No. Line
2 - 1 
# include "ldefs.h"
2 
void
3 
cfoll(int v)
4 
{
5 
	int i,j,k;
6 
	uchar *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 = ptr[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 
				ptr[v] = p;
40 
				name[v] = RCCL;	/* RNCCL eliminated */
41 
# ifdef DEBUG
42 
				if(debug && *p){
43 
					print("ccl %d: %d",v,*p++);
44 
					while(*p)
45 
						print(", %d",*p++);
46 
					print("\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 
}
71 
 
72 
# ifdef DEBUG
73 
void
74 
pfoll(void)
75 
	{
76 
	int i,k,*p;
77 
	int j;
78 
	/* print sets of chars which may follow positions */
79 
	print("pos\tchars\n");
80 
	for(i=0;i<tptr;i++)
81 
		if(p=foll[i]){
82 
			j = *p++;
83 
			if(j >= 1){
84 
				print("%d:\t%d",i,*p++);
85 
				for(k=2;k<=j;k++)
86 
					print(", %d",*p++);
87 
				print("\n");
88 
			}
89 
		}
90 
}
91 
# endif
92 
 
93 
void
94 
add(int **array, int n)
95 
{
96 
	int i, *temp;
97 
	uchar *ctemp;
98 
 
99 
	temp = nxtpos;
100 
	ctemp = tmpstat;
101 
	array[n] = nxtpos;		/* note no packing is done in positions */
102 
	*temp++ = count;
103 
	for(i=0;i<tptr;i++)
104 
		if(ctemp[i] == TRUE)
105 
			*temp++ = i;
106 
	nxtpos = temp;
107 
	if(nxtpos >= positions+maxpos)
108 
		error("Too many positions %s",(maxpos== MAXPOS?"\nTry using %p num":""));
109 
}
110 
 
111 
void
112 
follow(int v)
113 
{
114 
	int p;
115 
	if(v >= tptr-1)return;
116 
	p = parent[v];
117 
	if(p == 0) return;
118 
	switch(name[p]){
119 
			/* will not be CHAR RNULLS FINAL S1FINAL S2FINAL RCCL RNCCL */
120 
		case RSTR:
121 
			if(tmpstat[p] == FALSE){
122 
				count++;
123 
				tmpstat[p] = TRUE;
124 
			}
125 
			break;
126 
		case STAR: case PLUS:
127 
			first(v);
128 
			follow(p);
129 
			break;
130 
		case BAR: case QUEST: case RNEWE:
131 
			follow(p);
132 
			break;
133 
		case RCAT: case DIV:
134 
			if(v == left[p]){
135 
				if(nullstr[right[p]])
136 
					follow(p);
137 
				first(right[p]);
138 
			}
139 
			else follow(p);
140 
			break;
141 
		case RSCON: case CARAT:
142 
			follow(p);
143 
			break;
144 
# ifdef DEBUG
145 
		default:
146 
			warning("bad switch follow %d",p);
147 
# endif
148 
	}
149 
}
150 
 
151 
void
152 
first(int v)	/* calculate set of positions with v as root which can be active initially */
153 
{
154 
	int i;
155 
	uchar *p;
156 
	i = name[v];
157 
	if(i < NCH)i = 1;
158 
	switch(i){
159 
		case 1: case RCCL: case RNCCL: case RNULLS: case FINAL: case S1FINAL: case S2FINAL:
160 
			if(tmpstat[v] == FALSE){
161 
				count++;
162 
				tmpstat[v] = TRUE;
163 
			}
164 
			break;
165 
		case BAR: case RNEWE:
166 
			first(left[v]);
167 
			first(right[v]);
168 
			break;
169 
		case CARAT:
170 
			if(stnum % 2 == 1)
171 
				first(left[v]);
172 
			break;
173 
		case RSCON:
174 
			i = stnum/2 +1;
175 
			p = (uchar *)right[v];
176 
			while(*p)
177 
				if(*p++ == i){
178 
					first(left[v]);
179 
					break;
180 
				}
181 
			break;
182 
		case STAR: case QUEST: case PLUS:  case RSTR:
183 
			first(left[v]);
184 
			break;
185 
		case RCAT: case DIV:
186 
			first(left[v]);
187 
			if(nullstr[left[v]])
188 
				first(right[v]);
189 
			break;
190 
# ifdef DEBUG
191 
		default:
192 
			warning("bad switch first %d",v);
193 
# endif
194 
	}
195 
}
196 
 
197 
void
198 
cgoto(void)
199 
{
200 
	int i, j, s;
201 
	int npos, curpos, n;
202 
	int tryit;
203 
	uchar tch[NCH];
204 
	int tst[NCH];
205 
	uchar *q;
206 
 
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;
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 
				print("%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 = ptr[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 
			print("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 
					print("\n\t");
272 
				}
273 
			}
274 
			print("\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 
				} else {		/* xstate >= 0 ==> state exists */
294 
					tch[n] = i;
295 
					tst[n++] = xstate;
296 
				}
297 
			}
298 
		}
299 
		tch[n] = 0;
300 
		tst[n] = -1;
301 
		/* pack transitions into permanent array */
302 
		if(n > 0) packtrans(s,tch,tst,n,tryit);
303 
		else gotof[s] = -1;
304 
	}
305 
	Bprint(&fout,"0};\n");
306 
}
307 
 
308 
/*	Beware -- 70% of total CPU time is spent in this subroutine -
309 
	if you don't believe me - try it yourself ! */
310 
void
311 
nextstate(int s, int c)
312 
{
313 
	int j, *newpos;
314 
	uchar *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, ptr[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 
}
344 
 
345 
int
346 
notin(int n)
347 
{	/* see if tmpstat occurs previously */
348 
	int *j,k;
349 
	uchar *temp;
350 
	int i;
351 
 
352 
	if(count == 0)
353 
		return(-2);
354 
	temp = tmpstat;
355 
	for(i=n;i>=0;i--){	/* for each state */
356 
		j = state[i];
357 
		if(count == *j++){
358 
			for(k=0;k<count;k++)
359 
				if(!temp[*j++])break;
360 
			if(k >= count)
361 
				return(i);
362 
		}
363 
	}
364 
	return(-1);
365 
}
366 
 
367 
void
368 
packtrans(int st, uchar *tch, int *tst, int cnt, int tryit)
369 
{
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 */
373 
 
374 
	/* sfall[st] =  t implies t is fall back state for st */
375 
	/*	        == -1 implies no fall back */
376 
 
377 
	int i,j,k;
378 
	int cmin, cval, tcnt, diff, p, *ast;
379 
	uchar *ach;
380 
	int go[NCH], temp[NCH], c;
381 
	int swork[NCH];
382 
	uchar cwork[NCH];
383 
	int upper;
384 
 
385 
	rcount += cnt;
386 
	cmin = -1;
387 
	cval = NCH;
388 
	ast = tst;
389 
	ach = tch;
390 
	/* try to pack transitions using ccl's */
391 
	if(tryit){	/* ccl's used */
392 
		for(i=1;i<NCH;i++){
393 
			go[i] = temp[i] = -1;
394 
			symbol[i] = 1;
395 
		}
396 
		for(i=0;i<cnt;i++){
397 
			go[tch[i]] = tst[i];
398 
			symbol[tch[i]] = 0;
399 
		}
400 
		for(i=0; i<cnt;i++){
401 
			c = match[tch[i]];
402 
			if(go[c] != tst[i] || c == tch[i])
403 
				temp[tch[i]] = tst[i];
404 
		}
405 
		/* fill in error entries */
406 
		for(i=1;i<NCH;i++)
407 
			if(symbol[i]) temp[i] = -2;	/* error trans */
408 
		/* count them */
409 
		k = 0;
410 
		for(i=1;i<NCH;i++)
411 
			if(temp[i] != -1)k++;
412 
		if(k <cnt){	/* compress by char */
413 
# ifdef DEBUG
414 
			if(debug) print("use compression  %d,  %d vs %d\n",st,k,cnt);
415 
# endif
416 
			k = 0;
417 
			for(i=1;i<NCH;i++)
418 
				if(temp[i] != -1){
419 
					cwork[k] = i;
420 
					swork[k++] = (temp[i] == -2 ? -1 : temp[i]);
421 
				}
422 
			cwork[k] = 0;
423 
# ifdef PC
424 
			ach = cwork;
425 
			ast = swork;
426 
			cnt = k;
427 
			cpackflg[st] = TRUE;
428 
# endif
429 
		}
430 
	}
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;
436 
		p = gotof[i];
437 
		if(p == -1) /* no transitions */ continue;
438 
		tcnt = nexts[p];
439 
		if(tcnt > cnt) continue;
440 
		diff = 0;
441 
		j = 0;
442 
		upper = p + tcnt;
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++;
449 
			j++;
450 
		}
451 
		while(ach[j]){
452 
			diff++;
453 
			j++;
454 
		}
455 
		if(p < upper)diff = NCH;
456 
		if(diff < cval && diff < tcnt){
457 
			cval = diff;
458 
			cmin = i;
459 
			if(cval == 0)break;
460 
		}
461 
	}
462 
	/* cmin = state "most like" state st */
463 
# ifdef DEBUG
464 
	if(debug)print("select st %d for st %d diff %d\n",cmin,st,cval);
465 
# endif
466 
# ifdef PS
467 
	if(cmin != -1){ /* if we can use st cmin */
468 
		gotof[st] = nptr;
469 
		k = 0;
470 
		sfall[st] = cmin;
471 
		p = gotof[cmin]+1;
472 
		j = 0;
473 
		while(ach[j]){
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]){
477 
				k++;
478 
				nchar[nptr] = ach[j];
479 
				nexts[++nptr] = ast[j];
480 
				j++;
481 
			}
482 
			if(nchar[p-1] == 0)break;
483 
			if(ach[j] > nchar[p-1]){
484 
				warning("bad transition %d %d",st,cmin);
485 
				goto nopack;
486 
			}
487 
			/* ach[j] == nchar[p-1] */
488 
			if(ast[j] != nexts[p] || ast[j] == -1 || (cpackflg[st] && ach[j] != match[ach[j]])){
489 
				k++;
490 
				nchar[nptr] = ach[j];
491 
				nexts[++nptr] = ast[j];
492 
			}
493 
			p++;
494 
			j++;
495 
		}
496 
		while(ach[j]){
497 
			nchar[nptr] = ach[j];
498 
			nexts[++nptr] = ast[j++];
499 
			k++;
500 
		}
501 
		nexts[gotof[st]] = cnt = k;
502 
		nchar[nptr++] = 0;
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 
	} else
521 
		if(nptr > ntrans)
522 
			error("Too many transitions %s",(ntrans==NTRANS?"\nTry using %a num":""));
523 
}
524 
 
525 
# ifdef DEBUG
526 
void
527 
pstate(int s)
528 
{
529 
	int *p,i,j;
530 
	print("State %d:\n",s);
531 
	p = state[s];
532 
	i = *p++;
533 
	if(i == 0) return;
534 
	print("%4d",*p++);
535 
	for(j = 1; j<i; j++){
536 
		print(", %4d",*p++);
537 
		if(j%30 == 0)print("\n");
538 
	}
539 
	print("\n");
540 
}
541 
# endif
542 
 
543 
int
544 
member(int d, uchar *t)
545 
{
546 
	int c;
547 
	uchar *s;
548 
 
549 
	c = d;
550 
	s = t;
551 
	c = cindex[c];
552 
	while(*s)
553 
		if(*s++ == c) return(1);
554 
	return(0);
555 
}
556 
 
557 
# ifdef DEBUG
558 
void
559 
stprt(int i)
560 
{
561 
	int p, t;
562 
 
563 
	print("State %d:",i);
564 
	/* print actions, if any */
565 
	t = atable[i];
566 
	if(t != -1)print(" final");
567 
	print("\n");
568 
	if(cpackflg[i] == TRUE)print("backup char in use\n");
569 
	if(sfall[i] != -1)print("fall back state %d\n",sfall[i]);
570 
	p = gotof[i];
571 
	if(p == -1) return;
572 
	print("(%d transitions)\n",nexts[p]);
573 
	while(nchar[p]){
574 
		charc = 0;
575 
		if(nexts[p+1] >= 0)
576 
			print("%d\t",nexts[p+1]);
577 
		else print("err\t");
578 
		allprint(nchar[p++]);
579 
		while(nexts[p] == nexts[p+1] && nchar[p]){
580 
			if(charc > LINESIZE){
581 
				charc = 0;
582 
				print("\n\t");
583 
			}
584 
			allprint(nchar[p++]);
585 
		}
586 
		print("\n");
587 
	}
588 
	print("\n");
589 
}
590 
# endif
591 
 
592 
void
593 
acompute(int s)	/* compute action list = set of poss. actions */
594 
{
595 
	int *p, i, j;
596 
	int cnt, m;
597 
	int temp[300], k, neg[300], n;
598 
 
599 
	k = 0;
600 
	n = 0;
601 
	p = state[s];
602 
	cnt = *p++;
603 
	if(cnt > 300)
604 
		error("Too many positions for one state - acompute");
605 
	for(i=0;i<cnt;i++){
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");
609 
			extra[left[*p]] = 1;
610 
		} else if(name[*p] == S2FINAL)neg[n++] = left[*p];
611 
		p++;
612 
	}
613 
	atable[s] = -1;
614 
	if(k < 1 && n < 1) return;
615 
# ifdef DEBUG
616 
	if(debug) print("final %d actions:",s);
617 
# endif
618 
	/* sort action list */
619 
	for(i=0; i<k; i++)
620 
		for(j=i+1;j<k;j++)
621 
			if(temp[j] < temp[i]){
622 
				m = temp[j];
623 
				temp[j] = temp[i];
624 
				temp[i] = m;
625 
			}
626 
	/* remove dups */
627 
	for(i=0;i<k-1;i++)
628 
		if(temp[i] == temp[i+1]) temp[i] = 0;
629 
	/* copy to permanent quarters */
630 
	atable[s] = aptr;
631 
# ifdef DEBUG
632 
	Bprint(&fout,"/* actions for state %d */",s);
633 
# endif
634 
	Bputc(&fout, '\n');
635 
	for(i=0;i<k;i++)
636 
		if(temp[i] != 0){
637 
			Bprint(&fout,"%d,\n",temp[i]);
638 
# ifdef DEBUG
639 
			if(debug)
640 
				print("%d ",temp[i]);
641 
# endif
642 
			aptr++;
643 
		}
644 
	for(i=0;i<n;i++){		/* copy fall back actions - all neg */
645 
		Bprint(&fout,"%d,\n",neg[i]);
646 
		aptr++;
647 
# ifdef DEBUG
648 
		if(debug)print("%d ",neg[i]);
649 
# endif
650 
	}
651 
# ifdef DEBUG
652 
	if(debug)print("\n");
653 
# endif
654 
	Bprint(&fout,"0,\n");
655 
	aptr++;
656 
}
657 
 
658 
# ifdef DEBUG
659 
void
660 
pccl(void) {
661 
	/* print character class sets */
662 
	int i, j;
663 
 
664 
	print("char class intersection\n");
665 
	for(i=0; i< ccount; i++){
666 
		charc = 0;
667 
		print("class %d:\n\t",i);
668 
		for(j=1;j<NCH;j++)
669 
			if(cindex[j] == i){
670 
				allprint(j);
671 
				if(charc > LINESIZE){
672 
					print("\n\t");
673 
					charc = 0;
674 
				}
675 
			}
676 
		print("\n");
677 
	}
678 
	charc = 0;
679 
	print("match:\n");
680 
	for(i=0;i<NCH;i++){
681 
		allprint(match[i]);
682 
		if(charc > LINESIZE){
683 
			print("\n");
684 
			charc = 0;
685 
		}
686 
	}
687 
	print("\n");
688 
}
689 
# endif
690 
 
691 
void
692 
mkmatch(void)
693 
{
694 
	int i;
695 
	uchar tab[NCH];
696 
 
697 
	for(i=0; i<ccount; i++)
698 
		tab[i] = 0;
699 
	for(i=1;i<NCH;i++)
700 
		if(tab[cindex[i]] == 0)
701 
			tab[cindex[i]] = i;
702 
	/* tab[i] = principal char for new ccl i */
703 
	for(i = 1; i<NCH; i++)
704 
		match[i] = tab[cindex[i]];
705 
}
706 
 
707 
void
708 
layout(void)
709 
{
710 
	/* format and output final program's tables */
711 
	int i, j, k;
712 
	int  top, bot, startup, omin;
713 
 
714 
	for(i=0; i<outsize;i++)
715 
		verify[i] = advance[i] = 0;
716 
	omin = 0;
717 
	yytop = 0;
718 
	for(i=0; i<= stnum; i++){	/* for each state */
719 
		j = gotof[i];
720 
		if(j == -1){
721 
			stoff[i] = 0;
722 
			continue;
723 
			}
724 
		bot = j;
725 
		while(nchar[j])j++;
726 
		top = j - 1;
727 
# ifdef DEBUG
728 
		if (debug) {
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");
733 
			}
734 
			print("\n");
735 
		}
736 
# endif
737 
		while(verify[omin+NCH]) omin++;
738 
		startup = omin;
739 
# ifdef DEBUG
740 
		if (debug) print("bot,top %d, %d startup begins %d\n",bot,top,startup);
741 
# endif
742 
		do {
743 
			startup += 1;
744 
			if(startup > outsize - NCH)
745 
				error("output table overflow");
746 
			for(j = bot; j<= top; j++){
747 
				k = startup + nchar[j];
748 
				if(verify[k])break;
749 
			}
750 
		} while (j <= top);
751 
		/* have found place */
752 
# ifdef DEBUG
753 
		if (debug) print(" startup going to be %d\n", startup);
754 
# endif
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;
760 
		}
761 
		stoff[i] = startup;
762 
	}
763 
 
764 
	/* stoff[i] = offset into verify, advance for trans for state i */
765 
	/* put out yywork */
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){
769 
		for(j=0;j<4;j++){
770 
			k = i+j;
771 
			if(verify[k])
772 
				Bprint(&fout,"%d,%d,\t",verify[k],advance[k]);
773 
			else
774 
				Bprint(&fout,"0,0,\t");
775 
		}
776 
		Bputc(&fout, '\n');
777 
	}
778 
	Bprint(&fout,"0,0};\n");
779 
 
780 
	/* put out yysvec */
781 
 
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]);
787 
		if(sfall[i] != -1)
788 
			Bprint(&fout,"yysvec+%d,\t", sfall[i]+1);	/* state + 1 */
789 
		else Bprint(&fout,"0,\t\t");
790 
		if(atable[i] != -1)
791 
			Bprint(&fout,"yyvstop+%d,",atable[i]);
792 
		else Bprint(&fout,"0,\t");
793 
# ifdef DEBUG
794 
		Bprint(&fout,"\t\t/* state %d */",i);
795 
# endif
796 
		Bputc(&fout, '\n');
797 
	}
798 
	Bprint(&fout,"0,\t0,\t0};\n");
799 
 
800 
	/* put out yymatch */
801 
 
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){
806 
		for(j=0; j<8; j++){
807 
			int fbch;
808 
			fbch = match[i+j];
809 
			if(isprint(fbch) && fbch != '\'' && fbch != '\\')
810 
				Bprint(&fout,"'%c' ,",fbch);
811 
			else Bprint(&fout,"0%-3o,",fbch);
812 
		}
813 
		Bputc(&fout, '\n');
814 
	}
815 
	Bprint(&fout,"0};\n");
816 
	/* put out yyextra */
817 
	Bprint(&fout,"Uchar yyextra[] = {\n");
818 
	for(i=0;i<casecount;i+=8){
819 
		for(j=0;j<8;j++)
820 
			Bprint(&fout, "%d,", i+j<NACTIONS ?
821 
				extra[i+j] : 0);
822 
		Bputc(&fout, '\n');
823 
	}
824 
	Bprint(&fout,"0};\n");
825 
}
826 
 
827 
# ifdef PP
828 
void
829 
padd(int **array, int n)
830 
{
831 
	int i, *j, k;
832 
 
833 
	array[n] = nxtpos;
834 
	if(count == 0){
835 
		*nxtpos++ = 0;
836 
		return;
837 
	}
838 
	for(i=tptr-1;i>=0;i--){
839 
		j = array[i];
840 
		if(j && *j++ == count){
841 
			for(k=0;k<count;k++)
842 
				if(!tmpstat[*j++])break;
843 
			if(k >= count){
844 
				array[n] = array[i];
845 
				return;
846 
			}
847 
		}
848 
	}
849 
	add(array,n);
850 
}
851 
# endif