1 /* $Id: lalr.c,v 1.9 2009/10/27 09:49:27 tom Exp $ */ 2 3 #include "defs.h" 4 5 typedef struct shorts 6 { 7 struct shorts *next; 8 Value_t value; 9 } 10 shorts; 11 12 static Value_t map_goto(int state, int symbol); 13 static Value_t **transpose(Value_t ** R, int n); 14 static void add_lookback_edge(int stateno, int ruleno, int gotono); 15 static void build_relations(void); 16 static void compute_FOLLOWS(void); 17 static void compute_lookaheads(void); 18 static void digraph(Value_t ** relation); 19 static void initialize_F(void); 20 static void initialize_LA(void); 21 static void set_accessing_symbol(void); 22 static void set_goto_map(void); 23 static void set_maxrhs(void); 24 static void set_reduction_table(void); 25 static void set_shift_table(void); 26 static void set_state_table(void); 27 static void traverse(int i); 28 29 static int tokensetsize; 30 Value_t *lookaheads; 31 Value_t *LAruleno; 32 unsigned *LA; 33 Value_t *accessing_symbol; 34 core **state_table; 35 shifts **shift_table; 36 reductions **reduction_table; 37 Value_t *goto_map; 38 Value_t *from_state; 39 Value_t *to_state; 40 41 static Value_t infinity; 42 static int maxrhs; 43 static int ngotos; 44 static unsigned *F; 45 static Value_t **includes; 46 static shorts **lookback; 47 static Value_t **R; 48 static Value_t *INDEX; 49 static Value_t *VERTICES; 50 static Value_t top; 51 52 void 53 lalr(void) 54 { 55 tokensetsize = WORDSIZE(ntokens); 56 57 set_state_table(); 58 set_accessing_symbol(); 59 set_shift_table(); 60 set_reduction_table(); 61 set_maxrhs(); 62 initialize_LA(); 63 set_goto_map(); 64 initialize_F(); 65 build_relations(); 66 compute_FOLLOWS(); 67 compute_lookaheads(); 68 } 69 70 static void 71 set_state_table(void) 72 { 73 core *sp; 74 75 state_table = NEW2(nstates, core *); 76 for (sp = first_state; sp; sp = sp->next) 77 state_table[sp->number] = sp; 78 } 79 80 static void 81 set_accessing_symbol(void) 82 { 83 core *sp; 84 85 accessing_symbol = NEW2(nstates, Value_t); 86 for (sp = first_state; sp; sp = sp->next) 87 accessing_symbol[sp->number] = sp->accessing_symbol; 88 } 89 90 static void 91 set_shift_table(void) 92 { 93 shifts *sp; 94 95 shift_table = NEW2(nstates, shifts *); 96 for (sp = first_shift; sp; sp = sp->next) 97 shift_table[sp->number] = sp; 98 } 99 100 static void 101 set_reduction_table(void) 102 { 103 reductions *rp; 104 105 reduction_table = NEW2(nstates, reductions *); 106 for (rp = first_reduction; rp; rp = rp->next) 107 reduction_table[rp->number] = rp; 108 } 109 110 static void 111 set_maxrhs(void) 112 { 113 Value_t *itemp; 114 Value_t *item_end; 115 int length; 116 int max; 117 118 length = 0; 119 max = 0; 120 item_end = ritem + nitems; 121 for (itemp = ritem; itemp < item_end; itemp++) 122 { 123 if (*itemp >= 0) 124 { 125 length++; 126 } 127 else 128 { 129 if (length > max) 130 max = length; 131 length = 0; 132 } 133 } 134 135 maxrhs = max; 136 } 137 138 static void 139 initialize_LA(void) 140 { 141 int i, j, k; 142 reductions *rp; 143 144 lookaheads = NEW2(nstates + 1, Value_t); 145 146 k = 0; 147 for (i = 0; i < nstates; i++) 148 { 149 lookaheads[i] = (Value_t) k; 150 rp = reduction_table[i]; 151 if (rp) 152 k += rp->nreds; 153 } 154 lookaheads[nstates] = (Value_t) k; 155 156 LA = NEW2(k * tokensetsize, unsigned); 157 LAruleno = NEW2(k, Value_t); 158 lookback = NEW2(k, shorts *); 159 160 k = 0; 161 for (i = 0; i < nstates; i++) 162 { 163 rp = reduction_table[i]; 164 if (rp) 165 { 166 for (j = 0; j < rp->nreds; j++) 167 { 168 LAruleno[k] = rp->rules[j]; 169 k++; 170 } 171 } 172 } 173 } 174 175 static void 176 set_goto_map(void) 177 { 178 shifts *sp; 179 int i; 180 int symbol; 181 int k; 182 Value_t *temp_map; 183 Value_t state2; 184 Value_t state1; 185 186 goto_map = NEW2(nvars + 1, Value_t) - ntokens; 187 temp_map = NEW2(nvars + 1, Value_t) - ntokens; 188 189 ngotos = 0; 190 for (sp = first_shift; sp; sp = sp->next) 191 { 192 for (i = sp->nshifts - 1; i >= 0; i--) 193 { 194 symbol = accessing_symbol[sp->shift[i]]; 195 196 if (ISTOKEN(symbol)) 197 break; 198 199 if (ngotos == MAXSHORT) 200 fatal("too many gotos"); 201 202 ngotos++; 203 goto_map[symbol]++; 204 } 205 } 206 207 k = 0; 208 for (i = ntokens; i < nsyms; i++) 209 { 210 temp_map[i] = (Value_t) k; 211 k += goto_map[i]; 212 } 213 214 for (i = ntokens; i < nsyms; i++) 215 goto_map[i] = temp_map[i]; 216 217 goto_map[nsyms] = (Value_t) ngotos; 218 temp_map[nsyms] = (Value_t) ngotos; 219 220 from_state = NEW2(ngotos, Value_t); 221 to_state = NEW2(ngotos, Value_t); 222 223 for (sp = first_shift; sp; sp = sp->next) 224 { 225 state1 = sp->number; 226 for (i = sp->nshifts - 1; i >= 0; i--) 227 { 228 state2 = sp->shift[i]; 229 symbol = accessing_symbol[state2]; 230 231 if (ISTOKEN(symbol)) 232 break; 233 234 k = temp_map[symbol]++; 235 from_state[k] = state1; 236 to_state[k] = state2; 237 } 238 } 239 240 FREE(temp_map + ntokens); 241 } 242 243 /* Map_goto maps a state/symbol pair into its numeric representation. */ 244 245 static Value_t 246 map_goto(int state, int symbol) 247 { 248 int high; 249 int low; 250 int middle; 251 int s; 252 253 low = goto_map[symbol]; 254 high = goto_map[symbol + 1]; 255 256 for (;;) 257 { 258 assert(low <= high); 259 middle = (low + high) >> 1; 260 s = from_state[middle]; 261 if (s == state) 262 return (Value_t) (middle); 263 else if (s < state) 264 low = middle + 1; 265 else 266 high = middle - 1; 267 } 268 } 269 270 static void 271 initialize_F(void) 272 { 273 int i; 274 int j; 275 int k; 276 shifts *sp; 277 Value_t *edge; 278 unsigned *rowp; 279 Value_t *rp; 280 Value_t **reads; 281 int nedges; 282 int stateno; 283 int symbol; 284 int nwords; 285 286 nwords = ngotos * tokensetsize; 287 F = NEW2(nwords, unsigned); 288 289 reads = NEW2(ngotos, Value_t *); 290 edge = NEW2(ngotos + 1, Value_t); 291 nedges = 0; 292 293 rowp = F; 294 for (i = 0; i < ngotos; i++) 295 { 296 stateno = to_state[i]; 297 sp = shift_table[stateno]; 298 299 if (sp) 300 { 301 k = sp->nshifts; 302 303 for (j = 0; j < k; j++) 304 { 305 symbol = accessing_symbol[sp->shift[j]]; 306 if (ISVAR(symbol)) 307 break; 308 SETBIT(rowp, symbol); 309 } 310 311 for (; j < k; j++) 312 { 313 symbol = accessing_symbol[sp->shift[j]]; 314 if (nullable[symbol]) 315 edge[nedges++] = map_goto(stateno, symbol); 316 } 317 318 if (nedges) 319 { 320 reads[i] = rp = NEW2(nedges + 1, Value_t); 321 322 for (j = 0; j < nedges; j++) 323 rp[j] = edge[j]; 324 325 rp[nedges] = -1; 326 nedges = 0; 327 } 328 } 329 330 rowp += tokensetsize; 331 } 332 333 SETBIT(F, 0); 334 digraph(reads); 335 336 for (i = 0; i < ngotos; i++) 337 { 338 if (reads[i]) 339 FREE(reads[i]); 340 } 341 342 FREE(reads); 343 FREE(edge); 344 } 345 346 static void 347 build_relations(void) 348 { 349 int i; 350 int j; 351 int k; 352 Value_t *rulep; 353 Value_t *rp; 354 shifts *sp; 355 int length; 356 int nedges; 357 int done_flag; 358 Value_t state1; 359 Value_t stateno; 360 int symbol1; 361 int symbol2; 362 Value_t *shortp; 363 Value_t *edge; 364 Value_t *states; 365 Value_t **new_includes; 366 367 includes = NEW2(ngotos, Value_t *); 368 edge = NEW2(ngotos + 1, Value_t); 369 states = NEW2(maxrhs + 1, Value_t); 370 371 for (i = 0; i < ngotos; i++) 372 { 373 nedges = 0; 374 state1 = from_state[i]; 375 symbol1 = accessing_symbol[to_state[i]]; 376 377 for (rulep = derives[symbol1]; *rulep >= 0; rulep++) 378 { 379 length = 1; 380 states[0] = state1; 381 stateno = state1; 382 383 for (rp = ritem + rrhs[*rulep]; *rp >= 0; rp++) 384 { 385 symbol2 = *rp; 386 sp = shift_table[stateno]; 387 k = sp->nshifts; 388 389 for (j = 0; j < k; j++) 390 { 391 stateno = sp->shift[j]; 392 if (accessing_symbol[stateno] == symbol2) 393 break; 394 } 395 396 states[length++] = stateno; 397 } 398 399 add_lookback_edge(stateno, *rulep, i); 400 401 length--; 402 done_flag = 0; 403 while (!done_flag) 404 { 405 done_flag = 1; 406 rp--; 407 if (ISVAR(*rp)) 408 { 409 stateno = states[--length]; 410 edge[nedges++] = map_goto(stateno, *rp); 411 if (nullable[*rp] && length > 0) 412 done_flag = 0; 413 } 414 } 415 } 416 417 if (nedges) 418 { 419 includes[i] = shortp = NEW2(nedges + 1, Value_t); 420 for (j = 0; j < nedges; j++) 421 shortp[j] = edge[j]; 422 shortp[nedges] = -1; 423 } 424 } 425 426 new_includes = transpose(includes, ngotos); 427 428 for (i = 0; i < ngotos; i++) 429 if (includes[i]) 430 FREE(includes[i]); 431 432 FREE(includes); 433 434 includes = new_includes; 435 436 FREE(edge); 437 FREE(states); 438 } 439 440 static void 441 add_lookback_edge(int stateno, int ruleno, int gotono) 442 { 443 int i, k; 444 int found; 445 shorts *sp; 446 447 i = lookaheads[stateno]; 448 k = lookaheads[stateno + 1]; 449 found = 0; 450 while (!found && i < k) 451 { 452 if (LAruleno[i] == ruleno) 453 found = 1; 454 else 455 ++i; 456 } 457 assert(found); 458 459 sp = NEW(shorts); 460 sp->next = lookback[i]; 461 sp->value = (Value_t) gotono; 462 lookback[i] = sp; 463 } 464 465 static Value_t ** 466 transpose(Value_t ** R2, int n) 467 { 468 Value_t **new_R; 469 Value_t **temp_R; 470 Value_t *nedges; 471 Value_t *sp; 472 int i; 473 int k; 474 475 nedges = NEW2(n, Value_t); 476 477 for (i = 0; i < n; i++) 478 { 479 sp = R2[i]; 480 if (sp) 481 { 482 while (*sp >= 0) 483 nedges[*sp++]++; 484 } 485 } 486 487 new_R = NEW2(n, Value_t *); 488 temp_R = NEW2(n, Value_t *); 489 490 for (i = 0; i < n; i++) 491 { 492 k = nedges[i]; 493 if (k > 0) 494 { 495 sp = NEW2(k + 1, Value_t); 496 new_R[i] = sp; 497 temp_R[i] = sp; 498 sp[k] = -1; 499 } 500 } 501 502 FREE(nedges); 503 504 for (i = 0; i < n; i++) 505 { 506 sp = R2[i]; 507 if (sp) 508 { 509 while (*sp >= 0) 510 *temp_R[*sp++]++ = (Value_t) i; 511 } 512 } 513 514 FREE(temp_R); 515 516 return (new_R); 517 } 518 519 static void 520 compute_FOLLOWS(void) 521 { 522 digraph(includes); 523 } 524 525 static void 526 compute_lookaheads(void) 527 { 528 int i, n; 529 unsigned *fp1, *fp2, *fp3; 530 shorts *sp, *next; 531 unsigned *rowp; 532 533 rowp = LA; 534 n = lookaheads[nstates]; 535 for (i = 0; i < n; i++) 536 { 537 fp3 = rowp + tokensetsize; 538 for (sp = lookback[i]; sp; sp = sp->next) 539 { 540 fp1 = rowp; 541 fp2 = F + tokensetsize * sp->value; 542 while (fp1 < fp3) 543 *fp1++ |= *fp2++; 544 } 545 rowp = fp3; 546 } 547 548 for (i = 0; i < n; i++) 549 for (sp = lookback[i]; sp; sp = next) 550 { 551 next = sp->next; 552 FREE(sp); 553 } 554 555 FREE(lookback); 556 FREE(F); 557 } 558 559 static void 560 digraph(Value_t ** relation) 561 { 562 int i; 563 564 infinity = (Value_t) (ngotos + 2); 565 INDEX = NEW2(ngotos + 1, Value_t); 566 VERTICES = NEW2(ngotos + 1, Value_t); 567 top = 0; 568 569 R = relation; 570 571 for (i = 0; i < ngotos; i++) 572 INDEX[i] = 0; 573 574 for (i = 0; i < ngotos; i++) 575 { 576 if (INDEX[i] == 0 && R[i]) 577 traverse(i); 578 } 579 580 FREE(INDEX); 581 FREE(VERTICES); 582 } 583 584 static void 585 traverse(int i) 586 { 587 unsigned *fp1; 588 unsigned *fp2; 589 unsigned *fp3; 590 int j; 591 Value_t *rp; 592 593 Value_t height; 594 unsigned *base; 595 596 VERTICES[++top] = (Value_t) i; 597 INDEX[i] = height = top; 598 599 base = F + i * tokensetsize; 600 fp3 = base + tokensetsize; 601 602 rp = R[i]; 603 if (rp) 604 { 605 while ((j = *rp++) >= 0) 606 { 607 if (INDEX[j] == 0) 608 traverse(j); 609 610 if (INDEX[i] > INDEX[j]) 611 INDEX[i] = INDEX[j]; 612 613 fp1 = base; 614 fp2 = F + j * tokensetsize; 615 616 while (fp1 < fp3) 617 *fp1++ |= *fp2++; 618 } 619 } 620 621 if (INDEX[i] == height) 622 { 623 for (;;) 624 { 625 j = VERTICES[top--]; 626 INDEX[j] = infinity; 627 628 if (i == j) 629 break; 630 631 fp1 = base; 632 fp2 = F + j * tokensetsize; 633 634 while (fp1 < fp3) 635 *fp2++ = *fp1++; 636 } 637 } 638 } 639 640 #ifdef NO_LEAKS 641 void 642 lalr_leaks(void) 643 { 644 int i; 645 646 if (includes != 0) 647 { 648 for (i = 0; i < ngotos; i++) 649 { 650 free(includes[i]); 651 } 652 DO_FREE(includes); 653 } 654 } 655 #endif 656