Mercurial > ~dholland > hg > ag > index.cgi

comparison anagram/agcore/q8.cpp @ 0:13d2b8934445

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
Import AnaGram (near-)release tree into Mercurial.
author David A. Holland
date Sat, 22 Dec 2007 17:52:45 -0500
parents
children
comparison
equal deleted inserted replaced
-1:000000000000 0:13d2b8934445
1 /*
2 * AnaGram, A System for Syntax Directed Programming
3 * Copyright 1993-2002 Parsifal Software. All Rights Reserved.
4 * See the file COPYING for license and usage terms.
5 *
6 * q8.cpp
7 */
8
9 #include "agbaltree.h"
10 #include "arrays.h"
11 #include "assert.h"
12 #include "bitmap.h"
13 #include "dict.h"
14 #include "q1glbl.h"
15 #include "q8.h"
16 #include "rule.h"
17 #include "stacks.h"
18 #include "token.h"
19
20 //#define INCLUDE_LOGGING
21 #include "log.h"
22
23
24 int external_reduction;
25
26 static void find_free_states(int s) {
27 LOGSECTION("find_free_states");
28 LOGV(s);
29 state_number_map *msn = &map_state_number[s];
30 unsigned *p = lstptr(*msn, gotos);
31 int n = msn->n_gotos;
32 while (n--) {
33 int t = *p++;
34 int ns = *p++;
35 if (map_token_number[t].zero_length_flag) {
36 //if (distinguish_lexemes && t == disregard_token) continue;
37 if (isws(ns)) {
38 continue;
39 }
40 LOGV(t) LCV(disregard_token);
41 find_free_states(ns);
42 }
43 }
44 }
45
46 static void frss13(int sn, int f) {
47 LOGSECTION("frss13");
48 LOGV(sn) LCV(f);
49 int flag, kn, g, s, nf, n, *sp, m;
50 unsigned t;
51 unsigned *p;
52 unsigned *px;
53 state_number_map *msn = &map_state_number[sn];
54
55 if (f == 0) {
56 isws(0);
57 return;
58 }
59 sp = ibnfs + ibnfb[f];
60 m = ibnfn[f];
61 while (m--) {
62 int i;
63
64 t = sp[m];
65 if (map_token_number[t].subgrammar) {
66 external_reduction = 1;
67 continue;
68 }
69 flag = 0;
70 px = lstptr(*msn,completions);
71 i = 2*msn->n_completions;
72 while (i) {
73 i-=2;
74 if (px[i] != t) {
75 continue;
76 }
77 //g = px[i+1];
78 Rule rule(px[i+1]);
79 add_tuple_dict_new(frss_dict, sn, (int) rule, rule->length()-1);
80 flag++;
81 break;
82 }
83 if (flag) {
84 continue;
85 }
86 px = lstptr(*msn, gotos);
87 for (kn = msn->n_gotos; kn--; px +=2) {
88 if (t == *px) {
89 break;
90 }
91 }
92 if (kn < 0) continue;
93 s = px[1];
94 isws(s);
95 p = (unsigned *) dict_str(isht_dict,s);
96 nf = *p++ - 1;
97 p += nf;
98 nf /= 2;
99 while (nf--) {
100 n = *--p;
101 g = *--p;
102 Rule rule = g;
103 if ((unsigned) n < rule->non_vanishing_length) {
104 continue;
105 }
106 //if (distinguish_lexemes && n < rule->length() &&
107 // (int) rule.token(n) == disregard_token) {
108 // continue;
109 //}
110 LOGV(sn) LCV(g) LCV(n);
111 add_tuple_dict_new(frss_dict, sn, g, n-1);
112 }
113 find_free_states(s);
114 }
115 }
116
117 void frss12(int sn, int f, int n) {
118 unsigned k, ps;
119 unsigned *p, nt;
120 unsigned kk;
121
122 LOGSECTION("frss12");
123 LOGV(sn) LCV(f) LCV(n);
124 add_tuple_dict_new(frss_dict,sn,f,n);
125 external_reduction = 0;
126 iws();
127 k = 0;
128 while (k < frss_dict->nsx) {
129 completed_form_map *mcf;
130 extract_tuple_dict(frss_dict, k, &sn, &f, &n);
131 LOGV(k) LCV(frss_dict->nsx) LCV(sn) LCV(f) LCV(n) ;
132 k++;
133 if (f == 0) {
134 continue;
135 }
136 int length = Rule(f)->length();
137 assert(n <= length);
138 LOGV(f) LCV(length) LCV(n);
139 if (n == length) {
140 kk = add_tuple_dict_new(completed_form_dict, sn, f);
141 check_size(map_completed_form, kk, kk);
142 mcf = &map_completed_form[kk];
143 external_reduction |= mcf->external_reduction;
144 if (mcf->reduction_states_index) {
145 p = lstptr(*mcf, reduction_states);
146 nt = mcf->n_reduction_states;
147 while (nt--) {
148 isws(*p++);
149 }
150 continue;
151 }
152 }
153 if (n) {
154 LOGSECTION("Previous states");
155 state_number_map *msn = &map_state_number[sn];
156 unsigned *p = lstptr(*msn,previous_states);
157 int nt = msn->n_previous_states;
158 while (nt--) {
159 ps = *p++;
160 add_tuple_dict_new(frss_dict, ps, f, n-1);
161 LOGV(ps) LCV(f) LCV(n-1);
162 }
163 continue;
164 }
165 frss13(sn, f);
166 }
167 reset_tuple_dict(frss_dict);
168 }
169
170 static AgArray< AgBalancedTree<int> > digraphList;
171
172 //static void grstt3(unsigned t, unsigned ft) {
173 static void grstt3(Token token, Token follower) {
174 LOGSECTION("grstt3");
175 LOGV((int) token) LCV((int) follower);
176 unsigned nt;
177 unsigned n;
178 //Token token = t;
179 //Token follower = ft;
180
181 if (digraphList[token].insert(follower)) return;
182 n = token->ruleList.size();
183 while (n--) {
184 Rule rule = token.rule(n);
185 RuleDescriptor &ruleDescriptor(rule);
186
187 if ((nt = ruleDescriptor.length()) == 0) {
188 continue;
189 }
190 Token ruleToken;
191 do {
192 //token = rule.token(--nt);
193 ruleToken = ruleDescriptor.token(--nt);
194 if (!ruleToken->non_terminal_flag) {
195 break;
196 }
197 grstt3(ruleToken, follower);
198 } while (nt && ruleToken->zero_length_flag);
199 }
200 }
201
202 void bfst3(void) {
203 LOGSECTION("bfst3");
204 unsigned n, k, kk;
205 Rule ruleZero(0);
206
207 int last = ruleZero->length() - 1;
208 if (last < 0) {
209 return;
210 }
211 LOGV(last) LCV(ruleZero->length()) LCV(ruleZero->elementList.size());
212 if (ruleZero.token(last).isNull()) {
213 return;
214 }
215 digraphList = AgArray< AgBalancedTree<int> >(Token::count());
216 grstt3(ruleZero.token(last), Token());
217
218 for (Each<Rule> rule; rule.loopNotFinished(); rule.getNext()) {
219 RuleDescriptor &ruleDescriptor(rule);
220 //n = rule->length();
221 n = ruleDescriptor.length();
222 if (n < 2) {
223 continue;
224 }
225 k = 0;
226 while (1) {
227 LOGV(rule) LCV(rule->length()) LCV(k);
228 //Token token = rule.token(k);
229
230 //k++;
231 if (++k >= n) {
232 break;
233 }
234 Token token = ruleDescriptor.token(k-1);
235 token_number_map &tokenDescriptor(token);
236 //if (!token->non_terminal_flag &&
237 // !token->zero_length_flag) continue;
238 if (!tokenDescriptor.non_terminal_flag &&
239 !tokenDescriptor.zero_length_flag) {
240 continue;
241 }
242 kk = k;
243 while (kk < n) {
244 LOGV(rule) LCV(rule->length()) LCV(kk);
245 //Token followingToken = rule.token(kk);
246 Token followingToken = ruleDescriptor.token(kk);
247 grstt3(token, followingToken);
248 if (followingToken->zero_length_flag == 0) {
249 break;
250 }
251 kk++;
252 }
253 }
254 }
255 for (Each<Token> t; t.loopNotFinished(); t.getNext()) {
256 AgBalancedTree<int> &list = digraphList[t];
257 Bitmap map(Token::count());
258 AgStack<Token> followers;
259 for (unsigned i = 0; i < list.size(); i++) {
260 if (map.setBit(list[i])) {
261 continue;
262 }
263 followers.push(list[i]);
264 }
265 t->followerList = followers;
266 }
267 digraphList.reset();
268 }
269
270 void ivgtt(void) {
271 LOGSECTION("ivgtt");
272 unsigned ns, i;
273
274 if (nits == 0) {
275 return;
276 }
277 LOGV(n_gotos);
278
279 AgArray< AgBalancedTree< int > > predecessor(nits);
280 for (i = 0; i < nits; i++){
281 state_number_map *sp = &map_state_number[i];
282 unsigned *p = lstptr(*sp, gotos);
283 int nt = sp->n_gotos;
284 LOGV(i) LCV(nt);
285 while (nt--) {
286 p++;
287 ns = *p++;
288 assert(ns < nits);
289 predecessor[ns].insert(i);
290 }
291 }
292 for (i = 0; i < nits; i++) {
293 state_number_map *sp = &map_state_number[i];
294 AgBalancedTree<int> &list = predecessor[i];
295 int n = list.size();
296 iws();
297 LOGS("State") LS(i);
298 for (int j = 0; j < n; j++) {
299 #ifdef INCLUDE_LOGGING
300 LOGX() LS(list[j]);
301 #endif
302 aws(list[j]);
303 }
304 sp->previous_states_index = store_list(previous_states_list);
305 int nps = rws();
306 sp->n_previous_states = nps;
307 }
308 LOGV(n_gotos);
309 }