xref: /titanic_44/usr/src/cmd/sgs/lex/common/sub2.c (revision 40e5e17b3361b3eea56a9723071c406894a20b78)
1 /*
2  * CDDL HEADER START
3  *
4  * The contents of this file are subject to the terms of the
5  * Common Development and Distribution License, Version 1.0 only
6  * (the "License").  You may not use this file except in compliance
7  * with the License.
8  *
9  * You can obtain a copy of the license at usr/src/OPENSOLARIS.LICENSE
10  * or http://www.opensolaris.org/os/licensing.
11  * See the License for the specific language governing permissions
12  * and limitations under the License.
13  *
14  * When distributing Covered Code, include this CDDL HEADER in each
15  * file and include the License file at usr/src/OPENSOLARIS.LICENSE.
16  * If applicable, add the following below this CDDL HEADER, with the
17  * fields enclosed by brackets "[]" replaced with your own identifying
18  * information: Portions Copyright [yyyy] [name of copyright owner]
19  *
20  * CDDL HEADER END
21  */
22 /*
23  * Copyright 2005 Sun Microsystems, Inc.
24  * All rights reserved.
25  * Use is subject to license terms.
26  */
27 
28 /*	Copyright (c) 1988 AT&T	*/
29 /*	All Rights Reserved	*/
30 
31 #pragma ident	"%Z%%M%	%I%	%E% SMI"
32 
33 #include "ldefs.c"
34 
35 static void add(int **array, int n);
36 static void follow(int v);
37 static void first(int v);
38 static void nextstate(int s, int c);
39 static void packtrans(int st, CHR *tch, int *tst, int cnt, int tryit);
40 static void acompute(int s);
41 static void rprint(int *a, char *s, int n);
42 static void shiftr(int *a, int n);
43 static void upone(int *a, int n);
44 static void bprint(char *a, char *s, int n);
45 static int notin(int n);
46 static int member(int d, CHR *t);
47 
48 #ifdef PP
49 static void padd(int **array, int n);
50 #endif
51 
52 void
53 cfoll(int v)
54 {
55 	int i, j, k;
56 	CHR *p;
57 	i = name[v];
58 	if (!ISOPERATOR(i))
59 		i = 1;
60 	switch (i) {
61 		case 1: case RSTR: case RCCL: case RNCCL: case RNULLS:
62 			for (j = 0; j < tptr; j++)
63 				tmpstat[j] = FALSE;
64 			count = 0;
65 			follow(v);
66 #ifdef PP
67 			padd(foll, v); /* packing version */
68 #else
69 			add(foll, v); /* no packing version */
70 #endif
71 			if (i == RSTR)
72 				cfoll(left[v]);
73 			else if (i == RCCL || i == RNCCL) {
74 				for (j = 1; j < ncg; j++)
75 					symbol[j] = (i == RNCCL);
76 				p = (CHR *) left[v];
77 				while (*p)
78 					symbol[*p++] = (i == RCCL);
79 				p = pcptr;
80 				for (j = 1; j < ncg; j++)
81 					if (symbol[j]) {
82 						for (k = 0; p + k < pcptr; k++)
83 						    if (cindex[j] == *(p + k))
84 							break;
85 						if (p + k >= pcptr)
86 							*pcptr++ = cindex[j];
87 					}
88 				*pcptr++ = 0;
89 				if (pcptr > pchar + pchlen)
90 					error(
91 					"Too many packed character classes");
92 				left[v] = (int)p;
93 				name[v] = RCCL;	/* RNCCL eliminated */
94 #ifdef DEBUG
95 				if (debug && *p) {
96 					(void) printf("ccl %d: %d", v, *p++);
97 					while (*p)
98 						(void) printf(", %d", *p++);
99 					(void) putchar('\n');
100 				}
101 #endif
102 			}
103 			break;
104 		case CARAT:
105 			cfoll(left[v]);
106 			break;
107 
108 		/* XCU4: add RXSCON */
109 		case RXSCON:
110 
111 		case STAR: case PLUS: case QUEST: case RSCON:
112 			cfoll(left[v]);
113 			break;
114 		case BAR: case RCAT: case DIV: case RNEWE:
115 			cfoll(left[v]);
116 			cfoll(right[v]);
117 			break;
118 #ifdef DEBUG
119 		case FINAL:
120 		case S1FINAL:
121 		case S2FINAL:
122 			break;
123 		default:
124 			warning("bad switch cfoll %d", v);
125 #endif
126 	}
127 }
128 
129 #ifdef DEBUG
130 void
131 pfoll(void)
132 {
133 	int i, k, *p;
134 	int j;
135 	/* print sets of chars which may follow positions */
136 	(void) printf("pos\tchars\n");
137 	for (i = 0; i < tptr; i++)
138 		if (p = foll[i]) {
139 			j = *p++;
140 			if (j >= 1) {
141 				(void) printf("%d:\t%d", i, *p++);
142 				for (k = 2; k <= j; k++)
143 					(void) printf(", %d", *p++);
144 				(void) putchar('\n');
145 			}
146 		}
147 }
148 #endif
149 
150 static void
151 add(int **array, int n)
152 {
153 	int i, *temp;
154 	CHR *ctemp;
155 	temp = nxtpos;
156 	ctemp = tmpstat;
157 	array[n] = nxtpos;	/* note no packing is done in positions */
158 	*temp++ = count;
159 	for (i = 0; i < tptr; i++)
160 		if (ctemp[i] == TRUE)
161 			*temp++ = i;
162 	nxtpos = temp;
163 	if (nxtpos >= positions+maxpos)
164 		error(
165 		"Too many positions %s",
166 		(maxpos == MAXPOS ? "\nTry using %p num" : ""));
167 }
168 
169 static void
170 follow(int v)
171 {
172 	int p;
173 	if (v >= tptr-1)
174 		return;
175 	p = parent[v];
176 	if (p == 0)
177 		return;
178 	switch (name[p]) {
179 	/* will not be CHAR RNULLS FINAL S1FINAL S2FINAL RCCL RNCCL */
180 	case RSTR:
181 		if (tmpstat[p] == FALSE) {
182 			count++;
183 			tmpstat[p] = TRUE;
184 		}
185 		break;
186 	case STAR: case PLUS:
187 		first(v);
188 		follow(p);
189 		break;
190 	case BAR: case QUEST: case RNEWE:
191 		follow(p);
192 		break;
193 	case RCAT: case DIV:
194 		if (v == left[p]) {
195 			if (nullstr[right[p]])
196 				follow(p);
197 			first(right[p]);
198 		}
199 		else
200 			follow(p);
201 		break;
202 	/* XCU4: add RXSCON */
203 	case RXSCON:
204 	case RSCON: case CARAT:
205 		follow(p);
206 		break;
207 #ifdef DEBUG
208 	default:
209 		warning("bad switch follow %d", p);
210 #endif
211 	}
212 }
213 
214 /*
215  * Check if I have a RXSCON in my upper node
216  */
217 static int
218 check_me(int v)
219 {
220 	int tmp = parent[v];
221 
222 	while (name[tmp] != RNEWE) {
223 		if (name[tmp] == RXSCON)
224 			return (1);
225 		tmp = parent[tmp];
226 	}
227 	return (0);
228 }
229 
230 /* calculate set of positions with v as root which can be active initially */
231 static void
232 first(int v)
233 {
234 	int i;
235 	CHR *p;
236 	i = name[v];
237 	if (!ISOPERATOR(i))
238 		i = 1;
239 	switch (i) {
240 	case 1: case RCCL: case RNCCL:
241 	case RNULLS: case FINAL:
242 	case S1FINAL: case S2FINAL:
243 	/*
244 	 * XCU4: if we are working on an exclusive start state and
245 	 * the parent of this position is not RXSCON or RSTR this
246 	 * is not an active position.
247 	 *
248 	 * (There is a possibility that RSXCON appreas as the
249 	 *  (parent)* node. Check it by check_me().)
250 	 */
251 		if ((exclusive[stnum/2]) &&
252 		    ISOPERATOR(name[parent[v]]) &&
253 		    (name[parent[v]] != RXSCON) &&
254 		    (name[parent[v]] != RSTR) &&
255 		    (check_me(v) == 0)) {
256 				break;
257 		}
258 		if (tmpstat[v] == FALSE) {
259 			count++;
260 			tmpstat[v] = TRUE;
261 		}
262 		break;
263 	case BAR: case RNEWE:
264 		first(left[v]);
265 		first(right[v]);
266 		break;
267 	case CARAT:
268 		if (stnum % 2 == 1)
269 			first(left[v]);
270 		break;
271 	/* XCU4: add RXSCON */
272 	case RXSCON:
273 	case RSCON:
274 		i = stnum/2 +1;
275 		p = (CHR *) right[v];
276 		while (*p)
277 			if (*p++ == i) {
278 				first(left[v]);
279 				break;
280 			}
281 		break;
282 	case STAR: case QUEST:
283 	case PLUS:  case RSTR:
284 	/*
285 	 * XCU4: if we are working on an exclusive start state and
286 	 * the parent of this position is not RXSCON or RSTR this
287 	 * is not an active position.
288 	 *
289 	 * (There is a possibility that RSXCON appreas as the
290 	 *  (parent)* node. Check it by check_me().)
291 	 */
292 		if ((exclusive[stnum/2]) &&
293 		    ISOPERATOR(name[parent[v]]) &&
294 		    (name[parent[v]] != RXSCON) &&
295 		    (name[parent[v]] != RSTR) &&
296 		    (check_me(v) == 0)) {
297 				break;
298 		}
299 		first(left[v]);
300 		break;
301 	case RCAT: case DIV:
302 		first(left[v]);
303 		if (nullstr[left[v]])
304 			first(right[v]);
305 		break;
306 #ifdef DEBUG
307 	default:
308 		warning("bad switch first %d", v);
309 #endif
310 	}
311 }
312 
313 void
314 cgoto(void)
315 {
316 	int i, j;
317 	static int s;
318 	int npos, curpos, n;
319 	int tryit;
320 	CHR tch[MAXNCG];
321 	int tst[MAXNCG];
322 	CHR *q;
323 	/* generate initial state, for each start condition */
324 	if (ratfor) {
325 		(void) fprintf(fout, "blockdata\n");
326 		(void) fprintf(fout, "common /Lvstop/ vstop\n");
327 		(void) fprintf(fout, "define Svstop %d\n", nstates+1);
328 		(void) fprintf(fout, "integer vstop(Svstop)\n");
329 	} else
330 		(void) fprintf(fout, "int yyvstop[] = {\n0,\n");
331 	while (stnum < 2 || stnum/2 < sptr) {
332 		for (i = 0; i < tptr; i++)
333 			tmpstat[i] = 0;
334 		count = 0;
335 		if (tptr > 0)
336 			first(tptr-1);
337 		add(state, stnum);
338 #ifdef DEBUG
339 		if (debug) {
340 			if (stnum > 1)
341 				(void) printf("%ws:\n", sname[stnum/2]);
342 			pstate(stnum);
343 		}
344 #endif
345 		stnum++;
346 	}
347 	stnum--;
348 	/* even stnum = might not be at line begin */
349 	/* odd stnum  = must be at line begin */
350 	/* even states can occur anywhere, odd states only at line begin */
351 	for (s = 0; s <= stnum; s++) {
352 		tryit = FALSE;
353 		cpackflg[s] = FALSE;
354 		sfall[s] = -1;
355 		acompute(s);
356 		for (i = 0; i < ncg; i++)
357 			symbol[i] = 0;
358 		npos = *state[s];
359 		for (i = 1; i <= npos; i++) {
360 			curpos = *(state[s]+i);
361 			if (!ISOPERATOR(name[curpos]))
362 				symbol[name[curpos]] = TRUE;
363 			else {
364 				switch (name[curpos]) {
365 				case RCCL:
366 					tryit = TRUE;
367 					q = (CHR *)left[curpos];
368 					while (*q) {
369 						for (j = 1; j < ncg; j++)
370 						    if (cindex[j] == *q)
371 							symbol[j] = TRUE;
372 						q++;
373 					}
374 					break;
375 				case RSTR:
376 					symbol[right[curpos]] = TRUE;
377 					break;
378 #ifdef DEBUG
379 				case RNULLS:
380 				case FINAL:
381 				case S1FINAL:
382 				case S2FINAL:
383 					break;
384 				default:
385 					warning(
386 					"bad switch cgoto %d state %d",
387 					curpos, s);
388 					break;
389 #endif
390 				}
391 			}
392 		}
393 #ifdef DEBUG
394 		if (debug) {
395 			printf("State %d transitions on char-group {", s);
396 			charc = 0;
397 			for (i = 1; i < ncg; i++) {
398 				if (symbol[i]) {
399 					printf("%d,", i);
400 				}
401 				if (i == ncg-1)
402 					printf("}\n");
403 				if (charc > LINESIZE/4) {
404 					charc = 0;
405 					printf("\n\t");
406 				}
407 			}
408 		}
409 #endif
410 		/* for each char, calculate next state */
411 		n = 0;
412 		for (i = 1; i < ncg; i++) {
413 			if (symbol[i]) {
414 				/* executed for each state, transition pair */
415 				nextstate(s, i);
416 				xstate = notin(stnum);
417 				if (xstate == -2)
418 					warning("bad state  %d %o", s, i);
419 				else if (xstate == -1) {
420 					if (stnum+1 >= nstates) {
421 						stnum++;
422 						error("Too many states %s",
423 						(nstates == NSTATES ?
424 						"\nTry using %n num":""));
425 					}
426 					add(state, ++stnum);
427 #ifdef DEBUG
428 					if (debug)
429 						pstate(stnum);
430 #endif
431 					tch[n] = i;
432 					tst[n++] = stnum;
433 				} else { /* xstate >= 0 ==> state exists */
434 					tch[n] = i;
435 					tst[n++] = xstate;
436 				}
437 			}
438 		}
439 		tch[n] = 0;
440 		tst[n] = -1;
441 		/* pack transitions into permanent array */
442 		if (n > 0)
443 			packtrans(s, tch, tst, n, tryit);
444 		else
445 			gotof[s] = -1;
446 	}
447 	ratfor ? fprintf(fout, "end\n") : fprintf(fout, "0};\n");
448 }
449 
450 /*
451  * Beware -- 70% of total CPU time is spent in this subroutine -
452  * if you don't believe me - try it yourself !
453  */
454 static void
455 nextstate(int s, int c)
456 {
457 	int j, *newpos;
458 	CHR *temp, *tz;
459 	int *pos, i, *f, num, curpos, number;
460 	/* state to goto from state s on char c */
461 	num = *state[s];
462 	temp = tmpstat;
463 	pos = state[s] + 1;
464 	for (i = 0; i < num; i++) {
465 		curpos = *pos++;
466 		j = name[curpos];
467 		if ((!ISOPERATOR(j)) && j == c ||
468 			j == RSTR && c == right[curpos] ||
469 			j == RCCL && member(c, (CHR *) left[curpos])) {
470 			f = foll[curpos];
471 			number = *f;
472 			newpos = f+1;
473 			for (j = 0; j < number; j++)
474 				temp[*newpos++] = 2;
475 		}
476 	}
477 	j = 0;
478 	tz = temp + tptr;
479 	while (temp < tz) {
480 		if (*temp == 2) {
481 			j++;
482 			*temp++ = 1;
483 		}
484 		else
485 			*temp++ = 0;
486 	}
487 	count = j;
488 }
489 
490 static int
491 notin(int n)
492 {	/* see if tmpstat occurs previously */
493 	int *j, k;
494 	CHR *temp;
495 	int i;
496 	if (count == 0)
497 		return (-2);
498 	temp = tmpstat;
499 	for (i = n; i >= 0; i--) { /* for each state */
500 		j = state[i];
501 		if (count == *j++) {
502 			for (k = 0; k < count; k++)
503 				if (!temp[*j++])
504 					break;
505 			if (k >= count)
506 				return (i);
507 		}
508 	}
509 	return (-1);
510 }
511 
512 static void
513 packtrans(int st, CHR *tch, int *tst, int cnt, int tryit)
514 {
515 	/*
516 	 * pack transitions into nchar, nexts
517 	 * nchar is terminated by '\0', nexts uses cnt, followed by elements
518 	 * gotof[st] = index into nchr, nexts for state st
519 	 * sfall[st] =  t implies t is fall back state for st
520 	 * == -1 implies no fall back
521 	 */
522 
523 	int cmin, cval, tcnt, diff, p, *ast;
524 	int i, j, k;
525 	CHR *ach;
526 	int go[MAXNCG], temp[MAXNCG], index, c;
527 	int swork[MAXNCG];
528 	CHR cwork[MAXNCG];
529 	int upper;
530 
531 	rcount += (long)cnt;
532 	cmin = -1;
533 	cval = ncg;
534 	ast = tst;
535 	ach = tch;
536 	/* try to pack transitions using ccl's */
537 	if (!optim)
538 		goto nopack; /* skip all compaction */
539 	if (tryit) { /* ccl's used */
540 		for (i = 1; i < ncg; i++) {
541 			go[i] = temp[i] = -1;
542 			symbol[i] = 1;
543 		}
544 		for (i = 0; i < cnt; i++) {
545 			index = (unsigned char) tch[i];
546 			if ((index >= 0) && (index < NCH)) {
547 				go[index] = tst[i];
548 				symbol[index] = 0;
549 			} else {
550 				fprintf(stderr,
551 "lex`sub2`packtran: tch[%d] out of bounds (%d)\n",
552 				i, tch[i]);
553 			}
554 		}
555 		for (i = 0; i < cnt; i++) {
556 			c = match[tch[i]];
557 			if (go[c] != tst[i] || c == tch[i])
558 				temp[tch[i]] = tst[i];
559 		}
560 		/* fill in error entries */
561 		for (i = 1; i < ncg; i++)
562 			if (symbol[i])
563 				temp[i] = -2;	/* error trans */
564 		/* count them */
565 		k = 0;
566 		for (i = 1; i < ncg; i++)
567 			if (temp[i] != -1)
568 				k++;
569 		if (k < cnt) { /* compress by char */
570 #ifdef DEBUG
571 			if (debug)
572 				(void) printf(
573 				"use compression  %d,  %d vs %d\n", st, k, cnt);
574 #endif
575 			k = 0;
576 			for (i = 1; i < ncg; i++)
577 				if (temp[i] != -1) {
578 					cwork[k] = i;
579 					swork[k++] =
580 					(temp[i] == -2 ? -1 : temp[i]);
581 				}
582 			cwork[k] = 0;
583 #ifdef PC
584 			ach = cwork;
585 			ast = swork;
586 			cnt = k;
587 			cpackflg[st] = TRUE;
588 #endif
589 		}
590 	}
591 	/*
592 	 * get most similar state
593 	 * reject state with more transitions,
594 	 * state already represented by a third state,
595 	 * and state which is compressed by char if ours is not to be
596 	 */
597 	for (i = 0; i < st; i++) {
598 		if (sfall[i] != -1)
599 			continue;
600 		if (cpackflg[st] == 1)
601 			if (!(cpackflg[i] == 1))
602 				continue;
603 		p = gotof[i];
604 		if (p == -1) /* no transitions */
605 			continue;
606 		tcnt = nexts[p];
607 		if (tcnt > cnt)
608 			continue;
609 		diff = 0;
610 		k = 0;
611 		j = 0;
612 		upper = p + tcnt;
613 		while (ach[j] && p < upper) {
614 			while (ach[j] < nchar[p] && ach[j]) {
615 				diff++;
616 				j++;
617 			}
618 			if (ach[j] == 0)
619 				break;
620 			if (ach[j] > nchar[p]) {
621 				diff = ncg;
622 				break;
623 			}
624 			/* ach[j] == nchar[p] */
625 			if (ast[j] != nexts[++p] ||
626 				ast[j] == -1 ||
627 				(cpackflg[st] && ach[j] != match[ach[j]]))
628 				diff++;
629 			j++;
630 		}
631 		while (ach[j]) {
632 			diff++;
633 			j++;
634 		}
635 		if (p < upper)
636 			diff = ncg;
637 		if (diff < cval && diff < tcnt) {
638 			cval = diff;
639 			cmin = i;
640 			if (cval == 0)
641 				break;
642 		}
643 	}
644 	/* cmin = state "most like" state st */
645 #ifdef DEBUG
646 	if (debug)
647 		(void) printf("select st %d for st %d diff %d\n",
648 			cmin, st, cval);
649 #endif
650 #ifdef PS
651 	if (cmin != -1) { /* if we can use st cmin */
652 		gotof[st] = nptr;
653 		k = 0;
654 		sfall[st] = cmin;
655 		p = gotof[cmin] + 1;
656 		j = 0;
657 		while (ach[j]) {
658 			/* if cmin has a transition on c, then so will st */
659 			/* st may be "larger" than cmin, however */
660 			while (ach[j] < nchar[p-1] && ach[j]) {
661 				k++;
662 				nchar[nptr] = ach[j];
663 				nexts[++nptr] = ast[j];
664 				j++;
665 			}
666 			if (nchar[p-1] == 0)
667 				break;
668 			if (ach[j] > nchar[p-1]) {
669 				warning("bad transition %d %d", st, cmin);
670 				goto nopack;
671 			}
672 			/* ach[j] == nchar[p-1] */
673 			if (ast[j] != nexts[p] ||
674 				ast[j] == -1 ||
675 				(cpackflg[st] && ach[j] != match[ach[j]])) {
676 				k++;
677 				nchar[nptr] = ach[j];
678 				nexts[++nptr] = ast[j];
679 			}
680 			p++;
681 			j++;
682 		}
683 		while (ach[j]) {
684 			nchar[nptr] = ach[j];
685 			nexts[++nptr] = ast[j++];
686 			k++;
687 		}
688 		nexts[gotof[st]] = cnt = k;
689 		nchar[nptr++] = 0;
690 	} else {
691 #endif
692 nopack:
693 	/* stick it in */
694 		gotof[st] = nptr;
695 		nexts[nptr] = cnt;
696 		for (i = 0; i < cnt; i++) {
697 			nchar[nptr] = ach[i];
698 			nexts[++nptr] = ast[i];
699 		}
700 		nchar[nptr++] = 0;
701 #ifdef PS
702 	}
703 #endif
704 	if (cnt < 1) {
705 		gotof[st] = -1;
706 		nptr--;
707 	} else
708 		if (nptr > ntrans)
709 			error(
710 			"Too many transitions %s",
711 			(ntrans == NTRANS ? "\nTry using %a num" : ""));
712 }
713 
714 #ifdef DEBUG
715 void
716 pstate(int s)
717 {
718 	int *p, i, j;
719 	(void) printf("State %d:\n", s);
720 	p = state[s];
721 	i = *p++;
722 	if (i == 0)
723 		return;
724 	(void) printf("%4d", *p++);
725 	for (j = 1; j < i; j++) {
726 		(void) printf(", %4d", *p++);
727 		if (j%30 == 0)
728 			(void) putchar('\n');
729 	}
730 	(void) putchar('\n');
731 }
732 #endif
733 
734 static int
735 member(int d, CHR *t)
736 {
737 	int c;
738 	CHR *s;
739 	c = d;
740 	s = t;
741 	c = cindex[c];
742 	while (*s)
743 		if (*s++ == c)
744 			return (1);
745 	return (0);
746 }
747 
748 #ifdef DEBUG
749 void
750 stprt(int i)
751 {
752 	int p, t;
753 	(void) printf("State %d:", i);
754 	/* print actions, if any */
755 	t = atable[i];
756 	if (t != -1)
757 		(void) printf(" final");
758 	(void) putchar('\n');
759 	if (cpackflg[i] == TRUE)
760 		(void) printf("backup char in use\n");
761 	if (sfall[i] != -1)
762 		(void) printf("fall back state %d\n", sfall[i]);
763 	p = gotof[i];
764 	if (p == -1)
765 		return;
766 	(void) printf("(%d transitions)\n", nexts[p]);
767 	while (nchar[p]) {
768 		charc = 0;
769 		if (nexts[p+1] >= 0)
770 			(void) printf("%d\t", nexts[p+1]);
771 		else
772 			(void) printf("err\t");
773 		allprint(nchar[p++]);
774 		while (nexts[p] == nexts[p+1] && nchar[p]) {
775 			if (charc > LINESIZE) {
776 				charc = 0;
777 				(void) printf("\n\t");
778 			}
779 			allprint(nchar[p++]);
780 		}
781 		(void) putchar('\n');
782 	}
783 	(void) putchar('\n');
784 }
785 #endif
786 
787 /* compute action list = set of poss. actions */
788 static void
789 acompute(int s)
790 {
791 	int *p, i, j;
792 	int q, r;
793 	int cnt, m;
794 	int temp[MAXPOSSTATE], k, neg[MAXPOSSTATE], n;
795 	k = 0;
796 	n = 0;
797 	p = state[s];
798 	cnt = *p++;
799 	if (cnt > MAXPOSSTATE)
800 		error("Too many positions for one state - acompute");
801 	for (i = 0; i < cnt; i++) {
802 		q = *p;
803 		if (name[q] == FINAL)
804 			temp[k++] = left[q];
805 		else if (name[q] == S1FINAL) {
806 			temp[k++] = left[q];
807 			if ((r = left[q]) >= NACTIONS)
808 				error(
809 				"INTERNAL ERROR:left[%d]==%d>=NACTIONS", q, r);
810 			extra[r] = 1;
811 		} else if (name[q] == S2FINAL)
812 			neg[n++] = left[q];
813 		p++;
814 	}
815 	atable[s] = -1;
816 	if (k < 1 && n < 1)
817 		return;
818 #ifdef DEBUG
819 	if (debug)
820 		(void) printf("final %d actions:", s);
821 #endif
822 	/* sort action list */
823 	for (i = 0; i < k; i++)
824 		for (j = i+1; j < k; j++)
825 			if (temp[j] < temp[i]) {
826 				m = temp[j];
827 				temp[j] = temp[i];
828 				temp[i] = m;
829 			}
830 	/* remove dups */
831 	for (i = 0; i < k-1; i++)
832 		if (temp[i] == temp[i+1])
833 			temp[i] = 0;
834 	/* copy to permanent quarters */
835 	atable[s] = aptr;
836 #ifdef DEBUG
837 	if (!ratfor)
838 		(void) fprintf(fout, "/* actions for state %d */", s);
839 #endif
840 	(void) putc('\n', fout);
841 	for (i = 0; i < k; i++)
842 		if (temp[i] != 0) {
843 			ratfor ?
844 			fprintf(fout, "data vstop(%d)/%d/\n", aptr, temp[i]) :
845 			fprintf(fout, "%d,\n", temp[i]);
846 #ifdef DEBUG
847 			if (debug)
848 				(void) printf("%d ", temp[i]);
849 #endif
850 			aptr++;
851 		}
852 	for (i = 0; i < n; i++) { /* copy fall back actions - all neg */
853 		ratfor ?
854 		fprintf(fout, "data vstop(%d)/%d/\n", aptr, neg[i]) :
855 		fprintf(fout, "%d,\n", neg[i]);
856 		aptr++;
857 #ifdef DEBUG
858 		if (debug)
859 			(void) printf("%d ", neg[i]);
860 #endif
861 		}
862 #ifdef DEBUG
863 	if (debug)
864 		(void) putchar('\n');
865 #endif
866 	ratfor ? fprintf(fout, "data vstop (%d)/0/\n", aptr) :
867 		fprintf(fout, "0, \n");
868 	aptr++;
869 }
870 
871 #ifdef DEBUG
872 void
873 pccl(void)
874 {
875 	/* print character class sets */
876 	int i, j;
877 	(void) printf("char class intersection\n");
878 	for (i = 0; i < ccount; i++) {
879 		charc = 0;
880 		(void) printf("class %d:\n\t", i);
881 		for (j = 1; j < ncg; j++)
882 			if (cindex[j] == i) {
883 				allprint(j);
884 				if (charc > LINESIZE) {
885 					(void) printf("\n\t");
886 					charc = 0;
887 				}
888 			}
889 		(void) putchar('\n');
890 	}
891 	charc = 0;
892 	(void) printf("match:\n");
893 	for (i = 0; i < ncg; i++) {
894 		allprint(match[i]);
895 		if (charc > LINESIZE) {
896 			(void) putchar('\n');
897 			charc = 0;
898 		}
899 	}
900 	(void) putchar('\n');
901 }
902 #endif
903 
904 void
905 mkmatch(void)
906 {
907 	int i;
908 	CHR tab[MAXNCG];
909 	for (i = 0; i < ccount; i++)
910 		tab[i] = 0;
911 	for (i = 1; i < ncg; i++)
912 		if (tab[cindex[i]] == 0)
913 			tab[cindex[i]] = i;
914 	/* tab[i] = principal char for new ccl i */
915 	for (i = 1; i < ncg; i++)
916 		match[i] = tab[cindex[i]];
917 }
918 
919 void
920 layout(void)
921 {
922 	/* format and output final program's tables */
923 	int i, j, k;
924 	int  top, bot, startup, omin;
925 	startup = 0;
926 	for (i = 0; i < outsize; i++)
927 		verify[i] = advance[i] = 0;
928 	omin = 0;
929 	yytop = 0;
930 	for (i = 0; i <= stnum; i++) { /* for each state */
931 		j = gotof[i];
932 		if (j == -1) {
933 			stoff[i] = 0;
934 			continue;
935 		}
936 		bot = j;
937 		while (nchar[j])
938 			j++;
939 		top = j - 1;
940 #if DEBUG
941 		if (debug) {
942 			(void) printf("State %d: (layout)\n", i);
943 			for (j = bot; j <= top; j++) {
944 				(void) printf("  %o", nchar[j]);
945 				if (j % 10 == 0)
946 					(void) putchar('\n');
947 			}
948 			(void) putchar('\n');
949 		}
950 #endif
951 		while (verify[omin+ZCH])
952 			omin++;
953 		startup = omin;
954 #if DEBUG
955 		if (debug)
956 			(void) printf(
957 			"bot,top %d, %d startup begins %d\n",
958 			bot, top, startup);
959 #endif
960 		if (chset) {
961 			do {
962 				startup += 1;
963 				if (startup > outsize - ZCH)
964 					error("output table overflow");
965 				for (j = bot; j <= top; j++) {
966 					k = startup+ctable[nchar[j]];
967 					if (verify[k])
968 						break;
969 				}
970 			} while (j <= top);
971 #if DEBUG
972 			if (debug)
973 				(void) printf(" startup will be %d\n",
974 				startup);
975 #endif
976 			/* have found place */
977 			for (j = bot; j <= top; j++) {
978 				k = startup + ctable[nchar[j]];
979 				if (ctable[nchar[j]] <= 0)
980 					(void) printf(
981 					"j %d nchar %d ctable.nch %d\n",
982 					j, nchar[j], ctable[nchar[k]]);
983 				verify[k] = i + 1;	/* state number + 1 */
984 				advance[k] = nexts[j+1]+1;
985 				if (yytop < k)
986 					yytop = k;
987 			}
988 		} else {
989 			do {
990 				startup += 1;
991 				if (startup > outsize - ZCH)
992 					error("output table overflow");
993 				for (j = bot; j <= top; j++) {
994 					k = startup + nchar[j];
995 					if (verify[k])
996 						break;
997 				}
998 			} while (j <= top);
999 			/* have found place */
1000 #if DEBUG
1001 	if (debug)
1002 		(void) printf(" startup going to be %d\n", startup);
1003 #endif
1004 			for (j = bot; j <= top; j++) {
1005 				k = startup + nchar[j];
1006 				verify[k] = i+1; /* state number + 1 */
1007 				advance[k] = nexts[j+1] + 1;
1008 				if (yytop < k)
1009 					yytop = k;
1010 			}
1011 		}
1012 		stoff[i] = startup;
1013 	}
1014 
1015 	/* stoff[i] = offset into verify, advance for trans for state i */
1016 	/* put out yywork */
1017 	if (ratfor) {
1018 		(void) fprintf(fout, "define YYTOPVAL %d\n", yytop);
1019 		rprint(verify, "verif", yytop+1);
1020 		rprint(advance, "advan", yytop+1);
1021 		shiftr(stoff, stnum);
1022 		rprint(stoff, "stoff", stnum+1);
1023 		shiftr(sfall, stnum);
1024 		upone(sfall, stnum+1);
1025 		rprint(sfall, "fall", stnum+1);
1026 		bprint(extra, "extra", casecount+1);
1027 		bprint((char *)match, "match", ncg);
1028 		shiftr(atable, stnum);
1029 		rprint(atable, "atable", stnum+1);
1030 	}
1031 	(void) fprintf(fout,
1032 	"# define YYTYPE %s\n", stnum+1 >= NCH ? "int" : "unsigned char");
1033 	(void) fprintf(fout,
1034 	"struct yywork { YYTYPE verify, advance; } yycrank[] = {\n");
1035 	for (i = 0; i <= yytop; i += 4) {
1036 		for (j = 0; j < 4; j++) {
1037 			k = i+j;
1038 			if (verify[k])
1039 				(void) fprintf(fout,
1040 				"%d,%d,\t", verify[k], advance[k]);
1041 			else
1042 				(void) fprintf(fout, "0,0,\t");
1043 		}
1044 		(void) putc('\n', fout);
1045 	}
1046 	(void) fprintf(fout, "0,0};\n");
1047 
1048 	/* put out yysvec */
1049 
1050 	(void) fprintf(fout, "struct yysvf yysvec[] = {\n");
1051 	(void) fprintf(fout, "0,\t0,\t0,\n");
1052 	for (i = 0; i <= stnum; i++) {	/* for each state */
1053 		if (cpackflg[i])
1054 			stoff[i] = -stoff[i];
1055 		(void) fprintf(fout, "yycrank+%d,\t", stoff[i]);
1056 		if (sfall[i] != -1)
1057 			(void) fprintf(fout,
1058 			"yysvec+%d,\t", sfall[i]+1); /* state + 1 */
1059 		else
1060 			(void) fprintf(fout, "0,\t\t");
1061 		if (atable[i] != -1)
1062 			(void) fprintf(fout, "yyvstop+%d,", atable[i]);
1063 		else
1064 			(void) fprintf(fout, "0,\t");
1065 #ifdef DEBUG
1066 		(void) fprintf(fout, "\t\t/* state %d */", i);
1067 #endif
1068 		(void) putc('\n', fout);
1069 	}
1070 	(void) fprintf(fout, "0,\t0,\t0};\n");
1071 
1072 	/* put out yymatch */
1073 
1074 	(void) fprintf(fout, "struct yywork *yytop = yycrank+%d;\n", yytop);
1075 	(void) fprintf(fout, "struct yysvf *yybgin = yysvec+1;\n");
1076 	if (optim) {
1077 		if (handleeuc) {
1078 			(void) fprintf(fout, "int yymatch[] = {\n");
1079 		} else {
1080 			(void) fprintf(fout, "char yymatch[] = {\n");
1081 		}
1082 		if (chset == 0) { /* no chset, put out in normal order */
1083 			for (i = 0; i < ncg; i += 8) {
1084 				for (j = 0; j < 8; j++) {
1085 					int fbch;
1086 					fbch = match[i+j];
1087 					fprintf(fout, "%3d, ", fbch);
1088 				}
1089 				(void) putc('\n', fout);
1090 			}
1091 		} else {
1092 			int *fbarr;
1093 			fbarr = (int *)myalloc(2*MAXNCG, sizeof (*fbarr));
1094 			if (fbarr == 0)
1095 				error("No space for char table reverse", 0);
1096 			for (i = 0; i < MAXNCG; i++)
1097 				fbarr[i] = 0;
1098 			for (i = 0; i < ncg; i++)
1099 				fbarr[ctable[i]] = ctable[match[i]];
1100 			for (i = 0; i < ncg; i += 8) {
1101 				for (j = 0; j < 8; j++)
1102 					fprintf(fout, "0%-3o,", fbarr[i+j]);
1103 				putc('\n', fout);
1104 			}
1105 			free(fbarr);
1106 		}
1107 		(void) fprintf(fout, "0};\n");
1108 	}
1109 	/* put out yyextra */
1110 	(void) fprintf(fout, "char yyextra[] = {\n");
1111 	for (i = 0; i < casecount; i += 8) {
1112 		for (j = 0; j < 8; j++)
1113 			(void) fprintf(fout, "%d,", i+j < NACTIONS ?
1114 				extra[i+j] : 0);
1115 		(void) putc('\n', fout);
1116 	}
1117 	(void) fprintf(fout, "0};\n");
1118 	if (handleeuc) {
1119 		/* Put out yycgidtbl */
1120 		fprintf(fout, "#define YYNCGIDTBL %d\n", ncgidtbl);
1121 		fprintf(fout, "\tunsigned long yycgidtbl[]={");
1122 		/*
1123 		 * Use "unsigned long" instead of "lchar" to minimize
1124 		 * the name-space polution for the application program.
1125 		 */
1126 		for (i = 0; i < ncgidtbl; ++i) {
1127 			if (i%8 == 0)
1128 				fprintf(fout, "\n\t\t");
1129 			fprintf(fout, "0x%08x, ",  yycgidtbl[i]);
1130 		}
1131 		fprintf(fout, "\n\t0};\n");
1132 	}
1133 }
1134 
1135 static void
1136 rprint(int *a, char *s, int n)
1137 {
1138 	int i;
1139 	(void) fprintf(fout, "block data\n");
1140 	(void) fprintf(fout, "common /L%s/ %s\n", s, s);
1141 	(void) fprintf(fout, "define S%s %d\n", s, n);
1142 	(void) fprintf(fout, "integer %s (S%s)\n", s, s);
1143 	for (i = 1; i <= n; i++) {
1144 		if (i%8 == 1)
1145 			(void) fprintf(fout, "data ");
1146 		(void) fprintf(fout, "%s (%d)/%d/", s, i, a[i]);
1147 		(void) fprintf(fout, (i%8 && i < n) ? ", " : "\n");
1148 	}
1149 	(void) fprintf(fout, "end\n");
1150 }
1151 
1152 static void
1153 shiftr(int *a, int n)
1154 {
1155 	int i;
1156 	for (i = n; i >= 0; i--)
1157 		a[i+1] = a[i];
1158 }
1159 
1160 static void
1161 upone(int *a, int n)
1162 {
1163 	int i;
1164 	for (i = 0; i <= n; i++)
1165 		a[i]++;
1166 }
1167 
1168 static void
1169 bprint(char *a, char *s, int n)
1170 {
1171 	int i, j, k;
1172 	(void) fprintf(fout, "block data\n");
1173 	(void) fprintf(fout, "common /L%s/ %s\n", s, s);
1174 	(void) fprintf(fout, "define S%s %d\n", s, n);
1175 	(void) fprintf(fout, "integer %s (S%s)\n", s, s);
1176 	for (i = 1; i < n; i += 8) {
1177 		(void) fprintf(fout, "data %s (%d)/%d/", s, i, a[i]);
1178 		for (j = 1; j < 8; j++) {
1179 			k = i+j;
1180 			if (k < n)
1181 				(void) fprintf(fout,
1182 					", %s (%d)/%d/", s, k, a[k]);
1183 		}
1184 		(void) putc('\n', fout);
1185 	}
1186 	(void) fprintf(fout, "end\n");
1187 }
1188 
1189 #ifdef PP
1190 static void
1191 padd(int **array, int n)
1192 {
1193 	int i, *j, k;
1194 	array[n] = nxtpos;
1195 	if (count == 0) {
1196 		*nxtpos++ = 0;
1197 		return;
1198 	}
1199 	for (i = tptr-1; i >= 0; i--) {
1200 		j = array[i];
1201 		if (j && *j++ == count) {
1202 			for (k = 0; k < count; k++)
1203 				if (!tmpstat[*j++])
1204 					break;
1205 			if (k >= count) {
1206 				array[n] = array[i];
1207 				return;
1208 			}
1209 		}
1210 	}
1211 	add(array, n);
1212 }
1213 #endif
1214