3 Copyright (C) 1984, 1989, 2000, 2001, 2002, 2004 Free Software
6 This file is part of Bison, the GNU Compiler Compiler.
8 Bison is free software; you can redistribute it and/or modify it
9 under the terms of the GNU General Public License as published by
10 the Free Software Foundation; either version 2, or (at your option)
13 Bison is distributed in the hope that it will be useful, but
14 WITHOUT ANY WARRANTY; without even the implied warranty of
15 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
16 General Public License for more details.
18 You should have received a copy of the GNU General Public License
19 along with Bison; see the file COPYING. If not, write to the Free
20 Software Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA
26 #include <bitsetv-print.h>
37 /* NITEMSET is the size of the array ITEMSET. */
41 static bitset ruleset
;
43 /* internal data. See comments before set_fderives and set_firsts. */
44 static bitsetv fderives
= NULL
;
45 static bitsetv firsts
= NULL
;
47 /* Retrieve the FDERIVES/FIRSTS sets of the nonterminals numbered Var. */
48 #define FDERIVES(Var) fderives[(Var) - ntokens]
49 #define FIRSTS(Var) firsts[(Var) - ntokens]
57 print_closure (char const *title
, item_number
*array
, size_t size
)
60 fprintf (stderr
, "Closure: %s\n", title
);
61 for (i
= 0; i
< size
; ++i
)
64 fprintf (stderr
, " %2d: .", array
[i
]);
65 for (rp
= &ritem
[array
[i
]]; *rp
>= 0; ++rp
)
66 fprintf (stderr
, " %s", symbols
[*rp
]->tag
);
67 fprintf (stderr
, " (rule %d)\n", -*rp
- 1);
69 fputs ("\n\n", stderr
);
78 fprintf (stderr
, "FIRSTS\n");
79 for (i
= ntokens
; i
< nsyms
; i
++)
82 fprintf (stderr
, "\t%s firsts\n", symbols
[i
]->tag
);
83 BITSET_FOR_EACH (iter
, FIRSTS (i
), j
, 0)
85 fprintf (stderr
, "\t\t%s\n",
86 symbols
[j
+ ntokens
]->tag
);
89 fprintf (stderr
, "\n\n");
99 fprintf (stderr
, "FDERIVES\n");
100 for (i
= ntokens
; i
< nsyms
; i
++)
102 bitset_iterator iter
;
103 fprintf (stderr
, "\t%s derives\n", symbols
[i
]->tag
);
104 BITSET_FOR_EACH (iter
, FDERIVES (i
), r
, 0)
106 fprintf (stderr
, "\t\t%3d ", r
);
107 rule_rhs_print (&rules
[r
], stderr
);
110 fprintf (stderr
, "\n\n");
113 /*------------------------------------------------------------------.
114 | Set FIRSTS to be an NVARS array of NVARS bitsets indicating which |
115 | items can represent the beginning of the input corresponding to |
116 | which other items. |
118 | For example, if some rule expands symbol 5 into the sequence of |
119 | symbols 8 3 20, the symbol 8 can be the beginning of the data for |
120 | symbol 5, so the bit [8 - ntokens] in first[5 - ntokens] (= FIRST |
122 `------------------------------------------------------------------*/
129 firsts
= bitsetv_create (nvars
, nvars
, BITSET_FIXED
);
131 for (i
= ntokens
; i
< nsyms
; i
++)
132 for (j
= 0; derives
[i
- ntokens
][j
]; ++j
)
134 item_number sym
= derives
[i
- ntokens
][j
]->rhs
[0];
136 bitset_set (FIRSTS (i
), sym
- ntokens
);
139 if (trace_flag
& trace_sets
)
140 bitsetv_matrix_dump (stderr
, "RTC: Firsts Input", firsts
);
141 bitsetv_reflexive_transitive_closure (firsts
);
142 if (trace_flag
& trace_sets
)
143 bitsetv_matrix_dump (stderr
, "RTC: Firsts Output", firsts
);
145 if (trace_flag
& trace_sets
)
149 /*-------------------------------------------------------------------.
150 | Set FDERIVES to an NVARS by NRULES matrix of bits indicating which |
151 | rules can help derive the beginning of the data for each |
154 | For example, if symbol 5 can be derived as the sequence of symbols |
155 | 8 3 20, and one of the rules for deriving symbol 8 is rule 4, then |
156 | the [5 - NTOKENS, 4] bit in FDERIVES is set. |
157 `-------------------------------------------------------------------*/
165 fderives
= bitsetv_create (nvars
, nrules
, BITSET_FIXED
);
169 for (i
= ntokens
; i
< nsyms
; ++i
)
170 for (j
= ntokens
; j
< nsyms
; ++j
)
171 if (bitset_test (FIRSTS (i
), j
- ntokens
))
172 for (k
= 0; derives
[j
- ntokens
][k
]; ++k
)
173 bitset_set (FDERIVES (i
), derives
[j
- ntokens
][k
]->number
);
175 if (trace_flag
& trace_sets
)
178 bitsetv_free (firsts
);
184 new_closure (unsigned int n
)
186 itemset
= xnmalloc (n
, sizeof *itemset
);
188 ruleset
= bitset_create (nrules
, BITSET_FIXED
);
196 closure (item_number
*core
, size_t n
)
198 /* Index over CORE. */
201 /* A bit index over RULESET. */
204 bitset_iterator iter
;
206 if (trace_flag
& trace_sets
)
207 print_closure ("input", core
, n
);
209 bitset_zero (ruleset
);
211 for (c
= 0; c
< n
; ++c
)
212 if (ISVAR (ritem
[core
[c
]]))
213 bitset_or (ruleset
, ruleset
, FDERIVES (ritem
[core
[c
]]));
217 BITSET_FOR_EACH (iter
, ruleset
, ruleno
, 0)
219 item_number itemno
= rules
[ruleno
].rhs
- ritem
;
220 while (c
< n
&& core
[c
] < itemno
)
222 itemset
[nritemset
] = core
[c
];
226 itemset
[nritemset
] = itemno
;
232 itemset
[nritemset
] = core
[c
];
237 if (trace_flag
& trace_sets
)
238 print_closure ("output", itemset
, nritemset
);
246 bitset_free (ruleset
);
247 bitsetv_free (fderives
);