external/bsd/byacc/dist/lr0.c

   1 /*      $NetBSD$        */
   2 /* Id: lr0.c,v 1.9 2009/10/27 09:20:39 tom Exp */
   3
   4 #include "defs.h"
   5
   6 #include <sys/cdefs.h>
   7 __RCSID("$NetBSD: closure.c,v 1.8 2006/05/24 18:01:43 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 = 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     if (p == 0)
 236         no_space();
 237
 238     p->next = 0;
 239     p->link = 0;
 240     p->number = 0;
 241     p->accessing_symbol = 0;
 242     p->nitems = (Value_t) i;
 243
 244     for (i = 0; start_derives[i] >= 0; ++i)
 245         p->items[i] = rrhs[start_derives[i]];
 246
 247     first_state = last_state = this_state = p;
 248     nstates = 1;
 249 }
 250
 251 static void
 252 new_itemsets(void)
 253 {
 254     Value_t i;
 255     int shiftcount;
 256     short *isp;
 257     short *ksp;
 258     Value_t symbol;
 259
 260     for (i = 0; i < nsyms; i++)
 261         kernel_end[i] = 0;
 262
 263     shiftcount = 0;
 264     isp = itemset;
 265     while (isp < itemsetend)
 266     {
 267         i = *isp++;
 268         symbol = ritem[i];
 269         if (symbol > 0)
 270         {
 271             ksp = kernel_end[symbol];
 272             if (!ksp)
 273             {
 274                 shift_symbol[shiftcount++] = symbol;
 275                 ksp = kernel_base[symbol];
 276             }
 277
 278             *ksp++ = (Value_t) (i + 1);
 279             kernel_end[symbol] = ksp;
 280         }
 281     }
 282
 283     nshifts = shiftcount;
 284 }
 285
 286 static core *
 287 new_state(int symbol)
 288 {
 289     unsigned n;
 290     core *p;
 291     short *isp1;
 292     short *isp2;
 293     short *iend;
 294
 295 #ifdef  TRACE
 296     fprintf(stderr, "Entering new_state(%d)\n", symbol);
 297 #endif
 298
 299     if (nstates >= MAXSHORT)
 300         fatal("too many states");
 301
 302     isp1 = kernel_base[symbol];
 303     iend = kernel_end[symbol];
 304     n = (unsigned)(iend - isp1);
 305
 306     p = (core *)allocate((unsigned)(sizeof(core) + (n - 1) * sizeof(short)));
 307     p->accessing_symbol = (Value_t) symbol;
 308     p->number = (Value_t) nstates;
 309     p->nitems = (Value_t) n;
 310
 311     isp2 = p->items;
 312     while (isp1 < iend)
 313         *isp2++ = *isp1++;
 314
 315     last_state->next = p;
 316     last_state = p;
 317
 318     nstates++;
 319
 320     return (p);
 321 }
 322
 323 /* show_cores is used for debugging */
 324
 325 void
 326 show_cores(void)
 327 {
 328     core *p;
 329     int i, j, k, n;
 330     int itemno;
 331
 332     k = 0;
 333     for (p = first_state; p; ++k, p = p->next)
 334     {
 335         if (k)
 336             printf("\n");
 337         printf("state %d, number = %d, accessing symbol = %s\n",
 338                k, p->number, symbol_name[p->accessing_symbol]);
 339         n = p->nitems;
 340         for (i = 0; i < n; ++i)
 341         {
 342             itemno = p->items[i];
 343             printf("%4d  ", itemno);
 344             j = itemno;
 345             while (ritem[j] >= 0)
 346                 ++j;
 347             printf("%s :", symbol_name[rlhs[-ritem[j]]]);
 348             j = rrhs[-ritem[j]];
 349             while (j < itemno)
 350                 printf(" %s", symbol_name[ritem[j++]]);
 351             printf(" .");
 352             while (ritem[j] >= 0)
 353                 printf(" %s", symbol_name[ritem[j++]]);
 354             printf("\n");
 355             fflush(stdout);
 356         }
 357     }
 358 }
 359
 360 /* show_ritems is used for debugging */
 361
 362 void
 363 show_ritems(void)
 364 {
 365     int i;
 366
 367     for (i = 0; i < nitems; ++i)
 368         printf("ritem[%d] = %d\n", i, ritem[i]);
 369 }
 370
 371 /* show_rrhs is used for debugging */
 372 void
 373 show_rrhs(void)
 374 {
 375     int i;
 376
 377     for (i = 0; i < nrules; ++i)
 378         printf("rrhs[%d] = %d\n", i, rrhs[i]);
 379 }
 380
 381 /* show_shifts is used for debugging */
 382
 383 void
 384 show_shifts(void)
 385 {
 386     shifts *p;
 387     int i, j, k;
 388
 389     k = 0;
 390     for (p = first_shift; p; ++k, p = p->next)
 391     {
 392         if (k)
 393             printf("\n");
 394         printf("shift %d, number = %d, nshifts = %d\n", k, p->number,
 395                p->nshifts);
 396         j = p->nshifts;
 397         for (i = 0; i < j; ++i)
 398             printf("\t%d\n", p->shift[i]);
 399     }
 400 }
 401
 402 static void
 403 save_shifts(void)
 404 {
 405     shifts *p;
 406     short *sp1;
 407     short *sp2;
 408     short *send;
 409
 410     p = (shifts *)allocate((unsigned)(sizeof(shifts) +
 411                                         (unsigned)(nshifts - 1) * sizeof(short)));
 412
 413     p->number = this_state->number;
 414     p->nshifts = (Value_t) nshifts;
 415
 416     sp1 = shiftset;
 417     sp2 = p->shift;
 418     send = shiftset + nshifts;
 419
 420     while (sp1 < send)
 421         *sp2++ = *sp1++;
 422
 423     if (last_shift)
 424     {
 425         last_shift->next = p;
 426         last_shift = p;
 427     }
 428     else
 429     {
 430         first_shift = p;
 431         last_shift = p;
 432     }
 433 }
 434
 435 static void
 436 save_reductions(void)
 437 {
 438     short *isp;
 439     short *rp1;
 440     short *rp2;
 441     int item;
 442     Value_t count;
 443     reductions *p;
 444     short *rend;
 445
 446     count = 0;
 447     for (isp = itemset; isp < itemsetend; isp++)
 448     {
 449         item = ritem[*isp];
 450         if (item < 0)
 451         {
 452             redset[count++] = (Value_t) - item;
 453         }
 454     }
 455
 456     if (count)
 457     {
 458         p = (reductions *)allocate((unsigned)(sizeof(reductions) +
 459                                                 (unsigned)(count - 1) *
 460                                               sizeof(short)));
 461
 462         p->number = this_state->number;
 463         p->nreds = count;
 464
 465         rp1 = redset;
 466         rp2 = p->rules;
 467         rend = rp1 + count;
 468
 469         while (rp1 < rend)
 470             *rp2++ = *rp1++;
 471
 472         if (last_reduction)
 473         {
 474             last_reduction->next = p;
 475             last_reduction = p;
 476         }
 477         else
 478         {
 479             first_reduction = p;
 480             last_reduction = p;
 481         }
 482     }
 483 }
 484
 485 static void
 486 set_derives(void)
 487 {
 488     Value_t i, k;
 489     int lhs;
 490     short *rules;
 491
 492     derives = NEW2(nsyms, short *);
 493     rules = NEW2(nvars + nrules, short);
 494
 495     k = 0;
 496     for (lhs = start_symbol; lhs < nsyms; lhs++)
 497     {
 498         derives[lhs] = rules + k;
 499         for (i = 0; i < nrules; i++)
 500         {
 501             if (rlhs[i] == lhs)
 502             {
 503                 rules[k] = i;
 504                 k++;
 505             }
 506         }
 507         rules[k] = -1;
 508         k++;
 509     }
 510
 511 #ifdef  DEBUG
 512     print_derives();
 513 #endif
 514 }
 515
 516 #ifdef  DEBUG
 517 void
 518 print_derives(void)
 519 {
 520     int i;
 521     short *sp;
 522
 523     printf("\nDERIVES\n\n");
 524
 525     for (i = start_symbol; i < nsyms; i++)
 526     {
 527         printf("%s derives ", symbol_name[i]);
 528         for (sp = derives[i]; *sp >= 0; sp++)
 529         {
 530             printf("  %d", *sp);
 531         }
 532         putchar('\n');
 533     }
 534
 535     putchar('\n');
 536 }
 537 #endif
 538
 539 static void
 540 set_nullable(void)
 541 {
 542     int i, j;
 543     int empty;
 544     int done_flag;
 545
 546     nullable = MALLOC(nsyms);
 547     if (nullable == 0)
 548         no_space();
 549
 550     for (i = 0; i < nsyms; ++i)
 551         nullable[i] = 0;
 552
 553     done_flag = 0;
 554     while (!done_flag)
 555     {
 556         done_flag = 1;
 557         for (i = 1; i < nitems; i++)
 558         {
 559             empty = 1;
 560             while ((j = ritem[i]) >= 0)
 561             {
 562                 if (!nullable[j])
 563                     empty = 0;
 564                 ++i;
 565             }
 566             if (empty)
 567             {
 568                 j = rlhs[-j];
 569                 if (!nullable[j])
 570                 {
 571                     nullable[j] = 1;
 572                     done_flag = 0;
 573                 }
 574             }
 575         }
 576     }
 577
 578 #ifdef DEBUG
 579     for (i = 0; i < nsyms; i++)
 580     {
 581         if (nullable[i])
 582             printf("%s is nullable\n", symbol_name[i]);
 583         else
 584             printf("%s is not nullable\n", symbol_name[i]);
 585     }
 586 #endif
 587 }
 588
 589 void
 590 lr0(void)
 591 {
 592     set_derives();
 593     set_nullable();
 594     generate_states();
 595 }
 596
 597 #ifdef NO_LEAKS
 598 void
 599 lr0_leaks(void)
 600 {
 601     DO_FREE(derives[start_symbol]);
 602     DO_FREE(derives);
 603     DO_FREE(nullable);
 604 }
 605 #endif