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