4 * Manage tokens, regular expressions.
5 * Print methods for debugging
6 * Compute follow lists onto tail ends of rules.
8 * The following functions are visible:
10 * int addTname(char *); Add token name
11 * int addTexpr(char *); Add token expression
12 * int Tnum(char *); Get number of expr/token
13 * void Tklink(char *, char *); Link a name with an expression
14 * int hasAction(expr); Does expr already have action assigned?
15 * void setHasAction(expr); Indicate that expr now has an action
16 * Entry *newEntry(char *,int); Create new table entry with certain size
17 * void list_add(ListNode **list, char *e)
18 * void list_apply(ListNode *list, void (*f)())
19 * void lexclass(char *m); switch to new/old lexical class
20 * void lexmode(int i); switch to old lexical class i
24 * We reserve no LEGAL rights to the Purdue Compiler Construction Tool
25 * Set (PCCTS) -- PCCTS is in the public domain. An individual or
26 * company may do whatever they wish with source code distributed with
27 * PCCTS or the code generated by PCCTS, including the incorporation of
28 * PCCTS, or its output, into commerical software.
30 * We encourage users to develop software with PCCTS. However, we do ask
31 * that credit is given to us for developing PCCTS. By "credit",
32 * we mean that if you incorporate our source code into one of your
33 * programs (commercial product, research project, or otherwise) that you
34 * acknowledge this fact somewhere in the documentation, research report,
35 * etc... If you like PCCTS and have developed a nice tool with the
36 * output, please mention that you developed it using PCCTS. In
37 * addition, we ask that this header remain intact in our source code.
38 * As long as these guidelines are kept, we expect to continue enhancing
39 * this system and expect to make other tools available as they are
44 * Parr Research Corporation
45 * with Purdue University and AHPCRC, University of Minnesota
60 static int tsize=TSChunk; /* size of token str arrays */
64 RemapForcedTokensInSyntaxDiagram(Node *);
66 RemapForcedTokensInSyntaxDiagram();
69 /* T o k e n M a n i p u l a t i o n */
72 * add token 't' to the TokenStr/Expr array. Make more room if necessary.
73 * 't' is either an expression or a token name.
75 * There is only one TokenStr array, but multiple ExprStr's. Therefore,
76 * for each lex class (element of lclass) we must extend the ExprStr array.
77 * ExprStr's and TokenStr are always all the same size.
79 * Also, there is a Texpr hash table for each automaton.
89 if ( TokenNum >= tsize ) /* terminal table overflow? */
94 more = TSChunk * (1 + ((TokenNum-tsize) / TSChunk));
96 TokenStr = (char **) realloc((char *)TokenStr, tsize*sizeof(char *));
97 require(TokenStr != NULL, "Ttrack: can't extend TokenStr");
98 for (i=0; i<NumLexClasses; i++)
100 lclass[i].exprs = (char **)
101 realloc((char *)lclass[i].exprs, tsize*sizeof(char *));
102 require(lclass[i].exprs != NULL, "Ttrack: can't extend ExprStr");
103 for (p= &lclass[i].exprs[tsize-more],j=1; j<=more; j++) *p++ = NULL;
105 for (p= &TokenStr[tsize-more],i=1; i<=more; i++) *p++ = NULL;
106 lexmode( CurrentLexClass ); /* reset ExprStr in case table moved */
108 /* note: we use the actual ExprStr/TokenStr array
109 * here as TokenInd doesn't exist yet
111 if ( *t == '"' ) ExprStr[TokenNum] = t;
112 else TokenStr[TokenNum] = t;
123 Expr *p = (Expr *) calloc(1, sizeof(Expr));
124 require(p!=NULL, "newExpr: cannot alloc Expr node");
127 p->lclass = CurrentLexClass;
131 /* switch to lexical class/mode m. This amounts to creating a new
132 * lex mode if one does not already exist and making ExprStr point
133 * to the correct char string array. We must also switch Texpr tables.
135 * BTW, we need multiple ExprStr arrays because more than one automaton
136 * may have the same label for a token, but with different expressions.
137 * We need to track an expr for each automaton. If we disallowed this
138 * feature, only one ExprStr would be required.
150 static char EOFSTR[] = "\"@\"";
152 if ( hash_get(Tname, m) != NULL )
154 warn(eMsg1("lexclass name conflicts with token/errclass label '%s'",m));
156 /* does m already exist? */
157 i = LexClassIndex(m);
158 if ( i != -1 ) {lexmode(i); return;}
159 /* must make new one */
161 CurrentLexClass = NumLexClasses-1;
162 require(NumLexClasses<=MaxLexClasses, "number of allowable lexclasses exceeded\nIncrease MaxLexClasses in generic.h and recompile all C files");
163 lclass[CurrentLexClass].classnum = m;
164 lclass[CurrentLexClass].exprs = (char **) calloc(tsize, sizeof(char *));
165 require(lclass[CurrentLexClass].exprs!=NULL,
166 "lexclass: cannot allocate ExprStr");
167 lclass[CurrentLexClass].htable = newHashTable();
168 ExprStr = lclass[CurrentLexClass].exprs;
169 Texpr = lclass[CurrentLexClass].htable;
170 /* define EOF for each automaton */
171 p = newTermEntry( EOFSTR );
172 p->token = EofToken; /* couldn't have remapped tokens yet, use EofToken */
173 hash_add(Texpr, EOFSTR, (Entry *)p);
174 list_add(&ExprOrder, (void *)newExpr(EOFSTR));
175 /* note: we use the actual ExprStr array
176 * here as TokenInd doesn't exist yet
178 ExprStr[EofToken] = EOFSTR;
189 require(i<NumLexClasses, "lexmode: invalid mode");
190 ExprStr = lclass[i].exprs;
191 Texpr = lclass[i].htable;
195 /* return index into lclass array of lexical class. return -1 if nonexistent */
198 LexClassIndex( char *cl )
206 for (i=0; i<NumLexClasses; i++)
208 if ( strcmp(lclass[i].classnum, cl) == 0 ) return i;
215 hasAction( char *expr )
222 require(expr!=NULL, "hasAction: invalid expr");
224 p = (TermEntry *) hash_get(Texpr, expr);
225 require(p!=NULL, eMsg1("hasAction: expr '%s' doesn't exist",expr));
226 return (p->action!=NULL);
231 setHasAction( char *expr, char *action )
233 setHasAction( expr, action )
239 require(expr!=NULL, "setHasAction: invalid expr");
241 p = (TermEntry *) hash_get(Texpr, expr);
242 require(p!=NULL, eMsg1("setHasAction: expr '%s' doesn't exist",expr));
248 newForcedToken(char *token, int tnum)
250 newForcedToken(token, tnum)
255 ForcedToken *ft = (ForcedToken *) calloc(1, sizeof(ForcedToken));
256 require(ft!=NULL, "out of memory");
263 * Make a token indirection array that remaps token numbers and then walk
264 * the appropriate symbol tables and SynDiag to change token numbers
268 RemapForcedTokens(void)
275 unsigned int max_token_number=0;
278 if ( ForcedTokens == NULL ) return;
280 /* find max token num */
281 for (p = ForcedTokens->next; p!=NULL; p=p->next)
283 q = (ForcedToken *) p->elem;
284 if ( q->tnum > max_token_number ) max_token_number = q->tnum;
286 fprintf(stderr, "max token number is %d\n", max_token_number);
288 /* make token indirection array */
289 TokenInd = (int *) calloc(max_token_number+1, sizeof(int));
290 LastTokenCounted = TokenNum;
291 TokenNum = max_token_number+1;
292 require(TokenInd!=NULL, "RemapForcedTokens: cannot allocate TokenInd");
294 /* fill token indirection array and change token id htable ; swap token indices */
295 for (i=1; i<TokenNum; i++) TokenInd[i] = i;
296 for (p = ForcedTokens->next; p!=NULL; p=p->next)
301 q = (ForcedToken *) p->elem;
302 fprintf(stderr, "%s forced to %d\n", q->token, q->tnum);
303 te = (TermEntry *) hash_get(Tname, q->token);
304 require(te!=NULL, "RemapForcedTokens: token not in hash table");
306 fprintf(stderr, "Before: TokenInd[old_pos==%d] is %d\n", old_pos, TokenInd[old_pos]);
307 fprintf(stderr, "Before: TokenInd[target==%d] is %d\n", q->tnum, TokenInd[q->tnum]);
308 q = (ForcedToken *) p->elem;
309 t = TokenInd[old_pos];
310 TokenInd[old_pos] = q->tnum;
311 TokenInd[q->tnum] = t;
312 te->token = q->tnum; /* update token type id symbol table */
313 fprintf(stderr, "After: TokenInd[old_pos==%d] is %d\n", old_pos, TokenInd[old_pos]);
314 fprintf(stderr, "After: TokenInd[target==%d] is %d\n", q->tnum, TokenInd[q->tnum]);
316 /* Change the token number in the sym tab entry for the exprs
317 * at the old position of the token id and the target position
319 /* update expr at target (if any) of forced token id */
320 if ( q->tnum < TokenNum ) /* is it a valid position? */
322 for (i=0; i<NumLexClasses; i++)
324 if ( lclass[i].exprs[q->tnum]!=NULL )
326 /* update the symbol table for this expr */
327 TermEntry *e = (TermEntry *) hash_get(lclass[i].htable, lclass[i].exprs[q->tnum]);
328 require(e!=NULL, "RemapForcedTokens: expr not in hash table");
330 fprintf(stderr, "found expr '%s' at target %d in lclass[%d]; changed to %d\n",
331 lclass[i].exprs[q->tnum], q->tnum, i, old_pos);
335 /* update expr at old position (if any) of forced token id */
336 for (i=0; i<NumLexClasses; i++)
338 if ( lclass[i].exprs[old_pos]!=NULL )
340 /* update the symbol table for this expr */
341 TermEntry *e = (TermEntry *) hash_get(lclass[i].htable, lclass[i].exprs[old_pos]);
342 require(e!=NULL, "RemapForcedTokens: expr not in hash table");
344 fprintf(stderr, "found expr '%s' for id %s in lclass[%d]; changed to %d\n",
345 lclass[i].exprs[old_pos], q->token, i, q->tnum);
351 RemapForcedTokensInSyntaxDiagram((Node *)SynDiag);
356 RemapForcedTokensInSyntaxDiagram(Node *p)
358 RemapForcedTokensInSyntaxDiagram(p)
362 Junction *j = (Junction *) p;
363 RuleRefNode *r = (RuleRefNode *) p;
364 TokNode *t = (TokNode *)p;
366 if ( p==NULL ) return;
367 require(p->ntype>=1 && p->ntype<=NumNodeTypes, "Remap...: invalid diagram node");
371 if ( j->visited ) return;
372 if ( j->jtype == EndRule ) return;
374 RemapForcedTokensInSyntaxDiagram( j->p1 );
375 RemapForcedTokensInSyntaxDiagram( j->p2 );
379 RemapForcedTokensInSyntaxDiagram( r->next );
382 if ( t->remapped ) return; /* we've been here before */
384 fprintf(stderr, "remapping %d to %d\n", t->token, TokenInd[t->token]);
385 t->token = TokenInd[t->token];
386 RemapForcedTokensInSyntaxDiagram( t->next );
389 RemapForcedTokensInSyntaxDiagram( ((ActionNode *)p)->next );
392 fatal_internal("invalid node type");
397 * Add a token name. Return the token number associated with it. If it already
398 * exists, then return the token number assigned to it.
400 * Track the order in which tokens are found so that the DLG output maintains
401 * that order. It also lets us map token numbers to strings.
405 addTname( char *token )
412 require(token!=NULL, "addTname: invalid token name");
414 if ( (p=(TermEntry *)hash_get(Tname, token)) != NULL ) return p->token;
415 p = newTermEntry( token );
417 p->token = TokenNum++;
418 hash_add(Tname, token, (Entry *)p);
422 /* This is the same as addTname except we force the TokenNum to be tnum.
423 * We don't have to use the Forced token stuff as no tokens will have
424 * been defined with #tokens when this is called. This is only called
425 * when a #tokdefs meta-op is used.
429 addForcedTname( char *token, int tnum )
431 addForcedTname( token, tnum )
437 require(token!=NULL, "addTname: invalid token name");
439 if ( (p=(TermEntry *)hash_get(Tname, token)) != NULL ) return p->token;
440 p = newTermEntry( token );
443 hash_add(Tname, token, (Entry *)p);
448 * Add a token expr. Return the token number associated with it. If it already
449 * exists, then return the token number assigned to it.
453 addTexpr( char *expr )
460 require(expr!=NULL, "addTexpr: invalid regular expression");
462 if ( (p=(TermEntry *)hash_get(Texpr, expr)) != NULL ) return p->token;
463 p = newTermEntry( expr );
465 /* track the order in which they occur */
466 list_add(&ExprOrder, (void *)newExpr(p->str));
467 p->token = TokenNum++;
468 hash_add(Texpr, expr, (Entry *)p);
472 /* return the token number of 'term'. Return 0 if no 'term' exists */
482 require(term!=NULL, "Tnum: invalid terminal");
484 if ( *term=='"' ) p = (TermEntry *) hash_get(Texpr, term);
485 else p = (TermEntry *) hash_get(Tname, term);
486 if ( p == NULL ) return 0;
487 else return p->token;
490 /* associate a Name with an expr. If both have been already assigned
491 * token numbers, then an error is reported. Add the token or expr
492 * that has not been added if no error. This 'represents' the #token
493 * ANTLR pseudo-op. If both have not been defined, define them both
494 * linked to same token number.
498 Tklink( char *token, char *expr )
500 Tklink( token, expr )
506 require(token!=NULL && expr!=NULL, "Tklink: invalid token name and/or expr");
508 p = (TermEntry *) hash_get(Tname, token);
509 q = (TermEntry *) hash_get(Texpr, expr);
510 if ( p != NULL && q != NULL ) /* both defined */
512 warn( eMsg2("token name %s and rexpr %s already defined; ignored",
516 if ( p==NULL && q==NULL ) /* both not defined */
518 int t = addTname( token );
519 q = newTermEntry( expr );
520 hash_add(Texpr, expr, (Entry *)q);
522 /* note: we use the actual ExprStr array
523 * here as TokenInd doesn't exist yet
526 /* track the order in which they occur */
527 list_add(&ExprOrder, (void *)newExpr(q->str));
530 if ( p != NULL ) /* one is defined, one is not */
532 q = newTermEntry( expr );
533 hash_add(Texpr, expr, (Entry *)q);
535 ExprStr[p->token] = q->str; /* both expr and token str defined now */
536 list_add(&ExprOrder, (void *)newExpr(q->str));
538 else /* trying to associate name with expr here*/
540 p = newTermEntry( token );
541 hash_add(Tname, token, (Entry *)p);
543 TokenStr[p->token] = p->str;/* both expr and token str defined now */
548 * Given a string, this function allocates and returns a pointer to a
549 * hash table record of size 'sz' whose "str" pointer is reset to a position
550 * in the string table.
554 newEntry( char *text, int sz )
562 require(text!=NULL, "new: NULL terminal");
564 if ( (p = (Entry *) calloc(1,sz)) == 0 )
566 fatal_internal("newEntry: out of memory for terminals\n");
567 exit(PCCTS_EXIT_FAILURE);
569 p->str = mystrdup(text);
575 * add an element to a list.
577 * Any non-empty list has a sentinel node whose 'elem' pointer is really
578 * a pointer to the last element. (i.e. length(list) = #elemIn(list)+1).
579 * Elements are appended to the list.
583 list_add( ListNode **list, void *e )
591 require(e!=NULL, "list_add: attempting to add NULL list element");
594 require(p!=NULL, "list_add: cannot alloc new list node");
598 ListNode *sentinel = newListNode;
599 require(sentinel!=NULL, "list_add: cannot alloc sentinel node");
602 sentinel->elem = (char *)p; /* set tail pointer */
604 else /* find end of list */
606 tail = (ListNode *) (*list)->elem; /* get tail pointer */
608 (*list)->elem = (char *) p; /* reset tail */
614 list_apply( ListNode *list, void (*f)(void *) )
616 list_apply( list, f )
622 require(f!=NULL, "list_apply: NULL function to apply");
624 if ( list == NULL ) return;
625 for (p = list->next; p!=NULL; p=p->next) (*f)( p->elem );
628 /* F O L L O W C y c l e S t u f f */
630 /* make a key based upon (rulename, computation, k value).
631 * Computation values are 'i'==FIRST, 'o'==FOLLOW.
635 Fkey( char *rule, int computation, int k )
637 Fkey( rule, computation, k )
643 static char key[MaxRuleName+2+1];
647 fatal("k>255 is too big for this implementation of ANTLR!\n");
648 if ( (i=strlen(rule)) > MaxRuleName )
649 fatal( eMsgd("rule name > max of %d\n", MaxRuleName) );
651 key[i] = (int) computation;
652 key[i+1] = (char) ((unsigned int) k);
657 /* Push a rule onto the kth FOLLOW stack */
660 FoPush( char *rule, int k )
668 require(rule!=NULL, "FoPush: tried to push NULL rule");
669 require(k<=CLL_k, "FoPush: tried to access non-existent stack");
671 /*fprintf(stderr, "FoPush(%s)\n", rule);*/
672 r = (RuleEntry *) hash_get(Rname, rule);
673 if ( r == NULL ) {fatal_internal( eMsg1("rule %s must be defined but isn't", rule) );}
674 if ( FoStack[k] == NULL ) /* Does the kth stack exist yet? */
676 /*fprintf(stderr, "allocating FoStack\n");*/
677 FoStack[k] = (int *) calloc(FoStackSize, sizeof(int));
678 require(FoStack[k]!=NULL, "FoPush: cannot allocate FOLLOW stack\n");
680 if ( FoTOS[k] == NULL )
683 *(FoTOS[k]) = r->rulenum;
688 require(valid(FoStack[k]), "FoPush: invalid FoStack");
690 if ( FoTOS[k] >= &(FoStack[k][FoStackSize-1]) )
691 fatal( eMsgd("exceeded max depth of FOLLOW recursion (%d)\n",
693 require(FoTOS[k]>=FoStack[k],
694 eMsg1("FoPush: FoStack stack-ptr is playing out of its sandbox",
697 *(FoTOS[k]) = r->rulenum;
702 fprintf(stderr, "FoStack[k=%d]:\n", k);
703 for (p=FoStack[k]; p<=FoTOS[k]; p++)
705 fprintf(stderr, "\t%s\n", RulePtr[*p]->rname);
711 /* Pop one rule off of the FOLLOW stack. TOS ptr is NULL if empty. */
720 require(k<=CLL_k, "FoPop: tried to access non-existent stack");
721 /*fprintf(stderr, "FoPop\n");*/
722 require(FoTOS[k]>=FoStack[k]&&FoTOS[k]<=&(FoStack[k][FoStackSize-1]),
723 "FoPop: FoStack stack-ptr is playing out of its sandbox");
724 if ( FoTOS[k] == FoStack[k] ) FoTOS[k] = NULL;
728 /* Compute FOLLOW cycle.
729 * Mark all FOLLOW sets for rules in cycle as incomplete.
730 * Then, save cycle on the cycle list (Cycles) for later resolution.
731 * The Cycle is stored in the form:
732 * (head of cycle==croot, rest of rules in cycle==cyclicDep)
734 * e.g. (Fo means "FOLLOW of", "-->" means requires or depends on)
736 * Fo(x)-->Fo(a)-->Fo(b)-->Fo(c)-->Fo(x)
737 * ^----Infinite recursion (cycle)
739 * the cycle would be: x -> {a,b,c} or stored as (x,{a,b,c}). Fo(x) depends
740 * on the FOLLOW of a,b, and c. The root of a cycle is always complete after
741 * Fo(x) finishes. Fo(a,b,c) however are not. It turns out that all rules
742 * in a FOLLOW cycle have the same FOLLOW set.
746 RegisterCycle( char *rule, int k )
748 RegisterCycle( rule, k )
757 require(rule!=NULL, "RegisterCycle: tried to register NULL rule");
758 require(k<=CLL_k, "RegisterCycle: tried to access non-existent stack");
760 /*fprintf(stderr, "RegisterCycle(%s)\n", rule);*/
761 /* Find cycle start */
762 r = (RuleEntry *) hash_get(Rname, rule);
763 require(r!=NULL,eMsg1("rule %s must be defined but isn't", rule));
764 require(FoTOS[k]>=FoStack[k]&&FoTOS[k]<=&(FoStack[k][FoStackSize-1]),
765 eMsg1("RegisterCycle(%s): FoStack stack-ptr is playing out of its sandbox",
767 /* if ( FoTOS[k]<FoStack[k]||FoTOS[k]>&(FoStack[k][FoStackSize-1]) )
769 fprintf(stderr, "RegisterCycle(%s): FoStack stack-ptr is playing out of its sandbox\n",
771 fprintf(stderr, "RegisterCycle: sp==0x%x out of bounds 0x%x...0x%x\n",
772 FoTOS[k], FoStack[k], &(FoStack[k][FoStackSize-1]));
773 exit(PCCTS_EXIT_FAILURE);
777 require(valid(FoStack[k]), "RegisterCycle: invalid FoStack");
779 for (p=FoTOS[k]; *p != r->rulenum && p >= FoStack[k]; --p) {;}
780 require(p>=FoStack[k], "RegisterCycle: FoStack is screwed up beyond belief");
781 if ( p == FoTOS[k] ) return; /* don't worry about cycles to oneself */
783 /* compute cyclic dependents (rules in cycle except head) */
785 require(c!=NULL, "RegisterCycle: couldn't alloc new cycle");
786 c->cyclicDep = empty;
787 c->croot = *p++; /* record root of cycle */
788 for (; p<=FoTOS[k]; p++)
790 /* Mark all dependent rules as incomplete */
791 f = (CacheEntry *) hash_get(Fcache, Fkey(RulePtr[*p]->rname,'o',k));
794 f = newCacheEntry( Fkey(RulePtr[*p]->rname,'o',k) );
795 hash_add(Fcache, Fkey(RulePtr[*p]->rname,'o',k), (Entry *)f);
797 f->incomplete = TRUE;
799 set_orel(*p, &(c->cyclicDep)); /* mark rule as dependent of croot */
801 list_add(&(Cycles[k]), (void *)c);
804 /* make all rules in cycle complete
806 * while ( some set has changed ) do
808 * if degree of FOLLOW set for croot > old degree then
809 * update all FOLLOW sets for rules in cyclic dependency
817 ResolveFoCycles( int k )
830 /*fprintf(stderr, "Resolving following cycles for %d\n", k);*/
835 for (p = Cycles[k]->next; p!=NULL; p=p->next)
837 c = (Cycle *) p->elem;
838 /*fprintf(stderr, "cycle %d: %s -->", i++, RulePtr[c->croot]->rname);*/
839 /*s_fprT(stderr, c->cyclicDep);*/
840 /*fprintf(stderr, "\n");*/
842 hash_get(Fcache, Fkey(RulePtr[c->croot]->rname,'o',k));
843 require(f!=NULL, eMsg1("FOLLOW(%s) must be in cache but isn't", RulePtr[c->croot]->rname) );
844 if ( (d=set_deg(f->fset)) > c->deg )
846 /*fprintf(stderr, "Fo(%s) has changed\n", RulePtr[c->croot]->rname);*/
848 c->deg = d; /* update cycle FOLLOW set degree */
849 while ( !set_nil(c->cyclicDep) )
851 r = set_int(c->cyclicDep);
852 set_rm(r, c->cyclicDep);
853 /*fprintf(stderr, "updating Fo(%s)\n", RulePtr[r]->rname);*/
855 hash_get(Fcache, Fkey(RulePtr[r]->rname,'o',k));
856 require(g!=NULL, eMsg1("FOLLOW(%s) must be in cache but isn't", RulePtr[r]->rname) );
857 set_orin(&(g->fset), f->fset);
858 g->incomplete = FALSE;
862 if ( i == 1 ) changed = 0; /* if only 1 cycle, no need to repeat */
864 /* kill Cycle list */
865 for (q = Cycles[k]->next; q != NULL; q=p)
868 set_free( ((Cycle *)q->elem)->cyclicDep );
871 free( (char *)Cycles[k] );
876 /* P r i n t i n g S y n t a x D i a g r a m s */
880 pBlk( Junction *q, int btype )
890 q->end->pvisited = TRUE;
891 if ( btype == aLoopBegin )
893 require(q->p2!=NULL, "pBlk: invalid ()* block");
895 alt = (Junction *)q->p2;
901 while ( !set_nil(alt->fset[k]) )
903 s_fprT(stdout, alt->fset[k]);
904 if ( k++ == CLL_k ) break;
905 if ( !set_nil(alt->fset[k]) ) printf(", ");
911 for (a=1,alt=q; alt != NULL; alt= (Junction *) alt->p2, a++)
913 if ( alt->p1 != NULL ) PRINT(alt->p1);
916 printf( " /* [%d] ", alt->altnum);
918 while ( !set_nil(alt->fset[k]) )
920 s_fprT(stdout, alt->fset[k]);
921 if ( k++ == CLL_k ) break;
922 if ( !set_nil(alt->fset[k]) ) printf(", ");
924 if ( alt->p2 == NULL && btype == aOptBlk )
925 printf( " (optional branch) */\n");
926 else printf( " */\n");
929 /* ignore implied empty alt of Plus blocks */
930 if ( alt->p2 != NULL && ((Junction *)alt->p2)->ignore ) break;
932 if ( alt->p2 != NULL && !(((Junction *)alt->p2)->p2==NULL && btype == aOptBlk) )
937 if ( a+1==pAlt1 || a+1==pAlt2 ) printf("=>");
944 p = (Junction *) ((Junction *)alt->p2)->p1;
947 if ( p->ntype==nAction )
949 p=(Junction *)((ActionNode *)p)->next;
952 if ( p->ntype!=nJunction )
956 if ( p->jtype==EndBlk || p->jtype==EndRule )
961 p = (Junction *)p->p1;
963 if ( p==NULL ) printf("\n\t"); /* Empty alt? */
967 q->end->pvisited = FALSE;
970 /* How to print out a junction */
981 require(q!=NULL, "pJunc: NULL node");
982 require(q->ntype==nJunction, "pJunc: not junction");
984 if ( q->pvisited == TRUE ) return;
989 if ( PrintAnnotate ) First(q, 1, q->jtype, &dum_k);
990 if ( q->end->p1 != NULL && ((Junction *)q->end->p1)->ntype==nJunction &&
991 ((Junction *)q->end->p1)->jtype == EndRule ) doing_rule = 1;
996 if ( pAlt1==1 ) printf("=>");
1002 if ( pLevel==1 ) printf(" ");
1007 if ( pLevel==1 ) printf(" ");
1009 if ( pLevel>1 ) printf(" ");
1012 if ( q->guess ) printf("?");
1014 if ( PrintAnnotate ) freeBlkFsets(q);
1015 if ( q->end->p1 != NULL ) PRINT(q->end->p1);
1018 if ( PrintAnnotate ) First(q, 1, q->jtype, &dum_k);
1022 if ( pAlt1==1 ) printf("=>");
1027 if ( pLevel==1 ) printf(" ");
1029 if ( pLevel>1 ) printf(" ");
1030 else printf("\n\t");
1033 if ( PrintAnnotate ) freeBlkFsets(q);
1034 if ( q->end->p1 != NULL ) PRINT(q->end->p1);
1037 if ( PrintAnnotate ) First(q, 1, q->jtype, &dum_k);
1041 if ( pAlt1==1 ) printf("=>");
1046 if ( pLevel==1 ) printf(" ");
1048 if ( pLevel>1 ) printf(" ");
1049 else printf("\n\t");
1052 if ( PrintAnnotate ) freeBlkFsets(q);
1053 if ( q->end->p1 != NULL ) PRINT(q->end->p1);
1056 if ( PrintAnnotate ) First(q, 1, q->jtype, &dum_k);
1058 if ( PrintAnnotate ) freeBlkFsets(q);
1061 if ( PrintAnnotate ) First(q, 1, q->jtype, &dum_k);
1065 if ( pAlt1==1 ) printf("=>");
1070 if ( pLevel==1 ) printf(" ");
1072 if ( pLevel>1 ) printf(" ");
1075 if ( PrintAnnotate ) freeBlkFsets(q);
1076 if ( q->end->p1 != NULL ) PRINT(q->end->p1);
1081 printf( "\n%s :\n", q->rname);
1083 if ( q->p2 != NULL ) PRINT(q->p2);
1086 if ( q->p1 != NULL ) PRINT(q->p1);
1087 q->pvisited = FALSE;
1088 if ( q->p2 != NULL ) PRINT(q->p2);
1094 q->pvisited = FALSE;
1097 /* How to print out a rule reference node */
1100 pRuleRef( RuleRefNode *p )
1106 require(p!=NULL, "pRuleRef: NULL node");
1107 require(p->ntype==nRuleRef, "pRuleRef: not rule ref node");
1109 printf( " %s", p->text);
1113 /* How to print out a terminal node */
1116 pToken( TokNode *p )
1122 require(p!=NULL, "pToken: NULL node");
1123 require(p->ntype==nToken, "pToken: not token node");
1125 if ( p->wild_card ) printf(" .");
1126 printf( " %s", TerminalString(p->token));
1130 /* How to print out a terminal node */
1133 pAction( ActionNode *p )
1139 require(p!=NULL, "pAction: NULL node");
1140 require(p->ntype==nAction, "pAction: not action node");
1145 /* F i l l F o l l o w L i s t s */
1148 * Search all rules for all rule reference nodes, q to rule, r.
1149 * Add q->next to follow list dangling off of rule r.
1152 * r: -o-R-o-->o--> Ptr to node following rule r in another rule
1154 * o--> Ptr to node following another reference to r.
1156 * This is the data structure employed to avoid FOLLOW set computation. We
1157 * simply compute the FIRST (reach) of the EndRule Node which follows the
1158 * list found at the end of all rules which are referenced elsewhere. Rules
1159 * not invoked by other rules have no follow list (r->end->p1==NULL).
1160 * Generally, only start symbols are not invoked by another rule.
1162 * Note that this mechanism also gives a free cross-reference mechanism.
1164 * The entire syntax diagram is layed out like this:
1187 Junction *j = (Junction *) p;
1188 RuleRefNode *r = (RuleRefNode *) p;
1190 if ( p==NULL ) return;
1191 require(p->ntype>=1 && p->ntype<=NumNodeTypes,
1192 eMsgd("FoLink: invalid diagram node: ntype==%d",p->ntype));
1196 if ( j->fvisited ) return;
1197 if ( j->jtype == EndRule ) return;
1203 if ( r->linked ) return;
1204 q = (RuleEntry *) hash_get(Rname, r->text);
1207 warnFL( eMsg1("rule %s not defined",r->text), FileStr[r->file], r->line );
1211 if ( r->parms!=NULL && RulePtr[q->rulenum]->pdecl==NULL )
1213 warnFL( eMsg1("rule %s accepts no parameter(s)", r->text),
1214 FileStr[r->file], r->line );
1216 if ( r->parms==NULL && RulePtr[q->rulenum]->pdecl!=NULL )
1218 warnFL( eMsg1("rule %s requires parameter(s)", r->text),
1219 FileStr[r->file], r->line );
1221 if ( r->assign!=NULL && RulePtr[q->rulenum]->ret==NULL )
1223 warnFL( eMsg1("rule %s yields no return value(s)", r->text),
1224 FileStr[r->file], r->line );
1226 if ( r->assign==NULL && RulePtr[q->rulenum]->ret!=NULL )
1228 warnFL( eMsg1("rule %s returns a value(s)", r->text),
1229 FileStr[r->file], r->line );
1233 addFoLink( r->next, r->rname, RulePtr[q->rulenum] );
1240 FoLink( ((TokNode *)p)->next );
1243 FoLink( ((ActionNode *)p)->next );
1246 fatal_internal("invalid node type");
1251 * Add a reference to the end of a rule.
1253 * 'r' points to the RuleBlk node in a rule. r->end points to the last node
1254 * (EndRule jtype) in a rule.
1260 * r->end --> o-->o--> Ptr to node following rule r in another rule
1262 * o--> Ptr to node following another reference to r.
1264 * Note that the links are added to the head of the list so that r->end->p1
1265 * always points to the most recently added follow-link. At the end, it should
1266 * point to the last reference found in the grammar (starting from the 1st rule).
1270 addFoLink( Node *p, char *rname, Junction *r )
1272 addFoLink( p, rname, r )
1279 require(r!=NULL, "addFoLink: incorrect rule graph");
1280 require(r->end!=NULL, "addFoLink: incorrect rule graph");
1281 require(r->end->jtype==EndRule, "addFoLink: incorrect rule graph");
1282 require(p!=NULL, "addFoLink: NULL FOLLOW link");
1285 j->rname = rname; /* rname on follow links point to target rule */
1286 j->p1 = p; /* link to other rule */
1287 j->p2 = (Node *) r->end->p1;/* point to head of list */
1288 r->end->p1 = (Node *) j; /* reset head to point to new node */
1293 GenCrossRef( Junction *p )
1303 require(p!=NULL, "GenCrossRef: why are you passing me a null grammar?");
1305 printf("Cross Reference:\n\n");
1307 for (; p!=NULL; p = (Junction *)p->p2)
1309 printf("Rule %11s referenced by {", p->rname);
1310 /* make a set of rules for uniqueness */
1311 for (j = (Junction *)(p->end)->p1; j!=NULL; j = (Junction *)j->p2)
1313 q = (RuleEntry *) hash_get(Rname, j->rname);
1314 require(q!=NULL, "GenCrossRef: FoLinks are screwed up");
1315 set_orel(q->rulenum, &a);
1317 for (; !set_nil(a); set_rm(e, a))
1320 printf(" %s", RulePtr[e]->rname);