]>
git.proxmox.com Git - mirror_edk2.git/blob - Tools/Source/TianoTools/Pccts/antlr/build.c
2 * build.c -- functions associated with building syntax diagrams.
6 * We reserve no LEGAL rights to the Purdue Compiler Construction Tool
7 * Set (PCCTS) -- PCCTS is in the public domain. An individual or
8 * company may do whatever they wish with source code distributed with
9 * PCCTS or the code generated by PCCTS, including the incorporation of
10 * PCCTS, or its output, into commerical software.
12 * We encourage users to develop software with PCCTS. However, we do ask
13 * that credit is given to us for developing PCCTS. By "credit",
14 * we mean that if you incorporate our source code into one of your
15 * programs (commercial product, research project, or otherwise) that you
16 * acknowledge this fact somewhere in the documentation, research report,
17 * etc... If you like PCCTS and have developed a nice tool with the
18 * output, please mention that you developed it using PCCTS. In
19 * addition, we ask that this header remain intact in our source code.
20 * As long as these guidelines are kept, we expect to continue enhancing
21 * this system and expect to make other tools available as they are
26 * Parr Research Corporation
27 * with Purdue University and AHPCRC, University of Minnesota
41 #define SetBlk(g, t, approx, first_set_symbol) { \
42 ((Junction *)g.left)->jtype = t; \
43 ((Junction *)g.left)->approx = approx; \
44 ((Junction *)g.left)->pFirstSetSymbol = first_set_symbol; \
45 ((Junction *)g.left)->end = (Junction *) g.right; \
46 ((Junction *)g.right)->jtype = EndBlk;}
48 /* Add the parameter string 'parm' to the parms field of a block-type junction
49 * g.left points to the sentinel node on a block. i.e. g.left->p1 points to
50 * the actual junction with its jtype == some block-type.
54 addParm( Node
*p
, char *parm
)
61 char *q
= (char *) malloc( strlen(parm
) + 1 );
62 require(p
!=NULL
, "addParm: NULL object\n");
63 require(q
!=NULL
, "addParm: unable to alloc parameter\n");
66 if ( p
->ntype
== nRuleRef
)
68 ((RuleRefNode
*)p
)->parms
= q
;
70 else if ( p
->ntype
== nJunction
)
72 ((Junction
*)p
)->parm
= q
; /* only one parameter allowed on subrules */
74 else fatal_internal("addParm: invalid node for adding parm");
78 * Build an action node for the syntax diagram
80 * buildAction(ACTION) ::= --o-->ACTION-->o--
82 * Where o is a junction node.
86 buildAction( char *action
, int file
, int line
, int is_predicate
)
88 buildAction( action
, file
, line
, is_predicate
)
98 require(action
!=NULL
, "buildAction: invalid action");
103 a
->action
= (char *) malloc( strlen(action
)+1 );
104 require(a
->action
!=NULL
, "buildAction: cannot alloc space for action\n");
105 strcpy(a
->action
, action
);
107 a
->next
= (Node
*) j2
;
108 a
->is_predicate
= is_predicate
;
111 PredEntry
*predEntry
;
117 t
=key
=(char *)calloc(1,strlen(a
->action
)+1);
119 for (u
=a
->action
; *u
!= '\0' ; u
++) {
121 if (t
==key
&& *u
=='!') {
132 predEntry
=(PredEntry
*)hash_get(Pname
,key
);
133 a
->predEntry
=predEntry
;
134 if (predEntry
!= NULL
) a
->inverted
=inverted
;
136 /* MR12c */ char *strStart
=a
->action
;
137 /* MR12c */ char *strEnd
;
138 /* MR12c */ strEnd
=strStart
+strlen(strStart
)-1;
139 /* MR12c */ for ( ; strEnd
>= strStart
&& isspace(*strEnd
); strEnd
--) *strEnd
=0;
140 /* MR12c */ while (*strStart
!= '\0' && isspace(*strStart
)) strStart
++;
141 /* MR12c */ if (ci_strequ(strStart
,"nohoist")) {
142 /* MR12c */ a
->noHoist
=1;
146 g
.left
= (Node
*) j1
; g
.right
= (Node
*) j2
;
149 a
->rname
= CurRule
; /* MR10 */
154 * Build a token node for the syntax diagram
156 * buildToken(TOKEN) ::= --o-->TOKEN-->o--
158 * Where o is a junction node.
162 buildToken( char *text
)
171 require(text
!=NULL
, "buildToken: invalid token name");
176 t
->altstart
= CurAltStart
;
177 if ( *text
== '"' ) {t
->label
=FALSE
; t
->token
= addTexpr( text
);}
178 else {t
->label
=TRUE
; t
->token
= addTname( text
);}
180 t
->next
= (Node
*) j2
;
181 g
.left
= (Node
*) j1
; g
.right
= (Node
*) j2
;
186 * Build a wild-card node for the syntax diagram
188 * buildToken(TOKEN) ::= --o-->'.'-->o--
190 * Where o is a junction node.
194 buildWildCard( char *text
)
196 buildWildCard( text
)
205 require(text
!=NULL
, "buildWildCard: invalid token name");
211 /* If the ref a wild card, make a token class for it */
212 if ( Tnum(WildCardString
) == 0 )
215 w
->tok
= addTname( WildCardString
);
216 set_orel(w
->tok
, &imag_tokens
);
217 set_orel(w
->tok
, &tokclasses
);
218 WildCardToken
= w
->tok
;
219 require((p
=(TermEntry
*)hash_get(Tname
, WildCardString
)) != NULL
,
220 "hash table mechanism is broken");
221 p
->classname
= 1; /* entry is class name, not token */
222 p
->tclass
= w
; /* save ptr to this tclass def */
223 list_add(&tclasses
, (char *)w
);
226 p
=(TermEntry
*)hash_get(Tname
, WildCardString
);
227 require( p
!= NULL
, "hash table mechanism is broken");
235 t
->altstart
= CurAltStart
;
237 t
->next
= (Node
*) j2
;
238 g
.left
= (Node
*) j1
; g
.right
= (Node
*) j2
;
244 setUpperRange(TokNode
*t
, char *text
)
246 setUpperRange(t
, text
)
251 require(t
!=NULL
, "setUpperRange: NULL token node");
252 require(text
!=NULL
, "setUpperRange: NULL token string");
254 if ( *text
== '"' ) {t
->upper_range
= addTexpr( text
);}
255 else {t
->upper_range
= addTname( text
);}
259 * Build a rule reference node of the syntax diagram
261 * buildRuleRef(RULE) ::= --o-->RULE-->o--
263 * Where o is a junction node.
265 * If rule 'text' has been defined already, don't alloc new space to store string.
266 * Set r->text to point to old copy in string table.
270 buildRuleRef( char *text
)
280 require(text
!=NULL
, "buildRuleRef: invalid rule name");
285 r
->altstart
= CurAltStart
;
287 if ( (p
=(RuleEntry
*)hash_get(Rname
, text
)) != NULL
) r
->text
= p
->str
;
288 else r
->text
= mystrdup( text
);
290 r
->next
= (Node
*) j2
;
291 g
.left
= (Node
*) j1
; g
.right
= (Node
*) j2
;
296 * Or two subgraphs into one graph via:
298 * Or(G1, G2) ::= --o-G1-o--
303 * Set the altnum of junction starting G2 to 1 + altnum of junction starting G1.
304 * If, however, the G1 altnum is 0, make it 1 and then
305 * make G2 altnum = G1 altnum + 1.
309 Or( Graph g1
, Graph g2
)
317 require(g1
.left
!= NULL
, "Or: invalid graph");
318 require(g2
.left
!= NULL
&& g2
.right
!= NULL
, "Or: invalid graph");
320 ((Junction
*)g1
.left
)->p2
= g2
.left
;
321 ((Junction
*)g2
.right
)->p1
= g1
.right
;
323 if ( ((Junction
*)g1
.left
)->altnum
== 0 ) ((Junction
*)g1
.left
)->altnum
= 1;
324 ((Junction
*)g2
.left
)->altnum
= ((Junction
*)g1
.left
)->altnum
+ 1;
331 * Catenate two subgraphs
333 * Cat(G1, G2) ::= --o-G1-o-->o-G2-o--
334 * Cat(NULL,G2)::= --o-G2-o--
335 * Cat(G1,NULL)::= --o-G1-o--
339 Cat( Graph g1
, Graph g2
)
348 if ( g1
.left
== NULL
&& g1
.right
== NULL
) return g2
;
349 if ( g2
.left
== NULL
&& g2
.right
== NULL
) return g1
;
350 ((Junction
*)g1
.right
)->p1
= g2
.left
;
357 * Make a subgraph an optional block
359 * makeOpt(G) ::= --o-->o-G-o-->o--
364 * Note that this constructs {A|B|...|Z} as if (A|B|...|Z|) was found.
366 * The node on the far right is added so that every block owns its own
371 makeOpt( Graph g1
, int approx
, char * pFirstSetSymbol
)
373 makeOpt( g1
, approx
, pFirstSetSymbol
)
376 char * pFirstSetSymbol
;
381 require(g1
.left
!= NULL
&& g1
.right
!= NULL
, "makeOpt: invalid graph");
385 ((Junction
*)g1
.right
)->p1
= (Node
*) j2
; /* add node to G at end */
389 * There is code in genBlk which recognizes the node created
390 * by emptyAlt() as a special case and bypasses it. We don't
391 * want this to happen for the optBlk.
394 g
= emptyAlt3(); /* MR21 */
395 if ( ((Junction
*)g1
.left
)->altnum
== 0 ) ((Junction
*)g1
.left
)->altnum
= 1;
396 ((Junction
*)g
.left
)->altnum
= ((Junction
*)g1
.left
)->altnum
+ 1;
397 for(p
=(Junction
*)g1
.left
; p
->p2
!=NULL
; p
=(Junction
*)p
->p2
)
398 {;} /* find last alt */
399 p
->p2
= g
.left
; /* add optional alternative */
400 ((Junction
*)g
.right
)->p1
= (Node
*)j2
; /* opt alt points to EndBlk */
401 g1
.right
= (Node
*)j2
;
402 SetBlk(g1
, aOptBlk
, approx
, pFirstSetSymbol
);
403 j1
->p1
= g1
.left
; /* add generic node in front */
404 g
.left
= (Node
*) j1
;
410 * Make a graph into subblock
412 * makeBlk(G) ::= --o-->o-G-o-->o--
414 * The node on the far right is added so that every block owns its own
419 makeBlk( Graph g1
, int approx
, char * pFirstSetSymbol
)
421 makeBlk( g1
, approx
, pFirstSetSymbol
)
424 char * pFirstSetSymbol
;
429 require(g1
.left
!= NULL
&& g1
.right
!= NULL
, "makeBlk: invalid graph");
433 ((Junction
*)g1
.right
)->p1
= (Node
*) j2
; /* add node to G at end */
434 g1
.right
= (Node
*)j2
;
435 SetBlk(g1
, aSubBlk
, approx
, pFirstSetSymbol
);
436 j
->p1
= g1
.left
; /* add node in front */
444 * Make a subgraph into a loop (closure) block -- (...)*
446 * makeLoop(G) ::= |---|
448 * --o-->o-->o-G-o-->o--
453 * After making loop, always place generic node out front. It becomes
454 * the start of enclosing block. The aLoopBlk is the target of the loop.
456 * Loop blks have TWO EndBlk nodes--the far right and the node that loops back
457 * to the aLoopBlk node. Node with which we can branch past loop == aLoopBegin and
458 * one which is loop target == aLoopBlk.
459 * The branch-past (initial) aLoopBegin node has end
460 * pointing to the last EndBlk node. The loop-target node has end==NULL.
462 * Loop blocks have a set of locks (from 1..CLL_k) on the aLoopBlk node.
466 makeLoop( Graph g1
, int approx
, char * pFirstSetSymbol
)
468 makeLoop( g1
, approx
, pFirstSetSymbol
)
471 char * pFirstSetSymbol
;
474 Junction
*back
, *front
, *begin
;
476 require(g1
.left
!= NULL
&& g1
.right
!= NULL
, "makeLoop: invalid graph");
478 back
= newJunction();
479 front
= newJunction();
480 begin
= newJunction();
482 ((Junction
*)g1
.right
)->p2
= g1
.left
; /* add loop branch to G */
483 ((Junction
*)g1
.right
)->p1
= (Node
*) back
; /* add node to G at end */
484 ((Junction
*)g1
.right
)->jtype
= EndBlk
; /* mark 1st EndBlk node */
485 ((Junction
*)g1
.left
)->jtype
= aLoopBlk
; /* mark 2nd aLoopBlk node */
486 ((Junction
*)g1
.left
)->end
= (Junction
*) g1
.right
;
487 ((Junction
*)g1
.left
)->lock
= makelocks();
488 ((Junction
*)g1
.left
)->pred_lock
= makelocks();
489 g1
.right
= (Node
*) back
;
490 begin
->p1
= (Node
*) g1
.left
;
491 g1
.left
= (Node
*) begin
;
492 begin
->p2
= (Node
*) g
.left
; /* make bypass arc */
493 ((Junction
*)g
.right
)->p1
= (Node
*) back
;
494 SetBlk(g1
, aLoopBegin
, approx
, pFirstSetSymbol
);
495 front
->p1
= g1
.left
; /* add node to front */
496 g1
.left
= (Node
*) front
;
502 * Make a subgraph into a plus block -- (...)+ -- 1 or more times
504 * makePlus(G) ::= |---|
508 * After making loop, always place generic node out front. It becomes
509 * the start of enclosing block. The aPlusBlk is the target of the loop.
511 * Plus blks have TWO EndBlk nodes--the far right and the node that loops back
512 * to the aPlusBlk node.
514 * Plus blocks have a set of locks (from 1..CLL_k) on the aPlusBlk node.
518 makePlus( Graph g1
, int approx
, char * pFirstSetSymbol
)
520 makePlus( g1
, approx
, pFirstSetSymbol
)
523 char * pFirstSetSymbol
;
526 int has_empty_alt_already
= 0;
528 Junction
*j2
, *j3
, *first_alt
;
529 Junction
*last_alt
=NULL
, *p
;
530 require(g1
.left
!= NULL
&& g1
.right
!= NULL
, "makePlus: invalid graph");
532 first_alt
= (Junction
*)g1
.left
;
535 if ( ((Junction
*)g1
.left
)->altnum
== 0 ) ((Junction
*)g1
.left
)->altnum
= 1;
536 ((Junction
*)g1
.right
)->p2
= g1
.left
; /* add loop branch to G */
537 ((Junction
*)g1
.right
)->p1
= (Node
*) j2
; /* add node to G at end */
538 ((Junction
*)g1
.right
)->jtype
= EndBlk
; /* mark 1st EndBlk node */
539 g1
.right
= (Node
*) j2
;
540 SetBlk(g1
, aPlusBlk
, approx
, pFirstSetSymbol
);
541 ((Junction
*)g1
.left
)->lock
= makelocks();
542 ((Junction
*)g1
.left
)->pred_lock
= makelocks();
543 j3
->p1
= g1
.left
; /* add node to front */
544 g1
.left
= (Node
*) j3
;
546 /* add an optional branch which is the "exit" branch of loop */
547 /* FIRST, check to ensure that there does not already exist
551 for(p
=first_alt
; p
!=NULL
; p
=(Junction
*)p
->p2
)
553 if ( p
->p1
->ntype
== nJunction
&&
555 ((Junction
*)p
->p1
)->jtype
==Generic
&&
556 ((Junction
*)p
->p1
)->p1
!=NULL
&&
557 ((Junction
*)((Junction
*)p
->p1
)->p1
)->jtype
==EndBlk
)
559 has_empty_alt_already
= 1;
563 if ( !has_empty_alt_already
)
565 require(last_alt
!=NULL
, "last_alt==NULL; bad (..)+");
567 last_alt
->p2
= g
.left
;
568 ((Junction
*)g
.right
)->p1
= (Node
*) j2
;
570 /* make sure lookahead computation ignores this alt for
571 * FIRST("(..)+"); but it's still used for computing the FIRST
572 * of each alternative.
574 ((Junction
*)g
.left
)->ignore
= 1;
581 * Return an optional path: --o-->o--
596 j1
->p1
= (Node
*) j2
;
597 g
.left
= (Node
*) j1
;
598 g
.right
= (Node
*) j2
;
605 * There is code in genBlk which recognizes the node created
606 * by emptyAlt() as a special case and bypasses it. We don't
607 * want this to happen for the optBlk.
617 Junction
*j1
, *j2
, *j3
;
623 j1
->p1
= (Node
*) j2
;
624 j2
->p1
= (Node
*) j3
;
625 g
.left
= (Node
*) j1
;
626 g
.right
= (Node
*) j3
;
631 /* N o d e A l l o c a t i o n */
640 static TokNode
*FreeList
= NULL
;
643 if ( FreeList
== NULL
)
645 newblk
= (TokNode
*)calloc(TokenBlockAllocSize
, sizeof(TokNode
));
646 if ( newblk
== NULL
)
647 fatal_internal(eMsg1("out of memory while building rule '%s'",CurRule
));
648 for (p
=newblk
; p
<&(newblk
[TokenBlockAllocSize
]); p
++)
650 p
->next
= (Node
*)FreeList
; /* add all new token nodes to FreeList */
655 FreeList
= (TokNode
*)FreeList
->next
;/* remove a TokNode node */
656 p
->next
= NULL
; /* NULL the ptr we used */
657 memset( (char *) p
, 0, sizeof(TokNode
)); /* MR10 */
674 static RuleRefNode
*FreeList
= NULL
;
675 RuleRefNode
*p
, *newblk
;
677 if ( FreeList
== NULL
)
679 newblk
= (RuleRefNode
*)calloc(RRefBlockAllocSize
, sizeof(RuleRefNode
));
680 if ( newblk
== NULL
)
681 fatal_internal(eMsg1("out of memory while building rule '%s'",CurRule
));
682 for (p
=newblk
; p
<&(newblk
[RRefBlockAllocSize
]); p
++)
684 p
->next
= (Node
*)FreeList
; /* add all new rref nodes to FreeList */
689 FreeList
= (RuleRefNode
*)FreeList
->next
;/* remove a Junction node */
690 p
->next
= NULL
; /* NULL the ptr we used */
691 memset( (char *) p
, 0, sizeof(RuleRefNode
)); /* MR10 */
696 p
->astnode
= ASTinclude
;
702 static int junctionSeqNumber
=0; /* MR10 */
711 static Junction
*FreeList
= NULL
;
712 Junction
*p
, *newblk
;
714 if ( FreeList
== NULL
)
716 newblk
= (Junction
*)calloc(JunctionBlockAllocSize
, sizeof(Junction
));
717 if ( newblk
== NULL
)
718 fatal_internal(eMsg1("out of memory while building rule '%s'",CurRule
));
719 for (p
=newblk
; p
<&(newblk
[JunctionBlockAllocSize
]); p
++)
721 p
->p1
= (Node
*)FreeList
; /* add all new Junction nodes to FreeList */
726 FreeList
= (Junction
*)FreeList
->p1
;/* remove a Junction node */
727 p
->p1
= NULL
; /* NULL the ptr we used */
728 memset( (char *) p
, 0, sizeof(Junction
)); /* MR10 */
729 p
->ntype
= nJunction
;
735 p
->exception_label
= NULL
;
736 p
->fset
= (set
*) calloc(CLL_k
+1, sizeof(set
));
737 require(p
->fset
!=NULL
, "cannot allocate fset in newJunction");
738 p
->seq
=++junctionSeqNumber
; /* MR10 */
745 newActionNode( void )
750 static ActionNode
*FreeList
= NULL
;
751 ActionNode
*p
, *newblk
;
753 if ( FreeList
== NULL
)
755 newblk
= (ActionNode
*)calloc(ActionBlockAllocSize
, sizeof(ActionNode
));
756 if ( newblk
== NULL
)
757 fatal_internal(eMsg1("out of memory while building rule '%s'",CurRule
));
758 for (p
=newblk
; p
<&(newblk
[ActionBlockAllocSize
]); p
++)
760 p
->next
= (Node
*)FreeList
; /* add all new Action nodes to FreeList */
765 FreeList
= (ActionNode
*)FreeList
->next
;/* remove an Action node */
766 memset( (char *) p
, 0, sizeof(ActionNode
)); /* MR10 */
768 p
->next
= NULL
; /* NULL the ptr we used */
772 p
->ampersandPred
= NULL
;
777 * allocate the array of locks (1..CLL_k) used to inhibit infinite recursion.
778 * Infinite recursion can occur in (..)* blocks, FIRST calcs and FOLLOW calcs.
779 * Therefore, we need locks on aLoopBlk, RuleBlk, EndRule nodes.
781 * if ( lock[k]==TRUE ) then we have been here before looking for k tokens
791 char *p
= (char *) calloc(CLL_k
+1, sizeof(char));
792 require(p
!=NULL
, "cannot allocate lock array");
798 ** #ifdef __USE_PROTOS
799 ** void my_memset(char *p
,char value
,int count
)
801 ** void my_memset(p
,value
,count
)
809 ** for (i
=0; i
<count
; i
++) {