mrhoist.c

来自「SRI international 发布的OAA框架软件」· C语言 代码 · 共 2,360 行 · 第 1/5 页

	Junction        *p;

    int             nAlts=0;
    Junction        **jList;
    Predicate       **predList;
    int             *matchList;
    set             predSet;
    int             i;
    int             j;
    int             m;
    int             predDepth;
    set             incomplete;
    set             union_plainSet;
    set             setChange;
    int             changed;
    Predicate       *newPred;
    set             setDif;
    Predicate       *origPred;
    int             depth1=1;             /* const int */
    set             *plainContext;
    set             plainSet;

    predSet=empty;
    incomplete=empty;
    union_plainSet=empty;
    setChange=empty;
    setDif=empty;
    plainSet=empty;

    if (PRED_SUPPRESS == NULL) {
      PRED_SUPPRESS=new_pred();
      PRED_SUPPRESS->expr="Predicate Suppressed";
    };

    /* this section just counts the number of "interesting" alternatives  */
    /*   in order to allocate arrays                                      */

	for (p=alt; p!=NULL; p=(Junction *)p->p2) {
	  /* ignore empty alts */
	  if ( p->p1->ntype != nJunction ||
	        ((Junction *)p->p1)->jtype != EndBlk )	{
        nAlts++;
      };
    };

    /* if this is a (...)+ block then don't count the last alt because
       it can't be taken until at least one time through the block.
       In other words it isn't a real choice until the (...)+ is entered
         at which point the hoisting issue is moot.
       Maybe look at "ignore" instead ?
    */

    if (alt->jtype == aPlusBlk) {
      nAlts--;
    };

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

    plainContext=(set *)calloc(nAlts,sizeof(set));
    require(plainContext!=NULL,"cannot allocate MR_find_in_aSubBlk plainContext");
    for (m=0; m < nAlts; m++) plainContext[m]=empty;

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

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

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

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

	  /* ignore empty alts */

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

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

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

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

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

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

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

      MR_complete_predicates(predDepth,predList[i]);

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

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

      if (predDepth == 1) {

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

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

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

        }; /* end loop on j */

        changed=0;

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

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

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

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

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

      if (predDepth > 1 ) {

        changed=0;

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

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

EXIT_SIMPLE:

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

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

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

      /* make an OR list of predicates */

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

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

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

    root=MR_predSimplifyALL(root);

    MR_orin_plainSet(root,union_plainSet);

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

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

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

	return root;
}

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

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

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

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

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

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

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

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

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

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

    if (name == NULL) return NULL;

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

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

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

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

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

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

            /* identical predicates */

            if (hisParent->expr == PRED_OR_LIST &&
                myParent->expr == PRED_OR_LIST) {
              me->redundant=1;
            } else if (hisParent->expr == PRED_AND_LIST &&