mrhoist.c revision 4fd606d1f5abe38e1f42c38de1d2e895166bd0f4
/*
*
* 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
#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
#else
#endif
{
Predicate *f;
Predicate *s;
return 1;
return 0;
return 1; /* look identical - will never reach alt2 */
} else {
return 0; /* look different */
};
/* unreachable if first covers any child of second */
if (MR_secondPredicateUnreachable(first,s)) {
return 1;
};
};
return 0;
/* unreachable if first covers every child of second */
if (!MR_secondPredicateUnreachable(first,s)) {
return 0;
};
};
return 1;
} else {
require (0,"Illegal pred->expr");
return 0; /* MR20 Make compiler happy */
};
/* unreachable if every child of first covers second */
if (!MR_secondPredicateUnreachable(f,second)) {
return 0;
};
};
return 1;
/* unreachable if any child of first covers second */
if (MR_secondPredicateUnreachable(f,second)) {
return 1;
};
};
return 0;
} else {
require (0,"Illegal predicate->expr");
return 0; /* MR20 Make compiler happy */
};
} else {
/* unreachable if each child of first covers at least one child of second */
if (MR_secondPredicateUnreachable(f,s)) goto A_next_f;
};
return 0;
continue;
};
return 1;
/* unreachable if each child of first covers ALL of second's children */
if (!MR_secondPredicateUnreachable(f,s)) return 0;
};
};
return 1;
/* unreachable if any child of second is covered by any child of first */
if (MR_secondPredicateUnreachable(f,s)) return 1;
};
};
return 0;
/* unreachable if every child of second is covered by some child of first */
if (MR_secondPredicateUnreachable(f,s)) goto B_next_f;
};
return 0;
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
#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
{
}
#ifdef __USE_PROTOS
void MR_outputIndent(int depth)
#else
void MR_outputIndent(depth)
int depth;
#endif
{
}
#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
#else
int indent;
#endif
{
int i;
int j;
if (count == 0) {
return;
};
for (i=0; i < count; i++) {
};
};
}
#ifdef __USE_PROTOS
#else
FILE *f;
int depth;
int across;
#endif
{
};
} else {
};
newAcross=0;
};
if (newAcross > 3) {
newAcross=0;
};
}
#ifdef __USE_PROTOS
#else
int depth;
int across;
#endif
{
}
#ifdef __USE_PROTOS
#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");
fprintf(f,"nil\n");
return;
};
i=0;
for (i=0 ; ; i=i+4) {
fprintf(f,"\n");
for (j=0; j < 4 ; j++) {
};
};
fprintf(f,"\n");
}
#ifdef __USE_PROTOS
#else
int depth;
Predicate *p;
int withContext;
#endif
{
unsigned k;
if (p == NULL) {
return;
};
if (p->inverted) {
/* MR14a Left out print expression in fprintf
Reported by Manuel Kessler (mlkessle@cip.physik.uni-wuerzburg.de)
*/
} else {
};
} else {
}
};
k=set_int(p->completionSet);
if (k != nil) {
};
k=set_int(p->completionTree);
if (k != nil) {
};
};
if (withContext &&
if (p->k == 1) {
}
if (p->k != 1) {
} else {
};
};
};
};
};
};
}
#ifdef __USE_PROTOS
#else
void MR_dumpPred(p,withContext)
Predicate *p;
int withContext;
#endif
{
MR_dumpPred1(0,p,withContext);
}
#ifdef __USE_PROTOS
#else
set s;
#endif
{
int i;
};
};
return t;
}
#ifdef __USE_PROTOS
#else
void MR_check_pred_too_long(p,completion)
Predicate *p;
#endif
{
if (p != NULL &&
! p->source->predTooLong) {
if ( !set_nil(completion)) {
warnFL("It is unusual (but ok) for a semantic predicate to test context past the end of its own rule",
};
};
}
#ifdef __USE_PROTOS
#else
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) &
}
#ifdef __USE_PROTOS
#else
Node * MR_advance(n)
Node *n;
#endif
{
switch (n->ntype) {
default: return NULL;
};
return NULL; /* MSVC 5.0 complains about missing return statement */
}
#ifdef __USE_PROTOS
#else
Junction * MR_find_endRule(n)
Node *n;
#endif
{
break;
};
};
}
/*
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
#else
Tree *l;
Tree *r;
#endif
{
Tree *p;
Tree *q;
};
};
};
};
};
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
#else
Tree *MR_computeTreeAND(l,r)
Tree *l;
Tree *r;
#endif
{
Tree *p;
Tree *q;
/**** require(p->token != EpToken,"MR_computeTreeAND: p->EpToken unexpected\n"); ****/
};
/**** require(q->token != EpToken,"MR_computeTreeAND: q->EpToken unexpected\n"); ****/
};
};
};
};
return result;
}
#ifdef __USE_PROTOS
#else
void MR_union_plain_sets1(p,theUnion)
Predicate *p;
#endif
{
if (p == NULL) return;
return;
}
#ifdef __USE_PROTOS
#else
Predicate *p;
#endif
{
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
#else
Predicate *p;
#endif
{
Predicate *q;
Tree *t;
/* 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) {
t=NULL;
};
/* 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;
**
** l=p->down;
**
**/* l1 and r1 should already be in "canonical" format */
**
** l1=MR_compute_pred_tree(l);
** r1=MR_compute_pred_tree(r);
** };
**
**/* result from computeTreeAND should be in "canonical" format */
**
**
**/* result of MR_computeTreeAND should be in "canonical" format */
**
** return result;
** };
#endif
if (p->k == 1) {
} else {
};
return result;
}
#ifdef __USE_PROTOS
#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) {
};
}
/* this computes the OR of all the contexts */
#ifdef __USE_PROTOS
#else
Predicate *p;
#endif
{
Predicate *q;
if (p->expr == PRED_OR_LIST ||
/* remember: r1: (A)? => <<p>>? r2; */
/* r2: (B)? => <<q>>? r3; */
set t;
t=empty;
t=MR_compute_pred_set(q);
set_free(t);
};
return result;
} else if (p->k > 1) {
return empty;
} else {
};
}
#ifdef __USE_PROTOS
#else
int ck;
Junction *j;
#endif
{
Junction *p;
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;
};
}
/* does NOT return canonical tree */
#ifdef __USE_PROTOS
#else
Tree *t;
#endif
{
/* I think ALT can be ignored as a special case */
return t;
} else {
Tree *u;
u=MR_remove_epsilon_from_tree(t->right);
Tfree(t);
return u;
};
}
#ifdef __USE_PROTOS
#else
int predDepth;
#endif
{
int i;
set b;
int k2;
return;
};
"RuleRefStack and RuleBlkWithHaltStack not same size");
"RuleBlkWithHalt has no halt set");
if (MR_RuleBlkWithHalt != NULL) {
};
b=empty;
while ( !set_nil(*incomplete) ) {
set_orin(tokensUsed,b);
set_free(b);
};
};
if (MR_RuleBlkWithHalt != NULL) {
};
}
#ifdef __USE_PROTOS
#else
int predDepth;
Tree **t;
#endif
{
int i;
Tree *u;
unsigned k2;
int saveConstrainSearch;
return;
};
"RuleRefStack and RuleBlkWithHaltStack not same size");
"RuleBlkWithHalt has no halt set");
if (MR_RuleBlkWithHalt != NULL) {
};
while ( !set_nil(*incomplete) ) {
u = NULL;
/* any subtrees missing k2 tokens, add u onto end */
Tfree(u);
}
};
if (MR_RuleBlkWithHalt != NULL) {
};
}
#ifdef __USE_PROTOS
#else
int predDepth;
#endif
{
};
}
#ifdef __USE_PROTOS
#else
Junction *j;
#endif
{
/* don't want to follow p2 to the next alternative of this rule */
/* insert a generic node with null p2 if necessary */
/* however FIRST requires a junction */
thisAlt=j;
} else {
};
};
return thisAlt;
}
#ifdef __USE_PROTOS
#else
{
#endif
Tree *b;
Tree *s;
int bcount=0;
int scount=0;
"MR_tree_equ: small: ALT node has siblings");
};
"MR_tree_equ: big: ALT node has siblings");
};
scount++;
};
bcount++;
};
};
};
return 0;
continue;
};
return 1;
}
/* this does not compare sources - only contexts ! */
#ifdef __USE_PROTOS
#else
int MR_identicalContext(p,q)
Predicate *p;
Predicate *q;
#endif
{
if (p->k != q->k) return 0;
"tcontext inconsistent");
if (p->k == 1) {
} else {
};
}
#ifdef __USE_PROTOS
void MR_reportSetSuppression(int predDepth,
#else
int predDepth;
Predicate *p;
#endif
{
if (InfoP) {
fprintf(output,"The alt without the predicate includes all cases where the predicate is false.\n\n");
} else {
};
if (predDepth == 1) {
};
};
}
#ifdef __USE_PROTOS
#else
int predDepth;
#endif
{
if (! InfoP) return;
} else {
};
if (predDepth == 1) {
};
if (predDepth == 1) {
};
}
/* don't use Pass3 by itself unless you know that inverted is not important */
#ifdef __USE_PROTOS
#else
Predicate *p;
#endif
{
Predicate *q;
if (p->redundant) {
q=p->right;
predicate_free(p);
return q;
};
if (p->expr == PRED_AND_LIST ||
p->expr == PRED_OR_LIST) {
q=p->right;
predicate_free(p);
return q;
};
q=p->down;
return q;
};
};
return p;
}
#ifdef __USE_PROTOS
void MR_removeRedundantPredPass2(Predicate *p)
#else
void MR_removeRedundantPredPass2(p)
Predicate *p;
#endif
{
Predicate *q;
if (p == NULL) return;
if (p->expr == PRED_AND_LIST) {
if (q->isConst) {
if (q->constValue == 0) {
p->isConst=1;
p->constValue=0;
return;
} else {
q->redundant=1;
};
};
};
};
if (p->expr == PRED_OR_LIST) {
if (q->isConst) {
if (q->constValue == 0) {
q->redundant=1;
} else {
p->isConst=1;
p->constValue=1;
return;
};
};
};
};
return;
}
#if 0
| (B)? => <<r>>? sub2 /* 2 */
sub1 : (A)? => <<q>>? A B /* 3 */
| B /* 4 - suppresses line 2 */
;
#endif
#ifdef __USE_PROTOS
#else
int *changed;
#endif
{
} else {
set t;
if (pred->k == 1) {
if (*changed == 0 &&
*changed=1;
};
if (set_nil(t)) {
};
};
};
}
#ifdef __USE_PROTOS
#else
void MR_orin_plainSet(p,plainSet)
Predicate *p;
#endif
{
if (p == NULL) return;
}
#ifdef __USE_PROTOS
#else
#endif
{
Junction *p;
int nAlts=0;
int *matchList;
int i;
int j;
int m;
int predDepth;
int changed;
if (PRED_SUPPRESS == NULL) {
};
/* this section just counts the number of "interesting" alternatives */
/* in order to allocate arrays */
/* ignore empty alts */
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 ?
*/
nAlts--;
};
/* 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;
/* ignore empty alts */
jList[i]=MR_junctionWithoutP2(p);
} else {
plainContext[i]=plainSet;
};
};
};
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 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;
/* 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.
*/
};
/* 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) {
for (j=0; j < nAlts; j++) {
if (j == i) continue;
matchList[i] |= 1;
predicate_free(predList[i]);
goto next_i;
};
}; /* end loop on j */
changed=0;
/* predicate_dup is only to give good error messages */
/* remember to do a predicate_free() */
if (changed) {
/* don't use Pass3 by itself unless you know that inverted is not important */
matchList[i] |= 1;
} else {
};
};
};
/*
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() */
if (changed) {
matchList[i] |= 1;
} else {
};
};
};
continue;
};
for (i=0 ; i< nAlts ; i++) {
continue;
} else if ( (matchList[i] & 1) != 0) {
if (predList[i] != PRED_SUPPRESS) {
predicate_free(predList[i]);
};
continue;
};
/* make an OR list of predicates */
};
/* if just one pred, remove OR root */
root=p;
}
free ( (char *) plainContext);
return root;
}
#ifdef __USE_PROTOS
#else
Predicate *p;
int *allHaveContext;
int *noneHaveContext;
#endif
{
if (p == NULL) return;
if (p->expr != PRED_AND_LIST &&
p->expr != PRED_OR_LIST) {
*noneHaveContext=0;
} else {
*allHaveContext=0;
};
};
}
#ifdef __USE_PROTOS
#else
void *dataPointer;
#endif
{
void **newStack;
int newSize;
int i;
};
};
}
#ifdef __USE_PROTOS
#else
void * MR_pointerStackPop(ps)
#endif
{
void *dataPointer;
return dataPointer;
}
#ifdef __USE_PROTOS
#else
void * MR_pointerStackTop(ps)
#endif
{
}
#ifdef __USE_PROTOS
#else
void MR_pointerStackReset(ps)
#endif
{
int i;
};
};
}
#ifdef __USE_PROTOS
#else
char *name;
#endif
{
RuleEntry *q;
if ( q == NULL ) {
return NULL;
} else {
};
}
#ifdef __USE_PROTOS
#else
#endif
{
}
#ifdef __USE_PROTOS
#else
#endif
{
return;
return;
} else {
/* predicate->invert can be set only in the predEntry predicates */
/* thus they are only visible after the predEntry predicates have been "unfolded" */
int sameInvert=1 &
/* identical predicates */
||
) {
} 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 */
myParent->constValue=0;
||
) {
} else {
require (0,"MR_comparePredLeaves: not both PRED_LIST");
};
};
}; /* end same predEntry with opposite invert sense */
};
return;
};
}
#ifdef __USE_PROTOS
#else
#endif
{
return;
};
} else {
};
};
}
/* pretty much ignores things with the inverted bit set */
#ifdef __USE_PROTOS
#else
Predicate *p;
#endif
{
if (p->expr == PRED_OR_LIST
|| p->expr == PRED_AND_LIST) {
char *PRED_XXX_LIST=p->expr;
predicate_free(p);
return child;
};
/* make a single list of all children and grandchildren */
} else {
};
};
};
return p;
} else {
return p;
};
}
static char *alwaysFalseWarning=NULL;
#ifdef __USE_PROTOS
#else
Predicate *p;
#endif
{
if (p->isConst) {
if (p->constValue == 1) {
predicate_free(p);
return NULL;
} else {
if (InfoP && !p->conflictReported) {
p->conflictReported=1;
};
if (alwaysFalseWarning != CurRule) {
if (InfoP) {
- see output file for more information",CurRule));
} else {
- use \"-info p\" for more information",CurRule));
};
};
};
};
return p;
}
#ifdef __USE_PROTOS
int MR_countPredNodes(Predicate *p)
#else
int MR_countPredNodes(p)
Predicate *p;
#endif
{
if (p == NULL) return 0;
}
#ifdef __USE_PROTOS
#else
Predicate *p;
int skipPass3;
#endif
{
int countBefore;
int countAfter;
do {
MR_simplifyInverted(p,0);
p=MR_predFlatten(p);
if (! skipPass3) {
p=checkPredicateConflict(p);
};
} while (countBefore != countAfter);
return p;
}
#ifdef __USE_PROTOS
#else
Predicate *p;
#endif
{
return MR_predSimplifyALLX(p,0);
}
#ifdef __USE_PROTOS
void MR_releaseResourcesUsedInRule(Node *n)
#else
void MR_releaseResourcesUsedInRule(n)
Node *n;
#endif
{
Junction *j;
int i;
if (n == NULL) return;
j=(Junction *) n;
predicate_free(j->predicate);
};
for (i=0; i< CLL_k; i++) {
};
};
};
};
};
next=MR_advance(n);
}
#ifdef __USE_PROTOS
int MR_allPredLeaves(Predicate *p)
#else
int MR_allPredLeaves(p)
Predicate *p;
#endif
{
Predicate *q;
if (p == NULL) return 1;
};
return 1;
}
/* make sure it works for the last rule in a file */
#ifdef __USE_PROTOS
int MR_offsetFromRule(Node *n)
#else
int MR_offsetFromRule(n)
Node *n;
#endif
{
Junction *j;
int offset=(-1);
return offset;
};
} else {
if (offset == 0) return 0;
};
};
};
return offset;
}
#define ruleNameMax 50
static char ruleNameStatic1[ruleNameMax];
#ifdef __USE_PROTOS
char * MR_ruleNamePlusOffset(Node *n)
#else
char * MR_ruleNamePlusOffset(n)
Node *n;
#endif
{
int offset=MR_offsetFromRule(n);
if (offset < 0) {
} else {
};
return ruleNameStatic2;
}
#ifdef __USE_PROTOS
int MR_max_height_of_tree(Tree *t)
#else
int MR_max_height_of_tree(t)
Tree *t;
#endif
{
int h;
int height=0;
Tree *u;
if (t == NULL) return 0;
};
return height;
}
#ifdef __USE_PROTOS
#else
int MR_all_leaves_same_height(t,depth)
Tree *t;
int depth;
#endif
{
if (t == NULL) {
return (depth==0);
};
if (depth == 0) {
return 0;
} else {
return 0;
};
return 1;
} else {
};
};
}
#ifdef __USE_PROTOS
#else
int ck;
#endif
{
} else {
if (ck > 1) {
} else {
};
};
}
#ifdef __USE_PROTOS
#else
int MR_comparePredicates(a,b)
Predicate *a;
Predicate *b;
#endif
{
Predicate *p;
Predicate *q;
if (a == b) return 1;
/* predicate->invert can be set only in the predEntry predicates */
/* thus they are only visible after the predEntry predicates have been "unfolded" */
if (MR_identicalContext(a,b)) {
return 1;
};
};
return 0;
};
if (MR_comparePredicates(p,q)) goto NEXT_P;
};
return 0;
continue;
};
return 1;
}
/*
* action->inverted can be set only when a predicate symbol appears in
* a rule: "rule : <<!XXX>>? X". It cannot be set under any
* other circumstances. In particular it cannot be set by
* "#pred NotA !A" or by "#pred Nota <<!A>>?". The first case
* creates a predEntry and the predicate expression of that predEntry
* has inverted set. In the second case, the code for handling "!"
* is only present in buildAction, which is not called by the #pred
* semantic routines, only when a <<...>>? is recognized as part of
* a rule definition.
*
* predicate->inverted can only be set by a predicate created by a #pred
* expression, such as "#pred NotA !A" or "#pred NotXY ! (X && Y) or
* "#pred XbarY !(X && Y)". In particular, it cannot be set by any
* predicate expression occurring under any other circumstances.
* The #pred predicate expresssions are stored with in predEntry->pred
* and do not normally appear anywhere else until the predicates are
* "unfolded" in order to recognize redundancies, conflicts, and
* tautologies.
*
* The unfold routine expands all references to #pred expressions.
*
* The simplifyInvert goes through and propagates the invert bit so that
* all OR and AND nodes are un-inverted.
*
* Note that !(A and B) => (!A or !B)
* !(A or B) => (!A and !B)
*
* MR_unfold() is called to expand predicate symbols by replacing predicates
* that reference predicate entries with the copies of the predicate entries.
* Each reference receives a duplicate of the original. This is necessary
* because the next phase involves simplification and removal of redundant
* predicate nodes. Anyway, the point I'm making is that predicate->invert
* should not be set in any predicate until it has been expanded.
*
* This is a recursive structure, but there is no need for "recursive expansion"
* by which I mean a predicate symbol refers to other predicate symbols which
* must also be expanded.
*
* Recursive expansion is *not* performed by this routine because it is not
* necessary. Expansion of references is performed by predPrimary when
* a new predicate symbol is created by referring to others in the pred expr.
*/
#ifdef __USE_PROTOS
#else
#endif
{
; /* do nothing */ /* a reference to a literal #pred (perhaps with "!" */
} else {
};
};
/*** result=MR_unfold(result); *** not necessary */ /* recursive expansion */
return result;
};
} else {
; /* do nothing */ /* an inline literal predicate */
};
} else {
};
return pred;
}
/* this should be called immediately after MR_unfold() and
at no other times
*/
#ifdef __USE_PROTOS
#else
int inverted;
#endif
{
int newInverted;
} else {
if (newInverted != 0) {
} else {
};
};
};
}
/* only remove it from AND and OR nodes, not leaves */
#ifdef __USE_PROTOS
void MR_clearPredEntry(Predicate *p)
#else
void MR_clearPredEntry(p)
Predicate *p;
#endif
{
if (p == NULL) return;
MR_clearPredEntry(p->down);
MR_clearPredEntry(p->right);
}
#ifdef __USE_PROTOS
void MR_orphanRules(FILE *f)
#else
void MR_orphanRules(f)
FILE *f;
#endif
{
set a;
Junction *p;
unsigned e;
a=empty;
if (! InfoO) return;
}
}
if (set_deg(a) > 1) {
fprintf(f,"note: Start rules: {");
e=set_int(a);
};
fprintf(f," }\n");
};
set_free( a );
}
/* merge (X Y) and (X) to create (X) */
static int *mergeChain;
#ifdef __USE_PROTOS
#else
Tree *t;
int chain[];
#endif
{
if (chain[0] == 0) {
Tfree(t);
return MR_merge_tree_contexts_client(u,&chain[0]);
}
};
return t;
}
#ifdef __USE_PROTOS
#else
void MR_iterateOverTreeContexts(t,chain)
Tree *t;
int chain[];
#endif
{
if (t == NULL) return;
} else {
};
chain[0]=0;
}
#ifdef __USE_PROTOS
#else
Tree *t;
#endif
{
int h=MR_max_height_of_tree(t);
mergeTree=t;
t=tshrink(t);
t=tflatten(t);
t=tleft_factor(t);
free ( (char *) mergeChain);
return t;
}
#ifdef __USE_PROTOS
#else
Predicate *p;
#endif
{
Tree *t;
return t;
}
#ifdef __USE_PROTOS
#else
#endif
{
Junction *j;
if (!MRhoisting) return;
/* it doesn't really matter whether the predicate has
depth k=1 or k>1 because we're not really looking
at the predicate itself, just the stuff "behind"
the predicate.
*/
/* shouldn't have to worry about REACHing off the end
of the rule containing the predicate because the
Rule->end->halt should have been set already by the
the code which handles RuleRef nodes.
We don't want to REACH off the end of the rule because
this would give the "global" follow context rather than
the "local" context.
r1a : (A)? => <<p>>? r2 (A|B)
r1b : (A)? => <<p>>? r2 (A|C)
r2 : ();
For r1a we want follow of predicate = {A B}
we want plainSet = {B}
For r1b we want follow of predicate = {A C}
we want plainSet = {C}
*/
workPred->k=1;
if (pred->k == 1) {
} else {
}
}
/*******************************************************************************/
static Tree * suppressTree;
static int * suppressChain; /* element 0 not used */
static set * suppressSets;
static Node * suppressNode;
static int suppressChainLength;
int MR_SuppressSearch=0;
static int suppressSucceeded;
static Predicate * suppressPredicate;
#ifdef __USE_PROTOS
int MR_isChain(Tree *t)
#else
int MR_isChain(t)
Tree *t;
#endif
{
Tree *u;
}
return 1;
}
#ifdef __USE_PROTOS
#else
int tokensInChain[];
#endif
{
int i;
int save_ConstrainSearch;
Tree *t;
suppressSucceeded=0; /* volatile */
if (suppressSets == NULL) {
};
for (suppressChainLength=1;
suppressChainLength++) {};
for (i=1 ; i <= suppressChainLength ; i++) {
set_clr(suppressSets[i]);
set_orel( (unsigned) tokensInChain[i],
&suppressSets[i]);
};
t=NULL;
/*** constrain = &(fset[1]); ***/
Tfree(t);
"MR_suppressK_client: MR_BackTraceStack.count != 0");
return suppressSucceeded;
}
#ifdef __USE_PROTOS
#else
Tree *t;
int chain[];
#endif
{
Tfree(t);
chain[0]=0;
return u;
};
} else {
if (suppressSucceeded) {
Tfree(t);
chain[0]=0;
return u;
};
};
chain[0]=0;
return t;
}
/* @@@ */
#ifdef __USE_PROTOS
#else
Predicate * MR_suppressK(j,p)
Node *j;
Predicate *p;
#endif
{
int guardPred=0;
int ampersandPred=0;
if (! MRhoistingk) {
return p;
}
if (! MRhoisting) return p;
if (CLL_k == 1) return p;
if (suppressChain == NULL) {
}
} else {
nodePrime=j;
};
result=p;
goto EXIT;
};
if (p->k == 1) {
result=p;
goto EXIT;
};
}
suppressTree=p->tcontext;
if (guardPred || ampersandPred) {
predicate_free(p);
goto EXIT;
};
} else {
if (MR_isChain(p->tcontext)) {
predicate_free(p);
goto EXIT;
};
}
}
result=p;
EXIT:
return result;
}
#ifdef __USE_PROTOS
void MR_suppressSearchReport(void)
#else
void MR_suppressSearchReport()
#endif
{
int i;
Node *p;
int depth;
/* number of tokens in back trace stack matches length of chain */
depth=0;
for (i=0; i < MR_BackTraceStack.count ; i++) {
};
/* token codes match chain */
depth=0;
for (i=0; i < MR_BackTraceStack.count ; i++) {
depth++;
"MR_suppressSearchReport: no match to #token in chain");
} else {
"MR_suppressSearchReport: no match to #token set in chain");
};
};
/* have a match - now remove it from the predicate */
if (suppressSucceeded) {
for (i=1; i <= suppressChainLength; i++) {
};
for (i=0; i < MR_BackTraceStack.count ; i++) {
};
}
}
#ifdef __USE_PROTOS
void MR_markCompromisedRule(Node *n)
#else
void MR_markCompromisedRule(n)
Node *n;
#endif
{
RuleEntry *q;
Junction *j;
mark=n;
j=(Junction *)n;
switch (j->jtype) {
case aOptBlk:
case aLoopBlk:
case RuleBlk:
case EndRule:
case aPlusBlk:
case aLoopBegin:
mark=n;
break;
default:
break;
};
}
}
#ifdef __USE_PROTOS
void MR_alphaBetaTraceReport(void)
#else
void MR_alphaBetaTraceReport()
#endif
{
int i;
if (! AlphaBetaTrace) return;
for (i=0; i < MR_BackTraceStack.count ; i++) {
};
};
}
#ifdef __USE_PROTOS
void MR_dumpRuleSet(set s)
#else
void MR_dumpRuleSet(s)
set s;
#endif
{
unsigned *cursor;
} else {
/**** if (cursor != origin) fprintf(stderr,","); ****/
};
};
}