util/byacc/lr0.c

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