Commit | Line | Data |
---|---|---|
8e0e4084 KB |
1 | /* |
2 | * Copyright (c) 1989 The Regents of the University of California. | |
3 | * All rights reserved. | |
4 | * | |
5 | * This code is derived from software contributed to Berkeley by | |
6 | * Robert Paul Corbett. | |
7 | * | |
6ecf3d85 | 8 | * %sccs.include.redist.c% |
8e0e4084 KB |
9 | */ |
10 | ||
11 | #ifndef lint | |
6ecf3d85 | 12 | static char sccsid[] = "@(#)closure.c 5.2 (Berkeley) %G%"; |
8e0e4084 KB |
13 | #endif /* not lint */ |
14 | ||
15 | #include "defs.h" | |
16 | ||
17 | short *itemset; | |
18 | short *itemsetend; | |
19 | unsigned *ruleset; | |
20 | ||
21 | static unsigned *first_derives; | |
22 | static unsigned *EFF; | |
23 | ||
24 | ||
25 | set_EFF() | |
26 | { | |
27 | register unsigned *row; | |
28 | register int symbol; | |
29 | register short *sp; | |
30 | register int rowsize; | |
31 | register int i; | |
32 | register int rule; | |
33 | ||
34 | rowsize = WORDSIZE(nvars); | |
35 | EFF = NEW2(nvars * rowsize, unsigned); | |
36 | ||
37 | row = EFF; | |
38 | for (i = start_symbol; i < nsyms; i++) | |
39 | { | |
40 | sp = derives[i]; | |
41 | for (rule = *sp; rule > 0; rule = *++sp) | |
42 | { | |
43 | symbol = ritem[rrhs[rule]]; | |
44 | if (ISVAR(symbol)) | |
45 | { | |
46 | symbol -= start_symbol; | |
47 | SETBIT(row, symbol); | |
48 | } | |
49 | } | |
50 | row += rowsize; | |
51 | } | |
52 | ||
53 | reflexive_transitive_closure(EFF, nvars); | |
54 | ||
55 | #ifdef DEBUG | |
56 | print_EFF(); | |
57 | #endif | |
58 | } | |
59 | ||
60 | ||
61 | set_first_derives() | |
62 | { | |
63 | register unsigned *rrow; | |
64 | register unsigned *vrow; | |
65 | register int j; | |
66 | register unsigned mask; | |
67 | register unsigned cword; | |
68 | register short *rp; | |
69 | ||
70 | int rule; | |
71 | int i; | |
72 | int rulesetsize; | |
73 | int varsetsize; | |
74 | ||
75 | rulesetsize = WORDSIZE(nrules); | |
76 | varsetsize = WORDSIZE(nvars); | |
77 | first_derives = NEW2(nvars * rulesetsize, unsigned) - ntokens * rulesetsize; | |
78 | ||
79 | set_EFF(); | |
80 | ||
81 | rrow = first_derives + ntokens * rulesetsize; | |
82 | for (i = start_symbol; i < nsyms; i++) | |
83 | { | |
84 | vrow = EFF + ((i - ntokens) * varsetsize); | |
85 | cword = *vrow++; | |
86 | mask = 1; | |
87 | for (j = start_symbol; j < nsyms; j++) | |
88 | { | |
89 | if (cword & mask) | |
90 | { | |
91 | rp = derives[j]; | |
92 | while ((rule = *rp++) >= 0) | |
93 | { | |
94 | SETBIT(rrow, rule); | |
95 | } | |
96 | } | |
97 | ||
98 | mask <<= 1; | |
99 | if (mask == 0) | |
100 | { | |
101 | cword = *vrow++; | |
102 | mask = 1; | |
103 | } | |
104 | } | |
105 | ||
106 | vrow += varsetsize; | |
107 | rrow += rulesetsize; | |
108 | } | |
109 | ||
110 | #ifdef DEBUG | |
111 | print_first_derives(); | |
112 | #endif | |
113 | ||
114 | FREE(EFF); | |
115 | } | |
116 | ||
117 | ||
118 | closure(nucleus, n) | |
119 | short *nucleus; | |
120 | int n; | |
121 | { | |
122 | register int ruleno; | |
123 | register unsigned word; | |
124 | register unsigned mask; | |
125 | register short *csp; | |
126 | register unsigned *dsp; | |
127 | register unsigned *rsp; | |
128 | register int rulesetsize; | |
129 | ||
130 | short *csend; | |
131 | unsigned *rsend; | |
132 | int symbol; | |
133 | int itemno; | |
134 | ||
135 | rulesetsize = WORDSIZE(nrules); | |
136 | rsp = ruleset; | |
137 | rsend = ruleset + rulesetsize; | |
138 | for (rsp = ruleset; rsp < rsend; rsp++) | |
139 | *rsp = 0; | |
140 | ||
141 | csend = nucleus + n; | |
142 | for (csp = nucleus; csp < csend; ++csp) | |
143 | { | |
144 | symbol = ritem[*csp]; | |
145 | if (ISVAR(symbol)) | |
146 | { | |
147 | dsp = first_derives + symbol * rulesetsize; | |
148 | rsp = ruleset; | |
149 | while (rsp < rsend) | |
150 | *rsp++ |= *dsp++; | |
151 | } | |
152 | } | |
153 | ||
154 | ruleno = 0; | |
155 | itemsetend = itemset; | |
156 | csp = nucleus; | |
157 | for (rsp = ruleset; rsp < rsend; ++rsp) | |
158 | { | |
159 | word = *rsp; | |
160 | if (word == 0) | |
161 | ruleno += BITS_PER_WORD; | |
162 | else | |
163 | { | |
164 | mask = 1; | |
165 | while (mask) | |
166 | { | |
167 | if (word & mask) | |
168 | { | |
169 | itemno = rrhs[ruleno]; | |
170 | while (csp < csend && *csp < itemno) | |
171 | *itemsetend++ = *csp++; | |
172 | *itemsetend++ = itemno; | |
173 | while (csp < csend && *csp == itemno) | |
174 | ++csp; | |
175 | } | |
176 | ||
177 | mask <<= 1; | |
178 | ++ruleno; | |
179 | } | |
180 | } | |
181 | } | |
182 | ||
183 | while (csp < csend) | |
184 | *itemsetend++ = *csp++; | |
185 | ||
186 | #ifdef DEBUG | |
187 | print_closure(n); | |
188 | #endif | |
189 | } | |
190 | ||
191 | ||
192 | ||
193 | finalize_closure() | |
194 | { | |
195 | FREE(itemset); | |
196 | FREE(ruleset); | |
197 | FREE(first_derives + ntokens * WORDSIZE(nrules)); | |
198 | } | |
199 | ||
200 | ||
201 | #ifdef DEBUG | |
202 | ||
203 | print_closure(n) | |
204 | int n; | |
205 | { | |
206 | register short *isp; | |
207 | ||
208 | printf("\n\nn = %d\n\n", n); | |
209 | for (isp = itemset; isp < itemsetend; isp++) | |
210 | printf(" %d\n", *isp); | |
211 | } | |
212 | ||
213 | ||
214 | print_EFF() | |
215 | { | |
216 | register int i, j, k; | |
217 | register unsigned *rowp; | |
218 | register unsigned word; | |
219 | register unsigned mask; | |
220 | ||
221 | printf("\n\nEpsilon Free Firsts\n"); | |
222 | ||
223 | for (i = start_symbol; i < nsyms; i++) | |
224 | { | |
225 | printf("\n%s", symbol_name[i]); | |
226 | rowp = EFF + ((i - start_symbol) * WORDSIZE(nvars)); | |
227 | word = *rowp++; | |
228 | ||
229 | mask = 1; | |
230 | for (j = 0; j < nvars; j++) | |
231 | { | |
232 | if (word & mask) | |
233 | printf(" %s", symbol_name[start_symbol + j]); | |
234 | ||
235 | mask <<= 1; | |
236 | if (mask == 0) | |
237 | { | |
238 | word = *rowp++; | |
239 | mask = 1; | |
240 | } | |
241 | } | |
242 | } | |
243 | } | |
244 | ||
245 | ||
246 | print_first_derives() | |
247 | { | |
248 | register int i; | |
249 | register int j; | |
250 | register unsigned *rp; | |
251 | register unsigned cword; | |
252 | register unsigned mask; | |
253 | ||
254 | printf("\n\n\nFirst Derives\n"); | |
255 | ||
256 | for (i = start_symbol; i < nsyms; i++) | |
257 | { | |
258 | printf("\n%s derives\n", symbol_name[i]); | |
259 | rp = first_derives + i * WORDSIZE(nrules); | |
260 | cword = *rp++; | |
261 | mask = 1; | |
262 | for (j = 0; j <= nrules; j++) | |
263 | { | |
264 | if (cword & mask) | |
265 | printf(" %d\n", j); | |
266 | ||
267 | mask <<= 1; | |
268 | if (mask == 0) | |
269 | { | |
270 | cword = *rp++; | |
271 | mask = 1; | |
272 | } | |
273 | } | |
274 | } | |
275 | ||
276 | fflush(stdout); | |
277 | } | |
278 | ||
279 | #endif |