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