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 #include "nullable.h"
  34
  35 extern short **derives;
  36
  37 int tokensetsize;
  38 short *lookaheads;
  39 short *LAruleno;
  40 unsigned *LA;
  41 short *accessing_symbol;
  42 char *consistent;
  43 core **state_table;
  44 shifts **shift_table;
  45 reductions **reduction_table;
  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 = NEW2 (ngotos + 1, short);
 128   VERTICES = NEW2 (ngotos + 1, short);
 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   FREE (INDEX);
 143   FREE (VERTICES);
 144 }
 145
 146 static void
 147 set_state_table (void)
 148 {
 149   core *sp;
 150
 151   state_table = NEW2 (nstates, core *);
 152
 153   for (sp = first_state; sp; sp = sp->next)
 154     state_table[sp->number] = sp;
 155 }
 156
 157
 158 static void
 159 set_accessing_symbol (void)
 160 {
 161   core *sp;
 162
 163   accessing_symbol = NEW2 (nstates, short);
 164
 165   for (sp = first_state; sp; sp = sp->next)
 166     accessing_symbol[sp->number] = sp->accessing_symbol;
 167 }
 168
 169
 170 static void
 171 set_shift_table (void)
 172 {
 173   shifts *sp;
 174
 175   shift_table = NEW2 (nstates, shifts *);
 176
 177   for (sp = first_shift; sp; sp = sp->next)
 178     shift_table[sp->number] = sp;
 179 }
 180
 181
 182 static void
 183 set_reduction_table (void)
 184 {
 185   reductions *rp;
 186
 187   reduction_table = NEW2 (nstates, reductions *);
 188
 189   for (rp = first_reduction; rp; rp = rp->next)
 190     reduction_table[rp->number] = rp;
 191 }
 192
 193
 194 static void
 195 set_maxrhs (void)
 196 {
 197   short *itemp;
 198   int length;
 199   int max;
 200
 201   length = 0;
 202   max = 0;
 203   for (itemp = ritem; *itemp; itemp++)
 204     {
 205       if (*itemp > 0)
 206         {
 207           length++;
 208         }
 209       else
 210         {
 211           if (length > max)
 212             max = length;
 213           length = 0;
 214         }
 215     }
 216
 217   maxrhs = max;
 218 }
 219
 220
 221 static void
 222 initialize_LA (void)
 223 {
 224   int i;
 225   int j;
 226   int count;
 227   reductions *rp;
 228   shifts *sp;
 229   short *np;
 230
 231   consistent = NEW2 (nstates, char);
 232   lookaheads = NEW2 (nstates + 1, short);
 233
 234   count = 0;
 235   for (i = 0; i < nstates; i++)
 236     {
 237       int k;
 238
 239       lookaheads[i] = count;
 240
 241       rp = reduction_table[i];
 242       sp = shift_table[i];
 243       if (rp && (rp->nreds > 1
 244                  || (sp && !ISVAR (accessing_symbol[sp->shifts[0]]))))
 245         count += rp->nreds;
 246       else
 247         consistent[i] = 1;
 248
 249       if (sp)
 250         for (k = 0; k < sp->nshifts; k++)
 251           {
 252             if (accessing_symbol[sp->shifts[k]] == error_token_number)
 253               {
 254                 consistent[i] = 0;
 255                 break;
 256               }
 257           }
 258     }
 259
 260   lookaheads[nstates] = count;
 261
 262   if (count == 0)
 263     {
 264       LA = NEW2 (1 * tokensetsize, unsigned);
 265       LAruleno = NEW2 (1, short);
 266       lookback = NEW2 (1, shorts *);
 267     }
 268   else
 269     {
 270       LA = NEW2 (count * tokensetsize, unsigned);
 271       LAruleno = NEW2 (count, short);
 272       lookback = NEW2 (count, shorts *);
 273     }
 274
 275   np = LAruleno;
 276   for (i = 0; i < nstates; i++)
 277     {
 278       if (!consistent[i])
 279         {
 280           if ((rp = reduction_table[i]))
 281             for (j = 0; j < rp->nreds; j++)
 282               *np++ = rp->rules[j];
 283         }
 284     }
 285 }
 286
 287
 288 static void
 289 set_goto_map (void)
 290 {
 291   shifts *sp;
 292   int i;
 293   int symbol;
 294   int k;
 295   short *temp_map;
 296   int state2;
 297   int state1;
 298
 299   goto_map = NEW2 (nvars + 1, short) - ntokens;
 300   temp_map = NEW2 (nvars + 1, short) - ntokens;
 301
 302   ngotos = 0;
 303   for (sp = first_shift; sp; sp = sp->next)
 304     {
 305       for (i = sp->nshifts - 1; i >= 0; i--)
 306         {
 307           symbol = accessing_symbol[sp->shifts[i]];
 308
 309           if (ISTOKEN (symbol))
 310             break;
 311
 312           if (ngotos == MAXSHORT)
 313             fatal (_("too many gotos (max %d)"), MAXSHORT);
 314
 315           ngotos++;
 316           goto_map[symbol]++;
 317         }
 318     }
 319
 320   k = 0;
 321   for (i = ntokens; i < nsyms; i++)
 322     {
 323       temp_map[i] = k;
 324       k += goto_map[i];
 325     }
 326
 327   for (i = ntokens; i < nsyms; i++)
 328     goto_map[i] = temp_map[i];
 329
 330   goto_map[nsyms] = ngotos;
 331   temp_map[nsyms] = ngotos;
 332
 333   from_state = NEW2 (ngotos, short);
 334   to_state = NEW2 (ngotos, short);
 335
 336   for (sp = first_shift; sp; sp = sp->next)
 337     {
 338       state1 = sp->number;
 339       for (i = sp->nshifts - 1; i >= 0; i--)
 340         {
 341           state2 = sp->shifts[i];
 342           symbol = accessing_symbol[state2];
 343
 344           if (ISTOKEN (symbol))
 345             break;
 346
 347           k = temp_map[symbol]++;
 348           from_state[k] = state1;
 349           to_state[k] = state2;
 350         }
 351     }
 352
 353   FREE (temp_map + ntokens);
 354 }
 355
 356
 357
 358 /*  Map_goto maps a state/symbol pair into its numeric representation.  */
 359
 360 static int
 361 map_goto (int state, int symbol)
 362 {
 363   int high;
 364   int low;
 365   int middle;
 366   int s;
 367
 368   low = goto_map[symbol];
 369   high = goto_map[symbol + 1] - 1;
 370
 371   while (low <= high)
 372     {
 373       middle = (low + high) / 2;
 374       s = from_state[middle];
 375       if (s == state)
 376         return middle;
 377       else if (s < state)
 378         low = middle + 1;
 379       else
 380         high = middle - 1;
 381     }
 382
 383   berror ("map_goto");
 384 /* NOTREACHED */
 385   return 0;
 386 }
 387
 388
 389 static void
 390 initialize_F (void)
 391 {
 392   int i;
 393   int j;
 394   int k;
 395   shifts *sp;
 396   short *edge;
 397   unsigned *rowp;
 398   short *rp;
 399   short **reads;
 400   int nedges;
 401   int stateno;
 402   int symbol;
 403   int nwords;
 404
 405   nwords = ngotos * tokensetsize;
 406   F = NEW2 (nwords, unsigned);
 407
 408   reads = NEW2 (ngotos, short *);
 409   edge = NEW2 (ngotos + 1, short);
 410   nedges = 0;
 411
 412   rowp = F;
 413   for (i = 0; i < ngotos; i++)
 414     {
 415       stateno = to_state[i];
 416       sp = shift_table[stateno];
 417
 418       if (sp)
 419         {
 420           k = sp->nshifts;
 421
 422           for (j = 0; j < k; j++)
 423             {
 424               symbol = accessing_symbol[sp->shifts[j]];
 425               if (ISVAR (symbol))
 426                 break;
 427               SETBIT (rowp, symbol);
 428             }
 429
 430           for (; j < k; j++)
 431             {
 432               symbol = accessing_symbol[sp->shifts[j]];
 433               if (nullable[symbol])
 434                 edge[nedges++] = map_goto (stateno, symbol);
 435             }
 436
 437           if (nedges)
 438             {
 439               reads[i] = rp = NEW2 (nedges + 1, short);
 440
 441               for (j = 0; j < nedges; j++)
 442                 rp[j] = edge[j];
 443
 444               rp[nedges] = -1;
 445               nedges = 0;
 446             }
 447         }
 448
 449       rowp += tokensetsize;
 450     }
 451
 452   digraph (reads);
 453
 454   for (i = 0; i < ngotos; i++)
 455     {
 456       if (reads[i])
 457         FREE (reads[i]);
 458     }
 459
 460   FREE (reads);
 461   FREE (edge);
 462 }
 463
 464
 465 static void
 466 add_lookback_edge (int stateno, int ruleno, int gotono)
 467 {
 468   int i;
 469   int k;
 470   int found;
 471   shorts *sp;
 472
 473   i = lookaheads[stateno];
 474   k = lookaheads[stateno + 1];
 475   found = 0;
 476   while (!found && i < k)
 477     {
 478       if (LAruleno[i] == ruleno)
 479         found = 1;
 480       else
 481         i++;
 482     }
 483
 484   if (found == 0)
 485     berror ("add_lookback_edge");
 486
 487   sp = NEW (shorts);
 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 = NEW2 (n, short);
 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 = NEW2 (n, short *);
 517   temp_R = NEW2 (n, short *);
 518
 519   for (i = 0; i < n; i++)
 520     {
 521       k = nedges[i];
 522       if (k > 0)
 523         {
 524           sp = NEW2 (k + 1, short);
 525           new_R[i] = sp;
 526           temp_R[i] = sp;
 527           sp[k] = -1;
 528         }
 529     }
 530
 531   FREE (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   FREE (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 = NEW2 (ngotos, short *);
 571   edge = NEW2 (ngotos + 1, short);
 572   states = NEW2 (maxrhs + 1, short);
 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 = NEW2 (nedges + 1, short);
 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       FREE (includes[i]);
 636
 637   FREE (includes);
 638
 639   includes = new_includes;
 640
 641   FREE (edge);
 642   FREE (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         FREE (includes[i]);
 658     }
 659
 660   FREE (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           FREE (sp);
 699         }
 700     }
 701
 702   FREE (lookback);
 703   FREE (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 }