]> git.saurik.com Git - bison.git/blame - src/closure.c
(YY_USER_INIT): Initialize code_start, too.
[bison.git] / src / closure.c
CommitLineData
c7bd07f7
PE
1/* Closures for Bison
2
914feea9 3 Copyright (C) 1984, 1989, 2000, 2001, 2002 Free Software Foundation, Inc.
d0fb370f 4
8dc26b76 5 This file is part of Bison, the GNU Compiler Compiler.
d0fb370f 6
8dc26b76
AD
7 Bison is free software; you can redistribute it and/or modify it
8 under the terms of the GNU General Public License as published by
9 the Free Software Foundation; either version 2, or (at your option)
10 any later version.
d0fb370f 11
8dc26b76
AD
12 Bison is distributed in the hope that it will be useful, but
13 WITHOUT ANY WARRANTY; without even the implied warranty of
14 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
15 General Public License for more details.
d0fb370f 16
8dc26b76
AD
17 You should have received a copy of the GNU General Public License
18 along with Bison; see the file COPYING. If not, write to the Free
19 Software Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA
20 02111-1307, USA. */
d0fb370f 21
d0fb370f 22#include "system.h"
c7bd07f7
PE
23
24#include <bitset.h>
25#include <bitsetv-print.h>
26#include <bitsetv.h>
27#include <quotearg.h>
28
29#include "closure.h"
30#include "derives.h"
9bfe901c 31#include "getargs.h"
d0fb370f 32#include "gram.h"
2c5f66ed 33#include "reader.h"
c7bd07f7 34#include "symtab.h"
d0fb370f 35
b2872512 36/* NITEMSET is the size of the array ITEMSET. */
c7bd07f7 37item_number *itemset;
5123689b 38int nritemset;
fb908786 39
dfdb1797 40static bitset ruleset;
d0fb370f
RS
41
42/* internal data. See comments before set_fderives and set_firsts. */
914feea9
AD
43static bitsetv fderives = NULL;
44static bitsetv firsts = NULL;
d0fb370f 45
03ec521c 46/* Retrieve the FDERIVES/FIRSTS sets of the nonterminals numbered Var. */
7086e707 47#define FDERIVES(Var) fderives[(Var) - ntokens]
d8a0245c 48#define FIRSTS(Var) firsts[(Var) - ntokens]
2fa6973e 49\f
d0fb370f 50
2fa6973e
AD
51/*-----------------.
52| Debugging code. |
53`-----------------*/
d0fb370f 54
2fa6973e 55static void
c7bd07f7 56print_closure (char const *title, item_number *array, size_t size)
2fa6973e 57{
23cbcc6c 58 size_t i;
427c0dda 59 fprintf (stderr, "Closure: %s\n", title);
23cbcc6c
AD
60 for (i = 0; i < size; ++i)
61 {
c7bd07f7 62 item_number *rp;
23cbcc6c 63 fprintf (stderr, " %2d: .", array[i]);
75142d45 64 for (rp = &ritem[array[i]]; *rp >= 0; ++rp)
97650f4e 65 fprintf (stderr, " %s", symbols[*rp]->tag);
427c0dda 66 fprintf (stderr, " (rule %d)\n", -*rp - 1);
23cbcc6c
AD
67 }
68 fputs ("\n\n", stderr);
2fa6973e
AD
69}
70
71
72static void
73print_firsts (void)
d0fb370f 74{
c7bd07f7 75 symbol_number i, j;
2fa6973e 76
c87d4863 77 fprintf (stderr, "FIRSTS\n");
2fa6973e
AD
78 for (i = ntokens; i < nsyms; i++)
79 {
613f5e1a 80 bitset_iterator iter;
97650f4e 81 fprintf (stderr, "\t%s firsts\n", symbols[i]->tag);
613f5e1a
AD
82 BITSET_FOR_EACH (iter, FIRSTS (i), j, 0)
83 {
84 fprintf (stderr, "\t\t%s\n",
85 symbols[j + ntokens]->tag);
86 }
2fa6973e 87 }
c87d4863 88 fprintf (stderr, "\n\n");
d0fb370f
RS
89}
90
91
2fa6973e
AD
92static void
93print_fderives (void)
94{
9222837b 95 int i;
c7bd07f7 96 rule_number r;
2fa6973e 97
c87d4863 98 fprintf (stderr, "FDERIVES\n");
2fa6973e
AD
99 for (i = ntokens; i < nsyms; i++)
100 {
613f5e1a 101 bitset_iterator iter;
97650f4e 102 fprintf (stderr, "\t%s derives\n", symbols[i]->tag);
613f5e1a
AD
103 BITSET_FOR_EACH (iter, FDERIVES (i), r, 0)
104 {
e1a4f3a4
AD
105 fprintf (stderr, "\t\t%3d ", r);
106 rule_rhs_print (&rules[r], stderr);
613f5e1a 107 }
2fa6973e 108 }
c87d4863 109 fprintf (stderr, "\n\n");
2fa6973e 110}
2fa6973e 111\f
d8a0245c
AD
112/*------------------------------------------------------------------.
113| Set FIRSTS to be an NVARS array of NVARS bitsets indicating which |
114| items can represent the beginning of the input corresponding to |
115| which other items. |
116| |
117| For example, if some rule expands symbol 5 into the sequence of |
118| symbols 8 3 20, the symbol 8 can be the beginning of the data for |
119| symbol 5, so the bit [8 - ntokens] in first[5 - ntokens] (= FIRST |
120| (5)) is set. |
121`------------------------------------------------------------------*/
2fa6973e
AD
122
123static void
124set_firsts (void)
125{
c7bd07f7 126 symbol_number i, j;
2fa6973e 127
914feea9
AD
128 firsts = bitsetv_create (nvars, nvars, BITSET_FIXED);
129
2fa6973e 130 for (i = ntokens; i < nsyms; i++)
bb7c2bc6 131 for (j = 0; derives[i - ntokens][j]; ++j)
914feea9 132 {
bb7c2bc6 133 item_number sym = derives[i - ntokens][j]->rhs[0];
c7bd07f7
PE
134 if (ISVAR (sym))
135 bitset_set (FIRSTS (i), sym - ntokens);
914feea9 136 }
2fa6973e 137
273a74fa 138 if (trace_flag & trace_sets)
427c0dda 139 bitsetv_matrix_dump (stderr, "RTC: Firsts Input", firsts);
65ccf9fc 140 bitsetv_reflexive_transitive_closure (firsts);
273a74fa 141 if (trace_flag & trace_sets)
427c0dda 142 bitsetv_matrix_dump (stderr, "RTC: Firsts Output", firsts);
2fa6973e 143
273a74fa 144 if (trace_flag & trace_sets)
9bfe901c 145 print_firsts ();
2fa6973e
AD
146}
147
148/*-------------------------------------------------------------------.
149| Set FDERIVES to an NVARS by NRULES matrix of bits indicating which |
150| rules can help derive the beginning of the data for each |
151| nonterminal. |
152| |
153| For example, if symbol 5 can be derived as the sequence of symbols |
154| 8 3 20, and one of the rules for deriving symbol 8 is rule 4, then |
155| the [5 - NTOKENS, 4] bit in FDERIVES is set. |
156`-------------------------------------------------------------------*/
d0fb370f 157
4a120d45 158static void
d2729d44 159set_fderives (void)
d0fb370f 160{
c7bd07f7
PE
161 symbol_number i, j;
162 rule_number k;
d0fb370f 163
4b3d3a8e 164 fderives = bitsetv_create (nvars, nrules, BITSET_FIXED);
d0fb370f 165
2fa6973e 166 set_firsts ();
d0fb370f 167
1cbcf2e7
AD
168 for (i = ntokens; i < nsyms; ++i)
169 for (j = ntokens; j < nsyms; ++j)
d8a0245c 170 if (bitset_test (FIRSTS (i), j - ntokens))
bb7c2bc6
PE
171 for (k = 0; derives[j - ntokens][k]; ++k)
172 bitset_set (FDERIVES (i), derives[j - ntokens][k]->number);
d0fb370f 173
273a74fa 174 if (trace_flag & trace_sets)
9bfe901c 175 print_fderives ();
d0fb370f 176
914feea9 177 bitsetv_free (firsts);
d0fb370f 178}
1565b720 179
2fa6973e 180\f
d0fb370f 181
2fa6973e
AD
182void
183new_closure (int n)
d0fb370f 184{
bb7c2bc6 185 CALLOC (itemset, n);
d0fb370f 186
4b3d3a8e 187 ruleset = bitset_create (nrules, BITSET_FIXED);
d0fb370f 188
2fa6973e 189 set_fderives ();
d0fb370f
RS
190}
191
192
2fa6973e 193
d0fb370f 194void
c7bd07f7 195closure (item_number *core, int n)
d0fb370f 196{
576890b7
AD
197 /* Index over CORE. */
198 int c;
199
d2b04478 200 /* A bit index over RULESET. */
c7bd07f7 201 rule_number ruleno;
d0fb370f 202
613f5e1a
AD
203 bitset_iterator iter;
204
273a74fa 205 if (trace_flag & trace_sets)
427c0dda 206 print_closure ("input", core, n);
c87d4863 207
643a5994 208 bitset_zero (ruleset);
d0fb370f 209
643a5994
AD
210 for (c = 0; c < n; ++c)
211 if (ISVAR (ritem[core[c]]))
212 bitset_or (ruleset, ruleset, FDERIVES (ritem[core[c]]));
d0fb370f 213
5123689b 214 nritemset = 0;
576890b7 215 c = 0;
613f5e1a
AD
216 BITSET_FOR_EACH (iter, ruleset, ruleno, 0)
217 {
c7bd07f7 218 item_number itemno = rules[ruleno].rhs - ritem;
613f5e1a
AD
219 while (c < n && core[c] < itemno)
220 {
221 itemset[nritemset] = core[c];
222 nritemset++;
223 c++;
224 }
225 itemset[nritemset] = itemno;
226 nritemset++;
227 };
d0fb370f 228
576890b7
AD
229 while (c < n)
230 {
5123689b
AD
231 itemset[nritemset] = core[c];
232 nritemset++;
576890b7
AD
233 c++;
234 }
d0fb370f 235
273a74fa 236 if (trace_flag & trace_sets)
427c0dda 237 print_closure ("output", itemset, nritemset);
d0fb370f
RS
238}
239
240
241void
2fa6973e 242free_closure (void)
d0fb370f 243{
6c5f863a 244 XFREE (itemset);
dfdb1797 245 bitset_free (ruleset);
914feea9 246 bitsetv_free (fderives);
d0fb370f 247}