1 #ifndef lint 2 static char sccsid[] = "@(#)y1.c 4.2 (Berkeley) 05/10/89"; 3 #endif not lint 4 5 # include "dextern" 6 # include "pathnames.h" 7 8 /* variables used locally */ 9 10 /* lookahead computations */ 11 12 int tbitset; /* size of lookahead sets */ 13 struct looksets lkst [ LSETSIZE ]; 14 int nlset = 0; /* next lookahead set index */ 15 int nolook = 0; /* flag to suppress lookahead computations */ 16 struct looksets clset; /* temporary storage for lookahead computations */ 17 18 /* working set computations */ 19 20 struct wset wsets[ WSETSIZE ]; 21 struct wset *cwp; 22 23 /* state information */ 24 25 int nstate = 0; /* number of states */ 26 struct item *pstate[NSTATES+2]; /* pointers to the descriptions of the states */ 27 int tystate[NSTATES]; /* contains type information about the states */ 28 int indgo[NSTATES]; /* index to the stored goto table */ 29 int tstates[ NTERMS ]; /* states generated by terminal gotos */ 30 int ntstates[ NNONTERM ]; /* states generated by nonterminal gotos */ 31 int mstates[ NSTATES ]; /* chain of overflows of term/nonterm generation lists */ 32 33 /* storage for the actions in the parser */ 34 35 int amem[ACTSIZE]; /* action table storage */ 36 int *memp = amem; /* next free action table position */ 37 38 /* other storage areas */ 39 40 int temp1[TEMPSIZE]; /* temporary storage, indexed by terms + ntokens or states */ 41 int lineno= 1; /* current input line number */ 42 int fatfl = 1; /* if on, error is fatal */ 43 int nerrors = 0; /* number of errors */ 44 45 /* storage for information about the nonterminals */ 46 47 int **pres[NNONTERM+2]; /* vector of pointers to productions yielding each nonterminal */ 48 struct looksets *pfirst[NNONTERM+2]; /* vector of pointers to first sets for each nonterminal */ 49 int pempty[NNONTERM+1]; /* vector of nonterminals nontrivially deriving e */ 50 51 main(argc,argv) int argc; char *argv[]; { 52 53 setup(argc,argv); /* initialize and read productions */ 54 tbitset = NWORDS(ntokens); 55 cpres(); /* make table of which productions yield a given nonterminal */ 56 cempty(); /* make a table of which nonterminals can match the empty string */ 57 cpfir(); /* make a table of firsts of nonterminals */ 58 stagen(); /* generate the states */ 59 output(); /* write the states and the tables */ 60 go2out(); 61 hideprod(); 62 summary(); 63 callopt(); 64 others(); 65 exit(0); 66 } 67 68 others(){ /* put out other arrays, copy the parsers */ 69 register c, i, j; 70 71 finput = fopen( _PATH_PARSER, "r" ); 72 if( finput == NULL ) error( "cannot find parser %s", _PATH_PARSER); 73 74 warray( "yyr1", levprd, nprod ); 75 76 aryfil( temp1, nprod, 0 ); 77 PLOOP(1,i)temp1[i] = prdptr[i+1]-prdptr[i]-2; 78 warray( "yyr2", temp1, nprod ); 79 80 aryfil( temp1, nstate, -1000 ); 81 TLOOP(i){ 82 for( j=tstates[i]; j!=0; j=mstates[j] ){ 83 temp1[j] = tokset[i].value; 84 } 85 } 86 NTLOOP(i){ 87 for( j=ntstates[i]; j!=0; j=mstates[j] ){ 88 temp1[j] = -i; 89 } 90 } 91 warray( "yychk", temp1, nstate ); 92 93 warray( "yydef", defact, nstate ); 94 95 /* copy parser text */ 96 97 while( (c=getc(finput) ) != EOF ){ 98 if( c == '$' ){ 99 if( (c=getc(finput)) != 'A' ) putc( '$', ftable ); 100 else { /* copy actions */ 101 faction = fopen( ACTNAME, "r" ); 102 if( faction == NULL ) error( "cannot reopen action tempfile" ); 103 while( (c=getc(faction) ) != EOF ) putc( c, ftable ); 104 fclose(faction); 105 ZAPFILE(ACTNAME); 106 c = getc(finput); 107 } 108 } 109 putc( c, ftable ); 110 } 111 112 fclose( ftable ); 113 } 114 115 char *chcopy( p, q ) char *p, *q; { 116 /* copies string q into p, returning next free char ptr */ 117 while( *p = *q++ ) ++p; 118 return( p ); 119 } 120 121 # define ISIZE 400 122 char *writem(pp) int *pp; { /* creates output string for item pointed to by pp */ 123 int i,*p; 124 static char sarr[ISIZE]; 125 char *q; 126 127 for( p=pp; *p>0 ; ++p ) ; 128 p = prdptr[-*p]; 129 q = chcopy( sarr, nontrst[*p-NTBASE].name ); 130 q = chcopy( q, " : " ); 131 132 for(;;){ 133 *q++ = ++p==pp ? '_' : ' '; 134 *q = '\0'; 135 if((i = *p) <= 0) break; 136 q = chcopy( q, symnam(i) ); 137 if( q> &sarr[ISIZE-30] ) error( "item too big" ); 138 } 139 140 if( (i = *pp) < 0 ){ /* an item calling for a reduction */ 141 q = chcopy( q, " (" ); 142 sprintf( q, "%d)", -i ); 143 } 144 145 return( sarr ); 146 } 147 148 char *symnam(i){ /* return a pointer to the name of symbol i */ 149 char *cp; 150 151 cp = (i>=NTBASE) ? nontrst[i-NTBASE].name : tokset[i].name ; 152 if( *cp == ' ' ) ++cp; 153 return( cp ); 154 } 155 156 struct wset *zzcwp = wsets; 157 int zzgoent = 0; 158 int zzgobest = 0; 159 int zzacent = 0; 160 int zzexcp = 0; 161 int zzclose = 0; 162 int zzsrconf = 0; 163 int * zzmemsz = mem0; 164 int zzrrconf = 0; 165 166 summary(){ /* output the summary on the tty */ 167 168 if( foutput!=NULL ){ 169 fprintf( foutput, "\n%d/%d terminals, %d/%d nonterminals\n", ntokens, NTERMS, 170 nnonter, NNONTERM ); 171 fprintf( foutput, "%d/%d grammar rules, %d/%d states\n", nprod, NPROD, nstate, NSTATES ); 172 fprintf( foutput, "%d shift/reduce, %d reduce/reduce conflicts reported\n", zzsrconf, zzrrconf ); 173 fprintf( foutput, "%d/%d working sets used\n", zzcwp-wsets, WSETSIZE ); 174 fprintf( foutput, "memory: states,etc. %d/%d, parser %d/%d\n", zzmemsz-mem0, MEMSIZE, 175 memp-amem, ACTSIZE ); 176 fprintf( foutput, "%d/%d distinct lookahead sets\n", nlset, LSETSIZE ); 177 fprintf( foutput, "%d extra closures\n", zzclose - 2*nstate ); 178 fprintf( foutput, "%d shift entries, %d exceptions\n", zzacent, zzexcp ); 179 fprintf( foutput, "%d goto entries\n", zzgoent ); 180 fprintf( foutput, "%d entries saved by goto default\n", zzgobest ); 181 } 182 if( zzsrconf!=0 || zzrrconf!=0 ){ 183 fprintf( stdout,"\nconflicts: "); 184 if( zzsrconf )fprintf( stdout, "%d shift/reduce" , zzsrconf ); 185 if( zzsrconf && zzrrconf )fprintf( stdout, ", " ); 186 if( zzrrconf )fprintf( stdout, "%d reduce/reduce" , zzrrconf ); 187 fprintf( stdout, "\n" ); 188 } 189 190 fclose( ftemp ); 191 if( fdefine != NULL ) fclose( fdefine ); 192 } 193 194 /* VARARGS1 */ 195 error(s,a1) char *s; { /* write out error comment */ 196 197 ++nerrors; 198 fprintf( stderr, "\n fatal error: "); 199 fprintf( stderr, s,a1); 200 fprintf( stderr, ", line %d\n", lineno ); 201 if( !fatfl ) return; 202 summary(); 203 exit(1); 204 } 205 206 aryfil( v, n, c ) int *v,n,c; { /* set elements 0 through n-1 to c */ 207 int i; 208 for( i=0; i<n; ++i ) v[i] = c; 209 } 210 211 setunion( a, b ) register *a, *b; { 212 /* set a to the union of a and b */ 213 /* return 1 if b is not a subset of a, 0 otherwise */ 214 register i, x, sub; 215 216 sub = 0; 217 SETLOOP(i){ 218 *a = (x = *a)|*b++; 219 if( *a++ != x ) sub = 1; 220 } 221 return( sub ); 222 } 223 224 prlook( p ) struct looksets *p;{ 225 register j, *pp; 226 pp = p->lset; 227 if( pp == 0 ) fprintf( foutput, "\tNULL"); 228 else { 229 fprintf( foutput, " { " ); 230 TLOOP(j) { 231 if( BIT(pp,j) ) fprintf( foutput, "%s ", symnam(j) ); 232 } 233 fprintf( foutput, "}" ); 234 } 235 } 236 237 cpres(){ /* compute an array with the beginnings of productions yielding given nonterminals 238 The array pres points to these lists */ 239 /* the array pyield has the lists: the total size is only NPROD+1 */ 240 register **pmem; 241 register c, j, i; 242 static int * pyield[NPROD]; 243 244 pmem = pyield; 245 246 NTLOOP(i){ 247 c = i+NTBASE; 248 pres[i] = pmem; 249 fatfl = 0; /* make undefined symbols nonfatal */ 250 PLOOP(0,j){ 251 if (*prdptr[j] == c) *pmem++ = prdptr[j]+1; 252 } 253 if(pres[i] == pmem){ 254 error("nonterminal %s not defined!", nontrst[i].name); 255 } 256 } 257 pres[i] = pmem; 258 fatfl = 1; 259 if( nerrors ){ 260 summary(); 261 exit(1); 262 } 263 if( pmem != &pyield[nprod] ) error( "internal Yacc error: pyield %d", pmem-&pyield[nprod] ); 264 } 265 266 int indebug = 0; 267 cpfir() { 268 /* compute an array with the first of nonterminals */ 269 register *p, **s, i, **t, ch, changes; 270 271 zzcwp = &wsets[nnonter]; 272 NTLOOP(i){ 273 aryfil( wsets[i].ws.lset, tbitset, 0 ); 274 t = pres[i+1]; 275 for( s=pres[i]; s<t; ++s ){ /* initially fill the sets */ 276 for( p = *s; (ch = *p) > 0 ; ++p ) { 277 if( ch < NTBASE ) { 278 SETBIT( wsets[i].ws.lset, ch ); 279 break; 280 } 281 else if( !pempty[ch-NTBASE] ) break; 282 } 283 } 284 } 285 286 /* now, reflect transitivity */ 287 288 changes = 1; 289 while( changes ){ 290 changes = 0; 291 NTLOOP(i){ 292 t = pres[i+1]; 293 for( s=pres[i]; s<t; ++s ){ 294 for( p = *s; ( ch = (*p-NTBASE) ) >= 0; ++p ) { 295 changes |= setunion( wsets[i].ws.lset, wsets[ch].ws.lset ); 296 if( !pempty[ch] ) break; 297 } 298 } 299 } 300 } 301 302 NTLOOP(i) pfirst[i] = flset( &wsets[i].ws ); 303 if( !indebug ) return; 304 if( (foutput!=NULL) ){ 305 NTLOOP(i) { 306 fprintf( foutput, "\n%s: ", nontrst[i].name ); 307 prlook( pfirst[i] ); 308 fprintf( foutput, " %d\n", pempty[i] ); 309 } 310 } 311 } 312 313 state(c){ /* sorts last state,and sees if it equals earlier ones. returns state number */ 314 int size1,size2; 315 register i; 316 struct item *p1, *p2, *k, *l, *q1, *q2; 317 p1 = pstate[nstate]; 318 p2 = pstate[nstate+1]; 319 if(p1==p2) return(0); /* null state */ 320 /* sort the items */ 321 for(k=p2-1;k>p1;k--) { /* make k the biggest */ 322 for(l=k-1;l>=p1;--l)if( l->pitem > k->pitem ){ 323 int *s; 324 struct looksets *ss; 325 s = k->pitem; 326 k->pitem = l->pitem; 327 l->pitem = s; 328 ss = k->look; 329 k->look = l->look; 330 l->look = ss; 331 } 332 } 333 size1 = p2 - p1; /* size of state */ 334 335 for( i= (c>=NTBASE)?ntstates[c-NTBASE]:tstates[c]; i != 0; i = mstates[i] ) { 336 /* get ith state */ 337 q1 = pstate[i]; 338 q2 = pstate[i+1]; 339 size2 = q2 - q1; 340 if (size1 != size2) continue; 341 k=p1; 342 for(l=q1;l<q2;l++) { 343 if( l->pitem != k->pitem ) break; 344 ++k; 345 } 346 if (l != q2) continue; 347 /* found it */ 348 pstate[nstate+1] = pstate[nstate]; /* delete last state */ 349 /* fix up lookaheads */ 350 if( nolook ) return(i); 351 for( l=q1,k=p1; l<q2; ++l,++k ){ 352 int s; 353 SETLOOP(s) clset.lset[s] = l->look->lset[s]; 354 if( setunion( clset.lset, k->look->lset ) ) { 355 tystate[i] = MUSTDO; 356 /* register the new set */ 357 l->look = flset( &clset ); 358 } 359 } 360 return (i); 361 } 362 /* state is new */ 363 if( nolook ) error( "yacc state/nolook error" ); 364 pstate[nstate+2] = p2; 365 if(nstate+1 >= NSTATES) error("too many states" ); 366 if( c >= NTBASE ){ 367 mstates[ nstate ] = ntstates[ c-NTBASE ]; 368 ntstates[ c-NTBASE ] = nstate; 369 } 370 else { 371 mstates[ nstate ] = tstates[ c ]; 372 tstates[ c ] = nstate; 373 } 374 tystate[nstate]=MUSTDO; 375 return(nstate++); 376 } 377 378 int pidebug = 0; /* debugging flag for putitem */ 379 putitem( ptr, lptr ) int *ptr; struct looksets *lptr; { 380 register struct item *j; 381 382 if( pidebug && (foutput!=NULL) ) { 383 fprintf( foutput, "putitem(%s), state %d\n", writem(ptr), nstate ); 384 } 385 j = pstate[nstate+1]; 386 j->pitem = ptr; 387 if( !nolook ) j->look = flset( lptr ); 388 pstate[nstate+1] = ++j; 389 if( (int *)j > zzmemsz ){ 390 zzmemsz = (int *)j; 391 if( zzmemsz >= &mem0[MEMSIZE] ) error( "out of state space" ); 392 } 393 } 394 395 cempty(){ /* mark nonterminals which derive the empty string */ 396 /* also, look for nonterminals which don't derive any token strings */ 397 398 # define EMPTY 1 399 # define WHOKNOWS 0 400 # define OK 1 401 402 register i, *p; 403 404 /* first, use the array pempty to detect productions that can never be reduced */ 405 /* set pempty to WHONOWS */ 406 aryfil( pempty, nnonter+1, WHOKNOWS ); 407 408 /* now, look at productions, marking nonterminals which derive something */ 409 410 more: 411 PLOOP(0,i){ 412 if( pempty[ *prdptr[i] - NTBASE ] ) continue; 413 for( p=prdptr[i]+1; *p>=0; ++p ){ 414 if( *p>=NTBASE && pempty[ *p-NTBASE ] == WHOKNOWS ) break; 415 } 416 if( *p < 0 ){ /* production can be derived */ 417 pempty[ *prdptr[i]-NTBASE ] = OK; 418 goto more; 419 } 420 } 421 422 /* now, look at the nonterminals, to see if they are all OK */ 423 424 NTLOOP(i){ 425 /* the added production rises or falls as the start symbol ... */ 426 if( i == 0 ) continue; 427 if( pempty[ i ] != OK ) { 428 fatfl = 0; 429 error( "nonterminal %s never derives any token string", nontrst[i].name ); 430 } 431 } 432 433 if( nerrors ){ 434 summary(); 435 exit(1); 436 } 437 438 /* now, compute the pempty array, to see which nonterminals derive the empty string */ 439 440 /* set pempty to WHOKNOWS */ 441 442 aryfil( pempty, nnonter+1, WHOKNOWS ); 443 444 /* loop as long as we keep finding empty nonterminals */ 445 446 again: 447 PLOOP(1,i){ 448 if( pempty[ *prdptr[i]-NTBASE ]==WHOKNOWS ){ /* not known to be empty */ 449 for( p=prdptr[i]+1; *p>=NTBASE && pempty[*p-NTBASE]==EMPTY ; ++p ) ; 450 if( *p < 0 ){ /* we have a nontrivially empty nonterminal */ 451 pempty[*prdptr[i]-NTBASE] = EMPTY; 452 goto again; /* got one ... try for another */ 453 } 454 } 455 } 456 457 } 458 459 int gsdebug = 0; 460 stagen(){ /* generate the states */ 461 462 int i, j; 463 register c; 464 register struct wset *p, *q; 465 466 /* initialize */ 467 468 nstate = 0; 469 /* THIS IS FUNNY from the standpoint of portability */ 470 /* it represents the magic moment when the mem0 array, which has 471 /* been holding the productions, starts to hold item pointers, of a 472 /* different type... */ 473 /* someday, alloc should be used to allocate all this stuff... for now, we 474 /* accept that if pointers don't fit in integers, there is a problem... */ 475 476 pstate[0] = pstate[1] = (struct item *)mem; 477 aryfil( clset.lset, tbitset, 0 ); 478 putitem( prdptr[0]+1, &clset ); 479 tystate[0] = MUSTDO; 480 nstate = 1; 481 pstate[2] = pstate[1]; 482 483 aryfil( amem, ACTSIZE, 0 ); 484 485 /* now, the main state generation loop */ 486 487 more: 488 SLOOP(i){ 489 if( tystate[i] != MUSTDO ) continue; 490 tystate[i] = DONE; 491 aryfil( temp1, nnonter+1, 0 ); 492 /* take state i, close it, and do gotos */ 493 closure(i); 494 WSLOOP(wsets,p){ /* generate goto's */ 495 if( p->flag ) continue; 496 p->flag = 1; 497 c = *(p->pitem); 498 if( c <= 1 ) { 499 if( pstate[i+1]-pstate[i] <= p-wsets ) tystate[i] = MUSTLOOKAHEAD; 500 continue; 501 } 502 /* do a goto on c */ 503 WSLOOP(p,q){ 504 if( c == *(q->pitem) ){ /* this item contributes to the goto */ 505 putitem( q->pitem + 1, &q->ws ); 506 q->flag = 1; 507 } 508 } 509 if( c < NTBASE ) { 510 state(c); /* register new state */ 511 } 512 else { 513 temp1[c-NTBASE] = state(c); 514 } 515 } 516 if( gsdebug && (foutput!=NULL) ){ 517 fprintf( foutput, "%d: ", i ); 518 NTLOOP(j) { 519 if( temp1[j] ) fprintf( foutput, "%s %d, ", nontrst[j].name, temp1[j] ); 520 } 521 fprintf( foutput, "\n"); 522 } 523 indgo[i] = apack( &temp1[1], nnonter-1 ) - 1; 524 goto more; /* we have done one goto; do some more */ 525 } 526 /* no more to do... stop */ 527 } 528 529 int cldebug = 0; /* debugging flag for closure */ 530 closure(i){ /* generate the closure of state i */ 531 532 int c, ch, work, k; 533 register struct wset *u, *v; 534 int *pi; 535 int **s, **t; 536 struct item *q; 537 register struct item *p; 538 539 ++zzclose; 540 541 /* first, copy kernel of state i to wsets */ 542 543 cwp = wsets; 544 ITMLOOP(i,p,q){ 545 cwp->pitem = p->pitem; 546 cwp->flag = 1; /* this item must get closed */ 547 SETLOOP(k) cwp->ws.lset[k] = p->look->lset[k]; 548 WSBUMP(cwp); 549 } 550 551 /* now, go through the loop, closing each item */ 552 553 work = 1; 554 while( work ){ 555 work = 0; 556 WSLOOP(wsets,u){ 557 558 if( u->flag == 0 ) continue; 559 c = *(u->pitem); /* dot is before c */ 560 561 if( c < NTBASE ){ 562 u->flag = 0; 563 continue; /* only interesting case is where . is before nonterminal */ 564 } 565 566 /* compute the lookahead */ 567 aryfil( clset.lset, tbitset, 0 ); 568 569 /* find items involving c */ 570 571 WSLOOP(u,v){ 572 if( v->flag == 1 && *(pi=v->pitem) == c ){ 573 v->flag = 0; 574 if( nolook ) continue; 575 while( (ch= *++pi)>0 ){ 576 if( ch < NTBASE ){ /* terminal symbol */ 577 SETBIT( clset.lset, ch ); 578 break; 579 } 580 /* nonterminal symbol */ 581 setunion( clset.lset, pfirst[ch-NTBASE]->lset ); 582 if( !pempty[ch-NTBASE] ) break; 583 } 584 if( ch<=0 ) setunion( clset.lset, v->ws.lset ); 585 } 586 } 587 588 /* now loop over productions derived from c */ 589 590 c -= NTBASE; /* c is now nonterminal number */ 591 592 t = pres[c+1]; 593 for( s=pres[c]; s<t; ++s ){ 594 /* put these items into the closure */ 595 WSLOOP(wsets,v){ /* is the item there */ 596 if( v->pitem == *s ){ /* yes, it is there */ 597 if( nolook ) goto nexts; 598 if( setunion( v->ws.lset, clset.lset ) ) v->flag = work = 1; 599 goto nexts; 600 } 601 } 602 603 /* not there; make a new entry */ 604 if( cwp-wsets+1 >= WSETSIZE ) error( "working set overflow" ); 605 cwp->pitem = *s; 606 cwp->flag = 1; 607 if( !nolook ){ 608 work = 1; 609 SETLOOP(k) cwp->ws.lset[k] = clset.lset[k]; 610 } 611 WSBUMP(cwp); 612 613 nexts: ; 614 } 615 616 } 617 } 618 619 /* have computed closure; flags are reset; return */ 620 621 if( cwp > zzcwp ) zzcwp = cwp; 622 if( cldebug && (foutput!=NULL) ){ 623 fprintf( foutput, "\nState %d, nolook = %d\n", i, nolook ); 624 WSLOOP(wsets,u){ 625 if( u->flag ) fprintf( foutput, "flag set!\n"); 626 u->flag = 0; 627 fprintf( foutput, "\t%s", writem(u->pitem)); 628 prlook( &u->ws ); 629 fprintf( foutput, "\n" ); 630 } 631 } 632 } 633 634 struct looksets *flset( p ) struct looksets *p; { 635 /* decide if the lookahead set pointed to by p is known */ 636 /* return pointer to a perminent location for the set */ 637 638 register struct looksets *q; 639 int j, *w; 640 register *u, *v; 641 642 for( q = &lkst[nlset]; q-- > lkst; ){ 643 u = p->lset; 644 v = q->lset; 645 w = & v[tbitset]; 646 while( v<w) if( *u++ != *v++ ) goto more; 647 /* we have matched */ 648 return( q ); 649 more: ; 650 } 651 /* add a new one */ 652 q = &lkst[nlset++]; 653 if( nlset >= LSETSIZE )error("too many lookahead sets" ); 654 SETLOOP(j){ 655 q->lset[j] = p->lset[j]; 656 } 657 return( q ); 658 } 659