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 | * | |
8 | * Redistribution and use in source and binary forms are permitted | |
9 | * provided that the above copyright notice and this paragraph are | |
10 | * duplicated in all such forms and that any documentation, | |
11 | * advertising materials, and other materials related to such | |
12 | * distribution and use acknowledge that the software was developed | |
13 | * by the University of California, Berkeley. The name of the | |
14 | * University may not be used to endorse or promote products derived | |
15 | * from this software without specific prior written permission. | |
16 | * THIS SOFTWARE IS PROVIDED ``AS IS'' AND WITHOUT ANY EXPRESS OR | |
17 | * IMPLIED WARRANTIES, INCLUDING, WITHOUT LIMITATION, THE IMPLIED | |
18 | * WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE. | |
19 | */ | |
20 | ||
21 | #ifndef lint | |
22 | static char sccsid[] = "@(#)closure.c 5.1 (Berkeley) %G%"; | |
23 | #endif /* not lint */ | |
24 | ||
25 | #include "defs.h" | |
26 | ||
27 | short *itemset; | |
28 | short *itemsetend; | |
29 | unsigned *ruleset; | |
30 | ||
31 | static unsigned *first_derives; | |
32 | static unsigned *EFF; | |
33 | ||
34 | ||
35 | set_EFF() | |
36 | { | |
37 | register unsigned *row; | |
38 | register int symbol; | |
39 | register short *sp; | |
40 | register int rowsize; | |
41 | register int i; | |
42 | register int rule; | |
43 | ||
44 | rowsize = WORDSIZE(nvars); | |
45 | EFF = NEW2(nvars * rowsize, unsigned); | |
46 | ||
47 | row = EFF; | |
48 | for (i = start_symbol; i < nsyms; i++) | |
49 | { | |
50 | sp = derives[i]; | |
51 | for (rule = *sp; rule > 0; rule = *++sp) | |
52 | { | |
53 | symbol = ritem[rrhs[rule]]; | |
54 | if (ISVAR(symbol)) | |
55 | { | |
56 | symbol -= start_symbol; | |
57 | SETBIT(row, symbol); | |
58 | } | |
59 | } | |
60 | row += rowsize; | |
61 | } | |
62 | ||
63 | reflexive_transitive_closure(EFF, nvars); | |
64 | ||
65 | #ifdef DEBUG | |
66 | print_EFF(); | |
67 | #endif | |
68 | } | |
69 | ||
70 | ||
71 | set_first_derives() | |
72 | { | |
73 | register unsigned *rrow; | |
74 | register unsigned *vrow; | |
75 | register int j; | |
76 | register unsigned mask; | |
77 | register unsigned cword; | |
78 | register short *rp; | |
79 | ||
80 | int rule; | |
81 | int i; | |
82 | int rulesetsize; | |
83 | int varsetsize; | |
84 | ||
85 | rulesetsize = WORDSIZE(nrules); | |
86 | varsetsize = WORDSIZE(nvars); | |
87 | first_derives = NEW2(nvars * rulesetsize, unsigned) - ntokens * rulesetsize; | |
88 | ||
89 | set_EFF(); | |
90 | ||
91 | rrow = first_derives + ntokens * rulesetsize; | |
92 | for (i = start_symbol; i < nsyms; i++) | |
93 | { | |
94 | vrow = EFF + ((i - ntokens) * varsetsize); | |
95 | cword = *vrow++; | |
96 | mask = 1; | |
97 | for (j = start_symbol; j < nsyms; j++) | |
98 | { | |
99 | if (cword & mask) | |
100 | { | |
101 | rp = derives[j]; | |
102 | while ((rule = *rp++) >= 0) | |
103 | { | |
104 | SETBIT(rrow, rule); | |
105 | } | |
106 | } | |
107 | ||
108 | mask <<= 1; | |
109 | if (mask == 0) | |
110 | { | |
111 | cword = *vrow++; | |
112 | mask = 1; | |
113 | } | |
114 | } | |
115 | ||
116 | vrow += varsetsize; | |
117 | rrow += rulesetsize; | |
118 | } | |
119 | ||
120 | #ifdef DEBUG | |
121 | print_first_derives(); | |
122 | #endif | |
123 | ||
124 | FREE(EFF); | |
125 | } | |
126 | ||
127 | ||
128 | closure(nucleus, n) | |
129 | short *nucleus; | |
130 | int n; | |
131 | { | |
132 | register int ruleno; | |
133 | register unsigned word; | |
134 | register unsigned mask; | |
135 | register short *csp; | |
136 | register unsigned *dsp; | |
137 | register unsigned *rsp; | |
138 | register int rulesetsize; | |
139 | ||
140 | short *csend; | |
141 | unsigned *rsend; | |
142 | int symbol; | |
143 | int itemno; | |
144 | ||
145 | rulesetsize = WORDSIZE(nrules); | |
146 | rsp = ruleset; | |
147 | rsend = ruleset + rulesetsize; | |
148 | for (rsp = ruleset; rsp < rsend; rsp++) | |
149 | *rsp = 0; | |
150 | ||
151 | csend = nucleus + n; | |
152 | for (csp = nucleus; csp < csend; ++csp) | |
153 | { | |
154 | symbol = ritem[*csp]; | |
155 | if (ISVAR(symbol)) | |
156 | { | |
157 | dsp = first_derives + symbol * rulesetsize; | |
158 | rsp = ruleset; | |
159 | while (rsp < rsend) | |
160 | *rsp++ |= *dsp++; | |
161 | } | |
162 | } | |
163 | ||
164 | ruleno = 0; | |
165 | itemsetend = itemset; | |
166 | csp = nucleus; | |
167 | for (rsp = ruleset; rsp < rsend; ++rsp) | |
168 | { | |
169 | word = *rsp; | |
170 | if (word == 0) | |
171 | ruleno += BITS_PER_WORD; | |
172 | else | |
173 | { | |
174 | mask = 1; | |
175 | while (mask) | |
176 | { | |
177 | if (word & mask) | |
178 | { | |
179 | itemno = rrhs[ruleno]; | |
180 | while (csp < csend && *csp < itemno) | |
181 | *itemsetend++ = *csp++; | |
182 | *itemsetend++ = itemno; | |
183 | while (csp < csend && *csp == itemno) | |
184 | ++csp; | |
185 | } | |
186 | ||
187 | mask <<= 1; | |
188 | ++ruleno; | |
189 | } | |
190 | } | |
191 | } | |
192 | ||
193 | while (csp < csend) | |
194 | *itemsetend++ = *csp++; | |
195 | ||
196 | #ifdef DEBUG | |
197 | print_closure(n); | |
198 | #endif | |
199 | } | |
200 | ||
201 | ||
202 | ||
203 | finalize_closure() | |
204 | { | |
205 | FREE(itemset); | |
206 | FREE(ruleset); | |
207 | FREE(first_derives + ntokens * WORDSIZE(nrules)); | |
208 | } | |
209 | ||
210 | ||
211 | #ifdef DEBUG | |
212 | ||
213 | print_closure(n) | |
214 | int n; | |
215 | { | |
216 | register short *isp; | |
217 | ||
218 | printf("\n\nn = %d\n\n", n); | |
219 | for (isp = itemset; isp < itemsetend; isp++) | |
220 | printf(" %d\n", *isp); | |
221 | } | |
222 | ||
223 | ||
224 | print_EFF() | |
225 | { | |
226 | register int i, j, k; | |
227 | register unsigned *rowp; | |
228 | register unsigned word; | |
229 | register unsigned mask; | |
230 | ||
231 | printf("\n\nEpsilon Free Firsts\n"); | |
232 | ||
233 | for (i = start_symbol; i < nsyms; i++) | |
234 | { | |
235 | printf("\n%s", symbol_name[i]); | |
236 | rowp = EFF + ((i - start_symbol) * WORDSIZE(nvars)); | |
237 | word = *rowp++; | |
238 | ||
239 | mask = 1; | |
240 | for (j = 0; j < nvars; j++) | |
241 | { | |
242 | if (word & mask) | |
243 | printf(" %s", symbol_name[start_symbol + j]); | |
244 | ||
245 | mask <<= 1; | |
246 | if (mask == 0) | |
247 | { | |
248 | word = *rowp++; | |
249 | mask = 1; | |
250 | } | |
251 | } | |
252 | } | |
253 | } | |
254 | ||
255 | ||
256 | print_first_derives() | |
257 | { | |
258 | register int i; | |
259 | register int j; | |
260 | register unsigned *rp; | |
261 | register unsigned cword; | |
262 | register unsigned mask; | |
263 | ||
264 | printf("\n\n\nFirst Derives\n"); | |
265 | ||
266 | for (i = start_symbol; i < nsyms; i++) | |
267 | { | |
268 | printf("\n%s derives\n", symbol_name[i]); | |
269 | rp = first_derives + i * WORDSIZE(nrules); | |
270 | cword = *rp++; | |
271 | mask = 1; | |
272 | for (j = 0; j <= nrules; j++) | |
273 | { | |
274 | if (cword & mask) | |
275 | printf(" %d\n", j); | |
276 | ||
277 | mask <<= 1; | |
278 | if (mask == 0) | |
279 | { | |
280 | cword = *rp++; | |
281 | mask = 1; | |
282 | } | |
283 | } | |
284 | } | |
285 | ||
286 | fflush(stdout); | |
287 | } | |
288 | ||
289 | #endif |