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