mrhoist.c

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

    for (m=0; m < nAlts; m++) plainContext[m]=empty;

    predList=(Predicate **)calloc(nAlts,sizeof(Predicate *));
    require(predList!=NULL,"cannot allocate MR_find_in_aSubBlk predList");

    matchList=(int *)calloc(nAlts,sizeof(int));
    require(matchList!=NULL,"cannot allocate MR_find_in_aSubBlk matchList");

    /* this section just fills in the arrays previously allocated       */
    /* the most interesting one is matchList[]                          */
    /*                                                                  */
    /*   bit 0 => this alt has a semantic pred which is "covered"       */
    /*              by an alt without a semantic pred.  Don't hoist.    */

	for (i=0,p=alt;
         p!=NULL && i<nAlts;
         i++,p=(Junction *)p->p2) {

	  /* ignore empty alts */

	  if ( p->p1->ntype != nJunction ||
	        ((Junction *)p->p1)->jtype != EndBlk )	{
        jList[i]=MR_junctionWithoutP2(p);
        predList[i]=find_predicates(p->p1);      /* should be jList ????? */
        if (predList[i] != NULL) {
          MR_cleanup_pred_trees(predList[i]);    /* flatten & left factor */
          plainContext[i]=MR_union_plain_sets(predList[i]);
        } else {
          MR_set_reuse(&plainSet);
          MR_set_reuse(&incomplete);
          plainSet=MR_First(depth1,jList[i],&incomplete);
          MR_complete_set(depth1,&plainSet,&incomplete);
          require(set_nil(incomplete),"couldn't complete k=1");
          plainContext[i]=plainSet;
          plainSet=empty;
        };
        set_orin(&union_plainSet,plainContext[i]);
      };
    };

    if (nAlts == 1) {
      goto EXIT_SIMPLE;
    };

/*
 *  Looking for cases where alt i has a semantic pred and alt j does not.
 *  Don't care about cases where lookahead for semantic predicates overlap
 *    because normal predicate hoisting does the correct thing automatically.
 *  Don't care about cases where lookahead for alts without semantic predicates
 *    overlap because normal prediction does the correct thing automatically.
 *
 *  When we find such a case check for one of three subcases:
 *
 *      1.  if lookahead for alt i is contained in the lookahead for any
 *          alt j then ignore semantic predicate of alt i
 *      2.  if lookahead for alt i is not contained in the lookahead for
 *          any alt j then add add predicate i to the OR list to be hoisted
 *      3.  if lookahead for alt i overlaps the lookahead for some alt j then
 *          add a dummy semantic predicate for alt j
 *
 *  There is an implicit assumption that the context of all alternatives following
 *  the rule being processed here are identical (but may vary from hoist to
 *  hoist depending on the place where the rule was invoked that led to hoisting
 *  these predicates.  In othere words in the fragment:
 *
 *            ( <<a>>? a1 a2 a3 | <<b>>? b1 b2 b3 )
 *
 *  both a3 and b3 have the same follow sets  because they are both at the end of
 *  alternatives in the same block.
 */

    for (i=0; i < nAlts; i++) {
      if (jList[i] == NULL) continue;
      if (predList[i] == NULL) continue;

        /* if the predicate depth turns out to be one token only */
        /*   then it is can be easily represented as a set and   */
        /*   compared to the junction set create by MR_First()   */

      predDepth=0;
      MR_pred_depth(predList[i],&predDepth);
      require (predDepth >= 1,"MR_find_in_aSubBlk: pred depth < 1");
      require (predDepth <= CLL_k,"MR_find_in_aSubBlk: predDepth > CLL_k");

        /* complete predicates to predDepth
           If completed to depth=1 then the context would be incomplete.
           The context would be truncated and the predicate simplify routine
             would have incomplete information.  It would lead to
             either false matches of failure to find true matches.
        */

      MR_complete_predicates(predDepth,predList[i]);

      if (predList[i] != NULL) {
        MR_cleanup_pred_trees(predList[i]);    /* flatten & left factor */
      };

      /* If the predicate depth is 1 then it is possible to suppress
           a predicate completely using a single plain alt.  Check for suppression
           by a single plain alt first because it gives better messages.  If that
           fails try the union of all the plain alts.
      */

      if (predDepth == 1) {

        MR_set_reuse(&predSet);
        predSet=MR_compute_pred_set(predList[i]);   /* ignores k>1 predicates */

        for (j=0; j < nAlts; j++) {
          if (jList[j] == NULL) continue;
          if (j == i) continue;

          MR_set_reuse(&setDif);
          setDif=set_dif(predSet,plainContext[j]);
          if (set_nil(setDif)) {
            matchList[i] |= 1;
            MR_reportSetSuppression(predDepth,predSet,plainContext[j],jList[i],jList[j],predList[i]);
            predicate_free(predList[i]);
            predList[i]=PRED_SUPPRESS;
            goto next_i;
          };

        }; /* end loop on j */

        changed=0;

        /* predicate_dup is only to give good error messages */
        /* remember to do a predicate_free()                 */

        origPred=predicate_dup(predList[i]);
        MR_apply_restriction1(predList[i],&union_plainSet,&changed);
        if (changed) {

          /* don't use Pass3 by itself unless you know that inverted is not important */

          newPred=MR_removeRedundantPredPass3(predList[i]);
          newPred=MR_predSimplifyALL(newPred);
          if (newPred == NULL) {
            matchList[i] |= 1;
            MR_reportSetSuppression(predDepth,predSet,union_plainSet,jList[i],
                                                            NULL,origPred);
            predList[i]=PRED_SUPPRESS;
          } else {
            MR_reportSetRestriction(predDepth,predSet,union_plainSet,jList[i],
                                                    NULL,origPred,newPred);
            predList[i]=newPred;
          };
        };
        predicate_free(origPred);
        origPred=NULL;
      };

      /*
         If the predicate depth is > 1 then it can't be suppressed completely
           because the code doesn't support inspection of such things.  They're
           much messier than k=1 sets.
      */

      if (predDepth > 1 ) {

        changed=0;

        /* predicate_dup is only to give good error messages */
        /* remember to do a predicate_free()                 */

        origPred=predicate_dup(predList[i]);
        MR_apply_restriction1(predList[i],&union_plainSet,&changed);
        if (changed) {
          newPred=MR_removeRedundantPredPass3(predList[i]);
          newPred=MR_predSimplifyALL(newPred);
          if (newPred == NULL) {
            matchList[i] |= 1;
            MR_reportSetSuppression(predDepth,predSet,union_plainSet,jList[i],
                                                            NULL,origPred);
            predList[i]=PRED_SUPPRESS;
          } else {
            MR_reportSetRestriction(predDepth,predSet,union_plainSet,jList[i],
                                                    NULL,origPred,newPred);
            predList[i]=newPred;
          };
        };
        predicate_free(origPred);
        origPred=NULL;
      };
next_i:
      continue;
    };

EXIT_SIMPLE:

    root = new_pred();
    root->expr=PRED_OR_LIST;
    tail = &(root->down);

    for (i=0 ; i< nAlts ; i++) {
      if (jList[i] == NULL) continue;

      if (predList[i] == NULL) {
        continue;
      } else if ( (matchList[i] & 1) != 0) {
        if (predList[i] != PRED_SUPPRESS) {
          predicate_free(predList[i]);
        };
        continue;
      };

      /* make an OR list of predicates */

      *tail=predList[i];
      tail=&(predList[i]->right);
    };

	/* if just one pred, remove OR root */

	if (root->down == NULL) {
      predicate_free(root);
      root=NULL;
    } else if (root->down->right == NULL) {
      Predicate     *p=root->down;
      root->down=NULL;
      predicate_free(root);
      root=p;
	}

    root=MR_predSimplifyALL(root);

    MR_orin_plainSet(root,union_plainSet);

    set_free(predSet);
    set_free(union_plainSet);
    set_free(incomplete);
    set_free(setChange);
    set_free(setDif);

    for (m=0; m < nAlts; m++) set_free(plainContext[m]);

    free ( (char *) jList);
    free ( (char *) predList);
    free ( (char *) matchList);
    free ( (char *) plainContext);

	return root;
}

#ifdef __STDC__
void MR_predContextPresent(Predicate *p,int *allHaveContext,int *noneHaveContext)
#else
void MR_predContextPresent(p,allHaveContext,noneHaveContext)
  Predicate     *p;
  int           *allHaveContext;
  int           *noneHaveContext;
#endif
{
  if (p == NULL) return;
  MR_predContextPresent(p->right,allHaveContext,noneHaveContext);
  if (p->expr != PRED_AND_LIST &&
      p->expr != PRED_OR_LIST) {
    if (set_nil(p->scontext[1]) == 0 ||
            (p->tcontext != NULL)) {
      *noneHaveContext=0;
    } else {
      *allHaveContext=0;
    };
  };
  MR_predContextPresent(p->down,allHaveContext,noneHaveContext);
}

#ifdef __STDC__
int MR_pointerStackPush(PointerStack *ps,void *dataPointer)
#else
int MR_pointerStackPush(ps,dataPointer)
  PointerStack  *ps;
  void          *dataPointer;
#endif
{
  void             **newStack;
  int              newSize;
  int              i;

  if (ps->count == ps->size) {
    newSize=20+ps->size*2;
    newStack=(void **)calloc(newSize,sizeof(void *));
    require (newStack != NULL,"cannot allocate PointerStack");
    for (i=0; i < ps->size; i++) {
      newStack[i]=ps->data[i];
    };
    if (ps->data != NULL) free( (char *) ps->data);
    ps->data=newStack;
    ps->size=newSize;
  };
  ps->data[ps->count]=dataPointer;
  ps->count++;
  return ps->count-1;
}

#ifdef __STDC__
void * MR_pointerStackPop(PointerStack *ps)
#else
void * MR_pointerStackPop(ps)
  PointerStack  *ps;
#endif
{
  void  *dataPointer;

  require(ps->count > 0,"MR_pointerStackPop underflow");

  dataPointer=ps->data[ps->count-1];
  ps->data[ps->count-1]=NULL;
  (ps->count)--;
  return dataPointer;
}

#ifdef __STDC__
void * MR_pointerStackTop(PointerStack *ps)
#else
void * MR_pointerStackTop(ps)
  PointerStack  *ps;
#endif
{
  require(ps->count > 0,"MR_pointerStackTop underflow");
  return ps->data[ps->count-1];
}

#ifdef __STDC__
void MR_pointerStackReset(PointerStack *ps)
#else
void MR_pointerStackReset(ps)
  PointerStack  *ps;
#endif
{
  int i;
  if (ps->data != NULL) {
    for (i=0; i < ps->count ; i++) {
       ps->data[i]=NULL;
    };
  };
  ps->count=0;
}

#ifdef __STDC__
Junction *MR_nameToRuleBlk(char *name)
#else
Junction *MR_nameToRuleBlk(name)
  char  *name;
#endif
{
    RuleEntry *q;

    require (RulePtr != NULL,"MR_nameToRule: RulePtr not initialized");

    if (name == NULL) return NULL;

    q = (RuleEntry *) hash_get(Rname,name);

	if ( q == NULL ) {
      return NULL;
    } else {
      return RulePtr[q->rulenum];
    };
}

#ifdef __STDC__
Junction * MR_ruleReferenced(RuleRefNode *rrn)
#else
Junction * MR_ruleReferenced(rrn)
  RuleRefNode   *rrn;
#endif
{
    return MR_nameToRuleBlk(rrn->text);
}

#ifdef __STDC__
void MR_comparePredLeaves(Predicate *me,Predicate *myParent,Predicate *him,Predicate *hisParent)
#else
void MR_comparePredLeaves(me,myParent,him,hisParent)
    Predicate *me;
    Predicate *myParent;
    Predicate *him;
    Predicate *hisParent;
#endif
{
    if (me == NULL) return;
    if (me == him) {
      MR_comparePredLeaves(me->right,myParent,him,hisParent);
      return;
    } else if (me->expr == PRED_AND_LIST ||
               me->expr == PRED_OR_LIST) {
      MR_comparePredLeaves(me->down,me,him,hisParent);
      MR_comparePredLeaves(me->right,myParent,him,hisParent);
      return;
    } else {
      if (me->source != NULL) {

        /* predicate->invert can be set only in the predEntry predicates        */
        /* thus they are only visible after the predEntry predicates have been "unfolded" */

        int     sameSource=(me->source == him->source);
        int     sameInvert=1 &
                 (1 + me->inverted + him->inverted + me->source->inverted + him->source->inverted);
        int     samePredEntry=(me->source->predEntry != NULL
                                 && him->source->predEntry != NULL
                                    && me->source->predEntry == him->source->predEntry);
        if (sameInvert && (sameSource || samePredEntry)) {
          if (MR_identicalContext(me,him)) {

            /* identical predicates */

            if (hisParent->expr == PRED_OR_LIST &&
                myParent->expr == PRED_OR_LIST) {
              me->redundant=1;
            } else if (hisParent->expr == PRED_AND_LIST &&
                       myParent->expr == PRED_AND_LIST) {
              me->redundant=1;
            } else if (  (hisParent->expr == PRED_OR_LIST &&
                          myParent->expr == PRED_AND_LIST)
                       ||
                         (hisParent->expr == PRED_AND_LIST &&
                          myParent->expr == PRED_OR_LIST)
                      ) {
              myParent->redundant=1;
            } else {
              require (0,"MR_comparePredLeaves: not both PRED_LIST");
            };
          };
        };  /* end same source or same predEntrr with same invert sense */

        /* same predEntry but opposite invert sense */

        if (!sameInvert && (sameSource || samePredEntry)) {
          if (MR_identicalContext(me,him)) {
            if (hisParent->expr == PRED_OR_LIST &&
                myParent->expr == PRED_OR_LIST) {
              myParent->isConst=1;
              myParent->constValue=1;
            } else if (hisParent->expr == PRED_AND_LIST &&
                       myParent->expr == PRED_AND_LIST) {
              myParent->isConst=1;
              myParent->constValue=0;
            } else if (  (hisParent->expr == PRED_OR_LIST &&
                          myParent->expr == PRED_AND_LIST)
                       ||
                         (hisParent->expr == PRED_AND_LIST &&
                          myParent->expr == PRED_OR_LIST)
                      ) {
              me->redundant=1;
            } else {
              require (0,"MR_comparePredLeaves: not both PRED_LIST");
            };
          };
        };  /* end same predEntry with opposite invert sense */
      };

      MR_comparePredLeaves(me->right,myParent,him,hisParent);
      return;
    };
}

#ifdef __STDC__
void MR_removeRedundantPredPass1(Predicate *me,Predicate *myParent)
#else
void MR_removeRedundantPredPass1(me,myParent)
  Predicate     *me;
  Predicate     *myParent;
#endif
{
    if (me == NULL) return;
    if (me->redundant) {
      MR_removeRedundantPredPass1(me->right,myParent);
      return;
    };
    if (me->expr == PRED_AND_LIST ||
        me->expr == PRED_OR_LIST) {
      MR_removeRedundantPredPass1(me->down,me);
      MR_removeRedundantPredPass1(me->right,myParent);
    } else {
      require (me->source != NULL,"me->source == NULL");
      if (myParent != NULL) {
        MR_comparePredLeaves(myParent->down,myParent,me,myParent);
      };
      MR_removeRedundantPredPass1(me->right,myParent);
    };
}

/* pretty much ignores things with the inverted bit set */

#ifdef __STDC__
Predicate *MR_predFlatten(Predicate *p)
#else
Predicate *MR_predFlatten(p)
  Predicate     *p;