source: trunk/minix/commands/byacc/closure.c@ 10

Last change on this file since 10 was 9, checked in by Mattia Monga, 13 years ago

Minix 3.1.2a

File size: 4.2 KB
Line 
1#include "defs.h"
2
3short *itemset;
4short *itemsetend;
5unsigned *ruleset;
6
7static unsigned *first_derives;
8static unsigned *EFF;
9
10
11set_EFF()
12{
13 register unsigned *row;
14 register int symbol;
15 register short *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
47set_first_derives()
48{
49 register unsigned *rrow;
50 register unsigned *vrow;
51 register int j;
52 register unsigned k;
53 register unsigned cword;
54 register short *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 k = BITS_PER_WORD;
72 for (j = start_symbol; j < nsyms; k++, j++)
73 {
74 if (k >= BITS_PER_WORD)
75 {
76 cword = *vrow++;
77 k = 0;
78 }
79
80 if (cword & (1 << k))
81 {
82 rp = derives[j];
83 while ((rule = *rp++) >= 0)
84 {
85 SETBIT(rrow, rule);
86 }
87 }
88 }
89
90 vrow += varsetsize;
91 rrow += rulesetsize;
92 }
93
94#ifdef DEBUG
95 print_first_derives();
96#endif
97
98 FREE(EFF);
99}
100
101
102closure(nucleus, n)
103short *nucleus;
104int n;
105{
106 register int ruleno;
107 register unsigned word;
108 register unsigned i;
109 register short *csp;
110 register unsigned *dsp;
111 register unsigned *rsp;
112 register int rulesetsize;
113
114 short *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)
145 {
146 for (i = 0; i < BITS_PER_WORD; ++i)
147 {
148 if (word & (1 << i))
149 {
150 itemno = rrhs[ruleno+i];
151 while (csp < csend && *csp < itemno)
152 *itemsetend++ = *csp++;
153 *itemsetend++ = itemno;
154 while (csp < csend && *csp == itemno)
155 ++csp;
156 }
157 }
158 }
159 ruleno += BITS_PER_WORD;
160 }
161
162 while (csp < csend)
163 *itemsetend++ = *csp++;
164
165#ifdef DEBUG
166 print_closure(n);
167#endif
168}
169
170
171
172finalize_closure()
173{
174 FREE(itemset);
175 FREE(ruleset);
176 FREE(first_derives + ntokens * WORDSIZE(nrules));
177}
178
179
180#ifdef DEBUG
181
182print_closure(n)
183int n;
184{
185 register short *isp;
186
187 printf("\n\nn = %d\n\n", n);
188 for (isp = itemset; isp < itemsetend; isp++)
189 printf(" %d\n", *isp);
190}
191
192
193print_EFF()
194{
195 register int i, j;
196 register unsigned *rowp;
197 register unsigned word;
198 register unsigned k;
199
200 printf("\n\nEpsilon Free Firsts\n");
201
202 for (i = start_symbol; i < nsyms; i++)
203 {
204 printf("\n%s", symbol_name[i]);
205 rowp = EFF + ((i - start_symbol) * WORDSIZE(nvars));
206 word = *rowp++;
207
208 k = BITS_PER_WORD;
209 for (j = 0; j < nvars; k++, j++)
210 {
211 if (k >= BITS_PER_WORD)
212 {
213 word = *rowp++;
214 k = 0;
215 }
216
217 if (word & (1 << k))
218 printf(" %s", symbol_name[start_symbol + j]);
219 }
220 }
221}
222
223
224print_first_derives()
225{
226 register int i;
227 register int j;
228 register unsigned *rp;
229 register unsigned cword;
230 register unsigned k;
231
232 printf("\n\n\nFirst Derives\n");
233
234 for (i = start_symbol; i < nsyms; i++)
235 {
236 printf("\n%s derives\n", symbol_name[i]);
237 rp = first_derives + i * WORDSIZE(nrules);
238 k = BITS_PER_WORD;
239 for (j = 0; j <= nrules; k++, j++)
240 {
241 if (k >= BITS_PER_WORD)
242 {
243 cword = *rp++;
244 k = 0;
245 }
246
247 if (cword & (1 << k))
248 printf(" %d\n", j);
249 }
250 }
251
252 fflush(stdout);
253}
254
255#endif
Note: See TracBrowser for help on using the repository browser.