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