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