mrhoist.c

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

/*
 * mrhoist.c
 *
 * SOFTWARE RIGHTS
 *
 * We reserve no LEGAL rights to the Purdue Compiler Construction Tool
 * Set (PCCTS) -- PCCTS is in the public domain.  An individual or
 * company may do whatever they wish with source code distributed with
 * PCCTS or the code generated by PCCTS, including the incorporation of
 * PCCTS, or its output, into commerical software.
 *
 * We encourage users to develop software with PCCTS.  However, we do ask
 * that credit is given to us for developing PCCTS.  By "credit",
 * we mean that if you incorporate our source code into one of your
 * programs (commercial product, research project, or otherwise) that you
 * acknowledge this fact somewhere in the documentation, research report,
 * etc...  If you like PCCTS and have developed a nice tool with the
 * output, please mention that you developed it using PCCTS.  In
 * addition, we ask that this header remain intact in our source code.
 * As long as these guidelines are kept, we expect to continue enhancing
 * this system and expect to make other tools available as they are
 * completed.
 *
 * ANTLR 1.33MR10
 *
 */

#include <stdio.h>

#include "pcctscfg.h"

#include "set.h"
#include "syn.h"
#include "hash.h"
#include "generic.h"
#include "dlgdef.h"
#include <ctype.h>

#ifdef __USE_PROTOS
void dumppred(Predicate *);
#else
void dumppred();
#endif

/*
  Try to determine whether predicate "first" is true for
    all cases where "second" is true.  Comparison takes place
    without regard to context.
  Assumes that predicate symbols have been expanded.
  Assumes that there are no NAND or NOR nodes

*/

#ifdef __USE_PROTOS
int MR_secondPredicateUnreachable(Predicate *first,Predicate *second)
#else
int MR_secondPredicateUnreachable(first,second)
  Predicate     *first;
  Predicate     *second;
#endif
{
  Predicate     *f;
  Predicate     *s;

  if (first == NULL) {
    return 1;
  } else if (second == NULL) {
    return 0;
  } else if (first->down == NULL && second->down == NULL) {
    if (first->source == second->source &&
        first->inverted == second->inverted) {
      return 1; /* look identical - will never reach alt2 */
    } else {
      return 0; /* look different */
    };
  } else if (first->down == NULL && second->down != NULL) {

    if (second->expr == PRED_AND_LIST) {

      /* unreachable if first covers any child of second */

      for (s=second->down; s != NULL; s=s->right) {
        if (MR_secondPredicateUnreachable(first,s)) {
          return 1;
        };
      };
      return 0;
    } else if (second->expr == PRED_OR_LIST) {

      /* unreachable if first covers every child of second */

      for (s=second->down; s != NULL; s=s->right) {
        if (!MR_secondPredicateUnreachable(first,s)) {
          return 0;
        };
      };
      return 1;
    } else {
      require (0,"Illegal pred->expr");
      return 0; /* MR20 Make compiler happy */
    };
  } else if (first->down != NULL && second->down == NULL) {
    if (first->expr == PRED_AND_LIST) {

      /* unreachable if every child of first covers second */

      for (f=first->down; f != NULL; f=f->right) {
        if (!MR_secondPredicateUnreachable(f,second)) {
          return 0;
        };
      };
      return 1;
    } else if (first->expr == PRED_OR_LIST) {

      /* unreachable if any child of first covers second */

      for (f=first->down; f != NULL; f=f->right) {
        if (MR_secondPredicateUnreachable(f,second)) {
          return 1;
        };
      };
      return 0;
    } else {
      require (0,"Illegal predicate->expr");
      return 0; /* MR20 Make compiler happy */
    };
  } else {

    if (first->expr == PRED_AND_LIST && second->expr == PRED_AND_LIST) {

      /* unreachable if each child of first covers at least one child of second */

      for (f=first->down; f != NULL ; f=f->right) {
        for (s=second->down; s != NULL ; s=s->right) {
          if (MR_secondPredicateUnreachable(f,s)) goto A_next_f;
        };
        return 0;
A_next_f:
        continue;
      };
      return 1;

    } else if (first->expr == PRED_AND_LIST && second->expr == PRED_OR_LIST) {

      /* unreachable if each child of first covers ALL of second's children */

      for (f=first->down; f != NULL ; f=f->right) {
        for (s=second->down; s != NULL ; s=s->right) {
          if (!MR_secondPredicateUnreachable(f,s)) return 0;
        };
      };
      return 1;

    } else if (first->expr == PRED_OR_LIST && second->expr == PRED_AND_LIST) {

      /* unreachable if any child of second is covered by any child of first */

      for (f=first->down; f != NULL ; f=f->right) {
        for (s=second->down; s != NULL ; s=s->right) {
          if (MR_secondPredicateUnreachable(f,s)) return 1;
        };
      };
      return 0;

    } else if (first->expr == PRED_OR_LIST && second->expr == PRED_OR_LIST) {

      /* unreachable if every child of second is covered by some child of first */

      for (f=first->down; f != NULL ; f=f->right) {
        for (s=second->down; s != NULL ; s=s->right) {
          if (MR_secondPredicateUnreachable(f,s)) goto B_next_f;
        };
        return 0;
B_next_f:
       continue;
      };
      return 1;

    } else {
      require (0,"Illegal predicate->expr");
      return 0; /* MR20 Make compiler happy */
    };
  };
  return 0; /* MR20 MSVC 5.0 complains about missing return statement */
}

#ifdef __USE_PROTOS
void MR_xxxIndent(FILE *f,int depth)
#else
void MR_xxxIndent(f,depth)
  FILE  *f;
  int   depth;
#endif
{
  int   i;

  for (i=0; i<depth ; i++) {
    fprintf(f,"  ");
  };
}

#ifdef __USE_PROTOS
void MR_stderrIndent(int depth)
#else
void MR_stderrIndent(depth)
  int   depth;
#endif
{
  MR_xxxIndent(stderr,depth);
}

#ifdef __USE_PROTOS
void MR_outputIndent(int depth)
#else
void MR_outputIndent(depth)
  int   depth;
#endif
{
  MR_xxxIndent(output,depth);
}

#ifdef __USE_PROTOS
void MR_set_reuse(set *s)
#else
void MR_set_reuse(s)
  set   *s;
#endif
{
  set_free(*s);
  *s=empty;
}

#ifdef __USE_PROTOS
void MR_dumpPredRuleRefStack(FILE *iounit,int indent)
#else
void MR_dumpPredRuleRefStack(iounit,indent)
  FILE  *iounit;
  int   indent;
#endif
{
    int             i;
    int             j;
    int             count=MR_PredRuleRefStack.count;
    RuleRefNode     *rrn=NULL;
    Junction        *lastOne;

    if (count == 0) {
      fprintf(iounit,"empty\n");
      return;
    };
    for (i=0; i < count; i++) {
      rrn=(RuleRefNode *) MR_PredRuleRefStack.data[i];
      for (j=0; j<indent; j++) fprintf(iounit," ");
      fprintf(iounit,"#%-2d in rule %s (line %d %s) to rule %s\n",
            i,rrn->rname,rrn->line,FileStr[rrn->file],rrn->text);
    };
    lastOne=MR_ruleReferenced(rrn);
    if (lastOne != NULL) {
      for (j=0; j<indent; j++) fprintf(iounit," ");
      fprintf(iounit,"#%-2d in rule %s (line %d %s)\n",
        count,lastOne->rname,lastOne->line,FileStr[lastOne->file]);
    };
}

#ifdef __USE_PROTOS
void MR_dumpTreeF(FILE *f,int depth,Tree *tree,int across)
#else
void MR_dumpTreeF(f,depth,tree,across)
  FILE  *f;
  Tree  *tree;
  int   depth;
  int   across;
#endif
{
    int     newAcross=across;

	if (tree == NULL ) return;
	if (tree->down != NULL ) {
      fprintf(output,"\n");
      MR_outputIndent(depth);
      fprintf(output, "(root =");
    };
	if (tree->token == ALT ) {
      fprintf(output," %-16s","Alt");
	} else if (tree->token==EpToken ) {
      fprintf(output,"(%d)%13s",tree->v.rk," ");
	} else {
      fprintf(output," %-16s",TerminalString(tree->token));
    };
    if (tree->down != NULL) {
      fprintf(output,"\n");
      MR_outputIndent(depth+1);
      MR_dumpTreeF(f,depth+1,tree->down,1);
      newAcross=0;
      fprintf(output,"\n");
      MR_outputIndent(depth);
      fprintf(output,")");
    };
    if (newAcross > 3) {
      fprintf(output,"\n");
      MR_outputIndent(depth);
      newAcross=0;
    };
    MR_dumpTreeF(f,depth,tree->right,newAcross+1);
}

#ifdef __USE_PROTOS
void MR_dumpTreeX(int depth,Tree *tree,int across)
#else
void MR_dumpTreeX(depth,tree,across)
  Tree  *tree;
  int   depth;
  int   across;
#endif
{
  MR_dumpTreeF(output,depth,tree,across);
}

#ifdef __USE_PROTOS
void MR_dumpTokenSet(FILE *f,int depth,set s)
#else
void MR_dumpTokenSet(f,depth,s)
  FILE  *f;
  int   depth;
  set   s;
#endif
{
    int     i;
    int     j;

    unsigned  *pdq;

    if (set_nil(s)) {
      fprintf(f,"\n");
      MR_xxxIndent(f,depth+1);
      fprintf(f,"nil\n");
      return;
    };

    pdq=set_pdq(s);
    require(pdq != NULL,"set_pdq failed");
    i=0;
    for (i=0 ; ; i=i+4) {
      fprintf(f,"\n");
      MR_xxxIndent(f,depth+1);
      for (j=0; j < 4 ; j++) {
        if (pdq[i+j] == nil) break;
        fprintf(f," %-16s",TerminalString(pdq[i+j]));
      };
      if (pdq[i+j] == nil) break;
    };
    fprintf(f,"\n");
    free( (char *) pdq);
}

#ifdef __USE_PROTOS
void MR_dumpPred1(int depth,Predicate *p,int withContext)
#else
void MR_dumpPred1(depth,p,withContext)
  int           depth;
  Predicate     *p;
  int           withContext;
#endif
{
  unsigned      k;

  if (p == NULL) {
    MR_outputIndent(depth);
    fprintf(output,"The predicate is empty (or always true)\n\n");
    return;
  };
  if (p->down != NULL) {
    MR_outputIndent(depth);
    if (p->inverted) {

        /* MR14a Left out print expression in fprintf
                 Reported by Manuel Kessler ([e-mail])
        */

      if (p->expr == PRED_AND_LIST) fprintf(output,"%s NAND (not AND) expr\n\n",p->expr);
      if (p->expr == PRED_OR_LIST) fprintf(output,"%s NOR (not OR) expr\n\n",p->expr);
    } else {
      fprintf(output,"%s expr\n\n",p->expr);
    };
  } else {
    MR_outputIndent(depth);
    fprintf(output,"pred %s <<%s>>?\n",
            (p->inverted ? " *not*" : ""),
            (p->expr == NULL ? "null expr" : p->expr));
    MR_outputIndent(depth+1);
    fprintf(output,"              ");
    fprintf(output,"  depth=k=%d",p->k);
    if (p->source != NULL && p->source->guardpred) {
      fprintf(output,"  (\"=>\" guard)");
    }
    if (p->source != NULL && p->source->ampersandPred != NULL) {
      fprintf(output,"  (\"&&\" guard)");
    };
    k=set_int(p->completionSet);
    if (k != nil) {
      fprintf(output," Incomplete Set at k=%d !",k);
    };
    k=set_int(p->completionTree);
    if (k != nil) {
      fprintf(output," Incomplete Tree at k=%d !",k);
    };
    if (p->source != NULL) {
      fprintf(output,"  rule %s  line %d  %s",
                    p->source->rname,p->source->line,FileStr[p->source->file]);
    };
    fprintf(output,"\n");
    if (withContext &&
            (HoistPredicateContext ||
             ! set_nil(p->scontext[1]) ||
             p->tcontext != NULL)) {
      if (p->k == 1) {
        MR_outputIndent(depth+1);
        fprintf(output,"set context: ");
        MR_dumpTokenSet(output,depth+1,p->scontext[1]);
      }
      if (p->k != 1) {
        MR_outputIndent(depth+1);
        fprintf(output,"tree context:");
        if (p->tcontext == NULL) {
          fprintf(output," null");
        } else {
          MR_dumpTreeX(depth+2,p->tcontext,0);
        };
        fprintf(output,"\n");
      };
    };
    fprintf(output,"\n");
  };
  if (p->down != NULL) {
    MR_dumpPred1(depth+1,p->down,withContext);
  };
  if (p->right != NULL) {
    MR_dumpPred1(depth,p->right,withContext);
  };
}

#ifdef __USE_PROTOS
void MR_dumpPred(Predicate *p,int withContext)
#else
void MR_dumpPred(p,withContext)
  Predicate     *p;
  int           withContext;
#endif
{
  MR_dumpPred1(0,p,withContext);
}

#ifdef __USE_PROTOS
Tree * MR_make_tree_from_set(set s)
#else
Tree * MR_make_tree_from_set(s)
  set   s;
#endif
{
  Tree  *t=NULL;
  Tree  *node;
  Tree  **tp=&t;
  int   i;

  unsigned *pdq=set_pdq(s);

  if (pdq != NULL) {
    for (i=0 ; pdq[i] != nil ; i++) {
      node=tnode( (int) pdq[i]);
      *tp=node;
      tp=&(node->right);
    };