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 initialize_closure PARAMS((int));
  62 void set_fderives PARAMS((void));
  63 void set_firsts PARAMS((void));
  64 void closure PARAMS((short *, int));
  65 void finalize_closure 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
  84 void
  85 initialize_closure (int n)
  86 {
  87   itemset = NEW2(n, short);
  88
  89   rulesetsize = WORDSIZE(nrules + 1);
  90   ruleset = NEW2(rulesetsize, unsigned);
  91
  92   set_fderives();
  93 }
  94
  95
  96
  97 /* set fderives to an nvars by nrules matrix of bits
  98    indicating which rules can help derive the beginning of the data
  99    for each nonterminal.  For example, if symbol 5 can be derived as
 100    the sequence of symbols 8 3 20, and one of the rules for deriving
 101    symbol 8 is rule 4, then the [5 - ntokens, 4] bit in fderives is set.  */
 102 void
 103 set_fderives (void)
 104 {
 105   register unsigned *rrow;
 106   register unsigned *vrow;
 107   register int j;
 108   register unsigned cword;
 109   register short *rp;
 110   register int b;
 111
 112   int ruleno;
 113   int i;
 114
 115   fderives = NEW2(nvars * rulesetsize, unsigned) - ntokens * rulesetsize;
 116
 117   set_firsts();
 118
 119   rrow = fderives + ntokens * rulesetsize;
 120
 121   for (i = ntokens; i < nsyms; i++)
 122     {
 123       vrow = firsts + ((i - ntokens) * varsetsize);
 124       cword = *vrow++;
 125       b = 0;
 126       for (j = ntokens; j < nsyms; j++)
 127         {
 128           if (cword & (1 << b))
 129             {
 130               rp = derives[j];
 131               while ((ruleno = *rp++) > 0)
 132                 {
 133                   SETBIT(rrow, ruleno);
 134                 }
 135             }
 136
 137           b++;
 138           if (b >= BITS_PER_WORD && j + 1 < nsyms)
 139             {
 140               cword = *vrow++;
 141               b = 0;
 142             }
 143         }
 144
 145       rrow += rulesetsize;
 146     }
 147
 148 #ifdef  DEBUG
 149   print_fderives();
 150 #endif
 151
 152   FREE(firsts);
 153 }
 154
 155
 156
 157 /* set firsts to be an nvars by nvars bit matrix indicating which items
 158    can represent the beginning of the input corresponding to which other items.
 159    For example, if some rule expands symbol 5 into the sequence of symbols 8 3 20,
 160    the symbol 8 can be the beginning of the data for symbol 5,
 161    so the bit [8 - ntokens, 5 - ntokens] in firsts is set. */
 162 void
 163 set_firsts (void)
 164 {
 165   register unsigned *row;
 166 /*   register int done; JF unused */
 167   register int symbol;
 168   register short *sp;
 169   register int rowsize;
 170
 171   int i;
 172
 173   varsetsize = rowsize = WORDSIZE(nvars);
 174
 175   firsts = NEW2(nvars * rowsize, unsigned);
 176
 177   row = firsts;
 178   for (i = ntokens; i < nsyms; i++)
 179     {
 180       sp = derives[i];
 181       while (*sp >= 0)
 182         {
 183           symbol = ritem[rrhs[*sp++]];
 184           if (ISVAR(symbol))
 185             {
 186               symbol -= ntokens;
 187               SETBIT(row, symbol);
 188             }
 189         }
 190
 191       row += rowsize;
 192     }
 193
 194   RTC(firsts, nvars);
 195
 196 #ifdef  DEBUG
 197   print_firsts();
 198 #endif
 199 }
 200
 201
 202 void
 203 closure (short *core, 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 (void)
 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 void
 308 print_firsts (void)
 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 void
 330 print_fderives (void)
 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