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