l4/pkg/ocaml/contrib/yacc/lr0.c

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