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