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 <stdio.h>
  53 #include "system.h"
  54 #include "machine.h"
  55 #include "alloc.h"
  56 #include "gram.h"
  57
  58
  59 extern short **derives;
  60 extern char **tags;
  61
  62 void initialize_closure PARAMS((int));
  63 void set_fderives PARAMS((void));
  64 void set_firsts PARAMS((void));
  65 void closure PARAMS((short *, int));
  66 void finalize_closure PARAMS((void));
  67
  68 extern void RTC PARAMS((unsigned *, int));
  69
  70 short *itemset;
  71 short *itemsetend;
  72 static unsigned *ruleset;
  73
  74 /* internal data.  See comments before set_fderives and set_firsts.  */
  75 static unsigned *fderives;
  76 static unsigned *firsts;
  77
  78 /* number of words required to hold a bit for each rule */
  79 static int rulesetsize;
  80
  81 /* number of words required to hold a bit for each variable */
  82 static int varsetsize;
  83
  84
  85 void
  86 initialize_closure (int n)
  87 {
  88   itemset = NEW2(n, short);
  89
  90   rulesetsize = WORDSIZE(nrules + 1);
  91   ruleset = NEW2(rulesetsize, unsigned);
  92
  93   set_fderives();
  94 }
  95
  96
  97
  98 /* set fderives to an nvars by nrules matrix of bits
  99    indicating which rules can help derive the beginning of the data
 100    for each nonterminal.  For example, if symbol 5 can be derived as
 101    the sequence of symbols 8 3 20, and one of the rules for deriving
 102    symbol 8 is rule 4, then the [5 - ntokens, 4] bit in fderives is set.  */
 103 void
 104 set_fderives (void)
 105 {
 106   register unsigned *rrow;
 107   register unsigned *vrow;
 108   register int j;
 109   register unsigned cword;
 110   register short *rp;
 111   register int b;
 112
 113   int ruleno;
 114   int i;
 115
 116   fderives = NEW2(nvars * rulesetsize, unsigned) - ntokens * rulesetsize;
 117
 118   set_firsts();
 119
 120   rrow = fderives + ntokens * rulesetsize;
 121
 122   for (i = ntokens; i < nsyms; i++)
 123     {
 124       vrow = firsts + ((i - ntokens) * varsetsize);
 125       cword = *vrow++;
 126       b = 0;
 127       for (j = ntokens; j < nsyms; j++)
 128         {
 129           if (cword & (1 << b))
 130             {
 131               rp = derives[j];
 132               while ((ruleno = *rp++) > 0)
 133                 {
 134                   SETBIT(rrow, ruleno);
 135                 }
 136             }
 137
 138           b++;
 139           if (b >= BITS_PER_WORD && j + 1 < nsyms)
 140             {
 141               cword = *vrow++;
 142               b = 0;
 143             }
 144         }
 145
 146       rrow += rulesetsize;
 147     }
 148
 149 #ifdef  DEBUG
 150   print_fderives();
 151 #endif
 152
 153   FREE(firsts);
 154 }
 155
 156
 157
 158 /* set firsts to be an nvars by nvars bit matrix indicating which
 159    items can represent the beginning of the input corresponding to
 160    which other items.
 161
 162    For example, if some rule expands symbol 5 into the sequence of
 163    symbols 8 3 20, the symbol 8 can be the beginning of the data for
 164    symbol 5, so the bit [8 - ntokens, 5 - ntokens] in firsts is
 165    set. */
 166
 167 void
 168 set_firsts (void)
 169 {
 170   register unsigned *row;
 171 /*   register int done; JF unused */
 172   register int symbol;
 173   register short *sp;
 174   register int rowsize;
 175
 176   int i;
 177
 178   varsetsize = rowsize = WORDSIZE(nvars);
 179
 180   firsts = NEW2(nvars * rowsize, unsigned);
 181
 182   row = firsts;
 183   for (i = ntokens; i < nsyms; i++)
 184     {
 185       sp = derives[i];
 186       while (*sp >= 0)
 187         {
 188           symbol = ritem[rrhs[*sp++]];
 189           if (ISVAR(symbol))
 190             {
 191               symbol -= ntokens;
 192               SETBIT(row, symbol);
 193             }
 194         }
 195
 196       row += rowsize;
 197     }
 198
 199   RTC(firsts, nvars);
 200
 201 #ifdef  DEBUG
 202   print_firsts ();
 203 #endif
 204 }
 205
 206
 207 void
 208 closure (short *core, int n)
 209 {
 210   register int ruleno;
 211   register unsigned word;
 212   register short *csp;
 213   register unsigned *dsp;
 214   register unsigned *rsp;
 215
 216   short *csend;
 217   unsigned *rsend;
 218   int symbol;
 219   int itemno;
 220
 221   rsp = ruleset;
 222   rsend = ruleset + rulesetsize;
 223   csend = core + n;
 224
 225   if (n == 0)
 226     {
 227       dsp = fderives + start_symbol * rulesetsize;
 228       while (rsp < rsend)
 229         *rsp++ = *dsp++;
 230     }
 231   else
 232     {
 233       while (rsp < rsend)
 234         *rsp++ = 0;
 235
 236       csp = core;
 237       while (csp < csend)
 238         {
 239           symbol = ritem[*csp++];
 240           if (ISVAR(symbol))
 241             {
 242               dsp = fderives + symbol * rulesetsize;
 243               rsp = ruleset;
 244               while (rsp < rsend)
 245                 *rsp++ |= *dsp++;
 246             }
 247         }
 248     }
 249
 250   ruleno = 0;
 251   itemsetend = itemset;
 252   csp = core;
 253   rsp = ruleset;
 254   while (rsp < rsend)
 255     {
 256       word = *rsp++;
 257       if (word == 0)
 258         {
 259           ruleno += BITS_PER_WORD;
 260         }
 261       else
 262         {
 263           register int b;
 264
 265           for (b = 0; b < BITS_PER_WORD; b++)
 266             {
 267               if (word & (1 << b))
 268                 {
 269                   itemno = rrhs[ruleno];
 270                   while (csp < csend && *csp < itemno)
 271                     *itemsetend++ = *csp++;
 272                   *itemsetend++ = itemno;
 273                 }
 274
 275               ruleno++;
 276             }
 277         }
 278     }
 279
 280   while (csp < csend)
 281     *itemsetend++ = *csp++;
 282
 283 #ifdef  DEBUG
 284   print_closure(n);
 285 #endif
 286 }
 287
 288
 289 void
 290 finalize_closure (void)
 291 {
 292   FREE(itemset);
 293   FREE(ruleset);
 294   FREE(fderives + ntokens * rulesetsize);
 295 }
 296
 297
 298
 299 #ifdef  DEBUG
 300
 301 print_closure(n)
 302 int n;
 303 {
 304   register short *isp;
 305
 306   printf ("\n\nn = %d\n\n", n);
 307   for (isp = itemset; isp < itemsetend; isp++)
 308     printf ("   %d\n", *isp);
 309 }
 310
 311
 312 void
 313 print_firsts (void)
 314 {
 315   register int i;
 316   register int j;
 317   register unsigned *rowp;
 318
 319   printf ("\n\n\nFIRSTS\n\n");
 320
 321   for (i = ntokens; i < nsyms; i++)
 322     {
 323       printf ("\n\n%s firsts\n\n", tags[i]);
 324
 325       rowp = firsts + ((i - ntokens) * varsetsize);
 326
 327       for (j = 0; j < nvars; j++)
 328         if (BITISSET (rowp, j))
 329           printf ("   %s\n", tags[j + ntokens]);
 330     }
 331 }
 332
 333
 334 void
 335 print_fderives (void)
 336 {
 337   register int i;
 338   register int j;
 339   register unsigned *rp;
 340
 341   printf ("\n\n\nFDERIVES\n");
 342
 343   for (i = ntokens; i < nsyms; i++)
 344     {
 345       printf ("\n\n%s derives\n\n", tags[i]);
 346       rp = fderives + i * rulesetsize;
 347
 348       for (j = 0; j <= nrules; j++)
 349         if (BITISSET (rp, j))
 350           printf ("   %d\n", j);
 351     }
 352
 353   fflush(stdout);
 354 }
 355
 356 #endif