1 /* $OpenBSD: lalr.c,v 1.17 2014/05/17 15:19:17 chl Exp $ */ 2 /* $NetBSD: lalr.c,v 1.4 1996/03/19 03:21:33 jtc Exp $ */ 3 4 /* 5 * Copyright (c) 1989 The Regents of the University of California. 6 * All rights reserved. 7 * 8 * This code is derived from software contributed to Berkeley by 9 * Robert Paul Corbett. 10 * 11 * Redistribution and use in source and binary forms, with or without 12 * modification, are permitted provided that the following conditions 13 * are met: 14 * 1. Redistributions of source code must retain the above copyright 15 * notice, this list of conditions and the following disclaimer. 16 * 2. Redistributions in binary form must reproduce the above copyright 17 * notice, this list of conditions and the following disclaimer in the 18 * documentation and/or other materials provided with the distribution. 19 * 3. Neither the name of the University nor the names of its contributors 20 * may be used to endorse or promote products derived from this software 21 * without specific prior written permission. 22 * 23 * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND 24 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 25 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE 26 * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE 27 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL 28 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS 29 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) 30 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT 31 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY 32 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF 33 * SUCH DAMAGE. 34 */ 35 36 #include "defs.h" 37 38 typedef struct shorts { 39 struct shorts *next; 40 short value; 41 } shorts; 42 43 int tokensetsize; 44 short *lookaheads; 45 short *LAruleno; 46 unsigned *LA; 47 short *accessing_symbol; 48 core **state_table; 49 shifts **shift_table; 50 reductions **reduction_table; 51 short *goto_map; 52 short *from_state; 53 short *to_state; 54 55 short **transpose(); 56 void set_state_table(void); 57 void set_accessing_symbol(void); 58 void set_shift_table(void); 59 void set_reduction_table(void); 60 void set_maxrhs(void); 61 void initialize_LA(void); 62 void set_goto_map(void); 63 void initialize_F(void); 64 void build_relations(void); 65 void compute_FOLLOWS(void); 66 void compute_lookaheads(void); 67 int map_goto(int, int); 68 void digraph(short **); 69 void add_lookback_edge(int, int, int); 70 void traverse(int); 71 72 static int infinity; 73 static int maxrhs; 74 static int ngotos; 75 static unsigned *F; 76 static short **includes; 77 static shorts **lookback; 78 static short **R; 79 static short *INDEX; 80 static short *VERTICES; 81 static int top; 82 83 void 84 lalr(void) 85 { 86 tokensetsize = WORDSIZE(ntokens); 87 88 set_state_table(); 89 set_accessing_symbol(); 90 set_shift_table(); 91 set_reduction_table(); 92 set_maxrhs(); 93 initialize_LA(); 94 set_goto_map(); 95 initialize_F(); 96 build_relations(); 97 compute_FOLLOWS(); 98 compute_lookaheads(); 99 free_derives(); 100 free_nullable(); 101 } 102 103 104 void 105 set_state_table(void) 106 { 107 core *sp; 108 109 state_table = NEW2(nstates, core *); 110 for (sp = first_state; sp; sp = sp->next) 111 state_table[sp->number] = sp; 112 } 113 114 115 void 116 set_accessing_symbol(void) 117 { 118 core *sp; 119 120 accessing_symbol = NEW2(nstates, short); 121 for (sp = first_state; sp; sp = sp->next) 122 accessing_symbol[sp->number] = sp->accessing_symbol; 123 } 124 125 126 void 127 set_shift_table(void) 128 { 129 shifts *sp; 130 131 shift_table = NEW2(nstates, shifts *); 132 for (sp = first_shift; sp; sp = sp->next) 133 shift_table[sp->number] = sp; 134 } 135 136 137 void 138 set_reduction_table(void) 139 { 140 reductions *rp; 141 142 reduction_table = NEW2(nstates, reductions *); 143 for (rp = first_reduction; rp; rp = rp->next) 144 reduction_table[rp->number] = rp; 145 } 146 147 148 void 149 set_maxrhs(void) 150 { 151 short *itemp, *item_end; 152 int length, max; 153 154 length = 0; 155 max = 0; 156 item_end = ritem + nitems; 157 for (itemp = ritem; itemp < item_end; itemp++) { 158 if (*itemp >= 0) { 159 length++; 160 } else { 161 if (length > max) max = length; 162 length = 0; 163 } 164 } 165 166 maxrhs = max; 167 } 168 169 170 void 171 initialize_LA(void) 172 { 173 int i, j, k; 174 reductions *rp; 175 176 lookaheads = NEW2(nstates + 1, short); 177 178 k = 0; 179 for (i = 0; i < nstates; i++) { 180 lookaheads[i] = k; 181 rp = reduction_table[i]; 182 if (rp) 183 k += rp->nreds; 184 } 185 lookaheads[nstates] = k; 186 187 LA = NEW2(k * tokensetsize, unsigned); 188 LAruleno = NEW2(k, short); 189 lookback = NEW2(k, shorts *); 190 191 k = 0; 192 for (i = 0; i < nstates; i++) { 193 rp = reduction_table[i]; 194 if (rp) { 195 for (j = 0; j < rp->nreds; j++) { 196 LAruleno[k] = rp->rules[j]; 197 k++; 198 } 199 } 200 } 201 } 202 203 void 204 set_goto_map(void) 205 { 206 shifts *sp; 207 int i, k, symbol; 208 int state1, state2; 209 short *temp_map; 210 211 goto_map = NEW2(nvars + 1, short) - ntokens; 212 temp_map = NEW2(nvars + 1, short) - ntokens; 213 214 ngotos = 0; 215 for (sp = first_shift; sp; sp = sp->next) { 216 for (i = sp->nshifts - 1; i >= 0; i--) { 217 symbol = accessing_symbol[sp->shift[i]]; 218 219 if (ISTOKEN(symbol)) break; 220 221 if (ngotos == MAXSHORT) 222 fatal("too many gotos"); 223 224 ngotos++; 225 goto_map[symbol]++; 226 } 227 } 228 229 k = 0; 230 for (i = ntokens; i < nsyms; i++) { 231 temp_map[i] = k; 232 k += goto_map[i]; 233 } 234 235 for (i = ntokens; i < nsyms; i++) 236 goto_map[i] = temp_map[i]; 237 238 goto_map[nsyms] = ngotos; 239 temp_map[nsyms] = ngotos; 240 241 from_state = NEW2(ngotos, short); 242 to_state = NEW2(ngotos, short); 243 244 for (sp = first_shift; sp; sp = sp->next) { 245 state1 = sp->number; 246 for (i = sp->nshifts - 1; i >= 0; i--) { 247 state2 = sp->shift[i]; 248 symbol = accessing_symbol[state2]; 249 250 if (ISTOKEN(symbol)) break; 251 252 k = temp_map[symbol]++; 253 from_state[k] = state1; 254 to_state[k] = state2; 255 } 256 } 257 258 free(temp_map + ntokens); 259 } 260 261 262 263 /* Map_goto maps a state/symbol pair into its numeric representation. */ 264 265 int 266 map_goto(int state, int symbol) 267 { 268 int high, low, middle, s; 269 270 low = goto_map[symbol]; 271 high = goto_map[symbol + 1]; 272 273 for (;;) { 274 assert(low <= high); 275 middle = (low + high) >> 1; 276 s = from_state[middle]; 277 if (s == state) 278 return (middle); 279 else if (s < state) 280 low = middle + 1; 281 else 282 high = middle - 1; 283 } 284 } 285 286 287 void 288 initialize_F(void) 289 { 290 int i, j, k; 291 shifts *sp; 292 short *edge, *rp, **reads; 293 unsigned int *rowp; 294 int nedges, stateno, symbol, nwords; 295 296 nwords = ngotos * tokensetsize; 297 F = NEW2(nwords, unsigned); 298 299 reads = NEW2(ngotos, short *); 300 edge = NEW2(ngotos + 1, short); 301 nedges = 0; 302 303 rowp = F; 304 for (i = 0; i < ngotos; i++) { 305 stateno = to_state[i]; 306 sp = shift_table[stateno]; 307 308 if (sp) { 309 k = sp->nshifts; 310 311 for (j = 0; j < k; j++) { 312 symbol = accessing_symbol[sp->shift[j]]; 313 if (ISVAR(symbol)) 314 break; 315 SETBIT(rowp, symbol); 316 } 317 318 for (; j < k; j++) { 319 symbol = accessing_symbol[sp->shift[j]]; 320 if (nullable[symbol]) 321 edge[nedges++] = map_goto(stateno, symbol); 322 } 323 324 if (nedges) { 325 reads[i] = rp = NEW2(nedges + 1, short); 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 if (reads[i]) 343 free(reads[i]); 344 } 345 346 free(reads); 347 free(edge); 348 } 349 350 351 void 352 build_relations(void) 353 { 354 int i, j, k; 355 short *rulep, *rp; 356 shifts *sp; 357 int length, nedges, done; 358 int state1, stateno, symbol1, symbol2; 359 short *shortp, *edge, *states; 360 short **new_includes; 361 362 includes = NEW2(ngotos, short *); 363 edge = NEW2(ngotos + 1, short); 364 states = NEW2(maxrhs + 1, short); 365 366 for (i = 0; i < ngotos; i++) { 367 nedges = 0; 368 state1 = from_state[i]; 369 symbol1 = accessing_symbol[to_state[i]]; 370 371 for (rulep = derives[symbol1]; *rulep >= 0; rulep++) { 372 length = 1; 373 states[0] = state1; 374 stateno = state1; 375 376 for (rp = ritem + rrhs[*rulep]; *rp >= 0; rp++) { 377 symbol2 = *rp; 378 sp = shift_table[stateno]; 379 k = sp->nshifts; 380 381 for (j = 0; j < k; j++) { 382 stateno = sp->shift[j]; 383 if (accessing_symbol[stateno] == symbol2) 384 break; 385 } 386 387 states[length++] = stateno; 388 } 389 390 add_lookback_edge(stateno, *rulep, i); 391 392 length--; 393 done = 0; 394 while (!done) { 395 done = 1; 396 rp--; 397 if (ISVAR(*rp)) { 398 stateno = states[--length]; 399 edge[nedges++] = map_goto(stateno, *rp); 400 if (nullable[*rp] && length > 0) 401 done = 0; 402 } 403 } 404 } 405 406 if (nedges) { 407 includes[i] = shortp = NEW2(nedges + 1, short); 408 for (j = 0; j < nedges; j++) 409 shortp[j] = edge[j]; 410 shortp[nedges] = -1; 411 } 412 } 413 414 new_includes = transpose(includes, ngotos); 415 416 for (i = 0; i < ngotos; i++) 417 if (includes[i]) 418 free(includes[i]); 419 420 free(includes); 421 422 includes = new_includes; 423 424 free(edge); 425 free(states); 426 } 427 428 void 429 add_lookback_edge(int stateno, int ruleno, int gotono) 430 { 431 int i, k, found; 432 shorts *sp; 433 434 i = lookaheads[stateno]; 435 k = lookaheads[stateno + 1]; 436 found = 0; 437 while (!found && i < k) { 438 if (LAruleno[i] == ruleno) 439 found = 1; 440 else 441 ++i; 442 } 443 assert(found); 444 445 sp = NEW(shorts); 446 sp->next = lookback[i]; 447 sp->value = gotono; 448 lookback[i] = sp; 449 } 450 451 452 453 short ** 454 transpose(short **R, int n) 455 { 456 short **new_R, **temp_R, *nedges, *sp; 457 int i, k; 458 459 nedges = NEW2(n, short); 460 461 for (i = 0; i < n; i++) { 462 sp = R[i]; 463 if (sp) { 464 while (*sp >= 0) 465 nedges[*sp++]++; 466 } 467 } 468 469 new_R = NEW2(n, short *); 470 temp_R = NEW2(n, short *); 471 472 for (i = 0; i < n; i++) { 473 k = nedges[i]; 474 if (k > 0) { 475 sp = NEW2(k + 1, short); 476 new_R[i] = sp; 477 temp_R[i] = sp; 478 sp[k] = -1; 479 } 480 } 481 482 free(nedges); 483 484 for (i = 0; i < n; i++) { 485 sp = R[i]; 486 if (sp) { 487 while (*sp >= 0) 488 *temp_R[*sp++]++ = i; 489 } 490 } 491 492 free(temp_R); 493 494 return (new_R); 495 } 496 497 498 void 499 compute_FOLLOWS(void) 500 { 501 digraph(includes); 502 } 503 504 void 505 compute_lookaheads(void) 506 { 507 int i, n; 508 unsigned int *fp1, *fp2, *fp3; 509 shorts *sp, *next; 510 unsigned int *rowp; 511 512 rowp = LA; 513 n = lookaheads[nstates]; 514 for (i = 0; i < n; i++) { 515 fp3 = rowp + tokensetsize; 516 for (sp = lookback[i]; sp; sp = sp->next) { 517 fp1 = rowp; 518 fp2 = F + tokensetsize * sp->value; 519 while (fp1 < fp3) 520 *fp1++ |= *fp2++; 521 } 522 rowp = fp3; 523 } 524 525 for (i = 0; i < n; i++) 526 for (sp = lookback[i]; sp; sp = next) { 527 next = sp->next; 528 free(sp); 529 } 530 531 free(lookback); 532 free(F); 533 } 534 535 void 536 digraph(short **relation) 537 { 538 int i; 539 540 infinity = ngotos + 2; 541 INDEX = NEW2(ngotos + 1, short); 542 VERTICES = NEW2(ngotos + 1, short); 543 top = 0; 544 R = relation; 545 546 memset(INDEX, 0, ngotos * sizeof(short)); 547 for (i = 0; i < ngotos; i++) 548 if (R[i]) 549 traverse(i); 550 551 free(INDEX); 552 free(VERTICES); 553 } 554 555 556 void 557 traverse(int i) 558 { 559 unsigned int *base, *fp1, *fp2, *fp3; 560 int j, height; 561 short *rp; 562 563 VERTICES[++top] = i; 564 INDEX[i] = height = top; 565 566 base = F + i * tokensetsize; 567 fp3 = base + tokensetsize; 568 569 rp = R[i]; 570 if (rp) { 571 while ((j = *rp++) >= 0) { 572 if (INDEX[j] == 0) 573 traverse(j); 574 575 if (INDEX[i] > INDEX[j]) 576 INDEX[i] = INDEX[j]; 577 578 fp1 = base; 579 fp2 = F + j * tokensetsize; 580 581 while (fp1 < fp3) 582 *fp1++ |= *fp2++; 583 } 584 } 585 586 if (INDEX[i] == height) { 587 for (;;) { 588 j = VERTICES[top--]; 589 INDEX[j] = infinity; 590 591 if (i == j) 592 break; 593 594 fp1 = base; 595 fp2 = F + j * tokensetsize; 596 597 while (fp1 < fp3) 598 *fp2++ = *fp1++; 599 } 600 } 601 } 602