lr0.c

   1 /* $Id: lr0.c,v 1.9 2009/10/27 09:20:39 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 = 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     if (p == 0)
 232         no_space();
 233
 234     p->next = 0;
 235     p->link = 0;
 236     p->number = 0;
 237     p->accessing_symbol = 0;
 238     p->nitems = (Value_t) i;
 239
 240     for (i = 0; start_derives[i] >= 0; ++i)
 241         p->items[i] = rrhs[start_derives[i]];
 242
 243     first_state = last_state = this_state = p;
 244     nstates = 1;
 245 }
 246
 247 static void
 248 new_itemsets(void)
 249 {
 250     Value_t i;
 251     int shiftcount;
 252     short *isp;
 253     short *ksp;
 254     Value_t symbol;
 255
 256     for (i = 0; i < nsyms; i++)
 257         kernel_end[i] = 0;
 258
 259     shiftcount = 0;
 260     isp = itemset;
 261     while (isp < itemsetend)
 262     {
 263         i = *isp++;
 264         symbol = ritem[i];
 265         if (symbol > 0)
 266         {
 267             ksp = kernel_end[symbol];
 268             if (!ksp)
 269             {
 270                 shift_symbol[shiftcount++] = symbol;
 271                 ksp = kernel_base[symbol];
 272             }
 273
 274             *ksp++ = (Value_t) (i + 1);
 275             kernel_end[symbol] = ksp;
 276         }
 277     }
 278
 279     nshifts = shiftcount;
 280 }
 281
 282 static core *
 283 new_state(int symbol)
 284 {
 285     unsigned n;
 286     core *p;
 287     short *isp1;
 288     short *isp2;
 289     short *iend;
 290
 291 #ifdef  TRACE
 292     fprintf(stderr, "Entering new_state(%d)\n", symbol);
 293 #endif
 294
 295     if (nstates >= MAXSHORT)
 296         fatal("too many states");
 297
 298     isp1 = kernel_base[symbol];
 299     iend = kernel_end[symbol];
 300     n = (unsigned)(iend - isp1);
 301
 302     p = (core *)allocate((unsigned)(sizeof(core) + (n - 1) * sizeof(short)));
 303     p->accessing_symbol = (Value_t) symbol;
 304     p->number = (Value_t) nstates;
 305     p->nitems = (Value_t) n;
 306
 307     isp2 = p->items;
 308     while (isp1 < iend)
 309         *isp2++ = *isp1++;
 310
 311     last_state->next = p;
 312     last_state = p;
 313
 314     nstates++;
 315
 316     return (p);
 317 }
 318
 319 /* show_cores is used for debugging */
 320
 321 void
 322 show_cores(void)
 323 {
 324     core *p;
 325     int i, j, k, n;
 326     int itemno;
 327
 328     k = 0;
 329     for (p = first_state; p; ++k, p = p->next)
 330     {
 331         if (k)
 332             printf("\n");
 333         printf("state %d, number = %d, accessing symbol = %s\n",
 334                k, p->number, symbol_name[p->accessing_symbol]);
 335         n = p->nitems;
 336         for (i = 0; i < n; ++i)
 337         {
 338             itemno = p->items[i];
 339             printf("%4d  ", itemno);
 340             j = itemno;
 341             while (ritem[j] >= 0)
 342                 ++j;
 343             printf("%s :", symbol_name[rlhs[-ritem[j]]]);
 344             j = rrhs[-ritem[j]];
 345             while (j < itemno)
 346                 printf(" %s", symbol_name[ritem[j++]]);
 347             printf(" .");
 348             while (ritem[j] >= 0)
 349                 printf(" %s", symbol_name[ritem[j++]]);
 350             printf("\n");
 351             fflush(stdout);
 352         }
 353     }
 354 }
 355
 356 /* show_ritems is used for debugging */
 357
 358 void
 359 show_ritems(void)
 360 {
 361     int i;
 362
 363     for (i = 0; i < nitems; ++i)
 364         printf("ritem[%d] = %d\n", i, ritem[i]);
 365 }
 366
 367 /* show_rrhs is used for debugging */
 368 void
 369 show_rrhs(void)
 370 {
 371     int i;
 372
 373     for (i = 0; i < nrules; ++i)
 374         printf("rrhs[%d] = %d\n", i, rrhs[i]);
 375 }
 376
 377 /* show_shifts is used for debugging */
 378
 379 void
 380 show_shifts(void)
 381 {
 382     shifts *p;
 383     int i, j, k;
 384
 385     k = 0;
 386     for (p = first_shift; p; ++k, p = p->next)
 387     {
 388         if (k)
 389             printf("\n");
 390         printf("shift %d, number = %d, nshifts = %d\n", k, p->number,
 391                p->nshifts);
 392         j = p->nshifts;
 393         for (i = 0; i < j; ++i)
 394             printf("\t%d\n", p->shift[i]);
 395     }
 396 }
 397
 398 static void
 399 save_shifts(void)
 400 {
 401     shifts *p;
 402     short *sp1;
 403     short *sp2;
 404     short *send;
 405
 406     p = (shifts *)allocate((unsigned)(sizeof(shifts) +
 407                                         (unsigned)(nshifts - 1) * sizeof(short)));
 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     short *isp;
 435     short *rp1;
 436     short *rp2;
 437     int item;
 438     Value_t count;
 439     reductions *p;
 440     short *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((unsigned)(sizeof(reductions) +
 455                                                 (unsigned)(count - 1) *
 456                                               sizeof(short)));
 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     short *rules;
 487
 488     derives = NEW2(nsyms, short *);
 489     rules = NEW2(nvars + nrules, short);
 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     short *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 = MALLOC(nsyms);
 543     if (nullable == 0)
 544         no_space();
 545
 546     for (i = 0; i < nsyms; ++i)
 547         nullable[i] = 0;
 548
 549     done_flag = 0;
 550     while (!done_flag)
 551     {
 552         done_flag = 1;
 553         for (i = 1; i < nitems; i++)
 554         {
 555             empty = 1;
 556             while ((j = ritem[i]) >= 0)
 557             {
 558                 if (!nullable[j])
 559                     empty = 0;
 560                 ++i;
 561             }
 562             if (empty)
 563             {
 564                 j = rlhs[-j];
 565                 if (!nullable[j])
 566                 {
 567                     nullable[j] = 1;
 568                     done_flag = 0;
 569                 }
 570             }
 571         }
 572     }
 573
 574 #ifdef DEBUG
 575     for (i = 0; i < nsyms; i++)
 576     {
 577         if (nullable[i])
 578             printf("%s is nullable\n", symbol_name[i]);
 579         else
 580             printf("%s is not nullable\n", symbol_name[i]);
 581     }
 582 #endif
 583 }
 584
 585 void
 586 lr0(void)
 587 {
 588     set_derives();
 589     set_nullable();
 590     generate_states();
 591 }
 592
 593 #ifdef NO_LEAKS
 594 void
 595 lr0_leaks(void)
 596 {
 597     DO_FREE(derives[start_symbol]);
 598     DO_FREE(derives);
 599     DO_FREE(nullable);
 600 }
 601 #endif