Subversion Repositories tendra.SVN

Rev

Rev 5 | Details | Compare with Previous | Last modification | View Log | RSS feed

Rev Author Line No. Line
2 7u83 1 
/*
6 7u83 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 
 */
31 
/*
2 7u83 32 
    		 Crown Copyright (c) 1997
6 7u83 33 
 
2 7u83 34 
    This TenDRA(r) Computer Program is subject to Copyright
35 
    owned by the United Kingdom Secretary of State for Defence
36 
    acting through the Defence Evaluation and Research Agency
37 
    (DERA).  It is made available to Recipients with a
38 
    royalty-free licence for its use, reproduction, transfer
39 
    to other parties and amendment for any purpose not excluding
40 
    product development provided that any such use et cetera
41 
    shall be deemed to be acceptance of the following conditions:-
6 7u83 42 
 
2 7u83 43 
        (1) Its Recipients shall ensure that this Notice is
44 
        reproduced upon any copies or amended versions of it;
6 7u83 45 
 
2 7u83 46 
        (2) Any amended version of it shall be clearly marked to
47 
        show both the nature of and the organisation responsible
48 
        for the relevant amendment or amendments;
6 7u83 49 
 
2 7u83 50 
        (3) Its onward transfer from a recipient to another
51 
        party shall be deemed to be that party's acceptance of
52 
        these conditions;
6 7u83 53 
 
2 7u83 54 
        (4) DERA gives no warranty or assurance as to its
55 
        quality or suitability for any purpose and DERA accepts
56 
        no liability whatsoever in relation to any use to which
57 
        it may be put.
58 
*/
59 
 
60 
 
61 
/*** rule-firsts.c --- Computation of rule first sets.
62 
 *
63 
 ** Author: Steve Folkes <smf@hermes.mod.uk>
64 
 *
65 
 *** Commentary:
66 
 *
67 
 * This file implements the SID first set calculation routines.
68 
 *
69 
 * The first set of a rule is the set of all terminals that may start that
70 
 * rule.  As well as computing the first set of a rule, its priority and
71 
 * whether or not it is see through are also computed.  A rule is see through
72 
 * if there is an expansion of the rule that does not involve a basic or
73 
 * predicate.  The priority is used during the factorisation phase to work out
74 
 * which rules to expand.  The rule's priority is one more than the priority
75 
 * of the rule with the highest priority in any of the rule's alternatives
76 
 * that is not preceded by an action.  If there is no such rule, then the
77 
 * rule's priority is one.
78 
 *
79 
 * As well as computing the first sets, these routines check that there are no
80 
 * recursive calls that are not preceded by a basic or predicate.  They also
81 
 * check that predicates are either the first item in an alternative, or are
82 
 * preceded by a basic (or another predicate).  The same check is also made
83 
 * for rules that start with a predicate.
84 
 *
85 
 *** Change Log:
86 
 * $Log: rule-firsts.c,v $
87 
 * Revision 1.1.1.1  1998/01/17  15:57:47  release
88 
 * First version to be checked into rolling release.
89 
 *
90 
 * Revision 1.2  1994/12/15  09:58:39  smf
91 
 * Brought into line with OSSG C Coding Standards Document, as per
92 
 * "CR94_178.sid+tld-update".
93 
 *
94 
 * Revision 1.1.1.1  1994/07/25  16:04:38  smf
95 
 * Initial import of SID 1.8 non shared files.
96 
 *
97 
**/
98 
 
99 
/****************************************************************************/
100 
 
101 
#include "rule.h"
102 
#include "basic.h"
103 
#include "gen-errors.h"
104 
#include "table.h"
105 
 
106 
/*--------------------------------------------------------------------------*/
107 
 
108 
void
6 7u83 109 
rule_compute_first_set_1(RuleP rule)
2 7u83 110 
{
111 
    AltP     alt;
112 
    unsigned priority = 0;
113 
 
6 7u83 114 
    if (rule_has_computed_first_set(rule)) {
2 7u83 115 
	return;
6 7u83 116 
    } else if (rule_is_computing_first_set(rule)) {
117 
	E_cannot_compute_first_set(rule);
2 7u83 118 
	return;
119 
    }
6 7u83 120 
    rule_computing_first_set(rule);
121 
    for (alt = rule_alt_head(rule); alt; alt = alt_next(alt)) {
2 7u83 122 
	BoolT see_through = TRUE;
123 
	BoolT no_action   = TRUE;
6 7u83 124 
	ItemP item        = alt_item_head(alt);
2 7u83 125 
	ItemP initial     = item;
126 
 
6 7u83 127 
	for (; see_through && (item != NIL(ItemP)); item = item_next(item)) {
128 
	    switch (item_type(item))EXHAUSTIVE {
2 7u83 129 
	      case ET_PREDICATE:
130 
		if (item != initial) {
6 7u83 131 
		    E_see_to_predicate(entry_key(item_entry(item)), rule);
2 7u83 132 
		}
6 7u83 133 
		entry_list_add_if_missing(rule_predicate_first(rule),
134 
					  item_entry(item));
2 7u83 135 
		see_through = FALSE;
136 
		break;
137 
	      case ET_RENAME:
138 
	      case ET_ACTION:
139 
		no_action = FALSE;
140 
		break;
141 
	      case ET_RULE: {
6 7u83 142 
		  EntryP     entry      = item_entry(item);
143 
		  RuleP      item_rule  = entry_get_rule(entry);
144 
		  EntryListP pred_first = rule_predicate_first(item_rule);
2 7u83 145 
		  unsigned   item_priority;
146 
 
6 7u83 147 
		  rule_compute_first_set_1(item_rule);
2 7u83 148 
		  if ((item != initial) &&
6 7u83 149 
		     (!entry_list_is_empty(pred_first))) {
150 
		      E_see_to_rule_predicate(item_rule, rule);
2 7u83 151 
		  }
6 7u83 152 
		  bitvec_or(rule_first_set(rule), rule_first_set(item_rule));
153 
		  entry_list_append(rule_predicate_first(rule), pred_first);
154 
		  see_through   = rule_is_see_through(item_rule);
155 
		  item_priority = rule_get_priority(item_rule);
2 7u83 156 
		  if ((item_priority > priority) && no_action) {
157 
		      priority = item_priority;
158 
		  }
159 
	      }
160 
		break;
161 
	      case ET_BASIC: {
6 7u83 162 
		  BasicP basic = entry_get_basic(item_entry(item));
2 7u83 163 
 
6 7u83 164 
		  bitvec_set(rule_first_set(rule), basic_terminal(basic));
2 7u83 165 
		  see_through = FALSE;
166 
	      }
167 
		break;
168 
	      case ET_NON_LOCAL:
169 
	      case ET_NAME:
170 
	      case ET_TYPE:
171 
		UNREACHED;
172 
	    }
173 
	}
174 
	if (see_through) {
6 7u83 175 
	    rule_see_through(rule);
2 7u83 176 
	}
177 
    }
6 7u83 178 
    if (rule_has_empty_alt(rule)) {
179 
	rule_see_through(rule);
2 7u83 180 
    }
6 7u83 181 
    rule_set_priority(rule, priority + 1);
182 
    if (rule_is_see_through(rule) && bitvec_is_full(rule_first_set(rule))) {
183 
	E_redundant_see_through_alt(rule);
2 7u83 184 
    }
6 7u83 185 
    rule_computed_first_set(rule);
2 7u83 186 
}
187 
 
188 
void
6 7u83 189 
rule_compute_first_set(EntryP entry, GenericP gclosure)
2 7u83 190 
{
6 7u83 191 
    UNUSED(gclosure);
192 
    if (entry_is_rule(entry)) {
193 
	RuleP rule = entry_get_rule(entry);
2 7u83 194 
 
6 7u83 195 
	rule_compute_first_set_1(rule);
2 7u83 196 
    }
197 
}
198 
 
199 
/*
200 
 * Local variables(smf):
201 
 * eval: (include::add-path-entry "../os-interface" "../library")
202 
 * eval: (include::add-path-entry "../generated")
203 
 * end:
204 
**/