bin/yacc/lr0.c

   1 /* $OpenBSD: lr0.c,v 1.18 2014/03/13 01:18:22 tedu Exp $         */
   2 /* $NetBSD: lr0.c,v 1.4 1996/03/19 03:21:35 jtc Exp $    */
   3
   4 /*
   5  * Copyright (c) 1989 The Regents of the University of California.
   6  * All rights reserved.
   7  *
   8  * This code is derived from software contributed to Berkeley by
   9  * Robert Paul Corbett.
  10  *
  11  * Redistribution and use in source and binary forms, with or without
  12  * modification, are permitted provided that the following conditions
  13  * are met:
  14  * 1. Redistributions of source code must retain the above copyright
  15  *    notice, this list of conditions and the following disclaimer.
  16  * 2. Redistributions in binary form must reproduce the above copyright
  17  *    notice, this list of conditions and the following disclaimer in the
  18  *    documentation and/or other materials provided with the distribution.
  19  * 3. Neither the name of the University nor the names of its contributors
  20  *    may be used to endorse or promote products derived from this software
  21  *    without specific prior written permission.
  22  *
  23  * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
  24  * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
  25  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
  26  * ARE DISCLAIMED.  IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
  27  * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
  28  * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
  29  * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
  30  * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
  31  * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
  32  * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
  33  * SUCH DAMAGE.
  34  */
  35
  36 #include "defs.h"
  37
  38 extern short *itemset;
  39 extern short *itemsetend;
  40 extern unsigned *ruleset;
  41
  42 int nstates;
  43 core *first_state;
  44 shifts *first_shift;
  45 reductions *first_reduction;
  46
  47 short get_state(int);
  48 core *new_state(int);
  49
  50 void allocate_itemsets(void);
  51 void allocate_storage(void);
  52 void append_states(void);
  53 void free_storage(void);
  54 void generate_states(void);
  55 void initialize_states(void);
  56 void new_itemsets(void);
  57 void save_shifts(void);
  58 void save_reductions(void);
  59 void set_derives(void);
  60 void print_derives(void);
  61 void set_nullable(void);
  62
  63 static core **state_set;
  64 static core *this_state;
  65 static core *last_state;
  66 static shifts *last_shift;
  67 static reductions *last_reduction;
  68
  69 static int nshifts;
  70 static short *shift_symbol;
  71
  72 static short *redset;
  73 static short *shiftset;
  74
  75 static short **kernel_base;
  76 static short **kernel_end;
  77 static short *kernel_items;
  78
  79 void
  80 allocate_itemsets(void)
  81 {
  82         short *itemp, *item_end;
  83         int i, count, max, symbol;
  84         short *symbol_count;
  85
  86         count = 0;
  87         symbol_count = NEW2(nsyms, short);
  88
  89         item_end = ritem + nitems;
  90         for (itemp = ritem; itemp < item_end; itemp++) {
  91                 symbol = *itemp;
  92                 if (symbol >= 0) {
  93                         count++;
  94                         symbol_count[symbol]++;
  95                 }
  96         }
  97
  98         kernel_base = NEW2(nsyms, short *);
  99         kernel_items = NEW2(count, short);
 100
 101         count = 0;
 102         max = 0;
 103         for (i = 0; i < nsyms; i++) {
 104                 kernel_base[i] = kernel_items + count;
 105                 count += symbol_count[i];
 106                 if (max < symbol_count[i])
 107                         max = symbol_count[i];
 108         }
 109
 110         shift_symbol = symbol_count;
 111         kernel_end = NEW2(nsyms, short *);
 112 }
 113
 114 void
 115 allocate_storage(void)
 116 {
 117         allocate_itemsets();
 118         shiftset = NEW2(nsyms, short);
 119         redset = NEW2(nrules + 1, short);
 120         state_set = NEW2(nitems, core *);
 121 }
 122
 123 void
 124 append_states(void)
 125 {
 126         int i, j, symbol;
 127
 128 #ifdef  TRACE
 129         fprintf(stderr, "Entering append_states()\n");
 130 #endif
 131         for (i = 1; i < nshifts; i++) {
 132                 symbol = shift_symbol[i];
 133                 j = i;
 134                 while (j > 0 && shift_symbol[j - 1] > symbol) {
 135                         shift_symbol[j] = shift_symbol[j - 1];
 136                         j--;
 137                 }
 138                 shift_symbol[j] = symbol;
 139         }
 140
 141         for (i = 0; i < nshifts; i++) {
 142                 symbol = shift_symbol[i];
 143                 shiftset[i] = get_state(symbol);
 144         }
 145 }
 146
 147 void
 148 free_storage(void)
 149 {
 150         free(shift_symbol);
 151         free(redset);
 152         free(shiftset);
 153         free(kernel_base);
 154         free(kernel_end);
 155         free(kernel_items);
 156         free(state_set);
 157 }
 158
 159
 160 void
 161 generate_states(void)
 162 {
 163         allocate_storage();
 164         itemset = NEW2(nitems, short);
 165         ruleset = NEW2(WORDSIZE(nrules), unsigned);
 166         set_first_derives();
 167         initialize_states();
 168
 169         while (this_state) {
 170                 closure(this_state->items, this_state->nitems);
 171                 save_reductions();
 172                 new_itemsets();
 173                 append_states();
 174
 175                 if (nshifts > 0)
 176                         save_shifts();
 177
 178                 this_state = this_state->next;
 179         }
 180
 181         finalize_closure();
 182         free_storage();
 183 }
 184
 185
 186
 187 short
 188 get_state(int symbol)
 189 {
 190         int n, found, key;
 191         short *isp1, *isp2, *iend;
 192         core *sp;
 193
 194 #ifdef  TRACE
 195         fprintf(stderr, "Entering get_state(%d)\n", symbol);
 196 #endif
 197
 198         isp1 = kernel_base[symbol];
 199         iend = kernel_end[symbol];
 200         n = iend - isp1;
 201
 202         key = *isp1;
 203         assert(0 <= key && key < nitems);
 204         sp = state_set[key];
 205         if (sp) {
 206                 found = 0;
 207                 while (!found) {
 208                         if (sp->nitems == n) {
 209                                 found = 1;
 210                                 isp1 = kernel_base[symbol];
 211                                 isp2 = sp->items;
 212
 213                                 while (found && isp1 < iend) {
 214                                         if (*isp1++ != *isp2++)
 215                                                 found = 0;
 216                                 }
 217                         }
 218                         if (!found) {
 219                                 if (sp->link) {
 220                                         sp = sp->link;
 221                                 } else {
 222                                         sp = sp->link = new_state(symbol);
 223                                         found = 1;
 224                                 }
 225                         }
 226                 }
 227         } else {
 228                 state_set[key] = sp = new_state(symbol);
 229         }
 230
 231         return (sp->number);
 232 }
 233
 234
 235 void
 236 initialize_states(void)
 237 {
 238         int i;
 239         short *start_derives;
 240         core *p;
 241
 242         start_derives = derives[start_symbol];
 243         for (i = 0; start_derives[i] >= 0; ++i)
 244                 continue;
 245
 246         p = malloc(sizeof(core) + i * sizeof(short));
 247         if (p == NULL)
 248                 no_space();
 249
 250         p->next = 0;
 251         p->link = 0;
 252         p->number = 0;
 253         p->accessing_symbol = 0;
 254         p->nitems = i;
 255
 256         for (i = 0; start_derives[i] >= 0; ++i)
 257                 p->items[i] = rrhs[start_derives[i]];
 258
 259         first_state = last_state = this_state = p;
 260         nstates = 1;
 261 }
 262
 263 void
 264 new_itemsets(void)
 265 {
 266         int i, shiftcount;
 267         short *isp, *ksp;
 268         int symbol;
 269
 270         memset(kernel_end, 0, nsyms * sizeof(short *));
 271
 272         shiftcount = 0;
 273         isp = itemset;
 274         while (isp < itemsetend) {
 275                 i = *isp++;
 276                 symbol = ritem[i];
 277                 if (symbol > 0) {
 278                         ksp = kernel_end[symbol];
 279                         if (!ksp) {
 280                                 shift_symbol[shiftcount++] = symbol;
 281                                 ksp = kernel_base[symbol];
 282                         }
 283                         *ksp++ = i + 1;
 284                         kernel_end[symbol] = ksp;
 285                 }
 286         }
 287
 288         nshifts = shiftcount;
 289 }
 290
 291
 292
 293 core *
 294 new_state(int symbol)
 295 {
 296         int n;
 297         core *p;
 298         short *isp1, *isp2, *iend;
 299
 300 #ifdef  TRACE
 301         fprintf(stderr, "Entering new_state(%d)\n", symbol);
 302 #endif
 303
 304         if (nstates >= MAXSHORT)
 305                 fatal("too many states");
 306
 307         isp1 = kernel_base[symbol];
 308         iend = kernel_end[symbol];
 309         n = iend - isp1;
 310
 311         p = allocate(sizeof(core) + (n - 1) * sizeof(short));
 312         p->accessing_symbol = symbol;
 313         p->number = nstates;
 314         p->nitems = n;
 315
 316         isp2 = p->items;
 317         while (isp1 < iend)
 318                 *isp2++ = *isp1++;
 319
 320         last_state->next = p;
 321         last_state = p;
 322
 323         nstates++;
 324
 325         return (p);
 326 }
 327
 328
 329 void
 330 save_shifts(void)
 331 {
 332         shifts *p;
 333         short *sp1, *sp2, *send;
 334
 335         p = allocate(sizeof(shifts) + (nshifts - 1) * sizeof(short));
 336
 337         p->number = this_state->number;
 338         p->nshifts = nshifts;
 339
 340         sp1 = shiftset;
 341         sp2 = p->shift;
 342         send = shiftset + nshifts;
 343
 344         while (sp1 < send)
 345                 *sp2++ = *sp1++;
 346
 347         if (last_shift) {
 348                 last_shift->next = p;
 349                 last_shift = p;
 350         } else {
 351                 first_shift = p;
 352                 last_shift = p;
 353         }
 354 }
 355
 356
 357 void
 358 save_reductions(void)
 359 {
 360         short *isp, *rp1, *rp2;
 361         int item, count;
 362         reductions *p;
 363         short *rend;
 364
 365         count = 0;
 366         for (isp = itemset; isp < itemsetend; isp++) {
 367                 item = ritem[*isp];
 368                 if (item < 0) {
 369                         redset[count++] = -item;
 370                 }
 371         }
 372
 373         if (count) {
 374                 p = allocate(sizeof(reductions) + (count - 1) * sizeof(short));
 375
 376                 p->number = this_state->number;
 377                 p->nreds = count;
 378
 379                 rp1 = redset;
 380                 rp2 = p->rules;
 381                 rend = rp1 + count;
 382
 383                 while (rp1 < rend)
 384                         *rp2++ = *rp1++;
 385
 386                 if (last_reduction) {
 387                         last_reduction->next = p;
 388                         last_reduction = p;
 389                 } else {
 390                         first_reduction = p;
 391                         last_reduction = p;
 392                 }
 393         }
 394 }
 395
 396 void
 397 set_derives(void)
 398 {
 399         int i, k, lhs;
 400         short *rules;
 401
 402         derives = NEW2(nsyms, short *);
 403         rules = NEW2(nvars + nrules, short);
 404
 405         k = 0;
 406         for (lhs = start_symbol; lhs < nsyms; lhs++) {
 407                 derives[lhs] = rules + k;
 408                 for (i = 0; i < nrules; i++) {
 409                         if (rlhs[i] == lhs) {
 410                                 rules[k] = i;
 411                                 k++;
 412                         }
 413                 }
 414                 rules[k] = -1;
 415                 k++;
 416         }
 417
 418 #ifdef  DEBUG
 419         print_derives();
 420 #endif
 421 }
 422
 423 void
 424 free_derives(void)
 425 {
 426         free(derives[start_symbol]);
 427         free(derives);
 428 }
 429
 430 #ifdef  DEBUG
 431 void
 432 print_derives(void)
 433 {
 434         int i;
 435         short *sp;
 436
 437         printf("\nDERIVES\n\n");
 438
 439         for (i = start_symbol; i < nsyms; i++) {
 440                 printf("%s derives ", symbol_name[i]);
 441                 for (sp = derives[i]; *sp >= 0; sp++) {
 442                         printf("  %d", *sp);
 443                 }
 444                 putchar('\n');
 445         }
 446
 447         putchar('\n');
 448 }
 449 #endif
 450
 451 void
 452 set_nullable(void)
 453 {
 454         int i, j;
 455         int empty;
 456         int done;
 457
 458         nullable = calloc(1, nsyms);
 459         if (nullable == NULL)
 460                 no_space();
 461
 462         done = 0;
 463         while (!done) {
 464                 done = 1;
 465                 for (i = 1; i < nitems; i++) {
 466                         empty = 1;
 467                         while ((j = ritem[i]) >= 0) {
 468                                 if (!nullable[j])
 469                                         empty = 0;
 470                                 ++i;
 471                         }
 472                         if (empty) {
 473                                 j = rlhs[-j];
 474                                 if (!nullable[j]) {
 475                                         nullable[j] = 1;
 476                                         done = 0;
 477                                 }
 478                         }
 479                 }
 480         }
 481
 482 #ifdef DEBUG
 483         for (i = 0; i < nsyms; i++) {
 484                 if (nullable[i])
 485                         printf("%s is nullable\n", symbol_name[i]);
 486                 else
 487                         printf("%s is not nullable\n", symbol_name[i]);
 488         }
 489 #endif
 490 }
 491
 492 void
 493 free_nullable(void)
 494 {
 495         free(nullable);
 496 }
 497
 498 void
 499 lr0(void)
 500 {
 501         set_derives();
 502         set_nullable();
 503         generate_states();
 504 }