mrhoist.c

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

#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 __STDC__
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 __STDC__
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 __STDC__
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 __STDC__
Predicate *MR_predSimplifyALL(Predicate *p)
#else
Predicate *MR_predSimplifyALL(p)
  Predicate     *p;
#endif
{
  return MR_predSimplifyALLX(p,0);
}

#ifdef __STDC__
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 __STDC__
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 __STDC__
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 __STDC__
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 __STDC__
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 __STDC__
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 __STDC__
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 __STDC__
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 __STDC__
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 __STDC__
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_