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

comparison anagram/agcore/cd.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-1999 Parsifal Software. All Rights Reserved.
4 * See the file COPYING for license and usage terms.
5 *
6 * cd.cpp - Conflict Derivation module
7 */
8
9 #include "arrays.h"
10 #include "cd.h"
11 #include "data.h"
12 #include "dict.h"
13 #include "q1glbl.h"
14 #include "rule.h"
15 #include "stacks.h"
16 #include "tsd.h"
17 #include "token.h"
18
19 //#define INCLUDE_LOGGING
20 #include "log.h"
21
22
23 int conflict_token = 0;
24 tsd *token_derivation = NULL;
25
26 char *tried;
27
28 int find_gotos(int s, const unsigned **p) {
29 state_number_map *sp = &map_state_number[s];
30 int n = sp->n_chain_gotos;
31 if (n == 0) {
32 *p = lstptr(*sp, gotos);
33 n = sp->n_gotos;
34 }
35 else {
36 *p = lstptr(*sp, chain_gotos);
37 }
38 return n;
39 }
40
41 /*
42 * x2 returns true if llt is an expansion token of hlt, false otherwise
43 */
44
45 /*
46 int x2(unsigned hlt, unsigned llt) {
47 //LOGSECTION("x2");
48 //token_number_map *tp;
49 unsigned *fl;
50 int nf;
51
52 Token token = hlt;
53 Token candidate = llt;
54 if (token == candidate) return 1;
55 //LOGV(hlt);
56 //LOGV(llt);
57 //assert(hlt <= ntkns);
58 //tp = &map_token_number[hlt];
59 //fl = lstptr(*tp, expansion_forms);
60 //nf = tp->n_expansion_forms;
61 nf = token->n_expansion_forms;
62 while (nf--) {
63 //form_number_map *fp = &map_form_number[*fl++];
64 Rule rule = *fl++;
65 int k = rule->length();
66 if (k == 0) {
67 continue;
68 }
69 //if (llt == lstptr(*fp,tokens)[0]) return 1;
70 if (candidate == rule->token(0)) {
71 return 1;
72 }
73 }
74 return 0;
75 }
76 */
77
78 /*
79 static int x2x(unsigned hlt, unsigned llt) {
80 //token_number_map *tp;
81 //unsigned *tl;
82 int nt;
83
84 Token highLevel(hlt);
85 Token lowLevel(llt);
86 if (highLevel == lowLevel) return 1;
87 //tp = &map_token_number[hlt];
88 //tl = lstptr(*tp,leading_tokens);
89 //nt = tp->n_leading_tokens;
90 //while (nt--) if (llt == *tl++) return 1;
91 while (nt--) if (lowLevel == highLevel->leadingToken(nt)) return 1;
92 return 0;
93 }
94 */
95
96 /*
97 * x2d checks the characteristic rules in state sn, and returns true if
98 * tn is next token for some characteristic rule. Otherwise, return 0
99 */
100
101 int x2d(int sn, int tn) {
102 int *items = dict_str(isht_dict,sn);
103 int nitems = (*items++ -1)/2 ;
104 while (nitems--) {
105 Rule rule = *items++;
106 unsigned fx = *items++;
107 if (rule->length() <= fx) {
108 continue;
109 }
110 //if (x2x(lstptr(map_form_number[fn],tokens)[fx],tn)) return 1;
111 //if (x2x(Rule(fn)->token(fx),tn)) return 1;
112 if (rule.token(fx).isLeadingToken(tn)) {
113 return 1;
114 }
115 }
116 return 0;
117 }
118
119
120 /*
121 * x4 returns true if fn is a left expansion rule of hlt, false otherwise
122 */
123
124 /*
125 int x4(unsigned hlt, unsigned fn) {
126 assert(hlt <= ntkns);
127 token_number_map *tp = &map_token_number[hlt];
128 unsigned *fl = lstptr(*tp, expansion_forms);
129 unsigned nf = tp->n_expansion_forms;
130
131 assert(nf <= nforms);
132 while (nf--) if (*fl++ == fn) return 1;
133 return 0;
134 }
135 */
136
137 #ifndef COMMAND_LINE
138 int x3(tsd *isl, int sx, int fn, int fx) {
139 unsigned k;
140
141 check_tsd(isl);
142 assert((unsigned)fn <= nforms);
143 sx++;
144 for (k = 0; k < isl->nt; k++) {
145 int fsx, fsn, ffn, ffx;
146 xtxf(isl, k, &fsx, &fsn, &ffn, &ffx);
147 if (fsx < sx) {
148 return 0;
149 }
150 if (fsx > sx) {
151 continue;
152 }
153 if (ffn == fn && ffx == fx + 1) {
154 return 1;
155 }
156 if (ffx != 1) {
157 continue;
158 }
159 //if (x4(lstptr(map_form_number[fn],tokens)[fx],ffn)) return 1;
160 //if (x4(Rule(fn)->token(fx),ffn)) return 1;
161 if (Rule(fn).token(fx).isExpansionRule(ffn)) {
162 return 1;
163 }
164 }
165 return 0;
166 }
167
168 int x3a(tsd *isl, int sx, int fn, int fx) {
169 unsigned k;
170
171 check_tsd(isl);
172 assert((unsigned)fn <= nforms);
173 for (k = 0; k < isl->nt; k++) {
174 int fsx, fsn, ffn, ffx;
175 xtxf(isl, k, &fsx, &fsn, &ffn, &ffx);
176 if (fsx < sx) {
177 return 0;
178 }
179 if (fsx > sx) {
180 continue;
181 }
182 if (ffn == fn && ffx == fx) {
183 return 0;
184 }
185 //if (x4(lstptr(map_form_number[fn],tokens)[fx],ffn)) return 1;
186 //if (x4(Rule(fn)->token(fx),ffn)) return 1;
187 if (Rule(fn).token(fx).isExpansionRule(ffn)) {
188 return 1;
189 }
190 }
191 return 0;
192 }
193
194
195 /* x1 builds a rule stack from a token stack */
196
197 tuple_dict *xis(unsigned sn) {
198 tuple_dict *d = null_tuple_dict(2);
199 int *items, nitems, length;
200 unsigned k;
201
202 assert(sn < isht_dict->nsx);
203 items = dict_str(isht_dict, sn);
204 length = *items++ - 1;
205 nitems = length/2;
206 while (nitems--) {
207 int fn = *items++;
208 int fx = *items++;
209 insert_tuple_dict(d, fn, fx);
210 }
211 for (k = 0; k < d->nsx; k++) {
212 int *t = d->text+2*k;
213 int fn = *t++;
214 unsigned fx = *t;
215 if (fx < Rule(fn)->length()) {
216 //unsigned tn = lstptr(map_form_number[fn],tokens)[fx];
217 Token token(Rule(fn).token(fx));
218 //token_number_map *tp = &map_token_number[tn];
219 //int nf = token->n_forms;
220 int nf = token->ruleList.size();
221 //unsigned *fl = lstptr(*tp,forms);
222 //unsigned *fl = token->forms();
223 iws();
224 //while (nf--) {
225 for (int i = 0; i < nf; i++) {
226 //form_number_map *fp = &map_form_number[*fl];
227 //Rule rule(*fl);
228 Rule rule = token.rule(i);
229 //if (fp->length && lstptr(*fp, tokens)[0] == tn)
230 if (rule->length() && rule.token(0) == token) {
231 //insert_tuple_dict(d,*fl, 0);
232 insert_tuple_dict(d, (int) rule, 0);
233 }
234 else {
235 aws(rule);
236 }
237 }
238 unsigned *fl = (unsigned *) list_base;
239 nf = rws();
240 while (nf--) {
241 insert_tuple_dict(d, *fl++, 0);
242 }
243 }
244 }
245 return d;
246 }
247
248 #endif
249
250 /*
251 tsd *x1x(tsd *sl) {
252 int n = sl->nt;
253 int sx,sn,tn;
254 unsigned fx;
255 int *items;
256 int nitems;
257 tsd *isl = init_tsd(4);
258
259 check_tsd(sl);
260 sx = n-1;
261 xtxf(sl,sx,&sn,&tn);
262 if (!shift_token(tn,sn)) {
263 tn = 0;
264 }
265
266 {
267 tuple_dict *d;
268 d = xis(sn);
269 items = d->text;
270 nitems = d->nsx;
271 items += 2*nitems;
272 while (nitems--) {
273 fx = *--items;
274 Rule rule = *--items;
275 if (tn == 0 ||
276 fx >= rule->non_vanishing_length ||
277 rule.token(fx).isExpansionToken(tn)) {
278 at(isl,sx,sn,(int) rule,fx);
279 }
280 }
281 delete_tuple_dict(d);
282 }
283 while (sx-- > 0) {
284 tuple_dict *d;
285 unsigned psn = sn;
286 const unsigned *p;
287 int n;
288 xtxf(sl,sx,&sn,&tn);
289 n = find_gotos(sn, &p);
290 p += 2*n;
291 while (n-- && *--p != psn) {
292 p--;
293 }
294 assert(*p == psn && n >= 0);
295 d = xis(sn);
296 items = d->text;
297 nitems = d->nsx;
298 items += 2*nitems;
299 while (nitems--) {
300 fx = *--items;
301 Rule rule = *--items;
302 if (fx >= rule->length()) {
303 continue;
304 }
305 if (x3(isl, sx,rule,fx)) {
306 at(isl, sx, sn, (int)rule, fx);
307 }
308 }
309 delete_tuple_dict(d);
310 }
311 return isl;
312 }
313 */
314
315 int x9x(int tn) {
316 Token token = tn;
317 //token_number_map *tp = &map_token_number[tn];
318 //unsigned *fl = lstptr(*tp,forms);
319 //int nf = token->n_forms;
320 int nf = token->ruleList.size();
321
322 if (tn == conflict_token) {
323 return 1;
324 }
325 if (tried[tn]) {
326 return 0;
327 }
328 tried[tn] = 1;
329 //while (nf--) {
330 for (int i = 0; i < nf; i++) {
331 //int fn = *fl++;
332 Rule rule = token.rule(i);
333 //form_number_map *fp = &map_form_number[fn];
334 int length = rule->length();
335 int fx = 0;
336 while (fx < length) {
337 //int t = lstptr(*fp,tokens)[fx];
338 Token ruleToken = rule.token(fx);
339 if ((int) ruleToken == conflict_token || x9x(ruleToken)) {
340 at(token_derivation, (int) rule, fx);
341 return 1;
342 }
343 //if (!map_token_number[t].zero_length_flag) break;
344 if (!token->zero_length_flag) {
345 break;
346 }
347 fx++;
348 }
349 }
350 return 0;
351 }
352
353 int new_next_state(int s, unsigned t) {
354 LOGSECTION("new_next_state");
355 LOGV(s) LCV(t);
356 Token token = t;
357 //token_number_map *tp;
358 int ts;
359 int np;
360 const unsigned *gl;
361 int ng = find_gotos(s, &gl);
362 const unsigned *glx = gl;
363 int ngx = ng;
364
365 //check_stack;
366 while (ng--) {
367 LOGV(gl[0]) LCV(gl[1]);
368 Token token = *gl;
369 if (*gl == t ||
370 (token->junky && (unsigned) token.rule(0).token(0) == t)) {
371 return gl[1];
372 }
373 else {
374 gl += 2;
375 }
376 }
377 LOGS("Didn't find a goto");
378 //tp = &map_token_number[t];
379 //ts = tp->token_set_id;
380 ts = token->token_set_id;
381 Token pureToken;
382 LOGV(pureToken) LCV(ts);
383 if (token->junky) {
384 pureToken = token.rule(0).token(0);
385 }
386 if (ts == 0 && pureToken.isNotNull()) {
387 ts = pureToken->token_set_id;
388 }
389 LOGV(pureToken) LCV(ts);
390 np = map_char_set[ts].nparts;
391 LOGV(np);
392 if (ts && np > 1) {
393 unsigned *fl = lstptr(map_char_set[ts], part);
394 while (np--) {
395 const unsigned *g = glx;
396 int n = ngx;
397 unsigned pn = fl[np];
398 unsigned pt = map_part_number[pn].token_number;
399 while (n--) {
400 if (*g++ == pt) {
401 return *g;
402 }
403 else {
404 g++;
405 }
406 }
407 }
408 }
409 LOGS("Didn't find a partition set either");
410 return 0;
411 }
412
413 Token transitionToken(unsigned fromState, unsigned toState) {
414 LOGSECTION("transitionToken");
415 LOGV(fromState) LCV(toState);
416 const unsigned *gl;
417 int nGotos = find_gotos(fromState,&gl);
418 //const unsigned *glx = gl;
419 int ngx = nGotos;
420
421 //check_stack;
422 while (ngx--) {
423 LOGV(gl[0]) LCV(gl[1]);
424 Token token = *gl;
425 if (gl[1] == toState) {
426 return gl[0];
427 }
428 gl += 2;
429 }
430 LOGS("Didn't find a goto");
431 return Token();
432 }
433