2.9BSD - /usr/src/cmd/yacc/y4.c

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

Defined functions

Defined variables

Defined macros