src/closure.c

   1 /* Subroutines for bison
   2    Copyright (C) 1984, 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 /* 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,
  29 set up ruleset and itemset to indicate what rules could be run
  30 and which items could be accepted when those items are the active ones.
  31
  32 ruleset contains a bit for each rule.  closure sets the bits
  33 for all 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 the end
  36  of the part of it that is significant.
  37 closure places there the indices of all items which represent units of
  38 input that could arrive next.
  39
  40   initialize_closure (n)
  41
  42 Allocates the itemset and ruleset vectors,
  43 and precomputes useful data so that closure can be called.
  44 n is the number of elements to 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 items
 159    can represent the beginning of the input corresponding to which other items.
 160    For example, if some rule expands symbol 5 into the sequence of symbols 8 3 20,
 161    the symbol 8 can be the beginning of the data for symbol 5,
 162    so the bit [8 - ntokens, 5 - ntokens] in firsts is set. */
 163 void
 164 set_firsts (void)
 165 {
 166   register unsigned *row;
 167 /*   register int done; JF unused */
 168   register int symbol;
 169   register short *sp;
 170   register int rowsize;
 171
 172   int i;
 173
 174   varsetsize = rowsize = WORDSIZE(nvars);
 175
 176   firsts = NEW2(nvars * rowsize, unsigned);
 177
 178   row = firsts;
 179   for (i = ntokens; i < nsyms; i++)
 180     {
 181       sp = derives[i];
 182       while (*sp >= 0)
 183         {
 184           symbol = ritem[rrhs[*sp++]];
 185           if (ISVAR(symbol))
 186             {
 187               symbol -= ntokens;
 188               SETBIT(row, symbol);
 189             }
 190         }
 191
 192       row += rowsize;
 193     }
 194
 195   RTC(firsts, nvars);
 196
 197 #ifdef  DEBUG
 198   print_firsts();
 199 #endif
 200 }
 201
 202
 203 void
 204 closure (short *core, int n)
 205 {
 206   register int ruleno;
 207   register unsigned word;
 208   register short *csp;
 209   register unsigned *dsp;
 210   register unsigned *rsp;
 211
 212   short *csend;
 213   unsigned *rsend;
 214   int symbol;
 215   int itemno;
 216
 217   rsp = ruleset;
 218   rsend = ruleset + rulesetsize;
 219   csend = core + n;
 220
 221   if (n == 0)
 222     {
 223       dsp = fderives + start_symbol * rulesetsize;
 224       while (rsp < rsend)
 225         *rsp++ = *dsp++;
 226     }
 227   else
 228     {
 229       while (rsp < rsend)
 230         *rsp++ = 0;
 231
 232       csp = core;
 233       while (csp < csend)
 234         {
 235           symbol = ritem[*csp++];
 236           if (ISVAR(symbol))
 237             {
 238               dsp = fderives + symbol * rulesetsize;
 239               rsp = ruleset;
 240               while (rsp < rsend)
 241                 *rsp++ |= *dsp++;
 242             }
 243         }
 244     }
 245
 246   ruleno = 0;
 247   itemsetend = itemset;
 248   csp = core;
 249   rsp = ruleset;
 250   while (rsp < rsend)
 251     {
 252       word = *rsp++;
 253       if (word == 0)
 254         {
 255           ruleno += BITS_PER_WORD;
 256         }
 257       else
 258         {
 259           register int b;
 260
 261           for (b = 0; b < BITS_PER_WORD; b++)
 262             {
 263               if (word & (1 << b))
 264                 {
 265                   itemno = rrhs[ruleno];
 266                   while (csp < csend && *csp < itemno)
 267                     *itemsetend++ = *csp++;
 268                   *itemsetend++ = itemno;
 269                 }
 270
 271               ruleno++;
 272             }
 273         }
 274     }
 275
 276   while (csp < csend)
 277     *itemsetend++ = *csp++;
 278
 279 #ifdef  DEBUG
 280   print_closure(n);
 281 #endif
 282 }
 283
 284
 285 void
 286 finalize_closure (void)
 287 {
 288   FREE(itemset);
 289   FREE(ruleset);
 290   FREE(fderives + ntokens * rulesetsize);
 291 }
 292
 293
 294
 295 #ifdef  DEBUG
 296
 297 print_closure(n)
 298 int n;
 299 {
 300   register short *isp;
 301
 302   printf("\n\nn = %d\n\n", n);
 303   for (isp = itemset; isp < itemsetend; isp++)
 304     printf("   %d\n", *isp);
 305 }
 306
 307
 308 void
 309 print_firsts (void)
 310 {
 311   register int i;
 312   register int j;
 313   register unsigned *rowp;
 314
 315   printf(_("\n\n\nFIRSTS\n\n"));
 316
 317   for (i = ntokens; i < nsyms; i++)
 318     {
 319       printf(_("\n\n%s firsts\n\n"), tags[i]);
 320
 321       rowp = firsts + ((i - ntokens) * varsetsize);
 322
 323       for (j = 0; j < nvars; j++)
 324         if (BITISSET (rowp, j))
 325           printf("   %s\n", tags[j + ntokens]);
 326     }
 327 }
 328
 329
 330 void
 331 print_fderives (void)
 332 {
 333   register int i;
 334   register int j;
 335   register unsigned *rp;
 336
 337   printf(_("\n\n\nFDERIVES\n"));
 338
 339   for (i = ntokens; i < nsyms; i++)
 340     {
 341       printf(_("\n\n%s derives\n\n"), tags[i]);
 342       rp = fderives + i * rulesetsize;
 343
 344       for (j = 0; j <= nrules; j++)
 345         if (BITISSET (rp, j))
 346           printf("   %d\n", j);
 347     }
 348
 349   fflush(stdout);
 350 }
 351
 352 #endif