external/bsd/byacc/dist/lr0.c

   1 /*      $NetBSD: lr0.c,v 1.6 2011/09/10 21:29:04 christos Exp $ */
   2 /* Id: lr0.c,v 1.12 2010/06/09 08:53:17 tom Exp */
   3
   4 #include "defs.h"
   5
   6 #include <sys/cdefs.h>
   7 __RCSID("$NetBSD: lr0.c,v 1.6 2011/09/10 21:29:04 christos Exp $");
   8
   9 static core *new_state(int symbol);
  10 static Value_t get_state(int symbol);
  11 static void allocate_itemsets(void);
  12 static void allocate_storage(void);
  13 static void append_states(void);
  14 static void free_storage(void);
  15 static void generate_states(void);
  16 static void initialize_states(void);
  17 static void new_itemsets(void);
  18 static void save_reductions(void);
  19 static void save_shifts(void);
  20 static void set_derives(void);
  21 static void set_nullable(void);
  22
  23 int nstates;
  24 core *first_state;
  25 shifts *first_shift;
  26 reductions *first_reduction;
  27
  28 static core **state_set;
  29 static core *this_state;
  30 static core *last_state;
  31 static shifts *last_shift;
  32 static reductions *last_reduction;
  33
  34 static int nshifts;
  35 static short *shift_symbol;
  36
  37 static Value_t *redset;
  38 static Value_t *shiftset;
  39
  40 static Value_t **kernel_base;
  41 static Value_t **kernel_end;
  42 static Value_t *kernel_items;
  43
  44 static void
  45 allocate_itemsets(void)
  46 {
  47     short *itemp;
  48     short *item_end;
  49     int symbol;
  50     int i;
  51     int count;
  52     int max;
  53     short *symbol_count;
  54
  55     count = 0;
  56     symbol_count = NEW2(nsyms, short);
  57
  58     item_end = ritem + nitems;
  59     for (itemp = ritem; itemp < item_end; itemp++)
  60     {
  61         symbol = *itemp;
  62         if (symbol >= 0)
  63         {
  64             count++;
  65             symbol_count[symbol]++;
  66         }
  67     }
  68
  69     kernel_base = NEW2(nsyms, short *);
  70     kernel_items = NEW2(count, short);
  71
  72     count = 0;
  73     max = 0;
  74     for (i = 0; i < nsyms; i++)
  75     {
  76         kernel_base[i] = kernel_items + count;
  77         count += symbol_count[i];
  78         if (max < symbol_count[i])
  79             max = symbol_count[i];
  80     }
  81
  82     shift_symbol = symbol_count;
  83     kernel_end = NEW2(nsyms, short *);
  84 }
  85
  86 static void
  87 allocate_storage(void)
  88 {
  89     allocate_itemsets();
  90     shiftset = NEW2(nsyms, short);
  91     redset = NEW2(nrules + 1, short);
  92     state_set = NEW2(nitems, core *);
  93 }
  94
  95 static void
  96 append_states(void)
  97 {
  98     int i;
  99     int j;
 100     Value_t symbol;
 101
 102 #ifdef  TRACE
 103     fprintf(stderr, "Entering append_states()\n");
 104 #endif
 105     for (i = 1; i < nshifts; i++)
 106     {
 107         symbol = shift_symbol[i];
 108         j = i;
 109         while (j > 0 && shift_symbol[j - 1] > symbol)
 110         {
 111             shift_symbol[j] = shift_symbol[j - 1];
 112             j--;
 113         }
 114         shift_symbol[j] = symbol;
 115     }
 116
 117     for (i = 0; i < nshifts; i++)
 118     {
 119         symbol = shift_symbol[i];
 120         shiftset[i] = get_state(symbol);
 121     }
 122 }
 123
 124 static void
 125 free_storage(void)
 126 {
 127     FREE(shift_symbol);
 128     FREE(redset);
 129     FREE(shiftset);
 130     FREE(kernel_base);
 131     FREE(kernel_end);
 132     FREE(kernel_items);
 133     FREE(state_set);
 134 }
 135
 136 static void
 137 generate_states(void)
 138 {
 139     allocate_storage();
 140     itemset = NEW2(nitems, short);
 141     ruleset = NEW2(WORDSIZE(nrules), unsigned);
 142     set_first_derives();
 143     initialize_states();
 144
 145     while (this_state)
 146     {
 147         closure(this_state->items, this_state->nitems);
 148         save_reductions();
 149         new_itemsets();
 150         append_states();
 151
 152         if (nshifts > 0)
 153             save_shifts();
 154
 155         this_state = this_state->next;
 156     }
 157
 158     free_storage();
 159 }
 160
 161 static Value_t
 162 get_state(int symbol)
 163 {
 164     int key;
 165     short *isp1;
 166     short *isp2;
 167     short *iend;
 168     core *sp;
 169     int found;
 170     int n;
 171
 172 #ifdef  TRACE
 173     fprintf(stderr, "Entering get_state(%d)\n", symbol);
 174 #endif
 175
 176     isp1 = kernel_base[symbol];
 177     iend = kernel_end[symbol];
 178     n = (int)(iend - isp1);
 179
 180     key = *isp1;
 181     assert(0 <= key && key < nitems);
 182     sp = state_set[key];
 183     if (sp)
 184     {
 185         found = 0;
 186         while (!found)
 187         {
 188             if (sp->nitems == n)
 189             {
 190                 found = 1;
 191                 isp1 = kernel_base[symbol];
 192                 isp2 = sp->items;
 193
 194                 while (found && isp1 < iend)
 195                 {
 196                     if (*isp1++ != *isp2++)
 197                         found = 0;
 198                 }
 199             }
 200
 201             if (!found)
 202             {
 203                 if (sp->link)
 204                 {
 205                     sp = sp->link;
 206                 }
 207                 else
 208                 {
 209                     sp = sp->link = new_state(symbol);
 210                     found = 1;
 211                 }
 212             }
 213         }
 214     }
 215     else
 216     {
 217         state_set[key] = sp = new_state(symbol);
 218     }
 219
 220     return (sp->number);
 221 }
 222
 223 static void
 224 initialize_states(void)
 225 {
 226     unsigned i;
 227     short *start_derives;
 228     core *p;
 229
 230     start_derives = derives[start_symbol];
 231     for (i = 0; start_derives[i] >= 0; ++i)
 232         continue;
 233
 234     p = (core *)MALLOC(sizeof(core) + i * sizeof(short));
 235     NO_SPACE(p);
 236
 237     p->next = 0;
 238     p->link = 0;
 239     p->number = 0;
 240     p->accessing_symbol = 0;
 241     p->nitems = (Value_t) i;
 242
 243     for (i = 0; start_derives[i] >= 0; ++i)
 244         p->items[i] = rrhs[start_derives[i]];
 245
 246     first_state = last_state = this_state = p;
 247     nstates = 1;
 248 }
 249
 250 static void
 251 new_itemsets(void)
 252 {
 253     Value_t i;
 254     int shiftcount;
 255     short *isp;
 256     short *ksp;
 257     Value_t symbol;
 258
 259     for (i = 0; i < nsyms; i++)
 260         kernel_end[i] = 0;
 261
 262     shiftcount = 0;
 263     isp = itemset;
 264     while (isp < itemsetend)
 265     {
 266         i = *isp++;
 267         symbol = ritem[i];
 268         if (symbol > 0)
 269         {
 270             ksp = kernel_end[symbol];
 271             if (!ksp)
 272             {
 273                 shift_symbol[shiftcount++] = symbol;
 274                 ksp = kernel_base[symbol];
 275             }
 276
 277             *ksp++ = (Value_t) (i + 1);
 278             kernel_end[symbol] = ksp;
 279         }
 280     }
 281
 282     nshifts = shiftcount;
 283 }
 284
 285 static core *
 286 new_state(int symbol)
 287 {
 288     unsigned n;
 289     core *p;
 290     short *isp1;
 291     short *isp2;
 292     short *iend;
 293
 294 #ifdef  TRACE
 295     fprintf(stderr, "Entering new_state(%d)\n", symbol);
 296 #endif
 297
 298     if (nstates >= MAXSHORT)
 299         fatal("too many states");
 300
 301     isp1 = kernel_base[symbol];
 302     iend = kernel_end[symbol];
 303     n = (unsigned)(iend - isp1);
 304
 305     p = (core *)allocate((sizeof(core) + (n - 1) * sizeof(short)));
 306     p->accessing_symbol = (Value_t) symbol;
 307     p->number = (Value_t) nstates;
 308     p->nitems = (Value_t) n;
 309
 310     isp2 = p->items;
 311     while (isp1 < iend)
 312         *isp2++ = *isp1++;
 313
 314     last_state->next = p;
 315     last_state = p;
 316
 317     nstates++;
 318
 319     return (p);
 320 }
 321
 322 /* show_cores is used for debugging */
 323
 324 void
 325 show_cores(void)
 326 {
 327     core *p;
 328     int i, j, k, n;
 329     int itemno;
 330
 331     k = 0;
 332     for (p = first_state; p; ++k, p = p->next)
 333     {
 334         if (k)
 335             printf("\n");
 336         printf("state %d, number = %d, accessing symbol = %s\n",
 337                k, p->number, symbol_name[p->accessing_symbol]);
 338         n = p->nitems;
 339         for (i = 0; i < n; ++i)
 340         {
 341             itemno = p->items[i];
 342             printf("%4d  ", itemno);
 343             j = itemno;
 344             while (ritem[j] >= 0)
 345                 ++j;
 346             printf("%s :", symbol_name[rlhs[-ritem[j]]]);
 347             j = rrhs[-ritem[j]];
 348             while (j < itemno)
 349                 printf(" %s", symbol_name[ritem[j++]]);
 350             printf(" .");
 351             while (ritem[j] >= 0)
 352                 printf(" %s", symbol_name[ritem[j++]]);
 353             printf("\n");
 354             fflush(stdout);
 355         }
 356     }
 357 }
 358
 359 /* show_ritems is used for debugging */
 360
 361 void
 362 show_ritems(void)
 363 {
 364     int i;
 365
 366     for (i = 0; i < nitems; ++i)
 367         printf("ritem[%d] = %d\n", i, ritem[i]);
 368 }
 369
 370 /* show_rrhs is used for debugging */
 371 void
 372 show_rrhs(void)
 373 {
 374     int i;
 375
 376     for (i = 0; i < nrules; ++i)
 377         printf("rrhs[%d] = %d\n", i, rrhs[i]);
 378 }
 379
 380 /* show_shifts is used for debugging */
 381
 382 void
 383 show_shifts(void)
 384 {
 385     shifts *p;
 386     int i, j, k;
 387
 388     k = 0;
 389     for (p = first_shift; p; ++k, p = p->next)
 390     {
 391         if (k)
 392             printf("\n");
 393         printf("shift %d, number = %d, nshifts = %d\n", k, p->number,
 394                p->nshifts);
 395         j = p->nshifts;
 396         for (i = 0; i < j; ++i)
 397             printf("\t%d\n", p->shift[i]);
 398     }
 399 }
 400
 401 static void
 402 save_shifts(void)
 403 {
 404     shifts *p;
 405     short *sp1;
 406     short *sp2;
 407     short *send;
 408
 409     p = (shifts *)allocate((sizeof(shifts) +
 410                               (unsigned)(nshifts - 1) * sizeof(short)));
 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     short *isp;
 438     short *rp1;
 439     short *rp2;
 440     int item;
 441     Value_t count;
 442     reductions *p;
 443     short *rend;
 444
 445     count = 0;
 446     for (isp = itemset; isp < itemsetend; isp++)
 447     {
 448         item = ritem[*isp];
 449         if (item < 0)
 450         {
 451             redset[count++] = (Value_t) - item;
 452         }
 453     }
 454
 455     if (count)
 456     {
 457         p = (reductions *)allocate((sizeof(reductions) +
 458                                       (unsigned)(count - 1) *
 459                                     sizeof(short)));
 460
 461         p->number = this_state->number;
 462         p->nreds = count;
 463
 464         rp1 = redset;
 465         rp2 = p->rules;
 466         rend = rp1 + count;
 467
 468         while (rp1 < rend)
 469             *rp2++ = *rp1++;
 470
 471         if (last_reduction)
 472         {
 473             last_reduction->next = p;
 474             last_reduction = p;
 475         }
 476         else
 477         {
 478             first_reduction = p;
 479             last_reduction = p;
 480         }
 481     }
 482 }
 483
 484 static void
 485 set_derives(void)
 486 {
 487     Value_t i, k;
 488     int lhs;
 489     short *rules;
 490
 491     derives = NEW2(nsyms, short *);
 492     rules = NEW2(nvars + nrules, short);
 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     short *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 = MALLOC(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     DO_FREE(derives[start_symbol]);
 600     DO_FREE(derives);
 601     DO_FREE(nullable);
 602 }
 603 #endif