Subversion Repositories tendra.SVN

Rev

Rev 2 | Show entire file | Ignore whitespace | Details | Blame | Last modification | View Log | RSS feed

Rev 2 Rev 7
Line -... Line 1...
-
 
1
/*
-
 
2
 * Copyright (c) 2002-2005 The TenDRA Project <http://www.tendra.org/>.
-
 
3
 * All rights reserved.
-
 
4
 *
-
 
5
 * Redistribution and use in source and binary forms, with or without
-
 
6
 * modification, are permitted provided that the following conditions are met:
-
 
7
 *
-
 
8
 * 1. Redistributions of source code must retain the above copyright notice,
-
 
9
 *    this list of conditions and the following disclaimer.
-
 
10
 * 2. Redistributions in binary form must reproduce the above copyright notice,
-
 
11
 *    this list of conditions and the following disclaimer in the documentation
-
 
12
 *    and/or other materials provided with the distribution.
-
 
13
 * 3. Neither the name of The TenDRA Project nor the names of its contributors
-
 
14
 *    may be used to endorse or promote products derived from this software
-
 
15
 *    without specific, prior written permission.
-
 
16
 *
-
 
17
 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS ``AS
-
 
18
 * IS'' AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO,
-
 
19
 * THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
-
 
20
 * PURPOSE ARE DISCLAIMED.  IN NO EVENT SHALL THE COPYRIGHT HOLDERS OR
-
 
21
 * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
-
 
22
 * EXEMPLARY OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
-
 
23
 * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS;
-
 
24
 * OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY,
-
 
25
 * WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR
-
 
26
 * OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF
-
 
27
 * ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
-
 
28
 *
-
 
29
 * $Id$
-
 
30
 */
1
/*
31
/*
2
    		 Crown Copyright (c) 1997
32
    		 Crown Copyright (c) 1997
3
    
33
 
4
    This TenDRA(r) Computer Program is subject to Copyright
34
    This TenDRA(r) Computer Program is subject to Copyright
5
    owned by the United Kingdom Secretary of State for Defence
35
    owned by the United Kingdom Secretary of State for Defence
6
    acting through the Defence Evaluation and Research Agency
36
    acting through the Defence Evaluation and Research Agency
7
    (DERA).  It is made available to Recipients with a
37
    (DERA).  It is made available to Recipients with a
8
    royalty-free licence for its use, reproduction, transfer
38
    royalty-free licence for its use, reproduction, transfer
9
    to other parties and amendment for any purpose not excluding
39
    to other parties and amendment for any purpose not excluding
10
    product development provided that any such use et cetera
40
    product development provided that any such use et cetera
11
    shall be deemed to be acceptance of the following conditions:-
41
    shall be deemed to be acceptance of the following conditions:-
12
    
42
 
13
        (1) Its Recipients shall ensure that this Notice is
43
        (1) Its Recipients shall ensure that this Notice is
14
        reproduced upon any copies or amended versions of it;
44
        reproduced upon any copies or amended versions of it;
15
    
45
 
16
        (2) Any amended version of it shall be clearly marked to
46
        (2) Any amended version of it shall be clearly marked to
17
        show both the nature of and the organisation responsible
47
        show both the nature of and the organisation responsible
18
        for the relevant amendment or amendments;
48
        for the relevant amendment or amendments;
19
    
49
 
20
        (3) Its onward transfer from a recipient to another
50
        (3) Its onward transfer from a recipient to another
21
        party shall be deemed to be that party's acceptance of
51
        party shall be deemed to be that party's acceptance of
22
        these conditions;
52
        these conditions;
23
    
53
 
24
        (4) DERA gives no warranty or assurance as to its
54
        (4) DERA gives no warranty or assurance as to its
25
        quality or suitability for any purpose and DERA accepts
55
        quality or suitability for any purpose and DERA accepts
26
        no liability whatsoever in relation to any use to which
56
        no liability whatsoever in relation to any use to which
27
        it may be put.
57
        it may be put.
28
*/
58
*/
29
 
59
 
30
 
60
 
31
/*** rule-check.c --- Checks for grammar validity.
61
/*** rule-check.c --- Checks for grammar validity.
32
 *
62
 *
33
 ** Author: Steve Folkes <smf@hermes.mod.uk>
63
 ** Author: Steve Folkes <smf@hermes.mod.uk>
34
 *
64
 *
35
 *** Commentary:
65
 *** Commentary:
Line 72... Line 102...
72
#include "basic.h"
102
#include "basic.h"
73
#include "bitvec.h"
103
#include "bitvec.h"
74
#include "gen-errors.h"
104
#include "gen-errors.h"
75
 
105
 
76
/*--------------------------------------------------------------------------*/
106
/*--------------------------------------------------------------------------*/
77
 
107
 
78
static void
108
static void
79
rule_check_first_set_1 PROTO_N ((rule, grammar))
109
rule_check_first_set_1(RuleP rule, GrammarP grammar)
80
		       PROTO_T (RuleP    rule X
-
 
81
				GrammarP grammar)
-
 
82
{
110
{
83
    BoolT         is_empty            = rule_has_empty_alt (rule);
111
    BoolT         is_empty            = rule_has_empty_alt(rule);
84
    BoolT         is_empty_mesg_shown = FALSE;
112
    BoolT         is_empty_mesg_shown = FALSE;
85
    BitVecT       test;
113
    BitVecT       test;
86
    EntryListT    predicate_list;
114
    EntryListT    predicate_list;
87
    AltP          alt;
115
    AltP          alt;
88
    BasicClosureT closure;
116
    BasicClosureT closure;
89
 
117
 
90
    closure.grammar = grammar;
118
    closure.grammar = grammar;
91
    bitvec_init (&test);
119
    bitvec_init(&test);
92
    entry_list_init (&predicate_list);
120
    entry_list_init(&predicate_list);
93
    for (alt = rule_alt_head (rule); alt; alt = alt_next (alt)) {
121
    for (alt = rule_alt_head(rule); alt; alt = alt_next(alt)) {
94
	ItemP item        = alt_item_head (alt);
122
	ItemP item        = alt_item_head(alt);
95
	ItemP initial     = item;
123
	ItemP initial     = item;
96
	BoolT see_through = TRUE;
124
	BoolT see_through = TRUE;
97
 
125
 
98
	for (; see_through && item; item = item_next (item)) {
126
	for (; see_through && item; item = item_next(item)) {
99
	    EntryP entry = item_entry (item);
127
	    EntryP entry = item_entry(item);
100
 
128
 
101
	    switch (item_type (item)) EXHAUSTIVE {
129
	    switch (item_type(item))EXHAUSTIVE {
102
	      case ET_PREDICATE:
130
	      case ET_PREDICATE:
103
		ASSERT (item == initial);
131
		ASSERT(item == initial);
104
		if (entry_list_contains (&predicate_list, entry)) {
132
		if (entry_list_contains(&predicate_list, entry)) {
105
		    E_predicate_collision (rule, entry_key (entry));
133
		    E_predicate_collision(rule, entry_key(entry));
106
		} else {
134
		} else {
107
		    entry_list_add (&predicate_list, entry);
135
		    entry_list_add(&predicate_list, entry);
108
		}
136
		}
109
		see_through = FALSE;
137
		see_through = FALSE;
110
		break;
138
		break;
111
	      case ET_ACTION:
139
	      case ET_ACTION:
112
	      case ET_RENAME:
140
	      case ET_RENAME:
113
		break;
141
		break;
114
	      case ET_BASIC: {
142
	      case ET_BASIC: {
115
		  unsigned terminal = basic_terminal (entry_get_basic (entry));
143
		  unsigned terminal = basic_terminal(entry_get_basic(entry));
116
 
144
 
117
		  see_through = FALSE;
145
		  see_through = FALSE;
118
		  if (bitvec_is_set (&test, terminal)) {
146
		  if (bitvec_is_set(&test, terminal)) {
119
		      BitVecT tmp;
147
		      BitVecT tmp;
120
 
148
 
121
		      bitvec_init (&tmp);
149
		      bitvec_init(&tmp);
122
		      bitvec_set (&tmp, terminal);
150
		      bitvec_set(&tmp, terminal);
123
		      bitvec_and (&tmp, &test);
151
		      bitvec_and(&tmp, &test);
124
		      closure.bitvec = &tmp;
152
		      closure.bitvec = &tmp;
125
		      E_first_set_collision (rule, &closure);
153
		      E_first_set_collision(rule, &closure);
126
		      bitvec_destroy (&tmp);
154
		      bitvec_destroy(&tmp);
127
		  } else {
155
		  } else {
128
		      bitvec_set (&test, terminal);
156
		      bitvec_set(&test, terminal);
129
		  }
157
		  }
130
	      }
158
	      }
131
		break;
159
		break;
132
	      case ET_RULE: {
160
	      case ET_RULE: {
133
		  RuleP      item_rule  = entry_get_rule (entry);
161
		  RuleP      item_rule  = entry_get_rule(entry);
134
		  EntryListP item_preds = rule_predicate_first (item_rule);
162
		  EntryListP item_preds = rule_predicate_first(item_rule);
135
		  EntryListT tmp_list;
163
		  EntryListT tmp_list;
136
		  BitVecP    bitvec;
164
		  BitVecP    bitvec;
137
 
165
 
138
		  entry_list_intersection (&tmp_list, &predicate_list,
166
		  entry_list_intersection(&tmp_list, &predicate_list,
139
					   item_preds);
167
					  item_preds);
140
		  if (!entry_list_is_empty (&tmp_list)) {
168
		  if (!entry_list_is_empty(&tmp_list)) {
141
		      E_predicate_list_collision (rule, &tmp_list);
169
		      E_predicate_list_collision(rule, &tmp_list);
142
		  }
170
		  }
143
		  entry_list_destroy (&tmp_list);
171
		  entry_list_destroy(&tmp_list);
144
		  entry_list_append (&predicate_list, item_preds);
172
		  entry_list_append(&predicate_list, item_preds);
145
		  bitvec      = rule_first_set (item_rule);
173
		  bitvec      = rule_first_set(item_rule);
146
		  see_through = rule_is_see_through (item_rule);
174
		  see_through = rule_is_see_through(item_rule);
147
		  if (bitvec_intersects (&test, bitvec)) {
175
		  if (bitvec_intersects(&test, bitvec)) {
148
		      BitVecT tmp;
176
		      BitVecT tmp;
149
 
177
 
150
		      bitvec_copy (&tmp, bitvec);
178
		      bitvec_copy(&tmp, bitvec);
151
		      bitvec_and (&tmp, &test);
179
		      bitvec_and(&tmp, &test);
152
		      closure.bitvec = &tmp;
180
		      closure.bitvec = &tmp;
153
		      E_first_set_collision (rule, &closure);
181
		      E_first_set_collision(rule, &closure);
154
		      bitvec_destroy (&tmp);
182
		      bitvec_destroy(&tmp);
155
		  } else {
183
		  } else {
156
		      bitvec_or (&test, bitvec);
184
		      bitvec_or(&test, bitvec);
157
		  }
185
		  }
158
	      }
186
	      }
159
		break;
187
		break;
160
	      case ET_NON_LOCAL:
188
	      case ET_NON_LOCAL:
161
	      case ET_TYPE:
189
	      case ET_TYPE:
162
	      case ET_NAME:
190
	      case ET_NAME:
163
		UNREACHED;
191
		UNREACHED;
164
	    }
192
	    }
165
	}
193
	}
166
	if (see_through) {
194
	if (see_through) {
167
	    if (is_empty) {
195
	    if (is_empty) {
168
		if (!is_empty_mesg_shown) {
196
		if (!is_empty_mesg_shown) {
169
		    E_multiple_see_through_alts (rule);
197
		    E_multiple_see_through_alts(rule);
170
		    is_empty_mesg_shown = TRUE;
198
		    is_empty_mesg_shown = TRUE;
171
		}
199
		}
172
	    } else {
200
	    } else {
173
		is_empty = TRUE;
201
		is_empty = TRUE;
174
	    }
202
	    }
175
	}
203
	}
176
    }
204
    }
177
    bitvec_destroy (&test);
205
    bitvec_destroy(&test);
178
}
206
}
179
 
207
 
180
static void			rule_compute_follow_set_1
208
static void rule_compute_follow_set_1(RuleP, GrammarP, BitVecP, EntryListP,
181
	PROTO_S ((RuleP, GrammarP, BitVecP, EntryListP, ClashListP));
209
				      ClashListP);
182
 
210
 
183
static void
211
static void
184
rule_compute_follow_set_3 PROTO_N ((grammar, item, context, pred_context,
212
rule_compute_follow_set_3(GrammarP grammar, ItemP item, BitVecP context,
185
				    clashes))
-
 
186
			  PROTO_T (GrammarP   grammar X
-
 
187
				   ItemP      item X
-
 
188
				   BitVecP    context X
-
 
189
				   EntryListP pred_context X
213
			  EntryListP pred_context, ClashListP clashes)
190
				   ClashListP clashes)
-
 
191
{
214
{
192
    if (item != NIL (ItemP)) {
215
    if (item != NIL(ItemP)) {
193
	EntryP entry;
216
	EntryP entry;
194
 
217
 
195
	rule_compute_follow_set_3 (grammar, item_next (item), context,
218
	rule_compute_follow_set_3(grammar, item_next(item), context,
196
				   pred_context, clashes);
219
				  pred_context, clashes);
197
	entry = item_entry (item);
220
	entry = item_entry(item);
198
	switch (item_type (item)) EXHAUSTIVE {
221
	switch (item_type(item))EXHAUSTIVE {
199
	  case ET_PREDICATE:
222
	  case ET_PREDICATE:
200
	    entry_list_destroy (pred_context);
223
	    entry_list_destroy(pred_context);
201
	    entry_list_init (pred_context);
224
	    entry_list_init(pred_context);
202
	    entry_list_add (pred_context, entry);
225
	    entry_list_add(pred_context, entry);
203
	    clashes->next = NIL (ClashListP);
226
	    clashes->next = NIL(ClashListP);
204
	    break;
227
	    break;
205
	  case ET_ACTION:
228
	  case ET_ACTION:
206
	  case ET_RENAME:
229
	  case ET_RENAME:
207
	    break;
230
	    break;
208
	  case ET_RULE: {
231
	  case ET_RULE: {
209
	      RuleP rule = entry_get_rule (entry);
232
	      RuleP rule = entry_get_rule(entry);
210
 
233
 
211
	      clashes->item = item;
234
	      clashes->item = item;
212
	      rule_compute_follow_set_1 (rule, grammar, context, pred_context,
235
	      rule_compute_follow_set_1(rule, grammar, context, pred_context,
213
					 clashes);
236
					clashes);
214
	      if (rule_is_see_through (rule)) {
237
	      if (rule_is_see_through(rule)) {
215
		  bitvec_or (context, rule_first_set (rule));
238
		  bitvec_or(context, rule_first_set(rule));
216
		  entry_list_append (pred_context,
239
		  entry_list_append(pred_context, rule_predicate_first(rule));
217
				     rule_predicate_first (rule));
-
 
218
	      } else {
240
	      } else {
219
		  bitvec_replace (context, rule_first_set (rule));
241
		  bitvec_replace(context, rule_first_set(rule));
220
		  entry_list_destroy (pred_context);
242
		  entry_list_destroy(pred_context);
221
		  entry_list_init (pred_context);
243
		  entry_list_init(pred_context);
222
		  entry_list_append (pred_context,
244
		  entry_list_append(pred_context, rule_predicate_first(rule));
223
				     rule_predicate_first (rule));
-
 
224
		  clashes->next = NIL (ClashListP);
245
		  clashes->next = NIL(ClashListP);
225
	      }
246
	      }
226
	  }
247
	  }
227
	    break;
248
	    break;
228
	  case ET_BASIC: {
249
	  case ET_BASIC: {
229
	      BasicP basic = entry_get_basic (entry);
250
	      BasicP basic = entry_get_basic(entry);
230
 
251
 
231
	      bitvec_empty (context);
252
	      bitvec_empty(context);
232
	      bitvec_set (context, basic_terminal (basic));
253
	      bitvec_set(context, basic_terminal(basic));
233
	      clashes->next = NIL (ClashListP);
254
	      clashes->next = NIL(ClashListP);
234
	  }
255
	  }
235
	    break;
256
	    break;
236
	  case ET_NON_LOCAL:
257
	  case ET_NON_LOCAL:
237
	  case ET_NAME:
258
	  case ET_NAME:
238
	  case ET_TYPE:
259
	  case ET_TYPE:
Line 240... Line 261...
240
	}
261
	}
241
    }
262
    }
242
}
263
}
243
 
264
 
244
static void
265
static void
245
rule_compute_follow_set_2 PROTO_N ((rule, grammar, alt, context, pred_context,
266
rule_compute_follow_set_2(RuleP rule, GrammarP grammar, AltP alt,
246
				    clashes))
-
 
247
			  PROTO_T (RuleP      rule X
-
 
248
				   GrammarP   grammar X
-
 
249
				   AltP       alt X
-
 
250
				   BitVecP    context X
-
 
251
				   EntryListP pred_context X
267
			  BitVecP context, EntryListP pred_context,
252
				   ClashListP clashes)
268
			  ClashListP clashes)
253
{
269
{
254
    BitVecT    tmp;
270
    BitVecT    tmp;
255
    EntryListT tmp_list;
271
    EntryListT tmp_list;
256
    ClashListT clash;
272
    ClashListT clash;
257
 
273
 
258
    clash.next = clashes;
274
    clash.next = clashes;
259
    clash.rule = rule;
275
    clash.rule = rule;
260
    clash.alt  = alt;
276
    clash.alt  = alt;
261
    bitvec_copy (&tmp, context);
277
    bitvec_copy(&tmp, context);
262
    entry_list_copy (&tmp_list, pred_context);
278
    entry_list_copy(&tmp_list, pred_context);
263
    rule_compute_follow_set_3 (grammar, alt_item_head (alt), &tmp, &tmp_list,
279
    rule_compute_follow_set_3(grammar, alt_item_head(alt), &tmp, &tmp_list,
264
			       &clash);
280
			      &clash);
265
    bitvec_destroy (&tmp);
281
    bitvec_destroy(&tmp);
266
    entry_list_destroy (&tmp_list);
282
    entry_list_destroy(&tmp_list);
267
}
283
}
268
 
284
 
269
static void
285
static void
270
rule_compute_follow_set_1 PROTO_N ((rule, grammar, context, pred_context,
286
rule_compute_follow_set_1(RuleP rule, GrammarP grammar, BitVecP context,
271
				    clashes))
-
 
272
			  PROTO_T (RuleP      rule X
-
 
273
				   GrammarP   grammar X
-
 
274
				   BitVecP    context X
-
 
275
				   EntryListP pred_context X
287
			  EntryListP pred_context, ClashListP clashes)
276
				   ClashListP clashes)
-
 
277
{
288
{
278
    BitVecP       follow      = rule_follow_set (rule);
289
    BitVecP       follow      = rule_follow_set(rule);
279
    EntryListP    pred_follow = rule_predicate_follow (rule);
290
    EntryListP    pred_follow = rule_predicate_follow(rule);
280
    BitVecP       first       = rule_first_set (rule);
291
    BitVecP       first       = rule_first_set(rule);
281
    EntryListP    pred_first  = rule_predicate_first (rule);
292
    EntryListP    pred_first  = rule_predicate_first(rule);
282
    BitVecT       test;
293
    BitVecT       test;
283
    AltP          alt;
294
    AltP          alt;
284
    BasicClosureT closure;
295
    BasicClosureT closure;
285
 
296
 
286
    if (rule_has_started_follows (rule)) {
297
    if (rule_has_started_follows(rule)) {
287
	bitvec_copy (&test, follow);
298
	bitvec_copy(&test, follow);
288
	bitvec_or (follow, context);
299
	bitvec_or(follow, context);
289
	if (bitvec_equal (&test, follow) &&
300
	if (bitvec_equal(&test, follow) &&
290
	    entry_list_includes (pred_follow, pred_context)) {
301
	    entry_list_includes(pred_follow, pred_context)) {
291
	    bitvec_destroy (&test);
302
	    bitvec_destroy(&test);
292
	    return;
303
	    return;
293
	}
304
	}
294
	entry_list_append (pred_follow, pred_context);
305
	entry_list_append(pred_follow, pred_context);
295
	bitvec_destroy (&test);
306
	bitvec_destroy(&test);
296
    } else {
307
    } else {
297
	bitvec_replace (follow, context);
308
	bitvec_replace(follow, context);
298
	entry_list_append (pred_follow, pred_context);
309
	entry_list_append(pred_follow, pred_context);
299
	rule_started_follows (rule);
310
	rule_started_follows(rule);
300
    }
311
    }
301
    closure.grammar = grammar;
312
    closure.grammar = grammar;
302
    if (rule_is_see_through (rule)) {
313
    if (rule_is_see_through(rule)) {
303
	EntryListT tmp_list;
314
	EntryListT tmp_list;
304
 
315
 
305
	if (bitvec_intersects (follow, first)) {
316
	if (bitvec_intersects(follow, first)) {
306
	    bitvec_copy (&test, follow);
317
	    bitvec_copy(&test, follow);
307
	    bitvec_and (&test, first);
318
	    bitvec_and(&test, first);
308
	    closure.bitvec = &test;
319
	    closure.bitvec = &test;
309
	    E_follow_set_collision (rule, &closure, clashes);
320
	    E_follow_set_collision(rule, &closure, clashes);
310
	    bitvec_not (&test);
321
	    bitvec_not(&test);
311
	    bitvec_and (first, &test);
322
	    bitvec_and(first, &test);
312
	    bitvec_destroy (&test);
323
	    bitvec_destroy(&test);
313
	}
324
	}
314
	entry_list_intersection (&tmp_list, pred_follow, pred_first);
325
	entry_list_intersection(&tmp_list, pred_follow, pred_first);
315
	if (!entry_list_is_empty (&tmp_list)) {
326
	if (!entry_list_is_empty(&tmp_list)) {
316
	    E_predicate_follow_set_coll (rule, &tmp_list, clashes);
327
	    E_predicate_follow_set_coll(rule, &tmp_list, clashes);
317
	    entry_list_unlink_used (pred_first, &tmp_list);
328
	    entry_list_unlink_used(pred_first, &tmp_list);
318
	}
329
	}
319
	entry_list_destroy (&tmp_list);
330
	entry_list_destroy(&tmp_list);
320
    }
331
    }
321
    if ((alt = rule_get_handler (rule)) != NIL (AltP)) {
332
    if ((alt = rule_get_handler(rule)) != NIL(AltP)) {
322
	rule_compute_follow_set_2 (rule, grammar, alt, follow, pred_follow,
333
	rule_compute_follow_set_2(rule, grammar, alt, follow, pred_follow,
323
				   clashes);
334
				   clashes);
324
    }
335
    }
325
    for (alt = rule_alt_head (rule); alt; alt = alt_next (alt)) {
336
    for (alt = rule_alt_head(rule); alt; alt = alt_next(alt)) {
326
	rule_compute_follow_set_2 (rule, grammar, alt, follow, pred_follow,
337
	rule_compute_follow_set_2(rule, grammar, alt, follow, pred_follow,
327
				   clashes);
338
				  clashes);
328
    }
339
    }
329
}
340
}
330
 
341
 
331
static void
342
static void
332
rule_compute_see_through_alt_1 PROTO_N ((rule))
343
rule_compute_see_through_alt_1(RuleP rule)
333
			       PROTO_T (RuleP rule)
-
 
334
{
344
{
335
    if (!rule_has_empty_alt (rule)) {
345
    if (!rule_has_empty_alt(rule)) {
336
	AltP alt;
346
	AltP alt;
337
 
347
 
338
	for (alt = rule_alt_head (rule); alt; alt = alt_next (alt)) {
348
	for (alt = rule_alt_head(rule); alt; alt = alt_next(alt)) {
339
	    ItemP item;
349
	    ItemP item;
340
 
350
 
341
	    for (item = alt_item_head (alt); item; item = item_next (item)) {
351
	    for (item = alt_item_head(alt); item; item = item_next(item)) {
342
		RuleP item_rule;
352
		RuleP item_rule;
343
 
353
 
344
		if ((!item_is_action (item)) && (!item_is_rename (item)) &&
354
		if ((!item_is_action(item)) && (!item_is_rename(item)) &&
345
		    ((!item_is_rule (item)) ||
355
		    ((!item_is_rule(item)) ||
346
		     ((item_rule = entry_get_rule (item_entry (item))),
356
		     ((item_rule = entry_get_rule(item_entry(item))),
347
		      (!rule_is_see_through (item_rule))))) {
357
		      (!rule_is_see_through(item_rule))))) {
348
		    goto next_alt;
358
		    goto next_alt;
349
		}
359
		}
350
	    }
360
	    }
351
	    rule_set_see_through_alt (rule, alt);
361
	    rule_set_see_through_alt(rule, alt);
352
	    return;
362
	    return;
353
	  next_alt:;
363
	  next_alt:;
354
	}
364
	}
355
    }
365
    }
356
}
366
}
357
 
367
 
358
static void
368
static void
359
rule_compute_alt_first_sets_1 PROTO_N ((rule))
369
rule_compute_alt_first_sets_1(RuleP rule)
360
			      PROTO_T (RuleP rule)
-
 
361
{
370
{
362
    AltP alt;
371
    AltP alt;
363
 
372
 
364
    for (alt = rule_alt_head (rule); alt; alt = alt_next (alt)) {
373
    for (alt = rule_alt_head(rule); alt; alt = alt_next(alt)) {
365
	BitVecP alt_firsts  = alt_first_set (alt);
374
	BitVecP alt_firsts  = alt_first_set(alt);
366
	ItemP   item        = alt_item_head (alt);
375
	ItemP   item        = alt_item_head(alt);
367
	ItemP   initial     = item;
376
	ItemP   initial     = item;
368
	BoolT   see_through = TRUE;
377
	BoolT   see_through = TRUE;
369
 
378
 
370
	for (; see_through && item; item = item_next (item)) {
379
	for (; see_through && item; item = item_next(item)) {
371
	    EntryP entry = item_entry (item);
380
	    EntryP entry = item_entry(item);
372
 
381
 
373
	    switch (item_type (item)) EXHAUSTIVE {
382
	    switch (item_type(item))EXHAUSTIVE {
374
	      case ET_PREDICATE:
383
	      case ET_PREDICATE:
375
		ASSERT (item == initial);
384
		ASSERT(item == initial);
376
		see_through = FALSE;
385
		see_through = FALSE;
377
		break;
386
		break;
378
	      case ET_ACTION:
387
	      case ET_ACTION:
379
	      case ET_RENAME:
388
	      case ET_RENAME:
380
		break;
389
		break;
381
	      case ET_BASIC:
390
	      case ET_BASIC:
382
		see_through = FALSE;
391
		see_through = FALSE;
383
		bitvec_set (alt_firsts,
-
 
384
			    basic_terminal (entry_get_basic (entry)));
392
		bitvec_set(alt_firsts, basic_terminal(entry_get_basic(entry)));
385
		break;
393
		break;
386
	      case ET_RULE: {
394
	      case ET_RULE: {
387
		  RuleP item_rule = entry_get_rule (entry);
395
		  RuleP item_rule = entry_get_rule(entry);
388
 
396
 
389
		  see_through = rule_is_see_through (item_rule);
397
		  see_through = rule_is_see_through(item_rule);
390
		  bitvec_or (alt_firsts, rule_first_set (item_rule));
398
		  bitvec_or(alt_firsts, rule_first_set(item_rule));
391
	      }
399
	      }
392
		break;
400
		break;
393
	      case ET_NON_LOCAL:
401
	      case ET_NON_LOCAL:
394
	      case ET_TYPE:
402
	      case ET_TYPE:
395
	      case ET_NAME:
403
	      case ET_NAME:
396
		UNREACHED;
404
		UNREACHED;
397
	    }
405
	    }
398
	}
406
	}
399
	if (see_through) {
407
	if (see_through) {
400
	    bitvec_or (alt_firsts, rule_follow_set (rule));
408
	    bitvec_or(alt_firsts, rule_follow_set(rule));
401
	}
409
	}
402
    }
410
    }
403
}
411
}
404
 
412
 
405
/*--------------------------------------------------------------------------*/
413
/*--------------------------------------------------------------------------*/
406
 
414
 
407
void
415
void
408
rule_check_first_set PROTO_N ((entry, gclosure))
416
rule_check_first_set(EntryP entry, GenericP gclosure)
409
		     PROTO_T (EntryP   entry X
-
 
410
			      GenericP gclosure)
-
 
411
{
417
{
412
    GrammarP grammar = (GrammarP) gclosure;
418
    GrammarP grammar = (GrammarP)gclosure;
413
 
419
 
414
    if (entry_is_rule (entry)) {
420
    if (entry_is_rule(entry)) {
415
	RuleP rule = entry_get_rule (entry);
421
	RuleP rule = entry_get_rule(entry);
416
 
422
 
417
	rule_check_first_set_1 (rule, grammar);
423
	rule_check_first_set_1(rule, grammar);
418
    }
424
    }
419
}
425
}
420
 
426
 
421
void
427
void
422
rule_compute_follow_set PROTO_N ((entry, gclosure))
428
rule_compute_follow_set(EntryP entry, GenericP gclosure)
423
			PROTO_T (EntryP   entry X
-
 
424
				 GenericP gclosure)
-
 
425
{
429
{
426
    GrammarP grammar = (GrammarP) gclosure;
430
    GrammarP grammar = (GrammarP)gclosure;
427
 
431
 
428
    if (entry_is_rule (entry)) {
432
    if (entry_is_rule(entry)) {
429
	RuleP   rule = entry_get_rule (entry);
433
	RuleP   rule = entry_get_rule(entry);
430
	BitVecT    outer;
434
	BitVecT    outer;
431
	EntryListT pred_outer;
435
	EntryListT pred_outer;
432
 
436
 
433
	bitvec_init (&outer);
437
	bitvec_init(&outer);
434
	entry_list_init (&pred_outer);
438
	entry_list_init(&pred_outer);
435
	rule_compute_follow_set_1 (rule, grammar, &outer, &pred_outer,
439
	rule_compute_follow_set_1(rule, grammar, &outer, &pred_outer,
436
				   NIL (ClashListP));
440
				  NIL(ClashListP));
437
	bitvec_destroy (&outer);
441
	bitvec_destroy(&outer);
438
	entry_list_destroy (&pred_outer);
442
	entry_list_destroy(&pred_outer);
439
    }
443
    }
440
}
444
}
441
 
445
 
442
void
446
void
443
rule_compute_see_through_alt PROTO_N ((entry, gclosure))
447
rule_compute_see_through_alt(EntryP entry, GenericP gclosure)
444
			     PROTO_T (EntryP   entry X
-
 
445
				      GenericP gclosure)
-
 
446
{
448
{
447
    UNUSED (gclosure);
449
    UNUSED(gclosure);
448
    if (entry_is_rule (entry)) {
450
    if (entry_is_rule(entry)) {
449
	RuleP rule = entry_get_rule (entry);
451
	RuleP rule = entry_get_rule(entry);
450
 
452
 
451
	rule_compute_see_through_alt_1 (rule);
453
	rule_compute_see_through_alt_1(rule);
452
    }
454
    }
453
}
455
}
454
 
456
 
455
void
457
void
456
rule_compute_alt_first_sets PROTO_N ((entry, gclosure))
458
rule_compute_alt_first_sets(EntryP entry, GenericP gclosure)
457
			    PROTO_T (EntryP   entry X
-
 
458
				     GenericP gclosure)
-
 
459
{
459
{
460
    UNUSED (gclosure);
460
    UNUSED(gclosure);
461
    if (entry_is_rule (entry)) {
461
    if (entry_is_rule(entry)) {
462
	RuleP rule = entry_get_rule (entry);
462
	RuleP rule = entry_get_rule(entry);
463
 
463
 
464
	rule_compute_alt_first_sets_1 (rule);
464
	rule_compute_alt_first_sets_1(rule);
465
    }
465
    }
466
}
466
}
467
 
467
 
468
void
468
void
469
write_clashes PROTO_N ((ostream, clashes))
469
write_clashes(OStreamP ostream, ClashListP clashes)
470
	      PROTO_T (OStreamP   ostream X
-
 
471
		       ClashListP clashes)
-
 
472
{
470
{
473
    write_newline (ostream);
471
    write_newline(ostream);
474
    while (clashes) {
472
    while (clashes) {
475
	write_rule_lhs (ostream, clashes->rule);
473
	write_rule_lhs(ostream, clashes->rule);
476
	write_alt_highlighting (ostream, clashes->alt, clashes->item);
474
	write_alt_highlighting(ostream, clashes->alt, clashes->item);
477
	write_cstring (ostream, "};");
475
	write_cstring(ostream, "};");
478
	write_newline (ostream);
476
	write_newline(ostream);
479
	clashes = clashes->next;
477
	clashes = clashes->next;
480
    }
478
    }
481
}
479
}
482

480

483
/*
481
/*