1268899Sbapt/* $Id: lr0.c,v 1.16 2014/04/07 21:53:50 tom Exp $ */ 2234949Sbapt 3234949Sbapt#include "defs.h" 4234949Sbapt 5234949Sbaptstatic core *new_state(int symbol); 6234949Sbaptstatic Value_t get_state(int symbol); 7234949Sbaptstatic void allocate_itemsets(void); 8234949Sbaptstatic void allocate_storage(void); 9234949Sbaptstatic void append_states(void); 10234949Sbaptstatic void free_storage(void); 11234949Sbaptstatic void generate_states(void); 12234949Sbaptstatic void initialize_states(void); 13234949Sbaptstatic void new_itemsets(void); 14234949Sbaptstatic void save_reductions(void); 15234949Sbaptstatic void save_shifts(void); 16234949Sbaptstatic void set_derives(void); 17234949Sbaptstatic void set_nullable(void); 18234949Sbapt 19234949Sbaptint nstates; 20234949Sbaptcore *first_state; 21234949Sbaptshifts *first_shift; 22234949Sbaptreductions *first_reduction; 23234949Sbapt 24234949Sbaptstatic core **state_set; 25234949Sbaptstatic core *this_state; 26234949Sbaptstatic core *last_state; 27234949Sbaptstatic shifts *last_shift; 28234949Sbaptstatic reductions *last_reduction; 29234949Sbapt 30234949Sbaptstatic int nshifts; 31268899Sbaptstatic Value_t *shift_symbol; 32234949Sbapt 33234949Sbaptstatic Value_t *redset; 34234949Sbaptstatic Value_t *shiftset; 35234949Sbapt 36234949Sbaptstatic Value_t **kernel_base; 37234949Sbaptstatic Value_t **kernel_end; 38234949Sbaptstatic Value_t *kernel_items; 39234949Sbapt 40234949Sbaptstatic void 41234949Sbaptallocate_itemsets(void) 42234949Sbapt{ 43268899Sbapt Value_t *itemp; 44268899Sbapt Value_t *item_end; 45234949Sbapt int symbol; 46234949Sbapt int i; 47234949Sbapt int count; 48234949Sbapt int max; 49268899Sbapt Value_t *symbol_count; 50234949Sbapt 51234949Sbapt count = 0; 52268899Sbapt symbol_count = NEW2(nsyms, Value_t); 53234949Sbapt 54234949Sbapt item_end = ritem + nitems; 55234949Sbapt for (itemp = ritem; itemp < item_end; itemp++) 56234949Sbapt { 57234949Sbapt symbol = *itemp; 58234949Sbapt if (symbol >= 0) 59234949Sbapt { 60234949Sbapt count++; 61234949Sbapt symbol_count[symbol]++; 62234949Sbapt } 63234949Sbapt } 64234949Sbapt 65268899Sbapt kernel_base = NEW2(nsyms, Value_t *); 66268899Sbapt kernel_items = NEW2(count, Value_t); 67234949Sbapt 68234949Sbapt count = 0; 69234949Sbapt max = 0; 70234949Sbapt for (i = 0; i < nsyms; i++) 71234949Sbapt { 72234949Sbapt kernel_base[i] = kernel_items + count; 73234949Sbapt count += symbol_count[i]; 74234949Sbapt if (max < symbol_count[i]) 75234949Sbapt max = symbol_count[i]; 76234949Sbapt } 77234949Sbapt 78234949Sbapt shift_symbol = symbol_count; 79268899Sbapt kernel_end = NEW2(nsyms, Value_t *); 80234949Sbapt} 81234949Sbapt 82234949Sbaptstatic void 83234949Sbaptallocate_storage(void) 84234949Sbapt{ 85234949Sbapt allocate_itemsets(); 86268899Sbapt shiftset = NEW2(nsyms, Value_t); 87268899Sbapt redset = NEW2(nrules + 1, Value_t); 88234949Sbapt state_set = NEW2(nitems, core *); 89234949Sbapt} 90234949Sbapt 91234949Sbaptstatic void 92234949Sbaptappend_states(void) 93234949Sbapt{ 94234949Sbapt int i; 95234949Sbapt int j; 96234949Sbapt Value_t symbol; 97234949Sbapt 98234949Sbapt#ifdef TRACE 99234949Sbapt fprintf(stderr, "Entering append_states()\n"); 100234949Sbapt#endif 101234949Sbapt for (i = 1; i < nshifts; i++) 102234949Sbapt { 103234949Sbapt symbol = shift_symbol[i]; 104234949Sbapt j = i; 105234949Sbapt while (j > 0 && shift_symbol[j - 1] > symbol) 106234949Sbapt { 107234949Sbapt shift_symbol[j] = shift_symbol[j - 1]; 108234949Sbapt j--; 109234949Sbapt } 110234949Sbapt shift_symbol[j] = symbol; 111234949Sbapt } 112234949Sbapt 113234949Sbapt for (i = 0; i < nshifts; i++) 114234949Sbapt { 115234949Sbapt symbol = shift_symbol[i]; 116234949Sbapt shiftset[i] = get_state(symbol); 117234949Sbapt } 118234949Sbapt} 119234949Sbapt 120234949Sbaptstatic void 121234949Sbaptfree_storage(void) 122234949Sbapt{ 123234949Sbapt FREE(shift_symbol); 124234949Sbapt FREE(redset); 125234949Sbapt FREE(shiftset); 126234949Sbapt FREE(kernel_base); 127234949Sbapt FREE(kernel_end); 128234949Sbapt FREE(kernel_items); 129234949Sbapt FREE(state_set); 130234949Sbapt} 131234949Sbapt 132234949Sbaptstatic void 133234949Sbaptgenerate_states(void) 134234949Sbapt{ 135234949Sbapt allocate_storage(); 136268899Sbapt itemset = NEW2(nitems, Value_t); 137234949Sbapt ruleset = NEW2(WORDSIZE(nrules), unsigned); 138234949Sbapt set_first_derives(); 139234949Sbapt initialize_states(); 140234949Sbapt 141234949Sbapt while (this_state) 142234949Sbapt { 143234949Sbapt closure(this_state->items, this_state->nitems); 144234949Sbapt save_reductions(); 145234949Sbapt new_itemsets(); 146234949Sbapt append_states(); 147234949Sbapt 148234949Sbapt if (nshifts > 0) 149234949Sbapt save_shifts(); 150234949Sbapt 151234949Sbapt this_state = this_state->next; 152234949Sbapt } 153234949Sbapt 154234949Sbapt free_storage(); 155234949Sbapt} 156234949Sbapt 157234949Sbaptstatic Value_t 158234949Sbaptget_state(int symbol) 159234949Sbapt{ 160234949Sbapt int key; 161268899Sbapt Value_t *isp1; 162268899Sbapt Value_t *isp2; 163268899Sbapt Value_t *iend; 164234949Sbapt core *sp; 165234949Sbapt int found; 166234949Sbapt int n; 167234949Sbapt 168234949Sbapt#ifdef TRACE 169234949Sbapt fprintf(stderr, "Entering get_state(%d)\n", symbol); 170234949Sbapt#endif 171234949Sbapt 172234949Sbapt isp1 = kernel_base[symbol]; 173234949Sbapt iend = kernel_end[symbol]; 174234949Sbapt n = (int)(iend - isp1); 175234949Sbapt 176234949Sbapt key = *isp1; 177234949Sbapt assert(0 <= key && key < nitems); 178234949Sbapt sp = state_set[key]; 179234949Sbapt if (sp) 180234949Sbapt { 181234949Sbapt found = 0; 182234949Sbapt while (!found) 183234949Sbapt { 184234949Sbapt if (sp->nitems == n) 185234949Sbapt { 186234949Sbapt found = 1; 187234949Sbapt isp1 = kernel_base[symbol]; 188234949Sbapt isp2 = sp->items; 189234949Sbapt 190234949Sbapt while (found && isp1 < iend) 191234949Sbapt { 192234949Sbapt if (*isp1++ != *isp2++) 193234949Sbapt found = 0; 194234949Sbapt } 195234949Sbapt } 196234949Sbapt 197234949Sbapt if (!found) 198234949Sbapt { 199234949Sbapt if (sp->link) 200234949Sbapt { 201234949Sbapt sp = sp->link; 202234949Sbapt } 203234949Sbapt else 204234949Sbapt { 205234949Sbapt sp = sp->link = new_state(symbol); 206234949Sbapt found = 1; 207234949Sbapt } 208234949Sbapt } 209234949Sbapt } 210234949Sbapt } 211234949Sbapt else 212234949Sbapt { 213234949Sbapt state_set[key] = sp = new_state(symbol); 214234949Sbapt } 215234949Sbapt 216234949Sbapt return (sp->number); 217234949Sbapt} 218234949Sbapt 219234949Sbaptstatic void 220234949Sbaptinitialize_states(void) 221234949Sbapt{ 222234949Sbapt unsigned i; 223268899Sbapt Value_t *start_derives; 224234949Sbapt core *p; 225234949Sbapt 226234949Sbapt start_derives = derives[start_symbol]; 227234949Sbapt for (i = 0; start_derives[i] >= 0; ++i) 228234949Sbapt continue; 229234949Sbapt 230268899Sbapt p = (core *)MALLOC(sizeof(core) + i * sizeof(Value_t)); 231234949Sbapt NO_SPACE(p); 232234949Sbapt 233234949Sbapt p->next = 0; 234234949Sbapt p->link = 0; 235234949Sbapt p->number = 0; 236234949Sbapt p->accessing_symbol = 0; 237234949Sbapt p->nitems = (Value_t) i; 238234949Sbapt 239234949Sbapt for (i = 0; start_derives[i] >= 0; ++i) 240234949Sbapt p->items[i] = rrhs[start_derives[i]]; 241234949Sbapt 242234949Sbapt first_state = last_state = this_state = p; 243234949Sbapt nstates = 1; 244234949Sbapt} 245234949Sbapt 246234949Sbaptstatic void 247234949Sbaptnew_itemsets(void) 248234949Sbapt{ 249234949Sbapt Value_t i; 250234949Sbapt int shiftcount; 251268899Sbapt Value_t *isp; 252268899Sbapt Value_t *ksp; 253234949Sbapt Value_t symbol; 254234949Sbapt 255234949Sbapt for (i = 0; i < nsyms; i++) 256234949Sbapt kernel_end[i] = 0; 257234949Sbapt 258234949Sbapt shiftcount = 0; 259234949Sbapt isp = itemset; 260234949Sbapt while (isp < itemsetend) 261234949Sbapt { 262234949Sbapt i = *isp++; 263234949Sbapt symbol = ritem[i]; 264234949Sbapt if (symbol > 0) 265234949Sbapt { 266234949Sbapt ksp = kernel_end[symbol]; 267234949Sbapt if (!ksp) 268234949Sbapt { 269234949Sbapt shift_symbol[shiftcount++] = symbol; 270234949Sbapt ksp = kernel_base[symbol]; 271234949Sbapt } 272234949Sbapt 273234949Sbapt *ksp++ = (Value_t) (i + 1); 274234949Sbapt kernel_end[symbol] = ksp; 275234949Sbapt } 276234949Sbapt } 277234949Sbapt 278234949Sbapt nshifts = shiftcount; 279234949Sbapt} 280234949Sbapt 281234949Sbaptstatic core * 282234949Sbaptnew_state(int symbol) 283234949Sbapt{ 284234949Sbapt unsigned n; 285234949Sbapt core *p; 286268899Sbapt Value_t *isp1; 287268899Sbapt Value_t *isp2; 288268899Sbapt Value_t *iend; 289234949Sbapt 290234949Sbapt#ifdef TRACE 291234949Sbapt fprintf(stderr, "Entering new_state(%d)\n", symbol); 292234949Sbapt#endif 293234949Sbapt 294268899Sbapt if (nstates >= MAXYYINT) 295234949Sbapt fatal("too many states"); 296234949Sbapt 297234949Sbapt isp1 = kernel_base[symbol]; 298234949Sbapt iend = kernel_end[symbol]; 299234949Sbapt n = (unsigned)(iend - isp1); 300234949Sbapt 301268899Sbapt p = (core *)allocate((sizeof(core) + (n - 1) * sizeof(Value_t))); 302234949Sbapt p->accessing_symbol = (Value_t) symbol; 303234949Sbapt p->number = (Value_t) nstates; 304234949Sbapt p->nitems = (Value_t) n; 305234949Sbapt 306234949Sbapt isp2 = p->items; 307234949Sbapt while (isp1 < iend) 308234949Sbapt *isp2++ = *isp1++; 309234949Sbapt 310234949Sbapt last_state->next = p; 311234949Sbapt last_state = p; 312234949Sbapt 313234949Sbapt nstates++; 314234949Sbapt 315234949Sbapt return (p); 316234949Sbapt} 317234949Sbapt 318234949Sbapt/* show_cores is used for debugging */ 319268899Sbapt#ifdef DEBUG 320234949Sbaptvoid 321234949Sbaptshow_cores(void) 322234949Sbapt{ 323234949Sbapt core *p; 324234949Sbapt int i, j, k, n; 325234949Sbapt int itemno; 326234949Sbapt 327234949Sbapt k = 0; 328234949Sbapt for (p = first_state; p; ++k, p = p->next) 329234949Sbapt { 330234949Sbapt if (k) 331234949Sbapt printf("\n"); 332234949Sbapt printf("state %d, number = %d, accessing symbol = %s\n", 333234949Sbapt k, p->number, symbol_name[p->accessing_symbol]); 334234949Sbapt n = p->nitems; 335234949Sbapt for (i = 0; i < n; ++i) 336234949Sbapt { 337234949Sbapt itemno = p->items[i]; 338234949Sbapt printf("%4d ", itemno); 339234949Sbapt j = itemno; 340234949Sbapt while (ritem[j] >= 0) 341234949Sbapt ++j; 342234949Sbapt printf("%s :", symbol_name[rlhs[-ritem[j]]]); 343234949Sbapt j = rrhs[-ritem[j]]; 344234949Sbapt while (j < itemno) 345234949Sbapt printf(" %s", symbol_name[ritem[j++]]); 346234949Sbapt printf(" ."); 347234949Sbapt while (ritem[j] >= 0) 348234949Sbapt printf(" %s", symbol_name[ritem[j++]]); 349234949Sbapt printf("\n"); 350234949Sbapt fflush(stdout); 351234949Sbapt } 352234949Sbapt } 353234949Sbapt} 354234949Sbapt 355234949Sbapt/* show_ritems is used for debugging */ 356234949Sbapt 357234949Sbaptvoid 358234949Sbaptshow_ritems(void) 359234949Sbapt{ 360234949Sbapt int i; 361234949Sbapt 362234949Sbapt for (i = 0; i < nitems; ++i) 363234949Sbapt printf("ritem[%d] = %d\n", i, ritem[i]); 364234949Sbapt} 365234949Sbapt 366234949Sbapt/* show_rrhs is used for debugging */ 367234949Sbaptvoid 368234949Sbaptshow_rrhs(void) 369234949Sbapt{ 370234949Sbapt int i; 371234949Sbapt 372234949Sbapt for (i = 0; i < nrules; ++i) 373234949Sbapt printf("rrhs[%d] = %d\n", i, rrhs[i]); 374234949Sbapt} 375234949Sbapt 376234949Sbapt/* show_shifts is used for debugging */ 377234949Sbapt 378234949Sbaptvoid 379234949Sbaptshow_shifts(void) 380234949Sbapt{ 381234949Sbapt shifts *p; 382234949Sbapt int i, j, k; 383234949Sbapt 384234949Sbapt k = 0; 385234949Sbapt for (p = first_shift; p; ++k, p = p->next) 386234949Sbapt { 387234949Sbapt if (k) 388234949Sbapt printf("\n"); 389234949Sbapt printf("shift %d, number = %d, nshifts = %d\n", k, p->number, 390234949Sbapt p->nshifts); 391234949Sbapt j = p->nshifts; 392234949Sbapt for (i = 0; i < j; ++i) 393234949Sbapt printf("\t%d\n", p->shift[i]); 394234949Sbapt } 395234949Sbapt} 396268899Sbapt#endif 397234949Sbapt 398234949Sbaptstatic void 399234949Sbaptsave_shifts(void) 400234949Sbapt{ 401234949Sbapt shifts *p; 402268899Sbapt Value_t *sp1; 403268899Sbapt Value_t *sp2; 404268899Sbapt Value_t *send; 405234949Sbapt 406234949Sbapt p = (shifts *)allocate((sizeof(shifts) + 407268899Sbapt (unsigned)(nshifts - 1) * sizeof(Value_t))); 408234949Sbapt 409234949Sbapt p->number = this_state->number; 410234949Sbapt p->nshifts = (Value_t) nshifts; 411234949Sbapt 412234949Sbapt sp1 = shiftset; 413234949Sbapt sp2 = p->shift; 414234949Sbapt send = shiftset + nshifts; 415234949Sbapt 416234949Sbapt while (sp1 < send) 417234949Sbapt *sp2++ = *sp1++; 418234949Sbapt 419234949Sbapt if (last_shift) 420234949Sbapt { 421234949Sbapt last_shift->next = p; 422234949Sbapt last_shift = p; 423234949Sbapt } 424234949Sbapt else 425234949Sbapt { 426234949Sbapt first_shift = p; 427234949Sbapt last_shift = p; 428234949Sbapt } 429234949Sbapt} 430234949Sbapt 431234949Sbaptstatic void 432234949Sbaptsave_reductions(void) 433234949Sbapt{ 434268899Sbapt Value_t *isp; 435268899Sbapt Value_t *rp1; 436268899Sbapt Value_t *rp2; 437234949Sbapt int item; 438234949Sbapt Value_t count; 439234949Sbapt reductions *p; 440268899Sbapt Value_t *rend; 441234949Sbapt 442234949Sbapt count = 0; 443234949Sbapt for (isp = itemset; isp < itemsetend; isp++) 444234949Sbapt { 445234949Sbapt item = ritem[*isp]; 446234949Sbapt if (item < 0) 447234949Sbapt { 448234949Sbapt redset[count++] = (Value_t) - item; 449234949Sbapt } 450234949Sbapt } 451234949Sbapt 452234949Sbapt if (count) 453234949Sbapt { 454234949Sbapt p = (reductions *)allocate((sizeof(reductions) + 455234949Sbapt (unsigned)(count - 1) * 456268899Sbapt sizeof(Value_t))); 457234949Sbapt 458234949Sbapt p->number = this_state->number; 459234949Sbapt p->nreds = count; 460234949Sbapt 461234949Sbapt rp1 = redset; 462234949Sbapt rp2 = p->rules; 463234949Sbapt rend = rp1 + count; 464234949Sbapt 465234949Sbapt while (rp1 < rend) 466234949Sbapt *rp2++ = *rp1++; 467234949Sbapt 468234949Sbapt if (last_reduction) 469234949Sbapt { 470234949Sbapt last_reduction->next = p; 471234949Sbapt last_reduction = p; 472234949Sbapt } 473234949Sbapt else 474234949Sbapt { 475234949Sbapt first_reduction = p; 476234949Sbapt last_reduction = p; 477234949Sbapt } 478234949Sbapt } 479234949Sbapt} 480234949Sbapt 481234949Sbaptstatic void 482234949Sbaptset_derives(void) 483234949Sbapt{ 484234949Sbapt Value_t i, k; 485234949Sbapt int lhs; 486268899Sbapt Value_t *rules; 487234949Sbapt 488268899Sbapt derives = NEW2(nsyms, Value_t *); 489268899Sbapt rules = NEW2(nvars + nrules, Value_t); 490234949Sbapt 491234949Sbapt k = 0; 492234949Sbapt for (lhs = start_symbol; lhs < nsyms; lhs++) 493234949Sbapt { 494234949Sbapt derives[lhs] = rules + k; 495234949Sbapt for (i = 0; i < nrules; i++) 496234949Sbapt { 497234949Sbapt if (rlhs[i] == lhs) 498234949Sbapt { 499234949Sbapt rules[k] = i; 500234949Sbapt k++; 501234949Sbapt } 502234949Sbapt } 503234949Sbapt rules[k] = -1; 504234949Sbapt k++; 505234949Sbapt } 506234949Sbapt 507234949Sbapt#ifdef DEBUG 508234949Sbapt print_derives(); 509234949Sbapt#endif 510234949Sbapt} 511234949Sbapt 512234949Sbapt#ifdef DEBUG 513234949Sbaptvoid 514234949Sbaptprint_derives(void) 515234949Sbapt{ 516234949Sbapt int i; 517268899Sbapt Value_t *sp; 518234949Sbapt 519234949Sbapt printf("\nDERIVES\n\n"); 520234949Sbapt 521234949Sbapt for (i = start_symbol; i < nsyms; i++) 522234949Sbapt { 523234949Sbapt printf("%s derives ", symbol_name[i]); 524234949Sbapt for (sp = derives[i]; *sp >= 0; sp++) 525234949Sbapt { 526234949Sbapt printf(" %d", *sp); 527234949Sbapt } 528234949Sbapt putchar('\n'); 529234949Sbapt } 530234949Sbapt 531234949Sbapt putchar('\n'); 532234949Sbapt} 533234949Sbapt#endif 534234949Sbapt 535234949Sbaptstatic void 536234949Sbaptset_nullable(void) 537234949Sbapt{ 538234949Sbapt int i, j; 539234949Sbapt int empty; 540234949Sbapt int done_flag; 541234949Sbapt 542240517Sbapt nullable = TMALLOC(char, nsyms); 543234949Sbapt NO_SPACE(nullable); 544234949Sbapt 545234949Sbapt for (i = 0; i < nsyms; ++i) 546234949Sbapt nullable[i] = 0; 547234949Sbapt 548234949Sbapt done_flag = 0; 549234949Sbapt while (!done_flag) 550234949Sbapt { 551234949Sbapt done_flag = 1; 552234949Sbapt for (i = 1; i < nitems; i++) 553234949Sbapt { 554234949Sbapt empty = 1; 555234949Sbapt while ((j = ritem[i]) >= 0) 556234949Sbapt { 557234949Sbapt if (!nullable[j]) 558234949Sbapt empty = 0; 559234949Sbapt ++i; 560234949Sbapt } 561234949Sbapt if (empty) 562234949Sbapt { 563234949Sbapt j = rlhs[-j]; 564234949Sbapt if (!nullable[j]) 565234949Sbapt { 566234949Sbapt nullable[j] = 1; 567234949Sbapt done_flag = 0; 568234949Sbapt } 569234949Sbapt } 570234949Sbapt } 571234949Sbapt } 572234949Sbapt 573234949Sbapt#ifdef DEBUG 574234949Sbapt for (i = 0; i < nsyms; i++) 575234949Sbapt { 576234949Sbapt if (nullable[i]) 577234949Sbapt printf("%s is nullable\n", symbol_name[i]); 578234949Sbapt else 579234949Sbapt printf("%s is not nullable\n", symbol_name[i]); 580234949Sbapt } 581234949Sbapt#endif 582234949Sbapt} 583234949Sbapt 584234949Sbaptvoid 585234949Sbaptlr0(void) 586234949Sbapt{ 587234949Sbapt set_derives(); 588234949Sbapt set_nullable(); 589234949Sbapt generate_states(); 590234949Sbapt} 591234949Sbapt 592234949Sbapt#ifdef NO_LEAKS 593234949Sbaptvoid 594234949Sbaptlr0_leaks(void) 595234949Sbapt{ 596268899Sbapt if (derives) 597268899Sbapt { 598268899Sbapt DO_FREE(derives[start_symbol]); 599268899Sbapt DO_FREE(derives); 600268899Sbapt } 601234949Sbapt DO_FREE(nullable); 602234949Sbapt} 603234949Sbapt#endif 604