src/lalr.c

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