mrhoist.c

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

    *tp=NULL;
    free ( (char *) pdq);
  };
  return t;
}

#ifdef __USE_PROTOS
void MR_check_pred_too_long(Predicate *p,set completion)
#else
void MR_check_pred_too_long(p,completion)
  Predicate     *p;
  set           completion;
#endif
{
  if (p != NULL &&
      p->source != NULL &&
      ! p->source->predTooLong) {
    if ( !set_nil(completion)) {
      p->source->predTooLong=1;
warnFL("It is unusual (but ok) for a semantic predicate to test context past the end of its own rule",
                                FileStr[p->source->file],p->source->line);
    };
  };
}

#ifdef __USE_PROTOS
int MR_predicate_context_completed(Predicate *p)
#else
int MR_predicate_context_completed(p)
  Predicate     *p;
#endif
{
  if (p == NULL) return 1;
  if (p->expr != PRED_AND_LIST &&
      p->expr != PRED_OR_LIST) {
    if ( ! set_nil(p->completionSet)) return 0;
    if ( ! set_nil(p->completionTree)) return 0;
  };
  return MR_predicate_context_completed(p->down) &
         MR_predicate_context_completed(p->right);
}

#ifdef __USE_PROTOS
Node * MR_advance(Node *n)
#else
Node * MR_advance(n)
  Node  *n;
#endif
{
    if (n == NULL) return NULL;
    switch (n->ntype) {
      case nJunction:   return ((Junction *)n)->p1;
      case nToken:      return ((TokNode *)n)->next;
      case nRuleRef:    return ((RuleRefNode *)n)->next;
      case nAction:     return ((ActionNode *)n)->next;
      default:          return NULL;
    };
  return NULL; /* MSVC 5.0 complains about missing return statement */
}

#ifdef __USE_PROTOS
Junction * MR_find_endRule(Node *n)
#else
Junction * MR_find_endRule(n)
  Node  *n;
#endif
{
    Node    *next;
    if (n == NULL) return NULL;
    for (next=n; next != NULL; next=MR_advance(next)) {
      if (next->ntype == nJunction &&
            ( (Junction *) next)->jtype == EndRule) {
        break;
      };
    };
    return (Junction *)next;
}

/*
   Intersection:  a branch which is shorter is chosen
   over one which is longer: (A B C) intersect (A B) yields (A B).

   AND: a branch which is longer is chosen over the one
   which is shorter: (A B C) AND (A B) yields (A B C)

*/

#ifdef __USE_PROTOS
Tree *MR_computeTreeIntersection(Tree *l,Tree *r)
#else
Tree *MR_computeTreeIntersection(l,r)
    Tree    *l;
    Tree    *r;
#endif
{
    Tree    *result=NULL;
    Tree    **tail;
    Tree    *p;
    Tree    *q;
    Tree    *match;

    if (l == NULL || r == NULL) return NULL;
    for (p=l; p != NULL; p=p->right) {
      require(p->token != EpToken,"MR_computeTreeIntersection: p->EpToken unexpected\n");
      require (p->token != ALT,"MR_computeTreeIntersection: p->ALT unexpected\n");
    };
    for (q=r; q != NULL; q=q->right) {
      require(q->token != EpToken,"MR_computeTreeIntersection: q->EpToken unexpected\n");
      require(q->token != ALT,"MR_computeTreeIntersection: q->ALT unexpected\n");
    };

    result=tnode(ALT);
    tail=&(result->down);

    for (p=l; p != NULL ; p=p->right) {
      for (q=r; q != NULL ; q=q->right) {
        if (p->token == q->token) {
          match=tnode(p->token);
          match->down=MR_computeTreeIntersection(p->down,q->down);
          *tail=match;
          tail=&(match->right);
        };
      };
    };

    *tail=NULL;
    result=tshrink(result);
    result=tflatten( result );
    result=tleft_factor( result );
    return result;
}

/* the predicates which are ANDed together have a common
   context:  they must all have common roots.  Thus the
   AND operation is more like an OR operation because
   branches which are longer are grafted onto shorter
   branches of the AND tree.  For instance combining
   (A B C) with (A B C D) gives (A B C D).  There
   should never be a case of (A B C) and (A B D) because
   they have the same context.

   Actually, this may not be true once one throws in
   guard predicates which are defined by the user, not
   the context.
*/

/* requires input trees to be in "canonical" format */

#ifdef __USE_PROTOS
Tree *MR_computeTreeAND(Tree *l,Tree *r)
#else
Tree *MR_computeTreeAND(l,r)
    Tree    *l;
    Tree    *r;
#endif
{
    Tree    *result=NULL;
    Tree    **tail;
    Tree    *p;
    Tree    *q;
    Tree    *match;

    if (l == NULL) return tdup(r);
    if (r == NULL) return tdup(l);

    for (p=l; p != NULL; p=p->right) {
/**** require(p->token != EpToken,"MR_computeTreeAND: p->EpToken unexpected\n"); ****/
      require (p->token != ALT,"MR_computeTreeAND: p->ALT unexpected\n");
    };
    for (q=r; q != NULL; q=q->right) {
/**** require(q->token != EpToken,"MR_computeTreeAND: q->EpToken unexpected\n"); ****/
      require(q->token != ALT,"MR_computeTreeAND: q->ALT unexpected\n");
    };

    result=tnode(ALT);
    tail=&(result->down);

    for (p=l; p != NULL ; p=p->right) {
      for (q=r; q != NULL ; q=q->right) {
        if (p->token == q->token) {
          match=tnode(p->token);
          match->down=MR_computeTreeAND(p->down,q->down);
          *tail=match;
          tail=&(match->right);
        };
      };
    };

    *tail=NULL;
    result=tshrink(result);
    result=tflatten( result );
    result=tleft_factor( result );
    return result;
}

#ifdef __USE_PROTOS
void MR_union_plain_sets1(Predicate *p,set *theUnion)
#else
void MR_union_plain_sets1(p,theUnion)
  Predicate     *p;
  set           *theUnion;
#endif
{
  if (p == NULL) return;
  MR_union_plain_sets1(p->down,theUnion);
  MR_union_plain_sets1(p->right,theUnion);
  set_orin(theUnion,p->plainSet);
  return;
}

#ifdef __USE_PROTOS
set MR_union_plain_sets(Predicate *p)
#else
set MR_union_plain_sets(p)
  Predicate     *p;
#endif
{
  set   theUnion;

  theUnion=empty;

  MR_union_plain_sets1(p,&theUnion);
  return theUnion;
}

/* does NOT left factor: do not want to merge
     (A B) with (A) to get (A B)
   in fact the opposite: (A B) with (A) gives (A)
*/

#ifdef __USE_PROTOS
Tree *MR_compute_pred_tree_ctxXX(Predicate *p)
#else
Tree *MR_compute_pred_tree_ctxXX(p)
  Predicate     *p;
#endif
{
    Tree        *result=NULL;
    Predicate   *q;
    Tree        *t;

    if (p == NULL) return NULL;

/* this appears strange: why do we OR the context
   of and AND predicate ?  It is because of the way
   that predicates are evaluated: if the context is
   wrong then it's the same as if the predicate was
   true.  That means that even when one leg of an
   AND has unmatched context, if the other leg has
   matched context and is true then the predicate
   succeeds.  It's only when all the legs have unmatched
   context that this one can skip evaluation of the
   predicates.
*/
    if (p->expr == PRED_OR_LIST ||
        p->expr == PRED_AND_LIST) {
      for (q=p->down; q != NULL ; q=q->right) {
        t=MR_compute_pred_tree_ctxXX(q);
        result=tappend(result,t);
        t=NULL;
      };

      result=tshrink(result);
      result=tflatten( result );

/* does NOT left factor: do not want to merge
     (A B) with (A) to get (A B)
   in fact the opposite: (A B) with (A) gives (A)
*/

/**** result=tleft_factor( result ); ****/
      return result;
    };

#if 0
**    if (p->expr == PRED_AND_LIST) {
**
**      Predicate     *l;
**      Predicate     *r;
**      Tree          *l1;
**      Tree          *r1;
**      Tree          *prevl1;
**
**      l=p->down;
**      require (l->right != NULL,"MR_compute_pred_tree - AND has only one child");
**
**/* l1 and r1 should already be in "canonical" format */
**
**      l1=MR_compute_pred_tree(l);
**      for (r=l->right; r != NULL; r=r->right) {
**        r1=MR_compute_pred_tree(r);
**        prevl1=l1;
**        l1=MR_computeTreeAND(l1,r1);
**        Tfree(r1);
**        Tfree(prevl1);
**      };
**
**/* result from computeTreeAND should be in "canonical" format */
**
**      result=l1;
**
**/* result of MR_computeTreeAND should be in "canonical" format */
**
**      return result;
**    };
#endif

    if (p->k == 1) {
      result=MR_make_tree_from_set(p->scontext[1]);
    } else {
      result=tdup(p->tcontext);
      result=MR_remove_epsilon_from_tree(result);
      result=tshrink(result);
      result=tflatten(result);
      result=tleft_factor(result);
    };
    return result;
}

#ifdef __USE_PROTOS
void MR_pred_depth(Predicate *p,int *maxDepth)
#else
void MR_pred_depth(p,maxDepth)
  Predicate     *p;
  int           *maxDepth;
#endif
{
  if (p == NULL) return;
  if (p->expr != PRED_OR_LIST &&
      p->expr != PRED_AND_LIST) {
    if (p->k > *maxDepth) *maxDepth=p->k;
  };
  MR_pred_depth(p->down,maxDepth);
  MR_pred_depth(p->right,maxDepth);
}

/* this computes the OR of all the contexts */

#ifdef __USE_PROTOS
set MR_compute_pred_set(Predicate *p)
#else
set MR_compute_pred_set(p)
  Predicate     *p;
#endif
{
    set         result;
    Predicate   *q;

    result=empty;

    if (p == NULL) return empty;

    if (p->expr == PRED_OR_LIST ||
        p->expr == PRED_AND_LIST) {         /* yes, I do mean PRED_AND_LIST !   */
                                            /* remember: r1: (A)? => <<p>>? r2; */
                                            /*           r2: (B)? => <<q>>? r3; */
      set   t;

      t=empty;
      result=empty;

      for (q=p->down; q != NULL; q=q->right) {
        t=MR_compute_pred_set(q);
        set_orin(&result,t);
        set_free(t);
      };
      return result;
    } else if (p->k > 1) {
      return empty;
    } else {
      return set_dup(p->scontext[1]);
    };
}

#ifdef __USE_PROTOS
set MR_First(int ck,Junction *j,set *incomplete)
#else
set MR_First(ck,j,incomplete)
  int       ck;
  Junction  *j;
  set       *incomplete;
#endif
{
    Junction    *p;
    set         tokensUsed;

    tokensUsed=empty;

	require(j->ntype==nJunction, "MR_First: non junction passed");

	p = analysis_point((Junction *)j->p1);

	REACH(p,ck,incomplete,tokensUsed);

    return tokensUsed;
}

#ifdef __USE_PROTOS
void MR_cleanup_pred_trees(Predicate *p)
#else
void MR_cleanup_pred_trees(p)
  Predicate     *p;
#endif
{
  Tree      *t;

  if (p == NULL) return;
  if (p->expr != PRED_OR_LIST &&
      p->expr != PRED_AND_LIST) {
    t=p->tcontext;
    t=tshrink(t);
    t=tflatten(t);
    t=tleft_factor(t);
    p->tcontext=t;
  };
  MR_cleanup_pred_trees(p->down);
  MR_cleanup_pred_trees(p->right);
}

/* does NOT return canonical tree */

#ifdef __USE_PROTOS
Tree * MR_remove_epsilon_from_tree(Tree *t)
#else
Tree * MR_remove_epsilon_from_tree(t)
  Tree  *t;
#endif
{
  if (t == NULL) return NULL;

  /* I think ALT can be ignored as a special case */

  if (t->token != EpToken) {
    t->down=MR_remove_epsilon_from_tree(t->down);
    t->right=MR_remove_epsilon_from_tree(t->right);
    return t;
  } else {
    Tree    *u;
    u=MR_remove_epsilon_from_tree(t->right);
    t->right=NULL;
    Tfree(t);
    return u;
  };
}

#ifdef __USE_PROTOS
void MR_complete_set(int predDepth,set *tokensUsed,set *incomplete)
#else
void MR_complete_set(predDepth,tokensUsed,incomplete)
  int       predDepth;
  set       *tokensUsed;
  set       *incomplete;
#endif
{
    int             i;
    RuleRefNode     *ruleRef;
	set             rk2;
    set             b;
	int             k2;
    Junction        *save_MR_RuleBlkWithHalt;

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