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 int tokensetsize;
  36 short *lookaheads;
  37 short *LAruleno;
  38 unsigned *LA;
  39 short *accessing_symbol;
  40 char *consistent;
  41 core **state_table;
  42 shifts **shift_table;
  43 reductions **reduction_table;
  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   core *sp;
 148
 149   state_table = XCALLOC (core *, nstates);
 150
 151   for (sp = first_state; sp; sp = sp->next)
 152     state_table[sp->number] = sp;
 153 }
 154
 155
 156 static void
 157 set_accessing_symbol (void)
 158 {
 159   core *sp;
 160
 161   accessing_symbol = XCALLOC (short, nstates);
 162
 163   for (sp = first_state; sp; sp = sp->next)
 164     accessing_symbol[sp->number] = sp->accessing_symbol;
 165 }
 166
 167
 168 static void
 169 set_shift_table (void)
 170 {
 171   shifts *sp;
 172
 173   shift_table = XCALLOC (shifts *, nstates);
 174
 175   for (sp = first_shift; sp; sp = sp->next)
 176     shift_table[sp->number] = sp;
 177 }
 178
 179
 180 static void
 181 set_reduction_table (void)
 182 {
 183   reductions *rp;
 184
 185   reduction_table = XCALLOC (reductions *, nstates);
 186
 187   for (rp = first_reduction; rp; rp = rp->next)
 188     reduction_table[rp->number] = rp;
 189 }
 190
 191
 192 static void
 193 set_maxrhs (void)
 194 {
 195   short *itemp;
 196   int length;
 197   int max;
 198
 199   length = 0;
 200   max = 0;
 201   for (itemp = ritem; *itemp; itemp++)
 202     {
 203       if (*itemp > 0)
 204         {
 205           length++;
 206         }
 207       else
 208         {
 209           if (length > max)
 210             max = length;
 211           length = 0;
 212         }
 213     }
 214
 215   maxrhs = max;
 216 }
 217
 218
 219 static void
 220 initialize_LA (void)
 221 {
 222   int i;
 223   int j;
 224   int count;
 225   reductions *rp;
 226   shifts *sp;
 227   short *np;
 228
 229   consistent = XCALLOC (char, nstates);
 230   lookaheads = XCALLOC (short, nstates + 1);
 231
 232   count = 0;
 233   for (i = 0; i < nstates; i++)
 234     {
 235       int k;
 236
 237       lookaheads[i] = count;
 238
 239       rp = reduction_table[i];
 240       sp = shift_table[i];
 241       if (rp && (rp->nreds > 1
 242                  || (sp && !ISVAR (accessing_symbol[sp->shifts[0]]))))
 243         count += rp->nreds;
 244       else
 245         consistent[i] = 1;
 246
 247       if (sp)
 248         for (k = 0; k < sp->nshifts; k++)
 249           {
 250             if (accessing_symbol[sp->shifts[k]] == error_token_number)
 251               {
 252                 consistent[i] = 0;
 253                 break;
 254               }
 255           }
 256     }
 257
 258   lookaheads[nstates] = count;
 259
 260   if (count == 0)
 261     {
 262       LA = XCALLOC (unsigned, 1 * tokensetsize);
 263       LAruleno = XCALLOC (short, 1);
 264       lookback = XCALLOC (shorts *, 1);
 265     }
 266   else
 267     {
 268       LA = XCALLOC (unsigned, count * tokensetsize);
 269       LAruleno = XCALLOC (short, count);
 270       lookback = XCALLOC (shorts *, count);
 271     }
 272
 273   np = LAruleno;
 274   for (i = 0; i < nstates; i++)
 275     {
 276       if (!consistent[i])
 277         {
 278           if ((rp = reduction_table[i]))
 279             for (j = 0; j < rp->nreds; j++)
 280               *np++ = rp->rules[j];
 281         }
 282     }
 283 }
 284
 285
 286 static void
 287 set_goto_map (void)
 288 {
 289   shifts *sp;
 290   int i;
 291   int symbol;
 292   int k;
 293   short *temp_map;
 294   int state2;
 295   int state1;
 296
 297   goto_map = XCALLOC (short, nvars + 1) - ntokens;
 298   temp_map = XCALLOC (short, nvars + 1) - ntokens;
 299
 300   ngotos = 0;
 301   for (sp = first_shift; sp; sp = sp->next)
 302     {
 303       for (i = sp->nshifts - 1; i >= 0; i--)
 304         {
 305           symbol = accessing_symbol[sp->shifts[i]];
 306
 307           if (ISTOKEN (symbol))
 308             break;
 309
 310           if (ngotos == MAXSHORT)
 311             fatal (_("too many gotos (max %d)"), MAXSHORT);
 312
 313           ngotos++;
 314           goto_map[symbol]++;
 315         }
 316     }
 317
 318   k = 0;
 319   for (i = ntokens; i < nsyms; i++)
 320     {
 321       temp_map[i] = k;
 322       k += goto_map[i];
 323     }
 324
 325   for (i = ntokens; i < nsyms; i++)
 326     goto_map[i] = temp_map[i];
 327
 328   goto_map[nsyms] = ngotos;
 329   temp_map[nsyms] = ngotos;
 330
 331   from_state = XCALLOC (short, ngotos);
 332   to_state = XCALLOC (short, ngotos);
 333
 334   for (sp = first_shift; sp; sp = sp->next)
 335     {
 336       state1 = sp->number;
 337       for (i = sp->nshifts - 1; i >= 0; i--)
 338         {
 339           state2 = sp->shifts[i];
 340           symbol = accessing_symbol[state2];
 341
 342           if (ISTOKEN (symbol))
 343             break;
 344
 345           k = temp_map[symbol]++;
 346           from_state[k] = state1;
 347           to_state[k] = state2;
 348         }
 349     }
 350
 351   XFREE (temp_map + ntokens);
 352 }
 353
 354
 355
 356 /*----------------------------------------------------------.
 357 | Map a state/symbol pair into its numeric representation.  |
 358 `----------------------------------------------------------*/
 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   assert (0);
 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 = XCALLOC (unsigned, nwords);
 407
 408   reads = XCALLOC (short *, ngotos);
 409   edge = XCALLOC (short, ngotos + 1);
 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 = XCALLOC (short, nedges + 1);
 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         XFREE (reads[i]);
 458     }
 459
 460   XFREE (reads);
 461   XFREE (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   assert (found);
 485
 486   sp = XCALLOC (shorts, 1);
 487   sp->next = lookback[i];
 488   sp->value = gotono;
 489   lookback[i] = sp;
 490 }
 491
 492
 493 static short **
 494 transpose (short **R_arg, int n)
 495 {
 496   short **new_R;
 497   short **temp_R;
 498   short *nedges;
 499   short *sp;
 500   int i;
 501   int k;
 502
 503   nedges = XCALLOC (short, n);
 504
 505   for (i = 0; i < n; i++)
 506     {
 507       sp = R_arg[i];
 508       if (sp)
 509         {
 510           while (*sp >= 0)
 511             nedges[*sp++]++;
 512         }
 513     }
 514
 515   new_R = XCALLOC (short *, n);
 516   temp_R = XCALLOC (short *, n);
 517
 518   for (i = 0; i < n; i++)
 519     {
 520       k = nedges[i];
 521       if (k > 0)
 522         {
 523           sp = XCALLOC (short, k + 1);
 524           new_R[i] = sp;
 525           temp_R[i] = sp;
 526           sp[k] = -1;
 527         }
 528     }
 529
 530   XFREE (nedges);
 531
 532   for (i = 0; i < n; i++)
 533     {
 534       sp = R_arg[i];
 535       if (sp)
 536         {
 537           while (*sp >= 0)
 538             *temp_R[*sp++]++ = i;
 539         }
 540     }
 541
 542   XFREE (temp_R);
 543
 544   return new_R;
 545 }
 546
 547
 548 static void
 549 build_relations (void)
 550 {
 551   int i;
 552   int j;
 553   int k;
 554   short *rulep;
 555   short *rp;
 556   shifts *sp;
 557   int length;
 558   int nedges;
 559   int done;
 560   int state1;
 561   int stateno;
 562   int symbol1;
 563   int symbol2;
 564   short *shortp;
 565   short *edge;
 566   short *states;
 567   short **new_includes;
 568
 569   includes = XCALLOC (short *, ngotos);
 570   edge = XCALLOC (short, ngotos + 1);
 571   states = XCALLOC (short, maxrhs + 1);
 572
 573   for (i = 0; i < ngotos; i++)
 574     {
 575       nedges = 0;
 576       state1 = from_state[i];
 577       symbol1 = accessing_symbol[to_state[i]];
 578
 579       for (rulep = derives[symbol1]; *rulep > 0; rulep++)
 580         {
 581           length = 1;
 582           states[0] = state1;
 583           stateno = state1;
 584
 585           for (rp = ritem + rrhs[*rulep]; *rp > 0; rp++)
 586             {
 587               symbol2 = *rp;
 588               sp = shift_table[stateno];
 589               k = sp->nshifts;
 590
 591               for (j = 0; j < k; j++)
 592                 {
 593                   stateno = sp->shifts[j];
 594                   if (accessing_symbol[stateno] == symbol2)
 595                     break;
 596                 }
 597
 598               states[length++] = stateno;
 599             }
 600
 601           if (!consistent[stateno])
 602             add_lookback_edge (stateno, *rulep, i);
 603
 604           length--;
 605           done = 0;
 606           while (!done)
 607             {
 608               done = 1;
 609               rp--;
 610               /* JF added rp>=ritem &&   I hope to god its right! */
 611               if (rp >= ritem && ISVAR (*rp))
 612                 {
 613                   stateno = states[--length];
 614                   edge[nedges++] = map_goto (stateno, *rp);
 615                   if (nullable[*rp])
 616                     done = 0;
 617                 }
 618             }
 619         }
 620
 621       if (nedges)
 622         {
 623           includes[i] = shortp = XCALLOC (short, nedges + 1);
 624           for (j = 0; j < nedges; j++)
 625             shortp[j] = edge[j];
 626           shortp[nedges] = -1;
 627         }
 628     }
 629
 630   new_includes = transpose (includes, ngotos);
 631
 632   for (i = 0; i < ngotos; i++)
 633     if (includes[i])
 634       XFREE (includes[i]);
 635
 636   XFREE (includes);
 637
 638   includes = new_includes;
 639
 640   XFREE (edge);
 641   XFREE (states);
 642 }
 643
 644
 645
 646 static void
 647 compute_FOLLOWS (void)
 648 {
 649   int i;
 650
 651   digraph (includes);
 652
 653   for (i = 0; i < ngotos; i++)
 654     {
 655       if (includes[i])
 656         XFREE (includes[i]);
 657     }
 658
 659   XFREE (includes);
 660 }
 661
 662
 663 static void
 664 compute_lookaheads (void)
 665 {
 666   int i;
 667   int n;
 668   unsigned *fp1;
 669   unsigned *fp2;
 670   unsigned *fp3;
 671   shorts *sp;
 672   unsigned *rowp;
 673   shorts *sptmp;                /* JF */
 674
 675   rowp = LA;
 676   n = lookaheads[nstates];
 677   for (i = 0; i < n; i++)
 678     {
 679       fp3 = rowp + tokensetsize;
 680       for (sp = lookback[i]; sp; sp = sp->next)
 681         {
 682           fp1 = rowp;
 683           fp2 = F + tokensetsize * sp->value;
 684           while (fp1 < fp3)
 685             *fp1++ |= *fp2++;
 686         }
 687
 688       rowp = fp3;
 689     }
 690
 691   for (i = 0; i < n; i++)
 692     {
 693       /* JF removed ref to freed storage */
 694       for (sp = lookback[i]; sp; sp = sptmp)
 695         {
 696           sptmp = sp->next;
 697           XFREE (sp);
 698         }
 699     }
 700
 701   XFREE (lookback);
 702   XFREE (F);
 703 }
 704
 705
 706 void
 707 lalr (void)
 708 {
 709   tokensetsize = WORDSIZE (ntokens);
 710
 711   set_state_table ();
 712   set_accessing_symbol ();
 713   set_shift_table ();
 714   set_reduction_table ();
 715   set_maxrhs ();
 716   initialize_LA ();
 717   set_goto_map ();
 718   initialize_F ();
 719   build_relations ();
 720   compute_FOLLOWS ();
 721   compute_lookaheads ();
 722 }