# 2.11BSD#431 - /usr/src/usr.bin/yacc/y3.c

##### Functions

    apack             X
    go2gen            X
    go2out            X
    hideprod          X
    output            X
    precftn           X
    warray            X
    wdef              X
    wract             X
    wrstate           X

##### Variables

    defact            X
    g2debug           X
    lastred           X
    pkdebug           X

       1: #if !defined(lint) && defined(DOSCCS)
       2: static char sccsid[] = "@(#)y3.c	4.1.1	(2.11BSD)	1995/05/11";
       3: #endif
       4:
       5: # include "dextern"
       6:
       7:     /* important local variables */
       8: int lastred;  /* the number of the last reduction of a state */
       9: int defact[NSTATES];  /* the default actions of states */
      10:
      11: output(){ /* print the output for the states */
      12:
      13:     int i, k;
      14:     register int c;
      15:     register struct wset *u, *v;
      16:
      17:     fprintf( ftable, "short yyexca[] ={\n" );
      18:
      19:     SLOOP(i) { /* output the stuff for state i */
      20:         nolook = !(tystate[i]==MUSTLOOKAHEAD);
      21:         closure(i);
      22:         /* output actions */
      23:         nolook = 1;
      24:         aryfil( temp1, ntokens+nnonter+1, 0 );
      25:         WSLOOP(wsets,u){
      26:             c = *( u->pitem );
      27:             if( c>1 && c<NTBASE && temp1[c]==0 ) {
      28:                 WSLOOP(u,v){
      29:                     if( c == *(v->pitem) ) putitem( v->pitem+1, (struct looksets *)0 );
      30:                     }
      31:                 temp1[c] = state(c);
      32:                 }
      33:             else if( c > NTBASE && temp1[ (c -= NTBASE) + ntokens ] == 0 ){
      34:                 temp1[ c+ntokens ] = amem[indgo[i]+c];
      35:                 }
      36:             }
      37:
      38:         if( i == 1 ) temp1[1] = ACCEPTCODE;
      39:
      40:         /* now, we have the shifts; look at the reductions */
      41:
      42:         lastred = 0;
      43:         WSLOOP(wsets,u){
      44:             c = *( u->pitem );
      45:             if( c<=0 ){ /* reduction */
      46:                 lastred = -c;
      47:                 TLOOP(k){
      48:                     if( BIT(u->ws.lset,k) ){
      49:                           if( temp1[k] == 0 ) temp1[k] = c;
      50:                           else if( temp1[k]<0 ){ /* reduce/reduce conflict */
      51:                             if( foutput!=NULL )
      52:                               fprintf( foutput,
      53:                                 "\n%d: reduce/reduce conflict (red'ns %d and %d ) on %s",
      54:                                 i, -temp1[k], lastred, symnam(k) );
      55:                             if( -temp1[k] > lastred ) temp1[k] = -lastred;
      56:                             ++zzrrconf;
      57:                             }
      58:                           else { /* potential shift/reduce conflict */
      59:                             precftn( lastred, k, i );
      60:                             }
      61:                         }
      62:                     }
      63:                 }
      64:             }
      65:         wract(i);
      66:         }
      67:
      68:     fprintf( ftable, "\t};\n" );
      69:
      70:     wdef( "YYNPROD", nprod );
      71:
      72:     }
      73:
      74: int pkdebug = 0;
      75: apack(p, n ) int *p;{ /* pack state i from temp1 into amem */
      76:     int off;
      77:     register *pp, *qq, *rr;
      78:     int *q, *r;
      79:
      80:     /* we don't need to worry about checking because we
      81: 	   we will only look entries known to be there... */
      82:
      83:     /* eliminate leading and trailing 0's */
      84:
      85:     q = p+n;
      86:     for( pp=p,off=0 ; *pp==0 && pp<=q; ++pp,--off ) /* VOID */ ;
      87:     if( pp > q ) return(0);  /* no actions */
      88:     p = pp;
      89:
      90:     /* now, find a place for the elements from p to q, inclusive */
      91:
      92:     r = &amem[ACTSIZE-1];
      93:     for( rr=amem; rr<=r; ++rr,++off ){  /* try rr */
      94:         for( qq=rr,pp=p ; pp<=q ; ++pp,++qq){
      95:             if( *pp != 0 ){
      96:                 if( *pp != *qq && *qq != 0 ) goto nextk;
      97:                 }
      98:             }
      99:
     100:         /* we have found an acceptable k */
     101:
     102:         if( pkdebug && foutput!=NULL ) fprintf( foutput, "off = %d, k = %d\n", off, rr-amem );
     103:
     104:         for( qq=rr,pp=p; pp<=q; ++pp,++qq ){
     105:             if( *pp ){
     106:                 if( qq > r ) error( "action table overflow" );
     107:                 if( qq>memp ) memp = qq;
     108:                 *qq = *pp;
     109:                 }
     110:             }
     111:         if( pkdebug && foutput!=NULL ){
     112:             for( pp=amem; pp<= memp; pp+=10 ){
     113:                 fprintf( foutput, "\t");
     114:                 for( qq=pp; qq<=pp+9; ++qq ) fprintf( foutput, "%d ", *qq );
     115:                 fprintf( foutput, "\n");
     116:                 }
     117:             }
     118:         return( off );
     119:
     120:         nextk: ;
     121:         }
     122:     error("no space in action table" );
     123:     /* NOTREACHED */
     124:     }
     125:
     126: go2out(){ /* output the gotos for the nontermninals */
     127:     register int i, j, k;
     128:     int best, count, cbest, times;
     129:
     130:     fprintf( ftemp, "$\n" );  /* mark begining of gotos */
     131:
     132:     for( i=1; i<=nnonter; ++i ) {
     133:         go2gen(i);
     134:
     135:         /* find the best one to make default */
     136:
     137:         best = -1;
     138:         times = 0;
     139:
     140:         for( j=0; j<=nstate; ++j ){ /* is j the most frequent */
     141:             if( tystate[j] == 0 ) continue;
     142:             if( tystate[j] == best ) continue;
     143:
     144:             /* is tystate[j] the most frequent */
     145:
     146:             count = 0;
     147:             cbest = tystate[j];
     148:
     149:             for( k=j; k<=nstate; ++k ) if( tystate[k]==cbest ) ++count;
     150:
     151:             if( count > times ){
     152:                 best = cbest;
     153:                 times = count;
     154:                 }
     155:             }
     156:
     157:         /* best is now the default entry */
     158:
     159:         zzgobest += (times-1);
     160:         for( j=0; j<=nstate; ++j ){
     161:             if( tystate[j] != 0 && tystate[j]!=best ){
     162:                 fprintf( ftemp, "%d,%d,", j, tystate[j] );
     163:                 zzgoent += 1;
     164:                 }
     165:             }
     166:
     167:         /* now, the default */
     168:
     169:         zzgoent += 1;
     170:         fprintf( ftemp, "%d\n", best );
     171:
     172:         }
     173:
     174:
     175:
     176:     }
     177:
     178: int g2debug = 0;
     179: go2gen(c){ /* output the gotos for nonterminal c */
     180:
     181:     register int i, cc;
     182:     int work;
     183:     struct item *p, *q;
     184:
     185:
     186:     /* first, find nonterminals with gotos on c */
     187:
     188:     aryfil( temp1, nnonter+1, 0 );
     189:     temp1[c] = 1;
     190:
     191:     work = 1;
     192:     while( work ){
     193:         work = 0;
     194:         PLOOP(0,i){
     195:             if( (cc=prdptr[i][1]-NTBASE) >= 0 ){ /* cc is a nonterminal */
     196:                 if( temp1[cc] != 0 ){ /* cc has a goto on c */
     197:                     cc = *prdptr[i]-NTBASE; /* thus, the left side of production i does too */
     198:                     if( temp1[cc] == 0 ){
     199:                           work = 1;
     200:                           temp1[cc] = 1;
     201:                           }
     202:                     }
     203:                 }
     204:             }
     205:         }
     206:
     207:     /* now, we have temp1[c] = 1 if a goto on c in closure of cc */
     208:
     209:     if( g2debug && foutput!=NULL ){
     210:         fprintf( foutput, "%s: gotos on ", nontrst[c].name );
     211:         NTLOOP(i) if( temp1[i] ) fprintf( foutput, "%s ", nontrst[i].name);
     212:         fprintf( foutput, "\n");
     213:         }
     214:
     215:     /* now, go through and put gotos into tystate */
     216:
     217:     aryfil( tystate, nstate, 0 );
     218:     SLOOP(i){
     219:         ITMLOOP(i,p,q){
     220:             if( (cc= *p->pitem) >= NTBASE ){
     221:                 if( temp1[cc -= NTBASE] ){ /* goto on c is possible */
     222:                     tystate[i] = amem[indgo[i]+c];
     223:                     break;
     224:                     }
     225:                 }
     226:             }
     227:         }
     228:     }
     229:
     230: precftn(r,t,s) register int t;
     231:     { /* decide a shift/reduce conflict by precedence.
     232: 	/* r is a rule number, t a token number */
     233:     /* the conflict is in state s */
     234:     /* temp1[t] is changed to reflect the action */
     235:
     236:     int lp,lt, action;
     237:
     238:     lp = levprd[r];
     239:     lt = toklev[t];
     240:     if( PLEVEL(lt) == 0 || PLEVEL(lp) == 0 ) {
     241:         /* conflict */
     242:         if( foutput != NULL ) fprintf( foutput, "\n%d: shift/reduce conflict (shift %d, red'n %d) on %s",
     243:                         s, temp1[t], r, symnam(t) );
     244:         ++zzsrconf;
     245:         return;
     246:         }
     247:     if( PLEVEL(lt) == PLEVEL(lp) ) action = ASSOC(lt);
     248:     else if( PLEVEL(lt) > PLEVEL(lp) ) action = RASC;  /* shift */
     249:     else action = LASC;  /* reduce */
     250:
     251:     switch( action ){
     252:
     253:     case BASC:  /* error action */
     254:         temp1[t] = ERRCODE;
     255:         return;
     256:
     257:     case LASC:  /* reduce */
     258:         temp1[t] = -r;
     259:         return;
     260:
     261:         }
     262:     }
     263:
     264: wract(i) register int i; { /* output state i */
     265:     /* temp1 has the actions, lastred the default */
     266:     int p, p0, p1;
     267:     int ntimes, tred, count;
     268:     register int j;
     269:     int flag;
     270:
     271:     /* find the best choice for lastred */
     272:
     273:     lastred = 0;
     274:     ntimes = 0;
     275:     TLOOP(j){
     276:         if( temp1[j] >= 0 ) continue;
     277:         if( temp1[j]+lastred == 0 ) continue;
     278:         /* count the number of appearances of temp1[j] */
     279:         count = 0;
     280:         tred = -temp1[j];
     281:         levprd[tred] |= REDFLAG;
     282:         TLOOP(p){
     283:             if( temp1[p]+tred == 0 ) ++count;
     284:             }
     285:         if( count >ntimes ){
     286:             lastred = tred;
     287:             ntimes = count;
     288:             }
     289:         }
     290:
     291:     /* for error recovery, arrange that, if there is a shift on the
     292: 	/* error recovery token, `error', that the default be the error action */
     293:     if( temp1[1] > 0 ) lastred = 0;
     294:
     295:     /* clear out entries in temp1 which equal lastred */
     296:     TLOOP(p) if( temp1[p]+lastred == 0 )temp1[p]=0;
     297:
     298:     wrstate(i);
     299:     defact[i] = lastred;
     300:
     301:     flag = 0;
     302:     TLOOP(p0){
     303:         if( (p1=temp1[p0])!=0 ) {
     304:             if( p1 < 0 ){
     305:                 p1 = -p1;
     306:                 goto exc;
     307:                 }
     308:             else if( p1 == ACCEPTCODE ) {
     309:                 p1 = -1;
     310:                 goto exc;
     311:                 }
     312:             else if( p1 == ERRCODE ) {
     313:                 p1 = 0;
     314:                 goto exc;
     315:             exc:
     316:                 if( flag++ == 0 ) fprintf( ftable, "-1, %d,\n", i );
     317:                 fprintf( ftable, "\t%d, %d,\n", tokset[p0].value, p1 );
     318:                 ++zzexcp;
     319:                 }
     320:             else {
     321:                 fprintf( ftemp, "%d,%d,", tokset[p0].value, p1 );
     322:                 ++zzacent;
     323:                 }
     324:             }
     325:         }
     326:     if( flag ) {
     327:         defact[i] = -2;
     328:         fprintf( ftable, "\t-2, %d,\n", lastred );
     329:         }
     330:     fprintf( ftemp, "\n" );
     331:     return;
     332:     }
     333:
     334: wrstate(i){ /* writes state i */
     335:     register j0,j1;
     336:     register struct item *pp, *qq;
     337:     register struct wset *u;
     338:
     339:     if( foutput == NULL ) return;
     340:     fprintf( foutput, "\nstate %d\n",i);
     341:     ITMLOOP(i,pp,qq) fprintf( foutput, "\t%s\n", writem(pp->pitem));
     342:     if( tystate[i] == MUSTLOOKAHEAD ){
     343:         /* print out empty productions in closure */
     344:         WSLOOP( wsets+(pstate[i+1]-pstate[i]), u ){
     345:             if( *(u->pitem) < 0 ) fprintf( foutput, "\t%s\n", writem(u->pitem) );
     346:             }
     347:         }
     348:
     349:     /* check for state equal to another */
     350:
     351:     TLOOP(j0) if( (j1=temp1[j0]) != 0 ){
     352:         fprintf( foutput, "\n\t%s  ", symnam(j0) );
     353:         if( j1>0 ){ /* shift, error, or accept */
     354:             if( j1 == ACCEPTCODE ) fprintf( foutput,  "accept" );
     355:             else if( j1 == ERRCODE ) fprintf( foutput, "error" );
     356:             else fprintf( foutput,  "shift %d", j1 );
     357:             }
     358:         else fprintf( foutput, "reduce %d",-j1 );
     359:         }
     360:
     361:     /* output the final production */
     362:
     363:     if( lastred ) fprintf( foutput, "\n\t.  reduce %d\n\n", lastred );
     364:     else fprintf( foutput, "\n\t.  error\n\n" );
     365:
     366:     /* now, output nonterminal actions */
     367:
     368:     j1 = ntokens;
     369:     for( j0 = 1; j0 <= nnonter; ++j0 ){
     370:         if( temp1[++j1] ) fprintf( foutput, "\t%s  goto %d\n", symnam( j0+NTBASE), temp1[j1] );
     371:         }
     372:
     373:     }
     374:
     375: wdef( s, n ) char *s; { /* output a definition of s to the value n */
     376:     fprintf( ftable, "# define %s %d\n", s, n );
     377:     }
     378:
     379: warray( s, v, n ) char *s; int *v, n; {
     380:
     381:     register i;
     382:
     383:     fprintf( ftable, "short %s[]={\n", s );
     384:     for( i=0; i<n; ){
     385:         if( i%10 == 0 ) fprintf( ftable, "\n" );
     386:         fprintf( ftable, "%4d", v[i] );
     387:         if( ++i == n ) fprintf( ftable, " };\n" );
     388:         else fprintf( ftable, "," );
     389:         }
     390:     }
     391:
     392: hideprod(){
     393:     /* in order to free up the mem and amem arrays for the optimizer,
     394: 	/* and still be able to output yyr1, etc., after the sizes of
     395: 	/* the action array is known, we hide the nonterminals
     396: 	/* derived by productions in levprd.
     397: 	*/
     398:
     399:     register i, j;
     400:
     401:     j = 0;
     402:     levprd[0] = 0;
     403:     PLOOP(1,i){
     404:         if( !(levprd[i] & REDFLAG) ){
     405:             ++j;
     406:             if( foutput != NULL ){
     407:                 fprintf( foutput, "Rule not reduced:   %s\n", writem( prdptr[i] ) );
     408:                 }
     409:             }
     410:         levprd[i] = *prdptr[i] - NTBASE;
     411:         }
     412:     if( j ) fprintf( stdout, "%d rules never reduced\n", j );
     413:     }

#### Defined functions

apack defined in line 75; used 1 times

- in /usr/src/usr.bin/yacc/y1.c line 523

go2gen defined in line 179; used 1 times

- in line 133

go2out defined in line 126; used 1 times

- in /usr/src/usr.bin/yacc/y1.c line 59

hideprod defined in line 392; used 1 times

- in /usr/src/usr.bin/yacc/y1.c line 60

output defined in line 11; used 1 times

- in /usr/src/usr.bin/yacc/y1.c line 58

precftn defined in line 230; used 1 times

- in line 59

warray defined in line 379; used 4 times

- in /usr/src/usr.bin/yacc/y1.c line 73-77(2), 90-92(2)

wdef defined in line 375; used 1 times

- in line 70

wract defined in line 264; used 1 times

- in line 65

wrstate defined in line 334; used 1 times

- in line 298

#### Defined variables

defact defined in line 9; used 5 times

- in line 299, 327
- in /usr/src/usr.bin/yacc/y1.c line 92
- in /usr/src/usr.bin/yacc/y3.c line 299, 327

g2debug defined in line 178; used 1 times

- in line 209

lastred defined in line 8; used 15 times

- in line 42-46(2), 54-59(4), 273-277(2), 286, 293-299(3), 328, 363(2)

pkdebug defined in line 74; used 2 times

- in line 102, 111

sccsid defined in line 2; never used

Last modified: 1995-05-12 Generated: 2016-12-26 | Generated by src2html V0.67 page hit count: 1023 |