X-Git-Url: https://pd.if.org/git/?p=pccts;a=blobdiff_plain;f=antlr%2Fbuild.c;fp=antlr%2Fbuild.c;h=95e91037a8a6772fb3cdd68ea4c9aa87d34f090f;hp=0000000000000000000000000000000000000000;hb=129ce0f1c9d43c04ed8198ac184bce8d8be0042e;hpb=b5b3c41d4e99ca613b441d68458aa3cd873aa417 diff --git a/antlr/build.c b/antlr/build.c new file mode 100755 index 0000000..95e9103 --- /dev/null +++ b/antlr/build.c @@ -0,0 +1,716 @@ +/* + * build.c -- functions associated with building syntax diagrams. + * + * $Id: build.c,v 1.3 95/06/15 18:07:00 parrt Exp $ + * $Revision: 1.3 $ + * + * 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 +#ifdef __cplusplus +#ifndef __STDC__ +#define __STDC__ +#endif +#endif +#include "set.h" +#include "syn.h" +#include "hash.h" +#include "generic.h" +#include "dlgdef.h" + +#define SetBlk(g, t, approx) { \ + ((Junction *)g.left)->jtype = t; \ + ((Junction *)g.left)->approx = approx; \ + ((Junction *)g.left)->end = (Junction *) g.right; \ + ((Junction *)g.right)->jtype = EndBlk;} + +/* Add the parameter string 'parm' to the parms field of a block-type junction + * g.left points to the sentinel node on a block. i.e. g.left->p1 points to + * the actual junction with its jtype == some block-type. + */ +void +#ifdef __STDC__ +addParm( Node *p, char *parm ) +#else +addParm( p, parm ) +Node *p; +char *parm; +#endif +{ + char *q = (char *) malloc( strlen(parm) + 1 ); + require(p!=NULL, "addParm: NULL object\n"); + require(q!=NULL, "addParm: unable to alloc parameter\n"); + + strcpy(q, parm); + if ( p->ntype == nRuleRef ) + { + ((RuleRefNode *)p)->parms = q; + } + else if ( p->ntype == nJunction ) + { + ((Junction *)p)->parm = q; /* only one parameter allowed on subrules */ + } + else fatal_internal("addParm: invalid node for adding parm"); +} + +/* + * Build an action node for the syntax diagram + * + * buildAction(ACTION) ::= --o-->ACTION-->o-- + * + * Where o is a junction node. + */ +Graph +#ifdef __STDC__ +buildAction( char *action, int file, int line, int is_predicate ) +#else +buildAction( action, file, line, is_predicate ) +char *action; +int file; +int line; +int is_predicate; +#endif +{ + Junction *j1, *j2; + Graph g; + ActionNode *a; + require(action!=NULL, "buildAction: invalid action"); + + j1 = newJunction(); + j2 = newJunction(); + a = newActionNode(); + a->action = (char *) malloc( strlen(action)+1 ); + require(a->action!=NULL, "buildAction: cannot alloc space for action\n"); + strcpy(a->action, action); + j1->p1 = (Node *) a; + a->next = (Node *) j2; + a->is_predicate = is_predicate; + g.left = (Node *) j1; g.right = (Node *) j2; + a->file = file; + a->line = line; + a->rname = "not filled in"; + return g; +} + +/* + * Build a token node for the syntax diagram + * + * buildToken(TOKEN) ::= --o-->TOKEN-->o-- + * + * Where o is a junction node. + */ +Graph +#ifdef __STDC__ +buildToken( char *text ) +#else +buildToken( text ) +char *text; +#endif +{ + Junction *j1, *j2; + Graph g; + TokNode *t; + require(text!=NULL, "buildToken: invalid token name"); + + j1 = newJunction(); + j2 = newJunction(); + t = newTokNode(); + t->altstart = CurAltStart; + if ( *text == '"' ) {t->label=FALSE; t->token = addTexpr( text );} + else {t->label=TRUE; t->token = addTname( text );} + j1->p1 = (Node *) t; + t->next = (Node *) j2; + g.left = (Node *) j1; g.right = (Node *) j2; + return g; +} + +/* + * Build a wild-card node for the syntax diagram + * + * buildToken(TOKEN) ::= --o-->'.'-->o-- + * + * Where o is a junction node. + */ +Graph +#ifdef __STDC__ +buildWildCard( char *text ) +#else +buildWildCard( text ) +char *text; +#endif +{ + Junction *j1, *j2; + Graph g; + TokNode *t; + TCnode *w; + TermEntry *p; + require(text!=NULL, "buildWildCard: invalid token name"); + + j1 = newJunction(); + j2 = newJunction(); + t = newTokNode(); + + /* If the ref a wild card, make a token class for it */ + if ( Tnum(WildCardString) == 0 ) + { + w = newTCnode; + w->tok = addTname( WildCardString ); + set_orel(w->tok, &imag_tokens); + set_orel(w->tok, &tokclasses); + WildCardToken = w->tok; + require((p=(TermEntry *)hash_get(Tname, WildCardString)) != NULL, + "hash table mechanism is broken"); + p->classname = 1; /* entry is class name, not token */ + p->tclass = w; /* save ptr to this tclass def */ + list_add(&tclasses, (char *)w); + } + else { + p=(TermEntry *)hash_get(Tname, WildCardString); + require( p!= NULL, "hash table mechanism is broken"); + w = p->tclass; + } + + t->token = w->tok; + t->wild_card = 1; + t->tclass = w; + + t->altstart = CurAltStart; + j1->p1 = (Node *) t; + t->next = (Node *) j2; + g.left = (Node *) j1; g.right = (Node *) j2; + return g; +} + +void +#ifdef __STDC__ +setUpperRange(TokNode *t, char *text) +#else +setUpperRange(t, text) +TokNode *t; +char *text; +#endif +{ + require(t!=NULL, "setUpperRange: NULL token node"); + require(text!=NULL, "setUpperRange: NULL token string"); + + if ( *text == '"' ) {t->upper_range = addTexpr( text );} + else {t->upper_range = addTname( text );} +} + +/* + * Build a rule reference node of the syntax diagram + * + * buildRuleRef(RULE) ::= --o-->RULE-->o-- + * + * Where o is a junction node. + * + * If rule 'text' has been defined already, don't alloc new space to store string. + * Set r->text to point to old copy in string table. + */ +Graph +#ifdef __STDC__ +buildRuleRef( char *text ) +#else +buildRuleRef( text ) +char *text; +#endif +{ + Junction *j1, *j2; + Graph g; + RuleRefNode *r; + RuleEntry *p; + require(text!=NULL, "buildRuleRef: invalid rule name"); + + j1 = newJunction(); + j2 = newJunction(); + r = newRNode(); + r->altstart = CurAltStart; + r->assign = NULL; + if ( (p=(RuleEntry *)hash_get(Rname, text)) != NULL ) r->text = p->str; + else r->text = mystrdup( text ); + j1->p1 = (Node *) r; + r->next = (Node *) j2; + g.left = (Node *) j1; g.right = (Node *) j2; + return g; +} + +/* + * Or two subgraphs into one graph via: + * + * Or(G1, G2) ::= --o-G1-o-- + * | ^ + * v | + * o-G2-o + * + * Set the altnum of junction starting G2 to 1 + altnum of junction starting G1. + * If, however, the G1 altnum is 0, make it 1 and then + * make G2 altnum = G1 altnum + 1. + */ +Graph +#ifdef __STDC__ +Or( Graph g1, Graph g2 ) +#else +Or( g1, g2 ) +Graph g1; +Graph g2; +#endif +{ + Graph g; + require(g1.left != NULL, "Or: invalid graph"); + require(g2.left != NULL && g2.right != NULL, "Or: invalid graph"); + + ((Junction *)g1.left)->p2 = g2.left; + ((Junction *)g2.right)->p1 = g1.right; + /* set altnums */ + if ( ((Junction *)g1.left)->altnum == 0 ) ((Junction *)g1.left)->altnum = 1; + ((Junction *)g2.left)->altnum = ((Junction *)g1.left)->altnum + 1; + g.left = g2.left; + g.right = g1.right; + return g; +} + +/* + * Catenate two subgraphs + * + * Cat(G1, G2) ::= --o-G1-o-->o-G2-o-- + * Cat(NULL,G2)::= --o-G2-o-- + * Cat(G1,NULL)::= --o-G1-o-- + */ +Graph +#ifdef __STDC__ +Cat( Graph g1, Graph g2 ) +#else +Cat( g1, g2 ) +Graph g1; +Graph g2; +#endif +{ + Graph g; + + if ( g1.left == NULL && g1.right == NULL ) return g2; + if ( g2.left == NULL && g2.right == NULL ) return g1; + ((Junction *)g1.right)->p1 = g2.left; + g.left = g1.left; + g.right = g2.right; + return g; +} + +/* + * Make a subgraph an optional block + * + * makeOpt(G) ::= --o-->o-G-o-->o-- + * | ^ + * v | + * o-------o + * + * Note that this constructs {A|B|...|Z} as if (A|B|...|Z|) was found. + * + * The node on the far right is added so that every block owns its own + * EndBlk node. + */ +Graph +#ifdef __STDC__ +makeOpt( Graph g1, int approx ) +#else +makeOpt( g1, approx ) +Graph g1; +int approx; +#endif +{ + Junction *j1,*j2,*p; + Graph g; + require(g1.left != NULL && g1.right != NULL, "makeOpt: invalid graph"); + + j1 = newJunction(); + j2 = newJunction(); + ((Junction *)g1.right)->p1 = (Node *) j2; /* add node to G at end */ + g = emptyAlt(); + if ( ((Junction *)g1.left)->altnum == 0 ) ((Junction *)g1.left)->altnum = 1; + ((Junction *)g.left)->altnum = ((Junction *)g1.left)->altnum + 1; + for(p=(Junction *)g1.left; p->p2!=NULL; p=(Junction *)p->p2) + {;} /* find last alt */ + p->p2 = g.left; /* add optional alternative */ + ((Junction *)g.right)->p1 = (Node *)j2; /* opt alt points to EndBlk */ + g1.right = (Node *)j2; + SetBlk(g1, aOptBlk, approx); + j1->p1 = g1.left; /* add generic node in front */ + g.left = (Node *) j1; + g.right = g1.right; + + return g; +} + +/* + * Make a graph into subblock + * + * makeBlk(G) ::= --o-->o-G-o-->o-- + * + * The node on the far right is added so that every block owns its own + * EndBlk node. + */ +Graph +#ifdef __STDC__ +makeBlk( Graph g1, int approx ) +#else +makeBlk( g1, approx ) +Graph g1; +int approx; +#endif +{ + Junction *j,*j2; + Graph g; + require(g1.left != NULL && g1.right != NULL, "makeBlk: invalid graph"); + + j = newJunction(); + j2 = newJunction(); + ((Junction *)g1.right)->p1 = (Node *) j2; /* add node to G at end */ + g1.right = (Node *)j2; + SetBlk(g1, aSubBlk, approx); + j->p1 = g1.left; /* add node in front */ + g.left = (Node *) j; + g.right = g1.right; + + return g; +} + +/* + * Make a subgraph into a loop (closure) block -- (...)* + * + * makeLoop(G) ::= |---| + * v | + * --o-->o-->o-G-o-->o-- + * | ^ + * v | + * o-----------o + * + * After making loop, always place generic node out front. It becomes + * the start of enclosing block. The aLoopBlk is the target of the loop. + * + * Loop blks have TWO EndBlk nodes--the far right and the node that loops back + * to the aLoopBlk node. Node with which we can branch past loop == aLoopBegin and + * one which is loop target == aLoopBlk. + * The branch-past (initial) aLoopBegin node has end + * pointing to the last EndBlk node. The loop-target node has end==NULL. + * + * Loop blocks have a set of locks (from 1..CLL_k) on the aLoopBlk node. + */ +Graph +#ifdef __STDC__ +makeLoop( Graph g1, int approx ) +#else +makeLoop( g1, approx ) +Graph g1; +int approx; +#endif +{ + Junction *back, *front, *begin; + Graph g; + require(g1.left != NULL && g1.right != NULL, "makeLoop: invalid graph"); + + back = newJunction(); + front = newJunction(); + begin = newJunction(); + g = emptyAlt(); + ((Junction *)g1.right)->p2 = g1.left; /* add loop branch to G */ + ((Junction *)g1.right)->p1 = (Node *) back; /* add node to G at end */ + ((Junction *)g1.right)->jtype = EndBlk; /* mark 1st EndBlk node */ + ((Junction *)g1.left)->jtype = aLoopBlk; /* mark 2nd aLoopBlk node */ + ((Junction *)g1.left)->end = (Junction *) g1.right; + ((Junction *)g1.left)->lock = makelocks(); + ((Junction *)g1.left)->pred_lock = makelocks(); + g1.right = (Node *) back; + begin->p1 = (Node *) g1.left; + g1.left = (Node *) begin; + begin->p2 = (Node *) g.left; /* make bypass arc */ + ((Junction *)g.right)->p1 = (Node *) back; + SetBlk(g1, aLoopBegin, approx); + front->p1 = g1.left; /* add node to front */ + g1.left = (Node *) front; + + return g1; +} + +/* + * Make a subgraph into a plus block -- (...)+ -- 1 or more times + * + * makePlus(G) ::= |---| + * v | + * --o-->o-G-o-->o-- + * + * After making loop, always place generic node out front. It becomes + * the start of enclosing block. The aPlusBlk is the target of the loop. + * + * Plus blks have TWO EndBlk nodes--the far right and the node that loops back + * to the aPlusBlk node. + * + * Plus blocks have a set of locks (from 1..CLL_k) on the aPlusBlk node. + */ +Graph +#ifdef __STDC__ +makePlus( Graph g1, int approx ) +#else +makePlus( g1, approx ) +Graph g1; +int approx; +#endif +{ + int has_empty_alt_already = 0; + Graph g; + Junction *j2, *j3, *first_alt; + Junction *last_alt, *p; + require(g1.left != NULL && g1.right != NULL, "makePlus: invalid graph"); + + first_alt = (Junction *)g1.left; + j2 = newJunction(); + j3 = newJunction(); + if ( ((Junction *)g1.left)->altnum == 0 ) ((Junction *)g1.left)->altnum = 1; + ((Junction *)g1.right)->p2 = g1.left; /* add loop branch to G */ + ((Junction *)g1.right)->p1 = (Node *) j2; /* add node to G at end */ + ((Junction *)g1.right)->jtype = EndBlk; /* mark 1st EndBlk node */ + g1.right = (Node *) j2; + SetBlk(g1, aPlusBlk, approx); + ((Junction *)g1.left)->lock = makelocks(); + ((Junction *)g1.left)->pred_lock = makelocks(); + j3->p1 = g1.left; /* add node to front */ + g1.left = (Node *) j3; + + /* add an optional branch which is the "exit" branch of loop */ + /* FIRST, check to ensure that there does not already exist + * an optional path. + */ + /* find last alt */ + for(p=first_alt; p!=NULL; p=(Junction *)p->p2) + { + if ( p->p1->ntype == nJunction && + p->p1!=NULL && + ((Junction *)p->p1)->jtype==Generic && + ((Junction *)p->p1)->p1!=NULL && + ((Junction *)((Junction *)p->p1)->p1)->jtype==EndBlk ) + { + has_empty_alt_already = 1; + } + last_alt = p; + } + if ( !has_empty_alt_already ) + { + require(last_alt!=NULL, "last_alt==NULL; bad (..)+"); + g = emptyAlt(); + last_alt->p2 = g.left; + ((Junction *)g.right)->p1 = (Node *) j2; + + /* make sure lookahead computation ignores this alt for + * FIRST("(..)+"); but it's still used for computing the FIRST + * of each alternative. + */ + ((Junction *)g.left)->ignore = 1; + } + + return g1; +} + +/* + * Return an optional path: --o-->o-- + */ +Graph +#ifdef __STDC__ +emptyAlt( void ) +#else +emptyAlt( ) +#endif +{ + Junction *j1, *j2; + Graph g; + + j1 = newJunction(); + j2 = newJunction(); + j1->p1 = (Node *) j2; + g.left = (Node *) j1; + g.right = (Node *) j2; + + return g; +} + +/* N o d e A l l o c a t i o n */ + +TokNode * +#ifdef __STDC__ +newTokNode( void ) +#else +newTokNode( ) +#endif +{ + static TokNode *FreeList = NULL; + TokNode *p, *newblk; + + if ( FreeList == NULL ) + { + newblk = (TokNode *)calloc(TokenBlockAllocSize, sizeof(TokNode)); + if ( newblk == NULL ) + fatal_internal(eMsg1("out of memory while building rule '%s'",CurRule)); + for (p=newblk; p<&(newblk[TokenBlockAllocSize]); p++) + { + p->next = (Node *)FreeList; /* add all new token nodes to FreeList */ + FreeList = p; + } + } + p = FreeList; + FreeList = (TokNode *)FreeList->next;/* remove a TokNode node */ + p->next = NULL; /* NULL the ptr we used */ + + p->ntype = nToken; + p->rname = CurRule; + p->file = CurFile; + p->line = zzline; + p->altstart = NULL; + + return p; +} + +RuleRefNode * +#ifdef __STDC__ +newRNode( void ) +#else +newRNode( ) +#endif +{ + static RuleRefNode *FreeList = NULL; + RuleRefNode *p, *newblk; + + if ( FreeList == NULL ) + { + newblk = (RuleRefNode *)calloc(RRefBlockAllocSize, sizeof(RuleRefNode)); + if ( newblk == NULL ) + fatal_internal(eMsg1("out of memory while building rule '%s'",CurRule)); + for (p=newblk; p<&(newblk[RRefBlockAllocSize]); p++) + { + p->next = (Node *)FreeList; /* add all new rref nodes to FreeList */ + FreeList = p; + } + } + p = FreeList; + FreeList = (RuleRefNode *)FreeList->next;/* remove a Junction node */ + p->next = NULL; /* NULL the ptr we used */ + + p->ntype = nRuleRef; + p->rname = CurRule; + p->file = CurFile; + p->line = zzline; + p->astnode = ASTinclude; + p->altstart = NULL; + + return p; +} + +Junction * +#ifdef __STDC__ +newJunction( void ) +#else +newJunction( ) +#endif +{ + static Junction *FreeList = NULL; + Junction *p, *newblk; + + if ( FreeList == NULL ) + { + newblk = (Junction *)calloc(JunctionBlockAllocSize, sizeof(Junction)); + if ( newblk == NULL ) + fatal_internal(eMsg1("out of memory while building rule '%s'",CurRule)); + for (p=newblk; p<&(newblk[JunctionBlockAllocSize]); p++) + { + p->p1 = (Node *)FreeList; /* add all new Junction nodes to FreeList */ + FreeList = p; + } + } + p = FreeList; + FreeList = (Junction *)FreeList->p1;/* remove a Junction node */ + p->p1 = NULL; /* NULL the ptr we used */ + + p->ntype = nJunction; p->visited = 0; + p->jtype = Generic; + p->rname = CurRule; + p->file = CurFile; + p->line = zzline; + p->exception_label = NULL; + p->fset = (set *) calloc(CLL_k+1, sizeof(set)); + require(p->fset!=NULL, "cannot allocate fset in newJunction"); + + return p; +} + +ActionNode * +#ifdef __STDC__ +newActionNode( void ) +#else +newActionNode( ) +#endif +{ + static ActionNode *FreeList = NULL; + ActionNode *p, *newblk; + + if ( FreeList == NULL ) + { + newblk = (ActionNode *)calloc(ActionBlockAllocSize, sizeof(ActionNode)); + if ( newblk == NULL ) + fatal_internal(eMsg1("out of memory while building rule '%s'",CurRule)); + for (p=newblk; p<&(newblk[ActionBlockAllocSize]); p++) + { + p->next = (Node *)FreeList; /* add all new Action nodes to FreeList */ + FreeList = p; + } + } + p = FreeList; + FreeList = (ActionNode *)FreeList->next;/* remove an Action node */ + p->ntype = nAction; + p->next = NULL; /* NULL the ptr we used */ + p->done = 0; + p->pred_fail = NULL; + p->guardpred = NULL; + + return p; +} + +/* + * allocate the array of locks (1..CLL_k) used to inhibit infinite recursion. + * Infinite recursion can occur in (..)* blocks, FIRST calcs and FOLLOW calcs. + * Therefore, we need locks on aLoopBlk, RuleBlk, EndRule nodes. + * + * if ( lock[k]==TRUE ) then we have been here before looking for k tokens + * of lookahead. + */ +char * +#ifdef __STDC__ +makelocks( void ) +#else +makelocks( ) +#endif +{ + char *p = (char *) calloc(CLL_k+1, sizeof(char)); + require(p!=NULL, "cannot allocate lock array"); + + return p; +}