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

comparison anagram/agcore/q5.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 * q5.cpp
7 */
8
9 #include "arrays.h"
10 #include "assert.h"
11 #include "config.h"
12 #include "bpu.h"
13 #include "cra.h"
14 #include "data.h"
15 #include "dict.h"
16 #include "error.h"
17 #include "keyword.h"
18 #include "lexeme.h"
19 #include "minmax.h"
20 #include "myalloc.h"
21 #include "q1a.h"
22 #include "q1glbl.h"
23 #include "q5.h"
24 #include "q8.h"
25 #include "rule.h"
26 #include "stacks.h"
27 #include "token.h"
28 #include "tsd.h"
29 #include "ut.h"
30
31 //#define INCLUDE_LOGGING
32 #include "log.h"
33
34
35 static unsigned items_length;
36
37 unsigned n_gotos;
38 unsigned n_completions;
39 unsigned n_conflicts;
40 unsigned n_reductions;
41 unsigned n_default_reductions;
42 static int reduce_proc_flag;
43
44
45 tsd *lcft = NULL;
46 tsd *lcftp = NULL;
47 tsd *lgt = NULL;
48
49 int nInputRules = 0;
50
51 //extern tsd *items_table;
52
53 tsd *expand_state(int sn) {
54 int *list = dict_str(isht_dict, sn);
55 int n = (*list++ - 1)/2;
56 int fn, fx, k = n;
57 tsd *sx = init_tsd(2);
58 while (k--) {
59 fn = *list++;
60 fx = *list++;
61 at(sx, fn, fx);
62 }
63 list -= 2*n;
64 k = n;
65 iws();
66 while (k--) {
67 int nx;
68
69 fn = *list++;
70 fx = *list++;
71 if (fx >= (int) map_form_number[fn].length()) {
72 continue;
73 }
74 //tn = lstptr(map_form_number[fn],tokens)[fx];
75 Token token = Rule(fn).token(fx);
76 if (!token->non_terminal_flag) {
77 continue;
78 }
79 //xl = lstptr(map_token_number[tn], expansion_forms);
80 //nx = map_token_number[tn].n_expansion_forms;
81 //while (nx--) xws(*xl++);
82 nx = token->expansionRuleList.size();
83 for (int i = 0; i < nx; i++) {
84 xws(token.expansionRule(i));
85 }
86 }
87 k = tis();
88 list = list_base;
89 while (k--) {
90 at(sx, *list++, 0);
91 }
92 rws();
93 return sx;
94 }
95
96 static AgBalancedTree<OrderedPair<int> > pairs;
97 static AgBalancedTree<int> frameTokens;
98 static AgStack<int> frameRules;
99 static AgBalancedTree<int> frameStates;
100 int frameIndex;
101
102 static void findFrameStates(int sn, int rx) {
103 LOGSECTION("findFrameStates");
104 LOGV(sn) LCV(rx);
105 if (pairs.insert(OrderedPair<int>(sn, rx))) {
106 return;
107 }
108 LOGV(sn) LCV(rx);
109 if (rx) {
110 unsigned *p = lstptr(map_state_number[sn],previous_states);
111 int nt = map_state_number[sn].n_previous_states;
112 LOGV(nt);
113 while (nt--) {
114 LOGV(*p);
115 findFrameStates(*p++, rx - 1);
116 }
117 return;
118 }
119 frameStates.insert(sn);
120 }
121
122 static void findFrameTokens(void) {
123 LOGSECTION("findFrameTokens");
124 frameTokens.reset();
125 int n = frameStates.size();
126 LOGV(n);
127 if (n == 0) {
128 return;
129 }
130
131 int state = frameStates[0];
132 tsd *expansion = expand_state(state);
133 int k = expansion->nt;
134 LOGV(state) LCV(k);
135
136 { LOGSECTION("Scan expansion rules"); }
137
138 while (k--) {
139 int r, index;
140 xtx(expansion, k, &r, &index);
141 Rule rule(r);
142 RuleDescriptor &ruleDescriptor(rule);
143 if (index >= (int) ruleDescriptor.length()) {
144 continue;
145 }
146 Token token = ruleDescriptor.token(index);
147 token_number_map &tokenDescriptor(token);
148 if (tokenDescriptor.key || tokenDescriptor.fine_structure ||
149 tokenDescriptor.junky) {
150 continue;
151 }
152 if ((int) token == grammar_token) {
153 continue;
154 }
155 LOGV(rule) LCV(index) LCV(token);
156 int nFrameRules = frameRules.size();
157 // Does there exist a frameRule which is an expansion rule of token?
158 while (nFrameRules--) {
159 if (token.isExpansionRule(frameRules[nFrameRules])) {
160 break;
161 }
162 }
163 if (nFrameRules < 0) {
164 continue;
165 }
166 // Yes, at least one
167 nFrameRules = frameRules.size();
168 // Is there a frameRule which is not an expansion rule of token?
169 while (nFrameRules--) {
170 if (!token.isExpansionRule(frameRules[nFrameRules])) {
171 break;
172 }
173 }
174 if (nFrameRules >= 0 && index == 0) {
175 continue;
176 }
177 LOGV(token);
178 frameTokens.insert(token);
179 }
180 delete_tsd(expansion);
181
182 { LOGSECTION("Scan frameStates"); }
183
184 int i = 1;
185 while (i < n) {
186 AgBalancedTree<int> tokens;
187 state = frameStates[i++];
188 LOGV(state);
189 expansion = expand_state(state);
190 k = expansion->nt;
191 while (k--) {
192 int r, index;
193 xtx(expansion, k, &r, &index);
194 Rule rule(r);
195 RuleDescriptor &ruleDescriptor(rule);
196 if (index >= (int) ruleDescriptor.length()) {
197 continue;
198 }
199 Token token = rule.token(index);
200 if (!frameTokens.includes(token)) {
201 continue;
202 }
203 token_number_map &tokenDescriptor(token);
204 if (tokenDescriptor.key || tokenDescriptor.fine_structure ||
205 tokenDescriptor.junky) {
206 continue;
207 }
208 if ((int) token == grammar_token) {
209 continue;
210 }
211 LOGV(rule) LCV(index) LCV(token);
212 int nFrameRules = frameRules.size();
213 while (nFrameRules--) {
214 if (token.isExpansionRule(frameRules[nFrameRules])) {
215 break;
216 }
217 }
218 if (nFrameRules < 0) {
219 continue;
220 }
221 nFrameRules = frameRules.size();
222 while (nFrameRules--) {
223 if (!token.isExpansionRule(frameRules[nFrameRules])) {
224 break;
225 }
226 }
227 LOGV(nFrameRules);
228 if (nFrameRules >= 0 && index == 0) continue;
229 LOGV(token);
230 tokens.insert(token);
231 }
232 delete_tsd(expansion);
233 LOGS("Expansion deleted");
234 frameTokens *= tokens;
235 LOGS("Intersection complete");
236 }
237 }
238
239 int find_ctn(int state) {
240 LOGSECTION("find_ctn");
241 int *items, nitems;
242 int *p;
243
244 frameRules.reset();
245 items = dict_str(isht_dict,state);
246 nitems = (*items++ -1)/2;
247 p = items;
248 frameIndex = 0;
249 LOGV(state) LCV(nitems);
250 // Scan the items that define this state
251 // The goal is to identify the rule, or rules, that have the fewest tokens
252 // on the parse stack, that is the rules for which the rule index
253 // is at a minimum
254 while (nitems--) {
255 Rule rule(*p++);
256 RuleDescriptor &ruleDescriptor(rule);
257 int index = *p++;
258 if (index >= (int) ruleDescriptor.length()) {
259 continue;
260 }
261 Token token(ruleDescriptor.prim_tkn);
262 if (frameRules.size() == 0 || index < frameIndex) {
263 frameRules.reset().push(rule);
264 frameIndex = index;
265 LOGV(rule) LCV(frameIndex);
266 continue;
267 }
268 else if (index == frameIndex) {
269 frameRules.push(rule);
270 LOGV(rule);
271 }
272 }
273 if (frameRules.size() == 0) {
274 frameIndex = 0;
275 return 0;
276 }
277 frameStates.reset();
278 pairs.reset();
279
280 { LOGSECTION("frame states"); }
281
282 // identify states where frame rules originated
283 findFrameStates(state, frameIndex);
284 pairs.reset();
285
286 { LOGSECTION("frame tokens"); }
287 findFrameTokens();
288 { LOGSECTION("frame tokens complete"); }
289
290 int n = frameTokens.size();
291 if (n == 0) {
292 frameIndex = 0;
293 return 0;
294 }
295 Token token = frameTokens[0];
296 LOGV(n) LCV(token);
297 if (n == 1) {
298 return token;
299 }
300 int i = 1;
301 for (i = 1; i < n; i++) {
302 LOGV(token) LCV(frameTokens[i]);
303 if (token.isExpansionToken(frameTokens[i])) {
304 token = frameTokens[i];
305 }
306 }
307 LOGV(token);
308 frameTokens.reset();
309 frameRules.reset();
310 return (int) token;
311 }
312
313 static int zeros[] = {0,0,0};
314
315 //int *token_list;
316
317
318 static void cmpits3a(unsigned t) {
319 LOGSECTION("cmpits3a");
320 LOGV(t) LCV(tis());
321 unsigned lis_id;
322
323 if ((lits = tis()) == 1) { // if single rule on stack
324 Rule rule = list_base[0];
325 if (rule->length() == (unsigned) list_base[1]) {
326 if (!traditional_engine || rule.isNull() || (int) t == eof_token) {
327 LOGV(rule) LCV(list_base[1]);
328 at(lcft, t, (int) rule);
329 n_completions++;
330 return;
331 }
332 }
333 }
334 Rule rule(list_base[0]);
335 int index = list_base[1] - 1;
336 LOGV(rule) LCV(index);
337 int charToken = rule.token(index);
338 LOGV(charToken);
339 lis_id = add_list_dict(list_base, 2*lits, isht_dict);
340 check_size(map_state_number, lis_id, lis_id);
341 at(lgt, t, lis_id);
342 map_state_number[lis_id].char_token = charToken;
343 LOGV(lis_id) LCV(t);
344 n_gotos++;
345 }
346
347 void *size_prop(unsigned *list, unsigned n) {
348 unsigned m = nits + 1;
349 unsigned k = kits + 1;
350 n += list[0];
351 if (m > 3*k) m = 3*k;
352 return check_array_size(list, n, n*m/k);
353 }
354
355 #define resize(list, n) list = (unsigned *) size_prop(list, n)
356
357 void lalr(void) {
358 LOGSECTION("lalr");
359 int f, n, s, g;
360 int nt;
361 item_map item;
362 //int *chain_tokens = local_array(ntkns+1, int);
363 LocalArray<int> chain_tokens(ntkns+1);
364
365 nits = n_conflicts = 0;
366
367 check_size(map_state_number, n_states_est, n_states_est);
368 n = 4*n_states_est;
369 check_size(completions_list,n, n);
370 check_size(completed_forms_list, n_states_est, n_states_est);
371 check_size(gotos_list, n_gotos, n_gotos);
372 check_size(reductions_list, n_states_est, n_states_est);
373 check_size(chain_completions_list, n, n);
374 check_size(chain_gotos_list, n_gotos, n_gotos);
375 MAP(item, 100);
376 n_gotos = n_completions = 0;
377 n_reductions = n_default_reductions = 0;
378 //token_list = local_array(ntkns+1, int);
379 AgStack<int> tokenStack;
380 lcftp = spec_tsd(300, 2);
381 lcft = spec_tsd(300, 2);
382 lgt = spec_tsd(300, 2);
383 nitems = 1;
384 add_list_dict(zeros, 2, isht_dict);
385
386 nits = 1;
387
388 kits = 0;
389 while (kits < nits) {
390 LOGV(kits) LCV(nits);
391 state_number_map *sp;
392 //int *tnl;
393
394 memset(chain_tokens, 0, (ntkns+1)*sizeof(*chain_tokens));
395 sp = &map_state_number[nstates = kits];
396 nitems = 1;
397
398 items = (unsigned *) dict_str(isht_dict,kits);
399 items_length = (*items++ - 1)/2;
400 n = nitems + items_length + 1;
401 check_size(map_item, n, n);
402
403 ncssa = 0;
404 tokenStack.reset();
405 iws();
406 while (items_length--) {
407 Rule rule(item.form_number = f = *items++);
408 item.form_index = n = *items++;
409 LOGS("item") LS(f) LCS(n);
410 if (n > 0 && Token(rule.token(n-1))->sticky) {
411 sp->sticky = 1;
412 }
413 if ((unsigned) n >= rule->length()) {
414 aws(f);
415 continue;
416 }
417 Token t(rule.token(n));
418 //token_list[ncssa++] = t;
419 tokenStack.push(t);
420 LOGS("token") LS(t);
421 item.chain_item = chain_tokens[t];
422 map_item[nitems] = item;
423 chain_tokens[t] = nitems++;
424
425 nt = t->expansionRuleList.size();
426 check_size(map_item, nitems+nt, nitems+nt);
427 if (nt == 0) {
428 continue;
429 }
430 for (int i = 0; i < nt; i++) {
431 Rule expansionRule(item.form_number = g = t.expansionRule(i));
432 if (expansionRule->length() == 0) {
433 xws(expansionRule);
434 continue;
435 }
436 item.form_index = 0;
437 s = expansionRule.token(0);
438 LOGV(expansionRule)LCS("token is") LS(s);
439 item.chain_item = chain_tokens[s];
440 //if (item.chain_item == 0) token_list[ncssa++] = s;
441 if (item.chain_item == 0) {
442 tokenStack.push(s);
443 }
444 map_item[nitems] = item;
445 chain_tokens[s] = nitems++;
446 }
447 }
448 resize(completed_forms_list, tis());
449 sp->completed_forms_index = store_list(completed_forms_list);
450 sp->n_completed_forms = rws();
451
452 reset_tsd(lgt);
453 reset_tsd(lcft);
454 /*
455 iws();
456 n = 0;
457 while (n<ncssa) {
458 LOGV(n) LCV(token_list[n]);
459 xws(token_list[n++]);
460 }
461 tnl = list_base;
462 ncssa = tis();
463 */
464 AgStack<int> tnl;
465 n = 0;
466 ncssa = tokenStack.size();
467 LOGV(ncssa);
468 while (n < ncssa) {
469 //int tokenNumber = token_list[n++];
470 int tokenNumber = tokenStack[n++];
471 int i = tnl.size();
472 LOGV(tokenNumber);
473 while (i--) {
474 LOGV(i) LCV(tnl[i]);
475 if (tokenNumber == tnl[i]) {
476 break;
477 }
478 }
479 if (i >= 0) {
480 continue;
481 }
482 tnl.push(tokenNumber);
483 LOGV(i) LCV(tokenNumber) LCV(tnl.size());
484 LOGV(tnl.top()) LCV(tnl[tnl.size()-1]);
485 }
486 ncssa = tnl.size();
487 LOGS("Create") LS(ncssa) LS("proto-states");
488 #ifdef INCLUDE_LOGGING
489 n = ncssa;
490 if (n) {
491 LOGV(tnl.top()) LCV(tnl[tnl.size()-1]);
492 }
493 while (n--) {
494 LOGV(n) LCV(tnl[n]);
495 }
496 #endif
497 while (ncssa--) {
498 LOGV(ncssa) LCV(tnl[ncssa]);
499 Token token(tnl[ncssa]);
500 if (token->non_terminal_flag && token->token_set_id && !token->junky) {
501 continue;
502 }
503 iws();
504 n = chain_tokens[token];
505 LOGV(token) LCV(n);
506 while (n) {
507 item = map_item[n];
508 Token pt(Rule(item.form_number)->prim_tkn);
509 LOGV(item.form_number) LCV(pt) LCV(pt->token_set_id);
510 LOGV(pt->junky) LCV(pt->pure);
511
512 if (pt->non_terminal_flag && pt->token_set_id && !pt->junky) {
513 LOGV(n);
514 int n = chain_tokens[pt];
515 while (n) {
516 item_map item = map_item[n];
517 xps(item.form_number, item.form_index + 1);
518 LOGV(item.form_number) LCV(item.form_index + 1);
519 n = item.chain_item;
520 LOGV(n);
521 }
522 }
523 else {
524 xps(item.form_number, item.form_index + 1);
525 }
526 nitems--;
527 n = item.chain_item;
528 }
529 cmpits3a(token);
530 sp = &map_state_number[kits];
531 rps();
532 }
533 //rws();
534 resize(completions_list, lcft->nt);
535 sp->completions_index = store_tuples(lcft, completions_list);
536 sp->n_completions = lcft->nt;
537 resize(gotos_list, lgt->nt);
538 sp->gotos_index = store_tuples(lgt,gotos_list);
539 sp->n_gotos = lgt->nt;
540 nits = isht_dict->nsx;
541 check_size(map_state_number, nits, nits + nits/2);
542 if (!traditional_engine && !rule_coverage) {
543 cra();
544 }
545 kits++;
546 }
547 delete_tsd(lgt);
548 delete_tsd(lcft);
549 delete_tsd(lcftp);
550 delete_array(map_item);
551 map_state_number = (state_number_map *)
552 set_array_size(map_state_number, nits);
553 //close_list_dict(isht_dict);
554 n_states_est = nits - 1;
555 nstates = nits;
556 }
557
558 static void find_followers(int f) {
559 LOGSECTION("find_followers");
560 int nt, nq;
561 unsigned *p;
562
563 if (f == 0) {
564 sws(0);
565 return;
566 }
567 iws();
568 p = (unsigned *) ibnfs + ibnfb[f];
569 nt = ibnfn[f];
570 LOGV(nt);
571 while (nt--) {
572 Token token = *p++;
573 nq = token->followerList.size();
574 LOGV(nq);
575 if (nq == 0 || (nq == 1 && token.follower(0).isNull())) {
576 int errorNumber = errorList.size();
577 ssprintf("Nothing reduces T%03d -> ",(int)token);
578 append_item(f, 1+map_form_number[f].length());
579 log_error(map_form_number[f].line, map_form_number[f].col);
580
581 for (int k = 0; k < errorNumber; k++) {
582 if (errorList[k].message != errorList[errorNumber].message) {
583 continue;
584 }
585 errorList.pop();
586 break;
587 }
588 }
589 for (int k = 0; k < nq; k++) {
590 int nlt;
591 Token follower = token.follower(k);
592 LOGV(follower);
593 if(!follower->non_terminal_flag) {
594 isws(follower);
595 continue;
596 }
597 if ((nlt = follower->leadingTokenList.size()) == 0) {
598 continue;
599 }
600 for (int i = 0; i < nlt; i++) {
601 isws(follower.leadingToken(i));
602 }
603 }
604 }
605 }
606
607 static void bsgt(void) {
608 LOGSECTION("bsgt");
609 int kn, rtk, s, n, g, k;
610 int *p;
611 unsigned *px;
612 state_number_map *sp = &map_state_number[kits];
613
614 px = lstptr(*sp,gotos);
615 kn = sp->n_gotos;
616 while (kn--) {
617 rtk = *px++;
618 s = *px++;
619 if (map_token_number[rtk].non_terminal_flag) {
620 continue;
621 }
622 p = dict_str(isht_dict, s);
623 n = (*p++ - 1)/2;
624 while (n--) {
625 g = *p++;
626 k = *p++;
627 at(sgt, rtk, g, k-1);
628 tut[rtk]++;
629 LOGV(tut[rtk]) LCV(rtk) LCV(k);
630 }
631 }
632 px = lstptr(*sp,completions);
633 kn = sp->n_completions;
634 while (kn--) {
635 rtk = *px++;
636 g = *px++;
637 if (map_token_number[rtk].non_terminal_flag) {
638 continue;
639 }
640 at(sgt, rtk, g, map_form_number[g].length() - 1);
641 tut[rtk]++;
642 LOGV(tut[rtk]) LCV(rtk);
643 }
644 }
645
646 static void logcon(tsd *rrc, int *p, int nt) {
647 LOGSECTION("logcon");
648 LOGV(kits) LCV(nits);
649 int n;
650 int t, f;
651 int *q, nq,qt;
652
653 while (nt--) {
654 if (rrc != res_con) {
655 if (n_conflicts >= (unsigned) max_conflicts) {
656 return;
657 }
658 n_conflicts++;
659 }
660 t = *p++;
661 q = sgt->sb;
662 nq = sgt->nt;
663 while (nq--) {
664 if (*q++ != t) {
665 q += 2;
666 continue;
667 }
668 f = *q++;
669 n = *q++;
670 at(rrc, kits, t, f, n);
671 }
672 q = srt->sb; nq = srt->nt;
673 while (nq--) {
674 qt = *q++;
675 f = *q++;
676 if (qt != t) {
677 continue;
678 }
679 at(rrc, kits, t, f, map_form_number[f].length());
680 }
681 }
682 }
683
684 static void log_prr(tsd *s, tsd *r) {
685 int *p, n;
686
687 p = s->sb;
688 n = s->nt;
689 while (n--) {
690 int t = *p++;
691 int f = *p++;
692
693 at(prr, kits, 0, t, f);
694 }
695 p = r->sb;
696 n = r->nt;
697 while (n--) {
698 int t = *p++;
699 int f = *p++;
700
701 at(prr, kits, 1, t, f);
702 }
703 }
704
705 static tsd *purge_ts = NULL;
706
707 static void purge_gotos(tsd *st) {
708 tsd *t = purge_ts;
709 int kn;
710 state_number_map *sp = &map_state_number[kits];
711
712 t->tw = 2;
713 if ((kn = sp->n_gotos) != 0) {
714 t->nt = t->na = kn;
715 t->sb = (int *) lstptr(*sp,gotos);
716 p1_tsd(t, 0, st, 0);
717 sp->n_gotos = t->nt;
718 }
719 if ((kn = sp->n_chain_gotos) != 0) {
720 t->nt = t->na = kn;
721 t->sb = (int *) lstptr(*sp,chain_gotos);
722 p1_tsd(t, 0, st, 0);
723 sp->n_chain_gotos = t->nt;
724 }
725 if ((kn = sp->n_completions) != 0) {
726 t->nt = t->na = kn;
727 t->sb = (int *)lstptr(*sp,completions);
728 p1_tsd(t, 0, st, 0);
729 sp->n_completions = t->nt;
730 }
731 if ((kn = sp->n_chain_completions) != 0) {
732 t->nt = t-> na = kn;
733 t->sb = (int *) lstptr(*sp,chain_completions);
734 p1_tsd(t, 0, st, 0);
735 sp->n_chain_completions = t->nt;
736 }
737 }
738
739 static void find_terminals(state_number_map *msn) {
740 unsigned *p = lstptr(*msn, gotos);
741 int n = msn->n_gotos;
742
743 while (n--) {
744 int t = *p++;
745 p++;
746 if (!map_token_number[t].non_terminal_flag) {
747 xws(t);
748 }
749 }
750 p = lstptr(*msn, completions);
751 n = msn->n_completions;
752 while (n--) {
753 int t = *p++;
754 p++;
755 if (!map_token_number[t].non_terminal_flag) {
756 xws(t);
757 }
758 }
759 }
760
761 static int disregardToken(const Token &t) {
762 int k = disregardList.size();
763 while (k--) {
764 Token disregardToken = disregardList[k];
765 if (t == disregardToken) {
766 return 1;
767 }
768 AgArray<Token> &list = disregardToken->leadingTokenList;
769 int n = list.size();
770 while (n--) {
771 if (t == list[n]) {
772 return 1;
773 }
774 }
775 }
776 return 0;
777 }
778
779 void rlalr(void) {
780 LOGSECTION("rlalr");
781 unsigned f, k, n, s;
782 int flag;
783 int nf;
784 unsigned nt;
785 int *q, nq;
786 unsigned *p, *px;
787 int no_default;
788 tsd *spr = init_tsd(2);
789 tsd *sps = init_tsd(2);
790 tsd *discardedReductions = init_tsd(2);
791 int crc; /* conflict resolution count */
792 tsd *resolved_tokens = init_tsd(1);
793 unsigned char *stf = (unsigned char *) alloca(ntkns+1);
794
795
796 purge_ts = local_array(1,tsd);
797 no_default = error_token != 0 ||
798 !default_reductions ||
799 traditional_engine;
800 check_size(previous_states_list, n_gotos, n_gotos);
801 ivgtt();
802
803 if (key_list_dict != NULL) {
804 reset_list_dict(key_list_dict);
805 }
806 else {
807 key_list_dict = null_list_dict();
808 }
809 add_list_dict(zeros, 0, key_list_dict);
810
811 for (kits = 0; kits < nits; kits++) {
812 LOGV(kits) LCV(nits);
813 state_number_map *sp = &map_state_number[kits];
814 int sticky = sp->sticky;
815 int error_state = 0;
816
817 items = (unsigned *) dict_str(isht_dict, kits);
818 f = items[1];
819 n = items[2];
820 if (n > 0 && Rule(f).token(n-1) == Token(error_token)) {
821 error_state = 1;
822 }
823 crc = 0;
824 reset_tsd(sgt);
825 memset(tut, 0, sizeof(*tut) * (ntkns+1));
826 LOGS("tut zeroed");
827 bsgt();
828 if (tut[error_token]) {
829 error_state = 1;
830 }
831 if ((nf = sp->n_completed_forms) == 0) {
832 {
833 int n1, n2;
834 n1 = sp->n_gotos;
835 n2 = sp->n_chain_gotos;
836 nt = max(n1,n2);
837 n1 = sp->n_completions;
838 n2 = sp->n_chain_completions;
839 nt += max(n1,n2) + 1;
840 }
841 iws();
842 find_key_tokens(sgt->sb, sgt->nt,3);
843 k = tis();
844 if (k) {
845 k = add_list_dict(list_base, k, key_list_dict);
846 }
847 rws();
848 sp->key_list = k;
849 continue;
850 }
851 reset_tsd(srt);
852 kfrs = nf;
853 n = nf;
854 px = lstptr(*sp, completed_forms);
855 flag = 0;
856 int noDefaultOnNullProduction = 0;
857 while (n-- && (flag == 0)) {
858 Rule rule(frs = f = *px++);
859 RuleDescriptor &ruleDescriptor(rule);
860
861 flag = traditional_engine || error_state || !default_reductions;
862 if (flag) break;
863 //flag = noDefaultOnNullProduction = (nf == 1) && rule->length() == 0;
864 flag = noDefaultOnNullProduction =
865 (nf == 1) && ruleDescriptor.length() == 0;
866 if (flag) {
867 break;
868 }
869 //reduce_proc_flag = flag = rule->proc_name && !rule->immediate_proc;
870 reduce_proc_flag = flag =
871 ruleDescriptor.proc_name && !ruleDescriptor.immediate_proc;
872 /*|| noise_token; */
873 if ((no_default && reduce_proc_flag)) {
874 break;
875 }
876
877 find_followers(f);
878 p = (unsigned *) list_base;
879 nt = rws();
880 while (nt--) {
881 s = *p++;
882 if ((int) s == error_token) {
883 continue;
884 }
885 at(srt, s, f);
886 if (map_token_number[s].key || tut[s]) {
887 flag++;
888 break;
889 }
890 else {
891 tut[s] = (char) -1;
892 LOGV(tut[s]) LCV(s);
893 }
894 }
895 }
896 if (flag) {
897 LOGSECTION("Detailed resolution");
898 LOGV(noDefaultOnNullProduction);
899 flag = crc = 0;
900 memset(stf, 0, sizeof(*stf) * (ntkns+1));
901 memset(tut,0,sizeof(*tut) * (ntkns+1));
902 LOGS("tut zeroed") LCV(ntkns);
903 LOGV(tut[16]);
904 p = (unsigned *) sgt->sb;
905 nt = sgt->nt;
906 while (nt--){
907 s = *p;
908 assert(s <= ntkns);
909 tut[s]++;
910 LOGV(tut[s]) LCV(s);
911 stf[s]++;
912 p += 3;
913 }
914 LOGV(tut[16]);
915 reset_tsd(srt);
916 iws(); /* for list of tokens which have conflicts */
917 unsigned *unsortedForms = lstptr(*sp, completed_forms);
918 unsigned *sortedForms = local_array(nf, unsigned);
919 memcpy(sortedForms, unsortedForms, nf*sizeof(unsigned));
920 int i, j;
921 for (i = 0; i < nf; i++) {
922 for (j = i+1; j < nf; j++) {
923 if (sortedForms[i] > sortedForms[j]) {
924 unsigned temp = sortedForms[i];
925 sortedForms[i] = sortedForms[j];
926 sortedForms[j] = temp;
927 }
928 }
929 }
930 LOGV(tut[16]);
931 px = sortedForms;
932 while (nf--) {
933 int fpl;
934 int fra;
935 Rule rule(frs = f = *px++);
936 RuleDescriptor &ruleDescriptor(rule);
937 completed_form_map *mcf;
938
939 fpl = ruleDescriptor.precedence_level;
940 fra = ruleDescriptor.right_associative;
941
942 k = add_tuple_dict_new(completed_form_dict, kits, f);
943 check_size(map_completed_form, k, k*(nits+1)/(kits+1));
944 mcf = &map_completed_form[k];
945 if (mcf->reduction_states_index == 0) {
946 unsigned nrs;
947 extern int external_reduction;
948
949 frss12(kits, f, ruleDescriptor.length());
950 mcf = &map_completed_form[k];
951 mcf->external_reduction = external_reduction;
952 resize(reduction_states_list, tis());
953 mcf->reduction_states_index = store_list(reduction_states_list);
954 nrs = rws();
955 mcf->n_reduction_states = nrs;
956 }
957 LOGV(mcf->reduction_states_index);
958 if (mcf->reduction_states_index == 0) {
959 if(sit(srt, 0, f)) {
960 continue;
961 }
962 s = 0;
963 if (tut[s] > 0) {
964 tut[s] = - tut[s];
965 LOGV(s) LCV(tut[s]);
966 xws(s);
967 flag++;
968 continue;
969 }
970 else if (tut[s] < 0) {
971 continue;
972 }
973 tut[s]++;
974 LOGV(s) LCV(tut[s]);
975 continue;
976 }
977 p = lstptr(*mcf,reduction_states);
978 nt = mcf->n_reduction_states;
979 LOGV(f) LCV(nt);
980 iws();
981 while (nt--) {
982 int sn = *p++;
983 state_number_map *msn = &map_state_number[sn];
984 LOGV(sn);
985 if (sn == 0) {
986 xws(0);
987 }
988 else {
989 find_terminals(msn);
990 if (tis() == 0 && mcf->external_reduction) {
991 xws(0);
992 }
993 }
994 }
995 #ifdef INCLUDE_LOGGING
996 LOGS("terminals");
997 for (int i = 0; i < tis(); i++) {
998 LOGV(i) LCV(list_base[i]) LCV(tut[list_base[i]]);
999 }
1000 #endif
1001 {
1002 int *terminals;
1003 q = terminals = build_list();
1004 nq = fis();
1005 if (nq == 0) {
1006 continue;
1007 }
1008 while (nq--) {
1009 int sk;
1010
1011 s = *q++;
1012 LOGV(s) LCV(tut[s]);
1013 if ((int) s == error_token) {
1014 continue;
1015 }
1016 sk = map_token_number[s].key;
1017 LOGV(sk) LCV(sticky) LCV(distinguish_lexemes)
1018 LCV(disregard_skip_rule);
1019 LOGV(f) LCV(map_form_number[f].lexical);
1020 if (sk && !map_token_number[s].lexical && (
1021 sticky || (
1022 //!map_token_number[s].lexical &&
1023 distinguish_lexemes && (f == disregard_skip_rule
1024 || map_form_number[f].lexical)
1025 //) // || map_form_number[f].lexical)
1026 )
1027 )
1028 )
1029 {
1030 int c = *(unsigned char *) Keyword(sk)->string.pointer();
1031 assert(c >= min_char_number);
1032 int t = map_char_number[c - min_char_number].token_number;
1033 LOGV(c) LCV(t) LCV(stf[t]);
1034 if (stf[t]) continue;
1035 }
1036 if (sit(srt,s,f)) continue;
1037 LOGV(s) LCV(tut[s]);
1038 if (tut[s] > 0) {
1039 int spl = map_token_number[s].precedence_level;
1040 //int sla = map_token_number[s].left_associative;
1041 //int sra = map_token_number[s].right_associative;
1042 if (sticky || (fpl && spl)) {
1043 if (sticky || spl > fpl || (fra && spl == fpl)) {
1044 /* shift */
1045 LOGS("Shift") LCV(s) LCV(f);
1046 at(sps, s, f);
1047 }
1048 else {
1049 LOGS("Reduce") LCV(s) LCV(f);
1050 /* reduce */
1051 at(spr,s,f);
1052 }
1053 at(resolved_tokens, s);
1054 crc++;
1055 continue;
1056 }
1057 /*
1058 // not clear whether this should be done
1059 else if (sla) {
1060 LOGS("Shift -- left associative") LCV(s) LCV(f);
1061 at(sps, s, f);
1062 at(resolved_tokens, s);
1063 crc++;
1064 continue;
1065 }
1066 else if (sra) {
1067 LOGS("Reduce -- right associative") LCV(s) LCV(f);
1068 // reduce
1069 at(spr, s, f);
1070 at(resolved_tokens, s);
1071 crc++;
1072 continue;
1073 }
1074 */
1075 else if (disregardToken(s)) {
1076 if (f == disregard_skip_rule) {
1077 //LOGS("Reduce") LCV(s) LCV(f);
1078 //at(spr, s, f); /* reduce */
1079 LOGS("Shift") LCV(s) LCV(f);
1080 at(sps, s, f); /*shift */
1081 at(resolved_tokens, s);
1082 crc++;
1083 continue;
1084 }
1085 else if (f == disregard_cont_rule
1086 || map_form_number[f].lexical) {
1087 LOGS("Shift") LCV(s) LCV(f);
1088 at(sps, s, f); /*shift */
1089 at(resolved_tokens, s);
1090 crc++;
1091 continue;
1092 }
1093 }
1094
1095 else if (distinguish_lexemes && //!map_token_number[s].lexical &&
1096 (f == disregard_skip_rule
1097 || map_form_number[f].lexical))
1098 {
1099 LOGV(s) LCV(f);
1100 LOGS("Shift") LCV(s) LCV(f);
1101 at(sps, s, f); /* shift */
1102 continue;
1103 }
1104 xws(s);
1105 at(discardedReductions, s, f);
1106 LOGS("Discarding reduction") LCV(s) LCV(f);
1107 flag++;
1108 continue;
1109 }
1110 else if (tut[s] < 0) {
1111 xws(s);
1112 at(discardedReductions, s, f);
1113 LOGS("Discarding reduction") LCV(s) LCV(f);
1114 flag++;
1115 continue;
1116 }
1117 else {
1118 tut[s] = -1; // Assert this is a reducing token
1119 LOGV(s) LCV(tut[s]);
1120 }
1121 }
1122 DEALLOCATE(terminals);
1123 }
1124 }
1125 if (flag) {
1126 logcon(unres_con, list_base, tis());
1127 }
1128 rws();
1129 }
1130 if (crc) {
1131 logcon(res_con, resolved_tokens->sb, resolved_tokens->nt);
1132 purge_tsd(srt, sps);
1133 purge_gotos(spr);
1134 log_prr(sps, spr);
1135 reset_tsd(spr);
1136 reset_tsd(sps);
1137 }
1138 if (sps->nt) {
1139 purge_tsd(srt, sps);
1140 reset_tsd(sps);
1141 }
1142 if (discardedReductions->nt) {
1143 purge_tsd(srt, discardedReductions);
1144 reset_tsd(discardedReductions);
1145 }
1146 reset_tsd(resolved_tokens);
1147 iws();
1148 find_key_tokens(sgt->sb, sgt->nt, 3);
1149 find_key_tokens(srt->sb, srt->nt, 2);
1150 k = tis();
1151 if (k) {
1152 k = add_list_dict(list_base, k, key_list_dict);
1153 }
1154 sp->key_list = k;
1155 rws();
1156 if (error_state || (no_default && reduce_proc_flag) ||
1157 !default_reductions ||
1158 noDefaultOnNullProduction ||
1159 traditional_engine ||
1160 kfrs != 1) {
1161 p = (unsigned *) srt->sb;
1162 nt = srt->nt;
1163 resize(reductions_list, nt);
1164 sp->reductions_index = store_tuples(srt,reductions_list);
1165 sp->n_reductions = nt;
1166 n_reductions += nt;
1167 }
1168 else {
1169 n_default_reductions++;
1170 }
1171 {
1172 int n1, n2;
1173 n1 = sp->n_gotos;
1174 n2 = sp->n_chain_gotos;
1175 nt = max(n1, n2);
1176 n1 = sp->n_completions;
1177 n2 = sp->n_chain_completions;
1178 nt += max(n1, n2) + 1;
1179 }
1180 nt += sp->n_reductions;
1181 }
1182 LOGS("rlalr state loop complete");
1183 LOGV(previous_states_list[0]);
1184 previous_states_list = reset_list(previous_states_list,
1185 previous_states_list[0]);
1186 ivgtt();
1187 delete_tsd(resolved_tokens);
1188 delete_tsd(spr);
1189 delete_tsd(sps);
1190 delete_tsd(discardedReductions);
1191 //close_list_dict(key_list_dict);
1192 //LOGS("list dict closed");
1193 }
1194