2 * build.c -- functions associated with building syntax diagrams.
4 * $Id: build.c,v 1.3 95/06/15 18:07:00 parrt Exp $
9 * We reserve no LEGAL rights to the Purdue Compiler Construction Tool
10 * Set (PCCTS) -- PCCTS is in the public domain. An individual or
11 * company may do whatever they wish with source code distributed with
12 * PCCTS or the code generated by PCCTS, including the incorporation of
13 * PCCTS, or its output, into commerical software.
15 * We encourage users to develop software with PCCTS. However, we do ask
16 * that credit is given to us for developing PCCTS. By "credit",
17 * we mean that if you incorporate our source code into one of your
18 * programs (commercial product, research project, or otherwise) that you
19 * acknowledge this fact somewhere in the documentation, research report,
20 * etc... If you like PCCTS and have developed a nice tool with the
21 * output, please mention that you developed it using PCCTS. In
22 * addition, we ask that this header remain intact in our source code.
23 * As long as these guidelines are kept, we expect to continue enhancing
24 * this system and expect to make other tools available as they are
29 * Parr Research Corporation
30 * with Purdue University and AHPCRC, University of Minnesota
45 #define SetBlk(g, t, approx) { \
46 ((Junction *)g.left)->jtype = t; \
47 ((Junction *)g.left)->approx = approx; \
48 ((Junction *)g.left)->end = (Junction *) g.right; \
49 ((Junction *)g.right)->jtype = EndBlk;}
51 /* Add the parameter string 'parm' to the parms field of a block-type junction
52 * g.left points to the sentinel node on a block. i.e. g.left->p1 points to
53 * the actual junction with its jtype == some block-type.
57 addParm( Node *p, char *parm )
64 char *q = (char *) malloc( strlen(parm) + 1 );
65 require(p!=NULL, "addParm: NULL object\n");
66 require(q!=NULL, "addParm: unable to alloc parameter\n");
69 if ( p->ntype == nRuleRef )
71 ((RuleRefNode *)p)->parms = q;
73 else if ( p->ntype == nJunction )
75 ((Junction *)p)->parm = q; /* only one parameter allowed on subrules */
77 else fatal_internal("addParm: invalid node for adding parm");
81 * Build an action node for the syntax diagram
83 * buildAction(ACTION) ::= --o-->ACTION-->o--
85 * Where o is a junction node.
89 buildAction( char *action, int file, int line, int is_predicate )
91 buildAction( action, file, line, is_predicate )
101 require(action!=NULL, "buildAction: invalid action");
106 a->action = (char *) malloc( strlen(action)+1 );
107 require(a->action!=NULL, "buildAction: cannot alloc space for action\n");
108 strcpy(a->action, action);
110 a->next = (Node *) j2;
111 a->is_predicate = is_predicate;
112 g.left = (Node *) j1; g.right = (Node *) j2;
115 a->rname = "not filled in";
120 * Build a token node for the syntax diagram
122 * buildToken(TOKEN) ::= --o-->TOKEN-->o--
124 * Where o is a junction node.
128 buildToken( char *text )
137 require(text!=NULL, "buildToken: invalid token name");
142 t->altstart = CurAltStart;
143 if ( *text == '"' ) {t->label=FALSE; t->token = addTexpr( text );}
144 else {t->label=TRUE; t->token = addTname( text );}
146 t->next = (Node *) j2;
147 g.left = (Node *) j1; g.right = (Node *) j2;
152 * Build a wild-card node for the syntax diagram
154 * buildToken(TOKEN) ::= --o-->'.'-->o--
156 * Where o is a junction node.
160 buildWildCard( char *text )
162 buildWildCard( text )
171 require(text!=NULL, "buildWildCard: invalid token name");
177 /* If the ref a wild card, make a token class for it */
178 if ( Tnum(WildCardString) == 0 )
181 w->tok = addTname( WildCardString );
182 set_orel(w->tok, &imag_tokens);
183 set_orel(w->tok, &tokclasses);
184 WildCardToken = w->tok;
185 require((p=(TermEntry *)hash_get(Tname, WildCardString)) != NULL,
186 "hash table mechanism is broken");
187 p->classname = 1; /* entry is class name, not token */
188 p->tclass = w; /* save ptr to this tclass def */
189 list_add(&tclasses, (char *)w);
192 p=(TermEntry *)hash_get(Tname, WildCardString);
193 require( p!= NULL, "hash table mechanism is broken");
201 t->altstart = CurAltStart;
203 t->next = (Node *) j2;
204 g.left = (Node *) j1; g.right = (Node *) j2;
210 setUpperRange(TokNode *t, char *text)
212 setUpperRange(t, text)
217 require(t!=NULL, "setUpperRange: NULL token node");
218 require(text!=NULL, "setUpperRange: NULL token string");
220 if ( *text == '"' ) {t->upper_range = addTexpr( text );}
221 else {t->upper_range = addTname( text );}
225 * Build a rule reference node of the syntax diagram
227 * buildRuleRef(RULE) ::= --o-->RULE-->o--
229 * Where o is a junction node.
231 * If rule 'text' has been defined already, don't alloc new space to store string.
232 * Set r->text to point to old copy in string table.
236 buildRuleRef( char *text )
246 require(text!=NULL, "buildRuleRef: invalid rule name");
251 r->altstart = CurAltStart;
253 if ( (p=(RuleEntry *)hash_get(Rname, text)) != NULL ) r->text = p->str;
254 else r->text = mystrdup( text );
256 r->next = (Node *) j2;
257 g.left = (Node *) j1; g.right = (Node *) j2;
262 * Or two subgraphs into one graph via:
264 * Or(G1, G2) ::= --o-G1-o--
269 * Set the altnum of junction starting G2 to 1 + altnum of junction starting G1.
270 * If, however, the G1 altnum is 0, make it 1 and then
271 * make G2 altnum = G1 altnum + 1.
275 Or( Graph g1, Graph g2 )
283 require(g1.left != NULL, "Or: invalid graph");
284 require(g2.left != NULL && g2.right != NULL, "Or: invalid graph");
286 ((Junction *)g1.left)->p2 = g2.left;
287 ((Junction *)g2.right)->p1 = g1.right;
289 if ( ((Junction *)g1.left)->altnum == 0 ) ((Junction *)g1.left)->altnum = 1;
290 ((Junction *)g2.left)->altnum = ((Junction *)g1.left)->altnum + 1;
297 * Catenate two subgraphs
299 * Cat(G1, G2) ::= --o-G1-o-->o-G2-o--
300 * Cat(NULL,G2)::= --o-G2-o--
301 * Cat(G1,NULL)::= --o-G1-o--
305 Cat( Graph g1, Graph g2 )
314 if ( g1.left == NULL && g1.right == NULL ) return g2;
315 if ( g2.left == NULL && g2.right == NULL ) return g1;
316 ((Junction *)g1.right)->p1 = g2.left;
323 * Make a subgraph an optional block
325 * makeOpt(G) ::= --o-->o-G-o-->o--
330 * Note that this constructs {A|B|...|Z} as if (A|B|...|Z|) was found.
332 * The node on the far right is added so that every block owns its own
337 makeOpt( Graph g1, int approx )
339 makeOpt( g1, approx )
346 require(g1.left != NULL && g1.right != NULL, "makeOpt: invalid graph");
350 ((Junction *)g1.right)->p1 = (Node *) j2; /* add node to G at end */
352 if ( ((Junction *)g1.left)->altnum == 0 ) ((Junction *)g1.left)->altnum = 1;
353 ((Junction *)g.left)->altnum = ((Junction *)g1.left)->altnum + 1;
354 for(p=(Junction *)g1.left; p->p2!=NULL; p=(Junction *)p->p2)
355 {;} /* find last alt */
356 p->p2 = g.left; /* add optional alternative */
357 ((Junction *)g.right)->p1 = (Node *)j2; /* opt alt points to EndBlk */
358 g1.right = (Node *)j2;
359 SetBlk(g1, aOptBlk, approx);
360 j1->p1 = g1.left; /* add generic node in front */
361 g.left = (Node *) j1;
368 * Make a graph into subblock
370 * makeBlk(G) ::= --o-->o-G-o-->o--
372 * The node on the far right is added so that every block owns its own
377 makeBlk( Graph g1, int approx )
379 makeBlk( g1, approx )
386 require(g1.left != NULL && g1.right != NULL, "makeBlk: invalid graph");
390 ((Junction *)g1.right)->p1 = (Node *) j2; /* add node to G at end */
391 g1.right = (Node *)j2;
392 SetBlk(g1, aSubBlk, approx);
393 j->p1 = g1.left; /* add node in front */
401 * Make a subgraph into a loop (closure) block -- (...)*
403 * makeLoop(G) ::= |---|
405 * --o-->o-->o-G-o-->o--
410 * After making loop, always place generic node out front. It becomes
411 * the start of enclosing block. The aLoopBlk is the target of the loop.
413 * Loop blks have TWO EndBlk nodes--the far right and the node that loops back
414 * to the aLoopBlk node. Node with which we can branch past loop == aLoopBegin and
415 * one which is loop target == aLoopBlk.
416 * The branch-past (initial) aLoopBegin node has end
417 * pointing to the last EndBlk node. The loop-target node has end==NULL.
419 * Loop blocks have a set of locks (from 1..CLL_k) on the aLoopBlk node.
423 makeLoop( Graph g1, int approx )
425 makeLoop( g1, approx )
430 Junction *back, *front, *begin;
432 require(g1.left != NULL && g1.right != NULL, "makeLoop: invalid graph");
434 back = newJunction();
435 front = newJunction();
436 begin = newJunction();
438 ((Junction *)g1.right)->p2 = g1.left; /* add loop branch to G */
439 ((Junction *)g1.right)->p1 = (Node *) back; /* add node to G at end */
440 ((Junction *)g1.right)->jtype = EndBlk; /* mark 1st EndBlk node */
441 ((Junction *)g1.left)->jtype = aLoopBlk; /* mark 2nd aLoopBlk node */
442 ((Junction *)g1.left)->end = (Junction *) g1.right;
443 ((Junction *)g1.left)->lock = makelocks();
444 ((Junction *)g1.left)->pred_lock = makelocks();
445 g1.right = (Node *) back;
446 begin->p1 = (Node *) g1.left;
447 g1.left = (Node *) begin;
448 begin->p2 = (Node *) g.left; /* make bypass arc */
449 ((Junction *)g.right)->p1 = (Node *) back;
450 SetBlk(g1, aLoopBegin, approx);
451 front->p1 = g1.left; /* add node to front */
452 g1.left = (Node *) front;
458 * Make a subgraph into a plus block -- (...)+ -- 1 or more times
460 * makePlus(G) ::= |---|
464 * After making loop, always place generic node out front. It becomes
465 * the start of enclosing block. The aPlusBlk is the target of the loop.
467 * Plus blks have TWO EndBlk nodes--the far right and the node that loops back
468 * to the aPlusBlk node.
470 * Plus blocks have a set of locks (from 1..CLL_k) on the aPlusBlk node.
474 makePlus( Graph g1, int approx )
476 makePlus( g1, approx )
481 int has_empty_alt_already = 0;
483 Junction *j2, *j3, *first_alt;
484 Junction *last_alt, *p;
485 require(g1.left != NULL && g1.right != NULL, "makePlus: invalid graph");
487 first_alt = (Junction *)g1.left;
490 if ( ((Junction *)g1.left)->altnum == 0 ) ((Junction *)g1.left)->altnum = 1;
491 ((Junction *)g1.right)->p2 = g1.left; /* add loop branch to G */
492 ((Junction *)g1.right)->p1 = (Node *) j2; /* add node to G at end */
493 ((Junction *)g1.right)->jtype = EndBlk; /* mark 1st EndBlk node */
494 g1.right = (Node *) j2;
495 SetBlk(g1, aPlusBlk, approx);
496 ((Junction *)g1.left)->lock = makelocks();
497 ((Junction *)g1.left)->pred_lock = makelocks();
498 j3->p1 = g1.left; /* add node to front */
499 g1.left = (Node *) j3;
501 /* add an optional branch which is the "exit" branch of loop */
502 /* FIRST, check to ensure that there does not already exist
506 for(p=first_alt; p!=NULL; p=(Junction *)p->p2)
508 if ( p->p1->ntype == nJunction &&
510 ((Junction *)p->p1)->jtype==Generic &&
511 ((Junction *)p->p1)->p1!=NULL &&
512 ((Junction *)((Junction *)p->p1)->p1)->jtype==EndBlk )
514 has_empty_alt_already = 1;
518 if ( !has_empty_alt_already )
520 require(last_alt!=NULL, "last_alt==NULL; bad (..)+");
522 last_alt->p2 = g.left;
523 ((Junction *)g.right)->p1 = (Node *) j2;
525 /* make sure lookahead computation ignores this alt for
526 * FIRST("(..)+"); but it's still used for computing the FIRST
527 * of each alternative.
529 ((Junction *)g.left)->ignore = 1;
536 * Return an optional path: --o-->o--
550 j1->p1 = (Node *) j2;
551 g.left = (Node *) j1;
552 g.right = (Node *) j2;
557 /* N o d e A l l o c a t i o n */
566 static TokNode *FreeList = NULL;
569 if ( FreeList == NULL )
571 newblk = (TokNode *)calloc(TokenBlockAllocSize, sizeof(TokNode));
572 if ( newblk == NULL )
573 fatal_internal(eMsg1("out of memory while building rule '%s'",CurRule));
574 for (p=newblk; p<&(newblk[TokenBlockAllocSize]); p++)
576 p->next = (Node *)FreeList; /* add all new token nodes to FreeList */
581 FreeList = (TokNode *)FreeList->next;/* remove a TokNode node */
582 p->next = NULL; /* NULL the ptr we used */
600 static RuleRefNode *FreeList = NULL;
601 RuleRefNode *p, *newblk;
603 if ( FreeList == NULL )
605 newblk = (RuleRefNode *)calloc(RRefBlockAllocSize, sizeof(RuleRefNode));
606 if ( newblk == NULL )
607 fatal_internal(eMsg1("out of memory while building rule '%s'",CurRule));
608 for (p=newblk; p<&(newblk[RRefBlockAllocSize]); p++)
610 p->next = (Node *)FreeList; /* add all new rref nodes to FreeList */
615 FreeList = (RuleRefNode *)FreeList->next;/* remove a Junction node */
616 p->next = NULL; /* NULL the ptr we used */
622 p->astnode = ASTinclude;
635 static Junction *FreeList = NULL;
636 Junction *p, *newblk;
638 if ( FreeList == NULL )
640 newblk = (Junction *)calloc(JunctionBlockAllocSize, sizeof(Junction));
641 if ( newblk == NULL )
642 fatal_internal(eMsg1("out of memory while building rule '%s'",CurRule));
643 for (p=newblk; p<&(newblk[JunctionBlockAllocSize]); p++)
645 p->p1 = (Node *)FreeList; /* add all new Junction nodes to FreeList */
650 FreeList = (Junction *)FreeList->p1;/* remove a Junction node */
651 p->p1 = NULL; /* NULL the ptr we used */
653 p->ntype = nJunction; p->visited = 0;
658 p->exception_label = NULL;
659 p->fset = (set *) calloc(CLL_k+1, sizeof(set));
660 require(p->fset!=NULL, "cannot allocate fset in newJunction");
667 newActionNode( void )
672 static ActionNode *FreeList = NULL;
673 ActionNode *p, *newblk;
675 if ( FreeList == NULL )
677 newblk = (ActionNode *)calloc(ActionBlockAllocSize, sizeof(ActionNode));
678 if ( newblk == NULL )
679 fatal_internal(eMsg1("out of memory while building rule '%s'",CurRule));
680 for (p=newblk; p<&(newblk[ActionBlockAllocSize]); p++)
682 p->next = (Node *)FreeList; /* add all new Action nodes to FreeList */
687 FreeList = (ActionNode *)FreeList->next;/* remove an Action node */
689 p->next = NULL; /* NULL the ptr we used */
698 * allocate the array of locks (1..CLL_k) used to inhibit infinite recursion.
699 * Infinite recursion can occur in (..)* blocks, FIRST calcs and FOLLOW calcs.
700 * Therefore, we need locks on aLoopBlk, RuleBlk, EndRule nodes.
702 * if ( lock[k]==TRUE ) then we have been here before looking for k tokens
712 char *p = (char *) calloc(CLL_k+1, sizeof(char));
713 require(p!=NULL, "cannot allocate lock array");