2 * Copyright (c) 1989 The Regents of the University of California.
5 * This code is derived from software contributed to Berkeley by
8 * Redistribution and use in source and binary forms, with or without
9 * modification, are permitted provided that the following conditions
11 * 1. Redistributions of source code must retain the above copyright
12 * notice, this list of conditions and the following disclaimer.
13 * 2. Redistributions in binary form must reproduce the above copyright
14 * notice, this list of conditions and the following disclaimer in the
15 * documentation and/or other materials provided with the distribution.
16 * 3. All advertising materials mentioning features or use of this software
17 * must display the following acknowledgement:
18 * This product includes software developed by the University of
19 * California, Berkeley and its contributors.
20 * 4. Neither the name of the University nor the names of its contributors
21 * may be used to endorse or promote products derived from this software
22 * without specific prior written permission.
24 * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
25 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
26 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
27 * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
28 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
29 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
30 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
31 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
32 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
33 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
38 static char sccsid
[] = "@(#)closure.c 5.3 (Berkeley) 5/24/93";
47 static unsigned *first_derives
;
51 print_first_derives (void);
54 print_closure (int n
);
62 register unsigned *row
;
69 rowsize
= WORDSIZE(nvars
);
70 EFF
= NEW2(nvars
* rowsize
, unsigned);
73 for (i
= start_symbol
; i
< nsyms
; i
++)
76 for (rule
= *sp
; rule
> 0; rule
= *++sp
)
78 symbol
= ritem
[rrhs
[rule
]];
81 symbol
-= start_symbol
;
88 reflexive_transitive_closure(EFF
, nvars
);
96 set_first_derives (void)
98 register unsigned *rrow
;
99 register unsigned *vrow
;
102 register unsigned cword
;
110 rulesetsize
= WORDSIZE(nrules
);
111 varsetsize
= WORDSIZE(nvars
);
112 first_derives
= NEW2(nvars
* rulesetsize
, unsigned) - ntokens
* rulesetsize
;
116 rrow
= first_derives
+ ntokens
* rulesetsize
;
117 for (i
= start_symbol
; i
< nsyms
; i
++)
119 vrow
= EFF
+ ((i
- ntokens
) * varsetsize
);
121 for (j
= start_symbol
; j
< nsyms
; k
++, j
++)
123 if (k
>= BITS_PER_WORD
)
129 if (cword
& (1 << k
))
132 while ((rule
= *rp
++) >= 0)
144 print_first_derives();
151 closure (short *nucleus
, int n
)
154 register unsigned word
;
157 register unsigned *dsp
;
158 register unsigned *rsp
;
159 register int rulesetsize
;
166 rulesetsize
= WORDSIZE(nrules
);
168 rsend
= ruleset
+ rulesetsize
;
169 for (rsp
= ruleset
; rsp
< rsend
; rsp
++)
173 for (csp
= nucleus
; csp
< csend
; ++csp
)
175 symbol
= ritem
[*csp
];
178 dsp
= first_derives
+ symbol
* rulesetsize
;
186 itemsetend
= itemset
;
188 for (rsp
= ruleset
; rsp
< rsend
; ++rsp
)
193 for (i
= 0; i
< BITS_PER_WORD
; ++i
)
197 itemno
= rrhs
[ruleno
+i
];
198 while (csp
< csend
&& *csp
< itemno
)
199 *itemsetend
++ = *csp
++;
200 *itemsetend
++ = itemno
;
201 while (csp
< csend
&& *csp
== itemno
)
206 ruleno
+= BITS_PER_WORD
;
210 *itemsetend
++ = *csp
++;
218 finalize_closure (void)
222 FREE(first_derives
+ ntokens
* WORDSIZE(nrules
));
228 print_closure (int n
)
232 printf("\n\nn = %d\n\n", n
);
233 for (isp
= itemset
; isp
< itemsetend
; isp
++)
234 printf(" %d\n", *isp
);
241 register unsigned *rowp
;
242 register unsigned word
;
245 printf("\n\nEpsilon Free Firsts\n");
247 for (i
= start_symbol
; i
< nsyms
; i
++)
249 printf("\n%s", symbol_name
[i
]);
250 rowp
= EFF
+ ((i
- start_symbol
) * WORDSIZE(nvars
));
254 for (j
= 0; j
< nvars
; k
++, j
++)
256 if (k
>= BITS_PER_WORD
)
263 printf(" %s", symbol_name
[start_symbol
+ j
]);
269 print_first_derives (void)
273 register unsigned *rp
;
274 register unsigned cword
;
277 printf("\n\n\nFirst Derives\n");
279 for (i
= start_symbol
; i
< nsyms
; i
++)
281 printf("\n%s derives\n", symbol_name
[i
]);
282 rp
= first_derives
+ i
* WORDSIZE(nrules
);
284 for (j
= 0; j
<= nrules
; k
++, j
++)
286 if (k
>= BITS_PER_WORD
)
292 if (cword
& (1 << k
))