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