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 #include "ldefs.h"
30
31 static void add(int **array, int n);
32 static void follow(int v);
33 static void first(int v);
34 static void nextstate(int s, int c);
35 static void packtrans(int st, CHR *tch, int *tst, int cnt, int tryit);
36 static void acompute(int s);
37 static void rprint(int *a, char *s, int n);
38 static void shiftr(int *a, int n);
39 static void upone(int *a, int n);
40 static void bprint(char *a, char *s, int n);
41 static int notin(int n);
42 static int member(int d, CHR *t);
43
44 #ifdef PP
45 static void padd(int **array, int n);
46 #endif
47
48 void
cfoll(int v)49 cfoll(int v)
50 {
51 int i, j, k;
52 CHR *p;
53 i = name[v];
54 if (!ISOPERATOR(i))
55 i = 1;
56 switch (i) {
57 case 1: case RSTR: case RCCL: case RNCCL: case RNULLS:
58 for (j = 0; j < tptr; j++)
59 tmpstat[j] = FALSE;
60 count = 0;
61 follow(v);
62 #ifdef PP
63 padd(foll, v); /* packing version */
64 #else
65 add(foll, v); /* no packing version */
66 #endif
67 if (i == RSTR)
68 cfoll(left[v]);
69 else if (i == RCCL || i == RNCCL) {
70 for (j = 1; j < ncg; j++)
71 symbol[j] = (i == RNCCL);
72 p = (CHR *) left[v];
73 while (*p)
74 symbol[*p++] = (i == RCCL);
75 p = pcptr;
76 for (j = 1; j < ncg; j++)
77 if (symbol[j]) {
78 for (k = 0; p + k < pcptr; k++)
79 if (cindex[j] ==
80 *(p + k))
81 break;
82 if (p + k >= pcptr)
83 *pcptr++ = cindex[j];
84 }
85 *pcptr++ = 0;
86 if (pcptr > pchar + pchlen)
87 error(
88 "Too many packed character classes");
89 left[v] = (int)p;
90 name[v] = RCCL; /* RNCCL eliminated */
91 #ifdef DEBUG
92 if (debug && *p) {
93 (void) printf("ccl %d: %d", v, *p++);
94 while (*p)
95 (void) printf(", %d", *p++);
96 (void) putchar('\n');
97 }
98 #endif
99 }
100 break;
101 case CARAT:
102 cfoll(left[v]);
103 break;
104
105 /* XCU4: add RXSCON */
106 case RXSCON:
107
108 case STAR: case PLUS: case QUEST: case RSCON:
109 cfoll(left[v]);
110 break;
111 case BAR: case RCAT: case DIV: case RNEWE:
112 cfoll(left[v]);
113 cfoll(right[v]);
114 break;
115 #ifdef DEBUG
116 case FINAL:
117 case S1FINAL:
118 case S2FINAL:
119 break;
120 default:
121 warning("bad switch cfoll %d", v);
122 #endif
123 }
124 }
125
126 #ifdef DEBUG
127 void
pfoll(void)128 pfoll(void)
129 {
130 int i, k, *p;
131 int j;
132 /* print sets of chars which may follow positions */
133 (void) printf("pos\tchars\n");
134 for (i = 0; i < tptr; i++)
135 if (p = foll[i]) {
136 j = *p++;
137 if (j >= 1) {
138 (void) printf("%d:\t%d", i, *p++);
139 for (k = 2; k <= j; k++)
140 (void) printf(", %d", *p++);
141 (void) putchar('\n');
142 }
143 }
144 }
145 #endif
146
147 static void
add(int ** array,int n)148 add(int **array, int n)
149 {
150 int i, *temp;
151 CHR *ctemp;
152 temp = nxtpos;
153 ctemp = tmpstat;
154 array[n] = nxtpos; /* note no packing is done in positions */
155 *temp++ = count;
156 for (i = 0; i < tptr; i++)
157 if (ctemp[i] == TRUE)
158 *temp++ = i;
159 nxtpos = temp;
160 if (nxtpos >= positions+maxpos)
161 error(
162 "Too many positions %s",
163 (maxpos == MAXPOS ? "\nTry using %p num" : ""));
164 }
165
166 static void
follow(int v)167 follow(int v)
168 {
169 int p;
170 if (v >= tptr-1)
171 return;
172 p = parent[v];
173 if (p == 0)
174 return;
175 switch (name[p]) {
176 /* will not be CHAR RNULLS FINAL S1FINAL S2FINAL RCCL RNCCL */
177 case RSTR:
178 if (tmpstat[p] == FALSE) {
179 count++;
180 tmpstat[p] = TRUE;
181 }
182 break;
183 case STAR: case PLUS:
184 first(v);
185 follow(p);
186 break;
187 case BAR: case QUEST: case RNEWE:
188 follow(p);
189 break;
190 case RCAT: case DIV:
191 if (v == left[p]) {
192 if (nullstr[right[p]])
193 follow(p);
194 first(right[p]);
195 }
196 else
197 follow(p);
198 break;
199 /* XCU4: add RXSCON */
200 case RXSCON:
201 case RSCON: case CARAT:
202 follow(p);
203 break;
204 #ifdef DEBUG
205 default:
206 warning("bad switch follow %d", p);
207 #endif
208 }
209 }
210
211 /*
212 * Check if I have a RXSCON in my upper node
213 */
214 static int
check_me(int v)215 check_me(int v)
216 {
217 int tmp = parent[v];
218
219 while (name[tmp] != RNEWE) {
220 if (name[tmp] == RXSCON)
221 return (1);
222 tmp = parent[tmp];
223 }
224 return (0);
225 }
226
227 /* calculate set of positions with v as root which can be active initially */
228 static void
first(int v)229 first(int v)
230 {
231 int i;
232 CHR *p;
233 i = name[v];
234 if (!ISOPERATOR(i))
235 i = 1;
236 switch (i) {
237 case 1: case RCCL: case RNCCL:
238 case RNULLS: case FINAL:
239 case S1FINAL: case S2FINAL:
240 /*
241 * XCU4: if we are working on an exclusive start state and
242 * the parent of this position is not RXSCON or RSTR this
243 * is not an active position.
244 *
245 * (There is a possibility that RSXCON appreas as the
246 * (parent)* node. Check it by check_me().)
247 */
248 if ((exclusive[stnum/2]) &&
249 ISOPERATOR(name[parent[v]]) &&
250 (name[parent[v]] != RXSCON) &&
251 (name[parent[v]] != RSTR) &&
252 (check_me(v) == 0)) {
253 break;
254 }
255 if (tmpstat[v] == FALSE) {
256 count++;
257 tmpstat[v] = TRUE;
258 }
259 break;
260 case BAR: case RNEWE:
261 first(left[v]);
262 first(right[v]);
263 break;
264 case CARAT:
265 if (stnum % 2 == 1)
266 first(left[v]);
267 break;
268 /* XCU4: add RXSCON */
269 case RXSCON:
270 case RSCON:
271 i = stnum/2 +1;
272 p = (CHR *) right[v];
273 while (*p)
274 if (*p++ == i) {
275 first(left[v]);
276 break;
277 }
278 break;
279 case STAR: case QUEST:
280 case PLUS: case RSTR:
281 /*
282 * XCU4: if we are working on an exclusive start state and
283 * the parent of this position is not RXSCON or RSTR this
284 * is not an active position.
285 *
286 * (There is a possibility that RSXCON appreas as the
287 * (parent)* node. Check it by check_me().)
288 */
289 if ((exclusive[stnum/2]) &&
290 ISOPERATOR(name[parent[v]]) &&
291 (name[parent[v]] != RXSCON) &&
292 (name[parent[v]] != RSTR) &&
293 (check_me(v) == 0)) {
294 break;
295 }
296 first(left[v]);
297 break;
298 case RCAT: case DIV:
299 first(left[v]);
300 if (nullstr[left[v]])
301 first(right[v]);
302 break;
303 #ifdef DEBUG
304 default:
305 warning("bad switch first %d", v);
306 #endif
307 }
308 }
309
310 void
cgoto(void)311 cgoto(void)
312 {
313 int i, j;
314 static int s;
315 int npos, curpos, n;
316 int tryit;
317 CHR tch[MAXNCG];
318 int tst[MAXNCG];
319 CHR *q;
320 /* generate initial state, for each start condition */
321 if (ratfor) {
322 (void) fprintf(fout, "blockdata\n");
323 (void) fprintf(fout, "common /Lvstop/ vstop\n");
324 (void) fprintf(fout, "define Svstop %d\n", nstates+1);
325 (void) fprintf(fout, "integer vstop(Svstop)\n");
326 } else
327 (void) fprintf(fout, "int yyvstop[] = {\n0,\n");
328 while (stnum < 2 || stnum/2 < sptr) {
329 for (i = 0; i < tptr; i++)
330 tmpstat[i] = 0;
331 count = 0;
332 if (tptr > 0)
333 first(tptr-1);
334 add(state, stnum);
335 #ifdef DEBUG
336 if (debug) {
337 if (stnum > 1)
338 (void) printf("%ws:\n", sname[stnum/2]);
339 pstate(stnum);
340 }
341 #endif
342 stnum++;
343 }
344 stnum--;
345 /* even stnum = might not be at line begin */
346 /* odd stnum = must be at line begin */
347 /* even states can occur anywhere, odd states only at line begin */
348 for (s = 0; s <= stnum; s++) {
349 tryit = FALSE;
350 cpackflg[s] = FALSE;
351 sfall[s] = -1;
352 acompute(s);
353 for (i = 0; i < ncg; i++)
354 symbol[i] = 0;
355 npos = *state[s];
356 for (i = 1; i <= npos; i++) {
357 curpos = *(state[s]+i);
358 if (!ISOPERATOR(name[curpos]))
359 symbol[name[curpos]] = TRUE;
360 else {
361 switch (name[curpos]) {
362 case RCCL:
363 tryit = TRUE;
364 q = (CHR *)left[curpos];
365 while (*q) {
366 for (j = 1; j < ncg; j++)
367 if (cindex[j] == *q)
368 symbol[j] =
369 TRUE;
370 q++;
371 }
372 break;
373 case RSTR:
374 symbol[right[curpos]] = TRUE;
375 break;
376 #ifdef DEBUG
377 case RNULLS:
378 case FINAL:
379 case S1FINAL:
380 case S2FINAL:
381 break;
382 default:
383 warning(
384 "bad switch cgoto %d state %d",
385 curpos, s);
386 break;
387 #endif
388 }
389 }
390 }
391 #ifdef DEBUG
392 if (debug) {
393 printf("State %d transitions on char-group {", s);
394 charc = 0;
395 for (i = 1; i < ncg; i++) {
396 if (symbol[i]) {
397 printf("%d,", i);
398 }
399 if (i == ncg-1)
400 printf("}\n");
401 if (charc > LINESIZE/4) {
402 charc = 0;
403 printf("\n\t");
404 }
405 }
406 }
407 #endif
408 /* for each char, calculate next state */
409 n = 0;
410 for (i = 1; i < ncg; i++) {
411 if (symbol[i]) {
412 /* executed for each state, transition pair */
413 nextstate(s, i);
414 xstate = notin(stnum);
415 if (xstate == -2)
416 warning("bad state %d %o", s, i);
417 else if (xstate == -1) {
418 if (stnum+1 >= nstates) {
419 stnum++;
420 error("Too many states %s",
421 (nstates == NSTATES ?
422 "\nTry using %n num":""));
423 }
424 add(state, ++stnum);
425 #ifdef DEBUG
426 if (debug)
427 pstate(stnum);
428 #endif
429 tch[n] = i;
430 tst[n++] = stnum;
431 } else { /* xstate >= 0 ==> state exists */
432 tch[n] = i;
433 tst[n++] = xstate;
434 }
435 }
436 }
437 tch[n] = 0;
438 tst[n] = -1;
439 /* pack transitions into permanent array */
440 if (n > 0)
441 packtrans(s, tch, tst, n, tryit);
442 else
443 gotof[s] = -1;
444 }
445 (void) (ratfor ? fprintf(fout, "end\n") : fprintf(fout, "0};\n"));
446 }
447
448 /*
449 * Beware -- 70% of total CPU time is spent in this subroutine -
450 * if you don't believe me - try it yourself !
451 */
452 static void
nextstate(int s,int c)453 nextstate(int s, int c)
454 {
455 int j, *newpos;
456 CHR *temp, *tz;
457 int *pos, i, *f, num, curpos, number;
458 /* state to goto from state s on char c */
459 num = *state[s];
460 temp = tmpstat;
461 pos = state[s] + 1;
462 for (i = 0; i < num; i++) {
463 curpos = *pos++;
464 j = name[curpos];
465 if ((!ISOPERATOR(j) && j == c) ||
466 (j == RSTR && c == right[curpos]) ||
467 (j == RCCL && member(c, (CHR *) left[curpos]))) {
468 f = foll[curpos];
469 number = *f;
470 newpos = f+1;
471 for (j = 0; j < number; j++)
472 temp[*newpos++] = 2;
473 }
474 }
475 j = 0;
476 tz = temp + tptr;
477 while (temp < tz) {
478 if (*temp == 2) {
479 j++;
480 *temp++ = 1;
481 }
482 else
483 *temp++ = 0;
484 }
485 count = j;
486 }
487
488 /* see if tmpstat occurs previously */
489 static int
notin(int n)490 notin(int n)
491 {
492 int *j, k;
493 CHR *temp;
494 int i;
495
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