xref: /illumos-gate/usr/src/cmd/sgs/lex/common/sub2.c (revision 1dd08564)
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 (the "License").
6  * You may not use this file except in compliance with the License.
7  *
8  * You can obtain a copy of the license at usr/src/OPENSOLARIS.LICENSE
9  * or http://www.opensolaris.org/os/licensing.
10  * See the License for the specific language governing permissions
11  * and limitations under the License.
12  *
13  * When distributing Covered Code, include this CDDL HEADER in each
14  * file and include the License file at usr/src/OPENSOLARIS.LICENSE.
15  * If applicable, add the following below this CDDL HEADER, with the
16  * fields enclosed by brackets "[]" replaced with your own identifying
17  * information: Portions Copyright [yyyy] [name of copyright owner]
18  *
19  * CDDL HEADER END
20  */
21 /*
22  * Copyright 2008 Sun Microsystems, Inc.  All rights reserved.
23  * Use is subject to license terms.
24  */
25 
26 /*	Copyright (c) 1988 AT&T	*/
27 /*	All Rights Reserved	*/
28 
29 #pragma ident	"%Z%%M%	%I%	%E% SMI"
30 
31 #include "ldefs.h"
32 
33 static void add(int **array, int n);
34 static void follow(int v);
35 static void first(int v);
36 static void nextstate(int s, int c);
37 static void packtrans(int st, CHR *tch, int *tst, int cnt, int tryit);
38 static void acompute(int s);
39 static void rprint(int *a, char *s, int n);
40 static void shiftr(int *a, int n);
41 static void upone(int *a, int n);
42 static void bprint(char *a, char *s, int n);
43 static int notin(int n);
44 static int member(int d, CHR *t);
45 
46 #ifdef PP
47 static void padd(int **array, int n);
48 #endif
49 
50 void
cfoll(int v)51 cfoll(int v)
52 {
53 	int i, j, k;
54 	CHR *p;
55 	i = name[v];
56 	if (!ISOPERATOR(i))
57 		i = 1;
58 	switch (i) {
59 		case 1: case RSTR: case RCCL: case RNCCL: case RNULLS:
60 			for (j = 0; j < tptr; j++)
61 				tmpstat[j] = FALSE;
62 			count = 0;
63 			follow(v);
64 #ifdef PP
65 			padd(foll, v); /* packing version */
66 #else
67 			add(foll, v); /* no packing version */
68 #endif
69 			if (i == RSTR)
70 				cfoll(left[v]);
71 			else if (i == RCCL || i == RNCCL) {
72 				for (j = 1; j < ncg; j++)
73 					symbol[j] = (i == RNCCL);
74 				p = (CHR *) left[v];
75 				while (*p)
76 					symbol[*p++] = (i == RCCL);
77 				p = pcptr;
78 				for (j = 1; j < ncg; j++)
79 					if (symbol[j]) {
80 						for (k = 0; p + k < pcptr; k++)
81 							if (cindex[j] ==
82 							    *(p + k))
83 								break;
84 						if (p + k >= pcptr)
85 							*pcptr++ = cindex[j];
86 					}
87 				*pcptr++ = 0;
88 				if (pcptr > pchar + pchlen)
89 					error(
90 					"Too many packed character classes");
91 				left[v] = (int)p;
92 				name[v] = RCCL;	/* RNCCL eliminated */
93 #ifdef DEBUG
94 				if (debug && *p) {
95 					(void) printf("ccl %d: %d", v, *p++);
96 					while (*p)
97 						(void) printf(", %d", *p++);
98 					(void) putchar('\n');
99 				}
100 #endif
101 			}
102 			break;
103 		case CARAT:
104 			cfoll(left[v]);
105 			break;
106 
107 		/* XCU4: add RXSCON */
108 		case RXSCON:
109 
110 		case STAR: case PLUS: case QUEST: case RSCON:
111 			cfoll(left[v]);
112 			break;
113 		case BAR: case RCAT: case DIV: case RNEWE:
114 			cfoll(left[v]);
115 			cfoll(right[v]);
116 			break;
117 #ifdef DEBUG
118 		case FINAL:
119 		case S1FINAL:
120 		case S2FINAL:
121 			break;
122 		default:
123 			warning("bad switch cfoll %d", v);
124 #endif
125 	}
126 }
127 
128 #ifdef DEBUG
129 void
pfoll(void)130 pfoll(void)
131 {
132 	int i, k, *p;
133 	int j;
134 	/* print sets of chars which may follow positions */
135 	(void) printf("pos\tchars\n");
136 	for (i = 0; i < tptr; i++)
137 		if (p = foll[i]) {
138 			j = *p++;
139 			if (j >= 1) {
140 				(void) printf("%d:\t%d", i, *p++);
141 				for (k = 2; k <= j; k++)
142 					(void) printf(", %d", *p++);
143 				(void) putchar('\n');
144 			}
145 		}
146 }
147 #endif
148 
149 static void
add(int ** array,int n)150 add(int **array, int n)
151 {
152 	int i, *temp;
153 	CHR *ctemp;
154 	temp = nxtpos;
155 	ctemp = tmpstat;
156 	array[n] = nxtpos;	/* note no packing is done in positions */
157 	*temp++ = count;
158 	for (i = 0; i < tptr; i++)
159 		if (ctemp[i] == TRUE)
160 			*temp++ = i;
161 	nxtpos = temp;
162 	if (nxtpos >= positions+maxpos)
163 		error(
164 		"Too many positions %s",
165 		    (maxpos == MAXPOS ? "\nTry using %p num" : ""));
166 }
167 
168 static void
follow(int v)169 follow(int v)
170 {
171 	int p;
172 	if (v >= tptr-1)
173 		return;
174 	p = parent[v];
175 	if (p == 0)
176 		return;
177 	switch (name[p]) {
178 	/* will not be CHAR RNULLS FINAL S1FINAL S2FINAL RCCL RNCCL */
179 	case RSTR:
180 		if (tmpstat[p] == FALSE) {
181 			count++;
182 			tmpstat[p] = TRUE;
183 		}
184 		break;
185 	case STAR: case PLUS:
186 		first(v);
187 		follow(p);
188 		break;
189 	case BAR: case QUEST: case RNEWE:
190 		follow(p);
191 		break;
192 	case RCAT: case DIV:
193 		if (v == left[p]) {
194 			if (nullstr[right[p]])
195 				follow(p);
196 			first(right[p]);
197 		}
198 		else
199 			follow(p);
200 		break;
201 	/* XCU4: add RXSCON */
202 	case RXSCON:
203 	case RSCON: case CARAT:
204 		follow(p);
205 		break;
206 #ifdef DEBUG
207 	default:
208 		warning("bad switch follow %d", p);
209 #endif
210 	}
211 }
212 
213 /*
214  * Check if I have a RXSCON in my upper node
215  */
216 static int
check_me(int v)217 check_me(int v)
218 {
219 	int tmp = parent[v];
220 
221 	while (name[tmp] != RNEWE) {
222 		if (name[tmp] == RXSCON)
223 			return (1);
224 		tmp = parent[tmp];
225 	}
226 	return (0);
227 }
228 
229 /* calculate set of positions with v as root which can be active initially */
230 static void
first(int v)231 first(int v)
232 {
233 	int i;
234 	CHR *p;
235 	i = name[v];
236 	if (!ISOPERATOR(i))
237 		i = 1;
238 	switch (i) {
239 	case 1: case RCCL: case RNCCL:
240 	case RNULLS: case FINAL:
241 	case S1FINAL: case S2FINAL:
242 	/*
243 	 * XCU4: if we are working on an exclusive start state and
244 	 * the parent of this position is not RXSCON or RSTR this
245 	 * is not an active position.
246 	 *
247 	 * (There is a possibility that RSXCON appreas as the
248 	 *  (parent)* node. Check it by check_me().)
249 	 */
250 		if ((exclusive[stnum/2]) &&
251 		    ISOPERATOR(name[parent[v]]) &&
252 		    (name[parent[v]] != RXSCON) &&
253 		    (name[parent[v]] != RSTR) &&
254 		    (check_me(v) == 0)) {
255 				break;
256 		}
257 		if (tmpstat[v] == FALSE) {
258 			count++;
259 			tmpstat[v] = TRUE;
260 		}
261 		break;
262 	case BAR: case RNEWE:
263 		first(left[v]);
264 		first(right[v]);
265 		break;
266 	case CARAT:
267 		if (stnum % 2 == 1)
268 			first(left[v]);
269 		break;
270 	/* XCU4: add RXSCON */
271 	case RXSCON:
272 	case RSCON:
273 		i = stnum/2 +1;
274 		p = (CHR *) right[v];
275 		while (*p)
276 			if (*p++ == i) {
277 				first(left[v]);
278 				break;
279 			}
280 		break;
281 	case STAR: case QUEST:
282 	case PLUS:  case RSTR:
283 	/*
284 	 * XCU4: if we are working on an exclusive start state and
285 	 * the parent of this position is not RXSCON or RSTR this
286 	 * is not an active position.
287 	 *
288 	 * (There is a possibility that RSXCON appreas as the
289 	 *  (parent)* node. Check it by check_me().)
290 	 */
291 		if ((exclusive[stnum/2]) &&
292 		    ISOPERATOR(name[parent[v]]) &&
293 		    (name[parent[v]] != RXSCON) &&
294 		    (name[parent[v]] != RSTR) &&
295 		    (check_me(v) == 0)) {
296 				break;
297 		}
298 		first(left[v]);
299 		break;
300 	case RCAT: case DIV:
301 		first(left[v]);
302 		if (nullstr[left[v]])
303 			first(right[v]);
304 		break;
305 #ifdef DEBUG
306 	default:
307 		warning("bad switch first %d", v);
308 #endif
309 	}
310 }
311 
312 void
cgoto(void)313 cgoto(void)
314 {
315 	int i, j;
316 	static int s;
317 	int npos, curpos, n;
318 	int tryit;
319 	CHR tch[MAXNCG];
320 	int tst[MAXNCG];
321 	CHR *q;
322 	/* generate initial state, for each start condition */
323 	if (ratfor) {
324 		(void) fprintf(fout, "blockdata\n");
325 		(void) fprintf(fout, "common /Lvstop/ vstop\n");
326 		(void) fprintf(fout, "define Svstop %d\n", nstates+1);
327 		(void) fprintf(fout, "integer vstop(Svstop)\n");
328 	} else
329 		(void) fprintf(fout, "int yyvstop[] = {\n0,\n");
330 	while (stnum < 2 || stnum/2 < sptr) {
331 		for (i = 0; i < tptr; i++)
332 			tmpstat[i] = 0;
333 		count = 0;
334 		if (tptr > 0)
335 			first(tptr-1);
336 		add(state, stnum);
337 #ifdef DEBUG
338 		if (debug) {
339 			if (stnum > 1)
340 				(void) printf("%ws:\n", sname[stnum/2]);
341 			pstate(stnum);
342 		}
343 #endif
344 		stnum++;
345 	}
346 	stnum--;
347 	/* even stnum = might not be at line begin */
348 	/* odd stnum  = must be at line begin */
349 	/* even states can occur anywhere, odd states only at line begin */
350 	for (s = 0; s <= stnum; s++) {
351 		tryit = FALSE;
352 		cpackflg[s] = FALSE;
353 		sfall[s] = -1;
354 		acompute(s);
355 		for (i = 0; i < ncg; i++)
356 			symbol[i] = 0;
357 		npos = *state[s];
358 		for (i = 1; i <= npos; i++) {
359 			curpos = *(state[s]+i);
360 			if (!ISOPERATOR(name[curpos]))
361 				symbol[name[curpos]] = TRUE;
362 			else {
363 				switch (name[curpos]) {
364 				case RCCL:
365 					tryit = TRUE;
366 					q = (CHR *)left[curpos];
367 					while (*q) {
368 						for (j = 1; j < ncg; j++)
369 							if (cindex[j] == *q)
370 								symbol[j] =
371 								    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 	(void) (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
nextstate(int s,int c)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
notin(int n)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
packtrans(int st,CHR * tch,int * tst,int cnt,int tryit)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 				(void) fprintf(stderr,
551 "lex`sub2`packtran: tch[%d] out of bounds (%d)\n",
552 				    i, (int)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
pstate(int s)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
member(int d,CHR * t)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
stprt(int i)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
acompute(int s)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 			(void) (ratfor ?
844 			    fprintf(fout, "data vstop(%d)/%d/\n",
845 			    aptr, temp[i]) :
846 			    fprintf(fout, "%d,\n", temp[i]));
847 #ifdef DEBUG
848 			if (debug)
849 				(void) printf("%d ", temp[i]);
850 #endif
851 			aptr++;
852 		}
853 	for (i = 0; i < n; i++) { /* copy fall back actions - all neg */
854 		ratfor ?
855 		    (void) fprintf(fout, "data vstop(%d)/%d/\n", aptr, neg[i]) :
856 		    (void) fprintf(fout, "%d,\n", neg[i]);
857 		aptr++;
858 #ifdef DEBUG
859 		if (debug)
860 			(void) printf("%d ", neg[i]);
861 #endif
862 		}
863 #ifdef DEBUG
864 	if (debug)
865 		(void) putchar('\n');
866 #endif
867 	(void) (ratfor ? fprintf(fout, "data vstop (%d)/0/\n", aptr) :
868 	    fprintf(fout, "0, \n"));
869 	aptr++;
870 }
871 
872 #ifdef DEBUG
873 void
pccl(void)874 pccl(void)
875 {
876 	/* print character class sets */
877 	int i, j;
878 	(void) printf("char class intersection\n");
879 	for (i = 0; i < ccount; i++) {
880 		charc = 0;
881 		(void) printf("class %d:\n\t", i);
882 		for (j = 1; j < ncg; j++)
883 			if (cindex[j] == i) {
884 				allprint(j);
885 				if (charc > LINESIZE) {
886 					(void) printf("\n\t");
887 					charc = 0;
888 				}
889 			}
890 		(void) putchar('\n');
891 	}
892 	charc = 0;
893 	(void) printf("match:\n");
894 	for (i = 0; i < ncg; i++) {
895 		allprint(match[i]);
896 		if (charc > LINESIZE) {
897 			(void) putchar('\n');
898 			charc = 0;
899 		}
900 	}
901 	(void) putchar('\n');
902 }
903 #endif
904 
905 void
mkmatch(void)906 mkmatch(void)
907 {
908 	int i;
909 	CHR tab[MAXNCG];
910 	for (i = 0; i < ccount; i++)
911 		tab[i] = 0;
912 	for (i = 1; i < ncg; i++)
913 		if (tab[cindex[i]] == 0)
914 			tab[cindex[i]] = i;
915 	/* tab[i] = principal char for new ccl i */
916 	for (i = 1; i < ncg; i++)
917 		match[i] = tab[cindex[i]];
918 }
919 
920 void
layout(void)921 layout(void)
922 {
923 	/* format and output final program's tables */
924 	int i, j, k;
925 	int  top, bot, startup, omin;
926 	startup = 0;
927 	for (i = 0; i < outsize; i++)
928 		verify[i] = advance[i] = 0;
929 	omin = 0;
930 	yytop = 0;
931 	for (i = 0; i <= stnum; i++) { /* for each state */
932 		j = gotof[i];
933 		if (j == -1) {
934 			stoff[i] = 0;
935 			continue;
936 		}
937 		bot = j;
938 		while (nchar[j])
939 			j++;
940 		top = j - 1;
941 #if DEBUG
942 		if (debug) {
943 			(void) printf("State %d: (layout)\n", i);
944 			for (j = bot; j <= top; j++) {
945 				(void) printf("  %o", nchar[j]);
946 				if (j % 10 == 0)
947 					(void) putchar('\n');
948 			}
949 			(void) putchar('\n');
950 		}
951 #endif
952 		while (verify[omin+ZCH])
953 			omin++;
954 		startup = omin;
955 #if DEBUG
956 		if (debug)
957 			(void) printf(
958 			"bot,top %d, %d startup begins %d\n",
959 			    bot, top, startup);
960 #endif
961 		if (chset) {
962 			do {
963 				startup += 1;
964 				if (startup > outsize - ZCH)
965 					error("output table overflow");
966 				for (j = bot; j <= top; j++) {
967 					k = startup+ctable[nchar[j]];
968 					if (verify[k])
969 						break;
970 				}
971 			} while (j <= top);
972 #if DEBUG
973 			if (debug)
974 				(void) printf(" startup will be %d\n",
975 				    startup);
976 #endif
977 			/* have found place */
978 			for (j = bot; j <= top; j++) {
979 				k = startup + ctable[nchar[j]];
980 				if (ctable[nchar[j]] <= 0)
981 					(void) printf(
982 					"j %d nchar %d ctable.nch %d\n",
983 					    j, (int)nchar[j], ctable[nchar[k]]);
984 				verify[k] = i + 1;	/* state number + 1 */
985 				advance[k] = nexts[j+1]+1;
986 				if (yytop < k)
987 					yytop = k;
988 			}
989 		} else {
990 			do {
991 				startup += 1;
992 				if (startup > outsize - ZCH)
993 					error("output table overflow");
994 				for (j = bot; j <= top; j++) {
995 					k = startup + nchar[j];
996 					if (verify[k])
997 						break;
998 				}
999 			} while (j <= top);
1000 			/* have found place */
1001 #if DEBUG
1002 	if (debug)
1003 		(void) printf(" startup going to be %d\n", startup);
1004 #endif
1005 			for (j = bot; j <= top; j++) {
1006 				k = startup + nchar[j];
1007 				verify[k] = i+1; /* state number + 1 */
1008 				advance[k] = nexts[j+1] + 1;
1009 				if (yytop < k)
1010 					yytop = k;
1011 			}
1012 		}
1013 		stoff[i] = startup;
1014 	}
1015 
1016 	/* stoff[i] = offset into verify, advance for trans for state i */
1017 	/* put out yywork */
1018 	if (ratfor) {
1019 		(void) fprintf(fout, "define YYTOPVAL %d\n", yytop);
1020 		rprint(verify, "verif", yytop+1);
1021 		rprint(advance, "advan", yytop+1);
1022 		shiftr(stoff, stnum);
1023 		rprint(stoff, "stoff", stnum+1);
1024 		shiftr(sfall, stnum);
1025 		upone(sfall, stnum+1);
1026 		rprint(sfall, "fall", stnum+1);
1027 		bprint(extra, "extra", casecount+1);
1028 		bprint((char *)match, "match", ncg);
1029 		shiftr(atable, stnum);
1030 		rprint(atable, "atable", stnum+1);
1031 	}
1032 	(void) fprintf(fout,
1033 	"# define YYTYPE %s\n", stnum+1 >= NCH ? "int" : "unsigned char");
1034 	(void) fprintf(fout,
1035 	"struct yywork { YYTYPE verify, advance; } yycrank[] = {\n");
1036 	for (i = 0; i <= yytop; i += 4) {
1037 		for (j = 0; j < 4; j++) {
1038 			k = i+j;
1039 			if (verify[k])
1040 				(void) fprintf(fout,
1041 				"%d,%d,\t", verify[k], advance[k]);
1042 			else
1043 				(void) fprintf(fout, "0,0,\t");
1044 		}
1045 		(void) putc('\n', fout);
1046 	}
1047 	(void) fprintf(fout, "0,0};\n");
1048 
1049 	/* put out yysvec */
1050 
1051 	(void) fprintf(fout, "struct yysvf yysvec[] = {\n");
1052 	(void) fprintf(fout, "0,\t0,\t0,\n");
1053 	for (i = 0; i <= stnum; i++) {	/* for each state */
1054 		if (cpackflg[i])
1055 			stoff[i] = -stoff[i];
1056 		(void) fprintf(fout, "yycrank+%d,\t", stoff[i]);
1057 		if (sfall[i] != -1)
1058 			(void) fprintf(fout,
1059 			"yysvec+%d,\t", sfall[i]+1); /* state + 1 */
1060 		else
1061 			(void) fprintf(fout, "0,\t\t");
1062 		if (atable[i] != -1)
1063 			(void) fprintf(fout, "yyvstop+%d,", atable[i]);
1064 		else
1065 			(void) fprintf(fout, "0,\t");
1066 #ifdef DEBUG
1067 		(void) fprintf(fout, "\t\t/* state %d */", i);
1068 #endif
1069 		(void) putc('\n', fout);
1070 	}
1071 	(void) fprintf(fout, "0,\t0,\t0};\n");
1072 
1073 	/* put out yymatch */
1074 
1075 	(void) fprintf(fout, "struct yywork *yytop = yycrank+%d;\n", yytop);
1076 	(void) fprintf(fout, "struct yysvf *yybgin = yysvec+1;\n");
1077 	if (optim) {
1078 		if (handleeuc) {
1079 			(void) fprintf(fout, "int yymatch[] = {\n");
1080 		} else {
1081 			(void) fprintf(fout, "char yymatch[] = {\n");
1082 		}
1083 		if (chset == 0) { /* no chset, put out in normal order */
1084 			for (i = 0; i < ncg; i += 8) {
1085 				for (j = 0; j < 8; j++) {
1086 					int fbch;
1087 					fbch = match[i+j];
1088 					(void) fprintf(fout, "%3d, ", fbch);
1089 				}
1090 				(void) putc('\n', fout);
1091 			}
1092 		} else {
1093 			int *fbarr;
1094 			/*LINTED: E_BAD_PTR_CAST_ALIGN*/
1095 			fbarr = (int *)myalloc(2*MAXNCG, sizeof (*fbarr));
1096 			if (fbarr == 0)
1097 				error("No space for char table reverse", 0);
1098 			for (i = 0; i < MAXNCG; i++)
1099 				fbarr[i] = 0;
1100 			for (i = 0; i < ncg; i++)
1101 				fbarr[ctable[i]] = ctable[match[i]];
1102 			for (i = 0; i < ncg; i += 8) {
1103 				for (j = 0; j < 8; j++)
1104 					(void) fprintf(fout, "0%-3o,",
1105 					    fbarr[i+j]);
1106 				(void) putc('\n', fout);
1107 			}
1108 			free(fbarr);
1109 		}
1110 		(void) fprintf(fout, "0};\n");
1111 	}
1112 	/* put out yyextra */
1113 	(void) fprintf(fout, "char yyextra[] = {\n");
1114 	for (i = 0; i < casecount; i += 8) {
1115 		for (j = 0; j < 8; j++)
1116 			(void) fprintf(fout, "%d,", i+j < NACTIONS ?
1117 			    extra[i+j] : 0);
1118 		(void) putc('\n', fout);
1119 	}
1120 	(void) fprintf(fout, "0};\n");
1121 	if (handleeuc) {
1122 		/* Put out yycgidtbl */
1123 		(void) fprintf(fout, "#define YYNCGIDTBL %d\n", ncgidtbl);
1124 		(void) fprintf(fout, "\tunsigned long yycgidtbl[]={");
1125 		/*
1126 		 * Use "unsigned long" instead of "lchar" to minimize
1127 		 * the name-space polution for the application program.
1128 		 */
1129 		for (i = 0; i < ncgidtbl; ++i) {
1130 			if (i%8 == 0)
1131 				(void) fprintf(fout, "\n\t\t");
1132 			(void) fprintf(fout, "0x%08x, ",  (int)yycgidtbl[i]);
1133 		}
1134 		(void) fprintf(fout, "\n\t0};\n");
1135 	}
1136 }
1137 
1138 static void
rprint(int * a,char * s,int n)1139 rprint(int *a, char *s, int n)
1140 {
1141 	int i;
1142 	(void) fprintf(fout, "block data\n");
1143 	(void) fprintf(fout, "common /L%s/ %s\n", s, s);
1144 	(void) fprintf(fout, "define S%s %d\n", s, n);
1145 	(void) fprintf(fout, "integer %s (S%s)\n", s, s);
1146 	for (i = 1; i <= n; i++) {
1147 		if (i%8 == 1)
1148 			(void) fprintf(fout, "data ");
1149 		(void) fprintf(fout, "%s (%d)/%d/", s, i, a[i]);
1150 		(void) fprintf(fout, (i%8 && i < n) ? ", " : "\n");
1151 	}
1152 	(void) fprintf(fout, "end\n");
1153 }
1154 
1155 static void
shiftr(int * a,int n)1156 shiftr(int *a, int n)
1157 {
1158 	int i;
1159 	for (i = n; i >= 0; i--)
1160 		a[i+1] = a[i];
1161 }
1162 
1163 static void
upone(int * a,int n)1164 upone(int *a, int n)
1165 {
1166 	int i;
1167 	for (i = 0; i <= n; i++)
1168 		a[i]++;
1169 }
1170 
1171 static void
bprint(char * a,char * s,int n)1172 bprint(char *a, char *s, int n)
1173 {
1174 	int i, j, k;
1175 	(void) fprintf(fout, "block data\n");
1176 	(void) fprintf(fout, "common /L%s/ %s\n", s, s);
1177 	(void) fprintf(fout, "define S%s %d\n", s, n);
1178 	(void) fprintf(fout, "integer %s (S%s)\n", s, s);
1179 	for (i = 1; i < n; i += 8) {
1180 		(void) fprintf(fout, "data %s (%d)/%d/", s, i, a[i]);
1181 		for (j = 1; j < 8; j++) {
1182 			k = i+j;
1183 			if (k < n)
1184 				(void) fprintf(fout,
1185 				    ", %s (%d)/%d/", s, k, a[k]);
1186 		}
1187 		(void) putc('\n', fout);
1188 	}
1189 	(void) fprintf(fout, "end\n");
1190 }
1191 
1192 #ifdef PP
1193 static void
padd(int ** array,int n)1194 padd(int **array, int n)
1195 {
1196 	int i, *j, k;
1197 	array[n] = nxtpos;
1198 	if (count == 0) {
1199 		*nxtpos++ = 0;
1200 		return;
1201 	}
1202 	for (i = tptr-1; i >= 0; i--) {
1203 		j = array[i];
1204 		if (j && *j++ == count) {
1205 			for (k = 0; k < count; k++)
1206 				if (!tmpstat[*j++])
1207 					break;
1208 			if (k >= count) {
1209 				array[n] = array[i];
1210 				return;
1211 			}
1212 		}
1213 	}
1214 	add(array, n);
1215 }
1216 #endif
1217