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