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