mrhoist.c

本工具提供一个词法分析器和语法分析器的集成开发环境

  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 __STDC__
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 __STDC__
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 __STDC__
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 __STDC__
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 __STDC__
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 __STDC__
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 __STDC__
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 __STDC__
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 __STDC__
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 __STDC__
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 __STDC__
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");