diff options
Diffstat (limited to 'Tools/CCode/Source/Pccts/antlr/mrhoist.c')
| -rw-r--r-- | Tools/CCode/Source/Pccts/antlr/mrhoist.c | 3030 |
1 files changed, 3030 insertions, 0 deletions
diff --git a/Tools/CCode/Source/Pccts/antlr/mrhoist.c b/Tools/CCode/Source/Pccts/antlr/mrhoist.c new file mode 100644 index 0000000000..110bf5996f --- /dev/null +++ b/Tools/CCode/Source/Pccts/antlr/mrhoist.c @@ -0,0 +1,3030 @@ +/*
+ * mrhoist.c
+ *
+ * SOFTWARE RIGHTS
+ *
+ * We reserve no LEGAL rights to the Purdue Compiler Construction Tool
+ * Set (PCCTS) -- PCCTS is in the public domain. An individual or
+ * company may do whatever they wish with source code distributed with
+ * PCCTS or the code generated by PCCTS, including the incorporation of
+ * PCCTS, or its output, into commerical software.
+ *
+ * We encourage users to develop software with PCCTS. However, we do ask
+ * that credit is given to us for developing PCCTS. By "credit",
+ * we mean that if you incorporate our source code into one of your
+ * programs (commercial product, research project, or otherwise) that you
+ * acknowledge this fact somewhere in the documentation, research report,
+ * etc... If you like PCCTS and have developed a nice tool with the
+ * output, please mention that you developed it using PCCTS. In
+ * addition, we ask that this header remain intact in our source code.
+ * As long as these guidelines are kept, we expect to continue enhancing
+ * this system and expect to make other tools available as they are
+ * completed.
+ *
+ * ANTLR 1.33MR10
+ *
+ */
+
+#include <stdio.h>
+
+#include "pcctscfg.h"
+
+#include "set.h"
+#include "syn.h"
+#include "hash.h"
+#include "generic.h"
+#include "dlgdef.h"
+#include <ctype.h>
+
+#ifdef __USE_PROTOS
+void dumppred(Predicate *);
+#else
+void dumppred();
+#endif
+
+/*
+ Try to determine whether predicate "first" is true for
+ all cases where "second" is true. Comparison takes place
+ without regard to context.
+ Assumes that predicate symbols have been expanded.
+ Assumes that there are no NAND or NOR nodes
+
+*/
+
+#ifdef __USE_PROTOS
+int MR_secondPredicateUnreachable(Predicate *first,Predicate *second)
+#else
+int MR_secondPredicateUnreachable(first,second)
+ Predicate *first;
+ Predicate *second;
+#endif
+{
+ Predicate *f;
+ Predicate *s;
+
+ if (first == NULL) {
+ return 1;
+ } else if (second == NULL) {
+ return 0;
+ } else if (first->down == NULL && second->down == NULL) {
+ if (first->source == second->source &&
+ first->inverted == second->inverted) {
+ return 1; /* look identical - will never reach alt2 */
+ } else {
+ return 0; /* look different */
+ };
+ } else if (first->down == NULL && second->down != NULL) {
+
+ if (second->expr == PRED_AND_LIST) {
+
+ /* unreachable if first covers any child of second */
+
+ for (s=second->down; s != NULL; s=s->right) {
+ if (MR_secondPredicateUnreachable(first,s)) {
+ return 1;
+ };
+ };
+ return 0;
+ } else if (second->expr == PRED_OR_LIST) {
+
+ /* unreachable if first covers every child of second */
+
+ for (s=second->down; s != NULL; s=s->right) {
+ if (!MR_secondPredicateUnreachable(first,s)) {
+ return 0;
+ };
+ };
+ return 1;
+ } else {
+ require (0,"Illegal pred->expr");
+ return 0; /* MR20 Make compiler happy */
+ };
+ } else if (first->down != NULL && second->down == NULL) {
+ if (first->expr == PRED_AND_LIST) {
+
+ /* unreachable if every child of first covers second */
+
+ for (f=first->down; f != NULL; f=f->right) {
+ if (!MR_secondPredicateUnreachable(f,second)) {
+ return 0;
+ };
+ };
+ return 1;
+ } else if (first->expr == PRED_OR_LIST) {
+
+ /* unreachable if any child of first covers second */
+
+ for (f=first->down; f != NULL; f=f->right) {
+ if (MR_secondPredicateUnreachable(f,second)) {
+ return 1;
+ };
+ };
+ return 0;
+ } else {
+ require (0,"Illegal predicate->expr");
+ return 0; /* MR20 Make compiler happy */
+ };
+ } else {
+
+ if (first->expr == PRED_AND_LIST && second->expr == PRED_AND_LIST) {
+
+ /* unreachable if each child of first covers at least one child of second */
+
+ for (f=first->down; f != NULL ; f=f->right) {
+ for (s=second->down; s != NULL ; s=s->right) {
+ if (MR_secondPredicateUnreachable(f,s)) goto A_next_f;
+ };
+ return 0;
+A_next_f:
+ continue;
+ };
+ return 1;
+
+ } else if (first->expr == PRED_AND_LIST && second->expr == PRED_OR_LIST) {
+
+ /* unreachable if each child of first covers ALL of second's children */
+
+ for (f=first->down; f != NULL ; f=f->right) {
+ for (s=second->down; s != NULL ; s=s->right) {
+ if (!MR_secondPredicateUnreachable(f,s)) return 0;
+ };
+ };
+ return 1;
+
+ } else if (first->expr == PRED_OR_LIST && second->expr == PRED_AND_LIST) {
+
+ /* unreachable if any child of second is covered by any child of first */
+
+ for (f=first->down; f != NULL ; f=f->right) {
+ for (s=second->down; s != NULL ; s=s->right) {
+ if (MR_secondPredicateUnreachable(f,s)) return 1;
+ };
+ };
+ return 0;
+
+ } else if (first->expr == PRED_OR_LIST && second->expr == PRED_OR_LIST) {
+
+ /* unreachable if every child of second is covered by some child of first */
+
+ for (f=first->down; f != NULL ; f=f->right) {
+ for (s=second->down; s != NULL ; s=s->right) {
+ if (MR_secondPredicateUnreachable(f,s)) goto B_next_f;
+ };
+ return 0;
+B_next_f:
+ continue;
+ };
+ return 1;
+
+ } else {
+ require (0,"Illegal predicate->expr");
+ return 0; /* MR20 Make compiler happy */
+ };
+ };
+ return 0; /* MR20 MSVC 5.0 complains about missing return statement */
+}
+
+#ifdef __USE_PROTOS
+void MR_xxxIndent(FILE *f,int depth)
+#else
+void MR_xxxIndent(f,depth)
+ FILE *f;
+ int depth;
+#endif
+{
+ int i;
+
+ for (i=0; i<depth ; i++) {
+ fprintf(f," ");
+ };
+}
+
+#ifdef __USE_PROTOS
+void MR_stderrIndent(int depth)
+#else
+void MR_stderrIndent(depth)
+ int depth;
+#endif
+{
+ MR_xxxIndent(stderr,depth);
+}
+
+#ifdef __USE_PROTOS
+void MR_outputIndent(int depth)
+#else
+void MR_outputIndent(depth)
+ int depth;
+#endif
+{
+ MR_xxxIndent(output,depth);
+}
+
+#ifdef __USE_PROTOS
+void MR_set_reuse(set *s)
+#else
+void MR_set_reuse(s)
+ set *s;
+#endif
+{
+ set_free(*s);
+ *s=empty;
+}
+
+#ifdef __USE_PROTOS
+void MR_dumpPredRuleRefStack(FILE *iounit,int indent)
+#else
+void MR_dumpPredRuleRefStack(iounit,indent)
+ FILE *iounit;
+ int indent;
+#endif
+{
+ int i;
+ int j;
+ int count=MR_PredRuleRefStack.count;
+ RuleRefNode *rrn=NULL;
+ Junction *lastOne;
+
+ if (count == 0) {
+ fprintf(iounit,"empty\n");
+ return;
+ };
+ for (i=0; i < count; i++) {
+ rrn=(RuleRefNode *) MR_PredRuleRefStack.data[i];
+ for (j=0; j<indent; j++) fprintf(iounit," ");
+ fprintf(iounit,"#%-2d in rule %s (line %d %s) to rule %s\n",
+ i,rrn->rname,rrn->line,FileStr[rrn->file],rrn->text);
+ };
+ lastOne=MR_ruleReferenced(rrn);
+ if (lastOne != NULL) {
+ for (j=0; j<indent; j++) fprintf(iounit," ");
+ fprintf(iounit,"#%-2d in rule %s (line %d %s)\n",
+ count,lastOne->rname,lastOne->line,FileStr[lastOne->file]);
+ };
+}
+
+#ifdef __USE_PROTOS
+void MR_dumpTreeF(FILE *f,int depth,Tree *tree,int across)
+#else
+void MR_dumpTreeF(f,depth,tree,across)
+ FILE *f;
+ Tree *tree;
+ int depth;
+ int across;
+#endif
+{
+ int newAcross=across;
+
+ if (tree == NULL ) return;
+ if (tree->down != NULL ) {
+ fprintf(output,"\n");
+ MR_outputIndent(depth);
+ fprintf(output, "(root =");
+ };
+ if (tree->token == ALT ) {
+ fprintf(output," %-16s","Alt");
+ } else if (tree->token==EpToken ) {
+ fprintf(output,"(%d)%13s",tree->v.rk," ");
+ } else {
+ fprintf(output," %-16s",TerminalString(tree->token));
+ };
+ if (tree->down != NULL) {
+ fprintf(output,"\n");
+ MR_outputIndent(depth+1);
+ MR_dumpTreeF(f,depth+1,tree->down,1);
+ newAcross=0;
+ fprintf(output,"\n");
+ MR_outputIndent(depth);
+ fprintf(output,")");
+ };
+ if (newAcross > 3) {
+ fprintf(output,"\n");
+ MR_outputIndent(depth);
+ newAcross=0;
+ };
+ MR_dumpTreeF(f,depth,tree->right,newAcross+1);
+}
+
+#ifdef __USE_PROTOS
+void MR_dumpTreeX(int depth,Tree *tree,int across)
+#else
+void MR_dumpTreeX(depth,tree,across)
+ Tree *tree;
+ int depth;
+ int across;
+#endif
+{
+ MR_dumpTreeF(output,depth,tree,across);
+}
+
+#ifdef __USE_PROTOS
+void MR_dumpTokenSet(FILE *f,int depth,set s)
+#else
+void MR_dumpTokenSet(f,depth,s)
+ FILE *f;
+ int depth;
+ set s;
+#endif
+{
+ int i;
+ int j;
+
+ unsigned *pdq;
+
+ if (set_nil(s)) {
+ fprintf(f,"\n");
+ MR_xxxIndent(f,depth+1);
+ fprintf(f,"nil\n");
+ return;
+ };
+
+ pdq=set_pdq(s);
+ require(pdq != NULL,"set_pdq failed");
+ i=0;
+ for (i=0 ; ; i=i+4) {
+ fprintf(f,"\n");
+ MR_xxxIndent(f,depth+1);
+ for (j=0; j < 4 ; j++) {
+ if (pdq[i+j] == nil) break;
+ fprintf(f," %-16s",TerminalString(pdq[i+j]));
+ };
+ if (pdq[i+j] == nil) break;
+ };
+ fprintf(f,"\n");
+ free( (char *) pdq);
+}
+
+#ifdef __USE_PROTOS
+void MR_dumpPred1(int depth,Predicate *p,int withContext)
+#else
+void MR_dumpPred1(depth,p,withContext)
+ int depth;
+ Predicate *p;
+ int withContext;
+#endif
+{
+ unsigned k;
+
+ if (p == NULL) {
+ MR_outputIndent(depth);
+ fprintf(output,"The predicate is empty (or always true)\n\n");
+ return;
+ };
+ if (p->down != NULL) {
+ MR_outputIndent(depth);
+ if (p->inverted) {
+
+ /* MR14a Left out print expression in fprintf
+ Reported by Manuel Kessler (mlkessle@cip.physik.uni-wuerzburg.de)
+ */
+
+ if (p->expr == PRED_AND_LIST) fprintf(output,"%s NAND (not AND) expr\n\n",p->expr);
+ if (p->expr == PRED_OR_LIST) fprintf(output,"%s NOR (not OR) expr\n\n",p->expr);
+ } else {
+ fprintf(output,"%s expr\n\n",p->expr);
+ };
+ } else {
+ MR_outputIndent(depth);
+ fprintf(output,"pred %s <<%s>>?\n",
+ (p->inverted ? " *not*" : ""),
+ (p->expr == NULL ? "null expr" : p->expr));
+ MR_outputIndent(depth+1);
+ fprintf(output," ");
+ fprintf(output," depth=k=%d",p->k);
+ if (p->source != NULL && p->source->guardpred) {
+ fprintf(output," (\"=>\" guard)");
+ }
+ if (p->source != NULL && p->source->ampersandPred != NULL) {
+ fprintf(output," (\"&&\" guard)");
+ };
+ k=set_int(p->completionSet);
+ if (k != nil) {
+ fprintf(output," Incomplete Set at k=%d !",k);
+ };
+ k=set_int(p->completionTree);
+ if (k != nil) {
+ fprintf(output," Incomplete Tree at k=%d !",k);
+ };
+ if (p->source != NULL) {
+ fprintf(output," rule %s line %d %s",
+ p->source->rname,p->source->line,FileStr[p->source->file]);
+ };
+ fprintf(output,"\n");
+ if (withContext &&
+ (HoistPredicateContext ||
+ ! set_nil(p->scontext[1]) ||
+ p->tcontext != NULL)) {
+ if (p->k == 1) {
+ MR_outputIndent(depth+1);
+ fprintf(output,"set context: ");
+ MR_dumpTokenSet(output,depth+1,p->scontext[1]);
+ }
+ if (p->k != 1) {
+ MR_outputIndent(depth+1);
+ fprintf(output,"tree context:");
+ if (p->tcontext == NULL) {
+ fprintf(output," null");
+ } else {
+ MR_dumpTreeX(depth+2,p->tcontext,0);
+ };
+ fprintf(output,"\n");
+ };
+ };
+ fprintf(output,"\n");
+ };
+ if (p->down != NULL) {
+ MR_dumpPred1(depth+1,p->down,withContext);
+ };
+ if (p->right != NULL) {
+ MR_dumpPred1(depth,p->right,withContext);
+ };
+}
+
+#ifdef __USE_PROTOS
+void MR_dumpPred(Predicate *p,int withContext)
+#else
+void MR_dumpPred(p,withContext)
+ Predicate *p;
+ int withContext;
+#endif
+{
+ MR_dumpPred1(0,p,withContext);
+}
+
+#ifdef __USE_PROTOS
+Tree * MR_make_tree_from_set(set s)
+#else
+Tree * MR_make_tree_from_set(s)
+ set s;
+#endif
+{
+ Tree *t=NULL;
+ Tree *node;
+ Tree **tp=&t;
+ int i;
+
+ unsigned *pdq=set_pdq(s);
+
+ if (pdq != NULL) {
+ for (i=0 ; pdq[i] != nil ; i++) {
+ node=tnode( (int) pdq[i]);
+ *tp=node;
+ tp=&(node->right);
+ };
+ *tp=NULL;
+ free ( (char *) pdq);
+ };
+ return t;
+}
+
+#ifdef __USE_PROTOS
+void MR_check_pred_too_long(Predicate *p,set completion)
+#else
+void MR_check_pred_too_long(p,completion)
+ Predicate *p;
+ set completion;
+#endif
+{
+ if (p != NULL &&
+ p->source != NULL &&
+ ! p->source->predTooLong) {
+ if ( !set_nil(completion)) {
+ p->source->predTooLong=1;
+warnFL("It is unusual (but ok) for a semantic predicate to test context past the end of its own rule",
+ FileStr[p->source->file],p->source->line);
+ };
+ };
+}
+
+#ifdef __USE_PROTOS
+int MR_predicate_context_completed(Predicate *p)
+#else
+int MR_predicate_context_completed(p)
+ Predicate *p;
+#endif
+{
+ if (p == NULL) return 1;
+ if (p->expr != PRED_AND_LIST &&
+ p->expr != PRED_OR_LIST) {
+ if ( ! set_nil(p->completionSet)) return 0;
+ if ( ! set_nil(p->completionTree)) return 0;
+ };
+ return MR_predicate_context_completed(p->down) &
+ MR_predicate_context_completed(p->right);
+}
+
+#ifdef __USE_PROTOS
+Node * MR_advance(Node *n)
+#else
+Node * MR_advance(n)
+ Node *n;
+#endif
+{
+ if (n == NULL) return NULL;
+ switch (n->ntype) {
+ case nJunction: return ((Junction *)n)->p1;
+ case nToken: return ((TokNode *)n)->next;
+ case nRuleRef: return ((RuleRefNode *)n)->next;
+ case nAction: return ((ActionNode *)n)->next;
+ default: return NULL;
+ };
+ return NULL; /* MSVC 5.0 complains about missing return statement */
+}
+
+#ifdef __USE_PROTOS
+Junction * MR_find_endRule(Node *n)
+#else
+Junction * MR_find_endRule(n)
+ Node *n;
+#endif
+{
+ Node *next;
+ if (n == NULL) return NULL;
+ for (next=n; next != NULL; next=MR_advance(next)) {
+ if (next->ntype == nJunction &&
+ ( (Junction *) next)->jtype == EndRule) {
+ break;
+ };
+ };
+ return (Junction *)next;
+}
+
+/*
+ Intersection: a branch which is shorter is chosen
+ over one which is longer: (A B C) intersect (A B) yields (A B).
+
+ AND: a branch which is longer is chosen over the one
+ which is shorter: (A B C) AND (A B) yields (A B C)
+
+*/
+
+#ifdef __USE_PROTOS
+Tree *MR_computeTreeIntersection(Tree *l,Tree *r)
+#else
+Tree *MR_computeTreeIntersection(l,r)
+ Tree *l;
+ Tree *r;
+#endif
+{
+ Tree *result=NULL;
+ Tree **tail;
+ Tree *p;
+ Tree *q;
+ Tree *match;
+
+ if (l == NULL || r == NULL) return NULL;
+ for (p=l; p != NULL; p=p->right) {
+ require(p->token != EpToken,"MR_computeTreeIntersection: p->EpToken unexpected\n");
+ require (p->token != ALT,"MR_computeTreeIntersection: p->ALT unexpected\n");
+ };
+ for (q=r; q != NULL; q=q->right) {
+ require(q->token != EpToken,"MR_computeTreeIntersection: q->EpToken unexpected\n");
+ require(q->token != ALT,"MR_computeTreeIntersection: q->ALT unexpected\n");
+ };
+
+ result=tnode(ALT);
+ tail=&(result->down);
+
+ for (p=l; p != NULL ; p=p->right) {
+ for (q=r; q != NULL ; q=q->right) {
+ if (p->token == q->token) {
+ match=tnode(p->token);
+ match->down=MR_computeTreeIntersection(p->down,q->down);
+ *tail=match;
+ tail=&(match->right);
+ };
+ };
+ };
+
+ *tail=NULL;
+ result=tshrink(result);
+ result=tflatten( result );
+ result=tleft_factor( result );
+ return result;
+}
+
+/* the predicates which are ANDed together have a common
+ context: they must all have common roots. Thus the
+ AND operation is more like an OR operation because
+ branches which are longer are grafted onto shorter
+ branches of the AND tree. For instance combining
+ (A B C) with (A B C D) gives (A B C D). There
+ should never be a case of (A B C) and (A B D) because
+ they have the same context.
+
+ Actually, this may not be true once one throws in
+ guard predicates which are defined by the user, not
+ the context.
+*/
+
+/* requires input trees to be in "canonical" format */
+
+#ifdef __USE_PROTOS
+Tree *MR_computeTreeAND(Tree *l,Tree *r)
+#else
+Tree *MR_computeTreeAND(l,r)
+ Tree *l;
+ Tree *r;
+#endif
+{
+ Tree *result=NULL;
+ Tree **tail;
+ Tree *p;
+ Tree *q;
+ Tree *match;
+
+ if (l == NULL) return tdup(r);
+ if (r == NULL) return tdup(l);
+
+ for (p=l; p != NULL; p=p->right) {
+/**** require(p->token != EpToken,"MR_computeTreeAND: p->EpToken unexpected\n"); ****/
+ require (p->token != ALT,"MR_computeTreeAND: p->ALT unexpected\n");
+ };
+ for (q=r; q != NULL; q=q->right) {
+/**** require(q->token != EpToken,"MR_computeTreeAND: q->EpToken unexpected\n"); ****/
+ require(q->token != ALT,"MR_computeTreeAND: q->ALT unexpected\n");
+ };
+
+ result=tnode(ALT);
+ tail=&(result->down);
+
+ for (p=l; p != NULL ; p=p->right) {
+ for (q=r; q != NULL ; q=q->right) {
+ if (p->token == q->token) {
+ match=tnode(p->token);
+ match->down=MR_computeTreeAND(p->down,q->down);
+ *tail=match;
+ tail=&(match->right);
+ };
+ };
+ };
+
+ *tail=NULL;
+ result=tshrink(result);
+ result=tflatten( result );
+ result=tleft_factor( result );
+ return result;
+}
+
+#ifdef __USE_PROTOS
+void MR_union_plain_sets1(Predicate *p,set *theUnion)
+#else
+void MR_union_plain_sets1(p,theUnion)
+ Predicate *p;
+ set *theUnion;
+#endif
+{
+ if (p == NULL) return;
+ MR_union_plain_sets1(p->down,theUnion);
+ MR_union_plain_sets1(p->right,theUnion);
+ set_orin(theUnion,p->plainSet);
+ return;
+}
+
+#ifdef __USE_PROTOS
+set MR_union_plain_sets(Predicate *p)
+#else
+set MR_union_plain_sets(p)
+ Predicate *p;
+#endif
+{
+ set theUnion;
+
+ theUnion=empty;
+
+ MR_union_plain_sets1(p,&theUnion);
+ return theUnion;
+}
+
+/* does NOT left factor: do not want to merge
+ (A B) with (A) to get (A B)
+ in fact the opposite: (A B) with (A) gives (A)
+*/
+
+#ifdef __USE_PROTOS
+Tree *MR_compute_pred_tree_ctxXX(Predicate *p)
+#else
+Tree *MR_compute_pred_tree_ctxXX(p)
+ Predicate *p;
+#endif
+{
+ Tree *result=NULL;
+ Predicate *q;
+ Tree *t;
+
+ if (p == NULL) return NULL;
+
+/* this appears strange: why do we OR the context
+ of and AND predicate ? It is because of the way
+ that predicates are evaluated: if the context is
+ wrong then it's the same as if the predicate was
+ true. That means that even when one leg of an
+ AND has unmatched context, if the other leg has
+ matched context and is true then the predicate
+ succeeds. It's only when all the legs have unmatched
+ context that this one can skip evaluation of the
+ predicates.
+*/
+ if (p->expr == PRED_OR_LIST ||
+ p->expr == PRED_AND_LIST) {
+ for (q=p->down; q != NULL ; q=q->right) {
+ t=MR_compute_pred_tree_ctxXX(q);
+ result=tappend(result,t);
+ t=NULL;
+ };
+
+ result=tshrink(result);
+ result=tflatten( result );
+
+/* does NOT left factor: do not want to merge
+ (A B) with (A) to get (A B)
+ in fact the opposite: (A B) with (A) gives (A)
+*/
+
+/**** result=tleft_factor( result ); ****/
+ return result;
+ };
+
+#if 0
+** if (p->expr == PRED_AND_LIST) {
+**
+** Predicate *l;
+** Predicate *r;
+** Tree *l1;
+** Tree *r1;
+** Tree *prevl1;
+**
+** l=p->down;
+** require (l->right != NULL,"MR_compute_pred_tree - AND has only one child");
+**
+**/* l1 and r1 should already be in "canonical" format */
+**
+** l1=MR_compute_pred_tree(l);
+** for (r=l->right; r != NULL; r=r->right) {
+** r1=MR_compute_pred_tree(r);
+** prevl1=l1;
+** l1=MR_computeTreeAND(l1,r1);
+** Tfree(r1);
+** Tfree(prevl1);
+** };
+**
+**/* result from computeTreeAND should be in "canonical" format */
+**
+** result=l1;
+**
+**/* result of MR_computeTreeAND should be in "canonical" format */
+**
+** return result;
+** };
+#endif
+
+ if (p->k == 1) {
+ result=MR_make_tree_from_set(p->scontext[1]);
+ } else {
+ result=tdup(p->tcontext);
+ result=MR_remove_epsilon_from_tree(result);
+ result=tshrink(result);
+ result=tflatten(result);
+ result=tleft_factor(result);
+ };
+ return result;
+}
+
+#ifdef __USE_PROTOS
+void MR_pred_depth(Predicate *p,int *maxDepth)
+#else
+void MR_pred_depth(p,maxDepth)
+ Predicate *p;
+ int *maxDepth;
+#endif
+{
+ if (p == NULL) return;
+ if (p->expr != PRED_OR_LIST &&
+ p->expr != PRED_AND_LIST) {
+ if (p->k > *maxDepth) *maxDepth=p->k;
+ };
+ MR_pred_depth(p->down,maxDepth);
+ MR_pred_depth(p->right,maxDepth);
+}
+
+/* this computes the OR of all the contexts */
+
+#ifdef __USE_PROTOS
+set MR_compute_pred_set(Predicate *p)
+#else
+set MR_compute_pred_set(p)
+ Predicate *p;
+#endif
+{
+ set result;
+ Predicate *q;
+
+ result=empty;
+
+ if (p == NULL) return empty;
+
+ if (p->expr == PRED_OR_LIST ||
+ p->expr == PRED_AND_LIST) { /* yes, I do mean PRED_AND_LIST ! */
+ /* remember: r1: (A)? => <<p>>? r2; */
+ /* r2: (B)? => <<q>>? r3; */
+ set t;
+
+ t=empty;
+ result=empty;
+
+ for (q=p->down; q != NULL; q=q->right) {
+ t=MR_compute_pred_set(q);
+ set_orin(&result,t);
+ set_free(t);
+ };
+ return result;
+ } else if (p->k > 1) {
+ return empty;
+ } else {
+ return set_dup(p->scontext[1]);
+ };
+}
+
+#ifdef __USE_PROTOS
+set MR_First(int ck,Junction *j,set *incomplete)
+#else
+set MR_First(ck,j,incomplete)
+ int ck;
+ Junction *j;
+ set *incomplete;
+#endif
+{
+ Junction *p;
+ set tokensUsed;
+
+ tokensUsed=empty;
+
+ require(j->ntype==nJunction, "MR_First: non junction passed");
+
+ p = analysis_point((Junction *)j->p1);
+
+ REACH(p,ck,incomplete,tokensUsed);
+
+ return tokensUsed;
+}
+
+#ifdef __USE_PROTOS
+void MR_cleanup_pred_trees(Predicate *p)
+#else
+void MR_cleanup_pred_trees(p)
+ Predicate *p;
+#endif
+{
+ Tree *t;
+
+ if (p == NULL) return;
+ if (p->expr != PRED_OR_LIST &&
+ p->expr != PRED_AND_LIST) {
+ t=p->tcontext;
+ t=tshrink(t);
+ t=tflatten(t);
+ t=tleft_factor(t);
+ p->tcontext=t;
+ };
+ MR_cleanup_pred_trees(p->down);
+ MR_cleanup_pred_trees(p->right);
+}
+
+/* does NOT return canonical tree */
+
+#ifdef __USE_PROTOS
+Tree * MR_remove_epsilon_from_tree(Tree *t)
+#else
+Tree * MR_remove_epsilon_from_tree(t)
+ Tree *t;
+#endif
+{
+ if (t == NULL) return NULL;
+
+ /* I think ALT can be ignored as a special case */
+
+ if (t->token != EpToken) {
+ t->down=MR_remove_epsilon_from_tree(t->down);
+ t->right=MR_remove_epsilon_from_tree(t->right);
+ return t;
+ } else {
+ Tree *u;
+ u=MR_remove_epsilon_from_tree(t->right);
+ t->right=NULL;
+ Tfree(t);
+ return u;
+ };
+}
+
+#ifdef __USE_PROTOS
+void MR_complete_set(int predDepth,set *tokensUsed,set *incomplete)
+#else
+void MR_complete_set(predDepth,tokensUsed,incomplete)
+ int predDepth;
+ set *tokensUsed;
+ set *incomplete;
+#endif
+{
+ int i;
+ RuleRefNode *ruleRef;
+ set rk2;
+ set b;
+ int k2;
+ Junction *save_MR_RuleBlkWithHalt;
+
+ if (set_int(*incomplete) > (unsigned) predDepth) {
+ return;
+ };
+
+ require(MR_PredRuleRefStack.count == MR_RuleBlkWithHaltStack.count,
+ "RuleRefStack and RuleBlkWithHaltStack not same size");
+
+ require(MR_RuleBlkWithHalt == NULL ||
+ (MR_RuleBlkWithHalt->jtype == RuleBlk && MR_RuleBlkWithHalt->end->halt == TRUE),
+ "RuleBlkWithHalt has no halt set");
+
+ save_MR_RuleBlkWithHalt=MR_RuleBlkWithHalt;
+
+ if (MR_RuleBlkWithHalt != NULL) {
+ MR_RuleBlkWithHalt->end->halt=FALSE;
+ };
+
+ for (i=MR_PredRuleRefStack.count-1; i >= 0 ; i--) {
+ ruleRef=(RuleRefNode *)MR_PredRuleRefStack.data[i];
+ if (ruleRef == NULL) continue;
+
+ MR_RuleBlkWithHalt=(Junction *)MR_RuleBlkWithHaltStack.data[i];
+ if (MR_RuleBlkWithHalt != NULL) MR_RuleBlkWithHalt->end->halt=TRUE;
+
+ rk2=empty;
+ b=empty;
+
+ while ( !set_nil(*incomplete) ) {
+ k2=set_int(*incomplete);
+ if (k2 > predDepth) break; /* <=== another exit from loop */
+ set_rm(k2,*incomplete);
+ REACH(ruleRef->next,k2,&rk2,b);
+ set_orin(tokensUsed,b);
+ set_free(b);
+ };
+
+ if (MR_RuleBlkWithHalt != NULL) MR_RuleBlkWithHalt->end->halt=FALSE;
+
+ set_orin(incomplete,rk2); /* remember what we couldn't do */
+ set_free(rk2);
+ if (set_int(*incomplete) > (unsigned) predDepth) break; /* <=== another exit from loop */
+ };
+
+ MR_RuleBlkWithHalt=save_MR_RuleBlkWithHalt;
+ if (MR_RuleBlkWithHalt != NULL) {
+ MR_RuleBlkWithHalt->end->halt=TRUE;
+ };
+}
+
+#ifdef __USE_PROTOS
+void MR_complete_tree(int predDepth,Tree **t,set *incomplete)
+#else
+void MR_complete_tree(predDepth,t,incomplete)
+ int predDepth;
+ Tree **t;
+ set *incomplete;
+#endif
+{
+ int i;
+ RuleRefNode *ruleRef;
+ set rk2;
+ Tree *u;
+ unsigned k2;
+ Junction *save_MR_RuleBlkWithHalt;
+ int saveConstrainSearch;
+
+ if (set_int(*incomplete) > (unsigned) predDepth) {
+ return;
+ };
+
+ require(MR_PredRuleRefStack.count == MR_RuleBlkWithHaltStack.count,
+ "RuleRefStack and RuleBlkWithHaltStack not same size");
+
+ require(MR_RuleBlkWithHalt == NULL ||
+ (MR_RuleBlkWithHalt->jtype == RuleBlk && MR_RuleBlkWithHalt->end->halt == TRUE),
+ "RuleBlkWithHalt has no halt set");
+
+ save_MR_RuleBlkWithHalt=MR_RuleBlkWithHalt;
+ saveConstrainSearch=ConstrainSearch;
+ ConstrainSearch=0;
+
+ if (MR_RuleBlkWithHalt != NULL) {
+ MR_RuleBlkWithHalt->end->halt=FALSE;
+ };
+
+ for (i=MR_PredRuleRefStack.count-1; i >= 0 ; i--) {
+ ruleRef=(RuleRefNode *)MR_PredRuleRefStack.data[i];
+ if (ruleRef == NULL) continue;
+
+ MR_RuleBlkWithHalt=(Junction *)MR_RuleBlkWithHaltStack.data[i];
+
+ if (MR_RuleBlkWithHalt != NULL) MR_RuleBlkWithHalt->end->halt=TRUE;
+
+ rk2=empty;
+
+ while ( !set_nil(*incomplete) ) {
+ k2 = set_int(*incomplete);
+ if (k2 > (unsigned) predDepth) break; /* <=== another exit from loop */
+ set_rm(k2,*incomplete);
+ u = NULL;
+
+ TRAV(ruleRef->next,k2,&rk2,u);
+
+ /* any subtrees missing k2 tokens, add u onto end */
+
+ *t=tlink(*t,u,k2);
+ Tfree(u);
+ }
+
+ set_orin(incomplete,rk2); /* remember what we couldn't do */
+ set_free(rk2);
+
+ if (MR_RuleBlkWithHalt != NULL) MR_RuleBlkWithHalt->end->halt=FALSE;
+
+ if (set_int(*incomplete) > (unsigned) predDepth) break; /* <=== another exit from loop */
+ };
+
+ MR_RuleBlkWithHalt=save_MR_RuleBlkWithHalt;
+
+ if (MR_RuleBlkWithHalt != NULL) {
+ MR_RuleBlkWithHalt->end->halt=TRUE;
+ };
+ ConstrainSearch=saveConstrainSearch;
+}
+
+#ifdef __USE_PROTOS
+void MR_complete_predicates(int predDepth,Predicate *pred)
+#else
+void MR_complete_predicates(predDepth,pred)
+ int predDepth;
+ Predicate *pred;
+#endif
+{
+ if (pred == NULL) return;
+ if (pred->expr != PRED_AND_LIST &&
+ pred->expr != PRED_OR_LIST) {
+ MR_complete_set(predDepth,&(pred->scontext[1]),&(pred->completionSet));
+ MR_complete_tree(predDepth,&(pred->tcontext),&(pred->completionTree));
+ };
+ MR_complete_predicates(predDepth,pred->down);
+ MR_complete_predicates(predDepth,pred->right);
+}
+
+#ifdef __USE_PROTOS
+Junction * MR_junctionWithoutP2(Junction *j)
+#else
+Junction * MR_junctionWithoutP2(j)
+ Junction *j;
+#endif
+{
+ Junction *thisAlt;
+
+/* don't want to follow p2 to the next alternative of this rule */
+/* insert a generic node with null p2 if necessary */
+/* however FIRST requires a junction */
+
+ thisAlt=j;
+ if (thisAlt->p2 != NULL) {
+ if (thisAlt->p1->ntype == nJunction) {
+ thisAlt=(Junction *) thisAlt->p1;
+ } else {
+ thisAlt=newJunction();
+ thisAlt->p1=j->p1;
+ thisAlt->rname=j->rname;
+ thisAlt->file=j->file;
+ thisAlt->line=j->line;
+ j->p1=(Node *)thisAlt;
+ };
+ };
+ return thisAlt;
+}
+
+#ifdef __USE_PROTOS
+int MR_tree_equ(Tree *big, Tree *small) {
+#else
+int MR_tree_equ(big,small)
+ Tree *big;
+ Tree *small;
+{
+#endif
+
+ Tree *b;
+ Tree *s;
+ int bcount=0;
+ int scount=0;
+
+ if (small == NULL && big == NULL) return 1;
+ if (small == NULL) return 0;
+ if (big == NULL) return 0;
+
+ if (small->token == ALT) {
+ require(small->right == NULL,
+ "MR_tree_equ: small: ALT node has siblings");
+ return MR_tree_equ(big,small->down);
+ };
+ if (big->token == ALT) {
+ require(big->right == NULL,
+ "MR_tree_equ: big: ALT node has siblings");
+ return MR_tree_equ(big->down,small);
+ };
+ for (s=small; s != NULL; s=s->right) {
+ scount++;
+ require(s->token != EpToken,"MR_tree_equ: s->EpToken unexpected\n");
+ };
+ for (b=big; b != NULL; b=b->right) {
+ bcount++;
+ require(b->token != EpToken,"MR_tree_equ: b->EpToken unexpected\n");
+ };
+
+ if (bcount != scount) return 0;
+
+ for (s=small; s != NULL; s=s->right) {
+ for (b=big; b!= NULL; b=b->right) {
+ if (s->token == b->token) {
+ if (MR_tree_equ(b->down,s->down)) goto next_s;
+ };
+ };
+ return 0;
+next_s:
+ continue;
+ };
+ return 1;
+}
+
+/* this does not compare sources - only contexts ! */
+
+#ifdef __USE_PROTOS
+int MR_identicalContext(Predicate *p,Predicate *q)
+#else
+int MR_identicalContext(p,q)
+ Predicate *p;
+ Predicate *q;
+#endif
+{
+ if (p->k != q->k) return 0;
+ require ( (p->tcontext == NULL) == (q->tcontext == NULL),
+ "tcontext inconsistent");
+ if (p->k == 1) {
+ return set_equ(p->scontext[1],q->scontext[1]);
+ } else {
+ return MR_tree_equ(p->tcontext,q->tcontext);
+ };
+}
+
+#ifdef __USE_PROTOS
+void MR_reportSetSuppression(int predDepth,
+ set predSet,set plainSet,Junction *jPred,Junction *jPlain,Predicate *p)
+#else
+void MR_reportSetSuppression(predDepth,predSet,plainSet,jPred,jPlain,p)
+ int predDepth;
+ set predSet;
+ set plainSet;
+ Junction *jPred;
+ Junction *jPlain;
+ Predicate *p;
+#endif
+{
+ if (InfoP) {
+ fprintf(output,"\n#if 0\n\n");
+ fprintf(output,"Hoisting of predicate suppressed by alternative without predicate.\n");
+ fprintf(output,"The alt without the predicate includes all cases where the predicate is false.\n\n");
+ fprintf(output," WITH predicate: line %d %s\n",jPred->line,FileStr[jPred->file]);
+ if (jPlain != NULL) {
+ fprintf(output," WITHOUT predicate: line %d %s\n",jPlain->line,FileStr[jPlain->file]);
+ } else {
+ fprintf(output," WITHOUT predicate: all alternatives without predicates (combined)\n");
+ };
+ if (predDepth == 1) {
+ fprintf(output,"\nThe context set for the predicate:\n");
+ MR_dumpTokenSet(output,1,predSet);
+ };
+ fprintf(output,"\nThe lookahead set for the alt WITHOUT the semantic predicate:\n");
+ MR_dumpTokenSet(output,1,plainSet);
+ fprintf(output,"\nThe predicate:\n\n");
+ MR_dumpPred1(1,p,1);
+ fprintf(output,"Chain of referenced rules:\n\n");
+ MR_dumpPredRuleRefStack(output,4);
+ fprintf(output,"\n#endif\n");
+ };
+}
+
+#ifdef __USE_PROTOS
+void MR_reportSetRestriction(int predDepth,set predSet,set plainSet,
+ Junction *jPred,Junction *jPlain,Predicate *origPred,Predicate *newPred)
+#else
+void MR_reportSetRestriction(predDepth,predSet,plainSet,jPred,jPlain,origPred,newPred)
+ int predDepth;
+ set predSet;
+ set plainSet;
+ Junction *jPred;
+ Junction *jPlain;
+ Predicate *origPred;
+ Predicate *newPred;
+#endif
+{
+ set intersect;
+
+ intersect=empty;
+
+ if (! InfoP) return;
+ fprintf(output,"\n#if 0\n\n");
+ fprintf(output,"Restricting the context of a predicate because of overlap in the lookahead set\n");
+ fprintf(output," between the alternative with the semantic predicate and one without\n");
+ fprintf(output,"Without this restriction the alternative without the predicate could not\n");
+ fprintf(output," be reached when input matched the context of the predicate and the predicate\n");
+ fprintf(output," was false.\n\n");
+
+ fprintf(output," WITH predicate: line %d %s\n",jPred->line,FileStr[jPred->file]);
+ if (jPlain != NULL) {
+ fprintf(output," WITHOUT predicate: line %d %s\n",jPlain->line,FileStr[jPlain->file]);
+ } else {
+ fprintf(output," WITHOUT predicate: all alternatives without predicates (combined)\n");
+ };
+ if (predDepth == 1) {
+ fprintf(output,"\nThe original context set for the predicate:\n");
+ MR_dumpTokenSet(output,1,predSet);
+ };
+ fprintf(output,"\nThe lookahead set for the alt WITHOUT the semantic predicate:\n");
+ MR_dumpTokenSet(output,1,plainSet);
+ if (predDepth == 1) {
+ fprintf(output,"\nThe intersection of the two sets\n");
+ intersect=set_and(predSet,plainSet);
+ MR_dumpTokenSet(output,1,intersect);
+ set_free(intersect);
+ };
+ fprintf(output,"\nThe original predicate:\n\n");
+ MR_dumpPred1(1,origPred,1);
+ fprintf(output,"The new (modified) form of the predicate:\n\n");
+ MR_dumpPred1(1,newPred,1);
+ fprintf(output,"#endif\n");
+}
+
+/* don't use Pass3 by itself unless you know that inverted is not important */
+
+#ifdef __USE_PROTOS
+Predicate * MR_removeRedundantPredPass3(Predicate *p)
+#else
+Predicate * MR_removeRedundantPredPass3(p)
+ Predicate *p;
+#endif
+{
+ Predicate *q;
+
+ if (p == NULL) return NULL;
+ p->right=MR_removeRedundantPredPass3(p->right);
+ p->down=MR_removeRedundantPredPass3(p->down);
+ if (p->redundant) {
+ q=p->right;
+ p->right=NULL;
+ predicate_free(p);
+ return q;
+ };
+ if (p->expr == PRED_AND_LIST ||
+ p->expr == PRED_OR_LIST) {
+ if (p->down == NULL) {
+ q=p->right;
+ p->right=NULL;
+ predicate_free(p);
+ return q;
+ };
+ if (p->down != NULL && p->down->right == NULL) {
+ q=p->down;
+ q->right=p->right;
+ p->right=NULL;
+ p->down=NULL;
+ return q;
+ };
+ };
+ return p;
+}
+
+#ifdef __USE_PROTOS
+void MR_removeRedundantPredPass2(Predicate *p)
+#else
+void MR_removeRedundantPredPass2(p)
+ Predicate *p;
+#endif
+{
+ Predicate *q;
+
+ if (p == NULL) return;
+
+ if (p->expr == PRED_AND_LIST) {
+ for (q=p->down ; q != NULL ; q=q->right) {
+ MR_removeRedundantPredPass2(q);
+ if (q->isConst) {
+ if (q->constValue == 0) {
+ p->isConst=1;
+ p->constValue=0;
+ return;
+ } else {
+ q->redundant=1;
+ };
+ };
+ };
+ };
+
+ if (p->expr == PRED_OR_LIST) {
+ for (q=p->down ; q != NULL ; q=q->right) {
+ MR_removeRedundantPredPass2(q);
+ if (q->isConst) {
+ if (q->constValue == 0) {
+ q->redundant=1;
+ } else {
+ p->isConst=1;
+ p->constValue=1;
+ return;
+ };
+ };
+ };
+ };
+
+ return;
+}
+
+#if 0
+ this totally ignores the implications of guarded predicates
+ in which the part after the guard could possibly cover a predicate.
+ that would be much harder:
+
+ rule : (A)? => <<p>>? sub1; /* 1 */
+ | (B)? => <<r>>? sub2 /* 2 */
+ sub1 : (A)? => <<q>>? A B /* 3 */
+ | B /* 4 - suppresses line 2 */
+ ;
+#endif
+
+#ifdef __USE_PROTOS
+void MR_apply_restriction1(Predicate *pred,set *plainSet,int *changed)
+#else
+void MR_apply_restriction1(pred,plainSet,changed)
+ Predicate *pred;
+ set *plainSet;
+ int *changed;
+#endif
+{
+ if (pred == NULL) return;
+ MR_apply_restriction1(pred->right,plainSet,changed);
+ if (pred->down != NULL) {
+ MR_apply_restriction1(pred->down,plainSet,changed);
+ } else {
+ set t;
+ if (pred->k == 1) {
+ t=set_dif(pred->scontext[1],*plainSet);
+ if (*changed == 0 &&
+ !set_equ(t,pred->scontext[1])) {
+ *changed=1;
+ };
+ if (set_nil(t)) {
+ pred->redundant=1;
+ };
+ set_free(pred->scontext[1]);
+ pred->scontext[1]=t;
+ };
+ };
+}
+
+#ifdef __USE_PROTOS
+void MR_orin_plainSet(Predicate *p,set plainSet)
+#else
+void MR_orin_plainSet(p,plainSet)
+ Predicate *p;
+ set plainSet;
+#endif
+{
+ if (p == NULL) return;
+ MR_orin_plainSet(p->down,plainSet);
+ MR_orin_plainSet(p->right,plainSet);
+ set_orin(&p->plainSet,plainSet);
+}
+
+Predicate *PRED_SUPPRESS;
+
+#ifdef __USE_PROTOS
+Predicate * MR_find_in_aSubBlk(Junction *alt)
+#else
+Predicate * MR_find_in_aSubBlk(alt)
+ Junction *alt;
+#endif
+{
+ Predicate *root=NULL;
+ Predicate **tail=NULL;
+
+ Junction *p;
+
+ int nAlts=0;
+ Junction **jList;
+ Predicate **predList;
+ int *matchList;
+ set predSet;
+ int i;
+ int j;
+ int m;
+ int predDepth;
+ set incomplete;
+ set union_plainSet;
+ set setChange;
+ int changed;
+ Predicate *newPred;
+ set setDif;
+ Predicate *origPred;
+ int depth1=1; /* const int */
+ set *plainContext;
+ set plainSet;
+
+ predSet=empty;
+ incomplete=empty;
+ union_plainSet=empty;
+ setChange=empty;
+ setDif=empty;
+ plainSet=empty;
+
+ if (PRED_SUPPRESS == NULL) {
+ PRED_SUPPRESS=new_pred();
+ PRED_SUPPRESS->expr="Predicate Suppressed";
+ };
+
+ /* this section just counts the number of "interesting" alternatives */
+ /* in order to allocate arrays */
+
+ for (p=alt; p!=NULL; p=(Junction *)p->p2) {
+ /* ignore empty alts */
+ if ( p->p1->ntype != nJunction ||
+ ((Junction *)p->p1)->jtype != EndBlk ) {
+ nAlts++;
+ };
+ };
+
+ /* if this is a (...)+ block then don't count the last alt because
+ it can't be taken until at least one time through the block.
+ In other words it isn't a real choice until the (...)+ is entered
+ at which point the hoisting issue is moot.
+ Maybe look at "ignore" instead ?
+ */
+
+ if (alt->jtype == aPlusBlk) {
+ nAlts--;
+ };
+
+ jList=(Junction **)calloc(nAlts,sizeof(Junction *));
+ require(jList!=NULL,"cannot allocate MR_find_in_aSubBlk jList");
+
+ plainContext=(set *)calloc(nAlts,sizeof(set));
+ require(plainContext!=NULL,"cannot allocate MR_find_in_aSubBlk plainContext");
+ for (m=0; m < nAlts; m++) plainContext[m]=empty;
+
+ predList=(Predicate **)calloc(nAlts,sizeof(Predicate *));
+ require(predList!=NULL,"cannot allocate MR_find_in_aSubBlk predList");
+
+ matchList=(int *)calloc(nAlts,sizeof(int));
+ require(matchList!=NULL,"cannot allocate MR_find_in_aSubBlk matchList");
+
+ /* this section just fills in the arrays previously allocated */
+ /* the most interesting one is matchList[] */
+ /* */
+ /* bit 0 => this alt has a semantic pred which is "covered" */
+ /* by an alt without a semantic pred. Don't hoist. */
+
+ for (i=0,p=alt;
+ p!=NULL && i<nAlts;
+ i++,p=(Junction *)p->p2) {
+
+ /* ignore empty alts */
+
+ if ( p->p1->ntype != nJunction ||
+ ((Junction *)p->p1)->jtype != EndBlk ) {
+ jList[i]=MR_junctionWithoutP2(p);
+ predList[i]=find_predicates(p->p1); /* should be jList ????? */
+ if (predList[i] != NULL) {
+ MR_cleanup_pred_trees(predList[i]); /* flatten & left factor */
+ plainContext[i]=MR_union_plain_sets(predList[i]);
+ } else {
+ MR_set_reuse(&plainSet);
+ MR_set_reuse(&incomplete);
+ plainSet=MR_First(depth1,jList[i],&incomplete);
+ MR_complete_set(depth1,&plainSet,&incomplete);
+ require(set_nil(incomplete),"couldn't complete k=1");
+ plainContext[i]=plainSet;
+ plainSet=empty;
+ };
+ set_orin(&union_plainSet,plainContext[i]);
+ };
+ };
+
+ if (nAlts == 1) {
+ goto EXIT_SIMPLE;
+ };
+
+/*
+ * Looking for cases where alt i has a semantic pred and alt j does not.
+ * Don't care about cases where lookahead for semantic predicates overlap
+ * because normal predicate hoisting does the correct thing automatically.
+ * Don't care about cases where lookahead for alts without semantic predicates
+ * overlap because normal prediction does the correct thing automatically.
+ *
+ * When we find such a case check for one of three subcases:
+ *
+ * 1. if lookahead for alt i is contained in the lookahead for any
+ * alt j then ignore semantic predicate of alt i
+ * 2. if lookahead for alt i is not contained in the lookahead for
+ * any alt j then add add predicate i to the OR list to be hoisted
+ * 3. if lookahead for alt i overlaps the lookahead for some alt j then
+ * add a dummy semantic predicate for alt j
+ *
+ * There is an implicit assumption that the context of all alternatives following
+ * the rule being processed here are identical (but may vary from hoist to
+ * hoist depending on the place where the rule was invoked that led to hoisting
+ * these predicates. In othere words in the fragment:
+ *
+ * ( <<a>>? a1 a2 a3 | <<b>>? b1 b2 b3 )
+ *
+ * both a3 and b3 have the same follow sets because they are both at the end of
+ * alternatives in the same block.
+ */
+
+ for (i=0; i < nAlts; i++) {
+ if (jList[i] == NULL) continue;
+ if (predList[i] == NULL) continue;
+
+ /* if the predicate depth turns out to be one token only */
+ /* then it is can be easily represented as a set and */
+ /* compared to the junction set create by MR_First() */
+
+ predDepth=0;
+ MR_pred_depth(predList[i],&predDepth);
+ require (predDepth >= 1,"MR_find_in_aSubBlk: pred depth < 1");
+ require (predDepth <= CLL_k,"MR_find_in_aSubBlk: predDepth > CLL_k");
+
+ /* complete predicates to predDepth
+ If completed to depth=1 then the context would be incomplete.
+ The context would be truncated and the predicate simplify routine
+ would have incomplete information. It would lead to
+ either false matches of failure to find true matches.
+ */
+
+ MR_complete_predicates(predDepth,predList[i]);
+
+ if (predList[i] != NULL) {
+ MR_cleanup_pred_trees(predList[i]); /* flatten & left factor */
+ };
+
+ /* If the predicate depth is 1 then it is possible to suppress
+ a predicate completely using a single plain alt. Check for suppression
+ by a single plain alt first because it gives better messages. If that
+ fails try the union of all the plain alts.
+ */
+
+ if (predDepth == 1) {
+
+ MR_set_reuse(&predSet);
+ predSet=MR_compute_pred_set(predList[i]); /* ignores k>1 predicates */
+
+ for (j=0; j < nAlts; j++) {
+ if (jList[j] == NULL) continue;
+ if (j == i) continue;
+
+ MR_set_reuse(&setDif);
+ setDif=set_dif(predSet,plainContext[j]);
+ if (set_nil(setDif)) {
+ matchList[i] |= 1;
+ MR_reportSetSuppression(predDepth,predSet,plainContext[j],jList[i],jList[j],predList[i]);
+ predicate_free(predList[i]);
+ predList[i]=PRED_SUPPRESS;
+ goto next_i;
+ };
+
+ }; /* end loop on j */
+
+ changed=0;
+
+ /* predicate_dup is only to give good error messages */
+ /* remember to do a predicate_free() */
+
+ origPred=predicate_dup(predList[i]);
+ MR_apply_restriction1(predList[i],&union_plainSet,&changed);
+ if (changed) {
+
+ /* don't use Pass3 by itself unless you know that inverted is not important */
+
+ newPred=MR_removeRedundantPredPass3(predList[i]);
+ newPred=MR_predSimplifyALL(newPred);
+ if (newPred == NULL) {
+ matchList[i] |= 1;
+ MR_reportSetSuppression(predDepth,predSet,union_plainSet,jList[i],
+ NULL,origPred);
+ predList[i]=PRED_SUPPRESS;
+ } else {
+ MR_reportSetRestriction(predDepth,predSet,union_plainSet,jList[i],
+ NULL,origPred,newPred);
+ predList[i]=newPred;
+ };
+ };
+ predicate_free(origPred);
+ origPred=NULL;
+ };
+
+ /*
+ If the predicate depth is > 1 then it can't be suppressed completely
+ because the code doesn't support inspection of such things. They're
+ much messier than k=1 sets.
+ */
+
+ if (predDepth > 1 ) {
+
+ changed=0;
+
+ /* predicate_dup is only to give good error messages */
+ /* remember to do a predicate_free() */
+
+ origPred=predicate_dup(predList[i]);
+ MR_apply_restriction1(predList[i],&union_plainSet,&changed);
+ if (changed) {
+ newPred=MR_removeRedundantPredPass3(predList[i]);
+ newPred=MR_predSimplifyALL(newPred);
+ if (newPred == NULL) {
+ matchList[i] |= 1;
+ MR_reportSetSuppression(predDepth,predSet,union_plainSet,jList[i],
+ NULL,origPred);
+ predList[i]=PRED_SUPPRESS;
+ } else {
+ MR_reportSetRestriction(predDepth,predSet,union_plainSet,jList[i],
+ NULL,origPred,newPred);
+ predList[i]=newPred;
+ };
+ };
+ predicate_free(origPred);
+ origPred=NULL;
+ };
+next_i:
+ continue;
+ };
+
+EXIT_SIMPLE:
+
+ root = new_pred();
+ root->expr=PRED_OR_LIST;
+ tail = &(root->down);
+
+ for (i=0 ; i< nAlts ; i++) {
+ if (jList[i] == NULL) continue;
+
+ if (predList[i] == NULL) {
+ continue;
+ } else if ( (matchList[i] & 1) != 0) {
+ if (predList[i] != PRED_SUPPRESS) {
+ predicate_free(predList[i]);
+ };
+ continue;
+ };
+
+ /* make an OR list of predicates */
+
+ *tail=predList[i];
+ tail=&(predList[i]->right);
+ };
+
+ /* if just one pred, remove OR root */
+
+ if (root->down == NULL) {
+ predicate_free(root);
+ root=NULL;
+ } else if (root->down->right == NULL) {
+ Predicate *p=root->down;
+ root->down=NULL;
+ predicate_free(root);
+ root=p;
+ }
+
+ root=MR_predSimplifyALL(root);
+
+ MR_orin_plainSet(root,union_plainSet);
+
+ set_free(predSet);
+ set_free(union_plainSet);
+ set_free(incomplete);
+ set_free(setChange);
+ set_free(setDif);
+
+ for (m=0; m < nAlts; m++) set_free(plainContext[m]);
+
+ free ( (char *) jList);
+ free ( (char *) predList);
+ free ( (char *) matchList);
+ free ( (char *) plainContext);
+
+ return root;
+}
+
+#ifdef __USE_PROTOS
+void MR_predContextPresent(Predicate *p,int *allHaveContext,int *noneHaveContext)
+#else
+void MR_predContextPresent(p,allHaveContext,noneHaveContext)
+ Predicate *p;
+ int *allHaveContext;
+ int *noneHaveContext;
+#endif
+{
+ if (p == NULL) return;
+ MR_predContextPresent(p->right,allHaveContext,noneHaveContext);
+ if (p->expr != PRED_AND_LIST &&
+ p->expr != PRED_OR_LIST) {
+ if (set_nil(p->scontext[1]) == 0 ||
+ (p->tcontext != NULL)) {
+ *noneHaveContext=0;
+ } else {
+ *allHaveContext=0;
+ };
+ };
+ MR_predContextPresent(p->down,allHaveContext,noneHaveContext);
+}
+
+#ifdef __USE_PROTOS
+int MR_pointerStackPush(PointerStack *ps,void *dataPointer)
+#else
+int MR_pointerStackPush(ps,dataPointer)
+ PointerStack *ps;
+ void *dataPointer;
+#endif
+{
+ void **newStack;
+ int newSize;
+ int i;
+
+ if (ps->count == ps->size) {
+ newSize=20+ps->size*2;
+ newStack=(void **)calloc(newSize,sizeof(void *));
+ require (newStack != NULL,"cannot allocate PointerStack");
+ for (i=0; i < ps->size; i++) {
+ newStack[i]=ps->data[i];
+ };
+ if (ps->data != NULL) free( (char *) ps->data);
+ ps->data=newStack;
+ ps->size=newSize;
+ };
+ ps->data[ps->count]=dataPointer;
+ ps->count++;
+ return ps->count-1;
+}
+
+#ifdef __USE_PROTOS
+void * MR_pointerStackPop(PointerStack *ps)
+#else
+void * MR_pointerStackPop(ps)
+ PointerStack *ps;
+#endif
+{
+ void *dataPointer;
+
+ require(ps->count > 0,"MR_pointerStackPop underflow");
+
+ dataPointer=ps->data[ps->count-1];
+ ps->data[ps->count-1]=NULL;
+ (ps->count)--;
+ return dataPointer;
+}
+
+#ifdef __USE_PROTOS
+void * MR_pointerStackTop(PointerStack *ps)
+#else
+void * MR_pointerStackTop(ps)
+ PointerStack *ps;
+#endif
+{
+ require(ps->count > 0,"MR_pointerStackTop underflow");
+ return ps->data[ps->count-1];
+}
+
+#ifdef __USE_PROTOS
+void MR_pointerStackReset(PointerStack *ps)
+#else
+void MR_pointerStackReset(ps)
+ PointerStack *ps;
+#endif
+{
+ int i;
+ if (ps->data != NULL) {
+ for (i=0; i < ps->count ; i++) {
+ ps->data[i]=NULL;
+ };
+ };
+ ps->count=0;
+}
+
+#ifdef __USE_PROTOS
+Junction *MR_nameToRuleBlk(char *name)
+#else
+Junction *MR_nameToRuleBlk(name)
+ char *name;
+#endif
+{
+ RuleEntry *q;
+
+ require (RulePtr != NULL,"MR_nameToRule: RulePtr not initialized");
+
+ if (name == NULL) return NULL;
+
+ q = (RuleEntry *) hash_get(Rname,name);
+
+ if ( q == NULL ) {
+ return NULL;
+ } else {
+ return RulePtr[q->rulenum];
+ };
+}
+
+#ifdef __USE_PROTOS
+Junction * MR_ruleReferenced(RuleRefNode *rrn)
+#else
+Junction * MR_ruleReferenced(rrn)
+ RuleRefNode *rrn;
+#endif
+{
+ return MR_nameToRuleBlk(rrn->text);
+}
+
+#ifdef __USE_PROTOS
+void MR_comparePredLeaves(Predicate *me,Predicate *myParent,Predicate *him,Predicate *hisParent)
+#else
+void MR_comparePredLeaves(me,myParent,him,hisParent)
+ Predicate *me;
+ Predicate *myParent;
+ Predicate *him;
+ Predicate *hisParent;
+#endif
+{
+ if (me == NULL) return;
+ if (me == him) {
+ MR_comparePredLeaves(me->right,myParent,him,hisParent);
+ return;
+ } else if (me->expr == PRED_AND_LIST ||
+ me->expr == PRED_OR_LIST) {
+ MR_comparePredLeaves(me->down,me,him,hisParent);
+ MR_comparePredLeaves(me->right,myParent,him,hisParent);
+ return;
+ } else {
+ if (me->source != NULL) {
+
+ /* predicate->invert can be set only in the predEntry predicates */
+ /* thus they are only visible after the predEntry predicates have been "unfolded" */
+
+ int sameSource=(me->source == him->source);
+ int sameInvert=1 &
+ (1 + me->inverted + him->inverted + me->source->inverted + him->source->inverted);
+ int samePredEntry=(me->source->predEntry != NULL
+ && him->source->predEntry != NULL
+ && me->source->predEntry == him->source->predEntry);
+ if (sameInvert && (sameSource || samePredEntry)) {
+ if (MR_identicalContext(me,him)) {
+
+ /* identical predicates */
+
+ if (hisParent->expr == PRED_OR_LIST &&
+ myParent->expr == PRED_OR_LIST) {
+ me->redundant=1;
+ } else if (hisParent->expr == PRED_AND_LIST &&
+ myParent->expr == PRED_AND_LIST) {
+ me->redundant=1;
+ } else if ( (hisParent->expr == PRED_OR_LIST &&
+ myParent->expr == PRED_AND_LIST)
+ ||
+ (hisParent->expr == PRED_AND_LIST &&
+ myParent->expr == PRED_OR_LIST)
+ ) {
+ myParent->redundant=1;
+ } else {
+ require (0,"MR_comparePredLeaves: not both PRED_LIST");
+ };
+ };
+ }; /* end same source or same predEntrr with same invert sense */
+
+ /* same predEntry but opposite invert sense */
+
+ if (!sameInvert && (sameSource || samePredEntry)) {
+ if (MR_identicalContext(me,him)) {
+ if (hisParent->expr == PRED_OR_LIST &&
+ myParent->expr == PRED_OR_LIST) {
+ myParent->isConst=1;
+ myParent->constValue=1;
+ } else if (hisParent->expr == PRED_AND_LIST &&
+ myParent->expr == PRED_AND_LIST) {
+ myParent->isConst=1;
+ myParent->constValue=0;
+ } else if ( (hisParent->expr == PRED_OR_LIST &&
+ myParent->expr == PRED_AND_LIST)
+ ||
+ (hisParent->expr == PRED_AND_LIST &&
+ myParent->expr == PRED_OR_LIST)
+ ) {
+ me->redundant=1;
+ } else {
+ require (0,"MR_comparePredLeaves: not both PRED_LIST");
+ };
+ };
+ }; /* end same predEntry with opposite invert sense */
+ };
+
+ MR_comparePredLeaves(me->right,myParent,him,hisParent);
+ return;
+ };
+}
+
+#ifdef __USE_PROTOS
+void MR_removeRedundantPredPass1(Predicate *me,Predicate *myParent)
+#else
+void MR_removeRedundantPredPass1(me,myParent)
+ Predicate *me;
+ Predicate *myParent;
+#endif
+{
+ if (me == NULL) return;
+ if (me->redundant) {
+ MR_removeRedundantPredPass1(me->right,myParent);
+ return;
+ };
+ if (me->expr == PRED_AND_LIST ||
+ me->expr == PRED_OR_LIST) {
+ MR_removeRedundantPredPass1(me->down,me);
+ MR_removeRedundantPredPass1(me->right,myParent);
+ } else {
+ require (me->source != NULL,"me->source == NULL");
+ if (myParent != NULL) {
+ MR_comparePredLeaves(myParent->down,myParent,me,myParent);
+ };
+ MR_removeRedundantPredPass1(me->right,myParent);
+ };
+}
+
+/* pretty much ignores things with the inverted bit set */
+
+#ifdef __USE_PROTOS
+Predicate *MR_predFlatten(Predicate *p)
+#else
+Predicate *MR_predFlatten(p)
+ Predicate *p;
+#endif
+{
+ if (p == NULL) return NULL;
+ if (p->expr == PRED_OR_LIST
+ || p->expr == PRED_AND_LIST) {
+
+ Predicate *child;
+ Predicate *gchild;
+ Predicate **tail;
+ Predicate *next;
+ char *PRED_XXX_LIST=p->expr;
+
+ require (p->down != NULL,"MR_predFlatten AND/OR no child");
+
+
+ p->down=MR_predFlatten(p->down);
+ p->right=MR_predFlatten(p->right);
+ child=p->down;
+ if (child->right == NULL) {
+ child->right=p->right;
+ p->right=NULL;
+ p->down=NULL;
+ if (p->inverted) child->inverted=!child->inverted;
+ predicate_free(p);
+ return child;
+ };
+
+ /* make a single list of all children and grandchildren */
+
+ tail=&(p->down);
+ for (child=p->down; child != NULL; child=next) {
+ if (child->expr != PRED_XXX_LIST
+ || child->inverted
+ || child->predEntry != NULL) {
+ *tail=child;
+ tail=&(child->right);
+ next=child->right;
+ } else {
+ for (gchild=child->down;
+ gchild != NULL;
+ gchild=gchild->right) {
+ *tail=gchild;
+ tail=&(gchild->right);
+ };
+ next=child->right;
+ child->right=NULL;
+ child->down=NULL;
+ predicate_free(child);
+ };
+ };
+ *tail=NULL;
+ return p;
+ } else {
+ p->right=MR_predFlatten(p->right);
+ return p;
+ };
+}
+
+static char *alwaysFalseWarning=NULL;
+
+#ifdef __USE_PROTOS
+Predicate *checkPredicateConflict(Predicate *p)
+#else
+Predicate *checkPredicateConflict(p)
+ Predicate *p;
+#endif
+{
+ if (p->isConst) {
+ if (p->constValue == 1) {
+ predicate_free(p);
+ return NULL;
+ } else {
+ if (InfoP && !p->conflictReported) {
+ p->conflictReported=1;
+ fprintf(output,"\n#if 0\n\n");
+ fprintf(output,"The following predicate expression will always be false:\n\n");
+ MR_dumpPred1(1,p,1);
+ fprintf(output,"\n#endif\n");
+ };
+
+ if (alwaysFalseWarning != CurRule) {
+ alwaysFalseWarning=CurRule;
+ if (InfoP) {
+ warnNoFL(eMsg1("one (or more) predicate expression hoisted into rule \"%s\" are always false \
+- see output file for more information",CurRule));
+ } else {
+ warnNoFL(eMsg1("one (or more) predicate expressions hoisted into rule \"%s\" are always false \
+- use \"-info p\" for more information",CurRule));
+ };
+ };
+ };
+ };
+ return p;
+}
+
+
+#ifdef __USE_PROTOS
+int MR_countPredNodes(Predicate *p)
+#else
+int MR_countPredNodes(p)
+ Predicate *p;
+#endif
+{
+ if (p == NULL) return 0;
+ return 1 + MR_countPredNodes(p->down) + MR_countPredNodes(p->right);
+}
+
+#ifdef __USE_PROTOS
+Predicate *MR_predSimplifyALLX(Predicate *p,int skipPass3)
+#else
+Predicate *MR_predSimplifyALLX(p,skipPass3)
+ Predicate *p;
+ int skipPass3;
+#endif
+{
+ int countBefore;
+ int countAfter;
+
+ countAfter=MR_countPredNodes(p);
+
+ do {
+ if (p == NULL) return NULL;
+ if (p->right == NULL && p->down == NULL) return p;
+ countBefore=countAfter;
+ MR_simplifyInverted(p,0);
+ p=MR_predFlatten(p);
+ MR_removeRedundantPredPass1(p,NULL);
+ MR_removeRedundantPredPass2(p);
+ if (! skipPass3) {
+ p=checkPredicateConflict(p);
+ p=MR_removeRedundantPredPass3(p);
+ };
+ countAfter=MR_countPredNodes(p);
+ } while (countBefore != countAfter);
+
+ return p;
+}
+
+#ifdef __USE_PROTOS
+Predicate *MR_predSimplifyALL(Predicate *p)
+#else
+Predicate *MR_predSimplifyALL(p)
+ Predicate *p;
+#endif
+{
+ return MR_predSimplifyALLX(p,0);
+}
+
+#ifdef __USE_PROTOS
+void MR_releaseResourcesUsedInRule(Node *n)
+#else
+void MR_releaseResourcesUsedInRule(n)
+ Node *n;
+#endif
+{
+ Node *next;
+ Junction *j;
+ int i;
+
+ if (n == NULL) return;
+ if (n->ntype == nJunction) {
+ j=(Junction *) n;
+
+ if (j->predicate != NULL) {
+ predicate_free(j->predicate);
+ j->predicate=NULL;
+ };
+ for (i=0; i< CLL_k; i++) {
+ set_free(j->fset[i]);
+ j->fset[i]=empty;
+ };
+ if (j->ftree != NULL) {
+ Tfree(j->ftree);
+ j->ftree=NULL;
+ };
+ if (j->jtype == EndRule) return;
+ if (j->jtype != RuleBlk && j->jtype != EndBlk) {
+ if (j->p2 != NULL && !j->ignore) { /* MR11 */
+ MR_releaseResourcesUsedInRule(j->p2);
+ };
+ };
+ };
+ next=MR_advance(n);
+ MR_releaseResourcesUsedInRule(next);
+}
+
+#ifdef __USE_PROTOS
+int MR_allPredLeaves(Predicate *p)
+#else
+int MR_allPredLeaves(p)
+ Predicate *p;
+#endif
+{
+ Predicate *q;
+
+ if (p == NULL) return 1;
+
+ for (q=p; q != NULL; q=q->right) {
+ if (q->down != NULL) return 0;
+ };
+ return 1;
+}
+
+/* make sure it works for the last rule in a file */
+
+#ifdef __USE_PROTOS
+int MR_offsetFromRule(Node *n)
+#else
+int MR_offsetFromRule(n)
+ Node *n;
+#endif
+{
+ Junction *j;
+ int offset=(-1);
+
+ for (j=SynDiag; j != NULL; j=(Junction *)j->p2) {
+
+ require (j->ntype == nJunction && j->jtype == RuleBlk,"Not a rule block");
+
+ if (n->file < j->file) {
+ return offset;
+ };
+ if (n->file == j->file) {
+ if (n->line < j->line) {
+ return (offset < 0) ? 0 : offset;
+ } else {
+ offset=n->line - j->line;
+ if (offset == 0) return 0;
+ };
+ };
+ };
+ return offset;
+}
+
+#define ruleNameMax 50
+
+static char ruleNameStatic1[ruleNameMax];
+static char ruleNameStatic2[ruleNameMax+10];
+
+#ifdef __USE_PROTOS
+char * MR_ruleNamePlusOffset(Node *n)
+#else
+char * MR_ruleNamePlusOffset(n)
+ Node *n;
+#endif
+{
+ int offset=MR_offsetFromRule(n);
+
+ strncpy(ruleNameStatic1,n->rname,ruleNameMax);
+ if (offset < 0) {
+ sprintf(ruleNameStatic2,"%s/?",ruleNameStatic1);
+ } else {
+ sprintf(ruleNameStatic2,"%s/%d",ruleNameStatic1,offset+1);
+ };
+ return ruleNameStatic2;
+}
+
+#ifdef __USE_PROTOS
+int MR_max_height_of_tree(Tree *t)
+#else
+int MR_max_height_of_tree(t)
+ Tree *t;
+#endif
+{
+ int h;
+ int height=0;
+ Tree *u;
+
+ if (t == NULL) return 0;
+
+ require (t->token != ALT && t->token != EpToken,"MR_max_height_of_tree ALT or EpToken");
+
+ for (u=t; u != NULL; u=u->right) {
+ h=MR_max_height_of_tree(u->down)+1;
+ if (h > height) height=h;
+ };
+ return height;
+}
+
+#ifdef __USE_PROTOS
+int MR_all_leaves_same_height(Tree *t,int depth)
+#else
+int MR_all_leaves_same_height(t,depth)
+ Tree *t;
+ int depth;
+#endif
+{
+ if (t == NULL) {
+ return (depth==0);
+ };
+
+ require (t->token != ALT && t->token != EpToken,"MR_all_leaves_same_height ALT or EpToken");
+
+ if (depth == 0) {
+ return 0;
+ } else {
+ if ( ! MR_all_leaves_same_height(t->down,depth-1)) {
+ return 0;
+ };
+ if (t->right == NULL) {
+ return 1;
+ } else {
+ return MR_all_leaves_same_height(t->right,depth);
+ };
+ };
+}
+
+#ifdef __USE_PROTOS
+void MR_projectTreeOntoSet(Tree *tree,int ck,set *ckset)
+#else
+void MR_projectTreeOntoSet(tree,ck,ckset)
+ Tree *tree;
+ int ck;
+ set *ckset;
+#endif
+{
+ if (tree == NULL) return;
+
+ require(tree->token != EpToken,"MR_projectTreeOntoSet: EpToken unexpected\n");
+
+ MR_projectTreeOntoSet(tree->right,ck,ckset);
+ if (tree->token == ALT) {
+ MR_projectTreeOntoSet(tree->down,ck,ckset);
+ } else {
+ if (ck > 1) {
+ MR_projectTreeOntoSet(tree->down,ck-1,ckset);
+ } else {
+ set_orel(tree->token,ckset);
+ };
+ };
+}
+
+#ifdef __USE_PROTOS
+int MR_comparePredicates(Predicate *a,Predicate *b)
+#else
+int MR_comparePredicates(a,b)
+ Predicate *a;
+ Predicate *b;
+#endif
+{
+ Predicate *p;
+ Predicate *q;
+
+ if (a == b) return 1;
+ if (a == NULL || b == NULL ) return 0;
+ if (a->down == NULL && b->down == NULL) {
+
+ /* predicate->invert can be set only in the predEntry predicates */
+ /* thus they are only visible after the predEntry predicates have been "unfolded" */
+
+ int sameSource=(a->source == b->source);
+ int sameInvert= 1 & (1 +a->inverted + b->inverted +
+ a->source->inverted + b->source->inverted);
+ int samePredEntry=(a->source->predEntry != NULL
+ && b->source->predEntry != NULL
+ && a->source->predEntry == b->source->predEntry);
+ if (sameInvert && (sameSource || samePredEntry)) {
+ if (MR_identicalContext(a,b)) {
+ return 1;
+ };
+ };
+ return 0;
+ };
+ if (a->down == NULL || b->down == NULL) return 0;
+ if (a->expr != b->expr) return 0;
+
+ for (p=a->down; p != NULL; p=p->right) {
+ for (q=b->down; q != NULL; q=q->right) {
+ if (MR_comparePredicates(p,q)) goto NEXT_P;
+ };
+ return 0;
+NEXT_P:
+ continue;
+ };
+ return 1;
+}
+
+/*
+ * action->inverted can be set only when a predicate symbol appears in
+ * a rule: "rule : <<!XXX>>? X". It cannot be set under any
+ * other circumstances. In particular it cannot be set by
+ * "#pred NotA !A" or by "#pred Nota <<!A>>?". The first case
+ * creates a predEntry and the predicate expression of that predEntry
+ * has inverted set. In the second case, the code for handling "!"
+ * is only present in buildAction, which is not called by the #pred
+ * semantic routines, only when a <<...>>? is recognized as part of
+ * a rule definition.
+ *
+ * predicate->inverted can only be set by a predicate created by a #pred
+ * expression, such as "#pred NotA !A" or "#pred NotXY ! (X && Y) or
+ * "#pred XbarY !(X && Y)". In particular, it cannot be set by any
+ * predicate expression occurring under any other circumstances.
+ * The #pred predicate expresssions are stored with in predEntry->pred
+ * and do not normally appear anywhere else until the predicates are
+ * "unfolded" in order to recognize redundancies, conflicts, and
+ * tautologies.
+ *
+ * The unfold routine expands all references to #pred expressions.
+ *
+ * The simplifyInvert goes through and propagates the invert bit so that
+ * all OR and AND nodes are un-inverted.
+ *
+ * Note that !(A and B) => (!A or !B)
+ * !(A or B) => (!A and !B)
+ *
+ * MR_unfold() is called to expand predicate symbols by replacing predicates
+ * that reference predicate entries with the copies of the predicate entries.
+ * Each reference receives a duplicate of the original. This is necessary
+ * because the next phase involves simplification and removal of redundant
+ * predicate nodes. Anyway, the point I'm making is that predicate->invert
+ * should not be set in any predicate until it has been expanded.
+ *
+ * This is a recursive structure, but there is no need for "recursive expansion"
+ * by which I mean a predicate symbol refers to other predicate symbols which
+ * must also be expanded.
+ *
+ * Recursive expansion is *not* performed by this routine because it is not
+ * necessary. Expansion of references is performed by predPrimary when
+ * a new predicate symbol is created by referring to others in the pred expr.
+ */
+
+#ifdef __USE_PROTOS
+Predicate *MR_unfold(Predicate *pred)
+#else
+Predicate *MR_unfold(pred)
+ Predicate *pred;
+#endif
+{
+ Predicate *result;
+
+ if (pred == NULL) return NULL;
+
+ pred->right=MR_unfold(pred->right);
+
+ if (pred->down == NULL) {
+ if (pred->source->predEntry != NULL) {
+ if (pred->source->predEntry->pred == NULL) {
+ ; /* do nothing */ /* a reference to a literal #pred (perhaps with "!" */
+ } else {
+ result=predicate_dup_without_context(pred->source->predEntry->pred);
+ if (pred->inverted) {
+ result->inverted=!result->inverted;
+ };
+ if (pred->source->inverted) {
+ result->inverted=!result->inverted;
+ };
+ result->right=pred->right;
+ pred->right=NULL;
+ predicate_free(pred);
+/*** result=MR_unfold(result); *** not necessary */ /* recursive expansion */
+ return result;
+ };
+ } else {
+ ; /* do nothing */ /* an inline literal predicate */
+ };
+ } else {
+ pred->down=MR_unfold(pred->down);
+ };
+ return pred;
+}
+
+/* this should be called immediately after MR_unfold() and
+ at no other times
+*/
+
+#ifdef __USE_PROTOS
+void MR_simplifyInverted(Predicate *pred,int inverted)
+#else
+void MR_simplifyInverted(pred,inverted)
+ Predicate *pred;
+ int inverted;
+#endif
+{
+ int newInverted;
+
+ if (pred == NULL) return;
+
+ MR_simplifyInverted(pred->right,inverted);
+
+ newInverted= 1 & (inverted + pred->inverted);
+
+ if (pred->down == NULL) {
+ pred->inverted=newInverted;
+ } else {
+ if (newInverted != 0) {
+ if (pred->expr == PRED_AND_LIST) {
+ pred->expr=PRED_OR_LIST;
+ } else {
+ pred->expr=PRED_AND_LIST;
+ };
+ };
+ pred->inverted=0;
+ MR_simplifyInverted(pred->down,newInverted);
+ };
+}
+
+/* only remove it from AND and OR nodes, not leaves */
+
+#ifdef __USE_PROTOS
+void MR_clearPredEntry(Predicate *p)
+#else
+void MR_clearPredEntry(p)
+ Predicate *p;
+#endif
+{
+ if (p == NULL) return;
+ MR_clearPredEntry(p->down);
+ MR_clearPredEntry(p->right);
+ if (p->down != NULL) p->predEntry=NULL;
+}
+
+
+#ifdef __USE_PROTOS
+void MR_orphanRules(FILE *f)
+#else
+void MR_orphanRules(f)
+ FILE *f;
+#endif
+{
+ set a;
+ Junction *p;
+ unsigned e;
+ RuleEntry *re;
+
+ a=empty;
+
+ if (! InfoO) return;
+
+ for (p=SynDiag; p!=NULL; p = (Junction *)p->p2) {
+ if ( (Junction *) (p->end)->p1 == NULL) {
+ re=(RuleEntry *) hash_get(Rname,p->rname);
+ require (re != NULL,"RuleEntry == NULL");
+ set_orel(re->rulenum, &a);
+ }
+ }
+
+ if (set_deg(a) > 1) {
+ fprintf(f,"note: Start rules: {");
+ for (; !set_nil(a); set_rm(e,a)) {
+ e=set_int(a);
+ fprintf(f," %s",RulePtr[e]->rname);
+ };
+ fprintf(f," }\n");
+ };
+ set_free( a );
+}
+
+/* merge (X Y) and (X) to create (X) */
+
+static int *mergeChain;
+static Tree *mergeTree;
+
+#ifdef __USE_PROTOS
+Tree *MR_merge_tree_contexts_client(Tree *t,int chain[])
+#else
+Tree *MR_merge_tree_contexts_client(t,chain)
+ Tree *t;
+ int chain[];
+#endif
+{
+ if (t == NULL) return NULL;
+ if (chain[0] == 0) {
+ Tree *u=t->right;
+ t->right=NULL;
+ Tfree(t);
+ return MR_merge_tree_contexts_client(u,&chain[0]);
+ }
+ if (chain[0] == t->token) {
+ t->down=MR_merge_tree_contexts_client(t->down,&chain[1]);
+ };
+ t->right=MR_merge_tree_contexts_client(t->right,&chain[0]);
+ return t;
+}
+
+#ifdef __USE_PROTOS
+void MR_iterateOverTreeContexts(Tree *t,int chain[])
+#else
+void MR_iterateOverTreeContexts(t,chain)
+ Tree *t;
+ int chain[];
+#endif
+{
+ if (t == NULL) return;
+ chain[0]=t->token;
+ if (t->down != NULL) {
+ MR_iterateOverTreeContexts(t->down,&chain[1]);
+ } else {
+ MR_merge_tree_contexts_client(mergeTree,mergeChain);
+ };
+ MR_iterateOverTreeContexts(t->right,&chain[0]);
+ chain[0]=0;
+}
+
+#ifdef __USE_PROTOS
+Tree *MR_merge_tree_contexts(Tree *t)
+#else
+Tree *MR_merge_tree_contexts(t)
+ Tree *t;
+#endif
+{
+ int h=MR_max_height_of_tree(t);
+
+ mergeTree=t;
+ mergeChain=(int *) calloc(h+1,sizeof(int));
+ require (mergeChain != NULL,"MR_merge_tree_contexts: can't alloc chain");
+ MR_iterateOverTreeContexts(t,mergeChain);
+ t=tshrink(t);
+ t=tflatten(t);
+ t=tleft_factor(t);
+ free ( (char *) mergeChain);
+ mergeChain=NULL;
+ return t;
+}
+
+#ifdef __USE_PROTOS
+Tree *MR_compute_pred_tree_context(Predicate *p)
+#else
+Tree *MR_compute_pred_tree_context(p)
+ Predicate *p;
+#endif
+{
+ Tree *t;
+
+ t=MR_compute_pred_tree_ctxXX(p);
+ MR_merge_tree_contexts(t);
+ return t;
+}
+
+#ifdef __USE_PROTOS
+void MR_guardPred_plainSet(ActionNode *anode,Predicate *pred)
+#else
+void MR_guardPred_plainSet(anode,pred)
+ ActionNode *anode;
+ Predicate *pred;
+#endif
+{
+ Junction *j;
+ Predicate *workPred;
+ set maskSet;
+
+ maskSet=empty;
+
+ if (!MRhoisting) return;
+
+ /* it doesn't really matter whether the predicate has
+ depth k=1 or k>1 because we're not really looking
+ at the predicate itself, just the stuff "behind"
+ the predicate.
+ */
+
+ /* shouldn't have to worry about REACHing off the end
+ of the rule containing the predicate because the
+ Rule->end->halt should have been set already by the
+ the code which handles RuleRef nodes.
+
+ We don't want to REACH off the end of the rule because
+ this would give the "global" follow context rather than
+ the "local" context.
+
+ r1a : (A)? => <<p>>? r2 (A|B)
+ r1b : (A)? => <<p>>? r2 (A|C)
+ r2 : ();
+
+ For r1a we want follow of predicate = {A B}
+ we want plainSet = {B}
+ For r1b we want follow of predicate = {A C}
+ we want plainSet = {C}
+ */
+
+ require (anode->next->ntype == nJunction,"MR_guardpred_plainSet not Junction");
+ j=(Junction *)(anode->next);
+
+ workPred=predicate_dup_without_context(pred);
+ workPred->k=1;
+ workPred->scontext[1]=MR_First(1,j, &(workPred->completionSet) );
+ MR_complete_predicates(1,workPred);
+ if (pred->k == 1) {
+ maskSet=pred->scontext[1];
+ } else {
+ MR_projectTreeOntoSet(pred->tcontext,1,&maskSet);
+ }
+ pred->plainSet=set_dif(workPred->scontext[1],maskSet);
+ predicate_free(workPred);
+}
+
+/*******************************************************************************/
+
+static Tree * suppressTree;
+static int * suppressChain; /* element 0 not used */
+static set * suppressSets;
+static Node * suppressNode;
+static int suppressChainLength;
+int MR_SuppressSearch=0;
+static int suppressSucceeded;
+static Predicate * suppressPredicate;
+
+#ifdef __USE_PROTOS
+int MR_isChain(Tree *t)
+#else
+int MR_isChain(t)
+ Tree *t;
+#endif
+{
+ Tree *u;
+
+ for (u=t; u != NULL; u=u->down) {
+ if (u->right != NULL) return 0;
+ }
+ return 1;
+}
+
+#ifdef __USE_PROTOS
+int MR_suppressK_client(Tree *tree,int tokensInChain[])
+#else
+int MR_suppressK_client(tree,tokensInChain)
+ Tree *tree;
+ int tokensInChain[];
+#endif
+{
+ int i;
+ set *save_fset;
+ int save_ConstrainSearch;
+ set incomplete;
+ Tree *t;
+
+ suppressSucceeded=0; /* volatile */
+
+ if (suppressSets == NULL) {
+ suppressSets=(set *) calloc (CLL_k+1,sizeof(set));
+ require (suppressSets != NULL,"MR_suppressK_client: suppressSets alloc");
+ };
+
+ for (suppressChainLength=1;
+ tokensInChain[suppressChainLength+1] != 0;
+ suppressChainLength++) {};
+
+ require (suppressChainLength != 0,"MR_suppressK_client: chain empty");
+
+ for (i=1 ; i <= suppressChainLength ; i++) {
+ set_clr(suppressSets[i]);
+ set_orel( (unsigned) tokensInChain[i],
+ &suppressSets[i]);
+ };
+
+ save_fset=fset;
+ save_ConstrainSearch=ConstrainSearch;
+
+ fset=suppressSets;
+
+ MR_SuppressSearch=1;
+ MR_AmbSourceSearch=1;
+ MR_MaintainBackTrace=1;
+ ConstrainSearch=1;
+
+ maxk = suppressChainLength;
+
+ incomplete=empty;
+ t=NULL;
+
+/*** constrain = &(fset[1]); ***/
+
+ MR_setConstrainPointer(&(fset[1])); /* MR18 */
+
+ MR_pointerStackReset(&MR_BackTraceStack);
+
+ TRAV(suppressNode,maxk,&incomplete,t);
+
+ Tfree(t);
+
+ require (set_nil(incomplete),"MR_suppressK_client TRAV incomplete");
+ require (MR_BackTraceStack.count == 0,
+ "MR_suppressK_client: MR_BackTraceStack.count != 0");
+ set_free(incomplete);
+
+ ConstrainSearch=save_ConstrainSearch;
+ fset=save_fset;
+
+ MR_AmbSourceSearch=0;
+ MR_MaintainBackTrace=0;
+ MR_SuppressSearch=0;
+ return suppressSucceeded;
+}
+
+#ifdef __USE_PROTOS
+Tree * MR_iterateOverTreeSuppressK(Tree *t,int chain[])
+#else
+Tree * MR_iterateOverTreeSuppressK(t,chain)
+ Tree *t;
+ int chain[];
+#endif
+{
+ if (t == NULL) return NULL;
+ t->right=MR_iterateOverTreeSuppressK(t->right,&chain[0]);
+ chain[0]=t->token;
+ if (t->down != NULL) {
+ t->down=MR_iterateOverTreeSuppressK(t->down,&chain[1]);
+ if (t->down == NULL) {
+ Tree *u=t->right;
+ t->right=NULL;
+ Tfree(t);
+ chain[0]=0;
+ return u;
+ };
+ } else {
+ MR_suppressK_client(suppressTree,suppressChain);
+ if (suppressSucceeded) {
+ Tree *u=t->right;
+ t->right=NULL;
+ Tfree(t);
+ chain[0]=0;
+ return u;
+ };
+ };
+ chain[0]=0;
+ return t;
+}
+
+/* @@@ */
+
+#ifdef __USE_PROTOS
+Predicate * MR_suppressK(Node *j,Predicate *p)
+#else
+Predicate * MR_suppressK(j,p)
+ Node *j;
+ Predicate *p;
+#endif
+{
+ Predicate *result;
+ int guardPred=0;
+ int ampersandPred=0;
+ Node *nodePrime;
+
+ if (! MRhoistingk) {
+ return p;
+ }
+
+ if (! MRhoisting) return p;
+ if (CLL_k == 1) return p;
+
+ if (suppressChain == NULL) {
+ suppressChain=(int *) calloc(CLL_k+2,sizeof(int));
+ require (suppressChain != NULL,"MR_suppressK: can't allocate chain");
+ }
+
+ if (p == NULL) return NULL;
+
+ if (j->ntype == nJunction) {
+ nodePrime=(Node *) MR_junctionWithoutP2( (Junction *) j);
+ } else {
+ nodePrime=j;
+ };
+
+ p->down=MR_suppressK(j,p->down);
+ p->right=MR_suppressK(j,p->right);
+ if (p->down != NULL) {
+ result=p;
+ goto EXIT;
+ };
+ if (p->k == 1) {
+ result=p;
+ goto EXIT;
+ };
+
+ if (p->source != NULL) {
+ if (p->source->guardpred != NULL) guardPred=1;
+ if (p->source->ampersandPred != NULL) ampersandPred=1;
+ }
+
+ suppressPredicate=p;
+ suppressNode=nodePrime; /* was j*/
+
+ suppressTree=p->tcontext;
+
+ if (guardPred || ampersandPred) {
+ p->tcontext=MR_iterateOverTreeSuppressK(suppressTree,&suppressChain[1]);
+ if (p->tcontext == NULL) {
+ predicate_free(p);
+ result=NULL;
+ goto EXIT;
+ };
+ } else {
+ if (MR_isChain(p->tcontext)) {
+ p->tcontext=MR_iterateOverTreeSuppressK(suppressTree,&suppressChain[1]);
+ if (p->tcontext == NULL) {
+ predicate_free(p);
+ result=NULL;
+ goto EXIT;
+ };
+ }
+ }
+ result=p;
+EXIT:
+ return result;
+}
+
+#ifdef __USE_PROTOS
+void MR_suppressSearchReport(void)
+#else
+void MR_suppressSearchReport()
+#endif
+{
+ int i;
+ Node *p;
+ TokNode *tn;
+ int depth;
+ set setAnd;
+
+ /* number of tokens in back trace stack matches length of chain */
+
+ depth=0;
+ for (i=0; i < MR_BackTraceStack.count ; i++) {
+ p=(Node *) MR_BackTraceStack.data[i];
+ if (p->ntype == nToken) depth++;
+ };
+
+ require (depth == suppressChainLength,"depth > suppressChainLength");
+
+ /* token codes match chain */
+
+ depth=0;
+ for (i=0; i < MR_BackTraceStack.count ; i++) {
+ p=(Node *) MR_BackTraceStack.data[i];
+ if (p->ntype != nToken) continue;
+ tn=(TokNode *) p;
+ depth++;
+ if (set_nil(tn->tset)) {
+ require(set_el( (unsigned) tn->token,fset[depth]),
+ "MR_suppressSearchReport: no match to #token in chain");
+ } else {
+ setAnd=set_and(fset[depth],tn->tset);
+ require(!set_nil(setAnd),
+ "MR_suppressSearchReport: no match to #token set in chain");
+ set_free(setAnd);
+ };
+ };
+
+ /* have a match - now remove it from the predicate */
+
+ suppressSucceeded=1;
+
+ if (suppressSucceeded) {
+ fprintf(output,"\n");
+ fprintf(output,"#if 0\n");
+ fprintf(output,"\n");
+ fprintf(output,"Part (or all) of predicate with depth > 1 suppressed by ");
+ fprintf(output,"alternative without predicate\n\n");
+ MR_dumpPred(suppressPredicate,1);
+ fprintf(output,"The token sequence which is suppressed:");
+ fprintf(output," (");
+ for (i=1; i <= suppressChainLength; i++) {
+ fprintf(output," %s",TerminalString(suppressChain[i]));
+ };
+ fprintf(output," )\n");
+ fprintf(output,"The sequence of references which generate that sequence of tokens:\n\n");
+
+ MR_backTraceDumpItemReset();
+
+ for (i=0; i < MR_BackTraceStack.count ; i++) {
+ MR_backTraceDumpItem(output,0,(Node *) MR_BackTraceStack.data[i]);
+ };
+ fprintf(output,"\n");
+ fprintf(output,"#endif\n");
+ }
+}
+
+#ifdef __USE_PROTOS
+void MR_markCompromisedRule(Node *n)
+#else
+void MR_markCompromisedRule(n)
+ Node *n;
+#endif
+{
+ RuleEntry *q;
+ Node *mark=NULL;
+ Junction *j;
+
+ if (n->ntype == nRuleRef) {
+ mark=(Node *) MR_ruleReferenced( (RuleRefNode *) n);
+ } else if (n->ntype == nToken) {
+ mark=n;
+ } else if (n->ntype == nJunction) {
+ j=(Junction *)n;
+ switch (j->jtype) {
+ case aOptBlk:
+ case aLoopBlk:
+ case RuleBlk:
+ case EndRule:
+ case aPlusBlk:
+ case aLoopBegin:
+ mark=n;
+ break;
+ default:
+ break;
+ };
+ }
+
+ if (mark == NULL) return;
+
+ require (RulePtr != NULL,"RulePtr not initialized");
+
+ q = (RuleEntry *) hash_get(Rname,mark->rname);
+ require (q != NULL,"RuleEntry not found");
+ set_orel(q->rulenum,&MR_CompromisedRules);
+}
+
+#ifdef __USE_PROTOS
+void MR_alphaBetaTraceReport(void)
+#else
+void MR_alphaBetaTraceReport()
+#endif
+{
+ int i;
+
+ if (! AlphaBetaTrace) return;
+
+ MR_AlphaBetaMessageCount++;
+
+ fprintf(output,"\n");
+ fprintf(output,"#if 0\n");
+ fprintf(output,"\n");
+ fprintf(output,"Trace of references leading to attempt to compute the follow set of\n");
+ fprintf(output,"alpha in an \"(alpha)? beta\" block. It is not possible for antlr to\n");
+ fprintf(output,"compute this follow set because it is not known what part of beta has\n");
+ fprintf(output,"already been matched by alpha and what part remains to be matched.\n");
+ fprintf(output,"\n");
+ fprintf(output,"Rules which make use of the incorrect follow set will also be incorrect\n");
+ fprintf(output,"\n");
+
+ MR_backTraceDumpItemReset();
+
+ for (i=0; i < MR_BackTraceStack.count ; i++) {
+ MR_backTraceDumpItem(output,0,(Node *) MR_BackTraceStack.data[i]);
+ if (i < MR_BackTraceStack.count-1) {
+ MR_markCompromisedRule( (Node *) MR_BackTraceStack.data[i]);
+ };
+ };
+ fprintf(output,"\n");
+ fprintf(output,"#endif\n");
+}
+
+#ifdef __USE_PROTOS
+void MR_dumpRuleSet(set s)
+#else
+void MR_dumpRuleSet(s)
+ set s;
+#endif
+{
+ unsigned *cursor;
+ unsigned *origin=set_pdq(s);
+
+ require(origin != NULL,"set_pdq failed");
+
+ if (RulePtr == NULL) {
+ fprintf(stderr,"RulePtr[] not yet initialized");
+ } else {
+ for (cursor=origin; *cursor != nil ; cursor++) {
+/**** if (cursor != origin) fprintf(stderr,","); ****/
+ fprintf(stderr," %s",RulePtr[*cursor]->rname);
+ fprintf(stderr,"\n");
+ };
+ free( (char *) origin);
+ };
+}
|