home
***
CD-ROM
|
disk
|
FTP
|
other
***
search
/
OS/2 Shareware BBS: 10 Tools
/
10-Tools.zip
/
pccts1.zip
/
ANTLR
/
PRED.C
< prev
next >
Wrap
C/C++ Source or Header
|
1993-09-02
|
9KB
|
375 lines
/*
* pred.c -- source for predicate detection, manipulation
*
* $Id: pred.c,v 1.6 1993/08/24 14:44:32 pccts Exp pccts $
* $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.10
* Terence Parr
* Purdue University
* 1989-1993
*/
#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"
#ifdef __STDC__
static Predicate *new_pred(void);
static void complete_context_sets(RuleRefNode *, Predicate *);
static void complete_context_trees(RuleRefNode *, Predicate *);
#else
static Predicate *new_pred();
static void complete_context_sets();
static void complete_context_trees();
#endif
static Predicate pred_empty = {NULL,NULL,set_init,{set_init,set_init}};
/* 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;
int max_k=0;
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, TokenStr[t->token]);
break;
case nAction :
fprintf(stderr, "Action\n");
break;
}
#endif
switch ( alt->ntype )
{
case nJunction :
{
Predicate *a, *b, *c;
Junction *p = (Junction *) alt;
if ( p->jtype == EndRule )
{
return NULL;
}
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;
}
a = find_predicates(p->p1);
/* don't follow p2 link as that points to next rule */
if ( p->jtype==RuleBlk ) {p->pred_lock[1] = FALSE; return a;}
b = find_predicates(p->p2);
/* link p2 predicates to others */
if ( a==NULL ) a = b;
else
{
for (c=a; c->next!=NULL; c=c->next) {;}
c->next = b;
}
if ( p->jtype==aLoopBlk || p->jtype==RuleBlk ||
p->jtype==aPlusBlk || p->jtype==EndRule )
{
p->pred_lock[1] = FALSE;
}
return a;
}
case nAction :
{
Predicate *a;
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
pred = new_pred();
if ( HoistPredicateContext && LL_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, LL_k, &(pred->completion), t);
t = tshrink( t );
t = tflatten( t );
t = tleft_factor( t );
pred->tcontext = t;
#ifdef DBG_PRED
fprintf(stderr, "LL(%d) context:", LL_k);
preorder(t);
fprintf(stderr, "\n");
#endif
}
}
else if ( HoistPredicateContext && LL_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
}
}
pred->expr = p->action;
a = find_predicates(p->next);
pred->next = a;
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 )
{
warnNoFL( eMsg1("rule %s not defined",p->text) );
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
*/
if ( LL_k==1 ) {complete_context_sets(p,a); return a;}
complete_context_trees(p,a); return a;
}
case nToken :
break;
}
return NULL;
}
static 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;
for (; a!=NULL; a=a->next)
{
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 after ruleref:");
s_fprT(stderr, a->scontext[1]);
fprintf(stderr, "\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;
for (; a!=NULL; a=a->next)
{
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(%d) context after ruleref:", LL_k);
preorder(a->tcontext);
fprintf(stderr, "\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->next)
{
set_orin(&a, p->scontext[1]);
}
return a;
}