1 /*
2 * mrhoist.c
3 *
4 * SOFTWARE RIGHTS
5 *
6 * We reserve no LEGAL rights to the Purdue Compiler Construction Tool
7 * Set (PCCTS) -- PCCTS is in the public domain. An individual or
8 * company may do whatever they wish with source code distributed with
9 * PCCTS or the code generated by PCCTS, including the incorporation of
10 * PCCTS, or its output, into commerical software.
11 *
12 * We encourage users to develop software with PCCTS. However, we do ask
13 * that credit is given to us for developing PCCTS. By "credit",
14 * we mean that if you incorporate our source code into one of your
15 * programs (commercial product, research project, or otherwise) that you
16 * acknowledge this fact somewhere in the documentation, research report,
17 * etc... If you like PCCTS and have developed a nice tool with the
18 * output, please mention that you developed it using PCCTS. In
19 * addition, we ask that this header remain intact in our source code.
20 * As long as these guidelines are kept, we expect to continue enhancing
21 * this system and expect to make other tools available as they are
22 * completed.
23 *
24 * ANTLR 1.33MR10
25 *
26 */
27
28 #include <stdio.h>
29
30 #include "pcctscfg.h"
31
32 #include "set.h"
33 #include "syn.h"
34 #include "hash.h"
35 #include "generic.h"
36 #include "dlgdef.h"
37 #include <ctype.h>
38
39 #ifdef __USE_PROTOS
40 void dumppred(Predicate *);
41 #else
42 void dumppred();
43 #endif
44
45 /*
46 Try to determine whether predicate "first" is true for
47 all cases where "second" is true. Comparison takes place
48 without regard to context.
49 Assumes that predicate symbols have been expanded.
50 Assumes that there are no NAND or NOR nodes
51
52 */
53
54 #ifdef __USE_PROTOS
MR_secondPredicateUnreachable(Predicate * first,Predicate * second)55 int MR_secondPredicateUnreachable(Predicate *first,Predicate *second)
56 #else
57 int MR_secondPredicateUnreachable(first,second)
58 Predicate *first;
59 Predicate *second;
60 #endif
61 {
62 Predicate *f;
63 Predicate *s;
64
65 if (first == NULL) {
66 return 1;
67 } else if (second == NULL) {
68 return 0;
69 } else if (first->down == NULL && second->down == NULL) {
70 if (first->source == second->source &&
71 first->inverted == second->inverted) {
72 return 1; /* look identical - will never reach alt2 */
73 } else {
74 return 0; /* look different */
75 };
76 } else if (first->down == NULL && second->down != NULL) {
77
78 if (second->expr == PRED_AND_LIST) {
79
80 /* unreachable if first covers any child of second */
81
82 for (s=second->down; s != NULL; s=s->right) {
83 if (MR_secondPredicateUnreachable(first,s)) {
84 return 1;
85 };
86 };
87 return 0;
88 } else if (second->expr == PRED_OR_LIST) {
89
90 /* unreachable if first covers every child of second */
91
92 for (s=second->down; s != NULL; s=s->right) {
93 if (!MR_secondPredicateUnreachable(first,s)) {
94 return 0;
95 };
96 };
97 return 1;
98 } else {
99 require (0,"Illegal pred->expr");
100 return 0; /* MR20 Make compiler happy */
101 };
102 } else if (first->down != NULL && second->down == NULL) {
103 if (first->expr == PRED_AND_LIST) {
104
105 /* unreachable if every child of first covers second */
106
107 for (f=first->down; f != NULL; f=f->right) {
108 if (!MR_secondPredicateUnreachable(f,second)) {
109 return 0;
110 };
111 };
112 return 1;
113 } else if (first->expr == PRED_OR_LIST) {
114
115 /* unreachable if any child of first covers second */
116
117 for (f=first->down; f != NULL; f=f->right) {
118 if (MR_secondPredicateUnreachable(f,second)) {
119 return 1;
120 };
121 };
122 return 0;
123 } else {
124 require (0,"Illegal predicate->expr");
125 return 0; /* MR20 Make compiler happy */
126 };
127 } else {
128
129 if (first->expr == PRED_AND_LIST && second->expr == PRED_AND_LIST) {
130
131 /* unreachable if each child of first covers at least one child of second */
132
133 for (f=first->down; f != NULL ; f=f->right) {
134 for (s=second->down; s != NULL ; s=s->right) {
135 if (MR_secondPredicateUnreachable(f,s)) goto A_next_f;
136 };
137 return 0;
138 A_next_f:
139 continue;
140 };
141 return 1;
142
143 } else if (first->expr == PRED_AND_LIST && second->expr == PRED_OR_LIST) {
144
145 /* unreachable if each child of first covers ALL of second's children */
146
147 for (f=first->down; f != NULL ; f=f->right) {
148 for (s=second->down; s != NULL ; s=s->right) {
149 if (!MR_secondPredicateUnreachable(f,s)) return 0;
150 };
151 };
152 return 1;
153
154 } else if (first->expr == PRED_OR_LIST && second->expr == PRED_AND_LIST) {
155
156 /* unreachable if any child of second is covered by any child of first */
157
158 for (f=first->down; f != NULL ; f=f->right) {
159 for (s=second->down; s != NULL ; s=s->right) {
160 if (MR_secondPredicateUnreachable(f,s)) return 1;
161 };
162 };
163 return 0;
164
165 } else if (first->expr == PRED_OR_LIST && second->expr == PRED_OR_LIST) {
166
167 /* unreachable if every child of second is covered by some child of first */
168
169 for (f=first->down; f != NULL ; f=f->right) {
170 for (s=second->down; s != NULL ; s=s->right) {
171 if (MR_secondPredicateUnreachable(f,s)) goto B_next_f;
172 };
173 return 0;
174 B_next_f:
175 continue;
176 };
177 return 1;
178
179 } else {
180 require (0,"Illegal predicate->expr");
181 return 0; /* MR20 Make compiler happy */
182 };
183 };
184 return 0; /* MR20 MSVC 5.0 complains about missing return statement */
185 }
186
187 #ifdef __USE_PROTOS
MR_xxxIndent(FILE * f,int depth)188 void MR_xxxIndent(FILE *f,int depth)
189 #else
190 void MR_xxxIndent(f,depth)
191 FILE *f;
192 int depth;
193 #endif
194 {
195 int i;
196
197 for (i=0; i<depth ; i++) {
198 fprintf(f," ");
199 };
200 }
201
202 #ifdef __USE_PROTOS
MR_stderrIndent(int depth)203 void MR_stderrIndent(int depth)
204 #else
205 void MR_stderrIndent(depth)
206 int depth;
207 #endif
208 {
209 MR_xxxIndent(stderr,depth);
210 }
211
212 #ifdef __USE_PROTOS
MR_outputIndent(int depth)213 void MR_outputIndent(int depth)
214 #else
215 void MR_outputIndent(depth)
216 int depth;
217 #endif
218 {
219 MR_xxxIndent(output,depth);
220 }
221
222 #ifdef __USE_PROTOS
MR_set_reuse(set * s)223 void MR_set_reuse(set *s)
224 #else
225 void MR_set_reuse(s)
226 set *s;
227 #endif
228 {
229 set_free(*s);
230 *s=empty;
231 }
232
233 #ifdef __USE_PROTOS
MR_dumpPredRuleRefStack(FILE * iounit,int indent)234 void MR_dumpPredRuleRefStack(FILE *iounit,int indent)
235 #else
236 void MR_dumpPredRuleRefStack(iounit,indent)
237 FILE *iounit;
238 int indent;
239 #endif
240 {
241 int i;
242 int j;
243 int count=MR_PredRuleRefStack.count;
244 RuleRefNode *rrn=NULL;
245 Junction *lastOne;
246
247 if (count == 0) {
248 fprintf(iounit,"empty\n");
249 return;
250 };
251 for (i=0; i < count; i++) {
252 rrn=(RuleRefNode *) MR_PredRuleRefStack.data[i];
253 for (j=0; j<indent; j++) fprintf(iounit," ");
254 fprintf(iounit,"#%-2d in rule %s (line %d %s) to rule %s\n",
255 i,rrn->rname,rrn->line,FileStr[rrn->file],rrn->text);
256 };
257 lastOne=MR_ruleReferenced(rrn);
258 if (lastOne != NULL) {
259 for (j=0; j<indent; j++) fprintf(iounit," ");
260 fprintf(iounit,"#%-2d in rule %s (line %d %s)\n",
261 count,lastOne->rname,lastOne->line,FileStr[lastOne->file]);
262 };
263 }
264
265 #ifdef __USE_PROTOS
MR_dumpTreeF(FILE * f,int depth,Tree * tree,int across)266 void MR_dumpTreeF(FILE *f,int depth,Tree *tree,int across)
267 #else
268 void MR_dumpTreeF(f,depth,tree,across)
269 FILE *f;
270 Tree *tree;
271 int depth;
272 int across;
273 #endif
274 {
275 int newAcross=across;
276
277 if (tree == NULL ) return;
278 if (tree->down != NULL ) {
279 fprintf(output,"\n");
280 MR_outputIndent(depth);
281 fprintf(output, "(root =");
282 };
283 if (tree->token == ALT ) {
284 fprintf(output," %-16s","Alt");
285 } else if (tree->token==EpToken ) {
286 fprintf(output,"(%d)%13s",tree->v.rk," ");
287 } else {
288 fprintf(output," %-16s",TerminalString(tree->token));
289 };
290 if (tree->down != NULL) {
291 fprintf(output,"\n");
292 MR_outputIndent(depth+1);
293 MR_dumpTreeF(f,depth+1,tree->down,1);
294 newAcross=0;
295 fprintf(output,"\n");
296 MR_outputIndent(depth);
297 fprintf(output,")");
298 };
299 if (newAcross > 3) {
300 fprintf(output,"\n");
301 MR_outputIndent(depth);
302 newAcross=0;
303 };
304 MR_dumpTreeF(f,depth,tree->right,newAcross+1);
305 }
306
307 #ifdef __USE_PROTOS
MR_dumpTreeX(int depth,Tree * tree,int across)308 void MR_dumpTreeX(int depth,Tree *tree,int across)
309 #else
310 void MR_dumpTreeX(depth,tree,across)
311 Tree *tree;
312 int depth;
313 int across;
314 #endif
315 {
316 MR_dumpTreeF(output,depth,tree,across);
317 }
318
319 #ifdef __USE_PROTOS
MR_dumpTokenSet(FILE * f,int depth,set s)320 void MR_dumpTokenSet(FILE *f,int depth,set s)
321 #else
322 void MR_dumpTokenSet(f,depth,s)
323 FILE *f;
324 int depth;
325 set s;
326 #endif
327 {
328 int i;
329 int j;
330
331 unsigned *pdq;
332
333 if (set_nil(s)) {
334 fprintf(f,"\n");
335 MR_xxxIndent(f,depth+1);
336 fprintf(f,"nil\n");
337 return;
338 };
339
340 pdq=set_pdq(s);
341 require(pdq != NULL,"set_pdq failed");
342 i=0;
343 for (i=0 ; ; i=i+4) {
344 fprintf(f,"\n");
345 MR_xxxIndent(f,depth+1);
346 for (j=0; j < 4 ; j++) {
347 if (pdq[i+j] == nil) break;
348 fprintf(f," %-16s",TerminalString(pdq[i+j]));
349 };
350 if (pdq[i+j] == nil) break;
351 };
352 fprintf(f,"\n");
353 free( (char *) pdq);
354 }
355
356 #ifdef __USE_PROTOS
MR_dumpPred1(int depth,Predicate * p,int withContext)357 void MR_dumpPred1(int depth,Predicate *p,int withContext)
358 #else
359 void MR_dumpPred1(depth,p,withContext)
360 int depth;
361 Predicate *p;
362 int withContext;
363 #endif
364 {
365 unsigned k;
366
367 if (p == NULL) {
368 MR_outputIndent(depth);
369 fprintf(output,"The predicate is empty (or always true)\n\n");
370 return;
371 };
372 if (p->down != NULL) {
373 MR_outputIndent(depth);
374 if (p->inverted) {
375
376 /* MR14a Left out print expression in fprintf
377 Reported by Manuel Kessler (mlkessle@cip.physik.uni-wuerzburg.de)
378 */
379
380 if (p->expr == PRED_AND_LIST) fprintf(output,"%s NAND (not AND) expr\n\n",p->expr);
381 if (p->expr == PRED_OR_LIST) fprintf(output,"%s NOR (not OR) expr\n\n",p->expr);
382 } else {
383 fprintf(output,"%s expr\n\n",p->expr);
384 };
385 } else {
386 MR_outputIndent(depth);
387 fprintf(output,"pred %s <<%s>>?\n",
388 (p->inverted ? " *not*" : ""),
389 (p->expr == NULL ? "null expr" : p->expr));
390 MR_outputIndent(depth+1);
391 fprintf(output," ");
392 fprintf(output," depth=k=%d",p->k);
393 if (p->source != NULL && p->source->guardpred) {
394 fprintf(output," (\"=>\" guard)");
395 }
396 if (p->source != NULL && p->source->ampersandPred != NULL) {
397 fprintf(output," (\"&&\" guard)");
398 };
399 k=set_int(p->completionSet);
400 if (k != nil) {
401 fprintf(output," Incomplete Set at k=%d !",k);
402 };
403 k=set_int(p->completionTree);
404 if (k != nil) {
405 fprintf(output," Incomplete Tree at k=%d !",k);
406 };
407 if (p->source != NULL) {
408 fprintf(output," rule %s line %d %s",
409 p->source->rname,p->source->line,FileStr[p->source->file]);
410 };
411 fprintf(output,"\n");
412 if (withContext &&
413 (HoistPredicateContext ||
414 ! set_nil(p->scontext[1]) ||
415 p->tcontext != NULL)) {
416 if (p->k == 1) {
417 MR_outputIndent(depth+1);
418 fprintf(output,"set context: ");
419 MR_dumpTokenSet(output,depth+1,p->scontext[1]);
420 }
421 if (p->k != 1) {
422 MR_outputIndent(depth+1);
423 fprintf(output,"tree context:");
424 if (p->tcontext == NULL) {
425 fprintf(output," null");
426 } else {
427 MR_dumpTreeX(depth+2,p->tcontext,0);
428 };
429 fprintf(output,"\n");
430 };
431 };
432 fprintf(output,"\n");
433 };
434 if (p->down != NULL) {
435 MR_dumpPred1(depth+1,p->down,withContext);
436 };
437 if (p->right != NULL) {
438 MR_dumpPred1(depth,p->right,withContext);
439 };
440 }
441
442 #ifdef __USE_PROTOS
MR_dumpPred(Predicate * p,int withContext)443 void MR_dumpPred(Predicate *p,int withContext)
444 #else
445 void MR_dumpPred(p,withContext)
446 Predicate *p;
447 int withContext;
448 #endif
449 {
450 MR_dumpPred1(0,p,withContext);
451 }
452
453 #ifdef __USE_PROTOS
MR_make_tree_from_set(set s)454 Tree * MR_make_tree_from_set(set s)
455 #else
456 Tree * MR_make_tree_from_set(s)
457 set s;
458 #endif
459 {
460 Tree *t=NULL;
461 Tree *node;
462 Tree **tp=&t;
463 int i;
464
465 unsigned *pdq=set_pdq(s);
466
467 if (pdq != NULL) {
468 for (i=0 ; pdq[i] != nil ; i++) {
469 node=tnode( (int) pdq[i]);
470 *tp=node;
471 tp=&(node->right);
472 };
473 *tp=NULL;
474 free ( (char *) pdq);
475 };
476 return t;
477 }
478
479 #ifdef __USE_PROTOS
MR_check_pred_too_long(Predicate * p,set completion)480 void MR_check_pred_too_long(Predicate *p,set completion)
481 #else
482 void MR_check_pred_too_long(p,completion)
483 Predicate *p;
484 set completion;
485 #endif
486 {
487 if (p != NULL &&
488 p->source != NULL &&
489 ! p->source->predTooLong) {
490 if ( !set_nil(completion)) {
491 p->source->predTooLong=1;
492 warnFL("It is unusual (but ok) for a semantic predicate to test context past the end of its own rule",
493 FileStr[p->source->file],p->source->line);
494 };
495 };
496 }
497
498 #ifdef __USE_PROTOS
MR_predicate_context_completed(Predicate * p)499 int MR_predicate_context_completed(Predicate *p)
500 #else
501 int MR_predicate_context_completed(p)
502 Predicate *p;
503 #endif
504 {
505 if (p == NULL) return 1;
506 if (p->expr != PRED_AND_LIST &&
507 p->expr != PRED_OR_LIST) {
508 if ( ! set_nil(p->completionSet)) return 0;
509 if ( ! set_nil(p->completionTree)) return 0;
510 };
511 return MR_predicate_context_completed(p->down) &
512 MR_predicate_context_completed(p->right);
513 }
514
515 #ifdef __USE_PROTOS
MR_advance(Node * n)516 Node * MR_advance(Node *n)
517 #else
518 Node * MR_advance(n)
519 Node *n;
520 #endif
521 {
522 if (n == NULL) return NULL;
523 switch (n->ntype) {
524 case nJunction: return ((Junction *)n)->p1;
525 case nToken: return ((TokNode *)n)->next;
526 case nRuleRef: return ((RuleRefNode *)n)->next;
527 case nAction: return ((ActionNode *)n)->next;
528 default: return NULL;
529 };
530 return NULL; /* MSVC 5.0 complains about missing return statement */
531 }
532
533 #ifdef __USE_PROTOS
MR_find_endRule(Node * n)534 Junction * MR_find_endRule(Node *n)
535 #else
536 Junction * MR_find_endRule(n)
537 Node *n;
538 #endif
539 {
540 Node *next;
541 if (n == NULL) return NULL;
542 for (next=n; next != NULL; next=MR_advance(next)) {
543 if (next->ntype == nJunction &&
544 ( (Junction *) next)->jtype == EndRule) {
545 break;
546 };
547 };
548 return (Junction *)next;
549 }
550
551 /*
552 Intersection: a branch which is shorter is chosen
553 over one which is longer: (A B C) intersect (A B) yields (A B).
554
555 AND: a branch which is longer is chosen over the one
556 which is shorter: (A B C) AND (A B) yields (A B C)
557
558 */
559
560 #ifdef __USE_PROTOS
MR_computeTreeIntersection(Tree * l,Tree * r)561 Tree *MR_computeTreeIntersection(Tree *l,Tree *r)
562 #else
563 Tree *MR_computeTreeIntersection(l,r)
564 Tree *l;
565 Tree *r;
566 #endif
567 {
568 Tree *result=NULL;
569 Tree **tail;
570 Tree *p;
571 Tree *q;
572 Tree *match;
573
574 if (l == NULL || r == NULL) return NULL;
575 for (p=l; p != NULL; p=p->right) {
576 require(p->token != EpToken,"MR_computeTreeIntersection: p->EpToken unexpected\n");
577 require (p->token != ALT,"MR_computeTreeIntersection: p->ALT unexpected\n");
578 };
579 for (q=r; q != NULL; q=q->right) {
580 require(q->token != EpToken,"MR_computeTreeIntersection: q->EpToken unexpected\n");
581 require(q->token != ALT,"MR_computeTreeIntersection: q->ALT unexpected\n");
582 };
583
584 result=tnode(ALT);
585 tail=&(result->down);
586
587 for (p=l; p != NULL ; p=p->right) {
588 for (q=r; q != NULL ; q=q->right) {
589 if (p->token == q->token) {
590 match=tnode(p->token);
591 match->down=MR_computeTreeIntersection(p->down,q->down);
592 *tail=match;
593 tail=&(match->right);
594 };
595 };
596 };
597
598 *tail=NULL;
599 result=tshrink(result);
600 result=tflatten( result );
601 result=tleft_factor( result );
602 return result;
603 }
604
605 /* the predicates which are ANDed together have a common
606 context: they must all have common roots. Thus the
607 AND operation is more like an OR operation because
608 branches which are longer are grafted onto shorter
609 branches of the AND tree. For instance combining
610 (A B C) with (A B C D) gives (A B C D). There
611 should never be a case of (A B C) and (A B D) because
612 they have the same context.
613
614 Actually, this may not be true once one throws in
615 guard predicates which are defined by the user, not
616 the context.
617 */
618
619 /* requires input trees to be in "canonical" format */
620
621 #ifdef __USE_PROTOS
MR_computeTreeAND(Tree * l,Tree * r)622 Tree *MR_computeTreeAND(Tree *l,Tree *r)
623 #else
624 Tree *MR_computeTreeAND(l,r)
625 Tree *l;
626 Tree *r;
627 #endif
628 {
629 Tree *result=NULL;
630 Tree **tail;
631 Tree *p;
632 Tree *q;
633 Tree *match;
634
635 if (l == NULL) return tdup(r);
636 if (r == NULL) return tdup(l);
637
638 for (p=l; p != NULL; p=p->right) {
639 /**** require(p->token != EpToken,"MR_computeTreeAND: p->EpToken unexpected\n"); ****/
640 require (p->token != ALT,"MR_computeTreeAND: p->ALT unexpected\n");
641 };
642 for (q=r; q != NULL; q=q->right) {
643 /**** require(q->token != EpToken,"MR_computeTreeAND: q->EpToken unexpected\n"); ****/
644 require(q->token != ALT,"MR_computeTreeAND: q->ALT unexpected\n");
645 };
646
647 result=tnode(ALT);
648 tail=&(result->down);
649
650 for (p=l; p != NULL ; p=p->right) {
651 for (q=r; q != NULL ; q=q->right) {
652 if (p->token == q->token) {
653 match=tnode(p->token);
654 match->down=MR_computeTreeAND(p->down,q->down);
655 *tail=match;
656 tail=&(match->right);
657 };
658 };
659 };
660
661 *tail=NULL;
662 result=tshrink(result);
663 result=tflatten( result );
664 result=tleft_factor( result );
665 return result;
666 }
667
668 #ifdef __USE_PROTOS
MR_union_plain_sets1(Predicate * p,set * theUnion)669 void MR_union_plain_sets1(Predicate *p,set *theUnion)
670 #else
671 void MR_union_plain_sets1(p,theUnion)
672 Predicate *p;
673 set *theUnion;
674 #endif
675 {
676 if (p == NULL) return;
677 MR_union_plain_sets1(p->down,theUnion);
678 MR_union_plain_sets1(p->right,theUnion);
679 set_orin(theUnion,p->plainSet);
680 return;
681 }
682
683 #ifdef __USE_PROTOS
MR_union_plain_sets(Predicate * p)684 set MR_union_plain_sets(Predicate *p)
685 #else
686 set MR_union_plain_sets(p)
687 Predicate *p;
688 #endif
689 {
690 set theUnion;
691
692 theUnion=empty;
693
694 MR_union_plain_sets1(p,&theUnion);
695 return theUnion;
696 }
697
698 /* does NOT left factor: do not want to merge
699 (A B) with (A) to get (A B)
700 in fact the opposite: (A B) with (A) gives (A)
701 */
702
703 #ifdef __USE_PROTOS
MR_compute_pred_tree_ctxXX(Predicate * p)704 Tree *MR_compute_pred_tree_ctxXX(Predicate *p)
705 #else
706 Tree *MR_compute_pred_tree_ctxXX(p)
707 Predicate *p;
708 #endif
709 {
710 Tree *result=NULL;
711 Predicate *q;
712 Tree *t;
713
714 if (p == NULL) return NULL;
715
716 /* this appears strange: why do we OR the context
717 of and AND predicate ? It is because of the way
718 that predicates are evaluated: if the context is
719 wrong then it's the same as if the predicate was
720 true. That means that even when one leg of an
721 AND has unmatched context, if the other leg has
722 matched context and is true then the predicate
723 succeeds. It's only when all the legs have unmatched
724 context that this one can skip evaluation of the
725 predicates.
726 */
727 if (p->expr == PRED_OR_LIST ||
728 p->expr == PRED_AND_LIST) {
729 for (q=p->down; q != NULL ; q=q->right) {
730 t=MR_compute_pred_tree_ctxXX(q);
731 result=tappend(result,t);
732 t=NULL;
733 };
734
735 result=tshrink(result);
736 result=tflatten( result );
737
738 /* does NOT left factor: do not want to merge
739 (A B) with (A) to get (A B)
740 in fact the opposite: (A B) with (A) gives (A)
741 */
742
743 /**** result=tleft_factor( result ); ****/
744 return result;
745 };
746
747 #if 0
748 ** if (p->expr == PRED_AND_LIST) {
749 **
750 ** Predicate *l;
751 ** Predicate *r;
752 ** Tree *l1;
753 ** Tree *r1;
754 ** Tree *prevl1;
755 **
756 ** l=p->down;
757 ** require (l->right != NULL,"MR_compute_pred_tree - AND has only one child");
758 **
759 **/* l1 and r1 should already be in "canonical" format */
760 **
761 ** l1=MR_compute_pred_tree(l);
762 ** for (r=l->right; r != NULL; r=r->right) {
763 ** r1=MR_compute_pred_tree(r);
764 ** prevl1=l1;
765 ** l1=MR_computeTreeAND(l1,r1);
766 ** Tfree(r1);
767 ** Tfree(prevl1);
768 ** };
769 **
770 **/* result from computeTreeAND should be in "canonical" format */
771 **
772 ** result=l1;
773 **
774 **/* result of MR_computeTreeAND should be in "canonical" format */
775 **
776 ** return result;
777 ** };
778 #endif
779
780 if (p->k == 1) {
781 result=MR_make_tree_from_set(p->scontext[1]);
782 } else {
783 result=tdup(p->tcontext);
784 result=MR_remove_epsilon_from_tree(result);
785 result=tshrink(result);
786 result=tflatten(result);
787 result=tleft_factor(result);
788 };
789 return result;
790 }
791
792 #ifdef __USE_PROTOS
MR_pred_depth(Predicate * p,int * maxDepth)793 void MR_pred_depth(Predicate *p,int *maxDepth)
794 #else
795 void MR_pred_depth(p,maxDepth)
796 Predicate *p;
797 int *maxDepth;
798 #endif
799 {
800 if (p == NULL) return;
801 if (p->expr != PRED_OR_LIST &&
802 p->expr != PRED_AND_LIST) {
803 if (p->k > *maxDepth) *maxDepth=p->k;
804 };
805 MR_pred_depth(p->down,maxDepth);
806 MR_pred_depth(p->right,maxDepth);
807 }
808
809 /* this computes the OR of all the contexts */
810
811 #ifdef __USE_PROTOS
MR_compute_pred_set(Predicate * p)812 set MR_compute_pred_set(Predicate *p)
813 #else
814 set MR_compute_pred_set(p)
815 Predicate *p;
816 #endif
817 {
818 set result;
819 Predicate *q;
820
821 result=empty;
822
823 if (p == NULL) return empty;
824
825 if (p->expr == PRED_OR_LIST ||
826 p->expr == PRED_AND_LIST) { /* yes, I do mean PRED_AND_LIST ! */
827 /* remember: r1: (A)? => <<p>>? r2; */
828 /* r2: (B)? => <<q>>? r3; */
829 set t;
830
831 t=empty;
832 result=empty;
833
834 for (q=p->down; q != NULL; q=q->right) {
835 t=MR_compute_pred_set(q);
836 set_orin(&result,t);
837 set_free(t);
838 };
839 return result;
840 } else if (p->k > 1) {
841 return empty;
842 } else {
843 return set_dup(p->scontext[1]);
844 };
845 }
846
847 #ifdef __USE_PROTOS
MR_First(int ck,Junction * j,set * incomplete)848 set MR_First(int ck,Junction *j,set *incomplete)
849 #else
850 set MR_First(ck,j,incomplete)
851 int ck;
852 Junction *j;
853 set *incomplete;
854 #endif
855 {
856 Junction *p;
857 set tokensUsed;
858
859 tokensUsed=empty;
860
861 require(j->ntype==nJunction, "MR_First: non junction passed");
862
863 p = analysis_point((Junction *)j->p1);
864
865 REACH(p,ck,incomplete,tokensUsed);
866
867 return tokensUsed;
868 }
869
870 #ifdef __USE_PROTOS
MR_cleanup_pred_trees(Predicate * p)871 void MR_cleanup_pred_trees(Predicate *p)
872 #else
873 void MR_cleanup_pred_trees(p)
874 Predicate *p;
875 #endif
876 {
877 Tree *t;
878
879 if (p == NULL) return;
880 if (p->expr != PRED_OR_LIST &&
881 p->expr != PRED_AND_LIST) {
882 t=p->tcontext;
883 t=tshrink(t);
884 t=tflatten(t);
885 t=tleft_factor(t);
886 p->tcontext=t;
887 };
888 MR_cleanup_pred_trees(p->down);
889 MR_cleanup_pred_trees(p->right);
890 }
891
892 /* does NOT return canonical tree */
893
894 #ifdef __USE_PROTOS
MR_remove_epsilon_from_tree(Tree * t)895 Tree * MR_remove_epsilon_from_tree(Tree *t)
896 #else
897 Tree * MR_remove_epsilon_from_tree(t)
898 Tree *t;
899 #endif
900 {
901 if (t == NULL) return NULL;
902
903 /* I think ALT can be ignored as a special case */
904
905 if (t->token != EpToken) {
906 t->down=MR_remove_epsilon_from_tree(t->down);
907 t->right=MR_remove_epsilon_from_tree(t->right);
908 return t;
909 } else {
910 Tree *u;
911 u=MR_remove_epsilon_from_tree(t->right);
912 t->right=NULL;
913 Tfree(t);
914 return u;
915 };
916 }
917
918 #ifdef __USE_PROTOS
MR_complete_set(int predDepth,set * tokensUsed,set * incomplete)919 void MR_complete_set(int predDepth,set *tokensUsed,set *incomplete)
920 #else
921 void MR_complete_set(predDepth,tokensUsed,incomplete)
922 int predDepth;
923 set *tokensUsed;
924 set *incomplete;
925 #endif
926 {
927 int i;
928 RuleRefNode *ruleRef;
929 set rk2;
930 set b;
931 int k2;
932 Junction *save_MR_RuleBlkWithHalt;
933
934 if (set_int(*incomplete) > (unsigned) predDepth) {
935 return;
936 };
937
938 require(MR_PredRuleRefStack.count == MR_RuleBlkWithHaltStack.count,
939 "RuleRefStack and RuleBlkWithHaltStack not same size");
940
941 require(MR_RuleBlkWithHalt == NULL ||
942 (MR_RuleBlkWithHalt->jtype == RuleBlk && MR_RuleBlkWithHalt->end->halt == TRUE),
943 "RuleBlkWithHalt has no halt set");
944
945 save_MR_RuleBlkWithHalt=MR_RuleBlkWithHalt;
946
947 if (MR_RuleBlkWithHalt != NULL) {
948 MR_RuleBlkWithHalt->end->halt=FALSE;
949 };
950
951 for (i=MR_PredRuleRefStack.count-1; i >= 0 ; i--) {
952 ruleRef=(RuleRefNode *)MR_PredRuleRefStack.data[i];
953 if (ruleRef == NULL) continue;
954
955 MR_RuleBlkWithHalt=(Junction *)MR_RuleBlkWithHaltStack.data[i];
956 if (MR_RuleBlkWithHalt != NULL) MR_RuleBlkWithHalt->end->halt=TRUE;
957
958 rk2=empty;
959 b=empty;
960
961 while ( !set_nil(*incomplete) ) {
962 k2=set_int(*incomplete);
963 if (k2 > predDepth) break; /* <=== another exit from loop */
964 set_rm(k2,*incomplete);
965 REACH(ruleRef->next,k2,&rk2,b);
966 set_orin(tokensUsed,b);
967 set_free(b);
968 };
969
970 if (MR_RuleBlkWithHalt != NULL) MR_RuleBlkWithHalt->end->halt=FALSE;
971
972 set_orin(incomplete,rk2); /* remember what we couldn't do */
973 set_free(rk2);
974 if (set_int(*incomplete) > (unsigned) predDepth) break; /* <=== another exit from loop */
975 };
976
977 MR_RuleBlkWithHalt=save_MR_RuleBlkWithHalt;
978 if (MR_RuleBlkWithHalt != NULL) {
979 MR_RuleBlkWithHalt->end->halt=TRUE;
980 };
981 }
982
983 #ifdef __USE_PROTOS
MR_complete_tree(int predDepth,Tree ** t,set * incomplete)984 void MR_complete_tree(int predDepth,Tree **t,set *incomplete)
985 #else
986 void MR_complete_tree(predDepth,t,incomplete)
987 int predDepth;
988 Tree **t;
989 set *incomplete;
990 #endif
991 {
992 int i;
993 RuleRefNode *ruleRef;
994 set rk2;
995 Tree *u;
996 unsigned k2;
997 Junction *save_MR_RuleBlkWithHalt;
998 int saveConstrainSearch;
999
1000 if (set_int(*incomplete) > (unsigned) predDepth) {
1001 return;
1002 };
1003
1004 require(MR_PredRuleRefStack.count == MR_RuleBlkWithHaltStack.count,
1005 "RuleRefStack and RuleBlkWithHaltStack not same size");
1006
1007 require(MR_RuleBlkWithHalt == NULL ||
1008 (MR_RuleBlkWithHalt->jtype == RuleBlk && MR_RuleBlkWithHalt->end->halt == TRUE),
1009 "RuleBlkWithHalt has no halt set");
1010
1011 save_MR_RuleBlkWithHalt=MR_RuleBlkWithHalt;
1012 saveConstrainSearch=ConstrainSearch;
1013 ConstrainSearch=0;
1014
1015 if (MR_RuleBlkWithHalt != NULL) {
1016 MR_RuleBlkWithHalt->end->halt=FALSE;
1017 };
1018
1019 for (i=MR_PredRuleRefStack.count-1; i >= 0 ; i--) {
1020 ruleRef=(RuleRefNode *)MR_PredRuleRefStack.data[i];
1021 if (ruleRef == NULL) continue;
1022
1023 MR_RuleBlkWithHalt=(Junction *)MR_RuleBlkWithHaltStack.data[i];
1024
1025 if (MR_RuleBlkWithHalt != NULL) MR_RuleBlkWithHalt->end->halt=TRUE;
1026
1027 rk2=empty;
1028
1029 while ( !set_nil(*incomplete) ) {
1030 k2 = set_int(*incomplete);
1031 if (k2 > (unsigned) predDepth) break; /* <=== another exit from loop */
1032 set_rm(k2,*incomplete);
1033 u = NULL;
1034
1035 TRAV(ruleRef->next,k2,&rk2,u);
1036
1037 /* any subtrees missing k2 tokens, add u onto end */
1038
1039 *t=tlink(*t,u,k2);
1040 Tfree(u);
1041 }
1042
1043 set_orin(incomplete,rk2); /* remember what we couldn't do */
1044 set_free(rk2);
1045
1046 if (MR_RuleBlkWithHalt != NULL) MR_RuleBlkWithHalt->end->halt=FALSE;
1047
1048 if (set_int(*incomplete) > (unsigned) predDepth) break; /* <=== another exit from loop */
1049 };
1050
1051 MR_RuleBlkWithHalt=save_MR_RuleBlkWithHalt;
1052
1053 if (MR_RuleBlkWithHalt != NULL) {
1054 MR_RuleBlkWithHalt->end->halt=TRUE;
1055 };
1056 ConstrainSearch=saveConstrainSearch;
1057 }
1058
1059 #ifdef __USE_PROTOS
MR_complete_predicates(int predDepth,Predicate * pred)1060 void MR_complete_predicates(int predDepth,Predicate *pred)
1061 #else
1062 void MR_complete_predicates(predDepth,pred)
1063 int predDepth;
1064 Predicate *pred;
1065 #endif
1066 {
1067 if (pred == NULL) return;
1068 if (pred->expr != PRED_AND_LIST &&
1069 pred->expr != PRED_OR_LIST) {
1070 MR_complete_set(predDepth,&(pred->scontext[1]),&(pred->completionSet));
1071 MR_complete_tree(predDepth,&(pred->tcontext),&(pred->completionTree));
1072 };
1073 MR_complete_predicates(predDepth,pred->down);
1074 MR_complete_predicates(predDepth,pred->right);
1075 }
1076
1077 #ifdef __USE_PROTOS
MR_junctionWithoutP2(Junction * j)1078 Junction * MR_junctionWithoutP2(Junction *j)
1079 #else
1080 Junction * MR_junctionWithoutP2(j)
1081 Junction *j;
1082 #endif
1083 {
1084 Junction *thisAlt;
1085
1086 /* don't want to follow p2 to the next alternative of this rule */
1087 /* insert a generic node with null p2 if necessary */
1088 /* however FIRST requires a junction */
1089
1090 thisAlt=j;
1091 if (thisAlt->p2 != NULL) {
1092 if (thisAlt->p1->ntype == nJunction) {
1093 thisAlt=(Junction *) thisAlt->p1;
1094 } else {
1095 thisAlt=newJunction();
1096 thisAlt->p1=j->p1;
1097 thisAlt->rname=j->rname;
1098 thisAlt->file=j->file;
1099 thisAlt->line=j->line;
1100 j->p1=(Node *)thisAlt;
1101 };
1102 };
1103 return thisAlt;
1104 }
1105
1106 #ifdef __USE_PROTOS
MR_tree_equ(Tree * big,Tree * small)1107 int MR_tree_equ(Tree *big, Tree *small) {
1108 #else
1109 int MR_tree_equ(big,small)
1110 Tree *big;
1111 Tree *small;
1112 {
1113 #endif
1114
1115 Tree *b;
1116 Tree *s;
1117 int bcount=0;
1118 int scount=0;
1119
1120 if (small == NULL && big == NULL) return 1;
1121 if (small == NULL) return 0;
1122 if (big == NULL) return 0;
1123
1124 if (small->token == ALT) {
1125 require(small->right == NULL,
1126 "MR_tree_equ: small: ALT node has siblings");
1127 return MR_tree_equ(big,small->down);
1128 };
1129 if (big->token == ALT) {
1130 require(big->right == NULL,
1131 "MR_tree_equ: big: ALT node has siblings");
1132 return MR_tree_equ(big->down,small);
1133 };
1134 for (s=small; s != NULL; s=s->right) {
1135 scount++;
1136 require(s->token != EpToken,"MR_tree_equ: s->EpToken unexpected\n");
1137 };
1138 for (b=big; b != NULL; b=b->right) {
1139 bcount++;
1140 require(b->token != EpToken,"MR_tree_equ: b->EpToken unexpected\n");
1141 };
1142
1143 if (bcount != scount) return 0;
1144
1145 for (s=small; s != NULL; s=s->right) {
1146 for (b=big; b!= NULL; b=b->right) {
1147 if (s->token == b->token) {
1148 if (MR_tree_equ(b->down,s->down)) goto next_s;
1149 };
1150 };
1151 return 0;
1152 next_s:
1153 continue;
1154 };
1155 return 1;
1156 }
1157
1158 /* this does not compare sources - only contexts ! */
1159
1160 #ifdef __USE_PROTOS
1161 int MR_identicalContext(Predicate *p,Predicate *q)
1162 #else
1163 int MR_identicalContext(p,q)
1164 Predicate *p;
1165 Predicate *q;
1166 #endif
1167 {
1168 if (p->k != q->k) return 0;
1169 require ( (p->tcontext == NULL) == (q->tcontext == NULL),
1170 "tcontext inconsistent");
1171 if (p->k == 1) {
1172 return set_equ(p->scontext[1],q->scontext[1]);
1173 } else {
1174 return MR_tree_equ(p->tcontext,q->tcontext);
1175 };
1176 }
1177
1178 #ifdef __USE_PROTOS
1179 void MR_reportSetSuppression(int predDepth,
1180 set predSet,set plainSet,Junction *jPred,Junction *jPlain,Predicate *p)
1181 #else
1182 void MR_reportSetSuppression(predDepth,predSet,plainSet,jPred,jPlain,p)
1183 int predDepth;
1184 set predSet;
1185 set plainSet;
1186 Junction *jPred;
1187 Junction *jPlain;
1188 Predicate *p;
1189 #endif
1190 {
1191 if (InfoP) {
1192 fprintf(output,"\n#if 0\n\n");
1193 fprintf(output,"Hoisting of predicate suppressed by alternative without predicate.\n");
1194 fprintf(output,"The alt without the predicate includes all cases where the predicate is false.\n\n");
1195 fprintf(output," WITH predicate: line %d %s\n",jPred->line,FileStr[jPred->file]);
1196 if (jPlain != NULL) {
1197 fprintf(output," WITHOUT predicate: line %d %s\n",jPlain->line,FileStr[jPlain->file]);
1198 } else {
1199 fprintf(output," WITHOUT predicate: all alternatives without predicates (combined)\n");
1200 };
1201 if (predDepth == 1) {
1202 fprintf(output,"\nThe context set for the predicate:\n");
1203 MR_dumpTokenSet(output,1,predSet);
1204 };
1205 fprintf(output,"\nThe lookahead set for the alt WITHOUT the semantic predicate:\n");
1206 MR_dumpTokenSet(output,1,plainSet);
1207 fprintf(output,"\nThe predicate:\n\n");
1208 MR_dumpPred1(1,p,1);
1209 fprintf(output,"Chain of referenced rules:\n\n");
1210 MR_dumpPredRuleRefStack(output,4);
1211 fprintf(output,"\n#endif\n");
1212 };
1213 }
1214
1215 #ifdef __USE_PROTOS
1216 void MR_reportSetRestriction(int predDepth,set predSet,set plainSet,
1217 Junction *jPred,Junction *jPlain,Predicate *origPred,Predicate *newPred)
1218 #else
1219 void MR_reportSetRestriction(predDepth,predSet,plainSet,jPred,jPlain,origPred,newPred)
1220 int predDepth;
1221 set predSet;
1222 set plainSet;
1223 Junction *jPred;
1224 Junction *jPlain;
1225 Predicate *origPred;
1226 Predicate *newPred;
1227 #endif
1228 {
1229 set intersect;
1230
1231 intersect=empty;
1232
1233 if (! InfoP) return;
1234 fprintf(output,"\n#if 0\n\n");
1235 fprintf(output,"Restricting the context of a predicate because of overlap in the lookahead set\n");
1236 fprintf(output," between the alternative with the semantic predicate and one without\n");
1237 fprintf(output,"Without this restriction the alternative without the predicate could not\n");
1238 fprintf(output," be reached when input matched the context of the predicate and the predicate\n");
1239 fprintf(output," was false.\n\n");
1240
1241 fprintf(output," WITH predicate: line %d %s\n",jPred->line,FileStr[jPred->file]);
1242 if (jPlain != NULL) {
1243 fprintf(output," WITHOUT predicate: line %d %s\n",jPlain->line,FileStr[jPlain->file]);
1244 } else {
1245 fprintf(output," WITHOUT predicate: all alternatives without predicates (combined)\n");
1246 };
1247 if (predDepth == 1) {
1248 fprintf(output,"\nThe original context set for the predicate:\n");
1249 MR_dumpTokenSet(output,1,predSet);
1250 };
1251 fprintf(output,"\nThe lookahead set for the alt WITHOUT the semantic predicate:\n");
1252 MR_dumpTokenSet(output,1,plainSet);
1253 if (predDepth == 1) {
1254 fprintf(output,"\nThe intersection of the two sets\n");
1255 intersect=set_and(predSet,plainSet);
1256 MR_dumpTokenSet(output,1,intersect);
1257 set_free(intersect);
1258 };
1259 fprintf(output,"\nThe original predicate:\n\n");
1260 MR_dumpPred1(1,origPred,1);
1261 fprintf(output,"The new (modified) form of the predicate:\n\n");
1262 MR_dumpPred1(1,newPred,1);
1263 fprintf(output,"#endif\n");
1264 }
1265
1266 /* don't use Pass3 by itself unless you know that inverted is not important */
1267
1268 #ifdef __USE_PROTOS
1269 Predicate * MR_removeRedundantPredPass3(Predicate *p)
1270 #else
1271 Predicate * MR_removeRedundantPredPass3(p)
1272 Predicate *p;
1273 #endif
1274 {
1275 Predicate *q;
1276
1277 if (p == NULL) return NULL;
1278 p->right=MR_removeRedundantPredPass3(p->right);
1279 p->down=MR_removeRedundantPredPass3(p->down);
1280 if (p->redundant) {
1281 q=p->right;
1282 p->right=NULL;
1283 predicate_free(p);
1284 return q;
1285 };
1286 if (p->expr == PRED_AND_LIST ||
1287 p->expr == PRED_OR_LIST) {
1288 if (p->down == NULL) {
1289 q=p->right;
1290 p->right=NULL;
1291 predicate_free(p);
1292 return q;
1293 };
1294 if (p->down != NULL && p->down->right == NULL) {
1295 q=p->down;
1296 q->right=p->right;
1297 p->right=NULL;
1298 p->down=NULL;
1299 return q;
1300 };
1301 };
1302 return p;
1303 }
1304
1305 #ifdef __USE_PROTOS
1306 void MR_removeRedundantPredPass2(Predicate *p)
1307 #else
1308 void MR_removeRedundantPredPass2(p)
1309 Predicate *p;
1310 #endif
1311 {
1312 Predicate *q;
1313
1314 if (p == NULL) return;
1315
1316 if (p->expr == PRED_AND_LIST) {
1317 for (q=p->down ; q != NULL ; q=q->right) {
1318 MR_removeRedundantPredPass2(q);
1319 if (q->isConst) {
1320 if (q->constValue == 0) {
1321 p->isConst=1;
1322 p->constValue=0;
1323 return;
1324 } else {
1325 q->redundant=1;
1326 };
1327 };
1328 };
1329 };
1330
1331 if (p->expr == PRED_OR_LIST) {
1332 for (q=p->down ; q != NULL ; q=q->right) {
1333 MR_removeRedundantPredPass2(q);
1334 if (q->isConst) {
1335 if (q->constValue == 0) {
1336 q->redundant=1;
1337 } else {
1338 p->isConst=1;
1339 p->constValue=1;
1340 return;
1341 };
1342 };
1343 };
1344 };
1345
1346 return;
1347 }
1348
1349 #if 0
1350 this totally ignores the implications of guarded predicates
1351 in which the part after the guard could possibly cover a predicate.
1352 that would be much harder:
1353
1354 rule : (A)? => <<p>>? sub1; /* 1 */
1355 | (B)? => <<r>>? sub2 /* 2 */
1356 sub1 : (A)? => <<q>>? A B /* 3 */
1357 | B /* 4 - suppresses line 2 */
1358 ;
1359 #endif
1360
1361 #ifdef __USE_PROTOS
1362 void MR_apply_restriction1(Predicate *pred,set *plainSet,int *changed)
1363 #else
1364 void MR_apply_restriction1(pred,plainSet,changed)
1365 Predicate *pred;
1366 set *plainSet;
1367 int *changed;
1368 #endif
1369 {
1370 if (pred == NULL) return;
1371 MR_apply_restriction1(pred->right,plainSet,changed);
1372 if (pred->down != NULL) {
1373 MR_apply_restriction1(pred->down,plainSet,changed);
1374 } else {
1375 set t;
1376 if (pred->k == 1) {
1377 t=set_dif(pred->scontext[1],*plainSet);
1378 if (*changed == 0 &&
1379 !set_equ(t,pred->scontext[1])) {
1380 *changed=1;
1381 };
1382 if (set_nil(t)) {
1383 pred->redundant=1;
1384 };
1385 set_free(pred->scontext[1]);
1386 pred->scontext[1]=t;
1387 };
1388 };
1389 }
1390
1391 #ifdef __USE_PROTOS
1392 void MR_orin_plainSet(Predicate *p,set plainSet)
1393 #else
1394 void MR_orin_plainSet(p,plainSet)
1395 Predicate *p;
1396 set plainSet;
1397 #endif
1398 {
1399 if (p == NULL) return;
1400 MR_orin_plainSet(p->down,plainSet);
1401 MR_orin_plainSet(p->right,plainSet);
1402 set_orin(&p->plainSet,plainSet);
1403 }
1404
1405 Predicate *PRED_SUPPRESS;
1406
1407 #ifdef __USE_PROTOS
1408 Predicate * MR_find_in_aSubBlk(Junction *alt)
1409 #else
1410 Predicate * MR_find_in_aSubBlk(alt)
1411 Junction *alt;
1412 #endif
1413 {
1414 Predicate *root=NULL;
1415 Predicate **tail=NULL;
1416
1417 Junction *p;
1418
1419 int nAlts=0;
1420 Junction **jList;
1421 Predicate **predList;
1422 int *matchList;
1423 set predSet;
1424 int i;
1425 int j;
1426 int m;
1427 int predDepth;
1428 set incomplete;
1429 set union_plainSet;
1430 set setChange;
1431 int changed;
1432 Predicate *newPred;
1433 set setDif;
1434 Predicate *origPred;
1435 int depth1=1; /* const int */
1436 set *plainContext;
1437 set plainSet;
1438
1439 predSet=empty;
1440 incomplete=empty;
1441 union_plainSet=empty;
1442 setChange=empty;
1443 setDif=empty;
1444 plainSet=empty;
1445
1446 if (PRED_SUPPRESS == NULL) {
1447 PRED_SUPPRESS=new_pred();
1448 PRED_SUPPRESS->expr="Predicate Suppressed";
1449 };
1450
1451 /* this section just counts the number of "interesting" alternatives */
1452 /* in order to allocate arrays */
1453
1454 for (p=alt; p!=NULL; p=(Junction *)p->p2) {
1455 /* ignore empty alts */
1456 if ( p->p1->ntype != nJunction ||
1457 ((Junction *)p->p1)->jtype != EndBlk ) {
1458 nAlts++;
1459 };
1460 };
1461
1462 /* if this is a (...)+ block then don't count the last alt because
1463 it can't be taken until at least one time through the block.
1464 In other words it isn't a real choice until the (...)+ is entered
1465 at which point the hoisting issue is moot.
1466 Maybe look at "ignore" instead ?
1467 */
1468
1469 if (alt->jtype == aPlusBlk) {
1470 nAlts--;
1471 };
1472
1473 jList=(Junction **)calloc(nAlts,sizeof(Junction *));
1474 require(jList!=NULL,"cannot allocate MR_find_in_aSubBlk jList");
1475
1476 plainContext=(set *)calloc(nAlts,sizeof(set));
1477 require(plainContext!=NULL,"cannot allocate MR_find_in_aSubBlk plainContext");
1478 for (m=0; m < nAlts; m++) plainContext[m]=empty;
1479
1480 predList=(Predicate **)calloc(nAlts,sizeof(Predicate *));
1481 require(predList!=NULL,"cannot allocate MR_find_in_aSubBlk predList");
1482
1483 matchList=(int *)calloc(nAlts,sizeof(int));
1484 require(matchList!=NULL,"cannot allocate MR_find_in_aSubBlk matchList");
1485
1486 /* this section just fills in the arrays previously allocated */
1487 /* the most interesting one is matchList[] */
1488 /* */
1489 /* bit 0 => this alt has a semantic pred which is "covered" */
1490 /* by an alt without a semantic pred. Don't hoist. */
1491
1492 for (i=0,p=alt;
1493 p!=NULL && i<nAlts;
1494 i++,p=(Junction *)p->p2) {
1495
1496 /* ignore empty alts */
1497
1498 if ( p->p1->ntype != nJunction ||
1499 ((Junction *)p->p1)->jtype != EndBlk ) {
1500 jList[i]=MR_junctionWithoutP2(p);
1501 predList[i]=find_predicates(p->p1); /* should be jList ????? */
1502 if (predList[i] != NULL) {
1503 MR_cleanup_pred_trees(predList[i]); /* flatten & left factor */
1504 plainContext[i]=MR_union_plain_sets(predList[i]);
1505 } else {
1506 MR_set_reuse(&plainSet);
1507 MR_set_reuse(&incomplete);
1508 plainSet=MR_First(depth1,jList[i],&incomplete);
1509 MR_complete_set(depth1,&plainSet,&incomplete);
1510 require(set_nil(incomplete),"couldn't complete k=1");
1511 plainContext[i]=plainSet;
1512 plainSet=empty;
1513 };
1514 set_orin(&union_plainSet,plainContext[i]);
1515 };
1516 };
1517
1518 if (nAlts == 1) {
1519 goto EXIT_SIMPLE;
1520 };
1521
1522 /*
1523 * Looking for cases where alt i has a semantic pred and alt j does not.
1524 * Don't care about cases where lookahead for semantic predicates overlap
1525 * because normal predicate hoisting does the correct thing automatically.
1526 * Don't care about cases where lookahead for alts without semantic predicates
1527 * overlap because normal prediction does the correct thing automatically.
1528 *
1529 * When we find such a case check for one of three subcases:
1530 *
1531 * 1. if lookahead for alt i is contained in the lookahead for any
1532 * alt j then ignore semantic predicate of alt i
1533 * 2. if lookahead for alt i is not contained in the lookahead for
1534 * any alt j then add add predicate i to the OR list to be hoisted
1535 * 3. if lookahead for alt i overlaps the lookahead for some alt j then
1536 * add a dummy semantic predicate for alt j
1537 *
1538 * There is an implicit assumption that the context of all alternatives following
1539 * the rule being processed here are identical (but may vary from hoist to
1540 * hoist depending on the place where the rule was invoked that led to hoisting
1541 * these predicates. In othere words in the fragment:
1542 *
1543 * ( <<a>>? a1 a2 a3 | <<b>>? b1 b2 b3 )
1544 *
1545 * both a3 and b3 have the same follow sets because they are both at the end of
1546 * alternatives in the same block.
1547 */
1548
1549 for (i=0; i < nAlts; i++) {
1550 if (jList[i] == NULL) continue;
1551 if (predList[i] == NULL) continue;
1552
1553 /* if the predicate depth turns out to be one token only */
1554 /* then it is can be easily represented as a set and */
1555 /* compared to the junction set create by MR_First() */
1556
1557 predDepth=0;
1558 MR_pred_depth(predList[i],&predDepth);
1559 require (predDepth >= 1,"MR_find_in_aSubBlk: pred depth < 1");
1560 require (predDepth <= CLL_k,"MR_find_in_aSubBlk: predDepth > CLL_k");
1561
1562 /* complete predicates to predDepth
1563 If completed to depth=1 then the context would be incomplete.
1564 The context would be truncated and the predicate simplify routine
1565 would have incomplete information. It would lead to
1566 either false matches of failure to find true matches.
1567 */
1568
1569 MR_complete_predicates(predDepth,predList[i]);
1570
1571 if (predList[i] != NULL) {
1572 MR_cleanup_pred_trees(predList[i]); /* flatten & left factor */
1573 };
1574
1575 /* If the predicate depth is 1 then it is possible to suppress
1576 a predicate completely using a single plain alt. Check for suppression
1577 by a single plain alt first because it gives better messages. If that
1578 fails try the union of all the plain alts.
1579 */
1580
1581 if (predDepth == 1) {
1582
1583 MR_set_reuse(&predSet);
1584 predSet=MR_compute_pred_set(predList[i]); /* ignores k>1 predicates */
1585
1586 for (j=0; j < nAlts; j++) {
1587 if (jList[j] == NULL) continue;
1588 if (j == i) continue;
1589
1590 MR_set_reuse(&setDif);
1591 setDif=set_dif(predSet,plainContext[j]);
1592 if (set_nil(setDif)) {
1593 matchList[i] |= 1;
1594 MR_reportSetSuppression(predDepth,predSet,plainContext[j],jList[i],jList[j],predList[i]);
1595 predicate_free(predList[i]);
1596 predList[i]=PRED_SUPPRESS;
1597 goto next_i;
1598 };
1599
1600 }; /* end loop on j */
1601
1602 changed=0;
1603
1604 /* predicate_dup is only to give good error messages */
1605 /* remember to do a predicate_free() */
1606
1607 origPred=predicate_dup(predList[i]);
1608 MR_apply_restriction1(predList[i],&union_plainSet,&changed);
1609 if (changed) {
1610
1611 /* don't use Pass3 by itself unless you know that inverted is not important */
1612
1613 newPred=MR_removeRedundantPredPass3(predList[i]);
1614 newPred=MR_predSimplifyALL(newPred);
1615 if (newPred == NULL) {
1616 matchList[i] |= 1;
1617 MR_reportSetSuppression(predDepth,predSet,union_plainSet,jList[i],
1618 NULL,origPred);
1619 predList[i]=PRED_SUPPRESS;
1620 } else {
1621 MR_reportSetRestriction(predDepth,predSet,union_plainSet,jList[i],
1622 NULL,origPred,newPred);
1623 predList[i]=newPred;
1624 };
1625 };
1626 predicate_free(origPred);
1627 origPred=NULL;
1628 };
1629
1630 /*
1631 If the predicate depth is > 1 then it can't be suppressed completely
1632 because the code doesn't support inspection of such things. They're
1633 much messier than k=1 sets.
1634 */
1635
1636 if (predDepth > 1 ) {
1637
1638 changed=0;
1639
1640 /* predicate_dup is only to give good error messages */
1641 /* remember to do a predicate_free() */
1642
1643 origPred=predicate_dup(predList[i]);
1644 MR_apply_restriction1(predList[i],&union_plainSet,&changed);
1645 if (changed) {
1646 newPred=MR_removeRedundantPredPass3(predList[i]);
1647 newPred=MR_predSimplifyALL(newPred);
1648 if (newPred == NULL) {
1649 matchList[i] |= 1;
1650 MR_reportSetSuppression(predDepth,predSet,union_plainSet,jList[i],
1651 NULL,origPred);
1652 predList[i]=PRED_SUPPRESS;
1653 } else {
1654 MR_reportSetRestriction(predDepth,predSet,union_plainSet,jList[i],
1655 NULL,origPred,newPred);
1656 predList[i]=newPred;
1657 };
1658 };
1659 predicate_free(origPred);
1660 origPred=NULL;
1661 };
1662 next_i:
1663 continue;
1664 };
1665
1666 EXIT_SIMPLE:
1667
1668 root = new_pred();
1669 root->expr=PRED_OR_LIST;
1670 tail = &(root->down);
1671
1672 for (i=0 ; i< nAlts ; i++) {
1673 if (jList[i] == NULL) continue;
1674
1675 if (predList[i] == NULL) {
1676 continue;
1677 } else if ( (matchList[i] & 1) != 0) {
1678 if (predList[i] != PRED_SUPPRESS) {
1679 predicate_free(predList[i]);
1680 };
1681 continue;
1682 };
1683
1684 /* make an OR list of predicates */
1685
1686 *tail=predList[i];
1687 tail=&(predList[i]->right);
1688 };
1689
1690 /* if just one pred, remove OR root */
1691
1692 if (root->down == NULL) {
1693 predicate_free(root);
1694 root=NULL;
1695 } else if (root->down->right == NULL) {
1696 Predicate *p=root->down;
1697 root->down=NULL;
1698 predicate_free(root);
1699 root=p;
1700 }
1701
1702 root=MR_predSimplifyALL(root);
1703
1704 MR_orin_plainSet(root,union_plainSet);
1705
1706 set_free(predSet);
1707 set_free(union_plainSet);
1708 set_free(incomplete);
1709 set_free(setChange);
1710 set_free(setDif);
1711
1712 for (m=0; m < nAlts; m++) set_free(plainContext[m]);
1713
1714 free ( (char *) jList);
1715 free ( (char *) predList);
1716 free ( (char *) matchList);
1717 free ( (char *) plainContext);
1718
1719 return root;
1720 }
1721
1722 #ifdef __USE_PROTOS
1723 void MR_predContextPresent(Predicate *p,int *allHaveContext,int *noneHaveContext)
1724 #else
1725 void MR_predContextPresent(p,allHaveContext,noneHaveContext)
1726 Predicate *p;
1727 int *allHaveContext;
1728 int *noneHaveContext;
1729 #endif
1730 {
1731 if (p == NULL) return;
1732 MR_predContextPresent(p->right,allHaveContext,noneHaveContext);
1733 if (p->expr != PRED_AND_LIST &&
1734 p->expr != PRED_OR_LIST) {
1735 if (set_nil(p->scontext[1]) == 0 ||
1736 (p->tcontext != NULL)) {
1737 *noneHaveContext=0;
1738 } else {
1739 *allHaveContext=0;
1740 };
1741 };
1742 MR_predContextPresent(p->down,allHaveContext,noneHaveContext);
1743 }
1744
1745 #ifdef __USE_PROTOS
1746 int MR_pointerStackPush(PointerStack *ps,void *dataPointer)
1747 #else
1748 int MR_pointerStackPush(ps,dataPointer)
1749 PointerStack *ps;
1750 void *dataPointer;
1751 #endif
1752 {
1753 void **newStack;
1754 int newSize;
1755 int i;
1756
1757 if (ps->count == ps->size) {
1758 newSize=20+ps->size*2;
1759 newStack=(void **)calloc(newSize,sizeof(void *));
1760 require (newStack != NULL,"cannot allocate PointerStack");
1761 for (i=0; i < ps->size; i++) {
1762 newStack[i]=ps->data[i];
1763 };
1764 if (ps->data != NULL) free( (char *) ps->data);
1765 ps->data=newStack;
1766 ps->size=newSize;
1767 };
1768 ps->data[ps->count]=dataPointer;
1769 ps->count++;
1770 return ps->count-1;
1771 }
1772
1773 #ifdef __USE_PROTOS
1774 void * MR_pointerStackPop(PointerStack *ps)
1775 #else
1776 void * MR_pointerStackPop(ps)
1777 PointerStack *ps;
1778 #endif
1779 {
1780 void *dataPointer;
1781
1782 require(ps->count > 0,"MR_pointerStackPop underflow");
1783
1784 dataPointer=ps->data[ps->count-1];
1785 ps->data[ps->count-1]=NULL;
1786 (ps->count)--;
1787 return dataPointer;
1788 }
1789
1790 #ifdef __USE_PROTOS
1791 void * MR_pointerStackTop(PointerStack *ps)
1792 #else
1793 void * MR_pointerStackTop(ps)
1794 PointerStack *ps;
1795 #endif
1796 {
1797 require(ps->count > 0,"MR_pointerStackTop underflow");
1798 return ps->data[ps->count-1];
1799 }
1800
1801 #ifdef __USE_PROTOS
1802 void MR_pointerStackReset(PointerStack *ps)
1803 #else
1804 void MR_pointerStackReset(ps)
1805 PointerStack *ps;
1806 #endif
1807 {
1808 int i;
1809 if (ps->data != NULL) {
1810 for (i=0; i < ps->count ; i++) {
1811 ps->data[i]=NULL;
1812 };
1813 };
1814 ps->count=0;
1815 }
1816
1817 #ifdef __USE_PROTOS
1818 Junction *MR_nameToRuleBlk(char *name)
1819 #else
1820 Junction *MR_nameToRuleBlk(name)
1821 char *name;
1822 #endif
1823 {
1824 RuleEntry *q;
1825
1826 require (RulePtr != NULL,"MR_nameToRule: RulePtr not initialized");
1827
1828 if (name == NULL) return NULL;
1829
1830 q = (RuleEntry *) hash_get(Rname,name);
1831
1832 if ( q == NULL ) {
1833 return NULL;
1834 } else {
1835 return RulePtr[q->rulenum];
1836 };
1837 }
1838
1839 #ifdef __USE_PROTOS
1840 Junction * MR_ruleReferenced(RuleRefNode *rrn)
1841 #else
1842 Junction * MR_ruleReferenced(rrn)
1843 RuleRefNode *rrn;
1844 #endif
1845 {
1846 return MR_nameToRuleBlk(rrn->text);
1847 }
1848
1849 #ifdef __USE_PROTOS
1850 void MR_comparePredLeaves(Predicate *me,Predicate *myParent,Predicate *him,Predicate *hisParent)
1851 #else
1852 void MR_comparePredLeaves(me,myParent,him,hisParent)
1853 Predicate *me;
1854 Predicate *myParent;
1855 Predicate *him;
1856 Predicate *hisParent;
1857 #endif
1858 {
1859 if (me == NULL) return;
1860 if (me == him) {
1861 MR_comparePredLeaves(me->right,myParent,him,hisParent);
1862 return;
1863 } else if (me->expr == PRED_AND_LIST ||
1864 me->expr == PRED_OR_LIST) {
1865 MR_comparePredLeaves(me->down,me,him,hisParent);
1866 MR_comparePredLeaves(me->right,myParent,him,hisParent);
1867 return;
1868 } else {
1869 if (me->source != NULL) {
1870
1871 /* predicate->invert can be set only in the predEntry predicates */
1872 /* thus they are only visible after the predEntry predicates have been "unfolded" */
1873
1874 int sameSource=(me->source == him->source);
1875 int sameInvert=1 &
1876 (1 + me->inverted + him->inverted + me->source->inverted + him->source->inverted);
1877 int samePredEntry=(me->source->predEntry != NULL
1878 && him->source->predEntry != NULL
1879 && me->source->predEntry == him->source->predEntry);
1880 if (sameInvert && (sameSource || samePredEntry)) {
1881 if (MR_identicalContext(me,him)) {
1882
1883 /* identical predicates */
1884
1885 if (hisParent->expr == PRED_OR_LIST &&
1886 myParent->expr == PRED_OR_LIST) {
1887 me->redundant=1;
1888 } else if (hisParent->expr == PRED_AND_LIST &&
1889 myParent->expr == PRED_AND_LIST) {
1890 me->redundant=1;
1891 } else if ( (hisParent->expr == PRED_OR_LIST &&
1892 myParent->expr == PRED_AND_LIST)
1893 ||
1894 (hisParent->expr == PRED_AND_LIST &&
1895 myParent->expr == PRED_OR_LIST)
1896 ) {
1897 myParent->redundant=1;
1898 } else {
1899 require (0,"MR_comparePredLeaves: not both PRED_LIST");
1900 };
1901 };
1902 }; /* end same source or same predEntrr with same invert sense */
1903
1904 /* same predEntry but opposite invert sense */
1905
1906 if (!sameInvert && (sameSource || samePredEntry)) {
1907 if (MR_identicalContext(me,him)) {
1908 if (hisParent->expr == PRED_OR_LIST &&
1909 myParent->expr == PRED_OR_LIST) {
1910 myParent->isConst=1;
1911 myParent->constValue=1;
1912 } else if (hisParent->expr == PRED_AND_LIST &&
1913 myParent->expr == PRED_AND_LIST) {
1914 myParent->isConst=1;
1915 myParent->constValue=0;
1916 } else if ( (hisParent->expr == PRED_OR_LIST &&
1917 myParent->expr == PRED_AND_LIST)
1918 ||
1919 (hisParent->expr == PRED_AND_LIST &&
1920 myParent->expr == PRED_OR_LIST)
1921 ) {
1922 me->redundant=1;
1923 } else {
1924 require (0,"MR_comparePredLeaves: not both PRED_LIST");
1925 };
1926 };
1927 }; /* end same predEntry with opposite invert sense */
1928 };
1929
1930 MR_comparePredLeaves(me->right,myParent,him,hisParent);
1931 return;
1932 };
1933 }
1934
1935 #ifdef __USE_PROTOS
1936 void MR_removeRedundantPredPass1(Predicate *me,Predicate *myParent)
1937 #else
1938 void MR_removeRedundantPredPass1(me,myParent)
1939 Predicate *me;
1940 Predicate *myParent;
1941 #endif
1942 {
1943 if (me == NULL) return;
1944 if (me->redundant) {
1945 MR_removeRedundantPredPass1(me->right,myParent);
1946 return;
1947 };
1948 if (me->expr == PRED_AND_LIST ||
1949 me->expr == PRED_OR_LIST) {
1950 MR_removeRedundantPredPass1(me->down,me);
1951 MR_removeRedundantPredPass1(me->right,myParent);
1952 } else {
1953 require (me->source != NULL,"me->source == NULL");
1954 if (myParent != NULL) {
1955 MR_comparePredLeaves(myParent->down,myParent,me,myParent);
1956 };
1957 MR_removeRedundantPredPass1(me->right,myParent);
1958 };
1959 }
1960
1961 /* pretty much ignores things with the inverted bit set */
1962
1963 #ifdef __USE_PROTOS
1964 Predicate *MR_predFlatten(Predicate *p)
1965 #else
1966 Predicate *MR_predFlatten(p)
1967 Predicate *p;
1968 #endif
1969 {
1970 if (p == NULL) return NULL;
1971 if (p->expr == PRED_OR_LIST
1972 || p->expr == PRED_AND_LIST) {
1973
1974 Predicate *child;
1975 Predicate *gchild;
1976 Predicate **tail;
1977 Predicate *next;
1978 char *PRED_XXX_LIST=p->expr;
1979
1980 require (p->down != NULL,"MR_predFlatten AND/OR no child");
1981
1982
1983 p->down=MR_predFlatten(p->down);
1984 p->right=MR_predFlatten(p->right);
1985 child=p->down;
1986 if (child->right == NULL) {
1987 child->right=p->right;
1988 p->right=NULL;
1989 p->down=NULL;
1990 if (p->inverted) child->inverted=!child->inverted;
1991 predicate_free(p);
1992 return child;
1993 };
1994
1995 /* make a single list of all children and grandchildren */
1996
1997 tail=&(p->down);
1998 for (child=p->down; child != NULL; child=next) {
1999 if (child->expr != PRED_XXX_LIST
2000 || child->inverted
2001 || child->predEntry != NULL) {
2002 *tail=child;
2003 tail=&(child->right);
2004 next=child->right;
2005 } else {
2006 for (gchild=child->down;
2007 gchild != NULL;
2008 gchild=gchild->right) {
2009 *tail=gchild;
2010 tail=&(gchild->right);
2011 };
2012 next=child->right;
2013 child->right=NULL;
2014 child->down=NULL;
2015 predicate_free(child);
2016 };
2017 };
2018 *tail=NULL;
2019 return p;
2020 } else {
2021 p->right=MR_predFlatten(p->right);
2022 return p;
2023 };
2024 }
2025
2026 static char *alwaysFalseWarning=NULL;
2027
2028 #ifdef __USE_PROTOS
2029 Predicate *checkPredicateConflict(Predicate *p)
2030 #else
2031 Predicate *checkPredicateConflict(p)
2032 Predicate *p;
2033 #endif
2034 {
2035 if (p->isConst) {
2036 if (p->constValue == 1) {
2037 predicate_free(p);
2038 return NULL;
2039 } else {
2040 if (InfoP && !p->conflictReported) {
2041 p->conflictReported=1;
2042 fprintf(output,"\n#if 0\n\n");
2043 fprintf(output,"The following predicate expression will always be false:\n\n");
2044 MR_dumpPred1(1,p,1);
2045 fprintf(output,"\n#endif\n");
2046 };
2047
2048 if (alwaysFalseWarning != CurRule) {
2049 alwaysFalseWarning=CurRule;
2050 if (InfoP) {
2051 warnNoFL(eMsg1("one (or more) predicate expression hoisted into rule \"%s\" are always false \
2052 - see output file for more information",CurRule));
2053 } else {
2054 warnNoFL(eMsg1("one (or more) predicate expressions hoisted into rule \"%s\" are always false \
2055 - use \"-info p\" for more information",CurRule));
2056 };
2057 };
2058 };
2059 };
2060 return p;
2061 }
2062
2063
2064 #ifdef __USE_PROTOS
2065 int MR_countPredNodes(Predicate *p)
2066 #else
2067 int MR_countPredNodes(p)
2068 Predicate *p;
2069 #endif
2070 {
2071 if (p == NULL) return 0;
2072 return 1 + MR_countPredNodes(p->down) + MR_countPredNodes(p->right);
2073 }
2074
2075 #ifdef __USE_PROTOS
2076 Predicate *MR_predSimplifyALLX(Predicate *p,int skipPass3)
2077 #else
2078 Predicate *MR_predSimplifyALLX(p,skipPass3)
2079 Predicate *p;
2080 int skipPass3;
2081 #endif
2082 {
2083 int countBefore;
2084 int countAfter;
2085
2086 countAfter=MR_countPredNodes(p);
2087
2088 do {
2089 if (p == NULL) return NULL;
2090 if (p->right == NULL && p->down == NULL) return p;
2091 countBefore=countAfter;
2092 MR_simplifyInverted(p,0);
2093 p=MR_predFlatten(p);
2094 MR_removeRedundantPredPass1(p,NULL);
2095 MR_removeRedundantPredPass2(p);
2096 if (! skipPass3) {
2097 p=checkPredicateConflict(p);
2098 p=MR_removeRedundantPredPass3(p);
2099 };
2100 countAfter=MR_countPredNodes(p);
2101 } while (countBefore != countAfter);
2102
2103 return p;
2104 }
2105
2106 #ifdef __USE_PROTOS
2107 Predicate *MR_predSimplifyALL(Predicate *p)
2108 #else
2109 Predicate *MR_predSimplifyALL(p)
2110 Predicate *p;
2111 #endif
2112 {
2113 return MR_predSimplifyALLX(p,0);
2114 }
2115
2116 #ifdef __USE_PROTOS
2117 void MR_releaseResourcesUsedInRule(Node *n)
2118 #else
2119 void MR_releaseResourcesUsedInRule(n)
2120 Node *n;
2121 #endif
2122 {
2123 Node *next;
2124 Junction *j;
2125 int i;
2126
2127 if (n == NULL) return;
2128 if (n->ntype == nJunction) {
2129 j=(Junction *) n;
2130
2131 if (j->predicate != NULL) {
2132 predicate_free(j->predicate);
2133 j->predicate=NULL;
2134 };
2135 for (i=0; i< CLL_k; i++) {
2136 set_free(j->fset[i]);
2137 j->fset[i]=empty;
2138 };
2139 if (j->ftree != NULL) {
2140 Tfree(j->ftree);
2141 j->ftree=NULL;
2142 };
2143 if (j->jtype == EndRule) return;
2144 if (j->jtype != RuleBlk && j->jtype != EndBlk) {
2145 if (j->p2 != NULL && !j->ignore) { /* MR11 */
2146 MR_releaseResourcesUsedInRule(j->p2);
2147 };
2148 };
2149 };
2150 next=MR_advance(n);
2151 MR_releaseResourcesUsedInRule(next);
2152 }
2153
2154 #ifdef __USE_PROTOS
2155 int MR_allPredLeaves(Predicate *p)
2156 #else
2157 int MR_allPredLeaves(p)
2158 Predicate *p;
2159 #endif
2160 {
2161 Predicate *q;
2162
2163 if (p == NULL) return 1;
2164
2165 for (q=p; q != NULL; q=q->right) {
2166 if (q->down != NULL) return 0;
2167 };
2168 return 1;
2169 }
2170
2171 /* make sure it works for the last rule in a file */
2172
2173 #ifdef __USE_PROTOS
2174 int MR_offsetFromRule(Node *n)
2175 #else
2176 int MR_offsetFromRule(n)
2177 Node *n;
2178 #endif
2179 {
2180 Junction *j;
2181 int offset=(-1);
2182
2183 for (j=SynDiag; j != NULL; j=(Junction *)j->p2) {
2184
2185 require (j->ntype == nJunction && j->jtype == RuleBlk,"Not a rule block");
2186
2187 if (n->file < j->file) {
2188 return offset;
2189 };
2190 if (n->file == j->file) {
2191 if (n->line < j->line) {
2192 return (offset < 0) ? 0 : offset;
2193 } else {
2194 offset=n->line - j->line;
2195 if (offset == 0) return 0;
2196 };
2197 };
2198 };
2199 return offset;
2200 }
2201
2202 #define ruleNameMax 50
2203
2204 static char ruleNameStatic1[ruleNameMax];
2205 static char ruleNameStatic2[ruleNameMax+10];
2206
2207 #ifdef __USE_PROTOS
2208 char * MR_ruleNamePlusOffset(Node *n)
2209 #else
2210 char * MR_ruleNamePlusOffset(n)
2211 Node *n;
2212 #endif
2213 {
2214 int offset=MR_offsetFromRule(n);
2215
2216 strncpy(ruleNameStatic1,n->rname,ruleNameMax);
2217 if (offset < 0) {
2218 sprintf(ruleNameStatic2,"%s/?",ruleNameStatic1);
2219 } else {
2220 sprintf(ruleNameStatic2,"%s/%d",ruleNameStatic1,offset+1);
2221 };
2222 return ruleNameStatic2;
2223 }
2224
2225 #ifdef __USE_PROTOS
2226 int MR_max_height_of_tree(Tree *t)
2227 #else
2228 int MR_max_height_of_tree(t)
2229 Tree *t;
2230 #endif
2231 {
2232 int h;
2233 int height=0;
2234 Tree *u;
2235
2236 if (t == NULL) return 0;
2237
2238 require (t->token != ALT && t->token != EpToken,"MR_max_height_of_tree ALT or EpToken");
2239
2240 for (u=t; u != NULL; u=u->right) {
2241 h=MR_max_height_of_tree(u->down)+1;
2242 if (h > height) height=h;
2243 };
2244 return height;
2245 }
2246
2247 #ifdef __USE_PROTOS
2248 int MR_all_leaves_same_height(Tree *t,int depth)
2249 #else
2250 int MR_all_leaves_same_height(t,depth)
2251 Tree *t;
2252 int depth;
2253 #endif
2254 {
2255 if (t == NULL) {
2256 return (depth==0);
2257 };
2258
2259 require (t->token != ALT && t->token != EpToken,"MR_all_leaves_same_height ALT or EpToken");
2260
2261 if (depth == 0) {
2262 return 0;
2263 } else {
2264 if ( ! MR_all_leaves_same_height(t->down,depth-1)) {
2265 return 0;
2266 };
2267 if (t->right == NULL) {
2268 return 1;
2269 } else {
2270 return MR_all_leaves_same_height(t->right,depth);
2271 };
2272 };
2273 }
2274
2275 #ifdef __USE_PROTOS
2276 void MR_projectTreeOntoSet(Tree *tree,int ck,set *ckset)
2277 #else
2278 void MR_projectTreeOntoSet(tree,ck,ckset)
2279 Tree *tree;
2280 int ck;
2281 set *ckset;
2282 #endif
2283 {
2284 if (tree == NULL) return;
2285
2286 require(tree->token != EpToken,"MR_projectTreeOntoSet: EpToken unexpected\n");
2287
2288 MR_projectTreeOntoSet(tree->right,ck,ckset);
2289 if (tree->token == ALT) {
2290 MR_projectTreeOntoSet(tree->down,ck,ckset);
2291 } else {
2292 if (ck > 1) {
2293 MR_projectTreeOntoSet(tree->down,ck-1,ckset);
2294 } else {
2295 set_orel(tree->token,ckset);
2296 };
2297 };
2298 }
2299
2300 #ifdef __USE_PROTOS
2301 int MR_comparePredicates(Predicate *a,Predicate *b)
2302 #else
2303 int MR_comparePredicates(a,b)
2304 Predicate *a;
2305 Predicate *b;
2306 #endif
2307 {
2308 Predicate *p;
2309 Predicate *q;
2310
2311 if (a == b) return 1;
2312 if (a == NULL || b == NULL ) return 0;
2313 if (a->down == NULL && b->down == NULL) {
2314
2315 /* predicate->invert can be set only in the predEntry predicates */
2316 /* thus they are only visible after the predEntry predicates have been "unfolded" */
2317
2318 int sameSource=(a->source == b->source);
2319 int sameInvert= 1 & (1 +a->inverted + b->inverted +
2320 a->source->inverted + b->source->inverted);
2321 int samePredEntry=(a->source->predEntry != NULL
2322 && b->source->predEntry != NULL
2323 && a->source->predEntry == b->source->predEntry);
2324 if (sameInvert && (sameSource || samePredEntry)) {
2325 if (MR_identicalContext(a,b)) {
2326 return 1;
2327 };
2328 };
2329 return 0;
2330 };
2331 if (a->down == NULL || b->down == NULL) return 0;
2332 if (a->expr != b->expr) return 0;
2333
2334 for (p=a->down; p != NULL; p=p->right) {
2335 for (q=b->down; q != NULL; q=q->right) {
2336 if (MR_comparePredicates(p,q)) goto NEXT_P;
2337 };
2338 return 0;
2339 NEXT_P:
2340 continue;
2341 };
2342 return 1;
2343 }
2344
2345 /*
2346 * action->inverted can be set only when a predicate symbol appears in
2347 * a rule: "rule : <<!XXX>>? X". It cannot be set under any
2348 * other circumstances. In particular it cannot be set by
2349 * "#pred NotA !A" or by "#pred Nota <<!A>>?". The first case
2350 * creates a predEntry and the predicate expression of that predEntry
2351 * has inverted set. In the second case, the code for handling "!"
2352 * is only present in buildAction, which is not called by the #pred
2353 * semantic routines, only when a <<...>>? is recognized as part of
2354 * a rule definition.
2355 *
2356 * predicate->inverted can only be set by a predicate created by a #pred
2357 * expression, such as "#pred NotA !A" or "#pred NotXY ! (X && Y) or
2358 * "#pred XbarY !(X && Y)". In particular, it cannot be set by any
2359 * predicate expression occurring under any other circumstances.
2360 * The #pred predicate expresssions are stored with in predEntry->pred
2361 * and do not normally appear anywhere else until the predicates are
2362 * "unfolded" in order to recognize redundancies, conflicts, and
2363 * tautologies.
2364 *
2365 * The unfold routine expands all references to #pred expressions.
2366 *
2367 * The simplifyInvert goes through and propagates the invert bit so that
2368 * all OR and AND nodes are un-inverted.
2369 *
2370 * Note that !(A and B) => (!A or !B)
2371 * !(A or B) => (!A and !B)
2372 *
2373 * MR_unfold() is called to expand predicate symbols by replacing predicates
2374 * that reference predicate entries with the copies of the predicate entries.
2375 * Each reference receives a duplicate of the original. This is necessary
2376 * because the next phase involves simplification and removal of redundant
2377 * predicate nodes. Anyway, the point I'm making is that predicate->invert
2378 * should not be set in any predicate until it has been expanded.
2379 *
2380 * This is a recursive structure, but there is no need for "recursive expansion"
2381 * by which I mean a predicate symbol refers to other predicate symbols which
2382 * must also be expanded.
2383 *
2384 * Recursive expansion is *not* performed by this routine because it is not
2385 * necessary. Expansion of references is performed by predPrimary when
2386 * a new predicate symbol is created by referring to others in the pred expr.
2387 */
2388
2389 #ifdef __USE_PROTOS
2390 Predicate *MR_unfold(Predicate *pred)
2391 #else
2392 Predicate *MR_unfold(pred)
2393 Predicate *pred;
2394 #endif
2395 {
2396 Predicate *result;
2397
2398 if (pred == NULL) return NULL;
2399
2400 pred->right=MR_unfold(pred->right);
2401
2402 if (pred->down == NULL) {
2403 if (pred->source->predEntry != NULL) {
2404 if (pred->source->predEntry->pred == NULL) {
2405 ; /* do nothing */ /* a reference to a literal #pred (perhaps with "!" */
2406 } else {
2407 result=predicate_dup_without_context(pred->source->predEntry->pred);
2408 if (pred->inverted) {
2409 result->inverted=!result->inverted;
2410 };
2411 if (pred->source->inverted) {
2412 result->inverted=!result->inverted;
2413 };
2414 result->right=pred->right;
2415 pred->right=NULL;
2416 predicate_free(pred);
2417 /*** result=MR_unfold(result); *** not necessary */ /* recursive expansion */
2418 return result;
2419 };
2420 } else {
2421 ; /* do nothing */ /* an inline literal predicate */
2422 };
2423 } else {
2424 pred->down=MR_unfold(pred->down);
2425 };
2426 return pred;
2427 }
2428
2429 /* this should be called immediately after MR_unfold() and
2430 at no other times
2431 */
2432
2433 #ifdef __USE_PROTOS
2434 void MR_simplifyInverted(Predicate *pred,int inverted)
2435 #else
2436 void MR_simplifyInverted(pred,inverted)
2437 Predicate *pred;
2438 int inverted;
2439 #endif
2440 {
2441 int newInverted;
2442
2443 if (pred == NULL) return;
2444
2445 MR_simplifyInverted(pred->right,inverted);
2446
2447 newInverted= 1 & (inverted + pred->inverted);
2448
2449 if (pred->down == NULL) {
2450 pred->inverted=newInverted;
2451 } else {
2452 if (newInverted != 0) {
2453 if (pred->expr == PRED_AND_LIST) {
2454 pred->expr=PRED_OR_LIST;
2455 } else {
2456 pred->expr=PRED_AND_LIST;
2457 };
2458 };
2459 pred->inverted=0;
2460 MR_simplifyInverted(pred->down,newInverted);
2461 };
2462 }
2463
2464 /* only remove it from AND and OR nodes, not leaves */
2465
2466 #ifdef __USE_PROTOS
2467 void MR_clearPredEntry(Predicate *p)
2468 #else
2469 void MR_clearPredEntry(p)
2470 Predicate *p;
2471 #endif
2472 {
2473 if (p == NULL) return;
2474 MR_clearPredEntry(p->down);
2475 MR_clearPredEntry(p->right);
2476 if (p->down != NULL) p->predEntry=NULL;
2477 }
2478
2479
2480 #ifdef __USE_PROTOS
2481 void MR_orphanRules(FILE *f)
2482 #else
2483 void MR_orphanRules(f)
2484 FILE *f;
2485 #endif
2486 {
2487 set a;
2488 Junction *p;
2489 unsigned e;
2490 RuleEntry *re;
2491
2492 a=empty;
2493
2494 if (! InfoO) return;
2495
2496 for (p=SynDiag; p!=NULL; p = (Junction *)p->p2) {
2497 if ( (Junction *) (p->end)->p1 == NULL) {
2498 re=(RuleEntry *) hash_get(Rname,p->rname);
2499 require (re != NULL,"RuleEntry == NULL");
2500 set_orel(re->rulenum, &a);
2501 }
2502 }
2503
2504 if (set_deg(a) > 1) {
2505 fprintf(f,"note: Start rules: {");
2506 for (; !set_nil(a); set_rm(e,a)) {
2507 e=set_int(a);
2508 fprintf(f," %s",RulePtr[e]->rname);
2509 };
2510 fprintf(f," }\n");
2511 };
2512 set_free( a );
2513 }
2514
2515 /* merge (X Y) and (X) to create (X) */
2516
2517 static int *mergeChain;
2518 static Tree *mergeTree;
2519
2520 #ifdef __USE_PROTOS
2521 Tree *MR_merge_tree_contexts_client(Tree *t,int chain[])
2522 #else
2523 Tree *MR_merge_tree_contexts_client(t,chain)
2524 Tree *t;
2525 int chain[];
2526 #endif
2527 {
2528 if (t == NULL) return NULL;
2529 if (chain[0] == 0) {
2530 Tree *u=t->right;
2531 t->right=NULL;
2532 Tfree(t);
2533 return MR_merge_tree_contexts_client(u,&chain[0]);
2534 }
2535 if (chain[0] == t->token) {
2536 t->down=MR_merge_tree_contexts_client(t->down,&chain[1]);
2537 };
2538 t->right=MR_merge_tree_contexts_client(t->right,&chain[0]);
2539 return t;
2540 }
2541
2542 #ifdef __USE_PROTOS
2543 void MR_iterateOverTreeContexts(Tree *t,int chain[])
2544 #else
2545 void MR_iterateOverTreeContexts(t,chain)
2546 Tree *t;
2547 int chain[];
2548 #endif
2549 {
2550 if (t == NULL) return;
2551 chain[0]=t->token;
2552 if (t->down != NULL) {
2553 MR_iterateOverTreeContexts(t->down,&chain[1]);
2554 } else {
2555 MR_merge_tree_contexts_client(mergeTree,mergeChain);
2556 };
2557 MR_iterateOverTreeContexts(t->right,&chain[0]);
2558 chain[0]=0;
2559 }
2560
2561 #ifdef __USE_PROTOS
2562 Tree *MR_merge_tree_contexts(Tree *t)
2563 #else
2564 Tree *MR_merge_tree_contexts(t)
2565 Tree *t;
2566 #endif
2567 {
2568 int h=MR_max_height_of_tree(t);
2569
2570 mergeTree=t;
2571 mergeChain=(int *) calloc(h+1,sizeof(int));
2572 require (mergeChain != NULL,"MR_merge_tree_contexts: can't alloc chain");
2573 MR_iterateOverTreeContexts(t,mergeChain);
2574 t=tshrink(t);
2575 t=tflatten(t);
2576 t=tleft_factor(t);
2577 free ( (char *) mergeChain);
2578 mergeChain=NULL;
2579 return t;
2580 }
2581
2582 #ifdef __USE_PROTOS
2583 Tree *MR_compute_pred_tree_context(Predicate *p)
2584 #else
2585 Tree *MR_compute_pred_tree_context(p)
2586 Predicate *p;
2587 #endif
2588 {
2589 Tree *t;
2590
2591 t=MR_compute_pred_tree_ctxXX(p);
2592 MR_merge_tree_contexts(t);
2593 return t;
2594 }
2595
2596 #ifdef __USE_PROTOS
2597 void MR_guardPred_plainSet(ActionNode *anode,Predicate *pred)
2598 #else
2599 void MR_guardPred_plainSet(anode,pred)
2600 ActionNode *anode;
2601 Predicate *pred;
2602 #endif
2603 {
2604 Junction *j;
2605 Predicate *workPred;
2606 set maskSet;
2607
2608 maskSet=empty;
2609
2610 if (!MRhoisting) return;
2611
2612 /* it doesn't really matter whether the predicate has
2613 depth k=1 or k>1 because we're not really looking
2614 at the predicate itself, just the stuff "behind"
2615 the predicate.
2616 */
2617
2618 /* shouldn't have to worry about REACHing off the end
2619 of the rule containing the predicate because the
2620 Rule->end->halt should have been set already by the
2621 the code which handles RuleRef nodes.
2622
2623 We don't want to REACH off the end of the rule because
2624 this would give the "global" follow context rather than
2625 the "local" context.
2626
2627 r1a : (A)? => <<p>>? r2 (A|B)
2628 r1b : (A)? => <<p>>? r2 (A|C)
2629 r2 : ();
2630
2631 For r1a we want follow of predicate = {A B}
2632 we want plainSet = {B}
2633 For r1b we want follow of predicate = {A C}
2634 we want plainSet = {C}
2635 */
2636
2637 require (anode->next->ntype == nJunction,"MR_guardpred_plainSet not Junction");
2638 j=(Junction *)(anode->next);
2639
2640 workPred=predicate_dup_without_context(pred);
2641 workPred->k=1;
2642 workPred->scontext[1]=MR_First(1,j, &(workPred->completionSet) );
2643 MR_complete_predicates(1,workPred);
2644 if (pred->k == 1) {
2645 maskSet=pred->scontext[1];
2646 } else {
2647 MR_projectTreeOntoSet(pred->tcontext,1,&maskSet);
2648 }
2649 pred->plainSet=set_dif(workPred->scontext[1],maskSet);
2650 predicate_free(workPred);
2651 }
2652
2653 /*******************************************************************************/
2654
2655 static Tree * suppressTree;
2656 static int * suppressChain; /* element 0 not used */
2657 static set * suppressSets;
2658 static Node * suppressNode;
2659 static int suppressChainLength;
2660 int MR_SuppressSearch=0;
2661 static int suppressSucceeded;
2662 static Predicate * suppressPredicate;
2663
2664 #ifdef __USE_PROTOS
2665 int MR_isChain(Tree *t)
2666 #else
2667 int MR_isChain(t)
2668 Tree *t;
2669 #endif
2670 {
2671 Tree *u;
2672
2673 for (u=t; u != NULL; u=u->down) {
2674 if (u->right != NULL) return 0;
2675 }
2676 return 1;
2677 }
2678
2679 #ifdef __USE_PROTOS
2680 int MR_suppressK_client(Tree *tree,int tokensInChain[])
2681 #else
2682 int MR_suppressK_client(tree,tokensInChain)
2683 Tree *tree;
2684 int tokensInChain[];
2685 #endif
2686 {
2687 int i;
2688 set *save_fset;
2689 int save_ConstrainSearch;
2690 set incomplete;
2691 Tree *t;
2692
2693 suppressSucceeded=0; /* volatile */
2694
2695 if (suppressSets == NULL) {
2696 suppressSets=(set *) calloc (CLL_k+1,sizeof(set));
2697 require (suppressSets != NULL,"MR_suppressK_client: suppressSets alloc");
2698 };
2699
2700 for (suppressChainLength=1;
2701 tokensInChain[suppressChainLength+1] != 0;
2702 suppressChainLength++) {};
2703
2704 require (suppressChainLength != 0,"MR_suppressK_client: chain empty");
2705
2706 for (i=1 ; i <= suppressChainLength ; i++) {
2707 set_clr(suppressSets[i]);
2708 set_orel( (unsigned) tokensInChain[i],
2709 &suppressSets[i]);
2710 };
2711
2712 save_fset=fset;
2713 save_ConstrainSearch=ConstrainSearch;
2714
2715 fset=suppressSets;
2716
2717 MR_SuppressSearch=1;
2718 MR_AmbSourceSearch=1;
2719 MR_MaintainBackTrace=1;
2720 ConstrainSearch=1;
2721
2722 maxk = suppressChainLength;
2723
2724 incomplete=empty;
2725 t=NULL;
2726
2727 /*** constrain = &(fset[1]); ***/
2728
2729 MR_setConstrainPointer(&(fset[1])); /* MR18 */
2730
2731 MR_pointerStackReset(&MR_BackTraceStack);
2732
2733 TRAV(suppressNode,maxk,&incomplete,t);
2734
2735 Tfree(t);
2736
2737 require (set_nil(incomplete),"MR_suppressK_client TRAV incomplete");
2738 require (MR_BackTraceStack.count == 0,
2739 "MR_suppressK_client: MR_BackTraceStack.count != 0");
2740 set_free(incomplete);
2741
2742 ConstrainSearch=save_ConstrainSearch;
2743 fset=save_fset;
2744
2745 MR_AmbSourceSearch=0;
2746 MR_MaintainBackTrace=0;
2747 MR_SuppressSearch=0;
2748 return suppressSucceeded;
2749 }
2750
2751 #ifdef __USE_PROTOS
2752 Tree * MR_iterateOverTreeSuppressK(Tree *t,int chain[])
2753 #else
2754 Tree * MR_iterateOverTreeSuppressK(t,chain)
2755 Tree *t;
2756 int chain[];
2757 #endif
2758 {
2759 if (t == NULL) return NULL;
2760 t->right=MR_iterateOverTreeSuppressK(t->right,&chain[0]);
2761 chain[0]=t->token;
2762 if (t->down != NULL) {
2763 t->down=MR_iterateOverTreeSuppressK(t->down,&chain[1]);
2764 if (t->down == NULL) {
2765 Tree *u=t->right;
2766 t->right=NULL;
2767 Tfree(t);
2768 chain[0]=0;
2769 return u;
2770 };
2771 } else {
2772 MR_suppressK_client(suppressTree,suppressChain);
2773 if (suppressSucceeded) {
2774 Tree *u=t->right;
2775 t->right=NULL;
2776 Tfree(t);
2777 chain[0]=0;
2778 return u;
2779 };
2780 };
2781 chain[0]=0;
2782 return t;
2783 }
2784
2785 /* @@@ */
2786
2787 #ifdef __USE_PROTOS
2788 Predicate * MR_suppressK(Node *j,Predicate *p)
2789 #else
2790 Predicate * MR_suppressK(j,p)
2791 Node *j;
2792 Predicate *p;
2793 #endif
2794 {
2795 Predicate *result;
2796 int guardPred=0;
2797 int ampersandPred=0;
2798 Node *nodePrime;
2799
2800 if (! MRhoistingk) {
2801 return p;
2802 }
2803
2804 if (! MRhoisting) return p;
2805 if (CLL_k == 1) return p;
2806
2807 if (suppressChain == NULL) {
2808 suppressChain=(int *) calloc(CLL_k+2,sizeof(int));
2809 require (suppressChain != NULL,"MR_suppressK: can't allocate chain");
2810 }
2811
2812 if (p == NULL) return NULL;
2813
2814 if (j->ntype == nJunction) {
2815 nodePrime=(Node *) MR_junctionWithoutP2( (Junction *) j);
2816 } else {
2817 nodePrime=j;
2818 };
2819
2820 p->down=MR_suppressK(j,p->down);
2821 p->right=MR_suppressK(j,p->right);
2822 if (p->down != NULL) {
2823 result=p;
2824 goto EXIT;
2825 };
2826 if (p->k == 1) {
2827 result=p;
2828 goto EXIT;
2829 };
2830
2831 if (p->source != NULL) {
2832 if (p->source->guardpred != NULL) guardPred=1;
2833 if (p->source->ampersandPred != NULL) ampersandPred=1;
2834 }
2835
2836 suppressPredicate=p;
2837 suppressNode=nodePrime; /* was j*/
2838
2839 suppressTree=p->tcontext;
2840
2841 if (guardPred || ampersandPred) {
2842 p->tcontext=MR_iterateOverTreeSuppressK(suppressTree,&suppressChain[1]);
2843 if (p->tcontext == NULL) {
2844 predicate_free(p);
2845 result=NULL;
2846 goto EXIT;
2847 };
2848 } else {
2849 if (MR_isChain(p->tcontext)) {
2850 p->tcontext=MR_iterateOverTreeSuppressK(suppressTree,&suppressChain[1]);
2851 if (p->tcontext == NULL) {
2852 predicate_free(p);
2853 result=NULL;
2854 goto EXIT;
2855 };
2856 }
2857 }
2858 result=p;
2859 EXIT:
2860 return result;
2861 }
2862
2863 #ifdef __USE_PROTOS
2864 void MR_suppressSearchReport(void)
2865 #else
2866 void MR_suppressSearchReport()
2867 #endif
2868 {
2869 int i;
2870 Node *p;
2871 TokNode *tn;
2872 int depth;
2873 set setAnd;
2874
2875 /* number of tokens in back trace stack matches length of chain */
2876
2877 depth=0;
2878 for (i=0; i < MR_BackTraceStack.count ; i++) {
2879 p=(Node *) MR_BackTraceStack.data[i];
2880 if (p->ntype == nToken) depth++;
2881 };
2882
2883 require (depth == suppressChainLength,"depth > suppressChainLength");
2884
2885 /* token codes match chain */
2886
2887 depth=0;
2888 for (i=0; i < MR_BackTraceStack.count ; i++) {
2889 p=(Node *) MR_BackTraceStack.data[i];
2890 if (p->ntype != nToken) continue;
2891 tn=(TokNode *) p;
2892 depth++;
2893 if (set_nil(tn->tset)) {
2894 require(set_el( (unsigned) tn->token,fset[depth]),
2895 "MR_suppressSearchReport: no match to #token in chain");
2896 } else {
2897 setAnd=set_and(fset[depth],tn->tset);
2898 require(!set_nil(setAnd),
2899 "MR_suppressSearchReport: no match to #token set in chain");
2900 set_free(setAnd);
2901 };
2902 };
2903
2904 /* have a match - now remove it from the predicate */
2905
2906 suppressSucceeded=1;
2907
2908 if (suppressSucceeded) {
2909 fprintf(output,"\n");
2910 fprintf(output,"#if 0\n");
2911 fprintf(output,"\n");
2912 fprintf(output,"Part (or all) of predicate with depth > 1 suppressed by ");
2913 fprintf(output,"alternative without predicate\n\n");
2914 MR_dumpPred(suppressPredicate,1);
2915 fprintf(output,"The token sequence which is suppressed:");
2916 fprintf(output," (");
2917 for (i=1; i <= suppressChainLength; i++) {
2918 fprintf(output," %s",TerminalString(suppressChain[i]));
2919 };
2920 fprintf(output," )\n");
2921 fprintf(output,"The sequence of references which generate that sequence of tokens:\n\n");
2922
2923 MR_backTraceDumpItemReset();
2924
2925 for (i=0; i < MR_BackTraceStack.count ; i++) {
2926 MR_backTraceDumpItem(output,0,(Node *) MR_BackTraceStack.data[i]);
2927 };
2928 fprintf(output,"\n");
2929 fprintf(output,"#endif\n");
2930 }
2931 }
2932
2933 #ifdef __USE_PROTOS
2934 void MR_markCompromisedRule(Node *n)
2935 #else
2936 void MR_markCompromisedRule(n)
2937 Node *n;
2938 #endif
2939 {
2940 RuleEntry *q;
2941 Node *mark=NULL;
2942 Junction *j;
2943
2944 if (n->ntype == nRuleRef) {
2945 mark=(Node *) MR_ruleReferenced( (RuleRefNode *) n);
2946 } else if (n->ntype == nToken) {
2947 mark=n;
2948 } else if (n->ntype == nJunction) {
2949 j=(Junction *)n;
2950 switch (j->jtype) {
2951 case aOptBlk:
2952 case aLoopBlk:
2953 case RuleBlk:
2954 case EndRule:
2955 case aPlusBlk:
2956 case aLoopBegin:
2957 mark=n;
2958 break;
2959 default:
2960 break;
2961 };
2962 }
2963
2964 if (mark == NULL) return;
2965
2966 require (RulePtr != NULL,"RulePtr not initialized");
2967
2968 q = (RuleEntry *) hash_get(Rname,mark->rname);
2969 require (q != NULL,"RuleEntry not found");
2970 set_orel(q->rulenum,&MR_CompromisedRules);
2971 }
2972
2973 #ifdef __USE_PROTOS
2974 void MR_alphaBetaTraceReport(void)
2975 #else
2976 void MR_alphaBetaTraceReport()
2977 #endif
2978 {
2979 int i;
2980
2981 if (! AlphaBetaTrace) return;
2982
2983 MR_AlphaBetaMessageCount++;
2984
2985 fprintf(output,"\n");
2986 fprintf(output,"#if 0\n");
2987 fprintf(output,"\n");
2988 fprintf(output,"Trace of references leading to attempt to compute the follow set of\n");
2989 fprintf(output,"alpha in an \"(alpha)? beta\" block. It is not possible for antlr to\n");
2990 fprintf(output,"compute this follow set because it is not known what part of beta has\n");
2991 fprintf(output,"already been matched by alpha and what part remains to be matched.\n");
2992 fprintf(output,"\n");
2993 fprintf(output,"Rules which make use of the incorrect follow set will also be incorrect\n");
2994 fprintf(output,"\n");
2995
2996 MR_backTraceDumpItemReset();
2997
2998 for (i=0; i < MR_BackTraceStack.count ; i++) {
2999 MR_backTraceDumpItem(output,0,(Node *) MR_BackTraceStack.data[i]);
3000 if (i < MR_BackTraceStack.count-1) {
3001 MR_markCompromisedRule( (Node *) MR_BackTraceStack.data[i]);
3002 };
3003 };
3004 fprintf(output,"\n");
3005 fprintf(output,"#endif\n");
3006 }
3007
3008 #ifdef __USE_PROTOS
3009 void MR_dumpRuleSet(set s)
3010 #else
3011 void MR_dumpRuleSet(s)
3012 set s;
3013 #endif
3014 {
3015 unsigned *cursor;
3016 unsigned *origin=set_pdq(s);
3017
3018 require(origin != NULL,"set_pdq failed");
3019
3020 if (RulePtr == NULL) {
3021 fprintf(stderr,"RulePtr[] not yet initialized");
3022 } else {
3023 for (cursor=origin; *cursor != nil ; cursor++) {
3024 /**** if (cursor != origin) fprintf(stderr,","); ****/
3025 fprintf(stderr," %s",RulePtr[*cursor]->rname);
3026 fprintf(stderr,"\n");
3027 };
3028 free( (char *) origin);
3029 };
3030 }
3031