home
***
CD-ROM
|
disk
|
FTP
|
other
***
search
/
The World of Computer Software
/
World_Of_Computer_Software-02-385-Vol-1of3.iso
/
p
/
pccts.zip
/
antlr
/
fset2.c
< prev
next >
Wrap
C/C++ Source or Header
|
1992-12-08
|
18KB
|
749 lines
/*
* fset2.c
*
* Compute FIRST sets for full LL(k)
*
* 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.06
* Terence Parr
* Purdue University
* 1989-1992
*/
#include <stdio.h>
#ifdef __STDC__
#include <stdarg.h>
#else
#include <varargs.h>
#endif
#include "set.h"
#include "syn.h"
#include "hash.h"
#include "generic.h"
#include "dlgdef.h"
extern char tokens[];
/* ick! globals. Used by permute() to track which elements of a set have been used */
static int *index;
static set *fset;
static unsigned **ftbl;
static set *constrain; /* pts into fset. constrains tToken() to 'constrain' */
int ConstrainSearch;
static int maxk; /* set to initial k upon tree construction request */
static Tree *FreeList = NULL;
#ifdef __STDC__
Tree *tmake(Tree *root, ...);
#else
Tree *tmake();
#endif
/* Do root
* Then each sibling
*/
void
preorder(tree)
Tree *tree;
{
if ( tree == NULL ) return;
if ( tree->down != NULL ) fprintf(stderr, " (");
if ( tree->token == ALT ) fprintf(stderr, " J");
else fprintf(stderr, " %s", TerminalString(tree->token));
if ( tree->token==EpToken ) fprintf(stderr, "(%d)", tree->v.rk);
preorder(tree->down);
if ( tree->down != NULL ) fprintf(stderr, " )");
preorder(tree->right);
}
/* check the depth of each primary sibling to see that it is exactly
* k deep. e.g.;
*
* ALT
* |
* A ------- B
* | |
* C -- D E
*
* Remove all branches <= k deep.
*
* Added by TJP 9-23-92 to correct the LL(k) constraint mechanism to work.
*/
Tree *
prune(t, k)
Tree *t;
int k;
{
if ( t == NULL ) return NULL;
if ( t->token == ALT ) fatal("prune: ALT node in FIRST tree");
t->right = prune(t->right, k);
t->down = prune(t->down, k-1);
if ( t->down == NULL && k > 1 )
{
Tree *r = t->right;
t->right = NULL;
Tfree(t);
return r;
}
return t;
}
/* build a tree (root child1 child2 ... NULL) */
#ifdef __STDC__
Tree *tmake(Tree *root, ...)
#else
Tree *tmake(va_alist)
va_dcl
#endif
{
va_list ap;
Tree *child, *sibling=NULL, *tail;
#ifndef __STDC__
Tree *root;
#endif
#ifdef __STDC__
require(root!=NULL, "tmake: NULL root impossible");
#endif
#ifdef __STDC__
va_start(ap, root);
#else
va_start(ap);
root = va_arg(ap, Tree *);
#endif
child = va_arg(ap, Tree *);
while ( child != NULL )
{
if ( sibling == NULL ) sibling = tail = child;
else {tail->right = child; tail = child;}
child = va_arg(ap, Tree *);
}
root->down = sibling;
va_end(ap);
return root;
}
Tree *
tnode(tok)
int tok;
{
Tree *p, *newblk;
static int n=0;
if ( FreeList == NULL )
{
/*fprintf(stderr, "tnode: %d more nodes\n", TreeBlockAllocSize);*/
if ( TreeResourceLimit > 0 )
{
if ( (n+TreeBlockAllocSize) >= TreeResourceLimit )
{
fprintf(stderr, ErrHdr, FileStr[CurAmbigfile], CurAmbigline);
fprintf(stderr, " hit analysis resource limit while analyzing alts %d and %d %s\n",
CurAmbigAlt1,
CurAmbigAlt2,
CurAmbigbtype);
exit(-1);
}
}
newblk = (Tree *)calloc(TreeBlockAllocSize, sizeof(Tree));
if ( newblk == NULL )
{
fprintf(stderr, ErrHdr, FileStr[CurAmbigfile], CurAmbigline);
fprintf(stderr, " out of memory while analyzing alts %d and %d %s\n",
CurAmbigAlt1,
CurAmbigAlt2,
CurAmbigbtype);
exit(-1);
}
n += TreeBlockAllocSize;
for (p=newblk; p<&(newblk[TreeBlockAllocSize]); p++)
{
p->right = FreeList; /* add all new Tree nodes to Free List */
FreeList = p;
}
}
p = FreeList;
FreeList = FreeList->right; /* remove a tree node */
p->right = NULL; /* zero out ptrs */
p->down = NULL;
p->token = tok;
return p;
}
static Tree *
eofnode(k)
int k;
{
Tree *t=NULL;
int i;
for (i=1; i<=k; i++)
{
t = tmake(tnode(EofToken), t, NULL);
}
return t;
}
void
tfree(t)
Tree *t;
{
if ( t!=NULL )
{
t->right = FreeList;
FreeList = t;
}
}
/* tree duplicate */
Tree *
tdup(t)
Tree *t;
{
Tree *u;
if ( t == NULL ) return NULL;
u = tnode(t->token);
u->v.rk = t->v.rk;
u->right = tdup(t->right);
u->down = tdup(t->down);
return u;
}
Tree *
tappend(t,u)
Tree *t, *u;
{
Tree *w;
/*fprintf(stderr, "tappend(");
preorder(t); fprintf(stderr, ",");
preorder(u); fprintf(stderr, " )\n");*/
if ( t == NULL ) return u;
if ( t->token == ALT && t->right == NULL ) return tappend(t->down, u);
for (w=t; w->right!=NULL; w=w->right) {;}
w->right = u;
return t;
}
/* dealloc all nodes in a tree */
void
Tfree(t)
Tree *t;
{
if ( t == NULL ) return;
Tfree( t->down );
Tfree( t->right );
tfree( t );
}
/* find all children (alts) of t that require remaining_k nodes to be LL_k
* tokens long.
*
* t-->o
* |
* a1--a2--...--an <-- LL(1) tokens
* | | |
* b1 b2 ... bn <-- LL(2) tokens
* | | |
* . . .
* . . .
* z1 z2 ... zn <-- LL(LL_k) tokens
*
* We look for all [Ep] needing remaining_k nodes and replace with u.
* u is not destroyed or actually used by the tree (a copy is made).
*/
Tree *
tlink(t,u,remaining_k)
Tree *t, *u;
int remaining_k;
{
Tree *p;
require(remaining_k!=0, "tlink: bad tree");
if ( t==NULL ) return NULL;
/*fprintf(stderr, "tlink: u is:"); preorder(u); fprintf(stderr, "\n");*/
if ( t->token == EpToken && t->v.rk == remaining_k )
{
require(t->down==NULL, "tlink: invalid tree");
if ( u == NULL ) return t->right;
p = tdup( u );
p->right = t->right;
tfree( t );
return p;
}
t->down = tlink(t->down, u, remaining_k);
t->right = tlink(t->right, u, remaining_k);
return t;
}
/* remove as many ALT nodes as possible while still maintaining semantics */
Tree *
tshrink(t)
Tree *t;
{
if ( t == NULL ) return NULL;
t->down = tshrink( t->down );
t->right = tshrink( t->right );
if ( t->down == NULL )
{
if ( t->token == ALT )
{
Tree *u = t->right;
tfree(t);
return u; /* remove useless alts */
}
return t;
}
/* (? (ALT (? ...)) s) ==> (? (? ...) s) where s = sibling, ? = match any */
if ( t->token == ALT && t->down->right == NULL)
{
Tree *u = t->down;
u->right = t->right;
tfree( t );
return u;
}
/* (? (A (ALT t)) s) ==> (? (A t) s) where A is a token; s,t siblings */
if ( t->token != ALT && t->down->token == ALT && t->down->right == NULL )
{
Tree *u = t->down->down;
tfree( t->down );
t->down = u;
return t;
}
return t;
}
Tree *
tflatten(t)
Tree *t;
{
if ( t == NULL ) return NULL;
t->down = tflatten( t->down );
t->right = tflatten( t->right );
if ( t->down == NULL ) return t;
if ( t->token == ALT )
{
Tree *u;
/* find tail of children */
for (u=t->down; u->right!=NULL; u=u->right) {;}
u->right = t->right;
u = t->down;
tfree( t );
return u;
}
return t;
}
Tree *
tJunc(p,k,rk)
Junction *p;
int k;
set *rk;
{
Tree *t=NULL, *u=NULL;
Junction *alt;
Tree *tail, *r;
#ifdef DBG_TRAV
fprintf(stderr, "tJunc(%d): %s in rule %s\n", k,
decodeJType[p->jtype], ((Junction *)p)->rname);
#endif
if ( p->jtype==aLoopBlk || p->jtype==RuleBlk ||
p->jtype==aPlusBlk || p->jtype==aSubBlk || p->jtype==aOptBlk )
{
if ( p->jtype!=aSubBlk && p->jtype!=aOptBlk ) {
require(p->lock!=NULL, "rJunc: lock array is NULL");
if ( p->lock[k] ) return NULL;
p->lock[k] = TRUE;
}
TRAV(p->p1, k, rk, tail);
if ( p->jtype==RuleBlk ) {p->lock[k] = FALSE; return tail;}
r = tmake(tnode(ALT), tail, NULL);
for (alt=(Junction *)p->p2; alt!=NULL; alt = (Junction *)alt->p2)
{
if ( tail==NULL ) {TRAV(alt->p1, k, rk, tail); r->down = tail;}
else
{
TRAV(alt->p1, k, rk, tail->right);
/* TJP -- lost info when tail->right was NULL
tail = tail->right;*/
if ( tail->right != NULL ) tail = tail->right;
}
}
if ( p->jtype!=aSubBlk && p->jtype!=aOptBlk ) p->lock[k] = FALSE;
#ifdef DBG_TREES
fprintf(stderr, "blk(%s) returns:",((Junction *)p)->rname); preorder(r); fprintf(stderr, "\n");
#endif
if ( r->down == NULL ) {tfree(r); return NULL;}
return r;
}
if ( p->jtype==EndRule )
{
if ( p->halt ) /* don't want FOLLOW here? */
{
set_orel(k, rk); /* indicate this k value needed */
t = tnode(EpToken);
t->v.rk = k;
return t;
}
require(p->lock!=NULL, "rJunc: lock array is NULL");
if ( p->lock[k] ) return NULL;
/* if no FOLLOW assume k EOF's */
if ( p->p1 == NULL ) return eofnode(k);
p->lock[k] = TRUE;
}
if ( p->p2 == NULL )
{
TRAV(p->p1, k, rk,t);
if ( p->jtype==EndRule ) p->lock[k]=FALSE;
return t;
}
TRAV(p->p1, k, rk, t);
if ( p->jtype!=RuleBlk ) TRAV(p->p2, k, rk, u);
if ( p->jtype==EndRule ) p->lock[k] = FALSE;/* unlock node */
if ( t==NULL ) return tmake(tnode(ALT), u, NULL);
return tmake(tnode(ALT), t, u, NULL);
}
Tree *
tRuleRef(p,k,rk_out)
RuleRefNode *p;
int k;
set *rk_out;
{
int k2;
Tree *t, *u;
Junction *r;
set rk, rk2;
char save_halt;
RuleEntry *q = (RuleEntry *) hash_get(Rname, p->text);
#ifdef DBG_TRAV
fprintf(stderr, "tRuleRef: %s\n", p->text);
#endif
if ( q == NULL )
{
TRAV(p->next, k, rk_out, t);/* ignore undefined rules */
return t;
}
rk = rk2 = empty;
r = RulePtr[q->rulenum];
if ( r->lock[k] ) return NULL;
save_halt = r->end->halt;
r->end->halt = TRUE; /* don't let reach fall off end of rule here */
TRAV(r, k, &rk, t);
r->end->halt = save_halt;
#ifdef DBG_TREES
fprintf(stderr, "after ruleref, t is:"); preorder(t); fprintf(stderr, "\n");
#endif
t = tshrink( t );
while ( !set_nil(rk) ) { /* any k left to do? if so, link onto tree */
k2 = set_int(rk);
set_rm(k2, rk);
TRAV(p->next, k2, &rk2, u);
t = tlink(t, u, k2); /* any alts missing k2 toks, add u onto end */
}
set_orin(rk_out, rk2); /* remember what we couldn't do */
set_free(rk2);
return t;
}
Tree *
tToken(p,k,rk)
TokNode *p;
int k;
set *rk;
{
Tree *t;
require(constrain>=fset&&constrain<=&(fset[LL_k]),"tToken: constrain is not a valid set");
constrain = &fset[maxk-k+1];
#ifdef DBG_TRAV
fprintf(stderr, "tToken(%d): %s\n", k, TerminalString(p->token));
if ( ConstrainSearch ) {
fprintf(stderr, "constrain is:"); s_fprT(stderr, *constrain); fprintf(stderr, "\n");
}
#endif
if ( ConstrainSearch )
if ( !set_el(p->token, *constrain) )
{
/* fprintf(stderr, "ignoring token %s(%d)\n", TerminalString(p->token),
k);*/
return NULL;
}
if ( k == 1 ) return tnode(p->token);
TRAV(p->next, k-1, rk, t);
/* here, we are positive that, at least, this tree will not contribute
* to the LL(2) tree since it will be too shallow, IF t==NULL
*/
if ( t == NULL ) /* tree will be too shallow */
{
return NULL;
}
#ifdef DBG_TREES
fprintf(stderr, "tToken(%d)->next:",k); preorder(t); fprintf(stderr, "\n");
#endif
return tmake(tnode(p->token), t, NULL);
}
Tree *
tAction(p,k,rk)
ActionNode *p;
int k;
set *rk;
{
Tree *t;
/*fprintf(stderr, "tAction\n");*/
TRAV(p->next, k, rk, t);
return t;
}
/* see if e exists in s as a possible input permutation (e is always a chain) */
int
tmember(e,s)
Tree *e, *s;
{
if ( e==NULL||s==NULL ) return 0;
/*fprintf(stderr, "tmember(");
preorder(e); fprintf(stderr, ",");
preorder(s); fprintf(stderr, " )\n");*/
if ( s->token == ALT && s->right == NULL ) return tmember(e, s->down);
if ( e->token!=s->token )
{
if ( s->right==NULL ) return 0;
return tmember(e, s->right);
}
if ( e->down==NULL && s->down == NULL ) return 1;
if ( tmember(e->down, s->down) ) return 1;
if ( s->right==NULL ) return 0;
return tmember(e, s->right);
}
/* combine (? (A t) ... (A u) ...) into (? (A t u)) */
Tree *
tleft_factor(t)
Tree *t;
{
Tree *u, *v, *trail, *w;
/* left-factor what is at this level */
if ( t == NULL ) return NULL;
for (u=t; u!=NULL; u=u->right)
{
trail = u;
v=u->right;
while ( v!=NULL )
{
if ( u->token == v->token )
{
if ( u->down!=NULL )
{
for (w=u->down; w->right!=NULL; w=w->right) {;}
w->right = v->down; /* link children together */
}
else u->down = v->down;
trail->right = v->right; /* unlink factored node */
tfree( v );
v = trail->right;
}
else {trail = v; v=v->right;}
}
}
/* left-factor what is below */
for (u=t; u!=NULL; u=u->right) u->down = tleft_factor( u->down );
return t;
}
/* remove the permutation p from t if present */
Tree *
trm_perm(t,p)
Tree *t, *p;
{
/*
fprintf(stderr, "trm_perm(");
preorder(t); fprintf(stderr, ",");
preorder(p); fprintf(stderr, " )\n");
*/
if ( t == NULL || p == NULL ) return NULL;
if ( t->token == ALT )
{
t->down = trm_perm(t->down, p);
if ( t->down == NULL ) /* nothing left below, rm cur node */
{
Tree *u = t->right;
tfree( t );
return trm_perm(u, p);
}
t->right = trm_perm(t->right, p); /* look for more instances of p */
return t;
}
if ( p->token != t->token ) /* not found, try a sibling */
{
t->right = trm_perm(t->right, p);
return t;
}
t->down = trm_perm(t->down, p->down);
if ( t->down == NULL ) /* nothing left below, rm cur node */
{
Tree *u = t->right;
tfree( t );
return trm_perm(u, p);
}
t->right = trm_perm(t->right, p); /* look for more instances of p */
return t;
}
/* add the permutation 'perm' to the LL_k sets in 'fset' */
void
tcvt(fset,perm)
set *fset;
Tree *perm;
{
if ( perm==NULL ) return;
set_orel(perm->token, fset);
tcvt(fset+1, perm->down);
}
/* for each element of ftbl[k], make it the root of a tree with permute(ftbl[k+1])
* as a child.
*/
Tree *
permute(k)
int k;
{
Tree *t, *u;
if ( k>LL_k ) return NULL;
if ( ftbl[k][index[k]] == nil ) return NULL;
t = permute(k+1);
if ( t==NULL&&k<LL_k ) /* no permutation left below for k+1 tokens? */
{
index[k+1] = 0;
(index[k])++; /* try next token at this k */
return permute(k);
}
u = tmake(tnode(ftbl[k][index[k]]), t, NULL);
if ( k == LL_k ) (index[k])++;
return u;
}
/* Compute LL(k) trees for alts alt1 and alt2 of p.
* function result is tree of ambiguous input permutations
*
* ALGORITHM may change to look for something other than LL_k size
* trees ==> maxk will have to change.
*/
Tree *
VerifyAmbig(alt1,alt2,ft,fs,t,u,numAmbig)
Junction *alt1, *alt2;
unsigned **ft;
set *fs; /* set of possible ambiguities */
Tree **t, **u; /* return constrained perm sets */
int *numAmbig; /* how many ambigs were there */
{
set rk;
Tree *perm, *ambig=NULL;
int k;
maxk = LL_k; /* NOTE: for now, we look for LL_k */
ftbl = ft;
fset = fs;
constrain = &(fset[1]);
index = (int *) calloc(LL_k+1, sizeof(int));
if ( index == NULL )
{
fprintf(stderr, ErrHdr, CurAmbigfile, CurAmbigline);
fprintf(stderr, " out of memory while analyzing alts %d and %d of %s\n",
CurAmbigAlt1,
CurAmbigAlt2,
CurAmbigbtype);
exit(-1);
}
for (k=1; k<=LL_k; k++) index[k] = 0;
rk = empty;
ConstrainSearch = 1; /* consider only tokens in ambig sets */
TRAV(alt1->p1, LL_k, &rk, *t);
*t = tshrink( *t );
*t = tflatten( *t );
*t = prune(*t, LL_k);
*t = tleft_factor( *t );
/* fprintf(stderr, "after shrink&flatten&prune&left_factor:"); preorder(*t); fprintf(stderr, "\n");*/
if ( *t == NULL )
{
/* fprintf(stderr, "TreeIncomplete --> no LL(%d) ambiguity\n", LL_k);*/
Tfree( *t ); /* kill if impossible to have ambig */
*t = NULL;
}
TRAV(alt2->p1, LL_k, &rk, *u);
*u = tshrink( *u );
*u = tflatten( *u );
*u = prune(*u, LL_k);
*u = tleft_factor( *u );
/* fprintf(stderr, "after shrink&flatten&prune&lfactor:"); preorder(*u); fprintf(stderr, "\n");*/
if ( *u == NULL )
{
/* fprintf(stderr, "TreeIncomplete --> no LL(%d) ambiguity\n", LL_k);*/
Tfree( *u );
*u = NULL;
}
for (k=1; k<=LL_k; k++) set_clr( fs[k] );
ambig = tnode(ALT);
k = 0;
if ( *t!=NULL && *u!=NULL )
{
while ( (perm=permute(1))!=NULL )
{
/* fprintf(stderr, "chk perm:"); preorder(perm); fprintf(stderr, "\n");*/
if ( tmember(perm, *t) && tmember(perm, *u) )
{
/* fprintf(stderr, "ambig upon"); preorder(perm); fprintf(stderr, "\n");*/
k++;
perm->right = ambig->down;
ambig->down = perm;
tcvt(&(fs[1]), perm);
}
else Tfree( perm );
}
}
*numAmbig = k;
if ( ambig->down == NULL ) {tfree(ambig); ambig = NULL;}
free( index );
/*fprintf(stderr, "final ambig:"); preorder(ambig); fprintf(stderr, "\n");*/
return ambig;
}