1 //////////////////////////////////////////////////////////////////////////////
4 // ADLib, Prop and their related set of tools and documentation are in the
5 // public domain. The author(s) of this software reserve no copyrights on
6 // the source code and any code generated using the tools. You are encouraged
7 // to use ADLib and Prop to develop software, in both academic and commercial
8 // settings, and are free to incorporate any part of ADLib and Prop into
11 // Although you are under no obligation to do so, we strongly recommend that
12 // you give away all software developed using our tools.
14 // We also ask that credit be given to us when ADLib and/or Prop are used in
15 // your programs, and that this notice be preserved intact in all the source
18 // This software is still under development and we welcome any suggestions
19 // and help from the users.
23 //////////////////////////////////////////////////////////////////////////////
27 #include <AD/automata/treegram.ph>
28 #include <AD/contain/bitset.h>
30 //////////////////////////////////////////////////////////////////////////////
31 // Make hidden types visible
32 //////////////////////////////////////////////////////////////////////////////
33 typedef TreeGrammar::TreeProduction TreeProduction;
34 typedef TreeGrammar::Functor Functor;
35 typedef TreeGrammar::Arity Arity;
37 //////////////////////////////////////////////////////////////////////////////
38 // Function to allocate a new term
39 //////////////////////////////////////////////////////////////////////////////
40 TreeTerm new_term(Mem& mem, short int f, unsigned char n, TreeTerm * subterms)
41 { TreeTerm * S = n > 0 ? (TreeTerm*)mem.c_alloc(sizeof(TreeTerm) * n) : 0;
42 if (subterms) for (int i = n - 1; i >= 0; i--) S[i] = subterms[i];
43 return tree_term'(mem)(f,n,S);
46 //////////////////////////////////////////////////////////////////////////////
47 // Method to initialize an instance
48 //////////////////////////////////////////////////////////////////////////////
49 void TreeGrammar::init()
52 minimum_functor = maximum_functor =
53 minimum_variable = maximum_variable = 0;
55 number_of_productions = 0;
56 number_of_variables = 0;
57 number_of_functors = 0;
62 //////////////////////////////////////////////////////////////////////////////
63 // Constructors and destructor
64 //////////////////////////////////////////////////////////////////////////////
65 TreeGrammar::TreeGrammar() { init(); }
66 TreeGrammar::TreeGrammar(int n, TreeProduction P[], const char * f[], const char * v[])
67 { init(); compile(n,P,f,v); }
68 TreeGrammar::~TreeGrammar()
69 { delete [] productions;
73 //////////////////////////////////////////////////////////////////////////////
74 // Method to compile a set of tree productions
75 //////////////////////////////////////////////////////////////////////////////
76 void TreeGrammar::compile
77 ( int n, // number of productions
78 TreeProduction P[], // an array of tree productions
79 const char * f_names[], // names of functors
80 const char * v_names[], // names of variables(non-terminals)
81 Functor min_f, // user supplied minimal functor encoding
82 Functor max_f, // user supplied maximal functor encoding
83 Variable min_v, // user supplied minimal variable encoding
84 Variable max_v // user supplied maximal variable encoding
87 ///////////////////////////////////////////////////////////////////////////
88 // (1) Allocate the productions array and initialize various members.
89 ///////////////////////////////////////////////////////////////////////////
90 productions = new TreeProduction [n];
91 minimum_functor = min_f;
92 maximum_functor = max_f;
93 minimum_variable = min_v;
94 maximum_variable = max_v;
96 number_of_productions = n;
97 functor_names = f_names;
98 variable_names = v_names;
99 memcpy(productions,P,n * sizeof(TreeProduction));
101 ///////////////////////////////////////////////////////////////////////////
102 // (2) Compute the ranges of non-terminals and functors.
103 ///////////////////////////////////////////////////////////////////////////
105 for (i = 0; i < n; i++) {
106 Variable v = P[i].var;
107 if (v < minimum_variable) minimum_variable = v;
108 if (v > maximum_variable) maximum_variable = v;
111 if (minimum_functor > maximum_functor ) minimum_functor = maximum_functor = 0;
112 if (minimum_variable > maximum_variable) minimum_variable = maximum_variable = 0;
113 number_of_variables = maximum_variable - minimum_variable + 1;
114 number_of_functors = maximum_functor - minimum_functor + 1;
116 ///////////////////////////////////////////////////////////////////////////
117 // (3) Compute the mapping from functors to their rank.
118 ///////////////////////////////////////////////////////////////////////////
119 arities = new Arity [number_of_functors];
120 memset(arities, 0, number_of_functors * sizeof(Arity));
121 for (i = 0; i < n; i++) tabulate_arity(P[i].term);
123 assert(minimum_variable >= 0);
124 assert(minimum_functor >= 0);
127 //////////////////////////////////////////////////////////////////////////////
128 // Auxiliary method to compute the ranges of non-terminals and functors.
129 //////////////////////////////////////////////////////////////////////////////
130 void TreeGrammar::tabulate(const TreeTerm t)
132 case wild_term: // do nothing
133 case var_term(v): if (v < minimum_variable) minimum_variable = v;
134 if (v > maximum_variable) maximum_variable = v;
135 case and_term(x,y): tabulate(x); tabulate(y);
136 case or_term(x,y): tabulate(x); tabulate(y);
137 case not_term(n): tabulate(n);
138 case tree_term(f,n,subterms):
139 if (f < minimum_functor) minimum_functor = f;
140 if (f > maximum_functor) maximum_functor = f;
141 for (int i = n - 1; i >= 0; i--) tabulate(subterms[i]);
142 case set_term _: // do nothing
146 //////////////////////////////////////////////////////////////////////////////
147 // Auxiliary method to compute the arity of functors.
148 //////////////////////////////////////////////////////////////////////////////
149 void TreeGrammar::tabulate_arity(const TreeTerm t)
151 case and_term(x,y): tabulate_arity(x); tabulate_arity(y);
152 case or_term(x,y): tabulate_arity(x); tabulate_arity(y);
153 case not_term(n): tabulate_arity(n);
154 case tree_term(f,n,subterms):
156 for (int i = n - 1; i >= 0; i--)
157 tabulate_arity(subterms[i]);
158 if (n > maximum_arity) maximum_arity = n;
159 case _: // do nothing
163 ///////////////////////////////////////////////////////////////////////////
164 // Equality for terms. Shallow comparison only
165 ///////////////////////////////////////////////////////////////////////////
166 Bool equal(const TreeTerm a, const TreeTerm b)
167 { match (a) and (b) {
168 case (wild_term, wild_term): return true;
169 case (var_term u, var_term v): return u == v;
170 case (or_term(a,b), or_term(c,d)): return a == c && b == d;
171 case (and_term(a,b), and_term(c,d)): return a == c && b == d;
172 case (set_term a, set_term b): return a == b;
173 case (tree_term(f,n,s), tree_term(g,m,t)):
174 if (f != g || n != m) return false;
175 for (int i = n - 1; i >= 0; i--)
176 if (s[i] != t[i]) return false;
178 case _: return false;
182 ///////////////////////////////////////////////////////////////////////////
183 // Hash function for terms
184 ///////////////////////////////////////////////////////////////////////////
185 unsigned int hash(const TreeTerm a)
187 case wild_term: return 73;
188 case var_term v: return v;
189 case or_term(x,y): return 493 + (unsigned int)x + (unsigned int)y;
190 case and_term(x,y): return 245 + (unsigned int)x + (unsigned int)y;
191 case not_term(n): return 127 + (unsigned int)n;
192 case tree_term(f,n,subterms):
194 for (int i = n - 1; i >= 0; i--) h += h + (unsigned int)subterms[i];
196 case set_term s: return (unsigned int)s;
200 ///////////////////////////////////////////////////////////////////////////
202 ///////////////////////////////////////////////////////////////////////////
204 const char * TreeGrammar::functor_name(Functor f) const
205 { if (functor_names && f >= min_functor() && f <= max_functor())
206 return functor_names[f];
211 const char * TreeGrammar::variable_name(Variable v) const
212 { if (variable_names && v >= min_variable() && v <= max_variable() &&
213 variable_names[v] != 0)
214 return variable_names[v];
219 ///////////////////////////////////////////////////////////////////////////
220 // Method to print a functor name.
221 ///////////////////////////////////////////////////////////////////////////
222 ostream& TreeGrammar::print_functor(ostream& out, Functor f) const
223 { if (functor_names && f >= min_functor() && f <= max_functor())
224 return out << functor_names[f];
226 return out << 'F' << f;
229 ///////////////////////////////////////////////////////////////////////////
230 // Method to print a variable name.
231 ///////////////////////////////////////////////////////////////////////////
232 ostream& TreeGrammar::print_variable(ostream& out, Variable v) const
233 { if (variable_names && v >= min_variable() && v <= max_variable() &&
234 variable_names[v] != 0)
235 return out << '<' << variable_names[v] << '>';
240 ///////////////////////////////////////////////////////////////////////////
241 // Method to print a tree term.
242 ///////////////////////////////////////////////////////////////////////////
243 ostream& TreeGrammar::print(ostream& S, const TreeTerm term) const
245 case wild_term: S << '_';
246 case var_term v: print_variable(S, v);
247 case or_term(x,y): S << '('; print(S,x); S << " or: "; print(S,y); S << ')';
248 case and_term(x,y): S << '('; print(S,x); S << " and: "; print(S,y); S << ')';
249 case not_term n: S << "not: "; print(S,n);
250 case set_term s: S << *s;
251 case tree_term(f,n,subterms):
252 { const char * f_name = functor_name(f);
255 if (f_name[0] == '#')
256 { char begin_ch = f_name[1];
257 char end_ch = f_name[strlen(f_name)-1];
258 S << '#' << begin_ch;
260 { tree_term(f,2,subterms):
261 { if (! first) S << ", "; print(S,subterms[0]); first = false;
264 | tree_term(f,0,subterms) | (functor_name(f))[0] == '#':
265 { return S << end_ch; }
267 { if (! first) S << " ... "; print(S,t); return S << end_ch; }
269 } else if (f_name[0] != '\0' && f_name[1] == '|')
270 { S << f_name[0] << "| ";
271 for (int i = 0; i < n; i++) {
272 print(S,subterms[i]); if (i < n - 1) S << ", ";
274 S << ' ' << (f_name + 5);
276 { print_functor(S,f);
279 for (int i = 0; i < n; i++) {
280 print(S,subterms[i]); if (i < n - 1) S << ", ";
290 ///////////////////////////////////////////////////////////////////////////
291 // Method to print a tree production.
292 ///////////////////////////////////////////////////////////////////////////
293 ostream& TreeGrammar::print(ostream& out, const TreeProduction& P) const
294 { print_variable(out, P.var);
300 ///////////////////////////////////////////////////////////////////////////
301 // Method to print a tree grammar.
302 ///////////////////////////////////////////////////////////////////////////
303 ostream& operator << (ostream& out, const TreeGrammar& G)
304 { for (int i = 0; i < G.size(); i++) {
305 out << '[' << i << ']' << '\t';
306 G.print(out,G[i]) << '\n';