| 1 | #ifndef lint |
| 2 | static char sccsid[] = "@(#)sub2.c 4.1 (Berkeley) %G%"; |
| 3 | #endif |
| 4 | |
| 5 | # include "ldefs.c" |
| 6 | cfoll(v) |
| 7 | int v; |
| 8 | { |
| 9 | register int i,j,k; |
| 10 | char *p; |
| 11 | i = name[v]; |
| 12 | if(i < NCH) i = 1; /* character */ |
| 13 | switch(i){ |
| 14 | case 1: case RSTR: case RCCL: case RNCCL: case RNULLS: |
| 15 | for(j=0;j<tptr;j++) |
| 16 | tmpstat[j] = FALSE; |
| 17 | count = 0; |
| 18 | follow(v); |
| 19 | # ifdef PP |
| 20 | padd(foll,v); /* packing version */ |
| 21 | # endif |
| 22 | # ifndef PP |
| 23 | add(foll,v); /* no packing version */ |
| 24 | # endif |
| 25 | if(i == RSTR) cfoll(left[v]); |
| 26 | else if(i == RCCL || i == RNCCL){ /* compress ccl list */ |
| 27 | for(j=1; j<NCH;j++) |
| 28 | symbol[j] = (i==RNCCL); |
| 29 | p = left[v]; |
| 30 | while(*p) |
| 31 | symbol[*p++] = (i == RCCL); |
| 32 | p = pcptr; |
| 33 | for(j=1;j<NCH;j++) |
| 34 | if(symbol[j]){ |
| 35 | for(k=0;p+k < pcptr; k++) |
| 36 | if(cindex[j] == *(p+k)) |
| 37 | break; |
| 38 | if(p+k >= pcptr)*pcptr++ = cindex[j]; |
| 39 | } |
| 40 | *pcptr++ = 0; |
| 41 | if(pcptr > pchar + pchlen) |
| 42 | error("Too many packed character classes"); |
| 43 | left[v] = p; |
| 44 | name[v] = RCCL; /* RNCCL eliminated */ |
| 45 | # ifdef DEBUG |
| 46 | if(debug && *p){ |
| 47 | printf("ccl %d: %d",v,*p++); |
| 48 | while(*p) |
| 49 | printf(", %d",*p++); |
| 50 | putchar('\n'); |
| 51 | } |
| 52 | # endif |
| 53 | } |
| 54 | break; |
| 55 | case CARAT: |
| 56 | cfoll(left[v]); |
| 57 | break; |
| 58 | case STAR: case PLUS: case QUEST: case RSCON: |
| 59 | cfoll(left[v]); |
| 60 | break; |
| 61 | case BAR: case RCAT: case DIV: case RNEWE: |
| 62 | cfoll(left[v]); |
| 63 | cfoll(right[v]); |
| 64 | break; |
| 65 | # ifdef DEBUG |
| 66 | case FINAL: |
| 67 | case S1FINAL: |
| 68 | case S2FINAL: |
| 69 | break; |
| 70 | default: |
| 71 | warning("bad switch cfoll %d",v); |
| 72 | # endif |
| 73 | } |
| 74 | return; |
| 75 | } |
| 76 | # ifdef DEBUG |
| 77 | pfoll() |
| 78 | { |
| 79 | register int i,k,*p; |
| 80 | int j; |
| 81 | /* print sets of chars which may follow positions */ |
| 82 | printf("pos\tchars\n"); |
| 83 | for(i=0;i<tptr;i++) |
| 84 | if(p=foll[i]){ |
| 85 | j = *p++; |
| 86 | if(j >= 1){ |
| 87 | printf("%d:\t%d",i,*p++); |
| 88 | for(k=2;k<=j;k++) |
| 89 | printf(", %d",*p++); |
| 90 | putchar('\n'); |
| 91 | } |
| 92 | } |
| 93 | return; |
| 94 | } |
| 95 | # endif |
| 96 | add(array,n) |
| 97 | int **array; |
| 98 | int n; { |
| 99 | register int i, *temp; |
| 100 | register char *ctemp; |
| 101 | temp = nxtpos; |
| 102 | ctemp = tmpstat; |
| 103 | array[n] = nxtpos; /* note no packing is done in positions */ |
| 104 | *temp++ = count; |
| 105 | for(i=0;i<tptr;i++) |
| 106 | if(ctemp[i] == TRUE) |
| 107 | *temp++ = i; |
| 108 | nxtpos = temp; |
| 109 | if(nxtpos >= positions+maxpos) |
| 110 | error("Too many positions %s",(maxpos== MAXPOS?"\nTry using %p num":"")); |
| 111 | return; |
| 112 | } |
| 113 | follow(v) |
| 114 | int v; |
| 115 | { |
| 116 | register int p; |
| 117 | if(v >= tptr-1)return; |
| 118 | p = parent[v]; |
| 119 | if(p == 0) return; |
| 120 | switch(name[p]){ |
| 121 | /* will not be CHAR RNULLS FINAL S1FINAL S2FINAL RCCL RNCCL */ |
| 122 | case RSTR: |
| 123 | if(tmpstat[p] == FALSE){ |
| 124 | count++; |
| 125 | tmpstat[p] = TRUE; |
| 126 | } |
| 127 | break; |
| 128 | case STAR: case PLUS: |
| 129 | first(v); |
| 130 | follow(p); |
| 131 | break; |
| 132 | case BAR: case QUEST: case RNEWE: |
| 133 | follow(p); |
| 134 | break; |
| 135 | case RCAT: case DIV: |
| 136 | if(v == left[p]){ |
| 137 | if(nullstr[right[p]]) |
| 138 | follow(p); |
| 139 | first(right[p]); |
| 140 | } |
| 141 | else follow(p); |
| 142 | break; |
| 143 | case RSCON: case CARAT: |
| 144 | follow(p); |
| 145 | break; |
| 146 | # ifdef DEBUG |
| 147 | default: |
| 148 | warning("bad switch follow %d",p); |
| 149 | # endif |
| 150 | } |
| 151 | return; |
| 152 | } |
| 153 | first(v) /* calculate set of positions with v as root which can be active initially */ |
| 154 | int v; { |
| 155 | register int i; |
| 156 | register char *p; |
| 157 | i = name[v]; |
| 158 | if(i < NCH)i = 1; |
| 159 | switch(i){ |
| 160 | case 1: case RCCL: case RNCCL: case RNULLS: case FINAL: case S1FINAL: case S2FINAL: |
| 161 | if(tmpstat[v] == FALSE){ |
| 162 | count++; |
| 163 | tmpstat[v] = TRUE; |
| 164 | } |
| 165 | break; |
| 166 | case BAR: case RNEWE: |
| 167 | first(left[v]); |
| 168 | first(right[v]); |
| 169 | break; |
| 170 | case CARAT: |
| 171 | if(stnum % 2 == 1) |
| 172 | first(left[v]); |
| 173 | break; |
| 174 | case RSCON: |
| 175 | i = stnum/2 +1; |
| 176 | p = right[v]; |
| 177 | while(*p) |
| 178 | if(*p++ == i){ |
| 179 | first(left[v]); |
| 180 | break; |
| 181 | } |
| 182 | break; |
| 183 | case STAR: case QUEST: case PLUS: case RSTR: |
| 184 | first(left[v]); |
| 185 | break; |
| 186 | case RCAT: case DIV: |
| 187 | first(left[v]); |
| 188 | if(nullstr[left[v]]) |
| 189 | first(right[v]); |
| 190 | break; |
| 191 | # ifdef DEBUG |
| 192 | default: |
| 193 | warning("bad switch first %d",v); |
| 194 | # endif |
| 195 | } |
| 196 | return; |
| 197 | } |
| 198 | cgoto(){ |
| 199 | register int i, j, s; |
| 200 | int npos, curpos, n; |
| 201 | int tryit; |
| 202 | char tch[NCH]; |
| 203 | int tst[NCH]; |
| 204 | char *q; |
| 205 | /* generate initial state, for each start condition */ |
| 206 | if(ratfor){ |
| 207 | fprintf(fout,"blockdata\n"); |
| 208 | fprintf(fout,"common /Lvstop/ vstop\n"); |
| 209 | fprintf(fout,"define Svstop %d\n",nstates+1); |
| 210 | fprintf(fout,"integer vstop(Svstop)\n"); |
| 211 | } |
| 212 | else fprintf(fout,"int yyvstop[] ={\n0,\n"); |
| 213 | while(stnum < 2 || stnum/2 < sptr){ |
| 214 | for(i = 0; i<tptr; i++) tmpstat[i] = 0; |
| 215 | count = 0; |
| 216 | if(tptr > 0)first(tptr-1); |
| 217 | add(state,stnum); |
| 218 | # ifdef DEBUG |
| 219 | if(debug){ |
| 220 | if(stnum > 1) |
| 221 | printf("%s:\n",sname[stnum/2]); |
| 222 | pstate(stnum); |
| 223 | } |
| 224 | # endif |
| 225 | stnum++; |
| 226 | } |
| 227 | stnum--; |
| 228 | /* even stnum = might not be at line begin */ |
| 229 | /* odd stnum = must be at line begin */ |
| 230 | /* even states can occur anywhere, odd states only at line begin */ |
| 231 | for(s = 0; s <= stnum; s++){ |
| 232 | tryit = FALSE; |
| 233 | cpackflg[s] = FALSE; |
| 234 | sfall[s] = -1; |
| 235 | acompute(s); |
| 236 | for(i=0;i<NCH;i++) symbol[i] = 0; |
| 237 | npos = *state[s]; |
| 238 | for(i = 1; i<=npos; i++){ |
| 239 | curpos = *(state[s]+i); |
| 240 | if(name[curpos] < NCH) symbol[name[curpos]] = TRUE; |
| 241 | else switch(name[curpos]){ |
| 242 | case RCCL: |
| 243 | tryit = TRUE; |
| 244 | q = left[curpos]; |
| 245 | while(*q){ |
| 246 | for(j=1;j<NCH;j++) |
| 247 | if(cindex[j] == *q) |
| 248 | symbol[j] = TRUE; |
| 249 | q++; |
| 250 | } |
| 251 | break; |
| 252 | case RSTR: |
| 253 | symbol[right[curpos]] = TRUE; |
| 254 | break; |
| 255 | # ifdef DEBUG |
| 256 | case RNULLS: |
| 257 | case FINAL: |
| 258 | case S1FINAL: |
| 259 | case S2FINAL: |
| 260 | break; |
| 261 | default: |
| 262 | warning("bad switch cgoto %d state %d",curpos,s); |
| 263 | break; |
| 264 | # endif |
| 265 | } |
| 266 | } |
| 267 | # ifdef DEBUG |
| 268 | if(debug){ |
| 269 | printf("State %d transitions on:\n\t",s); |
| 270 | charc = 0; |
| 271 | for(i = 1; i<NCH; i++){ |
| 272 | if(symbol[i]) allprint(i); |
| 273 | if(charc > LINESIZE){ |
| 274 | charc = 0; |
| 275 | printf("\n\t"); |
| 276 | } |
| 277 | } |
| 278 | putchar('\n'); |
| 279 | } |
| 280 | # endif |
| 281 | /* for each char, calculate next state */ |
| 282 | n = 0; |
| 283 | for(i = 1; i<NCH; i++){ |
| 284 | if(symbol[i]){ |
| 285 | nextstate(s,i); /* executed for each state, transition pair */ |
| 286 | xstate = notin(stnum); |
| 287 | if(xstate == -2) warning("bad state %d %o",s,i); |
| 288 | else if(xstate == -1){ |
| 289 | if(stnum >= nstates) |
| 290 | error("Too many states %s",(nstates == NSTATES ? "\nTry using %n num":"")); |
| 291 | add(state,++stnum); |
| 292 | # ifdef DEBUG |
| 293 | if(debug)pstate(stnum); |
| 294 | # endif |
| 295 | tch[n] = i; |
| 296 | tst[n++] = stnum; |
| 297 | } |
| 298 | else { /* xstate >= 0 ==> state exists */ |
| 299 | tch[n] = i; |
| 300 | tst[n++] = xstate; |
| 301 | } |
| 302 | } |
| 303 | } |
| 304 | tch[n] = 0; |
| 305 | tst[n] = -1; |
| 306 | /* pack transitions into permanent array */ |
| 307 | if(n > 0) packtrans(s,tch,tst,n,tryit); |
| 308 | else gotof[s] = -1; |
| 309 | } |
| 310 | ratfor ? fprintf(fout,"end\n") : fprintf(fout,"0};\n"); |
| 311 | return; |
| 312 | } |
| 313 | /* Beware -- 70% of total CPU time is spent in this subroutine - |
| 314 | if you don't believe me - try it yourself ! */ |
| 315 | nextstate(s,c) |
| 316 | int s,c; { |
| 317 | register int j, *newpos; |
| 318 | register char *temp, *tz; |
| 319 | int *pos, i, *f, num, curpos, number; |
| 320 | /* state to goto from state s on char c */ |
| 321 | num = *state[s]; |
| 322 | temp = tmpstat; |
| 323 | pos = state[s] + 1; |
| 324 | for(i = 0; i<num; i++){ |
| 325 | curpos = *pos++; |
| 326 | j = name[curpos]; |
| 327 | if(j < NCH && j == c |
| 328 | || j == RSTR && c == right[curpos] |
| 329 | || j == RCCL && member(c,left[curpos])){ |
| 330 | f = foll[curpos]; |
| 331 | number = *f; |
| 332 | newpos = f+1; |
| 333 | for(j=0;j<number;j++) |
| 334 | temp[*newpos++] = 2; |
| 335 | } |
| 336 | } |
| 337 | j = 0; |
| 338 | tz = temp + tptr; |
| 339 | while(temp < tz){ |
| 340 | if(*temp == 2){ |
| 341 | j++; |
| 342 | *temp++ = 1; |
| 343 | } |
| 344 | else *temp++ = 0; |
| 345 | } |
| 346 | count = j; |
| 347 | return; |
| 348 | } |
| 349 | notin(n) |
| 350 | int n; { /* see if tmpstat occurs previously */ |
| 351 | register int *j,k; |
| 352 | register char *temp; |
| 353 | int i; |
| 354 | if(count == 0) |
| 355 | return(-2); |
| 356 | temp = tmpstat; |
| 357 | for(i=n;i>=0;i--){ /* for each state */ |
| 358 | j = state[i]; |
| 359 | if(count == *j++){ |
| 360 | for(k=0;k<count;k++) |
| 361 | if(!temp[*j++])break; |
| 362 | if(k >= count) |
| 363 | return(i); |
| 364 | } |
| 365 | } |
| 366 | return(-1); |
| 367 | } |
| 368 | packtrans(st,tch,tst,cnt,tryit) |
| 369 | int st, *tst, cnt,tryit; |
| 370 | char *tch; { |
| 371 | /* pack transitions into nchar, nexts */ |
| 372 | /* nchar is terminated by '\0', nexts uses cnt, followed by elements */ |
| 373 | /* gotof[st] = index into nchr, nexts for state st */ |
| 374 | |
| 375 | /* sfall[st] = t implies t is fall back state for st */ |
| 376 | /* == -1 implies no fall back */ |
| 377 | |
| 378 | int cmin, cval, tcnt, diff, p, *ast; |
| 379 | register int i,j,k; |
| 380 | char *ach; |
| 381 | int go[NCH], temp[NCH], c; |
| 382 | int swork[NCH]; |
| 383 | char cwork[NCH]; |
| 384 | int upper; |
| 385 | |
| 386 | rcount += cnt; |
| 387 | cmin = -1; |
| 388 | cval = NCH; |
| 389 | ast = tst; |
| 390 | ach = tch; |
| 391 | /* try to pack transitions using ccl's */ |
| 392 | if(!optim)goto nopack; /* skip all compaction */ |
| 393 | if(tryit){ /* ccl's used */ |
| 394 | for(i=1;i<NCH;i++){ |
| 395 | go[i] = temp[i] = -1; |
| 396 | symbol[i] = 1; |
| 397 | } |
| 398 | for(i=0;i<cnt;i++){ |
| 399 | go[tch[i]] = tst[i]; |
| 400 | symbol[tch[i]] = 0; |
| 401 | } |
| 402 | for(i=0; i<cnt;i++){ |
| 403 | c = match[tch[i]]; |
| 404 | if(go[c] != tst[i] || c == tch[i]) |
| 405 | temp[tch[i]] = tst[i]; |
| 406 | } |
| 407 | /* fill in error entries */ |
| 408 | for(i=1;i<NCH;i++) |
| 409 | if(symbol[i]) temp[i] = -2; /* error trans */ |
| 410 | /* count them */ |
| 411 | k = 0; |
| 412 | for(i=1;i<NCH;i++) |
| 413 | if(temp[i] != -1)k++; |
| 414 | if(k <cnt){ /* compress by char */ |
| 415 | # ifdef DEBUG |
| 416 | if(debug) printf("use compression %d, %d vs %d\n",st,k,cnt); |
| 417 | # endif |
| 418 | k = 0; |
| 419 | for(i=1;i<NCH;i++) |
| 420 | if(temp[i] != -1){ |
| 421 | cwork[k] = i; |
| 422 | swork[k++] = (temp[i] == -2 ? -1 : temp[i]); |
| 423 | } |
| 424 | cwork[k] = 0; |
| 425 | # ifdef PC |
| 426 | ach = cwork; |
| 427 | ast = swork; |
| 428 | cnt = k; |
| 429 | cpackflg[st] = TRUE; |
| 430 | # endif |
| 431 | } |
| 432 | } |
| 433 | for(i=0; i<st; i++){ /* get most similar state */ |
| 434 | /* reject state with more transitions, state already represented by a third state, |
| 435 | and state which is compressed by char if ours is not to be */ |
| 436 | if(sfall[i] != -1) continue; |
| 437 | if(cpackflg[st] == 1) if(!(cpackflg[i] == 1)) continue; |
| 438 | p = gotof[i]; |
| 439 | if(p == -1) /* no transitions */ continue; |
| 440 | tcnt = nexts[p]; |
| 441 | if(tcnt > cnt) continue; |
| 442 | diff = 0; |
| 443 | k = 0; |
| 444 | j = 0; |
| 445 | upper = p + tcnt; |
| 446 | while(ach[j] && p < upper){ |
| 447 | while(ach[j] < nchar[p] && ach[j]){diff++; j++; } |
| 448 | if(ach[j] == 0)break; |
| 449 | if(ach[j] > nchar[p]){diff=NCH;break;} |
| 450 | /* ach[j] == nchar[p] */ |
| 451 | if(ast[j] != nexts[++p] || ast[j] == -1 || (cpackflg[st] && ach[j] != match[ach[j]]))diff++; |
| 452 | j++; |
| 453 | } |
| 454 | while(ach[j]){ |
| 455 | diff++; |
| 456 | j++; |
| 457 | } |
| 458 | if(p < upper)diff = NCH; |
| 459 | if(diff < cval && diff < tcnt){ |
| 460 | cval = diff; |
| 461 | cmin = i; |
| 462 | if(cval == 0)break; |
| 463 | } |
| 464 | } |
| 465 | /* cmin = state "most like" state st */ |
| 466 | # ifdef DEBUG |
| 467 | if(debug)printf("select st %d for st %d diff %d\n",cmin,st,cval); |
| 468 | # endif |
| 469 | # ifdef PS |
| 470 | if(cmin != -1){ /* if we can use st cmin */ |
| 471 | gotof[st] = nptr; |
| 472 | k = 0; |
| 473 | sfall[st] = cmin; |
| 474 | p = gotof[cmin]+1; |
| 475 | j = 0; |
| 476 | while(ach[j]){ |
| 477 | /* if cmin has a transition on c, then so will st */ |
| 478 | /* st may be "larger" than cmin, however */ |
| 479 | while(ach[j] < nchar[p-1] && ach[j]){ |
| 480 | k++; |
| 481 | nchar[nptr] = ach[j]; |
| 482 | nexts[++nptr] = ast[j]; |
| 483 | j++; |
| 484 | } |
| 485 | if(nchar[p-1] == 0)break; |
| 486 | if(ach[j] > nchar[p-1]){ |
| 487 | warning("bad transition %d %d",st,cmin); |
| 488 | goto nopack; |
| 489 | } |
| 490 | /* ach[j] == nchar[p-1] */ |
| 491 | if(ast[j] != nexts[p] || ast[j] == -1 || (cpackflg[st] && ach[j] != match[ach[j]])){ |
| 492 | k++; |
| 493 | nchar[nptr] = ach[j]; |
| 494 | nexts[++nptr] = ast[j]; |
| 495 | } |
| 496 | p++; |
| 497 | j++; |
| 498 | } |
| 499 | while(ach[j]){ |
| 500 | nchar[nptr] = ach[j]; |
| 501 | nexts[++nptr] = ast[j++]; |
| 502 | k++; |
| 503 | } |
| 504 | nexts[gotof[st]] = cnt = k; |
| 505 | nchar[nptr++] = 0; |
| 506 | } |
| 507 | else { |
| 508 | # endif |
| 509 | nopack: |
| 510 | /* stick it in */ |
| 511 | gotof[st] = nptr; |
| 512 | nexts[nptr] = cnt; |
| 513 | for(i=0;i<cnt;i++){ |
| 514 | nchar[nptr] = ach[i]; |
| 515 | nexts[++nptr] = ast[i]; |
| 516 | } |
| 517 | nchar[nptr++] = 0; |
| 518 | # ifdef PS |
| 519 | } |
| 520 | # endif |
| 521 | if(cnt < 1){ |
| 522 | gotof[st] = -1; |
| 523 | nptr--; |
| 524 | } |
| 525 | else |
| 526 | if(nptr > ntrans) |
| 527 | error("Too many transitions %s",(ntrans==NTRANS?"\nTry using %a num":"")); |
| 528 | return; |
| 529 | } |
| 530 | # ifdef DEBUG |
| 531 | pstate(s) |
| 532 | int s; { |
| 533 | register int *p,i,j; |
| 534 | printf("State %d:\n",s); |
| 535 | p = state[s]; |
| 536 | i = *p++; |
| 537 | if(i == 0) return; |
| 538 | printf("%4d",*p++); |
| 539 | for(j = 1; j<i; j++){ |
| 540 | printf(", %4d",*p++); |
| 541 | if(j%30 == 0)putchar('\n'); |
| 542 | } |
| 543 | putchar('\n'); |
| 544 | return; |
| 545 | } |
| 546 | # endif |
| 547 | member(d,t) |
| 548 | int d; |
| 549 | char *t; { |
| 550 | register int c; |
| 551 | register char *s; |
| 552 | c = d; |
| 553 | s = t; |
| 554 | c = cindex[c]; |
| 555 | while(*s) |
| 556 | if(*s++ == c) return(1); |
| 557 | return(0); |
| 558 | } |
| 559 | # ifdef DEBUG |
| 560 | stprt(i) |
| 561 | int i; { |
| 562 | register int p, t; |
| 563 | printf("State %d:",i); |
| 564 | /* print actions, if any */ |
| 565 | t = atable[i]; |
| 566 | if(t != -1)printf(" final"); |
| 567 | putchar('\n'); |
| 568 | if(cpackflg[i] == TRUE)printf("backup char in use\n"); |
| 569 | if(sfall[i] != -1)printf("fall back state %d\n",sfall[i]); |
| 570 | p = gotof[i]; |
| 571 | if(p == -1) return; |
| 572 | printf("(%d transitions)\n",nexts[p]); |
| 573 | while(nchar[p]){ |
| 574 | charc = 0; |
| 575 | if(nexts[p+1] >= 0) |
| 576 | printf("%d\t",nexts[p+1]); |
| 577 | else printf("err\t"); |
| 578 | allprint(nchar[p++]); |
| 579 | while(nexts[p] == nexts[p+1] && nchar[p]){ |
| 580 | if(charc > LINESIZE){ |
| 581 | charc = 0; |
| 582 | printf("\n\t"); |
| 583 | } |
| 584 | allprint(nchar[p++]); |
| 585 | } |
| 586 | putchar('\n'); |
| 587 | } |
| 588 | putchar('\n'); |
| 589 | return; |
| 590 | } |
| 591 | # endif |
| 592 | acompute(s) /* compute action list = set of poss. actions */ |
| 593 | int s; { |
| 594 | register int *p, i, j; |
| 595 | int cnt, m; |
| 596 | int temp[300], k, neg[300], n; |
| 597 | k = 0; |
| 598 | n = 0; |
| 599 | p = state[s]; |
| 600 | cnt = *p++; |
| 601 | if(cnt > 300) |
| 602 | error("Too many positions for one state - acompute"); |
| 603 | for(i=0;i<cnt;i++){ |
| 604 | if(name[*p] == FINAL)temp[k++] = left[*p]; |
| 605 | else if(name[*p] == S1FINAL){temp[k++] = left[*p]; |
| 606 | if (left[*p] >NACTIONS) error("Too many right contexts"); |
| 607 | extra[left[*p]] = 1; |
| 608 | } |
| 609 | else if(name[*p] == S2FINAL)neg[n++] = left[*p]; |
| 610 | p++; |
| 611 | } |
| 612 | atable[s] = -1; |
| 613 | if(k < 1 && n < 1) return; |
| 614 | # ifdef DEBUG |
| 615 | if(debug) printf("final %d actions:",s); |
| 616 | # endif |
| 617 | /* sort action list */ |
| 618 | for(i=0; i<k; i++) |
| 619 | for(j=i+1;j<k;j++) |
| 620 | if(temp[j] < temp[i]){ |
| 621 | m = temp[j]; |
| 622 | temp[j] = temp[i]; |
| 623 | temp[i] = m; |
| 624 | } |
| 625 | /* remove dups */ |
| 626 | for(i=0;i<k-1;i++) |
| 627 | if(temp[i] == temp[i+1]) temp[i] = 0; |
| 628 | /* copy to permanent quarters */ |
| 629 | atable[s] = aptr; |
| 630 | # ifdef DEBUG |
| 631 | if(!ratfor)fprintf(fout,"/* actions for state %d */",s); |
| 632 | # endif |
| 633 | putc('\n',fout); |
| 634 | for(i=0;i<k;i++) |
| 635 | if(temp[i] != 0){ |
| 636 | ratfor ? fprintf(fout,"data vstop(%d)/%d/\n",aptr,temp[i]) : fprintf(fout,"%d,\n",temp[i]); |
| 637 | # ifdef DEBUG |
| 638 | if(debug) |
| 639 | printf("%d ",temp[i]); |
| 640 | # endif |
| 641 | aptr++; |
| 642 | } |
| 643 | for(i=0;i<n;i++){ /* copy fall back actions - all neg */ |
| 644 | ratfor ? fprintf(fout,"data vstop(%d)/%d/\n",aptr,neg[i]) : fprintf(fout,"%d,\n",neg[i]); |
| 645 | aptr++; |
| 646 | # ifdef DEBUG |
| 647 | if(debug)printf("%d ",neg[i]); |
| 648 | # endif |
| 649 | } |
| 650 | # ifdef DEBUG |
| 651 | if(debug)putchar('\n'); |
| 652 | # endif |
| 653 | ratfor ? fprintf(fout,"data vstop (%d)/0/\n",aptr) : fprintf(fout,"0,\n"); |
| 654 | aptr++; |
| 655 | return; |
| 656 | } |
| 657 | # ifdef DEBUG |
| 658 | pccl() { |
| 659 | /* print character class sets */ |
| 660 | register int i, j; |
| 661 | printf("char class intersection\n"); |
| 662 | for(i=0; i< ccount; i++){ |
| 663 | charc = 0; |
| 664 | printf("class %d:\n\t",i); |
| 665 | for(j=1;j<NCH;j++) |
| 666 | if(cindex[j] == i){ |
| 667 | allprint(j); |
| 668 | if(charc > LINESIZE){ |
| 669 | printf("\n\t"); |
| 670 | charc = 0; |
| 671 | } |
| 672 | } |
| 673 | putchar('\n'); |
| 674 | } |
| 675 | charc = 0; |
| 676 | printf("match:\n"); |
| 677 | for(i=0;i<NCH;i++){ |
| 678 | allprint(match[i]); |
| 679 | if(charc > LINESIZE){ |
| 680 | putchar('\n'); |
| 681 | charc = 0; |
| 682 | } |
| 683 | } |
| 684 | putchar('\n'); |
| 685 | return; |
| 686 | } |
| 687 | # endif |
| 688 | mkmatch(){ |
| 689 | register int i; |
| 690 | char tab[NCH]; |
| 691 | for(i=0; i<ccount; i++) |
| 692 | tab[i] = 0; |
| 693 | for(i=1;i<NCH;i++) |
| 694 | if(tab[cindex[i]] == 0) |
| 695 | tab[cindex[i]] = i; |
| 696 | /* tab[i] = principal char for new ccl i */ |
| 697 | for(i = 1; i<NCH; i++) |
| 698 | match[i] = tab[cindex[i]]; |
| 699 | return; |
| 700 | } |
| 701 | layout(){ |
| 702 | /* format and output final program's tables */ |
| 703 | register int i, j, k; |
| 704 | int top, bot, startup, omin; |
| 705 | startup = 0; |
| 706 | for(i=0; i<outsize;i++) |
| 707 | verify[i] = advance[i] = 0; |
| 708 | omin = 0; |
| 709 | yytop = 0; |
| 710 | for(i=0; i<= stnum; i++){ /* for each state */ |
| 711 | j = gotof[i]; |
| 712 | if(j == -1){ |
| 713 | stoff[i] = 0; |
| 714 | continue; |
| 715 | } |
| 716 | bot = j; |
| 717 | while(nchar[j])j++; |
| 718 | top = j - 1; |
| 719 | # if DEBUG |
| 720 | if (debug) |
| 721 | { |
| 722 | printf("State %d: (layout)\n", i); |
| 723 | for(j=bot; j<=top;j++) |
| 724 | { |
| 725 | printf(" %o", nchar[j]); |
| 726 | if (j%10==0) putchar('\n'); |
| 727 | } |
| 728 | putchar('\n'); |
| 729 | } |
| 730 | # endif |
| 731 | while(verify[omin+ZCH]) omin++; |
| 732 | startup = omin; |
| 733 | # if DEBUG |
| 734 | if (debug) printf("bot,top %d, %d startup begins %d\n",bot,top,startup); |
| 735 | # endif |
| 736 | if(chset){ |
| 737 | do { |
| 738 | ++startup; |
| 739 | if(startup > outsize - ZCH) |
| 740 | error("output table overflow"); |
| 741 | for(j = bot; j<= top; j++){ |
| 742 | k=startup+ctable[nchar[j]]; |
| 743 | if(verify[k])break; |
| 744 | } |
| 745 | } while (j <= top); |
| 746 | # if DEBUG |
| 747 | if (debug) printf(" startup will be %d\n",startup); |
| 748 | # endif |
| 749 | /* have found place */ |
| 750 | for(j = bot; j<= top; j++){ |
| 751 | k = startup + ctable[nchar[j]]; |
| 752 | if (ctable[nchar[j]]<=0) |
| 753 | printf("j %d nchar %d ctable.nch %d\n",j,nchar[j],ctable[nchar[k]]); |
| 754 | verify[k] = i+1; /* state number + 1*/ |
| 755 | advance[k] = nexts[j+1]+1; /* state number + 1*/ |
| 756 | if(yytop < k) yytop = k; |
| 757 | } |
| 758 | } |
| 759 | else { |
| 760 | do { |
| 761 | ++startup; |
| 762 | if(startup > outsize - ZCH) |
| 763 | error("output table overflow"); |
| 764 | for(j = bot; j<= top; j++){ |
| 765 | k = startup + nchar[j]; |
| 766 | if(verify[k])break; |
| 767 | } |
| 768 | } while (j <= top); |
| 769 | /* have found place */ |
| 770 | # if DEBUG |
| 771 | if (debug) printf(" startup going to be %d\n", startup); |
| 772 | # endif |
| 773 | for(j = bot; j<= top; j++){ |
| 774 | k = startup + nchar[j]; |
| 775 | verify[k] = i+1; /* state number + 1*/ |
| 776 | advance[k] = nexts[j+1]+1; /* state number + 1*/ |
| 777 | if(yytop < k) yytop = k; |
| 778 | } |
| 779 | } |
| 780 | stoff[i] = startup; |
| 781 | } |
| 782 | |
| 783 | /* stoff[i] = offset into verify, advance for trans for state i */ |
| 784 | /* put out yywork */ |
| 785 | if(ratfor){ |
| 786 | fprintf(fout, "define YYTOPVAL %d\n", yytop); |
| 787 | rprint(verify,"verif",yytop+1); |
| 788 | rprint(advance,"advan",yytop+1); |
| 789 | shiftr(stoff, stnum); |
| 790 | rprint(stoff,"stoff",stnum+1); |
| 791 | shiftr(sfall, stnum); upone(sfall, stnum+1); |
| 792 | rprint(sfall,"sfall",stnum+1); |
| 793 | bprint(extra,"extra",casecount+1); |
| 794 | bprint(match,"match",NCH); |
| 795 | shiftr(atable, stnum); |
| 796 | rprint(atable,"atable",stnum+1); |
| 797 | return; |
| 798 | } |
| 799 | fprintf(fout,"# define YYTYPE %s\n",stnum+1 > NCH ? "int" : "char"); |
| 800 | fprintf(fout,"struct yywork { YYTYPE verify, advance; } yycrank[] ={\n"); |
| 801 | for(i=0;i<=yytop;i+=4){ |
| 802 | for(j=0;j<4;j++){ |
| 803 | k = i+j; |
| 804 | if(verify[k]) |
| 805 | fprintf(fout,"%d,%d,\t",verify[k],advance[k]); |
| 806 | else |
| 807 | fprintf(fout,"0,0,\t"); |
| 808 | } |
| 809 | putc('\n',fout); |
| 810 | } |
| 811 | fprintf(fout,"0,0};\n"); |
| 812 | |
| 813 | /* put out yysvec */ |
| 814 | |
| 815 | fprintf(fout,"struct yysvf yysvec[] ={\n"); |
| 816 | fprintf(fout,"0,\t0,\t0,\n"); |
| 817 | for(i=0;i<=stnum;i++){ /* for each state */ |
| 818 | if(cpackflg[i])stoff[i] = -stoff[i]; |
| 819 | fprintf(fout,"yycrank+%d,\t",stoff[i]); |
| 820 | if(sfall[i] != -1) |
| 821 | fprintf(fout,"yysvec+%d,\t", sfall[i]+1); /* state + 1 */ |
| 822 | else fprintf(fout,"0,\t\t"); |
| 823 | if(atable[i] != -1) |
| 824 | fprintf(fout,"yyvstop+%d,",atable[i]); |
| 825 | else fprintf(fout,"0,\t"); |
| 826 | # ifdef DEBUG |
| 827 | fprintf(fout,"\t\t/* state %d */",i); |
| 828 | # endif |
| 829 | putc('\n',fout); |
| 830 | } |
| 831 | fprintf(fout,"0,\t0,\t0};\n"); |
| 832 | |
| 833 | /* put out yymatch */ |
| 834 | |
| 835 | fprintf(fout,"struct yywork *yytop = yycrank+%d;\n",yytop); |
| 836 | fprintf(fout,"struct yysvf *yybgin = yysvec+1;\n"); |
| 837 | if(optim){ |
| 838 | fprintf(fout,"char yymatch[] ={\n"); |
| 839 | if (chset==0) /* no chset, put out in normal order */ |
| 840 | { |
| 841 | for(i=0; i<NCH; i+=8){ |
| 842 | for(j=0; j<8; j++){ |
| 843 | int fbch; |
| 844 | fbch = match[i+j]; |
| 845 | if(printable(fbch) && fbch != '\'' && fbch != '\\') |
| 846 | fprintf(fout,"'%c' ,",fbch); |
| 847 | else fprintf(fout,"0%-3o,",fbch); |
| 848 | } |
| 849 | putc('\n',fout); |
| 850 | } |
| 851 | } |
| 852 | else |
| 853 | { |
| 854 | int *fbarr; |
| 855 | fbarr = myalloc(2*NCH, sizeof(*fbarr)); |
| 856 | if (fbarr==0) |
| 857 | error("No space for char table reverse",0); |
| 858 | for(i=0; i<ZCH; i++) |
| 859 | fbarr[i]=0; |
| 860 | for(i=0; i<NCH; i++) |
| 861 | fbarr[ctable[i]] = ctable[match[i]]; |
| 862 | for(i=0; i<ZCH; i+=8) |
| 863 | { |
| 864 | for(j=0; j<8; j++) |
| 865 | fprintf(fout, "0%-3o,",fbarr[i+j]); |
| 866 | putc('\n',fout); |
| 867 | } |
| 868 | cfree(fbarr, 2*NCH, 1); |
| 869 | } |
| 870 | fprintf(fout,"0};\n"); |
| 871 | } |
| 872 | /* put out yyextra */ |
| 873 | fprintf(fout,"char yyextra[] ={\n"); |
| 874 | for(i=0;i<casecount;i+=8){ |
| 875 | for(j=0;j<8;j++) |
| 876 | fprintf(fout, "%d,", i+j<NACTIONS ? |
| 877 | extra[i+j] : 0); |
| 878 | putc('\n',fout); |
| 879 | } |
| 880 | fprintf(fout,"0};\n"); |
| 881 | return; |
| 882 | } |
| 883 | rprint(a,s,n) |
| 884 | char *s; |
| 885 | int *a, n; { |
| 886 | register int i; |
| 887 | fprintf(fout,"block data\n"); |
| 888 | fprintf(fout,"common /L%s/ %s\n",s,s); |
| 889 | fprintf(fout,"define S%s %d\n",s,n); |
| 890 | fprintf(fout,"integer %s (S%s)\n",s,s); |
| 891 | for(i=1; i<=n; i++) |
| 892 | { |
| 893 | if (i%8==1) fprintf(fout, "data "); |
| 894 | fprintf(fout, "%s (%d)/%d/",s,i,a[i]); |
| 895 | fprintf(fout, (i%8 && i<n) ? ", " : "\n"); |
| 896 | } |
| 897 | fprintf(fout,"end\n"); |
| 898 | } |
| 899 | shiftr(a, n) |
| 900 | int *a; |
| 901 | { |
| 902 | int i; |
| 903 | for(i=n; i>=0; i--) |
| 904 | a[i+1]=a[i]; |
| 905 | } |
| 906 | upone(a,n) |
| 907 | int *a; |
| 908 | { |
| 909 | int i; |
| 910 | for(i=0; i<=n ; i++) |
| 911 | a[i]++; |
| 912 | } |
| 913 | bprint(a,s,n) |
| 914 | char *s, *a; |
| 915 | int n; { |
| 916 | register int i, j, k; |
| 917 | fprintf(fout,"block data\n"); |
| 918 | fprintf(fout,"common /L%s/ %s\n",s,s); |
| 919 | fprintf(fout,"define S%s %d\n",s,n); |
| 920 | fprintf(fout,"integer %s (S%s)\n",s,s); |
| 921 | for(i=1;i<n;i+=8){ |
| 922 | fprintf(fout,"data %s (%d)/%d/",s,i,a[i]); |
| 923 | for(j=1;j<8;j++){ |
| 924 | k = i+j; |
| 925 | if(k < n)fprintf(fout,", %s (%d)/%d/",s,k,a[k]); |
| 926 | } |
| 927 | putc('\n',fout); |
| 928 | } |
| 929 | fprintf(fout,"end\n"); |
| 930 | } |
| 931 | # ifdef PP |
| 932 | padd(array,n) |
| 933 | int **array; |
| 934 | int n; { |
| 935 | register int i, *j, k; |
| 936 | array[n] = nxtpos; |
| 937 | if(count == 0){ |
| 938 | *nxtpos++ = 0; |
| 939 | return; |
| 940 | } |
| 941 | for(i=tptr-1;i>=0;i--){ |
| 942 | j = array[i]; |
| 943 | if(j && *j++ == count){ |
| 944 | for(k=0;k<count;k++) |
| 945 | if(!tmpstat[*j++])break; |
| 946 | if(k >= count){ |
| 947 | array[n] = array[i]; |
| 948 | return; |
| 949 | } |
| 950 | } |
| 951 | } |
| 952 | add(array,n); |
| 953 | return; |
| 954 | } |
| 955 | # endif |