src/closure.c

   1 /* Subroutines for bison
   2    Copyright (C) 1984, 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 it
   7    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, but
  12    WITHOUT ANY WARRANTY; without even the implied warranty of
  13    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  14    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 the Free
  18    Software Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA
  19    02111-1307, USA.  */
  20
  21
  22 /* Subroutines of file LR0.c.
  23
  24 Entry points:
  25
  26   closure (items, n)
  27
  28 Given a vector of item numbers items, of length n, set up ruleset and
  29 itemset to indicate what rules could be run and which items could be
  30 accepted when those items are the active ones.
  31
  32 ruleset contains a bit for each rule.  closure sets the bits for all
  33 rules which could potentially describe the next input to be read.
  34
  35 itemset is a vector of item numbers; itemsetend points to just beyond
  36 the end of the part of it that is significant.  closure places there
  37 the indices of all items which represent units of input that could
  38 arrive next.
  39
  40   initialize_closure (n)
  41
  42 Allocates the itemset and ruleset vectors, and precomputes useful data
  43 so that closure can be called.  n is the number of elements to
  44 allocate for itemset.
  45
  46   finalize_closure ()
  47
  48 Frees itemset, ruleset and internal data.
  49
  50 */
  51
  52 #include "system.h"
  53 #include "alloc.h"
  54 #include "gram.h"
  55
  56
  57 extern short **derives;
  58 extern char **tags;
  59
  60 extern void initialize_closure PARAMS((int));
  61 extern void closure PARAMS((short *, int));
  62 extern void finalize_closure PARAMS((void));
  63
  64 static void set_fderives PARAMS((void));
  65 static void set_firsts PARAMS((void));
  66
  67 extern void RTC PARAMS((unsigned *, int));
  68
  69 short *itemset;
  70 short *itemsetend;
  71 static unsigned *ruleset;
  72
  73 /* internal data.  See comments before set_fderives and set_firsts.  */
  74 static unsigned *fderives;
  75 static unsigned *firsts;
  76
  77 /* number of words required to hold a bit for each rule */
  78 static int rulesetsize;
  79
  80 /* number of words required to hold a bit for each variable */
  81 static int varsetsize;
  82
  83 #ifdef DEBUG
  84 static void print_closure PARAMS((int));
  85 static void print_fderives PARAMS((void));
  86 static void print_firsts PARAMS((void));
  87 #endif
  88
  89 void
  90 initialize_closure (int n)
  91 {
  92   itemset = NEW2(n, short);
  93
  94   rulesetsize = WORDSIZE(nrules + 1);
  95   ruleset = NEW2(rulesetsize, unsigned);
  96
  97   set_fderives();
  98 }
  99
 100
 101
 102 /* set fderives to an nvars by nrules matrix of bits
 103    indicating which rules can help derive the beginning of the data
 104    for each nonterminal.  For example, if symbol 5 can be derived as
 105    the sequence of symbols 8 3 20, and one of the rules for deriving
 106    symbol 8 is rule 4, then the [5 - ntokens, 4] bit in fderives is set.  */
 107 static void
 108 set_fderives (void)
 109 {
 110   register unsigned *rrow;
 111   register unsigned *vrow;
 112   register int j;
 113   register unsigned cword;
 114   register short *rp;
 115   register int b;
 116
 117   int ruleno;
 118   int i;
 119
 120   fderives = NEW2(nvars * rulesetsize, unsigned) - ntokens * rulesetsize;
 121
 122   set_firsts();
 123
 124   rrow = fderives + ntokens * rulesetsize;
 125
 126   for (i = ntokens; i < nsyms; i++)
 127     {
 128       vrow = firsts + ((i - ntokens) * varsetsize);
 129       cword = *vrow++;
 130       b = 0;
 131       for (j = ntokens; j < nsyms; j++)
 132         {
 133           if (cword & (1 << b))
 134             {
 135               rp = derives[j];
 136               while ((ruleno = *rp++) > 0)
 137                 {
 138                   SETBIT(rrow, ruleno);
 139                 }
 140             }
 141
 142           b++;
 143           if (b >= BITS_PER_WORD && j + 1 < nsyms)
 144             {
 145               cword = *vrow++;
 146               b = 0;
 147             }
 148         }
 149
 150       rrow += rulesetsize;
 151     }
 152
 153 #ifdef  DEBUG
 154   print_fderives();
 155 #endif
 156
 157   FREE(firsts);
 158 }
 159
 160
 161
 162 /* set firsts to be an nvars by nvars bit matrix indicating which
 163    items can represent the beginning of the input corresponding to
 164    which other items.
 165
 166    For example, if some rule expands symbol 5 into the sequence of
 167    symbols 8 3 20, the symbol 8 can be the beginning of the data for
 168    symbol 5, so the bit [8 - ntokens, 5 - ntokens] in firsts is
 169    set. */
 170
 171 static void
 172 set_firsts (void)
 173 {
 174   register unsigned *row;
 175 /*   register int done; JF unused */
 176   register int symbol;
 177   register short *sp;
 178   register int rowsize;
 179
 180   int i;
 181
 182   varsetsize = rowsize = WORDSIZE(nvars);
 183
 184   firsts = NEW2(nvars * rowsize, unsigned);
 185
 186   row = firsts;
 187   for (i = ntokens; i < nsyms; i++)
 188     {
 189       sp = derives[i];
 190       while (*sp >= 0)
 191         {
 192           symbol = ritem[rrhs[*sp++]];
 193           if (ISVAR(symbol))
 194             {
 195               symbol -= ntokens;
 196               SETBIT(row, symbol);
 197             }
 198         }
 199
 200       row += rowsize;
 201     }
 202
 203   RTC(firsts, nvars);
 204
 205 #ifdef  DEBUG
 206   print_firsts ();
 207 #endif
 208 }
 209
 210
 211 void
 212 closure (short *core, int n)
 213 {
 214   register int ruleno;
 215   register unsigned word;
 216   register short *csp;
 217   register unsigned *dsp;
 218   register unsigned *rsp;
 219
 220   short *csend;
 221   unsigned *rsend;
 222   int symbol;
 223   int itemno;
 224
 225   rsp = ruleset;
 226   rsend = ruleset + rulesetsize;
 227   csend = core + n;
 228
 229   if (n == 0)
 230     {
 231       dsp = fderives + start_symbol * rulesetsize;
 232       while (rsp < rsend)
 233         *rsp++ = *dsp++;
 234     }
 235   else
 236     {
 237       while (rsp < rsend)
 238         *rsp++ = 0;
 239
 240       csp = core;
 241       while (csp < csend)
 242         {
 243           symbol = ritem[*csp++];
 244           if (ISVAR(symbol))
 245             {
 246               dsp = fderives + symbol * rulesetsize;
 247               rsp = ruleset;
 248               while (rsp < rsend)
 249                 *rsp++ |= *dsp++;
 250             }
 251         }
 252     }
 253
 254   ruleno = 0;
 255   itemsetend = itemset;
 256   csp = core;
 257   rsp = ruleset;
 258   while (rsp < rsend)
 259     {
 260       word = *rsp++;
 261       if (word == 0)
 262         {
 263           ruleno += BITS_PER_WORD;
 264         }
 265       else
 266         {
 267           register int b;
 268
 269           for (b = 0; b < BITS_PER_WORD; b++)
 270             {
 271               if (word & (1 << b))
 272                 {
 273                   itemno = rrhs[ruleno];
 274                   while (csp < csend && *csp < itemno)
 275                     *itemsetend++ = *csp++;
 276                   *itemsetend++ = itemno;
 277                 }
 278
 279               ruleno++;
 280             }
 281         }
 282     }
 283
 284   while (csp < csend)
 285     *itemsetend++ = *csp++;
 286
 287 #ifdef  DEBUG
 288   print_closure(n);
 289 #endif
 290 }
 291
 292
 293 void
 294 finalize_closure (void)
 295 {
 296   FREE(itemset);
 297   FREE(ruleset);
 298   FREE(fderives + ntokens * rulesetsize);
 299 }
 300
 301
 302
 303 #ifdef  DEBUG
 304
 305 static void
 306 print_closure(int n)
 307 {
 308   register short *isp;
 309
 310   printf ("\n\nn = %d\n\n", n);
 311   for (isp = itemset; isp < itemsetend; isp++)
 312     printf ("   %d\n", *isp);
 313 }
 314
 315
 316 static void
 317 print_firsts (void)
 318 {
 319   register int i;
 320   register int j;
 321   register unsigned *rowp;
 322
 323   printf ("\n\n\nFIRSTS\n\n");
 324
 325   for (i = ntokens; i < nsyms; i++)
 326     {
 327       printf ("\n\n%s firsts\n\n", tags[i]);
 328
 329       rowp = firsts + ((i - ntokens) * varsetsize);
 330
 331       for (j = 0; j < nvars; j++)
 332         if (BITISSET (rowp, j))
 333           printf ("   %s\n", tags[j + ntokens]);
 334     }
 335 }
 336
 337
 338 static void
 339 print_fderives (void)
 340 {
 341   register int i;
 342   register int j;
 343   register unsigned *rp;
 344
 345   printf ("\n\n\nFDERIVES\n");
 346
 347   for (i = ntokens; i < nsyms; i++)
 348     {
 349       printf ("\n\n%s derives\n\n", tags[i]);
 350       rp = fderives + i * rulesetsize;
 351
 352       for (j = 0; j <= nrules; j++)
 353         if (BITISSET (rp, j))
 354           printf ("   %d\n", j);
 355     }
 356
 357   fflush(stdout);
 358 }
 359
 360 #endif