![[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 / b / bin / yacc|
Return to y1.c CVS log | Up to [MW Coherent from dump] / coherent / b / bin / yacc |
1.1 ! root 1: /* ! 2: * LALR-1 parser generator ! 3: */ ! 4: ! 5: #include <string.h> ! 6: #include "yacc.h" ! 7: ! 8: main(argc,argv) ! 9: char *argv[]; ! 10: { ! 11: options(argc,argv); ! 12: getfiles(); ! 13: readrules(); ! 14: ntprod(); ! 15: ntderive(); ! 16: listgram(); ! 17: if( nerrors ) ! 18: cleanup(1); ! 19: ntempty(); ! 20: if( nerrors ) ! 21: cleanup(1); ! 22: genstates(); ! 23: genslist(); ! 24: sttrans(); ! 25: genlook(); ! 26: go2out(); ! 27: paout(); ! 28: callopt(); ! 29: cleanup(0); ! 30: } ! 31: ! 32: getfiles() ! 33: { ! 34: if( gramy==NULL ) ! 35: usage(); ! 36: if( strcmp(gramy,"-")==0 ) ! 37: defin = stdin; ! 38: else ! 39: if( (defin = fopen(gramy,"r")) == NULL ) ! 40: yyerror(!FATAL, "cannot open grammar file %s", gramy); ! 41: mktemp(acttmp); ! 42: mktemp(opttmp); ! 43: if( (actout = fopen(acttmp,"w")) == NULL ) ! 44: yyerror(!FATAL, "cannot create action temp file %s", acttmp); ! 45: if( (tabout = fopen(ytabc,"w")) == NULL ) ! 46: yyerror(!FATAL, "cannot create output file %s", ytabc); ! 47: if( (fhdr = fopen(ytabh, "w")) == NULL ) ! 48: yyerror(!FATAL, "cannot create %s", ytabh); ! 49: if( verbose ) ! 50: if( (listout = fopen(youtput,"w")) == NULL ) ! 51: yyerror(NLNO, "cannot open listing file %s", youtput); ! 52: if ((optout = fopen(opttmp, "wb")) == NULL ! 53: || (optout = freopen(opttmp, "rwb", optout)) == NULL) ! 54: yyerror(NLNO, "open error temp %s", opttmp); ! 55: if( nerrors ) ! 56: cleanup(2); ! 57: } ! 58: ! 59: rewopt() ! 60: { ! 61: fseek(optout, 0L, 0); ! 62: } ! 63: ! 64: /* ! 65: * for each non-terminal, generate a list of productions which the ! 66: * the non terminal derives ! 67: */ ! 68: ntprod() ! 69: { ! 70: register i; ! 71: register struct sym *sp; ! 72: ! 73: /* first run down the production table, counting references to ! 74: all the non terminals. */ ! 75: for(i=0; i<nnonterm; i++) ! 76: ntrmptr[i]->s_nprods = 0; ! 77: for(i=0; i<nprod; i++) ! 78: ntrmptr[-prdptr[i]->p_left-NTBASE]->s_nprods++; ! 79: for(i=0; i<nnonterm; i++) ! 80: if( ntrmptr[i]->s_nprods==0 ) ! 81: yyerror(NLNO|!FATAL, "non terminal %s not defined", ! 82: ntrmptr[i]->s_name); ! 83: if( nerrors ) ! 84: cleanup(1); ! 85: /* now allocate list pointers for each non-terminal */ ! 86: for(i=0; i<nnonterm; i++) { ! 87: sp = ntrmptr[i]; ! 88: sp->s_prods = (struct prod **) ! 89: 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 = PROD_RIGHT (pp); *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 = PROD_RIGHT (*ppp); *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] = PROD_RIGHT (prdptr[0]); ! 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 = NULL; ! 238: states[i].s_ntgos = NULL; ! 239: states[i].s_reds = NULL; /* MWC DSC */ ! 240: } ! 241: } while( newgen ); ! 242: free(ntp); ! 243: } ! 244: ! 245: /* ! 246: * generate the closure of a state (found in global variable `nititem' ! 247: * Algorithm: ! 248: * - look at every non terminal's after every '.' item pointer ! 249: * - add all the productions associated with this non-terminal ! 250: * to the state (the '.' being at the beginning of the rhs) unless ! 251: * they are already there. It suffices to test if one of them is ! 252: * already there, since productions are added to the closure according ! 253: * according to their lhs ! 254: * repeat this procedure until no new items are added. ! 255: * ! 256: * "It can be shown that (this procedure) computes exactly the sets ! 257: * of items that are valid for gamma X [Aho and Ullmann 1972]" ! 258: */ ! 259: ! 260: closure() ! 261: { ! 262: register j, **ipp; ! 263: register struct prod **ppp; ! 264: struct sitem *itp; ! 265: struct sym *sp; ! 266: int i, changed, nt; ! 267: ! 268: itp = nititem; ! 269: for(i=0; i<nnonterm; i++) ! 270: ntrmptr[i]->s_flags &= ~CPRES; ! 271: for(i=0; i<itp->i_nitems; i++) ! 272: /* kludge: requires p.left & p.rights contiguous */ ! 273: if( (nt = *(itp->i_items[i]-1)) < 0 ) { /* ARE THEY???? */ ! 274: #if 0 ! 275: fprintf (stderr, "CPRES : %d\n", i); ! 276: #endif ! 277: ntrmptr[-nt-NTBASE]->s_flags |= CPRES; ! 278: } ! 279: do { ! 280: changed = 0; ! 281: for(i=0; i<itp->i_nitems; i++) { ! 282: nt = *(itp->i_items[i]); ! 283: if( nt>=NTBASE && ((sp = ntrmptr[nt-NTBASE])->s_flags ! 284: &CPRES)==0 ) { ! 285: sp->s_flags |= CPRES; ! 286: changed = 1; ! 287: ppp = sp->s_prods; ! 288: ipp = &itp->i_items[itp->i_nitems]; ! 289: itp->i_nitems += j = sp->s_nprods; ! 290: bounded(itp->i_nitems, maxitem, "items in state"); ! 291: do ! 292: *ipp++ = PROD_RIGHT (*ppp++); ! 293: while( --j ); ! 294: } ! 295: } ! 296: } while( changed ); ! 297: } ! 298: ! 299: /* ! 300: * add the state in `nititem' to the collection of sets of accessible ! 301: * items, returning the state pointer ! 302: * the real work is concerned with finding out whether the set is there ! 303: * already or not ! 304: * we sort the items in nititem, compare with every set in "items", ! 305: * and return the old state pointer if its there already ! 306: */ ! 307: install() ! 308: { ! 309: register n, **ipp1, **ipp2; ! 310: struct sitem *itp, *itp1; ! 311: int i; ! 312: ! 313: itp = nititem; ! 314: bubble(itp->i_items, itp->i_nitems); ! 315: for(i=0; i<nstates; i++) { ! 316: itp1 = items[i]; ! 317: if( (n = itp->i_nitems) != itp1->i_nitems ) ! 318: continue; ! 319: ipp1 = itp->i_items; ! 320: ipp2 = itp1->i_items; ! 321: do ! 322: if( *ipp1++ != *ipp2++ ) ! 323: break; ! 324: while( --n ); ! 325: if( n==0 ) ! 326: break; ! 327: } ! 328: if (i == nstates) { ! 329: bounded (nstates,maxstates,"states"); ! 330: chklhs (); ! 331: ! 332: /* ! 333: * NIGEL: Changed to stop use of flex-arrays. ! 334: */ ! 335: ! 336: itp1 = (struct sitem *) ! 337: yalloc (1, SITEM_TOTAL_SIZE (itp->i_nitems)); ! 338: * itp1 = * itp; ! 339: SITEM_EXTRA_INIT (itp1); ! 340: ! 341: if (SITEM_EXTRA_SIZE (itp->i_nitems) > 0) ! 342: memcpy (itp1->i_items, itp->i_items, ! 343: SITEM_EXTRA_SIZE (itp->i_nitems)); ! 344: ! 345: newgen = 1; ! 346: items [nstates] = itp1; ! 347: if (verbose) ! 348: prstate (nstates, listout); ! 349: nstates ++; ! 350: } ! 351: return i; ! 352: } ! 353: ! 354: go2(itp, tk) ! 355: struct sitem *itp; ! 356: int tk; ! 357: { ! 358: register **ipp1, **ipp, n; ! 359: ! 360: nititem->i_nitems = 0; ! 361: ipp1 = nititem->i_items; ! 362: ipp = itp->i_items; ! 363: n = itp->i_nitems; ! 364: do { ! 365: if( **ipp == tk ) { ! 366: nititem->i_nitems++; ! 367: *ipp1++ = *ipp+1; ! 368: } ! 369: ipp++; ! 370: } while( --n ); ! 371: if( nititem->i_nitems==0 ) ! 372: return( -1 ); ! 373: else { ! 374: closure(); ! 375: return( install() ); ! 376: } ! 377: } ! 378: ! 379: chklhs() ! 380: { ! 381: register n, **ipp; ! 382: register char *cp; ! 383: int nt; ! 384: ! 385: n = nnonterm; ! 386: cp = ntp; ! 387: do *cp++ = 0; while( --n ); ! 388: ipp = nititem->i_items; ! 389: n = nititem->i_nitems; ! 390: cp = ntp; ! 391: do ! 392: if( (nt = (*ipp++) [-1]) < 0 ) ! 393: cp[ -nt-NTBASE ] = 1; ! 394: while( --n ); ! 395: for(n=0; n<nnonterm; n++) ! 396: if( cp[n] ) ! 397: ntrmptr[n]->s_nstates++; ! 398: } ! 399: ! 400: /* ! 401: * for each nonterminal generate a list of items ! 402: * containing items with all of the rhs of a production ! 403: * whose lhs is the non-terminal after the '.' ! 404: */ ! 405: genslist() ! 406: { ! 407: register struct sym *sp; ! 408: register i, j; ! 409: int *ip; ! 410: int *stp; ! 411: ! 412: for(i=j=0; i<nnonterm; i++) ! 413: j += ntrmptr[i]->s_nstates; ! 414: stp = (int *)yalloc(j, sizeof *stp); ! 415: for(i=0; i<nnonterm; i++) { ! 416: sp = ntrmptr[i]; ! 417: sp->s_states = stp; ! 418: stp += sp->s_nstates; ! 419: sp->s_nstates = 0; /* a recharcher dans le boucle suivant */ ! 420: } ! 421: for(i=0; i<nnonterm; i++) { ! 422: sp = ntrmptr[i]; ! 423: ip = PROD_RIGHT (sp->s_prods[0]); /* pick an item, any item */ ! 424: for(j=0; j<nstates; j++) ! 425: if( pitem(ip, items[j]) ) ! 426: sp->s_states[sp->s_nstates++] = j; ! 427: } ! 428: } ! 429: ! 430: /* binary search for an item in a state */ ! 431: ! 432: pitem(ip,itp) ! 433: int *ip; ! 434: register struct sitem *itp; ! 435: { ! 436: register int *el, nb; ! 437: int ub, lb; ! 438: ! 439: lb = 0; ! 440: ub = itp->i_nitems-1; ! 441: do { ! 442: nb = (ub+lb) / 2; ! 443: if( (el = itp->i_items[nb]) < ip ) ! 444: lb = nb+1; ! 445: else if( el > ip ) ! 446: ub = nb-1; ! 447: else ! 448: return(1); ! 449: } while( lb<=ub ); ! 450: return(0); ! 451: } ! 452: ! 453: /* ! 454: * linear insertion sort really. ! 455: * the decision not to use bubbbbbbbbbbbble sort is thanks to Randall ! 456: * and to his cs240b notes ! 457: * (p.s. -- i hate sorting) ! 458: */ ! 459: ! 460: bubble(ipp,n) ! 461: register **ipp; ! 462: int n; ! 463: { ! 464: register **min, **jpp; ! 465: int m, *t; /* MWC DSC */ ! 466: ! 467: do { ! 468: m = n; ! 469: min = jpp = ipp; ! 470: do { ! 471: if( *jpp < *min ) ! 472: min = jpp; ! 473: jpp++; ! 474: } while( --m ); ! 475: t = *min; ! 476: *min = *ipp; ! 477: *ipp++ = t; ! 478: } while( --n ); ! 479: } ! 480: ! 481: cleanup(err) ! 482: { ! 483: unlink(acttmp); ! 484: unlink(opttmp); ! 485: stats(); ! 486: exit(err); ! 487: } ! 488: ! 489: stats() ! 490: { ! 491: extern nsrconf, nrrconf; ! 492: ! 493: if( !pstat && (nsrconf || nrrconf) ) { ! 494: if( nrrconf ) { ! 495: fprintf(stderr, "%d R/R conflict", nrrconf); ! 496: if( nrrconf != 1 ) ! 497: fprintf(stderr, "s"); ! 498: } ! 499: if( nrrconf && nsrconf ) ! 500: fprintf(stderr, " and "); ! 501: if( nsrconf ) { ! 502: fprintf(stderr, "%d S/R conflict", nsrconf); ! 503: if( nsrconf != 1) ! 504: fprintf(stderr, "s"); ! 505: } ! 506: fprintf(stderr, "\n"); ! 507: } ! 508: if( verbose ) ! 509: stat1(listout); ! 510: if( pstat ) ! 511: stat1(stdout); ! 512: } ! 513: ! 514: ! 515: stat1(f) ! 516: FILE *f; ! 517: { ! 518: extern nsrconf, nrrconf, yygodef, yypact, yyredns; ! 519: extern ndupgos, ndupacts; ! 520: extern yydefact; ! 521: ! 522: fprintf(f, "Statistics:\n"); ! 523: fprintf(f, "%d/%d tokens, %d/%d non terminals\n", nterm, maxterm, ! 524: nnonterm, maxnterm); ! 525: fprintf(f, "%d/%d productions, %d/%d states\n", nprod, maxprod, ! 526: nstates, maxstates); ! 527: fprintf(f, "%d goto entries; %d saved by goto default\n", ! 528: yyredns, yygodef); ! 529: fprintf(f, "%d parsing actions; %d saved by default\n", ! 530: yypact, yydefact); ! 531: fprintf(f, "%d duplicated goto entries saved; %d actions\n", ! 532: ndupgos, ndupacts); ! 533: if( nsrconf || nrrconf ) ! 534: fprintf(f, "%d R/R conflicts, %d S/R conflicts\n", ! 535: nrrconf, nsrconf); ! 536: } ! 537: ! 538: char * ! 539: yalloc(n, s) ! 540: { ! 541: register char *cp; ! 542: ! 543: if ((cp = calloc(n, s)) == NULL) ! 544: yyerror (NLNO | FATAL, ! 545: "storage overflow (requested %d * %d)\n", n, s); ! 546: ! 547: return cp; ! 548: } ! 549: ! 550: /* ! 551: * transform the state representation ! 552: */ ! 553: ! 554: sttrans() ! 555: { ! 556: register j, k; ! 557: int i, totgo, tontgo; ! 558: register struct state *stp; ! 559: struct tgo *tgp; ! 560: struct ntgo *ngp; ! 561: ! 562: /* a la pubelle !! */ ! 563: for(i=0; i<nstates; i++) ! 564: free(items[i]); ! 565: free(items); ! 566: ! 567: if( yydebug ) ! 568: fprintf(listout,"Automaton transition graph:\n\n"); ! 569: for(i=totgo=0; i<nstates; i++) ! 570: totgo += states[i].s_tgo; ! 571: for(i=tontgo=0; i<nstates; i++) ! 572: tontgo += states[i].s_ntgo; ! 573: tgp = (struct tgo *)yalloc(totgo, sizeof *tgp); ! 574: ngp = (struct ntgo *)yalloc(tontgo, sizeof *ngp); ! 575: rewopt(); ! 576: ! 577: for(j=0; j<nstates; j++) { ! 578: if( yydebug ) ! 579: fprintf(listout, "State %d:\n\n", j); ! 580: stp = &states[j]; ! 581: if( fread(&i, sizeof i, 1, optout)!=1 || i!=j ) ! 582: yyerror(NLNO|FATAL, "temp file i/o error"); ! 583: fread(tgp, sizeof *tgp, stp->s_tgo, optout); ! 584: stp->s_tgos = tgp; ! 585: stp->s_ntgos = ngp; ! 586: if( yydebug ) ! 587: for(k=0; k<stp->s_tgo; k++) ! 588: fprintf(listout, "\t%s\t%d\n", ! 589: ptosym(stp->s_tgos[k].tg_trm), ! 590: stp->s_tgos[k].tg_st); ! 591: fread(ngp, sizeof *ngp, stp->s_ntgo, optout); ! 592: if( yydebug ) ! 593: for(k=0; k<stp->s_ntgo; k++) ! 594: fprintf(listout, "\t%s\t%d\n", ! 595: ptosym(stp->s_ntgos[k].ng_nt), ! 596: stp->s_ntgos[k].ng_st); ! 597: tgp += stp->s_tgo; ! 598: ngp += stp->s_ntgo; ! 599: } ! 600: } ! 601:
This archive runs on limited infrastructure. Preserving old code on modern bandwidth. Automated agents are requested to crawl responsibly.