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.
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
40 void dumppred(Predicate
*);
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
55 int MR_secondPredicateUnreachable(Predicate
*first
,Predicate
*second
)
57 int MR_secondPredicateUnreachable(first
,second
)
67 } else if (second
== NULL
) {
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 */
74 return 0; /* look different */
76 } else if (first
->down
== NULL
&& second
->down
!= NULL
) {
78 if (second
->expr
== PRED_AND_LIST
) {
80 /* unreachable if first covers any child of second */
82 for (s
=second
->down
; s
!= NULL
; s
=s
->right
) {
83 if (MR_secondPredicateUnreachable(first
,s
)) {
88 } else if (second
->expr
== PRED_OR_LIST
) {
90 /* unreachable if first covers every child of second */
92 for (s
=second
->down
; s
!= NULL
; s
=s
->right
) {
93 if (!MR_secondPredicateUnreachable(first
,s
)) {
99 require (0,"Illegal pred->expr");
100 return 0; /* MR20 Make compiler happy */
102 } else if (first
->down
!= NULL
&& second
->down
== NULL
) {
103 if (first
->expr
== PRED_AND_LIST
) {
105 /* unreachable if every child of first covers second */
107 for (f
=first
->down
; f
!= NULL
; f
=f
->right
) {
108 if (!MR_secondPredicateUnreachable(f
,second
)) {
113 } else if (first
->expr
== PRED_OR_LIST
) {
115 /* unreachable if any child of first covers second */
117 for (f
=first
->down
; f
!= NULL
; f
=f
->right
) {
118 if (MR_secondPredicateUnreachable(f
,second
)) {
124 require (0,"Illegal predicate->expr");
125 return 0; /* MR20 Make compiler happy */
129 if (first
->expr
== PRED_AND_LIST
&& second
->expr
== PRED_AND_LIST
) {
131 /* unreachable if each child of first covers at least one child of second */
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
;
143 } else if (first
->expr
== PRED_AND_LIST
&& second
->expr
== PRED_OR_LIST
) {
145 /* unreachable if each child of first covers ALL of second's children */
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;
154 } else if (first
->expr
== PRED_OR_LIST
&& second
->expr
== PRED_AND_LIST
) {
156 /* unreachable if any child of second is covered by any child of first */
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;
165 } else if (first
->expr
== PRED_OR_LIST
&& second
->expr
== PRED_OR_LIST
) {
167 /* unreachable if every child of second is covered by some child of first */
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
;
180 require (0,"Illegal predicate->expr");
181 return 0; /* MR20 Make compiler happy */
184 return 0; /* MR20 MSVC 5.0 complains about missing return statement */
188 void MR_xxxIndent(FILE *f
,int depth
)
190 void MR_xxxIndent(f
,depth
)
197 for (i
=0; i
<depth
; i
++) {
203 void MR_stderrIndent(int depth
)
205 void MR_stderrIndent(depth
)
209 MR_xxxIndent(stderr
,depth
);
213 void MR_outputIndent(int depth
)
215 void MR_outputIndent(depth
)
219 MR_xxxIndent(output
,depth
);
223 void MR_set_reuse(set
*s
)
234 void MR_dumpPredRuleRefStack(FILE *iounit
,int indent
)
236 void MR_dumpPredRuleRefStack(iounit
,indent
)
243 int count
=MR_PredRuleRefStack
.count
;
244 RuleRefNode
*rrn
=NULL
;
248 fprintf(iounit
,"empty\n");
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
);
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
]);
266 void MR_dumpTreeF(FILE *f
,int depth
,Tree
*tree
,int across
)
268 void MR_dumpTreeF(f
,depth
,tree
,across
)
275 int newAcross
=across
;
277 if (tree
== NULL
) return;
278 if (tree
->down
!= NULL
) {
279 fprintf(output
,"\n");
280 MR_outputIndent(depth
);
281 fprintf(output
, "(root =");
283 if (tree
->token
== ALT
) {
284 fprintf(output
," %-16s","Alt");
285 } else if (tree
->token
==EpToken
) {
286 fprintf(output
,"(%d)%13s",tree
->v
.rk
," ");
288 fprintf(output
," %-16s",TerminalString(tree
->token
));
290 if (tree
->down
!= NULL
) {
291 fprintf(output
,"\n");
292 MR_outputIndent(depth
+1);
293 MR_dumpTreeF(f
,depth
+1,tree
->down
,1);
295 fprintf(output
,"\n");
296 MR_outputIndent(depth
);
300 fprintf(output
,"\n");
301 MR_outputIndent(depth
);
304 MR_dumpTreeF(f
,depth
,tree
->right
,newAcross
+1);
308 void MR_dumpTreeX(int depth
,Tree
*tree
,int across
)
310 void MR_dumpTreeX(depth
,tree
,across
)
316 MR_dumpTreeF(output
,depth
,tree
,across
);
320 void MR_dumpTokenSet(FILE *f
,int depth
,set s
)
322 void MR_dumpTokenSet(f
,depth
,s
)
335 MR_xxxIndent(f
,depth
+1);
341 require(pdq
!= NULL
,"set_pdq failed");
343 for (i
=0 ; ; i
=i
+4) {
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
]));
350 if (pdq
[i
+j
] == nil
) break;
357 void MR_dumpPred1(int depth
,Predicate
*p
,int withContext
)
359 void MR_dumpPred1(depth
,p
,withContext
)
368 MR_outputIndent(depth
);
369 fprintf(output
,"The predicate is empty (or always true)\n\n");
372 if (p
->down
!= NULL
) {
373 MR_outputIndent(depth
);
376 /* MR14a Left out print expression in fprintf
377 Reported by Manuel Kessler (mlkessle@cip.physik.uni-wuerzburg.de)
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
);
383 fprintf(output
,"%s expr\n\n",p
->expr
);
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);
392 fprintf(output
," depth=k=%d",p
->k
);
393 if (p
->source
!= NULL
&& p
->source
->guardpred
) {
394 fprintf(output
," (\"=>\" guard)");
396 if (p
->source
!= NULL
&& p
->source
->ampersandPred
!= NULL
) {
397 fprintf(output
," (\"&&\" guard)");
399 k
=set_int(p
->completionSet
);
401 fprintf(output
," Incomplete Set at k=%d !",k
);
403 k
=set_int(p
->completionTree
);
405 fprintf(output
," Incomplete Tree at k=%d !",k
);
407 if (p
->source
!= NULL
) {
408 fprintf(output
," rule %s line %d %s",
409 p
->source
->rname
,p
->source
->line
,FileStr
[p
->source
->file
]);
411 fprintf(output
,"\n");
413 (HoistPredicateContext
||
414 ! set_nil(p
->scontext
[1]) ||
415 p
->tcontext
!= NULL
)) {
417 MR_outputIndent(depth
+1);
418 fprintf(output
,"set context: ");
419 MR_dumpTokenSet(output
,depth
+1,p
->scontext
[1]);
422 MR_outputIndent(depth
+1);
423 fprintf(output
,"tree context:");
424 if (p
->tcontext
== NULL
) {
425 fprintf(output
," null");
427 MR_dumpTreeX(depth
+2,p
->tcontext
,0);
429 fprintf(output
,"\n");
432 fprintf(output
,"\n");
434 if (p
->down
!= NULL
) {
435 MR_dumpPred1(depth
+1,p
->down
,withContext
);
437 if (p
->right
!= NULL
) {
438 MR_dumpPred1(depth
,p
->right
,withContext
);
443 void MR_dumpPred(Predicate
*p
,int withContext
)
445 void MR_dumpPred(p
,withContext
)
450 MR_dumpPred1(0,p
,withContext
);
454 Tree
* MR_make_tree_from_set(set s
)
456 Tree
* MR_make_tree_from_set(s
)
465 unsigned *pdq
=set_pdq(s
);
468 for (i
=0 ; pdq
[i
] != nil
; i
++) {
469 node
=tnode( (int) pdq
[i
]);
474 free ( (char *) pdq
);
480 void MR_check_pred_too_long(Predicate
*p
,set completion
)
482 void MR_check_pred_too_long(p
,completion
)
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
);
499 int MR_predicate_context_completed(Predicate
*p
)
501 int MR_predicate_context_completed(p
)
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;
511 return MR_predicate_context_completed(p
->down
) &
512 MR_predicate_context_completed(p
->right
);
516 Node
* MR_advance(Node
*n
)
522 if (n
== NULL
) return NULL
;
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
;
530 return NULL
; /* MSVC 5.0 complains about missing return statement */
534 Junction
* MR_find_endRule(Node
*n
)
536 Junction
* MR_find_endRule(n
)
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
) {
548 return (Junction
*)next
;
552 Intersection: a branch which is shorter is chosen
553 over one which is longer: (A B C) intersect (A B) yields (A B).
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)
561 Tree
*MR_computeTreeIntersection(Tree
*l
,Tree
*r
)
563 Tree
*MR_computeTreeIntersection(l
,r
)
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");
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");
585 tail
=&(result
->down
);
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
);
593 tail
=&(match
->right
);
599 result
=tshrink(result
);
600 result
=tflatten( result
);
601 result
=tleft_factor( result
);
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.
614 Actually, this may not be true once one throws in
615 guard predicates which are defined by the user, not
619 /* requires input trees to be in "canonical" format */
622 Tree
*MR_computeTreeAND(Tree
*l
,Tree
*r
)
624 Tree
*MR_computeTreeAND(l
,r
)
635 if (l
== NULL
) return tdup(r
);
636 if (r
== NULL
) return tdup(l
);
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");
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");
648 tail
=&(result
->down
);
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
);
656 tail
=&(match
->right
);
662 result
=tshrink(result
);
663 result
=tflatten( result
);
664 result
=tleft_factor( result
);
669 void MR_union_plain_sets1(Predicate
*p
,set
*theUnion
)
671 void MR_union_plain_sets1(p
,theUnion
)
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
);
684 set
MR_union_plain_sets(Predicate
*p
)
686 set
MR_union_plain_sets(p
)
694 MR_union_plain_sets1(p
,&theUnion
);
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)
704 Tree
*MR_compute_pred_tree_ctxXX(Predicate
*p
)
706 Tree
*MR_compute_pred_tree_ctxXX(p
)
714 if (p
== NULL
) return NULL
;
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
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
);
735 result
=tshrink(result
);
736 result
=tflatten( result
);
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)
743 /**** result=tleft_factor( result ); ****/
748 ** if (p
->expr
== PRED_AND_LIST
) {
757 ** require (l
->right
!= NULL
,"MR_compute_pred_tree - AND has only one child");
759 **/
* l1
and r1 should already be in
"canonical" format */
761 ** l1
=MR_compute_pred_tree(l
);
762 ** for (r
=l
->right
; r
!= NULL
; r
=r
->right
) {
763 ** r1
=MR_compute_pred_tree(r
);
765 ** l1
=MR_computeTreeAND(l1
,r1
);
770 **/
* result from computeTreeAND should be in
"canonical" format */
774 **/
* result of MR_computeTreeAND should be in
"canonical" format */
781 result
=MR_make_tree_from_set(p
->scontext
[1]);
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
);
793 void MR_pred_depth(Predicate
*p
,int *maxDepth
)
795 void MR_pred_depth(p
,maxDepth
)
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
;
805 MR_pred_depth(p
->down
,maxDepth
);
806 MR_pred_depth(p
->right
,maxDepth
);
809 /* this computes the OR of all the contexts */
812 set
MR_compute_pred_set(Predicate
*p
)
814 set
MR_compute_pred_set(p
)
823 if (p
== NULL
) return empty
;
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; */
834 for (q
=p
->down
; q
!= NULL
; q
=q
->right
) {
835 t
=MR_compute_pred_set(q
);
840 } else if (p
->k
> 1) {
843 return set_dup(p
->scontext
[1]);
848 set
MR_First(int ck
,Junction
*j
,set
*incomplete
)
850 set
MR_First(ck
,j
,incomplete
)
861 require(j
->ntype
==nJunction
, "MR_First: non junction passed");
863 p
= analysis_point((Junction
*)j
->p1
);
865 REACH(p
,ck
,incomplete
,tokensUsed
);
871 void MR_cleanup_pred_trees(Predicate
*p
)
873 void MR_cleanup_pred_trees(p
)
879 if (p
== NULL
) return;
880 if (p
->expr
!= PRED_OR_LIST
&&
881 p
->expr
!= PRED_AND_LIST
) {
888 MR_cleanup_pred_trees(p
->down
);
889 MR_cleanup_pred_trees(p
->right
);
892 /* does NOT return canonical tree */
895 Tree
* MR_remove_epsilon_from_tree(Tree
*t
)
897 Tree
* MR_remove_epsilon_from_tree(t
)
901 if (t
== NULL
) return NULL
;
903 /* I think ALT can be ignored as a special case */
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
);
911 u
=MR_remove_epsilon_from_tree(t
->right
);
919 void MR_complete_set(int predDepth
,set
*tokensUsed
,set
*incomplete
)
921 void MR_complete_set(predDepth
,tokensUsed
,incomplete
)
928 RuleRefNode
*ruleRef
;
932 Junction
*save_MR_RuleBlkWithHalt
;
934 if (set_int(*incomplete
) > (unsigned) predDepth
) {
938 require(MR_PredRuleRefStack
.count
== MR_RuleBlkWithHaltStack
.count
,
939 "RuleRefStack and RuleBlkWithHaltStack not same size");
941 require(MR_RuleBlkWithHalt
== NULL
||
942 (MR_RuleBlkWithHalt
->jtype
== RuleBlk
&& MR_RuleBlkWithHalt
->end
->halt
== TRUE
),
943 "RuleBlkWithHalt has no halt set");
945 save_MR_RuleBlkWithHalt
=MR_RuleBlkWithHalt
;
947 if (MR_RuleBlkWithHalt
!= NULL
) {
948 MR_RuleBlkWithHalt
->end
->halt
=FALSE
;
951 for (i
=MR_PredRuleRefStack
.count
-1; i
>= 0 ; i
--) {
952 ruleRef
=(RuleRefNode
*)MR_PredRuleRefStack
.data
[i
];
953 if (ruleRef
== NULL
) continue;
955 MR_RuleBlkWithHalt
=(Junction
*)MR_RuleBlkWithHaltStack
.data
[i
];
956 if (MR_RuleBlkWithHalt
!= NULL
) MR_RuleBlkWithHalt
->end
->halt
=TRUE
;
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
);
970 if (MR_RuleBlkWithHalt
!= NULL
) MR_RuleBlkWithHalt
->end
->halt
=FALSE
;
972 set_orin(incomplete
,rk2
); /* remember what we couldn't do */
974 if (set_int(*incomplete
) > (unsigned) predDepth
) break; /* <=== another exit from loop */
977 MR_RuleBlkWithHalt
=save_MR_RuleBlkWithHalt
;
978 if (MR_RuleBlkWithHalt
!= NULL
) {
979 MR_RuleBlkWithHalt
->end
->halt
=TRUE
;
984 void MR_complete_tree(int predDepth
,Tree
**t
,set
*incomplete
)
986 void MR_complete_tree(predDepth
,t
,incomplete
)
993 RuleRefNode
*ruleRef
;
997 Junction
*save_MR_RuleBlkWithHalt
;
998 int saveConstrainSearch
;
1000 if (set_int(*incomplete
) > (unsigned) predDepth
) {
1004 require(MR_PredRuleRefStack
.count
== MR_RuleBlkWithHaltStack
.count
,
1005 "RuleRefStack and RuleBlkWithHaltStack not same size");
1007 require(MR_RuleBlkWithHalt
== NULL
||
1008 (MR_RuleBlkWithHalt
->jtype
== RuleBlk
&& MR_RuleBlkWithHalt
->end
->halt
== TRUE
),
1009 "RuleBlkWithHalt has no halt set");
1011 save_MR_RuleBlkWithHalt
=MR_RuleBlkWithHalt
;
1012 saveConstrainSearch
=ConstrainSearch
;
1015 if (MR_RuleBlkWithHalt
!= NULL
) {
1016 MR_RuleBlkWithHalt
->end
->halt
=FALSE
;
1019 for (i
=MR_PredRuleRefStack
.count
-1; i
>= 0 ; i
--) {
1020 ruleRef
=(RuleRefNode
*)MR_PredRuleRefStack
.data
[i
];
1021 if (ruleRef
== NULL
) continue;
1023 MR_RuleBlkWithHalt
=(Junction
*)MR_RuleBlkWithHaltStack
.data
[i
];
1025 if (MR_RuleBlkWithHalt
!= NULL
) MR_RuleBlkWithHalt
->end
->halt
=TRUE
;
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
);
1035 TRAV(ruleRef
->next
,k2
,&rk2
,u
);
1037 /* any subtrees missing k2 tokens, add u onto end */
1043 set_orin(incomplete
,rk2
); /* remember what we couldn't do */
1046 if (MR_RuleBlkWithHalt
!= NULL
) MR_RuleBlkWithHalt
->end
->halt
=FALSE
;
1048 if (set_int(*incomplete
) > (unsigned) predDepth
) break; /* <=== another exit from loop */
1051 MR_RuleBlkWithHalt
=save_MR_RuleBlkWithHalt
;
1053 if (MR_RuleBlkWithHalt
!= NULL
) {
1054 MR_RuleBlkWithHalt
->end
->halt
=TRUE
;
1056 ConstrainSearch
=saveConstrainSearch
;
1060 void MR_complete_predicates(int predDepth
,Predicate
*pred
)
1062 void MR_complete_predicates(predDepth
,pred
)
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
));
1073 MR_complete_predicates(predDepth
,pred
->down
);
1074 MR_complete_predicates(predDepth
,pred
->right
);
1078 Junction
* MR_junctionWithoutP2(Junction
*j
)
1080 Junction
* MR_junctionWithoutP2(j
)
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 */
1091 if (thisAlt
->p2
!= NULL
) {
1092 if (thisAlt
->p1
->ntype
== nJunction
) {
1093 thisAlt
=(Junction
*) thisAlt
->p1
;
1095 thisAlt
=newJunction();
1097 thisAlt
->rname
=j
->rname
;
1098 thisAlt
->file
=j
->file
;
1099 thisAlt
->line
=j
->line
;
1100 j
->p1
=(Node
*)thisAlt
;
1107 int MR_tree_equ(Tree
*big
, Tree
*small
) {
1109 int MR_tree_equ(big
,small
)
1120 if (small
== NULL
&& big
== NULL
) return 1;
1121 if (small
== NULL
) return 0;
1122 if (big
== NULL
) return 0;
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
);
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
);
1134 for (s
=small
; s
!= NULL
; s
=s
->right
) {
1136 require(s
->token
!= EpToken
,"MR_tree_equ: s->EpToken unexpected\n");
1138 for (b
=big
; b
!= NULL
; b
=b
->right
) {
1140 require(b
->token
!= EpToken
,"MR_tree_equ: b->EpToken unexpected\n");
1143 if (bcount
!= scount
) return 0;
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
;
1158 /* this does not compare sources - only contexts ! */
1161 int MR_identicalContext(Predicate
*p
,Predicate
*q
)
1163 int MR_identicalContext(p
,q
)
1168 if (p
->k
!= q
->k
) return 0;
1169 require ( (p
->tcontext
== NULL
) == (q
->tcontext
== NULL
),
1170 "tcontext inconsistent");
1172 return set_equ(p
->scontext
[1],q
->scontext
[1]);
1174 return MR_tree_equ(p
->tcontext
,q
->tcontext
);
1179 void MR_reportSetSuppression(int predDepth
,
1180 set predSet
,set plainSet
,Junction
*jPred
,Junction
*jPlain
,Predicate
*p
)
1182 void MR_reportSetSuppression(predDepth
,predSet
,plainSet
,jPred
,jPlain
,p
)
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
]);
1199 fprintf(output
," WITHOUT predicate: all alternatives without predicates (combined)\n");
1201 if (predDepth
== 1) {
1202 fprintf(output
,"\nThe context set for the predicate:\n");
1203 MR_dumpTokenSet(output
,1,predSet
);
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");
1216 void MR_reportSetRestriction(int predDepth
,set predSet
,set plainSet
,
1217 Junction
*jPred
,Junction
*jPlain
,Predicate
*origPred
,Predicate
*newPred
)
1219 void MR_reportSetRestriction(predDepth
,predSet
,plainSet
,jPred
,jPlain
,origPred
,newPred
)
1225 Predicate
*origPred
;
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");
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
]);
1245 fprintf(output
," WITHOUT predicate: all alternatives without predicates (combined)\n");
1247 if (predDepth
== 1) {
1248 fprintf(output
,"\nThe original context set for the predicate:\n");
1249 MR_dumpTokenSet(output
,1,predSet
);
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
);
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");
1266 /* don't use Pass3 by itself unless you know that inverted is not important */
1269 Predicate
* MR_removeRedundantPredPass3(Predicate
*p
)
1271 Predicate
* MR_removeRedundantPredPass3(p
)
1277 if (p
== NULL
) return NULL
;
1278 p
->right
=MR_removeRedundantPredPass3(p
->right
);
1279 p
->down
=MR_removeRedundantPredPass3(p
->down
);
1286 if (p
->expr
== PRED_AND_LIST
||
1287 p
->expr
== PRED_OR_LIST
) {
1288 if (p
->down
== NULL
) {
1294 if (p
->down
!= NULL
&& p
->down
->right
== NULL
) {
1306 void MR_removeRedundantPredPass2(Predicate
*p
)
1308 void MR_removeRedundantPredPass2(p
)
1314 if (p
== NULL
) return;
1316 if (p
->expr
== PRED_AND_LIST
) {
1317 for (q
=p
->down
; q
!= NULL
; q
=q
->right
) {
1318 MR_removeRedundantPredPass2(q
);
1320 if (q
->constValue
== 0) {
1331 if (p
->expr
== PRED_OR_LIST
) {
1332 for (q
=p
->down
; q
!= NULL
; q
=q
->right
) {
1333 MR_removeRedundantPredPass2(q
);
1335 if (q
->constValue
== 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
:
1354 rule
: (A
)? => <<p
>>? sub1
; /* 1 */
1355 | (B
)? => <<r
>>? sub2
/* 2 */
1356 sub1
: (A
)? => <<q
>>? A B
/* 3 */
1357 | B
/* 4 - suppresses line 2 */
1362 void MR_apply_restriction1(Predicate
*pred
,set
*plainSet
,int *changed
)
1364 void MR_apply_restriction1(pred
,plainSet
,changed
)
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
);
1377 t
=set_dif(pred
->scontext
[1],*plainSet
);
1378 if (*changed
== 0 &&
1379 !set_equ(t
,pred
->scontext
[1])) {
1385 set_free(pred
->scontext
[1]);
1386 pred
->scontext
[1]=t
;
1392 void MR_orin_plainSet(Predicate
*p
,set plainSet
)
1394 void MR_orin_plainSet(p
,plainSet
)
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
);
1405 Predicate
*PRED_SUPPRESS
;
1408 Predicate
* MR_find_in_aSubBlk(Junction
*alt
)
1410 Predicate
* MR_find_in_aSubBlk(alt
)
1414 Predicate
*root
=NULL
;
1415 Predicate
**tail
=NULL
;
1421 Predicate
**predList
;
1434 Predicate
*origPred
;
1435 int depth1
=1; /* const int */
1441 union_plainSet
=empty
;
1446 if (PRED_SUPPRESS
== NULL
) {
1447 PRED_SUPPRESS
=new_pred();
1448 PRED_SUPPRESS
->expr
="Predicate Suppressed";
1451 /* this section just counts the number of "interesting" alternatives */
1452 /* in order to allocate arrays */
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
) {
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 ?
1469 if (alt
->jtype
== aPlusBlk
) {
1473 jList
=(Junction
**)calloc(nAlts
,sizeof(Junction
*));
1474 require(jList
!=NULL
,"cannot allocate MR_find_in_aSubBlk jList");
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
;
1480 predList
=(Predicate
**)calloc(nAlts
,sizeof(Predicate
*));
1481 require(predList
!=NULL
,"cannot allocate MR_find_in_aSubBlk predList");
1483 matchList
=(int *)calloc(nAlts
,sizeof(int));
1484 require(matchList
!=NULL
,"cannot allocate MR_find_in_aSubBlk matchList");
1486 /* this section just fills in the arrays previously allocated */
1487 /* the most interesting one is matchList[] */
1489 /* bit 0 => this alt has a semantic pred which is "covered" */
1490 /* by an alt without a semantic pred. Don't hoist. */
1494 i
++,p
=(Junction
*)p
->p2
) {
1496 /* ignore empty alts */
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
]);
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
;
1514 set_orin(&union_plainSet
,plainContext
[i
]);
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.
1529 * When we find such a case check for one of three subcases:
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
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:
1543 * ( <<a>>? a1 a2 a3 | <<b>>? b1 b2 b3 )
1545 * both a3 and b3 have the same follow sets because they are both at the end of
1546 * alternatives in the same block.
1549 for (i
=0; i
< nAlts
; i
++) {
1550 if (jList
[i
] == NULL
) continue;
1551 if (predList
[i
] == NULL
) continue;
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() */
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");
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.
1569 MR_complete_predicates(predDepth
,predList
[i
]);
1571 if (predList
[i
] != NULL
) {
1572 MR_cleanup_pred_trees(predList
[i
]); /* flatten & left factor */
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.
1581 if (predDepth
== 1) {
1583 MR_set_reuse(&predSet
);
1584 predSet
=MR_compute_pred_set(predList
[i
]); /* ignores k>1 predicates */
1586 for (j
=0; j
< nAlts
; j
++) {
1587 if (jList
[j
] == NULL
) continue;
1588 if (j
== i
) continue;
1590 MR_set_reuse(&setDif
);
1591 setDif
=set_dif(predSet
,plainContext
[j
]);
1592 if (set_nil(setDif
)) {
1594 MR_reportSetSuppression(predDepth
,predSet
,plainContext
[j
],jList
[i
],jList
[j
],predList
[i
]);
1595 predicate_free(predList
[i
]);
1596 predList
[i
]=PRED_SUPPRESS
;
1600 }; /* end loop on j */
1604 /* predicate_dup is only to give good error messages */
1605 /* remember to do a predicate_free() */
1607 origPred
=predicate_dup(predList
[i
]);
1608 MR_apply_restriction1(predList
[i
],&union_plainSet
,&changed
);
1611 /* don't use Pass3 by itself unless you know that inverted is not important */
1613 newPred
=MR_removeRedundantPredPass3(predList
[i
]);
1614 newPred
=MR_predSimplifyALL(newPred
);
1615 if (newPred
== NULL
) {
1617 MR_reportSetSuppression(predDepth
,predSet
,union_plainSet
,jList
[i
],
1619 predList
[i
]=PRED_SUPPRESS
;
1621 MR_reportSetRestriction(predDepth
,predSet
,union_plainSet
,jList
[i
],
1622 NULL
,origPred
,newPred
);
1623 predList
[i
]=newPred
;
1626 predicate_free(origPred
);
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.
1636 if (predDepth
> 1 ) {
1640 /* predicate_dup is only to give good error messages */
1641 /* remember to do a predicate_free() */
1643 origPred
=predicate_dup(predList
[i
]);
1644 MR_apply_restriction1(predList
[i
],&union_plainSet
,&changed
);
1646 newPred
=MR_removeRedundantPredPass3(predList
[i
]);
1647 newPred
=MR_predSimplifyALL(newPred
);
1648 if (newPred
== NULL
) {
1650 MR_reportSetSuppression(predDepth
,predSet
,union_plainSet
,jList
[i
],
1652 predList
[i
]=PRED_SUPPRESS
;
1654 MR_reportSetRestriction(predDepth
,predSet
,union_plainSet
,jList
[i
],
1655 NULL
,origPred
,newPred
);
1656 predList
[i
]=newPred
;
1659 predicate_free(origPred
);
1669 root
->expr
=PRED_OR_LIST
;
1670 tail
= &(root
->down
);
1672 for (i
=0 ; i
< nAlts
; i
++) {
1673 if (jList
[i
] == NULL
) continue;
1675 if (predList
[i
] == NULL
) {
1677 } else if ( (matchList
[i
] & 1) != 0) {
1678 if (predList
[i
] != PRED_SUPPRESS
) {
1679 predicate_free(predList
[i
]);
1684 /* make an OR list of predicates */
1687 tail
=&(predList
[i
]->right
);
1690 /* if just one pred, remove OR root */
1692 if (root
->down
== NULL
) {
1693 predicate_free(root
);
1695 } else if (root
->down
->right
== NULL
) {
1696 Predicate
*p
=root
->down
;
1698 predicate_free(root
);
1702 root
=MR_predSimplifyALL(root
);
1704 MR_orin_plainSet(root
,union_plainSet
);
1707 set_free(union_plainSet
);
1708 set_free(incomplete
);
1709 set_free(setChange
);
1712 for (m
=0; m
< nAlts
; m
++) set_free(plainContext
[m
]);
1714 free ( (char *) jList
);
1715 free ( (char *) predList
);
1716 free ( (char *) matchList
);
1717 free ( (char *) plainContext
);
1723 void MR_predContextPresent(Predicate
*p
,int *allHaveContext
,int *noneHaveContext
)
1725 void MR_predContextPresent(p
,allHaveContext
,noneHaveContext
)
1727 int *allHaveContext
;
1728 int *noneHaveContext
;
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
)) {
1742 MR_predContextPresent(p
->down
,allHaveContext
,noneHaveContext
);
1746 int MR_pointerStackPush(PointerStack
*ps
,void *dataPointer
)
1748 int MR_pointerStackPush(ps
,dataPointer
)
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
];
1764 if (ps
->data
!= NULL
) free( (char *) ps
->data
);
1768 ps
->data
[ps
->count
]=dataPointer
;
1774 void * MR_pointerStackPop(PointerStack
*ps
)
1776 void * MR_pointerStackPop(ps
)
1782 require(ps
->count
> 0,"MR_pointerStackPop underflow");
1784 dataPointer
=ps
->data
[ps
->count
-1];
1785 ps
->data
[ps
->count
-1]=NULL
;
1791 void * MR_pointerStackTop(PointerStack
*ps
)
1793 void * MR_pointerStackTop(ps
)
1797 require(ps
->count
> 0,"MR_pointerStackTop underflow");
1798 return ps
->data
[ps
->count
-1];
1802 void MR_pointerStackReset(PointerStack
*ps
)
1804 void MR_pointerStackReset(ps
)
1809 if (ps
->data
!= NULL
) {
1810 for (i
=0; i
< ps
->count
; i
++) {
1818 Junction
*MR_nameToRuleBlk(char *name
)
1820 Junction
*MR_nameToRuleBlk(name
)
1826 require (RulePtr
!= NULL
,"MR_nameToRule: RulePtr not initialized");
1828 if (name
== NULL
) return NULL
;
1830 q
= (RuleEntry
*) hash_get(Rname
,name
);
1835 return RulePtr
[q
->rulenum
];
1840 Junction
* MR_ruleReferenced(RuleRefNode
*rrn
)
1842 Junction
* MR_ruleReferenced(rrn
)
1846 return MR_nameToRuleBlk(rrn
->text
);
1850 void MR_comparePredLeaves(Predicate
*me
,Predicate
*myParent
,Predicate
*him
,Predicate
*hisParent
)
1852 void MR_comparePredLeaves(me
,myParent
,him
,hisParent
)
1854 Predicate
*myParent
;
1856 Predicate
*hisParent
;
1859 if (me
== NULL
) return;
1861 MR_comparePredLeaves(me
->right
,myParent
,him
,hisParent
);
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
);
1869 if (me
->source
!= NULL
) {
1871 /* predicate->invert can be set only in the predEntry predicates */
1872 /* thus they are only visible after the predEntry predicates have been "unfolded" */
1874 int sameSource
=(me
->source
== him
->source
);
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
)) {
1883 /* identical predicates */
1885 if (hisParent
->expr
== PRED_OR_LIST
&&
1886 myParent
->expr
== PRED_OR_LIST
) {
1888 } else if (hisParent
->expr
== PRED_AND_LIST
&&
1889 myParent
->expr
== PRED_AND_LIST
) {
1891 } else if ( (hisParent
->expr
== PRED_OR_LIST
&&
1892 myParent
->expr
== PRED_AND_LIST
)
1894 (hisParent
->expr
== PRED_AND_LIST
&&
1895 myParent
->expr
== PRED_OR_LIST
)
1897 myParent
->redundant
=1;
1899 require (0,"MR_comparePredLeaves: not both PRED_LIST");
1902 }; /* end same source or same predEntrr with same invert sense */
1904 /* same predEntry but opposite invert sense */
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
)
1919 (hisParent
->expr
== PRED_AND_LIST
&&
1920 myParent
->expr
== PRED_OR_LIST
)
1924 require (0,"MR_comparePredLeaves: not both PRED_LIST");
1927 }; /* end same predEntry with opposite invert sense */
1930 MR_comparePredLeaves(me
->right
,myParent
,him
,hisParent
);
1936 void MR_removeRedundantPredPass1(Predicate
*me
,Predicate
*myParent
)
1938 void MR_removeRedundantPredPass1(me
,myParent
)
1940 Predicate
*myParent
;
1943 if (me
== NULL
) return;
1944 if (me
->redundant
) {
1945 MR_removeRedundantPredPass1(me
->right
,myParent
);
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
);
1953 require (me
->source
!= NULL
,"me->source == NULL");
1954 if (myParent
!= NULL
) {
1955 MR_comparePredLeaves(myParent
->down
,myParent
,me
,myParent
);
1957 MR_removeRedundantPredPass1(me
->right
,myParent
);
1961 /* pretty much ignores things with the inverted bit set */
1964 Predicate
*MR_predFlatten(Predicate
*p
)
1966 Predicate
*MR_predFlatten(p
)
1970 if (p
== NULL
) return NULL
;
1971 if (p
->expr
== PRED_OR_LIST
1972 || p
->expr
== PRED_AND_LIST
) {
1978 char *PRED_XXX_LIST
=p
->expr
;
1980 require (p
->down
!= NULL
,"MR_predFlatten AND/OR no child");
1983 p
->down
=MR_predFlatten(p
->down
);
1984 p
->right
=MR_predFlatten(p
->right
);
1986 if (child
->right
== NULL
) {
1987 child
->right
=p
->right
;
1990 if (p
->inverted
) child
->inverted
=!child
->inverted
;
1995 /* make a single list of all children and grandchildren */
1998 for (child
=p
->down
; child
!= NULL
; child
=next
) {
1999 if (child
->expr
!= PRED_XXX_LIST
2001 || child
->predEntry
!= NULL
) {
2003 tail
=&(child
->right
);
2006 for (gchild
=child
->down
;
2008 gchild
=gchild
->right
) {
2010 tail
=&(gchild
->right
);
2015 predicate_free(child
);
2021 p
->right
=MR_predFlatten(p
->right
);
2026 static char *alwaysFalseWarning
=NULL
;
2029 Predicate
*checkPredicateConflict(Predicate
*p
)
2031 Predicate
*checkPredicateConflict(p
)
2036 if (p
->constValue
== 1) {
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");
2048 if (alwaysFalseWarning
!= CurRule
) {
2049 alwaysFalseWarning
=CurRule
;
2051 warnNoFL(eMsg1("one (or more) predicate expression hoisted into rule \"%s\" are always false \
2052 - see output file for more information",CurRule
));
2054 warnNoFL(eMsg1("one (or more) predicate expressions hoisted into rule \"%s\" are always false \
2055 - use \"-info p\" for more information",CurRule
));
2065 int MR_countPredNodes(Predicate
*p
)
2067 int MR_countPredNodes(p
)
2071 if (p
== NULL
) return 0;
2072 return 1 + MR_countPredNodes(p
->down
) + MR_countPredNodes(p
->right
);
2076 Predicate
*MR_predSimplifyALLX(Predicate
*p
,int skipPass3
)
2078 Predicate
*MR_predSimplifyALLX(p
,skipPass3
)
2086 countAfter
=MR_countPredNodes(p
);
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
);
2097 p
=checkPredicateConflict(p
);
2098 p
=MR_removeRedundantPredPass3(p
);
2100 countAfter
=MR_countPredNodes(p
);
2101 } while (countBefore
!= countAfter
);
2107 Predicate
*MR_predSimplifyALL(Predicate
*p
)
2109 Predicate
*MR_predSimplifyALL(p
)
2113 return MR_predSimplifyALLX(p
,0);
2117 void MR_releaseResourcesUsedInRule(Node
*n
)
2119 void MR_releaseResourcesUsedInRule(n
)
2127 if (n
== NULL
) return;
2128 if (n
->ntype
== nJunction
) {
2131 if (j
->predicate
!= NULL
) {
2132 predicate_free(j
->predicate
);
2135 for (i
=0; i
< CLL_k
; i
++) {
2136 set_free(j
->fset
[i
]);
2139 if (j
->ftree
!= NULL
) {
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
);
2151 MR_releaseResourcesUsedInRule(next
);
2155 int MR_allPredLeaves(Predicate
*p
)
2157 int MR_allPredLeaves(p
)
2163 if (p
== NULL
) return 1;
2165 for (q
=p
; q
!= NULL
; q
=q
->right
) {
2166 if (q
->down
!= NULL
) return 0;
2171 /* make sure it works for the last rule in a file */
2174 int MR_offsetFromRule(Node
*n
)
2176 int MR_offsetFromRule(n
)
2183 for (j
=SynDiag
; j
!= NULL
; j
=(Junction
*)j
->p2
) {
2185 require (j
->ntype
== nJunction
&& j
->jtype
== RuleBlk
,"Not a rule block");
2187 if (n
->file
< j
->file
) {
2190 if (n
->file
== j
->file
) {
2191 if (n
->line
< j
->line
) {
2192 return (offset
< 0) ? 0 : offset
;
2194 offset
=n
->line
- j
->line
;
2195 if (offset
== 0) return 0;
2202 #define ruleNameMax 50
2204 static char ruleNameStatic1
[ruleNameMax
];
2205 static char ruleNameStatic2
[ruleNameMax
+10];
2208 char * MR_ruleNamePlusOffset(Node
*n
)
2210 char * MR_ruleNamePlusOffset(n
)
2214 int offset
=MR_offsetFromRule(n
);
2216 strncpy(ruleNameStatic1
,n
->rname
,ruleNameMax
);
2218 sprintf(ruleNameStatic2
,"%s/?",ruleNameStatic1
);
2220 sprintf(ruleNameStatic2
,"%s/%d",ruleNameStatic1
,offset
+1);
2222 return ruleNameStatic2
;
2226 int MR_max_height_of_tree(Tree
*t
)
2228 int MR_max_height_of_tree(t
)
2236 if (t
== NULL
) return 0;
2238 require (t
->token
!= ALT
&& t
->token
!= EpToken
,"MR_max_height_of_tree ALT or EpToken");
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
;
2248 int MR_all_leaves_same_height(Tree
*t
,int depth
)
2250 int MR_all_leaves_same_height(t
,depth
)
2259 require (t
->token
!= ALT
&& t
->token
!= EpToken
,"MR_all_leaves_same_height ALT or EpToken");
2264 if ( ! MR_all_leaves_same_height(t
->down
,depth
-1)) {
2267 if (t
->right
== NULL
) {
2270 return MR_all_leaves_same_height(t
->right
,depth
);
2276 void MR_projectTreeOntoSet(Tree
*tree
,int ck
,set
*ckset
)
2278 void MR_projectTreeOntoSet(tree
,ck
,ckset
)
2284 if (tree
== NULL
) return;
2286 require(tree
->token
!= EpToken
,"MR_projectTreeOntoSet: EpToken unexpected\n");
2288 MR_projectTreeOntoSet(tree
->right
,ck
,ckset
);
2289 if (tree
->token
== ALT
) {
2290 MR_projectTreeOntoSet(tree
->down
,ck
,ckset
);
2293 MR_projectTreeOntoSet(tree
->down
,ck
-1,ckset
);
2295 set_orel(tree
->token
,ckset
);
2301 int MR_comparePredicates(Predicate
*a
,Predicate
*b
)
2303 int MR_comparePredicates(a
,b
)
2311 if (a
== b
) return 1;
2312 if (a
== NULL
|| b
== NULL
) return 0;
2313 if (a
->down
== NULL
&& b
->down
== NULL
) {
2315 /* predicate->invert can be set only in the predEntry predicates */
2316 /* thus they are only visible after the predEntry predicates have been "unfolded" */
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
)) {
2331 if (a
->down
== NULL
|| b
->down
== NULL
) return 0;
2332 if (a
->expr
!= b
->expr
) return 0;
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
;
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.
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
2365 * The unfold routine expands all references to #pred expressions.
2367 * The simplifyInvert goes through and propagates the invert bit so that
2368 * all OR and AND nodes are un-inverted.
2370 * Note that !(A and B) => (!A or !B)
2371 * !(A or B) => (!A and !B)
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.
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.
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.
2390 Predicate
*MR_unfold(Predicate
*pred
)
2392 Predicate
*MR_unfold(pred
)
2398 if (pred
== NULL
) return NULL
;
2400 pred
->right
=MR_unfold(pred
->right
);
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 "!" */
2407 result
=predicate_dup_without_context(pred
->source
->predEntry
->pred
);
2408 if (pred
->inverted
) {
2409 result
->inverted
=!result
->inverted
;
2411 if (pred
->source
->inverted
) {
2412 result
->inverted
=!result
->inverted
;
2414 result
->right
=pred
->right
;
2416 predicate_free(pred
);
2417 /*** result=MR_unfold(result); *** not necessary */ /* recursive expansion */
2421 ; /* do nothing */ /* an inline literal predicate */
2424 pred
->down
=MR_unfold(pred
->down
);
2429 /* this should be called immediately after MR_unfold() and
2434 void MR_simplifyInverted(Predicate
*pred
,int inverted
)
2436 void MR_simplifyInverted(pred
,inverted
)
2443 if (pred
== NULL
) return;
2445 MR_simplifyInverted(pred
->right
,inverted
);
2447 newInverted
= 1 & (inverted
+ pred
->inverted
);
2449 if (pred
->down
== NULL
) {
2450 pred
->inverted
=newInverted
;
2452 if (newInverted
!= 0) {
2453 if (pred
->expr
== PRED_AND_LIST
) {
2454 pred
->expr
=PRED_OR_LIST
;
2456 pred
->expr
=PRED_AND_LIST
;
2460 MR_simplifyInverted(pred
->down
,newInverted
);
2464 /* only remove it from AND and OR nodes, not leaves */
2467 void MR_clearPredEntry(Predicate
*p
)
2469 void MR_clearPredEntry(p
)
2473 if (p
== NULL
) return;
2474 MR_clearPredEntry(p
->down
);
2475 MR_clearPredEntry(p
->right
);
2476 if (p
->down
!= NULL
) p
->predEntry
=NULL
;
2481 void MR_orphanRules(FILE *f
)
2483 void MR_orphanRules(f
)
2494 if (! InfoO
) return;
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
);
2504 if (set_deg(a
) > 1) {
2505 fprintf(f
,"note: Start rules: {");
2506 for (; !set_nil(a
); set_rm(e
,a
)) {
2508 fprintf(f
," %s",RulePtr
[e
]->rname
);
2515 /* merge (X Y) and (X) to create (X) */
2517 static int *mergeChain
;
2518 static Tree
*mergeTree
;
2521 Tree
*MR_merge_tree_contexts_client(Tree
*t
,int chain
[])
2523 Tree
*MR_merge_tree_contexts_client(t
,chain
)
2528 if (t
== NULL
) return NULL
;
2529 if (chain
[0] == 0) {
2533 return MR_merge_tree_contexts_client(u
,&chain
[0]);
2535 if (chain
[0] == t
->token
) {
2536 t
->down
=MR_merge_tree_contexts_client(t
->down
,&chain
[1]);
2538 t
->right
=MR_merge_tree_contexts_client(t
->right
,&chain
[0]);
2543 void MR_iterateOverTreeContexts(Tree
*t
,int chain
[])
2545 void MR_iterateOverTreeContexts(t
,chain
)
2550 if (t
== NULL
) return;
2552 if (t
->down
!= NULL
) {
2553 MR_iterateOverTreeContexts(t
->down
,&chain
[1]);
2555 MR_merge_tree_contexts_client(mergeTree
,mergeChain
);
2557 MR_iterateOverTreeContexts(t
->right
,&chain
[0]);
2562 Tree
*MR_merge_tree_contexts(Tree
*t
)
2564 Tree
*MR_merge_tree_contexts(t
)
2568 int h
=MR_max_height_of_tree(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
);
2577 free ( (char *) mergeChain
);
2583 Tree
*MR_compute_pred_tree_context(Predicate
*p
)
2585 Tree
*MR_compute_pred_tree_context(p
)
2591 t
=MR_compute_pred_tree_ctxXX(p
);
2592 MR_merge_tree_contexts(t
);
2597 void MR_guardPred_plainSet(ActionNode
*anode
,Predicate
*pred
)
2599 void MR_guardPred_plainSet(anode
,pred
)
2605 Predicate
*workPred
;
2610 if (!MRhoisting
) return;
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"
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.
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.
2627 r1a : (A)? => <<p>>? r2 (A|B)
2628 r1b : (A)? => <<p>>? r2 (A|C)
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}
2637 require (anode
->next
->ntype
== nJunction
,"MR_guardpred_plainSet not Junction");
2638 j
=(Junction
*)(anode
->next
);
2640 workPred
=predicate_dup_without_context(pred
);
2642 workPred
->scontext
[1]=MR_First(1,j
, &(workPred
->completionSet
) );
2643 MR_complete_predicates(1,workPred
);
2645 maskSet
=pred
->scontext
[1];
2647 MR_projectTreeOntoSet(pred
->tcontext
,1,&maskSet
);
2649 pred
->plainSet
=set_dif(workPred
->scontext
[1],maskSet
);
2650 predicate_free(workPred
);
2653 /*******************************************************************************/
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
;
2665 int MR_isChain(Tree
*t
)
2673 for (u
=t
; u
!= NULL
; u
=u
->down
) {
2674 if (u
->right
!= NULL
) return 0;
2680 int MR_suppressK_client(Tree
*tree
,int tokensInChain
[])
2682 int MR_suppressK_client(tree
,tokensInChain
)
2684 int tokensInChain
[];
2689 int save_ConstrainSearch
;
2693 suppressSucceeded
=0; /* volatile */
2695 if (suppressSets
== NULL
) {
2696 suppressSets
=(set
*) calloc (CLL_k
+1,sizeof(set
));
2697 require (suppressSets
!= NULL
,"MR_suppressK_client: suppressSets alloc");
2700 for (suppressChainLength
=1;
2701 tokensInChain
[suppressChainLength
+1] != 0;
2702 suppressChainLength
++) {};
2704 require (suppressChainLength
!= 0,"MR_suppressK_client: chain empty");
2706 for (i
=1 ; i
<= suppressChainLength
; i
++) {
2707 set_clr(suppressSets
[i
]);
2708 set_orel( (unsigned) tokensInChain
[i
],
2713 save_ConstrainSearch
=ConstrainSearch
;
2717 MR_SuppressSearch
=1;
2718 MR_AmbSourceSearch
=1;
2719 MR_MaintainBackTrace
=1;
2722 maxk
= suppressChainLength
;
2727 /*** constrain = &(fset[1]); ***/
2729 MR_setConstrainPointer(&(fset
[1])); /* MR18 */
2731 MR_pointerStackReset(&MR_BackTraceStack
);
2733 TRAV(suppressNode
,maxk
,&incomplete
,t
);
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
);
2742 ConstrainSearch
=save_ConstrainSearch
;
2745 MR_AmbSourceSearch
=0;
2746 MR_MaintainBackTrace
=0;
2747 MR_SuppressSearch
=0;
2748 return suppressSucceeded
;
2752 Tree
* MR_iterateOverTreeSuppressK(Tree
*t
,int chain
[])
2754 Tree
* MR_iterateOverTreeSuppressK(t
,chain
)
2759 if (t
== NULL
) return NULL
;
2760 t
->right
=MR_iterateOverTreeSuppressK(t
->right
,&chain
[0]);
2762 if (t
->down
!= NULL
) {
2763 t
->down
=MR_iterateOverTreeSuppressK(t
->down
,&chain
[1]);
2764 if (t
->down
== NULL
) {
2772 MR_suppressK_client(suppressTree
,suppressChain
);
2773 if (suppressSucceeded
) {
2788 Predicate
* MR_suppressK(Node
*j
,Predicate
*p
)
2790 Predicate
* MR_suppressK(j
,p
)
2797 int ampersandPred
=0;
2800 if (! MRhoistingk
) {
2804 if (! MRhoisting
) return p
;
2805 if (CLL_k
== 1) return p
;
2807 if (suppressChain
== NULL
) {
2808 suppressChain
=(int *) calloc(CLL_k
+2,sizeof(int));
2809 require (suppressChain
!= NULL
,"MR_suppressK: can't allocate chain");
2812 if (p
== NULL
) return NULL
;
2814 if (j
->ntype
== nJunction
) {
2815 nodePrime
=(Node
*) MR_junctionWithoutP2( (Junction
*) j
);
2820 p
->down
=MR_suppressK(j
,p
->down
);
2821 p
->right
=MR_suppressK(j
,p
->right
);
2822 if (p
->down
!= NULL
) {
2831 if (p
->source
!= NULL
) {
2832 if (p
->source
->guardpred
!= NULL
) guardPred
=1;
2833 if (p
->source
->ampersandPred
!= NULL
) ampersandPred
=1;
2836 suppressPredicate
=p
;
2837 suppressNode
=nodePrime
; /* was j*/
2839 suppressTree
=p
->tcontext
;
2841 if (guardPred
|| ampersandPred
) {
2842 p
->tcontext
=MR_iterateOverTreeSuppressK(suppressTree
,&suppressChain
[1]);
2843 if (p
->tcontext
== NULL
) {
2849 if (MR_isChain(p
->tcontext
)) {
2850 p
->tcontext
=MR_iterateOverTreeSuppressK(suppressTree
,&suppressChain
[1]);
2851 if (p
->tcontext
== NULL
) {
2864 void MR_suppressSearchReport(void)
2866 void MR_suppressSearchReport()
2875 /* number of tokens in back trace stack matches length of chain */
2878 for (i
=0; i
< MR_BackTraceStack
.count
; i
++) {
2879 p
=(Node
*) MR_BackTraceStack
.data
[i
];
2880 if (p
->ntype
== nToken
) depth
++;
2883 require (depth
== suppressChainLength
,"depth > suppressChainLength");
2885 /* token codes match chain */
2888 for (i
=0; i
< MR_BackTraceStack
.count
; i
++) {
2889 p
=(Node
*) MR_BackTraceStack
.data
[i
];
2890 if (p
->ntype
!= nToken
) continue;
2893 if (set_nil(tn
->tset
)) {
2894 require(set_el( (unsigned) tn
->token
,fset
[depth
]),
2895 "MR_suppressSearchReport: no match to #token in chain");
2897 setAnd
=set_and(fset
[depth
],tn
->tset
);
2898 require(!set_nil(setAnd
),
2899 "MR_suppressSearchReport: no match to #token set in chain");
2904 /* have a match - now remove it from the predicate */
2906 suppressSucceeded
=1;
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
]));
2920 fprintf(output
," )\n");
2921 fprintf(output
,"The sequence of references which generate that sequence of tokens:\n\n");
2923 MR_backTraceDumpItemReset();
2925 for (i
=0; i
< MR_BackTraceStack
.count
; i
++) {
2926 MR_backTraceDumpItem(output
,0,(Node
*) MR_BackTraceStack
.data
[i
]);
2928 fprintf(output
,"\n");
2929 fprintf(output
,"#endif\n");
2934 void MR_markCompromisedRule(Node
*n
)
2936 void MR_markCompromisedRule(n
)
2944 if (n
->ntype
== nRuleRef
) {
2945 mark
=(Node
*) MR_ruleReferenced( (RuleRefNode
*) n
);
2946 } else if (n
->ntype
== nToken
) {
2948 } else if (n
->ntype
== nJunction
) {
2964 if (mark
== NULL
) return;
2966 require (RulePtr
!= NULL
,"RulePtr not initialized");
2968 q
= (RuleEntry
*) hash_get(Rname
,mark
->rname
);
2969 require (q
!= NULL
,"RuleEntry not found");
2970 set_orel(q
->rulenum
,&MR_CompromisedRules
);
2974 void MR_alphaBetaTraceReport(void)
2976 void MR_alphaBetaTraceReport()
2981 if (! AlphaBetaTrace
) return;
2983 MR_AlphaBetaMessageCount
++;
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");
2996 MR_backTraceDumpItemReset();
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
]);
3004 fprintf(output
,"\n");
3005 fprintf(output
,"#endif\n");
3009 void MR_dumpRuleSet(set s
)
3011 void MR_dumpRuleSet(s
)
3016 unsigned *origin
=set_pdq(s
);
3018 require(origin
!= NULL
,"set_pdq failed");
3020 if (RulePtr
== NULL
) {
3021 fprintf(stderr
,"RulePtr[] not yet initialized");
3023 for (cursor
=origin
; *cursor
!= nil
; cursor
++) {
3024 /**** if (cursor != origin) fprintf(stderr,","); ****/
3025 fprintf(stderr
," %s",RulePtr
[*cursor
]->rname
);
3026 fprintf(stderr
,"\n");
3028 free( (char *) origin
);