1 #ifndef lint 2 static char sccsid[] = "@(#)y4.c 4.1 (Berkeley) 02/11/83"; 3 #endif not lint 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 } 330