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