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