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