![[BACK]](/cvsweb/icons/back.gif){kind=icon}
Return to closure.c CVS log ![[TXT]](/cvsweb/icons/text.gif){kind=icon}
![[DIR]](/cvsweb/icons/dir.gif){kind=icon}
Up to [Apple XNU] / GNUtools / bison|
Return to closure.c CVS log | Up to [Apple XNU] / GNUtools / bison |
1.1 root 1: /* Subroutines for bison
2: Copyright (C) 1984, 1989 Free Software Foundation, Inc.
3:
4: This file is part of Bison, the GNU Compiler Compiler.
5:
6: Bison is free software; you can redistribute it and/or modify
7: it under the terms of the GNU General Public License as published by
8: the Free Software Foundation; either version 2, or (at your option)
9: any later version.
10:
11: Bison is distributed in the hope that it will be useful,
12: but WITHOUT ANY WARRANTY; without even the implied warranty of
13: MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
14: GNU General Public License for more details.
15:
16: You should have received a copy of the GNU General Public License
17: along with Bison; see the file COPYING. If not, write to
18: the Free Software Foundation, 675 Mass Ave, Cambridge, MA 02139, USA. */
19:
20:
21: /* subroutines of file LR0.c.
22:
23: Entry points:
24:
25: closure (items, n)
26:
27: Given a vector of item numbers items, of length n,
28: set up ruleset and itemset to indicate what rules could be run
29: and which items could be accepted when those items are the active ones.
30:
31: ruleset contains a bit for each rule. closure sets the bits
32: for all rules which could potentially describe the next input to be read.
33:
34: itemset is a vector of item numbers; itemsetend points to just beyond the end
35: of the part of it that is significant.
36: closure places there the indices of all items which represent units of
37: input that could arrive next.
38:
39: initialize_closure (n)
40:
41: Allocates the itemset and ruleset vectors,
42: and precomputes useful data so that closure can be called.
43: n is the number of elements to allocate for itemset.
44:
45: finalize_closure ()
46:
47: Frees itemset, ruleset and internal data.
48:
49: */
50:
51: #include <stdio.h>
52: #include "system.h"
53: #include "machine.h"
54: #include "new.h"
55: #include "gram.h"
56:
57:
58: extern short **derives;
59: extern char **tags;
60:
61: void set_fderives();
62: void set_firsts();
63:
64: extern void RTC();
65:
66: short *itemset;
67: short *itemsetend;
68: static unsigned *ruleset;
69:
70: /* internal data. See comments before set_fderives and set_firsts. */
71: static unsigned *fderives;
72: static unsigned *firsts;
73:
74: /* number of words required to hold a bit for each rule */
75: static int rulesetsize;
76:
77: /* number of words required to hold a bit for each variable */
78: static int varsetsize;
79:
80:
81: void
82: initialize_closure(n)
83: int n;
84: {
85: itemset = NEW2(n, short);
86:
87: rulesetsize = WORDSIZE(nrules + 1);
88: ruleset = NEW2(rulesetsize, unsigned);
89:
90: set_fderives();
91: }
92:
93:
94:
95: /* set fderives to an nvars by nrules matrix of bits
96: indicating which rules can help derive the beginning of the data
97: for each nonterminal. For example, if symbol 5 can be derived as
98: the sequence of symbols 8 3 20, and one of the rules for deriving
99: symbol 8 is rule 4, then the [5 - ntokens, 4] bit in fderives is set. */
100: void
101: set_fderives()
102: {
103: register unsigned *rrow;
104: register unsigned *vrow;
105: register int j;
106: register unsigned cword;
107: register short *rp;
108: register int b;
109:
110: int ruleno;
111: int i;
112:
113: fderives = NEW2(nvars * rulesetsize, unsigned) - ntokens * rulesetsize;
114:
115: set_firsts();
116:
117: rrow = fderives + ntokens * rulesetsize;
118:
119: for (i = ntokens; i < nsyms; i++)
120: {
121: vrow = firsts + ((i - ntokens) * varsetsize);
122: cword = *vrow++;
123: b = 0;
124: for (j = ntokens; j < nsyms; j++)
125: {
126: if (cword & (1 << b))
127: {
128: rp = derives[j];
129: while ((ruleno = *rp++) > 0)
130: {
131: SETBIT(rrow, ruleno);
132: }
133: }
134:
135: b++;
136: if (b >= BITS_PER_WORD && j + 1 < nsyms)
137: {
138: cword = *vrow++;
139: b = 0;
140: }
141: }
142:
143: rrow += rulesetsize;
144: }
145:
146: #ifdef DEBUG
147: print_fderives();
148: #endif
149:
150: FREE(firsts);
151: }
152:
153:
154:
155: /* set firsts to be an nvars by nvars bit matrix indicating which items
156: can represent the beginning of the input corresponding to which other items.
157: For example, if some rule expands symbol 5 into the sequence of symbols 8 3 20,
158: the symbol 8 can be the beginning of the data for symbol 5,
159: so the bit [8 - ntokens, 5 - ntokens] in firsts is set. */
160: void
161: set_firsts()
162: {
163: register unsigned *row;
164: /* register int done; JF unused */
165: register int symbol;
166: register short *sp;
167: register int rowsize;
168:
169: int i;
170:
171: varsetsize = rowsize = WORDSIZE(nvars);
172:
173: firsts = NEW2(nvars * rowsize, unsigned);
174:
175: row = firsts;
176: for (i = ntokens; i < nsyms; i++)
177: {
178: sp = derives[i];
179: while (*sp >= 0)
180: {
181: symbol = ritem[rrhs[*sp++]];
182: if (ISVAR(symbol))
183: {
184: symbol -= ntokens;
185: SETBIT(row, symbol);
186: }
187: }
188:
189: row += rowsize;
190: }
191:
192: RTC(firsts, nvars);
193:
194: #ifdef DEBUG
195: print_firsts();
196: #endif
197: }
198:
199:
200: void
201: closure(core, n)
202: short *core;
203: int n;
204: {
205: register int ruleno;
206: register unsigned word;
207: register short *csp;
208: register unsigned *dsp;
209: register unsigned *rsp;
210:
211: short *csend;
212: unsigned *rsend;
213: int symbol;
214: int itemno;
215:
216: rsp = ruleset;
217: rsend = ruleset + rulesetsize;
218: csend = core + n;
219:
220: if (n == 0)
221: {
222: dsp = fderives + start_symbol * rulesetsize;
223: while (rsp < rsend)
224: *rsp++ = *dsp++;
225: }
226: else
227: {
228: while (rsp < rsend)
229: *rsp++ = 0;
230:
231: csp = core;
232: while (csp < csend)
233: {
234: symbol = ritem[*csp++];
235: if (ISVAR(symbol))
236: {
237: dsp = fderives + symbol * rulesetsize;
238: rsp = ruleset;
239: while (rsp < rsend)
240: *rsp++ |= *dsp++;
241: }
242: }
243: }
244:
245: ruleno = 0;
246: itemsetend = itemset;
247: csp = core;
248: rsp = ruleset;
249: while (rsp < rsend)
250: {
251: word = *rsp++;
252: if (word == 0)
253: {
254: ruleno += BITS_PER_WORD;
255: }
256: else
257: {
258: register int b;
259:
260: for (b = 0; b < BITS_PER_WORD; b++)
261: {
262: if (word & (1 << b))
263: {
264: itemno = rrhs[ruleno];
265: while (csp < csend && *csp < itemno)
266: *itemsetend++ = *csp++;
267: *itemsetend++ = itemno;
268: }
269:
270: ruleno++;
271: }
272: }
273: }
274:
275: while (csp < csend)
276: *itemsetend++ = *csp++;
277:
278: #ifdef DEBUG
279: print_closure(n);
280: #endif
281: }
282:
283:
284: void
285: finalize_closure()
286: {
287: FREE(itemset);
288: FREE(ruleset);
289: FREE(fderives + ntokens * rulesetsize);
290: }
291:
292:
293:
294: #ifdef DEBUG
295:
296: print_closure(n)
297: int n;
298: {
299: register short *isp;
300:
301: printf("\n\nn = %d\n\n", n);
302: for (isp = itemset; isp < itemsetend; isp++)
303: printf(" %d\n", *isp);
304: }
305:
306:
307:
308: print_firsts()
309: {
310: register int i;
311: register int j;
312: register unsigned *rowp;
313:
314: printf("\n\n\nFIRSTS\n\n");
315:
316: for (i = ntokens; i < nsyms; i++)
317: {
318: printf("\n\n%s firsts\n\n", tags[i]);
319:
320: rowp = firsts + ((i - ntokens) * varsetsize);
321:
322: for (j = 0; j < nvars; j++)
323: if (BITISSET (rowp, j))
324: printf(" %s\n", tags[j + ntokens]);
325: }
326: }
327:
328:
329:
330: print_fderives()
331: {
332: register int i;
333: register int j;
334: register unsigned *rp;
335:
336: printf("\n\n\nFDERIVES\n");
337:
338: for (i = ntokens; i < nsyms; i++)
339: {
340: printf("\n\n%s derives\n\n", tags[i]);
341: rp = fderives + i * rulesetsize;
342:
343: for (j = 0; j <= nrules; j++)
344: if (BITISSET (rp, j))
345: printf(" %d\n", j);
346: }
347:
348: fflush(stdout);
349: }
350:
351: #endif
This archive runs on limited infrastructure. Preserving old code on modern bandwidth. Automated agents are requested to crawl responsibly.