contrib/byacc/lr0.c

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