1 /* $OpenBSD: closure.c,v 1.15 2017/05/25 20:11:03 tedu Exp $ */
2 /* $NetBSD: closure.c,v 1.4 1996/03/19 03:21:29 jtc Exp $ */
5 * Copyright (c) 1989 The Regents of the University of California.
8 * This code is derived from software contributed to Berkeley by
11 * Redistribution and use in source and binary forms, with or without
12 * modification, are permitted provided that the following conditions
14 * 1. Redistributions of source code must retain the above copyright
15 * notice, this list of conditions and the following disclaimer.
16 * 2. Redistributions in binary form must reproduce the above copyright
17 * notice, this list of conditions and the following disclaimer in the
18 * documentation and/or other materials provided with the distribution.
19 * 3. Neither the name of the University nor the names of its contributors
20 * may be used to endorse or promote products derived from this software
21 * without specific prior written permission.
23 * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
24 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
25 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
26 * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
27 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
28 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
29 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
30 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
31 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
32 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
42 static unsigned *first_derives
;
53 printf("\n\nn = %d\n\n", n
);
54 for (isp
= itemset
; isp
< itemsetend
; isp
++)
55 printf(" %d\n", *isp
);
65 printf("\n\nEpsilon Free Firsts\n");
67 for (i
= start_symbol
; i
< nsyms
; i
++) {
68 printf("\n%s", symbol_name
[i
]);
69 rowp
= EFF
+ ((i
- start_symbol
) * WORDSIZE(nvars
));
73 for (j
= 0; j
< nvars
; k
++, j
++) {
74 if (k
>= BITS_PER_WORD
) {
80 printf(" %s", symbol_name
[start_symbol
+ j
]);
86 print_first_derives(void)
90 unsigned int k
, cword
= 0;
92 printf("\n\n\nFirst Derives\n");
94 for (i
= start_symbol
; i
< nsyms
; i
++) {
95 printf("\n%s derives\n", symbol_name
[i
]);
96 rp
= first_derives
+ i
* WORDSIZE(nrules
);
98 for (j
= 0; j
<= nrules
; k
++, j
++) {
99 if (k
>= BITS_PER_WORD
) {
104 if (cword
& (1 << k
))
119 int symbol
, rowsize
, i
, rule
;
122 rowsize
= WORDSIZE(nvars
);
123 EFF
= NEW2(nvars
* rowsize
, unsigned);
126 for (i
= start_symbol
; i
< nsyms
; i
++) {
128 for (rule
= *sp
; rule
> 0; rule
= *++sp
) {
129 symbol
= ritem
[rrhs
[rule
]];
131 symbol
-= start_symbol
;
138 reflexive_transitive_closure(EFF
, nvars
);
147 set_first_derives(void)
149 unsigned int *rrow
, *vrow
;
150 unsigned int k
, cword
= 0;
151 int i
, j
, rule
, rulesetsize
, varsetsize
;
154 rulesetsize
= WORDSIZE(nrules
);
155 varsetsize
= WORDSIZE(nvars
);
156 first_derives
= NEW2(nvars
* rulesetsize
, unsigned) - ntokens
* rulesetsize
;
160 rrow
= first_derives
+ ntokens
* rulesetsize
;
161 for (i
= start_symbol
; i
< nsyms
; i
++) {
162 vrow
= EFF
+ ((i
- ntokens
) * varsetsize
);
164 for (j
= start_symbol
; j
< nsyms
; k
++, j
++) {
165 if (k
>= BITS_PER_WORD
) {
170 if (cword
& (1 << k
)) {
172 while ((rule
= *rp
++) >= 0) {
181 print_first_derives();
189 closure(short *nucleus
, int n
)
191 unsigned int i
, word
;
193 unsigned int *dsp
, *rsp
, *rsend
;
195 int ruleno
, symbol
, itemno
;
197 rulesetsize
= WORDSIZE(nrules
);
198 rsend
= ruleset
+ rulesetsize
;
199 memset(ruleset
, 0, rulesetsize
* sizeof(*ruleset
));
202 for (csp
= nucleus
; csp
< csend
; ++csp
) {
203 symbol
= ritem
[*csp
];
205 dsp
= first_derives
+ symbol
* rulesetsize
;
213 itemsetend
= itemset
;
215 for (rsp
= ruleset
; rsp
< rsend
; ++rsp
) {
218 for (i
= 0; i
< BITS_PER_WORD
; ++i
) {
219 if (word
& (1 << i
)) {
220 itemno
= rrhs
[ruleno
+i
];
221 while (csp
< csend
&& *csp
< itemno
)
222 *itemsetend
++ = *csp
++;
223 *itemsetend
++ = itemno
;
224 while (csp
< csend
&& *csp
== itemno
)
229 ruleno
+= BITS_PER_WORD
;
233 *itemsetend
++ = *csp
++;
243 finalize_closure(void)
247 free(first_derives
+ ntokens
* WORDSIZE(nrules
));