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

   1: #if !defined(lint) && defined(DOSCCS)
   2: static char sccsid[] = "@(#)y4.c	4.1.1	(2.11BSD)	1995/05/11";
   3: #endif
   4: 
   5: # include "dextern"
   6: 
   7: # define a amem
   8: # define mem mem0
   9: # define pa indgo
  10: # define yypact temp1
  11: # define greed tystate
  12: 
  13: int * ggreed = lkst[0].lset;
  14: int * pgo = wsets[0].ws.lset;
  15: int *yypgo = &nontrst[0].tvalue;
  16: 
  17: int maxspr = 0;  /* maximum spread of any entry */
  18: int maxoff = 0;  /* maximum offset into a array */
  19: int *pmem = mem;
  20: int *maxa;
  21: # define NOMORE -1000
  22: 
  23: int nxdb = 0;
  24: int adb = 0;
  25: 
  26: callopt(){
  27: 
  28:     register i, *p, j, k, *q;
  29: 
  30:     /* read the arrays from tempfile and set parameters */
  31: 
  32:     if( (finput=fopen(TEMPNAME,"r")) == NULL ) error( "optimizer cannot open tempfile" );
  33: 
  34:     pgo[0] = 0;
  35:     yypact[0] = 0;
  36:     nstate = 0;
  37:     nnonter = 0;
  38:     for(;;){
  39:         switch( gtnm() ){
  40: 
  41:         case '\n':
  42:             yypact[++nstate] = (--pmem) - mem;
  43:         case ',':
  44:             continue;
  45: 
  46:         case '$':
  47:             break;
  48: 
  49:         default:
  50:             error( "bad tempfile" );
  51:             }
  52:         break;
  53:         }
  54: 
  55:     yypact[nstate] = yypgo[0] = (--pmem) - mem;
  56: 
  57:     for(;;){
  58:         switch( gtnm() ){
  59: 
  60:         case '\n':
  61:             yypgo[++nnonter]= pmem-mem;
  62:         case ',':
  63:             continue;
  64: 
  65:         case EOF:
  66:             break;
  67: 
  68:         default:
  69:             error( "bad tempfile" );
  70:             }
  71:         break;
  72:         }
  73: 
  74:     yypgo[nnonter--] = (--pmem) - mem;
  75: 
  76: 
  77: 
  78:     for( i=0; i<nstate; ++i ){
  79: 
  80:         k = 32000;
  81:         j = 0;
  82:         q = mem + yypact[i+1];
  83:         for( p = mem + yypact[i]; p<q ; p += 2 ){
  84:             if( *p > j ) j = *p;
  85:             if( *p < k ) k = *p;
  86:             }
  87:         if( k <= j ){ /* nontrivial situation */
  88:             /* temporarily, kill this for compatibility
  89: 			j -= k;  /* j is now the range */
  90:             if( k > maxoff ) maxoff = k;
  91:             }
  92:         greed[i] = (yypact[i+1]-yypact[i]) + 2*j;
  93:         if( j > maxspr ) maxspr = j;
  94:         }
  95: 
  96:     /* initialize ggreed table */
  97: 
  98:     for( i=1; i<=nnonter; ++i ){
  99:         ggreed[i] = 1;
 100:         j = 0;
 101:         /* minimum entry index is always 0 */
 102:         q = mem + yypgo[i+1] -1;
 103:         for( p = mem+yypgo[i]; p<q ; p += 2 ) {
 104:             ggreed[i] += 2;
 105:             if( *p > j ) j = *p;
 106:             }
 107:         ggreed[i] = ggreed[i] + 2*j;
 108:         if( j > maxoff ) maxoff = j;
 109:         }
 110: 
 111: 
 112:     /* now, prepare to put the shift actions into the a array */
 113: 
 114:     for( i=0; i<ACTSIZE; ++i ) a[i] = 0;
 115:     maxa = a;
 116: 
 117:     for( i=0; i<nstate; ++i ) {
 118:         if( greed[i]==0 && adb>1 ) fprintf( ftable, "State %d: null\n", i );
 119:         pa[i] = YYFLAG1;
 120:         }
 121: 
 122:     while( (i = nxti()) != NOMORE ) {
 123:         if( i >= 0 ) stin(i);
 124:         else gin(-i);
 125: 
 126:         }
 127: 
 128:     if( adb>2 ){ /* print a array */
 129:         for( p=a; p <= maxa; p += 10){
 130:             fprintf( ftable, "%4d  ", p-a );
 131:             for( i=0; i<10; ++i ) fprintf( ftable, "%4d  ", p[i] );
 132:             fprintf( ftable, "\n" );
 133:             }
 134:         }
 135:     /* write out the output appropriate to the language */
 136: 
 137:     aoutput();
 138: 
 139:     osummary();
 140:     ZAPFILE(TEMPNAME);
 141:     }
 142: 
 143: gin(i){
 144: 
 145:     register *p, *r, *s, *q1, *q2;
 146: 
 147:     /* enter gotos on nonterminal i into array a */
 148: 
 149:     ggreed[i] = 0;
 150: 
 151:     q2 = mem+ yypgo[i+1] - 1;
 152:     q1 = mem + yypgo[i];
 153: 
 154:     /* now, find a place for it */
 155: 
 156:     for( p=a; p < &a[ACTSIZE]; ++p ){
 157:         if( *p ) continue;
 158:         for( r=q1; r<q2; r+=2 ){
 159:             s = p + *r +1;
 160:             if( *s ) goto nextgp;
 161:             if( s > maxa ){
 162:                 if( (maxa=s) > &a[ACTSIZE] ) error( "a array overflow" );
 163:                 }
 164:             }
 165:         /* we have found a spot */
 166: 
 167:         *p = *q2;
 168:         if( p > maxa ){
 169:             if( (maxa=p) > &a[ACTSIZE] ) error( "a array overflow" );
 170:             }
 171:         for( r=q1; r<q2; r+=2 ){
 172:             s = p + *r + 1;
 173:             *s = r[1];
 174:             }
 175: 
 176:         pgo[i] = p-a;
 177:         if( adb>1 ) fprintf( ftable, "Nonterminal %d, entry at %d\n" , i, pgo[i] );
 178:         goto nextgi;
 179: 
 180:         nextgp:  ;
 181:         }
 182: 
 183:     error( "cannot place goto %d\n", i );
 184: 
 185:     nextgi:  ;
 186:     }
 187: 
 188: stin(i){
 189:     register *r, *s, n, flag, j, *q1, *q2;
 190: 
 191:     greed[i] = 0;
 192: 
 193:     /* enter state i into the a array */
 194: 
 195:     q2 = mem+yypact[i+1];
 196:     q1 = mem+yypact[i];
 197:     /* find an acceptable place */
 198: 
 199:     for( n= -maxoff; n<ACTSIZE; ++n ){
 200: 
 201:         flag = 0;
 202:         for( r = q1; r < q2; r += 2 ){
 203:             if( (s = *r + n + a ) < a ) goto nextn;
 204:             if( *s == 0 ) ++flag;
 205:             else if( *s != r[1] ) goto nextn;
 206:             }
 207: 
 208:         /* check that the position equals another only if the states are identical */
 209: 
 210:         for( j=0; j<nstate; ++j ){
 211:             if( pa[j] == n ) {
 212:                 if( flag ) goto nextn;  /* we have some disagreement */
 213:                 if( yypact[j+1] + yypact[i] == yypact[j] + yypact[i+1] ){
 214:                     /* states are equal */
 215:                     pa[i] = n;
 216:                     if( adb>1 ) fprintf( ftable, "State %d: entry at %d equals state %d\n",
 217:                         i, n, j );
 218:                     return;
 219:                     }
 220:                 goto nextn;  /* we have some disagreement */
 221:                 }
 222:             }
 223: 
 224:         for( r = q1; r < q2; r += 2 ){
 225:             if( (s = *r + n + a ) >= &a[ACTSIZE] ) error( "out of space in optimizer a array" );
 226:             if( s > maxa ) maxa = s;
 227:             if( *s != 0 && *s != r[1] ) error( "clobber of a array, pos'n %d, by %d", s-a, r[1] );
 228:             *s = r[1];
 229:             }
 230:         pa[i] = n;
 231:         if( adb>1 ) fprintf( ftable, "State %d: entry at %d\n", i, pa[i] );
 232:         return;
 233: 
 234:         nextn:  ;
 235:         }
 236: 
 237:     error( "Error; failure to place state %d\n", i );
 238: 
 239:     }
 240: 
 241: nxti(){ /* finds the next i */
 242:     register i, max, maxi;
 243: 
 244:     max = 0;
 245: 
 246:     for( i=1; i<= nnonter; ++i ) if( ggreed[i] >= max ){
 247:         max = ggreed[i];
 248:         maxi = -i;
 249:         }
 250: 
 251:     for( i=0; i<nstate; ++i ) if( greed[i] >= max ){
 252:         max = greed[i];
 253:         maxi = i;
 254:         }
 255: 
 256:     if( nxdb ) fprintf( ftable, "nxti = %d, max = %d\n", maxi, max );
 257:     if( max==0 ) return( NOMORE );
 258:     else return( maxi );
 259:     }
 260: 
 261: osummary(){
 262:     /* write summary */
 263: 
 264:     register i, *p;
 265: 
 266:     if( foutput == NULL ) return;
 267:     i=0;
 268:     for( p=maxa; p>=a; --p ) {
 269:         if( *p == 0 ) ++i;
 270:         }
 271: 
 272:     fprintf( foutput, "Optimizer space used: input %d/%d, output %d/%d\n",
 273:         pmem-mem+1, MEMSIZE, maxa-a+1, ACTSIZE );
 274:     fprintf( foutput, "%d table entries, %d zero\n", (maxa-a)+1, i );
 275:     fprintf( foutput, "maximum spread: %d, maximum offset: %d\n", maxspr, maxoff );
 276: 
 277:     }
 278: 
 279: aoutput(){ /* this version is for C */
 280: 
 281: 
 282:     /* write out the optimized parser */
 283: 
 284:     fprintf( ftable, "# define YYLAST %d\n", maxa-a+1 );
 285: 
 286:     arout( "yyact", a, (maxa-a)+1 );
 287:     arout( "yypact", pa, nstate );
 288:     arout( "yypgo", pgo, nnonter+1 );
 289: 
 290:     }
 291: 
 292: arout( s, v, n ) char *s; int *v, n; {
 293: 
 294:     register i;
 295: 
 296:     fprintf( ftable, "short %s[]={\n", s );
 297:     for( i=0; i<n; ){
 298:         if( i%10 == 0 ) fprintf( ftable, "\n" );
 299:         fprintf( ftable, "%4d", v[i] );
 300:         if( ++i == n ) fprintf( ftable, " };\n" );
 301:         else fprintf( ftable, "," );
 302:         }
 303:     }
 304: 
 305: 
 306: gtnm(){
 307: 
 308:     register s, val, c;
 309: 
 310:     /* read and convert an integer from the standard input */
 311:     /* return the terminating character */
 312:     /* blanks, tabs, and newlines are ignored */
 313: 
 314:     s = 1;
 315:     val = 0;
 316: 
 317:     while( (c=getc(finput)) != EOF ){
 318:         if( isdigit(c) ){
 319:             val = val * 10 + c - '0';
 320:             }
 321:         else if ( c == '-' ) s = -1;
 322:         else break;
 323:         }
 324: 
 325:     *pmem++ = s*val;
 326:     if( pmem > &mem[MEMSIZE] ) error( "out of space" );
 327:     return( c );
 328: 
 329:     }

Defined functions

Defined variables

Defined macros