diff options
Diffstat (limited to 'BaseTools/Source/C/VfrCompile/Pccts/antlr/mrhoist.c')
| -rw-r--r-- | BaseTools/Source/C/VfrCompile/Pccts/antlr/mrhoist.c | 3030 |
1 files changed, 0 insertions, 3030 deletions
diff --git a/BaseTools/Source/C/VfrCompile/Pccts/antlr/mrhoist.c b/BaseTools/Source/C/VfrCompile/Pccts/antlr/mrhoist.c deleted file mode 100644 index 110bf5996f..0000000000 --- a/BaseTools/Source/C/VfrCompile/Pccts/antlr/mrhoist.c +++ /dev/null @@ -1,3030 +0,0 @@ -/*
- * 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);
- };
-}
|