util/byacc/lalr.c

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