contrib/byacc/lalr.c

   1 /* $Id: lalr.c,v 1.9 2009/10/27 09:49:27 tom Exp $ */
   2
   3 #include "defs.h"
   4
   5 typedef struct shorts
   6 {
   7     struct shorts *next;
   8     Value_t value;
   9 }
  10 shorts;
  11
  12 static Value_t map_goto(int state, int symbol);
  13 static Value_t **transpose(Value_t ** R, int n);
  14 static void add_lookback_edge(int stateno, int ruleno, int gotono);
  15 static void build_relations(void);
  16 static void compute_FOLLOWS(void);
  17 static void compute_lookaheads(void);
  18 static void digraph(Value_t ** relation);
  19 static void initialize_F(void);
  20 static void initialize_LA(void);
  21 static void set_accessing_symbol(void);
  22 static void set_goto_map(void);
  23 static void set_maxrhs(void);
  24 static void set_reduction_table(void);
  25 static void set_shift_table(void);
  26 static void set_state_table(void);
  27 static void traverse(int i);
  28
  29 static int tokensetsize;
  30 Value_t *lookaheads;
  31 Value_t *LAruleno;
  32 unsigned *LA;
  33 Value_t *accessing_symbol;
  34 core **state_table;
  35 shifts **shift_table;
  36 reductions **reduction_table;
  37 Value_t *goto_map;
  38 Value_t *from_state;
  39 Value_t *to_state;
  40
  41 static Value_t infinity;
  42 static int maxrhs;
  43 static int ngotos;
  44 static unsigned *F;
  45 static Value_t **includes;
  46 static shorts **lookback;
  47 static Value_t **R;
  48 static Value_t *INDEX;
  49 static Value_t *VERTICES;
  50 static Value_t top;
  51
  52 void
  53 lalr(void)
  54 {
  55     tokensetsize = WORDSIZE(ntokens);
  56
  57     set_state_table();
  58     set_accessing_symbol();
  59     set_shift_table();
  60     set_reduction_table();
  61     set_maxrhs();
  62     initialize_LA();
  63     set_goto_map();
  64     initialize_F();
  65     build_relations();
  66     compute_FOLLOWS();
  67     compute_lookaheads();
  68 }
  69
  70 static void
  71 set_state_table(void)
  72 {
  73     core *sp;
  74
  75     state_table = NEW2(nstates, core *);
  76     for (sp = first_state; sp; sp = sp->next)
  77         state_table[sp->number] = sp;
  78 }
  79
  80 static void
  81 set_accessing_symbol(void)
  82 {
  83     core *sp;
  84
  85     accessing_symbol = NEW2(nstates, Value_t);
  86     for (sp = first_state; sp; sp = sp->next)
  87         accessing_symbol[sp->number] = sp->accessing_symbol;
  88 }
  89
  90 static void
  91 set_shift_table(void)
  92 {
  93     shifts *sp;
  94
  95     shift_table = NEW2(nstates, shifts *);
  96     for (sp = first_shift; sp; sp = sp->next)
  97         shift_table[sp->number] = sp;
  98 }
  99
 100 static void
 101 set_reduction_table(void)
 102 {
 103     reductions *rp;
 104
 105     reduction_table = NEW2(nstates, reductions *);
 106     for (rp = first_reduction; rp; rp = rp->next)
 107         reduction_table[rp->number] = rp;
 108 }
 109
 110 static void
 111 set_maxrhs(void)
 112 {
 113     Value_t *itemp;
 114     Value_t *item_end;
 115     int length;
 116     int max;
 117
 118     length = 0;
 119     max = 0;
 120     item_end = ritem + nitems;
 121     for (itemp = ritem; itemp < item_end; itemp++)
 122     {
 123         if (*itemp >= 0)
 124         {
 125             length++;
 126         }
 127         else
 128         {
 129             if (length > max)
 130                 max = length;
 131             length = 0;
 132         }
 133     }
 134
 135     maxrhs = max;
 136 }
 137
 138 static void
 139 initialize_LA(void)
 140 {
 141     int i, j, k;
 142     reductions *rp;
 143
 144     lookaheads = NEW2(nstates + 1, Value_t);
 145
 146     k = 0;
 147     for (i = 0; i < nstates; i++)
 148     {
 149         lookaheads[i] = (Value_t) k;
 150         rp = reduction_table[i];
 151         if (rp)
 152             k += rp->nreds;
 153     }
 154     lookaheads[nstates] = (Value_t) k;
 155
 156     LA = NEW2(k * tokensetsize, unsigned);
 157     LAruleno = NEW2(k, Value_t);
 158     lookback = NEW2(k, shorts *);
 159
 160     k = 0;
 161     for (i = 0; i < nstates; i++)
 162     {
 163         rp = reduction_table[i];
 164         if (rp)
 165         {
 166             for (j = 0; j < rp->nreds; j++)
 167             {
 168                 LAruleno[k] = rp->rules[j];
 169                 k++;
 170             }
 171         }
 172     }
 173 }
 174
 175 static void
 176 set_goto_map(void)
 177 {
 178     shifts *sp;
 179     int i;
 180     int symbol;
 181     int k;
 182     Value_t *temp_map;
 183     Value_t state2;
 184     Value_t state1;
 185
 186     goto_map = NEW2(nvars + 1, Value_t) - ntokens;
 187     temp_map = NEW2(nvars + 1, Value_t) - ntokens;
 188
 189     ngotos = 0;
 190     for (sp = first_shift; sp; sp = sp->next)
 191     {
 192         for (i = sp->nshifts - 1; i >= 0; i--)
 193         {
 194             symbol = accessing_symbol[sp->shift[i]];
 195
 196             if (ISTOKEN(symbol))
 197                 break;
 198
 199             if (ngotos == MAXSHORT)
 200                 fatal("too many gotos");
 201
 202             ngotos++;
 203             goto_map[symbol]++;
 204         }
 205     }
 206
 207     k = 0;
 208     for (i = ntokens; i < nsyms; i++)
 209     {
 210         temp_map[i] = (Value_t) k;
 211         k += goto_map[i];
 212     }
 213
 214     for (i = ntokens; i < nsyms; i++)
 215         goto_map[i] = temp_map[i];
 216
 217     goto_map[nsyms] = (Value_t) ngotos;
 218     temp_map[nsyms] = (Value_t) ngotos;
 219
 220     from_state = NEW2(ngotos, Value_t);
 221     to_state = NEW2(ngotos, Value_t);
 222
 223     for (sp = first_shift; sp; sp = sp->next)
 224     {
 225         state1 = sp->number;
 226         for (i = sp->nshifts - 1; i >= 0; i--)
 227         {
 228             state2 = sp->shift[i];
 229             symbol = accessing_symbol[state2];
 230
 231             if (ISTOKEN(symbol))
 232                 break;
 233
 234             k = temp_map[symbol]++;
 235             from_state[k] = state1;
 236             to_state[k] = state2;
 237         }
 238     }
 239
 240     FREE(temp_map + ntokens);
 241 }
 242
 243 /*  Map_goto maps a state/symbol pair into its numeric representation.  */
 244
 245 static Value_t
 246 map_goto(int state, int symbol)
 247 {
 248     int high;
 249     int low;
 250     int middle;
 251     int s;
 252
 253     low = goto_map[symbol];
 254     high = goto_map[symbol + 1];
 255
 256     for (;;)
 257     {
 258         assert(low <= high);
 259         middle = (low + high) >> 1;
 260         s = from_state[middle];
 261         if (s == state)
 262             return (Value_t) (middle);
 263         else if (s < state)
 264             low = middle + 1;
 265         else
 266             high = middle - 1;
 267     }
 268 }
 269
 270 static void
 271 initialize_F(void)
 272 {
 273     int i;
 274     int j;
 275     int k;
 276     shifts *sp;
 277     Value_t *edge;
 278     unsigned *rowp;
 279     Value_t *rp;
 280     Value_t **reads;
 281     int nedges;
 282     int stateno;
 283     int symbol;
 284     int nwords;
 285
 286     nwords = ngotos * tokensetsize;
 287     F = NEW2(nwords, unsigned);
 288
 289     reads = NEW2(ngotos, Value_t *);
 290     edge = NEW2(ngotos + 1, Value_t);
 291     nedges = 0;
 292
 293     rowp = F;
 294     for (i = 0; i < ngotos; i++)
 295     {
 296         stateno = to_state[i];
 297         sp = shift_table[stateno];
 298
 299         if (sp)
 300         {
 301             k = sp->nshifts;
 302
 303             for (j = 0; j < k; j++)
 304             {
 305                 symbol = accessing_symbol[sp->shift[j]];
 306                 if (ISVAR(symbol))
 307                     break;
 308                 SETBIT(rowp, symbol);
 309             }
 310
 311             for (; j < k; j++)
 312             {
 313                 symbol = accessing_symbol[sp->shift[j]];
 314                 if (nullable[symbol])
 315                     edge[nedges++] = map_goto(stateno, symbol);
 316             }
 317
 318             if (nedges)
 319             {
 320                 reads[i] = rp = NEW2(nedges + 1, Value_t);
 321
 322                 for (j = 0; j < nedges; j++)
 323                     rp[j] = edge[j];
 324
 325                 rp[nedges] = -1;
 326                 nedges = 0;
 327             }
 328         }
 329
 330         rowp += tokensetsize;
 331     }
 332
 333     SETBIT(F, 0);
 334     digraph(reads);
 335
 336     for (i = 0; i < ngotos; i++)
 337     {
 338         if (reads[i])
 339             FREE(reads[i]);
 340     }
 341
 342     FREE(reads);
 343     FREE(edge);
 344 }
 345
 346 static void
 347 build_relations(void)
 348 {
 349     int i;
 350     int j;
 351     int k;
 352     Value_t *rulep;
 353     Value_t *rp;
 354     shifts *sp;
 355     int length;
 356     int nedges;
 357     int done_flag;
 358     Value_t state1;
 359     Value_t stateno;
 360     int symbol1;
 361     int symbol2;
 362     Value_t *shortp;
 363     Value_t *edge;
 364     Value_t *states;
 365     Value_t **new_includes;
 366
 367     includes = NEW2(ngotos, Value_t *);
 368     edge = NEW2(ngotos + 1, Value_t);
 369     states = NEW2(maxrhs + 1, Value_t);
 370
 371     for (i = 0; i < ngotos; i++)
 372     {
 373         nedges = 0;
 374         state1 = from_state[i];
 375         symbol1 = accessing_symbol[to_state[i]];
 376
 377         for (rulep = derives[symbol1]; *rulep >= 0; rulep++)
 378         {
 379             length = 1;
 380             states[0] = state1;
 381             stateno = state1;
 382
 383             for (rp = ritem + rrhs[*rulep]; *rp >= 0; rp++)
 384             {
 385                 symbol2 = *rp;
 386                 sp = shift_table[stateno];
 387                 k = sp->nshifts;
 388
 389                 for (j = 0; j < k; j++)
 390                 {
 391                     stateno = sp->shift[j];
 392                     if (accessing_symbol[stateno] == symbol2)
 393                         break;
 394                 }
 395
 396                 states[length++] = stateno;
 397             }
 398
 399             add_lookback_edge(stateno, *rulep, i);
 400
 401             length--;
 402             done_flag = 0;
 403             while (!done_flag)
 404             {
 405                 done_flag = 1;
 406                 rp--;
 407                 if (ISVAR(*rp))
 408                 {
 409                     stateno = states[--length];
 410                     edge[nedges++] = map_goto(stateno, *rp);
 411                     if (nullable[*rp] && length > 0)
 412                         done_flag = 0;
 413                 }
 414             }
 415         }
 416
 417         if (nedges)
 418         {
 419             includes[i] = shortp = NEW2(nedges + 1, Value_t);
 420             for (j = 0; j < nedges; j++)
 421                 shortp[j] = edge[j];
 422             shortp[nedges] = -1;
 423         }
 424     }
 425
 426     new_includes = transpose(includes, ngotos);
 427
 428     for (i = 0; i < ngotos; i++)
 429         if (includes[i])
 430             FREE(includes[i]);
 431
 432     FREE(includes);
 433
 434     includes = new_includes;
 435
 436     FREE(edge);
 437     FREE(states);
 438 }
 439
 440 static void
 441 add_lookback_edge(int stateno, int ruleno, int gotono)
 442 {
 443     int i, k;
 444     int found;
 445     shorts *sp;
 446
 447     i = lookaheads[stateno];
 448     k = lookaheads[stateno + 1];
 449     found = 0;
 450     while (!found && i < k)
 451     {
 452         if (LAruleno[i] == ruleno)
 453             found = 1;
 454         else
 455             ++i;
 456     }
 457     assert(found);
 458
 459     sp = NEW(shorts);
 460     sp->next = lookback[i];
 461     sp->value = (Value_t) gotono;
 462     lookback[i] = sp;
 463 }
 464
 465 static Value_t **
 466 transpose(Value_t ** R2, int n)
 467 {
 468     Value_t **new_R;
 469     Value_t **temp_R;
 470     Value_t *nedges;
 471     Value_t *sp;
 472     int i;
 473     int k;
 474
 475     nedges = NEW2(n, Value_t);
 476
 477     for (i = 0; i < n; i++)
 478     {
 479         sp = R2[i];
 480         if (sp)
 481         {
 482             while (*sp >= 0)
 483                 nedges[*sp++]++;
 484         }
 485     }
 486
 487     new_R = NEW2(n, Value_t *);
 488     temp_R = NEW2(n, Value_t *);
 489
 490     for (i = 0; i < n; i++)
 491     {
 492         k = nedges[i];
 493         if (k > 0)
 494         {
 495             sp = NEW2(k + 1, Value_t);
 496             new_R[i] = sp;
 497             temp_R[i] = sp;
 498             sp[k] = -1;
 499         }
 500     }
 501
 502     FREE(nedges);
 503
 504     for (i = 0; i < n; i++)
 505     {
 506         sp = R2[i];
 507         if (sp)
 508         {
 509             while (*sp >= 0)
 510                 *temp_R[*sp++]++ = (Value_t) i;
 511         }
 512     }
 513
 514     FREE(temp_R);
 515
 516     return (new_R);
 517 }
 518
 519 static void
 520 compute_FOLLOWS(void)
 521 {
 522     digraph(includes);
 523 }
 524
 525 static void
 526 compute_lookaheads(void)
 527 {
 528     int i, n;
 529     unsigned *fp1, *fp2, *fp3;
 530     shorts *sp, *next;
 531     unsigned *rowp;
 532
 533     rowp = LA;
 534     n = lookaheads[nstates];
 535     for (i = 0; i < n; i++)
 536     {
 537         fp3 = rowp + tokensetsize;
 538         for (sp = lookback[i]; sp; sp = sp->next)
 539         {
 540             fp1 = rowp;
 541             fp2 = F + tokensetsize * sp->value;
 542             while (fp1 < fp3)
 543                 *fp1++ |= *fp2++;
 544         }
 545         rowp = fp3;
 546     }
 547
 548     for (i = 0; i < n; i++)
 549         for (sp = lookback[i]; sp; sp = next)
 550         {
 551             next = sp->next;
 552             FREE(sp);
 553         }
 554
 555     FREE(lookback);
 556     FREE(F);
 557 }
 558
 559 static void
 560 digraph(Value_t ** relation)
 561 {
 562     int i;
 563
 564     infinity = (Value_t) (ngotos + 2);
 565     INDEX = NEW2(ngotos + 1, Value_t);
 566     VERTICES = NEW2(ngotos + 1, Value_t);
 567     top = 0;
 568
 569     R = relation;
 570
 571     for (i = 0; i < ngotos; i++)
 572         INDEX[i] = 0;
 573
 574     for (i = 0; i < ngotos; i++)
 575     {
 576         if (INDEX[i] == 0 && R[i])
 577             traverse(i);
 578     }
 579
 580     FREE(INDEX);
 581     FREE(VERTICES);
 582 }
 583
 584 static void
 585 traverse(int i)
 586 {
 587     unsigned *fp1;
 588     unsigned *fp2;
 589     unsigned *fp3;
 590     int j;
 591     Value_t *rp;
 592
 593     Value_t height;
 594     unsigned *base;
 595
 596     VERTICES[++top] = (Value_t) i;
 597     INDEX[i] = height = top;
 598
 599     base = F + i * tokensetsize;
 600     fp3 = base + tokensetsize;
 601
 602     rp = R[i];
 603     if (rp)
 604     {
 605         while ((j = *rp++) >= 0)
 606         {
 607             if (INDEX[j] == 0)
 608                 traverse(j);
 609
 610             if (INDEX[i] > INDEX[j])
 611                 INDEX[i] = INDEX[j];
 612
 613             fp1 = base;
 614             fp2 = F + j * tokensetsize;
 615
 616             while (fp1 < fp3)
 617                 *fp1++ |= *fp2++;
 618         }
 619     }
 620
 621     if (INDEX[i] == height)
 622     {
 623         for (;;)
 624         {
 625             j = VERTICES[top--];
 626             INDEX[j] = infinity;
 627
 628             if (i == j)
 629                 break;
 630
 631             fp1 = base;
 632             fp2 = F + j * tokensetsize;
 633
 634             while (fp1 < fp3)
 635                 *fp2++ = *fp1++;
 636         }
 637     }
 638 }
 639
 640 #ifdef NO_LEAKS
 641 void
 642 lalr_leaks(void)
 643 {
 644     int i;
 645
 646     if (includes != 0)
 647     {
 648         for (i = 0; i < ngotos; i++)
 649         {
 650             free(includes[i]);
 651         }
 652         DO_FREE(includes);
 653     }
 654 }
 655 #endif