mrhoist.c

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

}

#ifdef __STDC__
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 __STDC__
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;
    };
}

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

    save_MR_RuleBlkWithHalt=MR_RuleBlkWithHalt;

    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;
      b=empty;

      while ( !set_nil(*incomplete) ) {
		k2=set_int(*incomplete);
        if (k2 > predDepth) break;                    /* <=== another exit from loop */
		set_rm(k2,*incomplete);
        REACH(ruleRef->next,k2,&rk2,b);
		set_orin(tokensUsed,b);
		set_free(b);
      };

      if (MR_RuleBlkWithHalt != NULL) MR_RuleBlkWithHalt->end->halt=FALSE;

	  set_orin(incomplete,rk2);                       /* remember what we couldn't do */
      set_free(rk2);
	  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;
    };
}

#ifdef __STDC__
void MR_complete_tree(int predDepth,Tree **t,set *incomplete)
#else
void MR_complete_tree(predDepth,t,incomplete)
  int       predDepth;