![[BACK]](/cvsweb/icons/back.gif){kind=icon}
Return to y1.c CVS log ![[TXT]](/cvsweb/icons/text.gif){kind=icon}
![[DIR]](/cvsweb/icons/dir.gif){kind=icon}
Up to [MW Coherent from dump] / coherent / d / bin / yacc|
Return to y1.c CVS log | Up to [MW Coherent from dump] / coherent / d / bin / yacc |
1.1 ! root 1: /* ! 2: * LALR-1 parser generator ! 3: * ! 4: * the comments previously here have been suppressed since they were ! 5: * boring ! 6: */ ! 7: #include "yacc.h" ! 8: ! 9: main(argc,argv) ! 10: char *argv[]; ! 11: { ! 12: options(argc,argv); ! 13: getfiles(); ! 14: readrules(); ! 15: ntprod(); ! 16: ntderive(); ! 17: listgram(); ! 18: if( nerrors ) ! 19: cleanup(1); ! 20: ntempty(); ! 21: if( nerrors ) ! 22: cleanup(1); ! 23: genstates(); ! 24: genslist(); ! 25: sttrans(); ! 26: genlook(); ! 27: go2out(); ! 28: paout(); ! 29: callopt(); ! 30: cleanup(0); ! 31: } ! 32: ! 33: getfiles() ! 34: { ! 35: if( gramy==NULL ) ! 36: usage(); ! 37: if( strcmp(gramy,"-")==0 ) ! 38: defin = stdin; ! 39: else ! 40: if( (defin = fopen(gramy,"r")) == NULL ) ! 41: yyerror(!FATAL, "cannot open grammar file %s", gramy); ! 42: mktemp(acttmp); ! 43: mktemp(opttmp); ! 44: if( (actout = fopen(acttmp,"w")) == NULL ) ! 45: yyerror(!FATAL, "cannot create action temp file %s", acttmp); ! 46: if( (tabout = fopen(ytabc,"w")) == NULL ) ! 47: yyerror(!FATAL, "cannot create output file %s", ytabc); ! 48: if( (fhdr = fopen(ytabh, "w")) == NULL ) ! 49: yyerror(!FATAL, "cannot create %s", ytabh); ! 50: if( verbose ) ! 51: if( (listout = fopen(youtput,"w")) == NULL ) ! 52: yyerror(NLNO, "cannot open listing file %s", youtput); ! 53: if ((optout = fopen(opttmp, "wb")) == NULL ! 54: || (optout = freopen(opttmp, "rwb", optout)) == NULL) ! 55: yyerror(NLNO, "open error temp %s", opttmp); ! 56: if( nerrors ) ! 57: cleanup(2); ! 58: } ! 59: ! 60: rewopt() ! 61: { ! 62: fseek(optout, 0L, 0); ! 63: } ! 64: ! 65: /* ! 66: * for each non-terminal, generate a list of productions which the ! 67: * the non terminal derives ! 68: */ ! 69: ntprod() ! 70: { ! 71: register i; ! 72: register struct sym *sp; ! 73: ! 74: /* first run down the production table, counting references to ! 75: all the non terminals. */ ! 76: for(i=0; i<nnonterm; i++) ! 77: ntrmptr[i]->s_nprods = 0; ! 78: for(i=0; i<nprod; i++) ! 79: ntrmptr[-prdptr[i]->p_left-NTBASE]->s_nprods++; ! 80: for(i=0; i<nnonterm; i++) ! 81: if( ntrmptr[i]->s_nprods==0 ) ! 82: yyerror(NLNO|!FATAL, "non terminal %s not defined", ! 83: ntrmptr[i]->s_name); ! 84: if( nerrors ) ! 85: cleanup(1); ! 86: /* now allocate list pointers for each non-terminal */ ! 87: for(i=0; i<nnonterm; i++) { ! 88: sp = ntrmptr[i]; ! 89: sp->s_prods = (struct prod **)yalloc(sp->s_nprods, sizeof *sp->s_prods); ! 90: sp->s_nprods = 0; /* il sera recharge a la suite */ ! 91: } ! 92: /* finally, run down the production table again filling in the ! 93: list pointers for the corresponding non terminal */ ! 94: for(i=0; i<nprod; i++) { ! 95: sp = ntrmptr[ -prdptr[i]->p_left-NTBASE ]; ! 96: sp->s_prods[sp->s_nprods++] = prdptr[i]; ! 97: } ! 98: } ! 99: ! 100: /* ! 101: * assure that all non-terminals generate a token string ! 102: * algorithm: ! 103: * assume a priori that no non-terminal generates a token string ! 104: * if a non terminal contains a production which consists only ! 105: * of non-terminals generating a token string, and terminals ! 106: * then it generates a token string ! 107: * cycle on this until no new non terminals are found ! 108: * - a similar procedure applies for finding out which non terminals ! 109: * generate the empty string ! 110: */ ! 111: ! 112: ntderive() ! 113: { ! 114: register i, j; ! 115: register struct sym *sp; ! 116: register struct prod *pp; ! 117: int *ip; ! 118: int changed; ! 119: ! 120: for(i=0; i<nnonterm; i++) ! 121: ntrmptr[i]->s_flags &= ~DERIV; ! 122: do { ! 123: changed = 0; ! 124: for(i=0; i<nnonterm; i++) { ! 125: sp = ntrmptr[i]; ! 126: if( sp->s_flags&DERIV ) ! 127: continue; ! 128: for(j=0; j<sp->s_nprods; j++) { ! 129: pp = sp->s_prods[j]; ! 130: for(ip=pp->p_right; *ip!=-1; ip++) ! 131: if( *ip>=NTBASE && ! 132: (ntrmptr[*ip-NTBASE]->s_flags&DERIV)==0 ) ! 133: break; ! 134: if( *ip == -1 ) { ! 135: sp->s_flags |= DERIV; ! 136: changed++; ! 137: break; ! 138: } ! 139: } ! 140: } ! 141: } while( changed ); ! 142: for(i=0; i<nnonterm; i++) ! 143: if( (ntrmptr[i]->s_flags&DERIV)==0 ) ! 144: yyerror(NLNO|!FATAL, "nonterminal %s derives no token string", ! 145: ntrmptr[i]->s_name); ! 146: if( nerrors ) ! 147: cleanup(1); ! 148: } ! 149: ! 150: /* ! 151: * find out which non-terminals derive the empty string ! 152: * algorithm is simple ! 153: * if the non-terminal has a production deriving the empty string ! 154: * it derives the empty string trivially ! 155: * otherwise if it consists only of productions which can derive the ! 156: * empty string, then it derives the empty string as well ! 157: */ ! 158: ! 159: ntempty() ! 160: { ! 161: register *kp; ! 162: register struct prod **ppp; ! 163: register struct sym *sp; ! 164: int i, changed; ! 165: ! 166: for(i=0; i<nnonterm; i++) ! 167: ntrmptr[i]->s_flags &= ~DERIV; ! 168: do { ! 169: changed = 0; ! 170: for(i=0; i<nnonterm; i++) { ! 171: sp = ntrmptr[i]; ! 172: if( sp->s_flags&DERIV ) ! 173: continue; ! 174: for(ppp=sp->s_prods; ppp<&sp->s_prods[sp->s_nprods]; ppp++) { ! 175: for(kp = (*ppp)->p_right; *kp!=-1; kp++ ) ! 176: if( *kp<NTBASE || ! 177: (ntrmptr[*kp-NTBASE]->s_flags&DERIV)==0 ) ! 178: break; ! 179: if( *kp==-1 ) { ! 180: sp->s_flags |= DERIV; ! 181: changed++; ! 182: break; ! 183: } ! 184: } ! 185: } ! 186: } while( changed ); ! 187: } ! 188: ! 189: /* some useful local variables */ ! 190: static newgen; /* communication between genstates and install */ ! 191: static char *ntp; /* buffer for use by chklhs */ ! 192: ! 193: genstates() ! 194: { ! 195: extern struct sitem *nititem; ! 196: register k, sno; ! 197: int i; ! 198: struct tgo tgo; ! 199: struct ntgo ntgo; ! 200: ! 201: /* initialize the list of states associated with each nt to empty */ ! 202: if( verbose ) ! 203: fprintf(listout, "\nAutomaton state description:\n\n"); ! 204: for(i=0; i<nnonterm; i++) ! 205: ntrmptr[i]->s_nstates = 0; ! 206: ntp = yalloc(nnonterm, sizeof *ntp); /* array used by "install" */ ! 207: nititem->i_nitems = 1; ! 208: nititem->i_items[0] = prdptr[0]->p_right; ! 209: closure(); ! 210: install(); ! 211: i = 0; ! 212: do { ! 213: newgen = 0; /* newgen is flagged by the install routine */ ! 214: for(; i<nstates; i++) { ! 215: fwrite(&i, sizeof i, 1, optout); /* sync number */ ! 216: states[i].s_tgo = 0; ! 217: for(k=0; k<nterm; k++) ! 218: if( (sno = go2(items[i], k)) >= 0 ) { ! 219: states[i].s_tgo++; ! 220: tgo.tg_st = sno; ! 221: tgo.tg_trm = k; ! 222: fwrite(&tgo, sizeof tgo, 1, optout); ! 223: } ! 224: states[i].s_ntgo = 0; ! 225: for(k=0; k<nnonterm; k++) ! 226: if( (sno = go2(items[i], k+NTBASE)) >= 0 ) { ! 227: states[i].s_ntgo++; ! 228: ntgo.ng_st = sno; ! 229: ntgo.ng_nt = k+NTBASE; ! 230: ntgo.ng_rel = NULL; /* MWC DSC */ ! 231: fwrite(&ntgo, sizeof ntgo, 1, optout); ! 232: } ! 233: states[i].s_nred = 0; ! 234: for(k=0; k<items[i]->i_nitems; k++) ! 235: if( *(items[i]->i_items[k]) == -1 ) ! 236: states[i].s_nred++; ! 237: states[i].s_tgos = states[i].s_ntgos = ! 238: states[i].s_reds = NULL; /* MWC DSC */ ! 239: } ! 240: } while( newgen ); ! 241: free(ntp); ! 242: } ! 243: ! 244: /* ! 245: * generate the closure of a state (found in global variable `nititem' ! 246: * Algorithm: ! 247: * - look at every non terminal's after every '.' item pointer ! 248: * - add all the productions associated with this non-terminal ! 249: * to the state (the '.' being at the beginning of the rhs) unless ! 250: * they are already there. It suffices to test if one of them is ! 251: * already there, since productions are added to the closure according ! 252: * according to their lhs ! 253: * repeat this procedure until no new items are added. ! 254: * ! 255: * "It can be shown that (this procedure) computes exactly the sets ! 256: * of items that are valid for gamma X [Aho and Ullmann 1972]" ! 257: */ ! 258: ! 259: closure() ! 260: { ! 261: register j, **ipp; ! 262: register struct prod **ppp; ! 263: struct sitem *itp; ! 264: struct sym *sp; ! 265: int i, changed, nt; ! 266: ! 267: itp = nititem; ! 268: for(i=0; i<nnonterm; i++) ! 269: ntrmptr[i]->s_flags &= ~CPRES; ! 270: for(i=0; i<itp->i_nitems; i++) ! 271: /* kludge: requires p.left & p.rights contigouuous */ ! 272: if( (nt = *(itp->i_items[i]-1)) < 0 ) /* ARE THEY???? */ ! 273: ntrmptr[-nt-NTBASE]->s_flags |= CPRES; ! 274: do { ! 275: changed = 0; ! 276: for(i=0; i<itp->i_nitems; i++) { ! 277: nt = *(itp->i_items[i]); ! 278: if( nt>=NTBASE && ((sp = ntrmptr[nt-NTBASE])->s_flags ! 279: &CPRES)==0 ) { ! 280: sp->s_flags |= CPRES; ! 281: changed = 1; ! 282: ppp = sp->s_prods; ! 283: ipp = &itp->i_items[itp->i_nitems]; ! 284: itp->i_nitems += j = sp->s_nprods; ! 285: bounded(itp->i_nitems, MAXITEM, "items in state"); ! 286: do ! 287: *ipp++ = (*ppp++)->p_right; ! 288: while( --j ); ! 289: } ! 290: } ! 291: } while( changed ); ! 292: } ! 293: ! 294: /* ! 295: * add the state in `nititem' to the collection of sets of accessible ! 296: * items, returning the state pointer ! 297: * the real work is concerned with finding out whether the set is there ! 298: * already or not ! 299: * we sort the items in nititem, compare with every set in "items", ! 300: * and return the old state pointer if its there already ! 301: */ ! 302: install() ! 303: { ! 304: register n, **ipp1, **ipp2; ! 305: struct sitem *itp, *itp1; ! 306: int i; ! 307: ! 308: itp = nititem; ! 309: bubble(itp->i_items, itp->i_nitems); ! 310: for(i=0; i<nstates; i++) { ! 311: itp1 = items[i]; ! 312: if( (n = itp->i_nitems) != itp1->i_nitems ) ! 313: continue; ! 314: ipp1 = itp->i_items; ! 315: ipp2 = itp1->i_items; ! 316: do ! 317: if( *ipp1++ != *ipp2++ ) ! 318: break; ! 319: while( --n ); ! 320: if( n==0 ) ! 321: break; ! 322: } ! 323: if( i==nstates ) { ! 324: bounded(nstates,maxstates,"states"); ! 325: chklhs(); ! 326: itp1 = (struct sitem *)yalloc(1, sizeof *itp1 + itp->i_nitems * ! 327: sizeof itp->i_items[0]); ! 328: copyb(itp, itp1, sizeof *itp1 + itp->i_nitems * ! 329: sizeof itp->i_items[0]); ! 330: newgen = 1; ! 331: items[nstates] = itp1; ! 332: if( verbose ) ! 333: prstate(nstates, listout); ! 334: nstates++; ! 335: } ! 336: return( i ); ! 337: } ! 338: ! 339: go2(itp, tk) ! 340: struct sitem *itp; ! 341: int tk; ! 342: { ! 343: register **ipp1, **ipp, n; ! 344: ! 345: nititem->i_nitems = 0; ! 346: ipp1 = nititem->i_items; ! 347: ipp = itp->i_items; ! 348: n = itp->i_nitems; ! 349: do { ! 350: if( **ipp == tk ) { ! 351: nititem->i_nitems++; ! 352: *ipp1++ = *ipp+1; ! 353: } ! 354: ipp++; ! 355: } while( --n ); ! 356: if( nititem->i_nitems==0 ) ! 357: return( -1 ); ! 358: else { ! 359: closure(); ! 360: return( install() ); ! 361: } ! 362: } ! 363: ! 364: chklhs() ! 365: { ! 366: register n, **ipp; ! 367: register char *cp; ! 368: int nt; ! 369: ! 370: n = nnonterm; ! 371: cp = ntp; ! 372: do *cp++ = 0; while( --n ); ! 373: ipp = nititem->i_items; ! 374: n = nititem->i_nitems; ! 375: cp = ntp; ! 376: do ! 377: if( (nt = (*ipp++) [-1]) < 0 ) ! 378: cp[ -nt-NTBASE ] = 1; ! 379: while( --n ); ! 380: for(n=0; n<nnonterm; n++) ! 381: if( cp[n] ) ! 382: ntrmptr[n]->s_nstates++; ! 383: } ! 384: ! 385: /* ! 386: * for each nonterminal generate a list of items ! 387: * containing items with all of the rhs of a production ! 388: * whose lhs is the non-terminal after the '.' ! 389: */ ! 390: genslist() ! 391: { ! 392: register struct sym *sp; ! 393: register i, j; ! 394: int *ip; ! 395: int *stp; ! 396: ! 397: for(i=j=0; i<nnonterm; i++) ! 398: j += ntrmptr[i]->s_nstates; ! 399: stp = (int *)yalloc(j, sizeof *stp); ! 400: for(i=0; i<nnonterm; i++) { ! 401: sp = ntrmptr[i]; ! 402: sp->s_states = stp; ! 403: stp += sp->s_nstates; ! 404: sp->s_nstates = 0; /* a recharcher dans le boucle suivant */ ! 405: } ! 406: for(i=0; i<nnonterm; i++) { ! 407: sp = ntrmptr[i]; ! 408: ip = sp->s_prods[0]->p_right; /* pick an item, any item */ ! 409: for(j=0; j<nstates; j++) ! 410: if( pitem(ip, items[j]) ) ! 411: sp->s_states[sp->s_nstates++] = j; ! 412: } ! 413: } ! 414: ! 415: /* binary search for an item in a state */ ! 416: ! 417: pitem(ip,itp) ! 418: int *ip; ! 419: register struct sitem *itp; ! 420: { ! 421: register int *el, nb; ! 422: int ub, lb; ! 423: ! 424: lb = 0; ! 425: ub = itp->i_nitems-1; ! 426: do { ! 427: nb = (ub+lb) / 2; ! 428: if( (el = itp->i_items[nb]) < ip ) ! 429: lb = nb+1; ! 430: else if( el > ip ) ! 431: ub = nb-1; ! 432: else ! 433: return(1); ! 434: } while( lb<=ub ); ! 435: return(0); ! 436: } ! 437: ! 438: /* ! 439: * linear insertion sort really. ! 440: * the decision not to use bubbbbbbbbbbbble sort is thanks to Randall ! 441: * and to his cs240b notes ! 442: * (p.s. -- i hate sorting) ! 443: */ ! 444: ! 445: bubble(ipp,n) ! 446: register **ipp; ! 447: int n; ! 448: { ! 449: register **min, **jpp; ! 450: int m, *t; /* MWC DSC */ ! 451: ! 452: do { ! 453: m = n; ! 454: min = jpp = ipp; ! 455: do { ! 456: if( *jpp < *min ) ! 457: min = jpp; ! 458: jpp++; ! 459: } while( --m ); ! 460: t = *min; ! 461: *min = *ipp; ! 462: *ipp++ = t; ! 463: } while( --n ); ! 464: } ! 465: ! 466: copyb(sp,dp,n) ! 467: register char *sp, *dp; ! 468: register n; ! 469: { ! 470: do ! 471: *dp++ = *sp++; ! 472: while( --n ); ! 473: } ! 474: ! 475: cleanup(err) ! 476: { ! 477: unlink(acttmp); ! 478: unlink(opttmp); ! 479: stats(); ! 480: exit(err); ! 481: } ! 482: ! 483: stats() ! 484: { ! 485: extern nsrconf, nrrconf; ! 486: ! 487: if( !pstat && (nsrconf || nrrconf) ) { ! 488: if( nrrconf ) { ! 489: fprintf(stderr, "%d R/R conflict", nrrconf); ! 490: if( nrrconf != 1 ) ! 491: fprintf(stderr, "s"); ! 492: } ! 493: if( nrrconf && nsrconf ) ! 494: fprintf(stderr, " and "); ! 495: if( nsrconf ) { ! 496: fprintf(stderr, "%d S/R conflict", nsrconf); ! 497: if( nsrconf != 1) ! 498: fprintf(stderr, "s"); ! 499: } ! 500: fprintf(stderr, "\n"); ! 501: } ! 502: if( verbose ) ! 503: stat1(listout); ! 504: if( pstat ) ! 505: stat1(stdout); ! 506: } ! 507: ! 508: ! 509: stat1(f) ! 510: FILE *f; ! 511: { ! 512: extern nsrconf, nrrconf, yygodef, yypact, yyredns; ! 513: extern ndupgos, ndupacts; ! 514: extern yydefact; ! 515: ! 516: fprintf(f, "Statistics:\n"); ! 517: fprintf(f, "%d/%d tokens, %d/%d non terminals\n", nterm, maxterm, ! 518: nnonterm, maxnterm); ! 519: fprintf(f, "%d/%d productions, %d/%d states\n", nprod, maxprod, ! 520: nstates, maxstates); ! 521: fprintf(f, "%d goto entries; %d saved by goto default\n", ! 522: yyredns, yygodef); ! 523: fprintf(f, "%d parsing actions; %d saved by default\n", ! 524: yypact, yydefact); ! 525: fprintf(f, "%d duplicated goto entries saved; %d actions\n", ! 526: ndupgos, ndupacts); ! 527: if( nsrconf || nrrconf ) ! 528: fprintf(f, "%d R/R conflicts, %d S/R conflicts\n", ! 529: nrrconf, nsrconf); ! 530: } ! 531: ! 532: char * ! 533: yalloc(n, s) ! 534: { ! 535: register char *cp; ! 536: ! 537: if( cp = calloc(n, s) ) ! 538: return(cp); ! 539: yyerror(NLNO|FATAL, "storage overflow (requested %d)\n", n*s); ! 540: } ! 541: ! 542: /* ! 543: * transform the state representation ! 544: */ ! 545: ! 546: sttrans() ! 547: { ! 548: register j, k; ! 549: int i, totgo, tontgo; ! 550: register struct state *stp; ! 551: struct tgo *tgp; ! 552: struct ntgo *ngp; ! 553: ! 554: /* a la pubelle !! */ ! 555: for(i=0; i<nstates; i++) ! 556: free(items[i]); ! 557: free(items); ! 558: ! 559: if( yydebug ) ! 560: fprintf(listout,"Automaton transition graph:\n\n"); ! 561: for(i=totgo=0; i<nstates; i++) ! 562: totgo += states[i].s_tgo; ! 563: for(i=tontgo=0; i<nstates; i++) ! 564: tontgo += states[i].s_ntgo; ! 565: tgp = (struct tgo *)yalloc(totgo, sizeof *tgp); ! 566: ngp = (struct ntgo *)yalloc(tontgo, sizeof *ngp); ! 567: rewopt(); ! 568: ! 569: for(j=0; j<nstates; j++) { ! 570: if( yydebug ) ! 571: fprintf(listout, "State %d:\n\n", j); ! 572: stp = &states[j]; ! 573: if( fread(&i, sizeof i, 1, optout)!=1 || i!=j ) ! 574: yyerror(NLNO|FATAL, "temp file i/o error"); ! 575: fread(tgp, sizeof *tgp, stp->s_tgo, optout); ! 576: stp->s_tgos = tgp; ! 577: stp->s_ntgos = ngp; ! 578: if( yydebug ) ! 579: for(k=0; k<stp->s_tgo; k++) ! 580: fprintf(listout, "\t%s\t%d\n", ! 581: ptosym(stp->s_tgos[k].tg_trm), ! 582: stp->s_tgos[k].tg_st); ! 583: fread(ngp, sizeof *ngp, stp->s_ntgo, optout); ! 584: if( yydebug ) ! 585: for(k=0; k<stp->s_ntgo; k++) ! 586: fprintf(listout, "\t%s\t%d\n", ! 587: ptosym(stp->s_ntgos[k].ng_nt), ! 588: stp->s_ntgos[k].ng_st); ! 589: tgp += stp->s_tgo; ! 590: ngp += stp->s_ntgo; ! 591: } ! 592: } ! 593:
This archive runs on limited infrastructure. Preserving old code on modern bandwidth. Automated agents are requested to crawl responsibly.