contrib/byacc/lr0.c

   1 /* $Id: lr0.c,v 1.20 2020/09/10 17:30:37 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 i;
  48     int count;
  49     int max;
  50     Value_t *symbol_count;
  51
  52     count = 0;
  53     symbol_count = NEW2(nsyms, Value_t);
  54
  55     item_end = ritem + nitems;
  56     for (itemp = ritem; itemp < item_end; itemp++)
  57     {
  58         int symbol = *itemp;
  59
  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     Value_t symbol;
  98
  99 #ifdef  TRACE
 100     fprintf(stderr, "Entering append_states()\n");
 101 #endif
 102     for (i = 1; i < nshifts; i++)
 103     {
 104         int j = i;
 105
 106         symbol = shift_symbol[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 *iend;
 165     core *sp;
 166     int n;
 167
 168 #ifdef  TRACE
 169     fprintf(stderr, "Entering get_state(%d)\n", symbol);
 170 #endif
 171
 172     isp1 = kernel_base[symbol];
 173     iend = kernel_end[symbol];
 174     n = (int)(iend - isp1);
 175
 176     key = *isp1;
 177     assert(0 <= key && key < nitems);
 178     sp = state_set[key];
 179     if (sp)
 180     {
 181         int found = 0;
 182
 183         while (!found)
 184         {
 185             if (sp->nitems == n)
 186             {
 187                 Value_t *isp2;
 188
 189                 found = 1;
 190                 isp1 = kernel_base[symbol];
 191                 isp2 = sp->items;
 192
 193                 while (found && isp1 < iend)
 194                 {
 195                     if (*isp1++ != *isp2++)
 196                         found = 0;
 197                 }
 198             }
 199
 200             if (!found)
 201             {
 202                 if (sp->link)
 203                 {
 204                     sp = sp->link;
 205                 }
 206                 else
 207                 {
 208                     sp = sp->link = new_state(symbol);
 209                     found = 1;
 210                 }
 211             }
 212         }
 213     }
 214     else
 215     {
 216         state_set[key] = sp = new_state(symbol);
 217     }
 218
 219     return (sp->number);
 220 }
 221
 222 static void
 223 initialize_states(void)
 224 {
 225     unsigned i;
 226     Value_t *start_derives;
 227     core *p;
 228
 229     start_derives = derives[start_symbol];
 230     for (i = 0; start_derives[i] >= 0; ++i)
 231         continue;
 232
 233     p = (core *)MALLOC(sizeof(core) + i * sizeof(Value_t));
 234     NO_SPACE(p);
 235
 236     p->next = 0;
 237     p->link = 0;
 238     p->number = 0;
 239     p->accessing_symbol = 0;
 240     p->nitems = (Value_t)i;
 241
 242     for (i = 0; start_derives[i] >= 0; ++i)
 243         p->items[i] = rrhs[start_derives[i]];
 244
 245     first_state = last_state = this_state = p;
 246     nstates = 1;
 247 }
 248
 249 static void
 250 new_itemsets(void)
 251 {
 252     Value_t i;
 253     int shiftcount;
 254     Value_t *isp;
 255     Value_t *ksp;
 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         int j = *isp++;
 265         Value_t symbol = ritem[j];
 266
 267         if (symbol > 0)
 268         {
 269             ksp = kernel_end[symbol];
 270             if (!ksp)
 271             {
 272                 shift_symbol[shiftcount++] = symbol;
 273                 ksp = kernel_base[symbol];
 274             }
 275
 276             *ksp++ = (Value_t)(j + 1);
 277             kernel_end[symbol] = ksp;
 278         }
 279     }
 280
 281     nshifts = shiftcount;
 282 }
 283
 284 static core *
 285 new_state(int symbol)
 286 {
 287     unsigned n;
 288     core *p;
 289     Value_t *isp1;
 290     Value_t *isp2;
 291     Value_t *iend;
 292
 293 #ifdef  TRACE
 294     fprintf(stderr, "Entering new_state(%d)\n", symbol);
 295 #endif
 296
 297     if (nstates >= MAXYYINT)
 298         fatal("too many states");
 299
 300     isp1 = kernel_base[symbol];
 301     iend = kernel_end[symbol];
 302     n = (unsigned)(iend - isp1);
 303
 304     p = (core *)allocate((sizeof(core) + (n - 1) * sizeof(Value_t)));
 305     p->accessing_symbol = (Value_t)symbol;
 306     p->number = (Value_t)nstates;
 307     p->nitems = (Value_t)n;
 308
 309     isp2 = p->items;
 310     while (isp1 < iend)
 311         *isp2++ = *isp1++;
 312
 313     last_state->next = p;
 314     last_state = p;
 315
 316     nstates++;
 317
 318     return (p);
 319 }
 320
 321 /* show_cores is used for debugging */
 322 #ifdef DEBUG
 323 void
 324 show_cores(void)
 325 {
 326     core *p;
 327     int i, j, k, n;
 328     int itemno;
 329
 330     k = 0;
 331     for (p = first_state; p; ++k, p = p->next)
 332     {
 333         if (k)
 334             printf("\n");
 335         printf("state %d, number = %d, accessing symbol = %s\n",
 336                k, p->number, symbol_name[p->accessing_symbol]);
 337         n = p->nitems;
 338         for (i = 0; i < n; ++i)
 339         {
 340             itemno = p->items[i];
 341             printf("%4d  ", itemno);
 342             j = itemno;
 343             while (ritem[j] >= 0)
 344                 ++j;
 345             printf("%s :", symbol_name[rlhs[-ritem[j]]]);
 346             j = rrhs[-ritem[j]];
 347             while (j < itemno)
 348                 printf(" %s", symbol_name[ritem[j++]]);
 349             printf(" .");
 350             while (ritem[j] >= 0)
 351                 printf(" %s", symbol_name[ritem[j++]]);
 352             printf("\n");
 353             fflush(stdout);
 354         }
 355     }
 356 }
 357
 358 /* show_ritems is used for debugging */
 359
 360 void
 361 show_ritems(void)
 362 {
 363     int i;
 364
 365     for (i = 0; i < nitems; ++i)
 366         printf("ritem[%d] = %d\n", i, ritem[i]);
 367 }
 368
 369 /* show_rrhs is used for debugging */
 370 void
 371 show_rrhs(void)
 372 {
 373     int i;
 374
 375     for (i = 0; i < nrules; ++i)
 376         printf("rrhs[%d] = %d\n", i, rrhs[i]);
 377 }
 378
 379 /* show_shifts is used for debugging */
 380
 381 void
 382 show_shifts(void)
 383 {
 384     shifts *p;
 385     int i, j, k;
 386
 387     k = 0;
 388     for (p = first_shift; p; ++k, p = p->next)
 389     {
 390         if (k)
 391             printf("\n");
 392         printf("shift %d, number = %d, nshifts = %d\n", k, p->number,
 393                p->nshifts);
 394         j = p->nshifts;
 395         for (i = 0; i < j; ++i)
 396             printf("\t%d\n", p->shift[i]);
 397     }
 398 }
 399 #endif
 400
 401 static void
 402 save_shifts(void)
 403 {
 404     shifts *p;
 405     Value_t *sp1;
 406     Value_t *sp2;
 407     Value_t *send;
 408
 409     p = (shifts *)allocate((sizeof(shifts) +
 410                               (unsigned)(nshifts - 1) * sizeof(Value_t)));
 411
 412     p->number = this_state->number;
 413     p->nshifts = (Value_t)nshifts;
 414
 415     sp1 = shiftset;
 416     sp2 = p->shift;
 417     send = shiftset + nshifts;
 418
 419     while (sp1 < send)
 420         *sp2++ = *sp1++;
 421
 422     if (last_shift)
 423     {
 424         last_shift->next = p;
 425         last_shift = p;
 426     }
 427     else
 428     {
 429         first_shift = p;
 430         last_shift = p;
 431     }
 432 }
 433
 434 static void
 435 save_reductions(void)
 436 {
 437     Value_t *isp;
 438     Value_t *rp1;
 439     Value_t count;
 440     reductions *p;
 441
 442     count = 0;
 443     for (isp = itemset; isp < itemsetend; isp++)
 444     {
 445         int item = ritem[*isp];
 446
 447         if (item < 0)
 448         {
 449             redset[count++] = (Value_t)-item;
 450         }
 451     }
 452
 453     if (count)
 454     {
 455         Value_t *rp2;
 456         Value_t *rend;
 457
 458         p = (reductions *)allocate((sizeof(reductions) +
 459                                       (unsigned)(count - 1) *
 460                                     sizeof(Value_t)));
 461
 462         p->number = this_state->number;
 463         p->nreds = count;
 464
 465         rp1 = redset;
 466         rp2 = p->rules;
 467         rend = rp1 + count;
 468
 469         while (rp1 < rend)
 470             *rp2++ = *rp1++;
 471
 472         if (last_reduction)
 473         {
 474             last_reduction->next = p;
 475             last_reduction = p;
 476         }
 477         else
 478         {
 479             first_reduction = p;
 480             last_reduction = p;
 481         }
 482     }
 483 }
 484
 485 static void
 486 set_derives(void)
 487 {
 488     Value_t i, k;
 489     int lhs;
 490
 491     derives = NEW2(nsyms, Value_t *);
 492     rules = NEW2(nvars + nrules, Value_t);
 493
 494     k = 0;
 495     for (lhs = start_symbol; lhs < nsyms; lhs++)
 496     {
 497         derives[lhs] = rules + k;
 498         for (i = 0; i < nrules; i++)
 499         {
 500             if (rlhs[i] == lhs)
 501             {
 502                 rules[k] = i;
 503                 k++;
 504             }
 505         }
 506         rules[k] = -1;
 507         k++;
 508     }
 509
 510 #ifdef  DEBUG
 511     print_derives();
 512 #endif
 513 }
 514
 515 #ifdef  DEBUG
 516 void
 517 print_derives(void)
 518 {
 519     int i;
 520     Value_t *sp;
 521
 522     printf("\nDERIVES\n\n");
 523
 524     for (i = start_symbol; i < nsyms; i++)
 525     {
 526         printf("%s derives ", symbol_name[i]);
 527         for (sp = derives[i]; *sp >= 0; sp++)
 528         {
 529             printf("  %d", *sp);
 530         }
 531         putchar('\n');
 532     }
 533
 534     putchar('\n');
 535 }
 536 #endif
 537
 538 static void
 539 set_nullable(void)
 540 {
 541     int i, j;
 542     int empty;
 543     int done_flag;
 544
 545     nullable = TMALLOC(char, nsyms);
 546     NO_SPACE(nullable);
 547
 548     for (i = 0; i < nsyms; ++i)
 549         nullable[i] = 0;
 550
 551     done_flag = 0;
 552     while (!done_flag)
 553     {
 554         done_flag = 1;
 555         for (i = 1; i < nitems; i++)
 556         {
 557             empty = 1;
 558             while ((j = ritem[i]) >= 0)
 559             {
 560                 if (!nullable[j])
 561                     empty = 0;
 562                 ++i;
 563             }
 564             if (empty)
 565             {
 566                 j = rlhs[-j];
 567                 if (!nullable[j])
 568                 {
 569                     nullable[j] = 1;
 570                     done_flag = 0;
 571                 }
 572             }
 573         }
 574     }
 575
 576 #ifdef DEBUG
 577     for (i = 0; i < nsyms; i++)
 578     {
 579         if (nullable[i])
 580             printf("%s is nullable\n", symbol_name[i]);
 581         else
 582             printf("%s is not nullable\n", symbol_name[i]);
 583     }
 584 #endif
 585 }
 586
 587 void
 588 lr0(void)
 589 {
 590     set_derives();
 591     set_nullable();
 592     generate_states();
 593 }
 594
 595 #ifdef NO_LEAKS
 596 void
 597 lr0_leaks(void)
 598 {
 599     if (derives)
 600     {
 601         if (derives[start_symbol] != rules)
 602         {
 603             DO_FREE(derives[start_symbol]);
 604         }
 605         DO_FREE(derives);
 606         DO_FREE(rules);
 607     }
 608     DO_FREE(nullable);
 609 }
 610 #endif