contrib/byacc/lr0.c

   1 /* $Id: lr0.c,v 1.13 2012/05/26 00:40:47 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 short *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     short *itemp;
  44     short *item_end;
  45     int symbol;
  46     int i;
  47     int count;
  48     int max;
  49     short *symbol_count;
  50
  51     count = 0;
  52     symbol_count = NEW2(nsyms, short);
  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, short *);
  66     kernel_items = NEW2(count, short);
  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, short *);
  80 }
  81
  82 static void
  83 allocate_storage(void)
  84 {
  85     allocate_itemsets();
  86     shiftset = NEW2(nsyms, short);
  87     redset = NEW2(nrules + 1, short);
  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, short);
 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     short *isp1;
 162     short *isp2;
 163     short *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     short *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(short));
 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     short *isp;
 252     short *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     short *isp1;
 287     short *isp2;
 288     short *iend;
 289
 290 #ifdef  TRACE
 291     fprintf(stderr, "Entering new_state(%d)\n", symbol);
 292 #endif
 293
 294     if (nstates >= MAXSHORT)
 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(short)));
 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
 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
 397 static void
 398 save_shifts(void)
 399 {
 400     shifts *p;
 401     short *sp1;
 402     short *sp2;
 403     short *send;
 404
 405     p = (shifts *)allocate((sizeof(shifts) +
 406                               (unsigned)(nshifts - 1) * sizeof(short)));
 407
 408     p->number = this_state->number;
 409     p->nshifts = (Value_t) nshifts;
 410
 411     sp1 = shiftset;
 412     sp2 = p->shift;
 413     send = shiftset + nshifts;
 414
 415     while (sp1 < send)
 416         *sp2++ = *sp1++;
 417
 418     if (last_shift)
 419     {
 420         last_shift->next = p;
 421         last_shift = p;
 422     }
 423     else
 424     {
 425         first_shift = p;
 426         last_shift = p;
 427     }
 428 }
 429
 430 static void
 431 save_reductions(void)
 432 {
 433     short *isp;
 434     short *rp1;
 435     short *rp2;
 436     int item;
 437     Value_t count;
 438     reductions *p;
 439     short *rend;
 440
 441     count = 0;
 442     for (isp = itemset; isp < itemsetend; isp++)
 443     {
 444         item = ritem[*isp];
 445         if (item < 0)
 446         {
 447             redset[count++] = (Value_t) - item;
 448         }
 449     }
 450
 451     if (count)
 452     {
 453         p = (reductions *)allocate((sizeof(reductions) +
 454                                       (unsigned)(count - 1) *
 455                                     sizeof(short)));
 456
 457         p->number = this_state->number;
 458         p->nreds = count;
 459
 460         rp1 = redset;
 461         rp2 = p->rules;
 462         rend = rp1 + count;
 463
 464         while (rp1 < rend)
 465             *rp2++ = *rp1++;
 466
 467         if (last_reduction)
 468         {
 469             last_reduction->next = p;
 470             last_reduction = p;
 471         }
 472         else
 473         {
 474             first_reduction = p;
 475             last_reduction = p;
 476         }
 477     }
 478 }
 479
 480 static void
 481 set_derives(void)
 482 {
 483     Value_t i, k;
 484     int lhs;
 485     short *rules;
 486
 487     derives = NEW2(nsyms, short *);
 488     rules = NEW2(nvars + nrules, short);
 489
 490     k = 0;
 491     for (lhs = start_symbol; lhs < nsyms; lhs++)
 492     {
 493         derives[lhs] = rules + k;
 494         for (i = 0; i < nrules; i++)
 495         {
 496             if (rlhs[i] == lhs)
 497             {
 498                 rules[k] = i;
 499                 k++;
 500             }
 501         }
 502         rules[k] = -1;
 503         k++;
 504     }
 505
 506 #ifdef  DEBUG
 507     print_derives();
 508 #endif
 509 }
 510
 511 #ifdef  DEBUG
 512 void
 513 print_derives(void)
 514 {
 515     int i;
 516     short *sp;
 517
 518     printf("\nDERIVES\n\n");
 519
 520     for (i = start_symbol; i < nsyms; i++)
 521     {
 522         printf("%s derives ", symbol_name[i]);
 523         for (sp = derives[i]; *sp >= 0; sp++)
 524         {
 525             printf("  %d", *sp);
 526         }
 527         putchar('\n');
 528     }
 529
 530     putchar('\n');
 531 }
 532 #endif
 533
 534 static void
 535 set_nullable(void)
 536 {
 537     int i, j;
 538     int empty;
 539     int done_flag;
 540
 541     nullable = TMALLOC(char, nsyms);
 542     NO_SPACE(nullable);
 543
 544     for (i = 0; i < nsyms; ++i)
 545         nullable[i] = 0;
 546
 547     done_flag = 0;
 548     while (!done_flag)
 549     {
 550         done_flag = 1;
 551         for (i = 1; i < nitems; i++)
 552         {
 553             empty = 1;
 554             while ((j = ritem[i]) >= 0)
 555             {
 556                 if (!nullable[j])
 557                     empty = 0;
 558                 ++i;
 559             }
 560             if (empty)
 561             {
 562                 j = rlhs[-j];
 563                 if (!nullable[j])
 564                 {
 565                     nullable[j] = 1;
 566                     done_flag = 0;
 567                 }
 568             }
 569         }
 570     }
 571
 572 #ifdef DEBUG
 573     for (i = 0; i < nsyms; i++)
 574     {
 575         if (nullable[i])
 576             printf("%s is nullable\n", symbol_name[i]);
 577         else
 578             printf("%s is not nullable\n", symbol_name[i]);
 579     }
 580 #endif
 581 }
 582
 583 void
 584 lr0(void)
 585 {
 586     set_derives();
 587     set_nullable();
 588     generate_states();
 589 }
 590
 591 #ifdef NO_LEAKS
 592 void
 593 lr0_leaks(void)
 594 {
 595     DO_FREE(derives[start_symbol]);
 596     DO_FREE(derives);
 597     DO_FREE(nullable);
 598 }
 599 #endif