src/lalr.c

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