X-Git-Url: https://pd.if.org/git/?p=pccts;a=blobdiff_plain;f=antlr%2Fpred.c;fp=antlr%2Fpred.c;h=0c327956833c8fe9f94a25c07cc58e9c4ba21ede;hp=0000000000000000000000000000000000000000;hb=4c1585478dbadc88148f5417d75d6f58b8042c82;hpb=129ce0f1c9d43c04ed8198ac184bce8d8be0042e

diff --git a/antlr/pred.c b/antlr/pred.c
new file mode 100755
index 0000000..0c32795
--- /dev/null
+++ b/antlr/pred.c
@@ -0,0 +1,607 @@
+/*
+ * pred.c -- source for predicate detection, manipulation
+ *
+ * $Id: pred.c,v 1.6 95/09/26 12:58:44 parrt Exp $
+ * $Revision: 1.6 $
+ *
+ * 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.33
+ * Terence Parr
+ * Parr Research Corporation
+ * with Purdue University and AHPCRC, University of Minnesota
+ * 1989-1995
+ */
+#include <stdio.h>
+#ifdef __cplusplus
+#ifndef __STDC__
+#define __STDC__
+#endif
+#endif
+#include "set.h"
+#include "syn.h"
+#include "hash.h"
+#include "generic.h"
+#include "dlgdef.h"
+#include <ctype.h>
+
+#ifdef __STDC__
+static void complete_context_sets(RuleRefNode *, Predicate *);
+static void complete_context_trees(RuleRefNode *, Predicate *);
+#else
+static void complete_context_sets();
+static void complete_context_trees();
+#endif
+
+static Predicate pred_empty = {
+	NULL,NULL,NULL,NULL,NULL,NULL,0,
+	{set_init,set_init},set_init
+};
+
+char *PRED_AND_LIST = "AND";
+char *PRED_OR_LIST = "OR";
+
+/*
+ * In C mode, return the largest constant integer found as the
+ * sole argument to LATEXT(i).
+ *
+ * In C++ mode, return the largest constant integer found as the
+ * sole argument to LT(i) given that the char before is nonalpha.
+ */
+static int
+#ifdef __STDC__
+predicateLookaheadDepth(ActionNode *a)
+#else
+predicateLookaheadDepth(a)
+ActionNode *a;
+#endif
+{
+	int max_k=0;
+
+	if ( GenCC )
+	{
+		/* scan for LT(i) */
+		int k = 0;
+		char *p = a->action;
+		while ( p!=NULL )
+		{
+			p = strstr(p, "LT(");
+			if ( p!=NULL )
+			{
+				if ( p>=a->action && !isalpha(*(p-1)) )
+				{
+					k = atoi(p+strlen("LT("));
+					if ( k>max_k ) max_k=k;
+				}
+				p += strlen("LT(");
+			}
+		}
+	}
+	else {
+		/* scan for LATEXT(i) */
+		int k = 0;
+		char *p = a->action;
+		while ( p!=NULL )
+		{
+			p = strstr(p, "LATEXT(");
+			if ( p!=NULL )
+			{
+				p += strlen("LATEXT(");
+				k = atoi(p);
+				if ( k>max_k ) max_k=k;
+			}
+		}
+	}
+
+	if ( max_k==0 )
+	{
+		if ( !a->frmwarned )
+		{
+			a->frmwarned = 1;
+			warnFL(eMsg1("predicate: %s missing, bad, or with i=0; assuming i=1",
+						 GenCC?"LT(i)":"LATEXT(i)"),
+				   FileStr[a->file], a->line);
+		}
+		max_k = 1;
+	}
+
+	return max_k;
+}
+
+/* Find all predicates in a block of alternatives.  DO NOT find predicates
+ * behind the block because that predicate could depend on things set in
+ * one of the nonoptional blocks
+ */
+Predicate *
+#ifdef __STDC__
+find_in_aSubBlk( Junction *alt )
+#else
+find_in_aSubBlk( alt )
+Junction *alt;
+#endif
+{
+	Predicate *a, *head=NULL, *tail, *root=NULL;
+	Junction *p = alt;
+
+	for (; p!=NULL; p=(Junction *)p->p2)
+	{
+		/* ignore empty alts */
+		if ( p->p1->ntype != nJunction ||
+			 ((Junction *)p->p1)->jtype != EndBlk )
+		{
+			a = find_predicates(p->p1);	/* get preds for this alt */
+			if ( a==NULL ) continue;
+
+			/* make an OR list of predicates */
+			if ( head==NULL )
+			{
+				root = new_pred();
+				root->expr = PRED_OR_LIST;
+				head = tail = a;
+				root->down = head;
+			}
+			else {
+				tail->right = a;
+				a->left = tail;
+				a->up = tail->up;
+				tail = a;
+			}
+		}
+	}
+
+	/* if just one pred, remove OR root */
+	if ( root!=NULL && root->down->right == NULL )
+	{
+		Predicate *d = root->down;
+		free(root);
+		return d;
+	}
+
+	return root;
+}
+
+Predicate *
+#ifdef __STDC__
+find_in_aOptBlk( Junction *alt )
+#else
+find_in_aOptBlk( alt )
+Junction *alt;
+#endif
+{
+	return find_in_aSubBlk( alt );
+}
+
+Predicate *
+#ifdef __STDC__
+find_in_aLoopBegin( Junction *alt )
+#else
+find_in_aLoopBegin( alt )
+Junction *alt;
+#endif
+{
+	return find_in_aSubBlk( (Junction *) alt->p1 );	/* get preds in alts */
+}
+
+Predicate *
+#ifdef __STDC__
+find_in_aPlusBlk( Junction *alt )
+#else
+find_in_aPlusBlk( alt )
+Junction *alt;
+#endif
+{
+	require(alt!=NULL&&alt->p2!=NULL, "invalid aPlusBlk");
+	return find_in_aSubBlk( alt );
+}
+
+/* Look for a predicate;
+ *
+ * Do not pass anything but Junction nodes; no Actions, Tokens, RuleRefs.
+ * This means that a "hoisting distance" of zero is the only distance
+ * allowable.  Init actions are ignored.
+ *
+ * WARNING:
+ *		Assumes no (..)? block after predicate for the moment.
+ *		Does not check to see if pred is in production that can generate
+ *			a sequence contained in the set of ambiguous tuples.
+ *
+ * Return the predicate found if any.
+ */
+Predicate *
+#ifdef __STDC__
+find_predicates( Node *alt )
+#else
+find_predicates( alt )
+Node *alt;
+#endif
+{
+#ifdef DBG_PRED
+	Junction *j;
+	RuleRefNode *r;
+	TokNode *t;
+#endif
+	Predicate *pred;
+
+	if ( alt==NULL ) return NULL;
+
+#ifdef DBG_PRED
+	switch ( alt->ntype )
+	{
+		case nJunction :
+			j = (Junction *) alt;
+			fprintf(stderr, "Junction(in %s)", j->rname);
+			switch ( j->jtype )
+			{
+				case aSubBlk :
+					fprintf(stderr,"aSubBlk\n");
+					break;
+				case aOptBlk :
+					fprintf(stderr,"aOptBlk\n");
+					break;
+				case aLoopBegin :
+					fprintf(stderr,"aLoopBeginBlk\n");
+					break;
+				case aLoopBlk :
+					fprintf(stderr,"aLoopBlk\n");
+					break;
+				case aPlusBlk :
+					fprintf(stderr,"aPlusBlk\n");
+					break;
+				case EndBlk :
+					fprintf(stderr,"EndBlk\n");
+					break;
+				case RuleBlk :
+					fprintf(stderr,"RuleBlk\n");
+					break;
+				case Generic :
+					fprintf(stderr,"Generic\n");
+					break;
+				case EndRule :
+					fprintf(stderr,"EndRule\n");
+					break;
+			}
+			break;
+		case nRuleRef :
+			r = (RuleRefNode *) alt;
+			fprintf(stderr, "RuleRef(in %s)\n", r->rname);
+			break;
+		case nToken :
+			t = (TokNode *) alt;
+			fprintf(stderr, "TokenNode(in %s)%s\n", t->rname, TokenString(t->token));
+			break;
+		case nAction :
+			fprintf(stderr, "Action\n");
+			break;
+	}
+#endif
+
+	switch ( alt->ntype )
+	{
+		case nJunction :
+		{
+			Predicate *a, *b;
+			Junction *p = (Junction *) alt;	
+
+			/* lock nodes */
+			if ( p->jtype==aLoopBlk || p->jtype==RuleBlk ||
+				 p->jtype==aPlusBlk || p->jtype==EndRule )
+			{
+				require(p->pred_lock!=NULL, "rJunc: lock array is NULL");
+				if ( p->pred_lock[1] )
+				{
+					return NULL;
+				}
+				p->pred_lock[1] = TRUE;
+			}
+
+			switch ( p->jtype )
+			{
+				case aSubBlk :
+					a = find_in_aSubBlk(p);
+					return a;	/* nothing is visible past this guy */
+				case aOptBlk :
+					a = find_in_aOptBlk(p);
+					return a;
+				case aLoopBegin :
+					a = find_in_aLoopBegin(p);
+					return a;
+				case aLoopBlk :
+					a = find_in_aSubBlk(p);
+					p->pred_lock[1] = FALSE;
+					return a;
+				case aPlusBlk :
+					a = find_in_aPlusBlk(p);
+					p->pred_lock[1] = FALSE;
+					return a;	/* nothing is visible past this guy */
+				case RuleBlk :
+					a = find_predicates(p->p1);
+					p->pred_lock[1] = FALSE;
+					return a;
+				case Generic :
+					a = find_predicates(p->p1);
+					b = find_predicates(p->p2);
+					if ( p->pred_lock!=NULL ) p->pred_lock[1] = FALSE;
+					if ( a==NULL ) return b;
+					if ( b==NULL ) return a;
+					/* otherwise OR the two preds together */
+					{
+					fatal_internal("hit unknown situation during predicate hoisting");
+					}
+				case EndBlk :
+				case EndRule :	/* Find no predicates after a rule ref */
+					return NULL;
+				default:
+					fatal_internal("this cannot be printed\n");
+					break;
+			}
+		}
+		case nAction :
+		{
+			ActionNode *p = (ActionNode *) alt;
+			if ( p->init_action ) return find_predicates(p->next);
+			if ( p->is_predicate )
+			{
+				Tree *t;
+#ifdef DBG_PRED
+				fprintf(stderr, "predicate: <<%s>>?\n", p->action);
+#endif
+				if ( p->guardpred!=NULL )
+				{
+					pred = p->guardpred;
+				}
+				else
+				{
+					pred = new_pred();
+					pred->k = predicateLookaheadDepth(p);
+					pred->source = p;
+					pred->expr = p->action;
+					if ( HoistPredicateContext && pred->k > 1 )
+					{
+						if ( first_item_is_guess_block((Junction *)p->next) )
+						{
+							warnFL("cannot compute context of predicate in front of (..)? block", FileStr[p->file], p->line);
+						}
+						else
+						{
+							ConstrainSearch = 0;
+							TRAV(p->next,
+								 pred->k,
+								 &(pred->completion), t);
+							pred->tcontext = t;
+#ifdef DBG_PRED
+							fprintf(stderr, "LL(%d) context:", pred->k);
+							preorder(t);
+							fprintf(stderr, "\n");
+#endif
+						}
+					}
+					else if ( HoistPredicateContext && pred->k == 1 )
+					{
+						pred->scontext[1] = empty;
+						if ( first_item_is_guess_block((Junction *)p->next) )
+						{
+							warnFL("cannot compute context of predicate in front of (..)? block", FileStr[p->file], p->line);
+						}
+						else
+						{
+							REACH((Junction *)p->next,
+								  1,
+								  &(pred->completion),
+								  pred->scontext[1]);
+#ifdef DBG_PRED
+							fprintf(stderr, "LL(1) context:");
+							s_fprT(stderr, pred->scontext[1]);
+							fprintf(stderr, "\n");
+#endif
+						}
+					}
+				}
+				{
+					Predicate *d = find_predicates(p->next), *root;
+/* Warning: Doesn't seem like the up pointers will all be set correctly;
+ * TJP: that's ok, we're not using them now.
+ */
+					if ( d!=NULL )
+					{
+						root = new_pred();
+						root->expr = PRED_AND_LIST;
+						root->down = pred;
+						pred->right = d;
+						pred->up = root;
+						d->left = pred;
+						d->up = pred->up;
+						return root;
+					}
+				}
+				return pred;
+			}
+			return NULL;
+		}
+		case nRuleRef :
+		{
+			Predicate *a;
+			RuleRefNode *p = (RuleRefNode *) alt;
+			Junction *r;
+			int save_halt;
+			RuleEntry *q = (RuleEntry *) hash_get(Rname, p->text);
+			if ( q == NULL )
+			{
+				warnFL( eMsg1("rule %s not defined",p->text), FileStr[p->file], p->line );
+				return NULL;
+			}
+			r = RulePtr[q->rulenum];
+			if ( r->pred_lock[1] )
+			{
+				/* infinite left-recursion; ignore 'cause LL sup 1 (k) analysis
+				 * must have seen it earlier.
+				 */
+				return NULL;
+			}
+			save_halt = r->end->halt;
+			r->end->halt = TRUE;
+/*			a = find_predicates((Node *)r->p1);*/
+			a = find_predicates((Node *)r);
+			r->end->halt = save_halt;
+			if ( a==NULL ) return NULL;
+			/* attempt to compute the "local" FOLLOW just like in normal lookahead
+			 * computation if needed
+			 */
+			complete_context_sets(p,a);
+			complete_context_trees(p,a);
+			return a;
+		}
+		case nToken :
+			break;
+	}
+
+	return NULL;
+}
+
+Predicate *
+#ifdef __STDC__
+new_pred( void )
+#else
+new_pred( )
+#endif
+{
+	Predicate *p = (Predicate *) malloc(sizeof(Predicate));
+	require(p!=NULL, "new_pred: cannot alloc predicate");
+	*p = pred_empty;
+	return p;
+}
+
+static void
+#ifdef __STDC__
+complete_context_sets( RuleRefNode *p, Predicate *a )
+#else
+complete_context_sets( p, a )
+RuleRefNode *p;
+Predicate *a;
+#endif
+{
+	set rk2, b;
+	int k2;
+
+#ifdef DBG_PRED
+	fprintf(stderr, "enter complete_context_sets\n");
+#endif
+	for (; a!=NULL; a=a->right)
+	{
+		if ( a->expr == PRED_AND_LIST || a->expr == PRED_OR_LIST )
+		{
+			complete_context_sets(p, a->down);
+			continue;
+		}
+		rk2 = b = empty;
+		while ( !set_nil(a->completion) )
+		{
+			k2 = set_int(a->completion);
+			set_rm(k2, a->completion);
+			REACH(p->next, k2, &rk2, b);
+			set_orin(&(a->scontext[1]), b);
+			set_free(b);
+		}
+		set_orin(&(a->completion), rk2);/* remember what we couldn't do */
+		set_free(rk2);
+#ifdef DBG_PRED
+		fprintf(stderr, "LL(1) context for %s(addr 0x%x) after ruleref:", a->expr, a);
+		s_fprT(stderr, a->scontext[1]);
+		fprintf(stderr, "\n");
+#endif
+/*		complete_context_sets(p, a->down);*/
+	}
+#ifdef DBG_PRED
+	fprintf(stderr, "exit complete_context_sets\n");
+#endif
+}
+
+static void
+#ifdef __STDC__
+complete_context_trees( RuleRefNode *p, Predicate *a )
+#else
+complete_context_trees( p, a )
+RuleRefNode *p;
+Predicate *a;
+#endif
+{
+	set rk2;
+	int k2;
+	Tree *u;
+
+#ifdef DBG_PRED
+	fprintf(stderr, "enter complete_context_trees\n");
+#endif
+	for (; a!=NULL; a=a->right)
+	{
+		if ( a->expr == PRED_AND_LIST || a->expr == PRED_OR_LIST )
+		{
+			complete_context_trees(p, a->down);
+			continue;
+		}
+		rk2 = empty;
+		/* any k left to do? if so, link onto tree */
+		while ( !set_nil(a->completion) )
+		{	
+			k2 = set_int(a->completion);
+			set_rm(k2, a->completion);
+			u = NULL;
+			TRAV(p->next, k2, &rk2, u);
+			/* any subtrees missing k2 tokens, add u onto end */
+			a->tcontext = tlink(a->tcontext, u, k2);
+		}
+		set_orin(&(a->completion), rk2);/* remember what we couldn't do */
+		set_free(rk2);
+#ifdef DBG_PRED
+		fprintf(stderr, "LL(i<%d) context after ruleref:", LL_k);
+		preorder(a->tcontext);
+		fprintf(stderr, "\n");
+#endif
+/*		complete_context_trees(p, a->down);*/
+	}
+#ifdef DBG_PRED
+	fprintf(stderr, "exit complete_context_trees\n");
+#endif
+}
+
+/* Walk a list of predicates and return the set of all tokens in scontext[1]'s */
+set
+#ifdef __STDC__
+covered_set( Predicate *p )
+#else
+covered_set( p )
+Predicate *p;
+#endif
+{
+	set a;
+
+	a = empty;
+	for (; p!=NULL; p=p->right)
+	{
+		if ( p->expr == PRED_AND_LIST || p->expr == PRED_OR_LIST )
+		{
+			set_orin(&a, covered_set(p->down));
+			continue;
+		}
+		set_orin(&a, p->scontext[1]);
+		set_orin(&a, covered_set(p->down));
+	}
+	return a;
+}