y4.c (9526B)
1 /* 2 * CDDL HEADER START 3 * 4 * The contents of this file are subject to the terms of the 5 * Common Development and Distribution License, Version 1.0 only 6 * (the "License"). You may not use this file except in compliance 7 * with the License. 8 * 9 * You can obtain a copy of the license at usr/src/OPENSOLARIS.LICENSE 10 * or http://www.opensolaris.org/os/licensing. 11 * See the License for the specific language governing permissions 12 * and limitations under the License. 13 * 14 * When distributing Covered Code, include this CDDL HEADER in each 15 * file and include the License file at usr/src/OPENSOLARIS.LICENSE. 16 * If applicable, add the following below this CDDL HEADER, with the 17 * fields enclosed by brackets "[]" replaced with your own identifying 18 * information: Portions Copyright [yyyy] [name of copyright owner] 19 * 20 * CDDL HEADER END 21 */ 22 /* 23 * Copyright 1990 Sun Microsystems, Inc. All rights reserved. 24 * Use is subject to license terms. 25 */ 26 27 /* Copyright (c) 1988 AT&T */ 28 /* All Rights Reserved */ 29 30 /* from OpenSolaris "y4.c 6.15 05/06/08 SMI" */ 31 32 /* 33 * Portions Copyright (c) 2005 Gunnar Ritter, Freiburg i. Br., Germany 34 * 35 * Sccsid @(#)y4.c 1.5 (gritter) 11/26/05 36 */ 37 38 #include "dextern" 39 #include <wchar.h> 40 #include <unistd.h> 41 #define NOMORE -1000 42 43 static void gin(int); 44 static void stin(int); 45 static void osummary(void); 46 static void aoutput(void); 47 static void arout(wchar_t *, int *, int); 48 static int nxti(void); 49 static int gtnm(void); 50 51 static int *ggreed; 52 static int *pgo; 53 static int *yypgo; 54 55 static int maxspr = 0; /* maximum spread of any entry */ 56 static int maxoff = 0; /* maximum offset into an array */ 57 int *optimmem; 58 static int *maxa; 59 60 static int nxdb = 0; 61 static int adb = 0; 62 63 void 64 callopt(void) 65 { 66 register int i, *p, j, k, *q; 67 68 ggreed = malloc(sizeof (int) * size); 69 pgo = malloc(sizeof (int) * size); 70 yypgo = &nontrst[0].tvalue; 71 72 /* read the arrays from tempfile and set parameters */ 73 74 if ((finput = fopen(TEMPNAME, "r")) == NULL) 75 error("optimizer cannot open tempfile"); 76 77 optimmem = tracemem; 78 pgo[0] = 0; 79 temp1[0] = 0; 80 nstate = 0; 81 nnonter = 0; 82 for (;;) { 83 switch (gtnm()) { 84 85 case L'\n': 86 temp1[++nstate] = (--optimmem) - tracemem; 87 /* FALLTHRU */ 88 89 case L',': 90 continue; 91 92 case L'$': 93 break; 94 95 default: 96 error("bad tempfile"); 97 } 98 break; 99 } 100 101 temp1[nstate] = yypgo[0] = (--optimmem) - tracemem; 102 103 for (;;) { 104 switch (gtnm()) { 105 106 case L'\n': 107 yypgo[++nnonter] = optimmem-tracemem; 108 /* FALLTHRU */ 109 case L',': 110 continue; 111 112 case EOF: 113 break; 114 115 default: 116 error("bad tempfile"); 117 } 118 break; 119 } 120 121 yypgo[nnonter--] = (--optimmem) - tracemem; 122 123 for (i = 0; i < nstate; ++i) { 124 k = 32000000; 125 j = 0; 126 q = tracemem + temp1[i+1]; 127 for (p = tracemem + temp1[i]; p < q; p += 2) { 128 if (*p > j) 129 j = *p; 130 if (*p < k) 131 k = *p; 132 } 133 if (k <= j) { 134 /* 135 * nontrivial situation 136 * temporarily, kill this for compatibility 137 */ 138 /* j -= k; j is now the range */ 139 if (k > maxoff) 140 maxoff = k; 141 } 142 tystate[i] = (temp1[i+1] - temp1[i]) + 2*j; 143 if (j > maxspr) 144 maxspr = j; 145 } 146 147 /* initialize ggreed table */ 148 for (i = 1; i <= nnonter; ++i) { 149 ggreed[i] = 1; 150 j = 0; 151 /* minimum entry index is always 0 */ 152 q = tracemem + yypgo[i+1] -1; 153 for (p = tracemem + yypgo[i]; p < q; p += 2) { 154 ggreed[i] += 2; 155 if (*p > j) 156 j = *p; 157 } 158 ggreed[i] = ggreed[i] + 2*j; 159 if (j > maxoff) 160 maxoff = j; 161 } 162 163 /* now, prepare to put the shift actions into the amem array */ 164 for (i = 0; i < new_actsize; ++i) 165 amem[i] = 0; 166 maxa = amem; 167 168 for (i = 0; i < nstate; ++i) { 169 if (tystate[i] == 0 && adb > 1) 170 fprintf(ftable, "State %d: null\n", i); 171 indgo[i] = YYFLAG1; 172 } 173 174 while ((i = nxti()) != NOMORE) { 175 if (i >= 0) 176 stin(i); 177 else 178 gin(-i); 179 } 180 181 if (adb > 2) { /* print a array */ 182 for (p = amem; p <= maxa; p += 10) { 183 fprintf(ftable, "%4d ", p-amem); 184 for (i = 0; i < 10; ++i) 185 fprintf(ftable, "%4d ", p[i]); 186 fprintf(ftable, "\n"); 187 } 188 } 189 /* write out the output appropriate to the language */ 190 aoutput(); 191 osummary(); 192 ZAPFILE(TEMPNAME); 193 } 194 195 static void 196 gin(int i) 197 { 198 register int *r, *s, *q1, *q2; 199 int *p; 200 201 /* enter gotos on nonterminal i into array amem */ 202 ggreed[i] = 0; 203 204 q2 = tracemem + yypgo[i+1] - 1; 205 q1 = tracemem + yypgo[i]; 206 207 /* now, find a place for it */ 208 209 /* for( p=amem; p < &amem[new_actsize]; ++p ){ */ 210 p = amem; 211 for (;;) { 212 while (p >= &amem[new_actsize]) 213 exp_act(&p); 214 if (*p) 215 goto nextgp; 216 for (r = q1; r < q2; r += 2) { 217 s = p + *r + 1; 218 /* 219 * Check if action table needs to 220 * be expanded or not. If so, 221 * expand it. 222 */ 223 while (s >= &amem[new_actsize]) { 224 exp_act(&p); 225 s = p + *r + 1; 226 } 227 if (*s) 228 goto nextgp; 229 if (s > maxa) { 230 while ((maxa = s) >= &amem[new_actsize]) 231 /* error( "amem array overflow" ); */ 232 exp_act(&p); 233 } 234 } 235 /* we have found a spot */ 236 *p = *q2; 237 if (p > maxa) { 238 while ((maxa = p) >= &amem[new_actsize]) 239 /* error("amem array overflow"); */ 240 exp_act(&p); 241 } 242 for (r = q1; r < q2; r += 2) { 243 s = p + *r + 1; 244 /* 245 * Check if action table needs to 246 * be expanded or not. If so, 247 * expand it. 248 */ 249 while (s >= &amem[new_actsize]) { 250 exp_act(&p); 251 s = p + *r + 1; 252 } 253 *s = r[1]; 254 } 255 256 pgo[i] = p - amem; 257 if (adb > 1) 258 fprintf(ftable, 259 "Nonterminal %d, entry at %d\n", i, pgo[i]); 260 goto nextgi; 261 262 nextgp: 263 ++p; 264 } 265 /* error( "cannot place goto %d\n", i ); */ 266 nextgi:; 267 } 268 269 static void 270 stin(int i) 271 { 272 register int *r, n, nn, flag, j, *q1, *q2; 273 int *s; 274 275 tystate[i] = 0; 276 277 /* Enter state i into the amem array */ 278 279 q2 = tracemem + temp1[i + 1]; 280 q1 = tracemem + temp1[i]; 281 /* Find an acceptable place */ 282 283 nn = -maxoff; 284 more: 285 for (n = nn; n < new_actsize; ++n) { 286 flag = 0; 287 for (r = q1; r < q2; r += 2) { 288 s = *r + n + amem; 289 if (s < amem) 290 goto nextn; 291 /* 292 * Check if action table needs to 293 * be expanded or not. If so, 294 * expand it. 295 */ 296 while (s >= &amem[new_actsize]) { 297 exp_act(NULL); 298 s = *r + n + amem; 299 } 300 if (*s == 0) 301 ++flag; 302 else if (*s != r[1]) 303 goto nextn; 304 } 305 306 /* 307 * check that the position equals another 308 * only if the states are identical 309 */ 310 for (j = 0; j < nstate; ++j) { 311 if (indgo[j] == n) { 312 if (flag) 313 /* 314 * we have some disagreement. 315 */ 316 goto nextn; 317 if (temp1[j+1] + temp1[i] == 318 temp1[j] + temp1[i+1]) { 319 /* states are equal */ 320 indgo[i] = n; 321 if (adb > 1) 322 fprintf(ftable, 323 "State %d: entry at" 324 " %d equals state %d\n", 325 i, n, j); 326 return; 327 } 328 goto nextn; /* we have some disagreement */ 329 } 330 } 331 332 for (r = q1; r < q2; r += 2) { 333 while ((s = *r + n + amem) >= &amem[new_actsize]) { 334 /* 335 * error( "out of space"); 336 */ 337 exp_act(NULL); 338 } 339 if (s > maxa) 340 maxa = s; 341 if (*s != 0 && *s != r[1]) 342 error( 343 "clobber of amem array, pos'n %d, by %d", 344 s-amem, r[1]); 345 *s = r[1]; 346 } 347 indgo[i] = n; 348 if (adb > 1) 349 fprintf(ftable, 350 "State %d: entry at %d\n", i, indgo[i]); 351 return; 352 nextn:; 353 } 354 355 /* error( "Error; failure to place state %d\n", i ); */ 356 exp_act(NULL); 357 nn = new_actsize - ACTSIZE; 358 goto more; 359 /* NOTREACHED */ 360 } 361 362 static int 363 nxti(void) 364 { 365 /* finds the next i */ 366 register int i, max, maxi = 0; 367 max = 0; 368 369 for (i = 1; i <= nnonter; ++i) 370 if (ggreed[i] >= max) { 371 max = ggreed[i]; 372 maxi = -i; 373 } 374 375 for (i = 0; i < nstate; ++i) 376 if (tystate[i] >= max) { 377 max = tystate[i]; 378 maxi = i; 379 } 380 if (nxdb) 381 fprintf(ftable, "nxti = %d, max = %d\n", maxi, max); 382 if (max == 0) 383 return (NOMORE); 384 else 385 return (maxi); 386 } 387 388 static void 389 osummary(void) 390 { 391 /* write summary */ 392 register int i, *p; 393 394 if (foutput == NULL) 395 return; 396 i = 0; 397 for (p = maxa; p >= amem; --p) { 398 if (*p == 0) 399 ++i; 400 } 401 402 fprintf(foutput, "Optimizer space used: input %d/%d, output %d/%d\n", 403 optimmem-tracemem + 1, new_memsize, maxa-amem + 1, new_actsize); 404 fprintf(foutput, "%d table entries, %d zero\n", (maxa-amem) + 1, i); 405 fprintf(foutput, 406 "maximum spread: %d, maximum offset: %d\n", maxspr, maxoff); 407 408 } 409 410 static void 411 aoutput(void) 412 { 413 /* this version is for C */ 414 /* write out the optimized parser */ 415 416 fprintf(ftable, "# define YYLAST %d\n", maxa-amem + 1); 417 arout(L"yyact", amem, (maxa - amem) + 1); 418 arout(L"yypact", indgo, nstate); 419 arout(L"yypgo", pgo, nnonter + 1); 420 } 421 422 static void 423 arout(wchar_t *s, int *v, int n) 424 { 425 register int i; 426 427 fprintf(ftable, "static YYCONST yytabelem %ls[]={\n", s); 428 for (i = 0; i < n; ) { 429 if (i % 10 == 0) 430 fprintf(ftable, "\n"); 431 fprintf(ftable, "%6d", v[i]); 432 if (++i == n) 433 fprintf(ftable, " };\n"); 434 else 435 fprintf(ftable, ","); 436 } 437 } 438 439 static int 440 gtnm(void) 441 { 442 register int s, val, c; 443 444 /* read and convert an integer from the standard input */ 445 /* return the terminating character */ 446 /* blanks, tabs, and newlines are ignored */ 447 448 s = 1; 449 val = 0; 450 451 while ((c = getwc(finput)) != EOF) { 452 if (iswdigit(c)) 453 val = val * 10 + c - L'0'; 454 else if (c == L'-') 455 s = -1; 456 else 457 break; 458 } 459 *optimmem++ = s*val; 460 if (optimmem >= &tracemem[new_memsize]) 461 exp_mem(0); 462 return (c); 463 } 464 465 void 466 exp_act(int **ptr) 467 { 468 static int *actbase; 469 int i; 470 new_actsize += ACTSIZE; 471 472 actbase = amem; 473 amem = realloc(amem, sizeof (int) * new_actsize); 474 if (amem == NULL) 475 error("couldn't expand action table"); 476 477 for (i = new_actsize-ACTSIZE; i < new_actsize; ++i) 478 amem[i] = 0; 479 if (ptr != NULL) 480 *ptr = *ptr - actbase + amem; 481 if (memp >= amem) 482 memp = memp - actbase + amem; 483 if (maxa >= amem) 484 maxa = maxa - actbase + amem; 485 }