src/lalr.c

   1 /* Compute look-ahead criteria for bison,
   2    Copyright 1984, 1986, 1989, 2000 Free Software Foundation, Inc.
   3
   4    This file is part of Bison, the GNU Compiler Compiler.
   5
   6    Bison is free software; you can redistribute it and/or modify
   7    it under the terms of the GNU General Public License as published by
   8    the Free Software Foundation; either version 2, or (at your option)
   9    any later version.
  10
  11    Bison is distributed in the hope that it will be useful,
  12    but WITHOUT ANY WARRANTY; without even the implied warranty of
  13    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  14    GNU General Public License for more details.
  15
  16    You should have received a copy of the GNU General Public License
  17    along with Bison; see the file COPYING.  If not, write to
  18    the Free Software Foundation, Inc., 59 Temple Place - Suite 330,
  19    Boston, MA 02111-1307, USA.  */
  20
  21
  22 /* Compute how to make the finite state machine deterministic; find
  23    which rules need lookahead in each state, and which lookahead
  24    tokens they accept.  */
  25
  26 #include "system.h"
  27 #include "types.h"
  28 #include "LR0.h"
  29 #include "gram.h"
  30 #include "complain.h"
  31 #include "lalr.h"
  32 #include "nullable.h"
  33 #include "derives.h"
  34
  35 /* All the decorated states, indexed by the state number.  Warning:
  36    there is a state_TABLE in LR0.c, but it is different and static.
  37    */
  38 state_t *state_table = NULL;
  39
  40 int tokensetsize;
  41 short *lookaheads;
  42 short *LAruleno;
  43 unsigned *LA;
  44
  45 char *consistent;
  46 short *goto_map;
  47 short *from_state;
  48 short *to_state;
  49
  50 extern void berror PARAMS ((const char *));
  51
  52 static int infinity;
  53 static int maxrhs;
  54 static int ngotos;
  55 static unsigned *F;
  56 static short **includes;
  57 static shorts **lookback;
  58 static short **R;
  59 static short *INDEX;
  60 static short *VERTICES;
  61 static int top;
  62
  63
  64 static void
  65 traverse (int i)
  66 {
  67   unsigned *fp1;
  68   unsigned *fp2;
  69   unsigned *fp3;
  70   int j;
  71   short *rp;
  72
  73   int height;
  74   unsigned *base;
  75
  76   VERTICES[++top] = i;
  77   INDEX[i] = height = top;
  78
  79   base = F + i * tokensetsize;
  80   fp3 = base + tokensetsize;
  81
  82   rp = R[i];
  83   if (rp)
  84     {
  85       while ((j = *rp++) >= 0)
  86         {
  87           if (INDEX[j] == 0)
  88             traverse (j);
  89
  90           if (INDEX[i] > INDEX[j])
  91             INDEX[i] = INDEX[j];
  92
  93           fp1 = base;
  94           fp2 = F + j * tokensetsize;
  95
  96           while (fp1 < fp3)
  97             *fp1++ |= *fp2++;
  98         }
  99     }
 100
 101   if (INDEX[i] == height)
 102     {
 103       for (;;)
 104         {
 105           j = VERTICES[top--];
 106           INDEX[j] = infinity;
 107
 108           if (i == j)
 109             break;
 110
 111           fp1 = base;
 112           fp2 = F + j * tokensetsize;
 113
 114           while (fp1 < fp3)
 115             *fp2++ = *fp1++;
 116         }
 117     }
 118 }
 119
 120
 121 static void
 122 digraph (short **relation)
 123 {
 124   int i;
 125
 126   infinity = ngotos + 2;
 127   INDEX = XCALLOC (short, ngotos + 1);
 128   VERTICES = XCALLOC (short, ngotos + 1);
 129   top = 0;
 130
 131   R = relation;
 132
 133   for (i = 0; i < ngotos; i++)
 134     INDEX[i] = 0;
 135
 136   for (i = 0; i < ngotos; i++)
 137     {
 138       if (INDEX[i] == 0 && R[i])
 139         traverse (i);
 140     }
 141
 142   XFREE (INDEX);
 143   XFREE (VERTICES);
 144 }
 145
 146 static void
 147 set_state_table (void)
 148 {
 149   state_table = XCALLOC (state_t, nstates);
 150
 151   {
 152     core *sp;
 153     for (sp = first_state; sp; sp = sp->next)
 154       {
 155         state_table[sp->number].state = sp;
 156         state_table[sp->number].accessing_symbol = sp->accessing_symbol;
 157       }
 158   }
 159
 160   {
 161     shifts *sp;
 162     for (sp = first_shift; sp; sp = sp->next)
 163       state_table[sp->number].shift_table = sp;
 164   }
 165
 166   {
 167     reductions *rp;
 168     for (rp = first_reduction; rp; rp = rp->next)
 169       state_table[rp->number].reduction_table = rp;
 170   }
 171 }
 172
 173
 174 static void
 175 set_maxrhs (void)
 176 {
 177   short *itemp;
 178   int length;
 179   int max;
 180
 181   length = 0;
 182   max = 0;
 183   for (itemp = ritem; *itemp; itemp++)
 184     {
 185       if (*itemp > 0)
 186         {
 187           length++;
 188         }
 189       else
 190         {
 191           if (length > max)
 192             max = length;
 193           length = 0;
 194         }
 195     }
 196
 197   maxrhs = max;
 198 }
 199
 200
 201 static void
 202 initialize_LA (void)
 203 {
 204   int i;
 205   int j;
 206   int count;
 207   reductions *rp;
 208   shifts *sp;
 209   short *np;
 210
 211   consistent = XCALLOC (char, nstates);
 212   lookaheads = XCALLOC (short, nstates + 1);
 213
 214   count = 0;
 215   for (i = 0; i < nstates; i++)
 216     {
 217       int k;
 218
 219       lookaheads[i] = count;
 220
 221       rp = state_table[i].reduction_table;
 222       sp = state_table[i].shift_table;
 223       if (rp
 224           && (rp->nreds > 1
 225               || (sp && !ISVAR (state_table[sp->shifts[0]].accessing_symbol))))
 226         count += rp->nreds;
 227       else
 228         consistent[i] = 1;
 229
 230       if (sp)
 231         for (k = 0; k < sp->nshifts; k++)
 232           if (state_table[sp->shifts[k]].accessing_symbol
 233               == error_token_number)
 234             {
 235               consistent[i] = 0;
 236               break;
 237             }
 238     }
 239
 240   lookaheads[nstates] = count;
 241
 242   if (count == 0)
 243     {
 244       LA = XCALLOC (unsigned, 1 * tokensetsize);
 245       LAruleno = XCALLOC (short, 1);
 246       lookback = XCALLOC (shorts *, 1);
 247     }
 248   else
 249     {
 250       LA = XCALLOC (unsigned, count * tokensetsize);
 251       LAruleno = XCALLOC (short, count);
 252       lookback = XCALLOC (shorts *, count);
 253     }
 254
 255   np = LAruleno;
 256   for (i = 0; i < nstates; i++)
 257     {
 258       if (!consistent[i])
 259         {
 260           if ((rp = state_table[i].reduction_table))
 261             for (j = 0; j < rp->nreds; j++)
 262               *np++ = rp->rules[j];
 263         }
 264     }
 265 }
 266
 267
 268 static void
 269 set_goto_map (void)
 270 {
 271   shifts *sp;
 272   int i;
 273   int symbol;
 274   int k;
 275   short *temp_map;
 276   int state2;
 277   int state1;
 278
 279   goto_map = XCALLOC (short, nvars + 1) - ntokens;
 280   temp_map = XCALLOC (short, nvars + 1) - ntokens;
 281
 282   ngotos = 0;
 283   for (sp = first_shift; sp; sp = sp->next)
 284     {
 285       for (i = sp->nshifts - 1; i >= 0; i--)
 286         {
 287           symbol = state_table[sp->shifts[i]].accessing_symbol;
 288
 289           if (ISTOKEN (symbol))
 290             break;
 291
 292           if (ngotos == MAXSHORT)
 293             fatal (_("too many gotos (max %d)"), MAXSHORT);
 294
 295           ngotos++;
 296           goto_map[symbol]++;
 297         }
 298     }
 299
 300   k = 0;
 301   for (i = ntokens; i < nsyms; i++)
 302     {
 303       temp_map[i] = k;
 304       k += goto_map[i];
 305     }
 306
 307   for (i = ntokens; i < nsyms; i++)
 308     goto_map[i] = temp_map[i];
 309
 310   goto_map[nsyms] = ngotos;
 311   temp_map[nsyms] = ngotos;
 312
 313   from_state = XCALLOC (short, ngotos);
 314   to_state = XCALLOC (short, ngotos);
 315
 316   for (sp = first_shift; sp; sp = sp->next)
 317     {
 318       state1 = sp->number;
 319       for (i = sp->nshifts - 1; i >= 0; i--)
 320         {
 321           state2 = sp->shifts[i];
 322           symbol = state_table[state2].accessing_symbol;
 323
 324           if (ISTOKEN (symbol))
 325             break;
 326
 327           k = temp_map[symbol]++;
 328           from_state[k] = state1;
 329           to_state[k] = state2;
 330         }
 331     }
 332
 333   XFREE (temp_map + ntokens);
 334 }
 335
 336
 337
 338 /*----------------------------------------------------------.
 339 | Map a state/symbol pair into its numeric representation.  |
 340 `----------------------------------------------------------*/
 341
 342 static int
 343 map_goto (int state, int symbol)
 344 {
 345   int high;
 346   int low;
 347   int middle;
 348   int s;
 349
 350   low = goto_map[symbol];
 351   high = goto_map[symbol + 1] - 1;
 352
 353   while (low <= high)
 354     {
 355       middle = (low + high) / 2;
 356       s = from_state[middle];
 357       if (s == state)
 358         return middle;
 359       else if (s < state)
 360         low = middle + 1;
 361       else
 362         high = middle - 1;
 363     }
 364
 365   assert (0);
 366   /* NOTREACHED */
 367   return 0;
 368 }
 369
 370
 371 static void
 372 initialize_F (void)
 373 {
 374   int i;
 375   int j;
 376   int k;
 377   shifts *sp;
 378   short *edge;
 379   unsigned *rowp;
 380   short *rp;
 381   short **reads;
 382   int nedges;
 383   int stateno;
 384   int symbol;
 385   int nwords;
 386
 387   nwords = ngotos * tokensetsize;
 388   F = XCALLOC (unsigned, nwords);
 389
 390   reads = XCALLOC (short *, ngotos);
 391   edge = XCALLOC (short, ngotos + 1);
 392   nedges = 0;
 393
 394   rowp = F;
 395   for (i = 0; i < ngotos; i++)
 396     {
 397       stateno = to_state[i];
 398       sp = state_table[stateno].shift_table;
 399
 400       if (sp)
 401         {
 402           k = sp->nshifts;
 403
 404           for (j = 0; j < k; j++)
 405             {
 406               symbol = state_table[sp->shifts[j]].accessing_symbol;
 407               if (ISVAR (symbol))
 408                 break;
 409               SETBIT (rowp, symbol);
 410             }
 411
 412           for (; j < k; j++)
 413             {
 414               symbol = state_table[sp->shifts[j]].accessing_symbol;
 415               if (nullable[symbol])
 416                 edge[nedges++] = map_goto (stateno, symbol);
 417             }
 418
 419           if (nedges)
 420             {
 421               reads[i] = rp = XCALLOC (short, nedges + 1);
 422
 423               for (j = 0; j < nedges; j++)
 424                 rp[j] = edge[j];
 425
 426               rp[nedges] = -1;
 427               nedges = 0;
 428             }
 429         }
 430
 431       rowp += tokensetsize;
 432     }
 433
 434   digraph (reads);
 435
 436   for (i = 0; i < ngotos; i++)
 437     {
 438       if (reads[i])
 439         XFREE (reads[i]);
 440     }
 441
 442   XFREE (reads);
 443   XFREE (edge);
 444 }
 445
 446
 447 static void
 448 add_lookback_edge (int stateno, int ruleno, int gotono)
 449 {
 450   int i;
 451   int k;
 452   int found;
 453   shorts *sp;
 454
 455   i = lookaheads[stateno];
 456   k = lookaheads[stateno + 1];
 457   found = 0;
 458   while (!found && i < k)
 459     {
 460       if (LAruleno[i] == ruleno)
 461         found = 1;
 462       else
 463         i++;
 464     }
 465
 466   assert (found);
 467
 468   sp = XCALLOC (shorts, 1);
 469   sp->next = lookback[i];
 470   sp->value = gotono;
 471   lookback[i] = sp;
 472 }
 473
 474
 475 static short **
 476 transpose (short **R_arg, int n)
 477 {
 478   short **new_R;
 479   short **temp_R;
 480   short *nedges;
 481   short *sp;
 482   int i;
 483   int k;
 484
 485   nedges = XCALLOC (short, n);
 486
 487   for (i = 0; i < n; i++)
 488     {
 489       sp = R_arg[i];
 490       if (sp)
 491         {
 492           while (*sp >= 0)
 493             nedges[*sp++]++;
 494         }
 495     }
 496
 497   new_R = XCALLOC (short *, n);
 498   temp_R = XCALLOC (short *, n);
 499
 500   for (i = 0; i < n; i++)
 501     {
 502       k = nedges[i];
 503       if (k > 0)
 504         {
 505           sp = XCALLOC (short, k + 1);
 506           new_R[i] = sp;
 507           temp_R[i] = sp;
 508           sp[k] = -1;
 509         }
 510     }
 511
 512   XFREE (nedges);
 513
 514   for (i = 0; i < n; i++)
 515     {
 516       sp = R_arg[i];
 517       if (sp)
 518         {
 519           while (*sp >= 0)
 520             *temp_R[*sp++]++ = i;
 521         }
 522     }
 523
 524   XFREE (temp_R);
 525
 526   return new_R;
 527 }
 528
 529
 530 static void
 531 build_relations (void)
 532 {
 533   int i;
 534   int j;
 535   int k;
 536   short *rulep;
 537   short *rp;
 538   shifts *sp;
 539   int length;
 540   int nedges;
 541   int done;
 542   int state1;
 543   int stateno;
 544   int symbol1;
 545   int symbol2;
 546   short *shortp;
 547   short *edge;
 548   short *states;
 549   short **new_includes;
 550
 551   includes = XCALLOC (short *, ngotos);
 552   edge = XCALLOC (short, ngotos + 1);
 553   states = XCALLOC (short, maxrhs + 1);
 554
 555   for (i = 0; i < ngotos; i++)
 556     {
 557       nedges = 0;
 558       state1 = from_state[i];
 559       symbol1 = state_table[to_state[i]].accessing_symbol;
 560
 561       for (rulep = derives[symbol1]; *rulep > 0; rulep++)
 562         {
 563           length = 1;
 564           states[0] = state1;
 565           stateno = state1;
 566
 567           for (rp = ritem + rrhs[*rulep]; *rp > 0; rp++)
 568             {
 569               symbol2 = *rp;
 570               sp = state_table[stateno].shift_table;
 571               k = sp->nshifts;
 572
 573               for (j = 0; j < k; j++)
 574                 {
 575                   stateno = sp->shifts[j];
 576                   if (state_table[stateno].accessing_symbol == symbol2)
 577                     break;
 578                 }
 579
 580               states[length++] = stateno;
 581             }
 582
 583           if (!consistent[stateno])
 584             add_lookback_edge (stateno, *rulep, i);
 585
 586           length--;
 587           done = 0;
 588           while (!done)
 589             {
 590               done = 1;
 591               rp--;
 592               /* JF added rp>=ritem &&   I hope to god its right! */
 593               if (rp >= ritem && ISVAR (*rp))
 594                 {
 595                   stateno = states[--length];
 596                   edge[nedges++] = map_goto (stateno, *rp);
 597                   if (nullable[*rp])
 598                     done = 0;
 599                 }
 600             }
 601         }
 602
 603       if (nedges)
 604         {
 605           includes[i] = shortp = XCALLOC (short, nedges + 1);
 606           for (j = 0; j < nedges; j++)
 607             shortp[j] = edge[j];
 608           shortp[nedges] = -1;
 609         }
 610     }
 611
 612   new_includes = transpose (includes, ngotos);
 613
 614   for (i = 0; i < ngotos; i++)
 615     if (includes[i])
 616       XFREE (includes[i]);
 617
 618   XFREE (includes);
 619
 620   includes = new_includes;
 621
 622   XFREE (edge);
 623   XFREE (states);
 624 }
 625
 626
 627
 628 static void
 629 compute_FOLLOWS (void)
 630 {
 631   int i;
 632
 633   digraph (includes);
 634
 635   for (i = 0; i < ngotos; i++)
 636     {
 637       if (includes[i])
 638         XFREE (includes[i]);
 639     }
 640
 641   XFREE (includes);
 642 }
 643
 644
 645 static void
 646 compute_lookaheads (void)
 647 {
 648   int i;
 649   int n;
 650   unsigned *fp1;
 651   unsigned *fp2;
 652   unsigned *fp3;
 653   shorts *sp;
 654   unsigned *rowp;
 655   shorts *sptmp;                /* JF */
 656
 657   rowp = LA;
 658   n = lookaheads[nstates];
 659   for (i = 0; i < n; i++)
 660     {
 661       fp3 = rowp + tokensetsize;
 662       for (sp = lookback[i]; sp; sp = sp->next)
 663         {
 664           fp1 = rowp;
 665           fp2 = F + tokensetsize * sp->value;
 666           while (fp1 < fp3)
 667             *fp1++ |= *fp2++;
 668         }
 669
 670       rowp = fp3;
 671     }
 672
 673   for (i = 0; i < n; i++)
 674     {
 675       /* JF removed ref to freed storage */
 676       for (sp = lookback[i]; sp; sp = sptmp)
 677         {
 678           sptmp = sp->next;
 679           XFREE (sp);
 680         }
 681     }
 682
 683   XFREE (lookback);
 684   XFREE (F);
 685 }
 686
 687
 688 void
 689 lalr (void)
 690 {
 691   tokensetsize = WORDSIZE (ntokens);
 692
 693   set_state_table ();
 694   set_maxrhs ();
 695   initialize_LA ();
 696   set_goto_map ();
 697   initialize_F ();
 698   build_relations ();
 699   compute_FOLLOWS ();
 700   compute_lookaheads ();
 701 }