contrib/byacc/lr0.c

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