external/bsd/byacc/dist/lr0.c

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