1 /* $OpenBSD: lr0.c,v 1.11 2011/04/03 20:42:54 nicm Exp $ */ 2 /* $NetBSD: lr0.c,v 1.4 1996/03/19 03:21:35 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 extern short *itemset; 39 extern short *itemsetend; 40 extern unsigned *ruleset; 41 42 int nstates; 43 core *first_state; 44 shifts *first_shift; 45 reductions *first_reduction; 46 47 int get_state(int); 48 core *new_state(int); 49 50 void allocate_itemsets(void); 51 void allocate_storage(void); 52 void append_states(void); 53 void free_storage(void); 54 void generate_states(void); 55 void initialize_states(void); 56 void new_itemsets(void); 57 void save_shifts(void); 58 void save_reductions(void); 59 void set_derives(void); 60 void print_derives(void); 61 void set_nullable(void); 62 63 static core **state_set; 64 static core *this_state; 65 static core *last_state; 66 static shifts *last_shift; 67 static reductions *last_reduction; 68 69 static int nshifts; 70 static short *shift_symbol; 71 72 static short *redset; 73 static short *shiftset; 74 75 static short **kernel_base; 76 static short **kernel_end; 77 static short *kernel_items; 78 79 void 80 allocate_itemsets(void) 81 { 82 short *itemp; 83 short *item_end; 84 int symbol; 85 int i; 86 int count; 87 int max; 88 short *symbol_count; 89 90 count = 0; 91 symbol_count = NEW2(nsyms, short); 92 93 item_end = ritem + nitems; 94 for (itemp = ritem; itemp < item_end; itemp++) 95 { 96 symbol = *itemp; 97 if (symbol >= 0) 98 { 99 count++; 100 symbol_count[symbol]++; 101 } 102 } 103 104 kernel_base = NEW2(nsyms, short *); 105 kernel_items = NEW2(count, short); 106 107 count = 0; 108 max = 0; 109 for (i = 0; i < nsyms; i++) 110 { 111 kernel_base[i] = kernel_items + count; 112 count += symbol_count[i]; 113 if (max < symbol_count[i]) 114 max = symbol_count[i]; 115 } 116 117 shift_symbol = symbol_count; 118 kernel_end = NEW2(nsyms, short *); 119 } 120 121 void 122 allocate_storage(void) 123 { 124 allocate_itemsets(); 125 shiftset = NEW2(nsyms, short); 126 redset = NEW2(nrules + 1, short); 127 state_set = NEW2(nitems, core *); 128 } 129 130 void 131 append_states(void) 132 { 133 int i; 134 int j; 135 int symbol; 136 137 #ifdef TRACE 138 fprintf(stderr, "Entering append_states()\n"); 139 #endif 140 for (i = 1; i < nshifts; i++) 141 { 142 symbol = shift_symbol[i]; 143 j = i; 144 while (j > 0 && shift_symbol[j - 1] > symbol) 145 { 146 shift_symbol[j] = shift_symbol[j - 1]; 147 j--; 148 } 149 shift_symbol[j] = symbol; 150 } 151 152 for (i = 0; i < nshifts; i++) 153 { 154 symbol = shift_symbol[i]; 155 shiftset[i] = get_state(symbol); 156 } 157 } 158 159 void 160 free_storage(void) 161 { 162 FREE(shift_symbol); 163 FREE(redset); 164 FREE(shiftset); 165 FREE(kernel_base); 166 FREE(kernel_end); 167 FREE(kernel_items); 168 FREE(state_set); 169 } 170 171 172 void 173 generate_states(void) 174 { 175 allocate_storage(); 176 itemset = NEW2(nitems, short); 177 ruleset = NEW2(WORDSIZE(nrules), unsigned); 178 set_first_derives(); 179 initialize_states(); 180 181 while (this_state) 182 { 183 closure(this_state->items, this_state->nitems); 184 save_reductions(); 185 new_itemsets(); 186 append_states(); 187 188 if (nshifts > 0) 189 save_shifts(); 190 191 this_state = this_state->next; 192 } 193 194 finalize_closure(); 195 free_storage(); 196 } 197 198 199 200 int 201 get_state(int symbol) 202 { 203 int key; 204 short *isp1; 205 short *isp2; 206 short *iend; 207 core *sp; 208 int found; 209 int n; 210 211 #ifdef TRACE 212 fprintf(stderr, "Entering get_state(%d)\n", symbol); 213 #endif 214 215 isp1 = kernel_base[symbol]; 216 iend = kernel_end[symbol]; 217 n = iend - isp1; 218 219 key = *isp1; 220 assert(0 <= key && key < nitems); 221 sp = state_set[key]; 222 if (sp) 223 { 224 found = 0; 225 while (!found) 226 { 227 if (sp->nitems == n) 228 { 229 found = 1; 230 isp1 = kernel_base[symbol]; 231 isp2 = sp->items; 232 233 while (found && isp1 < iend) 234 { 235 if (*isp1++ != *isp2++) 236 found = 0; 237 } 238 } 239 240 if (!found) 241 { 242 if (sp->link) 243 { 244 sp = sp->link; 245 } 246 else 247 { 248 sp = sp->link = new_state(symbol); 249 found = 1; 250 } 251 } 252 } 253 } 254 else 255 { 256 state_set[key] = sp = new_state(symbol); 257 } 258 259 return (sp->number); 260 } 261 262 263 void 264 initialize_states(void) 265 { 266 int i; 267 short *start_derives; 268 core *p; 269 270 start_derives = derives[start_symbol]; 271 for (i = 0; start_derives[i] >= 0; ++i) 272 continue; 273 274 p = (core *) MALLOC(sizeof(core) + i*sizeof(short)); 275 if (p == 0) no_space(); 276 277 p->next = 0; 278 p->link = 0; 279 p->number = 0; 280 p->accessing_symbol = 0; 281 p->nitems = i; 282 283 for (i = 0; start_derives[i] >= 0; ++i) 284 p->items[i] = rrhs[start_derives[i]]; 285 286 first_state = last_state = this_state = p; 287 nstates = 1; 288 } 289 290 void 291 new_itemsets(void) 292 { 293 int i; 294 int shiftcount; 295 short *isp; 296 short *ksp; 297 int symbol; 298 299 for (i = 0; i < nsyms; i++) 300 kernel_end[i] = 0; 301 302 shiftcount = 0; 303 isp = itemset; 304 while (isp < itemsetend) 305 { 306 i = *isp++; 307 symbol = ritem[i]; 308 if (symbol > 0) 309 { 310 ksp = kernel_end[symbol]; 311 if (!ksp) 312 { 313 shift_symbol[shiftcount++] = symbol; 314 ksp = kernel_base[symbol]; 315 } 316 317 *ksp++ = i + 1; 318 kernel_end[symbol] = ksp; 319 } 320 } 321 322 nshifts = shiftcount; 323 } 324 325 326 327 core * 328 new_state(int symbol) 329 { 330 int n; 331 core *p; 332 short *isp1; 333 short *isp2; 334 short *iend; 335 336 #ifdef TRACE 337 fprintf(stderr, "Entering new_state(%d)\n", symbol); 338 #endif 339 340 if (nstates >= MAXSHORT) 341 fatal("too many states"); 342 343 isp1 = kernel_base[symbol]; 344 iend = kernel_end[symbol]; 345 n = iend - isp1; 346 347 p = (core *) allocate((unsigned) (sizeof(core) + (n - 1) * sizeof(short))); 348 p->accessing_symbol = symbol; 349 p->number = nstates; 350 p->nitems = n; 351 352 isp2 = p->items; 353 while (isp1 < iend) 354 *isp2++ = *isp1++; 355 356 last_state->next = p; 357 last_state = p; 358 359 nstates++; 360 361 return (p); 362 } 363 364 365 void 366 save_shifts(void) 367 { 368 shifts *p; 369 short *sp1; 370 short *sp2; 371 short *send; 372 373 p = (shifts *) allocate((unsigned) (sizeof(shifts) + 374 (nshifts - 1) * sizeof(short))); 375 376 p->number = this_state->number; 377 p->nshifts = nshifts; 378 379 sp1 = shiftset; 380 sp2 = p->shift; 381 send = shiftset + nshifts; 382 383 while (sp1 < send) 384 *sp2++ = *sp1++; 385 386 if (last_shift) 387 { 388 last_shift->next = p; 389 last_shift = p; 390 } 391 else 392 { 393 first_shift = p; 394 last_shift = p; 395 } 396 } 397 398 399 void 400 save_reductions(void) 401 { 402 short *isp; 403 short *rp1; 404 short *rp2; 405 int item; 406 int count; 407 reductions *p; 408 short *rend; 409 410 count = 0; 411 for (isp = itemset; isp < itemsetend; isp++) 412 { 413 item = ritem[*isp]; 414 if (item < 0) 415 { 416 redset[count++] = -item; 417 } 418 } 419 420 if (count) 421 { 422 p = (reductions *) allocate((unsigned) (sizeof(reductions) + 423 (count - 1) * sizeof(short))); 424 425 p->number = this_state->number; 426 p->nreds = count; 427 428 rp1 = redset; 429 rp2 = p->rules; 430 rend = rp1 + count; 431 432 while (rp1 < rend) 433 *rp2++ = *rp1++; 434 435 if (last_reduction) 436 { 437 last_reduction->next = p; 438 last_reduction = p; 439 } 440 else 441 { 442 first_reduction = p; 443 last_reduction = p; 444 } 445 } 446 } 447 448 void 449 set_derives(void) 450 { 451 int i, k; 452 int lhs; 453 short *rules; 454 455 derives = NEW2(nsyms, short *); 456 rules = NEW2(nvars + nrules, short); 457 458 k = 0; 459 for (lhs = start_symbol; lhs < nsyms; lhs++) 460 { 461 derives[lhs] = rules + k; 462 for (i = 0; i < nrules; i++) 463 { 464 if (rlhs[i] == lhs) 465 { 466 rules[k] = i; 467 k++; 468 } 469 } 470 rules[k] = -1; 471 k++; 472 } 473 474 #ifdef DEBUG 475 print_derives(); 476 #endif 477 } 478 479 void 480 free_derives(void) 481 { 482 FREE(derives[start_symbol]); 483 FREE(derives); 484 } 485 486 #ifdef DEBUG 487 void 488 print_derives(void) 489 { 490 int i; 491 short *sp; 492 493 printf("\nDERIVES\n\n"); 494 495 for (i = start_symbol; i < nsyms; i++) 496 { 497 printf("%s derives ", symbol_name[i]); 498 for (sp = derives[i]; *sp >= 0; sp++) 499 { 500 printf(" %d", *sp); 501 } 502 putchar('\n'); 503 } 504 505 putchar('\n'); 506 } 507 #endif 508 509 void 510 set_nullable(void) 511 { 512 int i, j; 513 int empty; 514 int done; 515 516 nullable = MALLOC(nsyms); 517 if (nullable == 0) no_space(); 518 519 memset(nullable, 0, nsyms); 520 521 done = 0; 522 while (!done) 523 { 524 done = 1; 525 for (i = 1; i < nitems; i++) 526 { 527 empty = 1; 528 while ((j = ritem[i]) >= 0) 529 { 530 if (!nullable[j]) 531 empty = 0; 532 ++i; 533 } 534 if (empty) 535 { 536 j = rlhs[-j]; 537 if (!nullable[j]) 538 { 539 nullable[j] = 1; 540 done = 0; 541 } 542 } 543 } 544 } 545 546 #ifdef DEBUG 547 for (i = 0; i < nsyms; i++) 548 { 549 if (nullable[i]) 550 printf("%s is nullable\n", symbol_name[i]); 551 else 552 printf("%s is not nullable\n", symbol_name[i]); 553 } 554 #endif 555 } 556 557 void 558 free_nullable(void) 559 { 560 FREE(nullable); 561 } 562 563 void 564 lr0(void) 565 { 566 set_derives(); 567 set_nullable(); 568 generate_states(); 569 } 570