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 2007 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 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 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 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 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 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 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 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 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", 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 fprintf(fout, "data vstop(%d)/%d/\n", aptr, neg[i]) : 856 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 ratfor ? fprintf(fout, "data vstop (%d)/0/\n", aptr) : 868 fprintf(fout, "0, \n"); 869 aptr++; 870 } 871 872 #ifdef DEBUG 873 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 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 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, 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 fprintf(fout, "%3d, ", fbch); 1089 } 1090 (void) putc('\n', fout); 1091 } 1092 } else { 1093 int *fbarr; 1094 fbarr = (int *)myalloc(2*MAXNCG, sizeof (*fbarr)); 1095 if (fbarr == 0) 1096 error("No space for char table reverse", 0); 1097 for (i = 0; i < MAXNCG; i++) 1098 fbarr[i] = 0; 1099 for (i = 0; i < ncg; i++) 1100 fbarr[ctable[i]] = ctable[match[i]]; 1101 for (i = 0; i < ncg; i += 8) { 1102 for (j = 0; j < 8; j++) 1103 fprintf(fout, "0%-3o,", fbarr[i+j]); 1104 putc('\n', fout); 1105 } 1106 free(fbarr); 1107 } 1108 (void) fprintf(fout, "0};\n"); 1109 } 1110 /* put out yyextra */ 1111 (void) fprintf(fout, "char yyextra[] = {\n"); 1112 for (i = 0; i < casecount; i += 8) { 1113 for (j = 0; j < 8; j++) 1114 (void) fprintf(fout, "%d,", i+j < NACTIONS ? 1115 extra[i+j] : 0); 1116 (void) putc('\n', fout); 1117 } 1118 (void) fprintf(fout, "0};\n"); 1119 if (handleeuc) { 1120 /* Put out yycgidtbl */ 1121 fprintf(fout, "#define YYNCGIDTBL %d\n", ncgidtbl); 1122 fprintf(fout, "\tunsigned long yycgidtbl[]={"); 1123 /* 1124 * Use "unsigned long" instead of "lchar" to minimize 1125 * the name-space polution for the application program. 1126 */ 1127 for (i = 0; i < ncgidtbl; ++i) { 1128 if (i%8 == 0) 1129 fprintf(fout, "\n\t\t"); 1130 fprintf(fout, "0x%08x, ", yycgidtbl[i]); 1131 } 1132 fprintf(fout, "\n\t0};\n"); 1133 } 1134 } 1135 1136 static void 1137 rprint(int *a, char *s, int n) 1138 { 1139 int i; 1140 (void) fprintf(fout, "block data\n"); 1141 (void) fprintf(fout, "common /L%s/ %s\n", s, s); 1142 (void) fprintf(fout, "define S%s %d\n", s, n); 1143 (void) fprintf(fout, "integer %s (S%s)\n", s, s); 1144 for (i = 1; i <= n; i++) { 1145 if (i%8 == 1) 1146 (void) fprintf(fout, "data "); 1147 (void) fprintf(fout, "%s (%d)/%d/", s, i, a[i]); 1148 (void) fprintf(fout, (i%8 && i < n) ? ", " : "\n"); 1149 } 1150 (void) fprintf(fout, "end\n"); 1151 } 1152 1153 static void 1154 shiftr(int *a, int n) 1155 { 1156 int i; 1157 for (i = n; i >= 0; i--) 1158 a[i+1] = a[i]; 1159 } 1160 1161 static void 1162 upone(int *a, int n) 1163 { 1164 int i; 1165 for (i = 0; i <= n; i++) 1166 a[i]++; 1167 } 1168 1169 static void 1170 bprint(char *a, char *s, int n) 1171 { 1172 int i, j, k; 1173 (void) fprintf(fout, "block data\n"); 1174 (void) fprintf(fout, "common /L%s/ %s\n", s, s); 1175 (void) fprintf(fout, "define S%s %d\n", s, n); 1176 (void) fprintf(fout, "integer %s (S%s)\n", s, s); 1177 for (i = 1; i < n; i += 8) { 1178 (void) fprintf(fout, "data %s (%d)/%d/", s, i, a[i]); 1179 for (j = 1; j < 8; j++) { 1180 k = i+j; 1181 if (k < n) 1182 (void) fprintf(fout, 1183 ", %s (%d)/%d/", s, k, a[k]); 1184 } 1185 (void) putc('\n', fout); 1186 } 1187 (void) fprintf(fout, "end\n"); 1188 } 1189 1190 #ifdef PP 1191 static void 1192 padd(int **array, int n) 1193 { 1194 int i, *j, k; 1195 array[n] = nxtpos; 1196 if (count == 0) { 1197 *nxtpos++ = 0; 1198 return; 1199 } 1200 for (i = tptr-1; i >= 0; i--) { 1201 j = array[i]; 1202 if (j && *j++ == count) { 1203 for (k = 0; k < count; k++) 1204 if (!tmpstat[*j++]) 1205 break; 1206 if (k >= count) { 1207 array[n] = array[i]; 1208 return; 1209 } 1210 } 1211 } 1212 add(array, n); 1213 } 1214 #endif 1215