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