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