1 /* $Id: lalr.c,v 1.14 2021/05/20 23:57:23 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 Value_t 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 187 goto_base = NEW2(nvars + 1, Value_t); 188 temp_base = NEW2(nvars + 1, Value_t); 189 190 goto_map = goto_base - ntokens; 191 temp_map = temp_base - ntokens; 192 193 ngotos = 0; 194 for (sp = first_shift; sp; sp = sp->next) 195 { 196 for (i = sp->nshifts - 1; i >= 0; i--) 197 { 198 symbol = accessing_symbol[sp->shift[i]]; 199 200 if (ISTOKEN(symbol)) 201 break; 202 203 if (ngotos == MAXYYINT) 204 fatal("too many gotos"); 205 206 ngotos++; 207 goto_map[symbol]++; 208 } 209 } 210 211 k = 0; 212 for (i = ntokens; i < nsyms; i++) 213 { 214 temp_map[i] = (Value_t)k; 215 k += goto_map[i]; 216 } 217 218 for (i = ntokens; i < nsyms; i++) 219 goto_map[i] = temp_map[i]; 220 221 goto_map[nsyms] = (Value_t)ngotos; 222 temp_map[nsyms] = (Value_t)ngotos; 223 224 from_state = NEW2(ngotos, Value_t); 225 to_state = NEW2(ngotos, Value_t); 226 227 for (sp = first_shift; sp; sp = sp->next) 228 { 229 Value_t state1 = sp->number; 230 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 low = goto_map[symbol]; 254 int high = goto_map[symbol + 1]; 255 256 for (;;) 257 { 258 int middle; 259 int s; 260 261 assert(low <= high); 262 middle = (low + high) >> 1; 263 s = from_state[middle]; 264 if (s == state) 265 return (Value_t)(middle); 266 else if (s < state) 267 low = middle + 1; 268 else 269 high = middle - 1; 270 } 271 } 272 273 static void 274 initialize_F(void) 275 { 276 int i; 277 int j; 278 int k; 279 shifts *sp; 280 Value_t *edge; 281 unsigned *rowp; 282 Value_t *rp; 283 Value_t **reads; 284 int nedges; 285 int symbol; 286 int nwords; 287 288 nwords = ngotos * tokensetsize; 289 F = NEW2(nwords, unsigned); 290 291 reads = NEW2(ngotos, Value_t *); 292 edge = NEW2(ngotos + 1, Value_t); 293 nedges = 0; 294 295 rowp = F; 296 for (i = 0; i < ngotos; i++) 297 { 298 int stateno = to_state[i]; 299 300 sp = shift_table[stateno]; 301 302 if (sp) 303 { 304 k = sp->nshifts; 305 306 for (j = 0; j < k; j++) 307 { 308 symbol = accessing_symbol[sp->shift[j]]; 309 if (ISVAR(symbol)) 310 break; 311 SETBIT(rowp, symbol); 312 } 313 314 for (; j < k; j++) 315 { 316 symbol = accessing_symbol[sp->shift[j]]; 317 if (nullable[symbol]) 318 edge[nedges++] = map_goto(stateno, symbol); 319 } 320 321 if (nedges) 322 { 323 reads[i] = rp = NEW2(nedges + 1, Value_t); 324 325 for (j = 0; j < nedges; j++) 326 rp[j] = edge[j]; 327 328 rp[nedges] = -1; 329 nedges = 0; 330 } 331 } 332 333 rowp += tokensetsize; 334 } 335 336 SETBIT(F, 0); 337 digraph(reads); 338 339 for (i = 0; i < ngotos; i++) 340 { 341 if (reads[i]) 342 FREE(reads[i]); 343 } 344 345 FREE(reads); 346 FREE(edge); 347 } 348 349 static void 350 build_relations(void) 351 { 352 int i; 353 int j; 354 int k; 355 Value_t *rulep; 356 Value_t *rp; 357 shifts *sp; 358 int length; 359 int done_flag; 360 Value_t stateno; 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 int nedges = 0; 374 int symbol1 = accessing_symbol[to_state[i]]; 375 Value_t state1 = from_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 474 nedges = NEW2(n, Value_t); 475 476 for (i = 0; i < n; i++) 477 { 478 sp = R2[i]; 479 if (sp) 480 { 481 while (*sp >= 0) 482 nedges[*sp++]++; 483 } 484 } 485 486 new_R = NEW2(n, Value_t *); 487 temp_R = NEW2(n, Value_t *); 488 489 for (i = 0; i < n; i++) 490 { 491 int k = nedges[i]; 492 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 if (includes != 0) 645 { 646 int i; 647 648 for (i = 0; i < ngotos; i++) 649 { 650 free(includes[i]); 651 } 652 DO_FREE(includes); 653 } 654 } 655 #endif 656