home *** CD-ROM | disk | FTP | other *** search
/ OS/2 Shareware BBS: 10 Tools / 10-Tools.zip / pccts.zip / pccts / antlr / misc.c < prev    next >
C/C++ Source or Header  |  1994-03-31  |  34KB  |  1,326 lines
  1. /*
  2.  * misc.c
  3.  *
  4.  * Manage tokens, regular expressions.
  5.  * Print methods for debugging
  6.  * Compute follow lists onto tail ends of rules.
  7.  *
  8.  * The following functions are visible:
  9.  *
  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
  21.  *
  22.  * SOFTWARE RIGHTS
  23.  *
  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.
  29.  * 
  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
  40.  * completed.
  41.  *
  42.  * ANTLR 1.20
  43.  * Terence Parr
  44.  * Purdue University
  45.  * With AHPCRC, University of Minnesota
  46.  * 1989-1994
  47.  */
  48. #include <stdio.h>
  49. #ifdef __cplusplus
  50. #ifndef __STDC__
  51. #define __STDC__
  52. #endif
  53. #endif
  54. #include "set.h"
  55. #include "syn.h"
  56. #include "hash.h"
  57. #include "generic.h"
  58. #include "dlgdef.h"
  59.  
  60. static int tsize=TSChunk;        /* size of token str arrays */
  61.  
  62. static void
  63. #ifdef __STDC__
  64. RemapForcedTokensInSyntaxDiagram(Node *);
  65. #else
  66. RemapForcedTokensInSyntaxDiagram();
  67. #endif
  68.  
  69.                 /* T o k e n  M a n i p u l a t i o n */
  70.  
  71. /*
  72.  * add token 't' to the TokenStr/Expr array.  Make more room if necessary.
  73.  * 't' is either an expression or a token name.
  74.  *
  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.
  78.  *
  79.  * Also, there is a Texpr hash table for each automaton.
  80.  */
  81. static void
  82. #ifdef __STDC__
  83. Ttrack( char *t )
  84. #else
  85. Ttrack( t )
  86. char *t;
  87. #endif
  88. {
  89.     if ( TokenNum >= tsize )    /* terminal table overflow? */
  90.     {
  91.         char **p;
  92.         int i, more, j;
  93.  
  94.         more = TSChunk * (1 + ((TokenNum-tsize) / TSChunk));
  95.         tsize += more;
  96.         TokenStr = (char **) realloc(TokenStr, tsize*sizeof(char *));
  97.         require(TokenStr != NULL, "Ttrack: can't extend TokenStr");
  98.         for (i=0; i<NumLexClasses; i++)
  99.         {
  100.             lclass[i].exprs = (char **)
  101.                               realloc(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;
  104.         }
  105.         for (p= &TokenStr[tsize-more],i=1; i<=more; i++) *p++ = NULL;
  106.         lexmode( CurrentLexClass ); /* reset ExprStr in case table moved */
  107.     }
  108.     /* note: we use the actual ExprStr/TokenStr array
  109.      * here as TokenInd doesn't exist yet
  110.      */
  111.     if ( *t == '"' ) ExprStr[TokenNum] = t;
  112.     else TokenStr[TokenNum] = t;
  113. }
  114.  
  115. static Expr *
  116. #ifdef __STDC__
  117. newExpr( char *e )
  118. #else
  119. newExpr( e )
  120. char *e;
  121. #endif
  122. {
  123.     Expr *p = (Expr *) calloc(1, sizeof(Expr));
  124.     require(p!=NULL, "newExpr: cannot alloc Expr node");
  125.  
  126.     p->expr = e;
  127.     p->lclass = CurrentLexClass;
  128.     return p;
  129. }
  130.  
  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.
  134.  *
  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.
  139.  */
  140. void
  141. #ifdef __STDC__
  142. lexclass( char *m )
  143. #else
  144. lexclass( m )
  145. char *m;
  146. #endif
  147. {
  148.     int i;
  149.     TermEntry *p;
  150.     static char EOFSTR[] = "\"@\"";
  151.  
  152.     if ( hash_get(Tname, m) != NULL )
  153.     {
  154.         warn(eMsg1("lexclass name conflicts with token/errclass label '%s'",m));
  155.     }
  156.     /* does m already exist? */
  157.     i = LexClassIndex(m);
  158.     if ( i != -1 ) {lexmode(i); return;}
  159.     /* must make new one */
  160.     NumLexClasses++;
  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
  177.      */
  178.     ExprStr[EofToken] = EOFSTR;
  179. }
  180.  
  181. void
  182. #ifdef __STDC__
  183. lexmode( int i )
  184. #else
  185. lexmode( i )
  186. int i;
  187. #endif
  188. {
  189.     require(i<NumLexClasses, "lexmode: invalid mode");
  190.     ExprStr = lclass[i].exprs;
  191.     Texpr = lclass[i].htable;
  192.     CurrentLexClass = i;
  193. }
  194.  
  195. /* return index into lclass array of lexical class. return -1 if nonexistent */
  196. int
  197. #ifdef __STDC__
  198. LexClassIndex( char *cl )
  199. #else
  200. LexClassIndex( cl )
  201. char *cl;
  202. #endif
  203. {
  204.     int i;
  205.  
  206.     for (i=0; i<NumLexClasses; i++)
  207.     {
  208.         if ( strcmp(lclass[i].classnum, cl) == 0 ) return i;
  209.     }
  210.     return -1;
  211. }
  212.  
  213. int
  214. #ifdef __STDC__
  215. hasAction( char *expr )
  216. #else
  217. hasAction( expr )
  218. char *expr;
  219. #endif
  220. {
  221.     TermEntry *p;
  222.     require(expr!=NULL, "hasAction: invalid expr");
  223.  
  224.     p = (TermEntry *) hash_get(Texpr, expr);
  225.     require(p!=NULL, eMsg1("hasAction: expr '%s' doesn't exist",expr));
  226.     return (p->action!=NULL);
  227. }
  228.  
  229. void
  230. #ifdef __STDC__
  231. setHasAction( char *expr, char *action )
  232. #else
  233. setHasAction( expr, action )
  234. char *expr;
  235. char *action;
  236. #endif
  237. {
  238.     TermEntry *p;
  239.     require(expr!=NULL, "setHasAction: invalid expr");
  240.  
  241.     p = (TermEntry *) hash_get(Texpr, expr);
  242.     require(p!=NULL, eMsg1("setHasAction: expr '%s' doesn't exist",expr));
  243.     p->action = action;
  244. }
  245.  
  246. ForcedToken *
  247. #ifdef __STDC__
  248. newForcedToken(char *token, int tnum)
  249. #else
  250. newForcedToken(token, tnum)
  251. char *token;
  252. int tnum;
  253. #endif
  254. {
  255.     ForcedToken *ft = (ForcedToken *) calloc(1, sizeof(ForcedToken));
  256.     require(ft!=NULL, "out of memory");
  257.     ft->token = token;
  258.     ft->tnum = tnum;
  259.     return ft;
  260. }
  261.  
  262. /*
  263.  * Make a token indirection array that remaps token numbers and then walk
  264.  * the appropriate symbol tables and SynDiag to change token numbers
  265.  */
  266. void
  267. #ifdef __STDC__
  268. RemapForcedTokens(void)
  269. #else
  270. RemapForcedTokens()
  271. #endif
  272. {
  273.     ListNode *p;
  274.     ForcedToken *q;
  275.     unsigned int max_token_number=0;
  276.     int i;
  277.  
  278.     if ( ForcedTokens == NULL ) return;
  279.  
  280.     /* find max token num */
  281.     for (p = ForcedTokens->next; p!=NULL; p=p->next)
  282.     {
  283.         q = (ForcedToken *) p->elem;
  284.         if ( q->tnum > max_token_number ) max_token_number = q->tnum;
  285.     }
  286.     fprintf(stderr, "max token number is %d\n", max_token_number);
  287.  
  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");
  293.  
  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)
  297.     {
  298.         TermEntry *te;
  299.         int old_pos, t;
  300.  
  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");
  305.         old_pos = te->token;
  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]);
  315.  
  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
  318.          */
  319.         /* update expr at target (if any) of forced token id */
  320.         if ( q->tnum < TokenNum )    /* is it a valid position? */
  321.         {
  322.             for (i=0; i<NumLexClasses; i++)
  323.             {
  324.                 if ( lclass[i].exprs[q->tnum]!=NULL )
  325.                 {
  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");
  329.                     e->token = old_pos;
  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);
  332.                 }
  333.             }
  334.         }
  335.         /* update expr at old position (if any) of forced token id */
  336.         for (i=0; i<NumLexClasses; i++)
  337.         {
  338.             if ( lclass[i].exprs[old_pos]!=NULL )
  339.             {
  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");
  343.                 e->token = q->tnum;
  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);
  346.             }
  347.         }
  348.     }
  349.  
  350.     /* Update SynDiag */
  351.     RemapForcedTokensInSyntaxDiagram((Node *)SynDiag);
  352. }
  353.  
  354. static void
  355. #ifdef __STDC__
  356. RemapForcedTokensInSyntaxDiagram(Node *p)
  357. #else
  358. RemapForcedTokensInSyntaxDiagram(p)
  359. Node *p;
  360. #endif
  361. {
  362.     Junction *j = (Junction *) p;
  363.     RuleRefNode *r = (RuleRefNode *) p;
  364.     TokNode *t = (TokNode *)p;
  365.  
  366.     if ( p==NULL ) return;
  367.     require(p->ntype>=1 && p->ntype<=NumNodeTypes,    "Remap...: invalid diagram node");
  368.     switch ( p->ntype )
  369.     {
  370.         case nJunction :
  371.             if ( j->visited ) return;
  372.             if ( j->jtype == EndRule ) return;
  373.             j->visited = TRUE;
  374.             RemapForcedTokensInSyntaxDiagram( j->p1 );
  375.             RemapForcedTokensInSyntaxDiagram( j->p2 );
  376.             j->visited = FALSE;
  377.             return;
  378.         case nRuleRef :
  379.             RemapForcedTokensInSyntaxDiagram( r->next );
  380.             return;
  381.         case nToken :
  382.             if ( t->remapped ) return;    /* we've been here before */
  383.             t->remapped = 1;
  384.             fprintf(stderr, "remapping %d to %d\n", t->token, TokenInd[t->token]);
  385.             t->token = TokenInd[t->token];
  386.             RemapForcedTokensInSyntaxDiagram( t->next );
  387.             return;
  388.         case nAction :
  389.             RemapForcedTokensInSyntaxDiagram( ((ActionNode *)p)->next );
  390.             return;
  391.         default :
  392.             fatal("invalid node type");
  393.     }
  394. }
  395.  
  396. /*
  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.
  399.  *
  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.
  402.  */
  403. int
  404. #ifdef __STDC__
  405. addTname( char *token )
  406. #else
  407. addTname( token )
  408. char *token;
  409. #endif
  410. {
  411.     TermEntry *p;
  412.     require(token!=NULL, "addTname: invalid token name");
  413.  
  414.     if ( (p=(TermEntry *)hash_get(Tname, token)) != NULL ) return p->token;
  415.     p = newTermEntry( token );
  416.     Ttrack( p->str );
  417.     p->token = TokenNum++;
  418.     hash_add(Tname, token, (Entry *)p);
  419.     return p->token;
  420. }
  421.  
  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.
  426.  */
  427. int
  428. #ifdef __STDC__
  429. addForcedTname( char *token, int tnum )
  430. #else
  431. addForcedTname( token, tnum )
  432. char *token;
  433. int tnum;
  434. #endif
  435. {
  436.     TermEntry *p;
  437.     require(token!=NULL, "addTname: invalid token name");
  438.  
  439.     if ( (p=(TermEntry *)hash_get(Tname, token)) != NULL ) return p->token;
  440.     p = newTermEntry( token );
  441.     Ttrack( p->str );
  442.     p->token = tnum;
  443.     hash_add(Tname, token, (Entry *)p);
  444.     return p->token;
  445. }
  446.  
  447. /*
  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.
  450.  */
  451. int
  452. #ifdef __STDC__
  453. addTexpr( char *expr )
  454. #else
  455. addTexpr( expr )
  456. char *expr;
  457. #endif
  458. {
  459.     TermEntry *p;
  460.     require(expr!=NULL, "addTexpr: invalid regular expression");
  461.  
  462.     if ( (p=(TermEntry *)hash_get(Texpr, expr)) != NULL ) return p->token;
  463.     p = newTermEntry( expr );
  464.     Ttrack( p->str );
  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);
  469.     return p->token;
  470. }
  471.  
  472. /* return the token number of 'term'.  Return 0 if no 'term' exists */
  473. int
  474. #ifdef __STDC__
  475. Tnum( char *term )
  476. #else
  477. Tnum( term )
  478. char *term;
  479. #endif
  480. {
  481.     TermEntry *p;
  482.     require(term!=NULL, "Tnum: invalid terminal");
  483.     
  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;
  488. }
  489.  
  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.
  495.  */
  496. void
  497. #ifdef __STDC__
  498. Tklink( char *token, char *expr )
  499. #else
  500. Tklink( token, expr )
  501. char *token;
  502. char *expr;
  503. #endif
  504. {
  505.     TermEntry *p, *q;
  506.     require(token!=NULL && expr!=NULL, "Tklink: invalid token name and/or expr");
  507.  
  508.     p = (TermEntry *) hash_get(Tname, token);
  509.     q = (TermEntry *) hash_get(Texpr, expr);
  510.     if ( p != NULL && q != NULL )    /* both defined */
  511.     {
  512.         warn( eMsg2("token name %s and rexpr %s already defined; ignored",
  513.                     token, expr) );
  514.         return;
  515.     }
  516.     if ( p==NULL && q==NULL )        /* both not defined */
  517.     {
  518.         int t = addTname( token );
  519.         q = newTermEntry( expr );
  520.         hash_add(Texpr, expr, (Entry *)q);
  521.         q->token = t;
  522.         /* note: we use the actual ExprStr array
  523.          * here as TokenInd doesn't exist yet
  524.          */
  525.         ExprStr[t] = q->str;
  526.         /* track the order in which they occur */
  527.         list_add(&ExprOrder, (void *)newExpr(q->str));
  528.         return;
  529.     }
  530.     if ( p != NULL )                /* one is defined, one is not */
  531.     {
  532.         q = newTermEntry( expr );
  533.         hash_add(Texpr, expr, (Entry *)q);
  534.         q->token = p->token;
  535.         ExprStr[p->token] = q->str;    /* both expr and token str defined now */
  536.         list_add(&ExprOrder, (void *)newExpr(q->str));
  537.     }
  538.     else                            /* trying to associate name with expr here*/
  539.     {
  540.         p = newTermEntry( token );
  541.         hash_add(Tname, token, (Entry *)p);
  542.         p->token = q->token;
  543.         TokenStr[p->token] = p->str;/* both expr and token str defined now */
  544.     }
  545. }
  546.  
  547. /*
  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.
  551.  */
  552. Entry *
  553. #ifdef __STDC__
  554. newEntry( char *text, int sz )
  555. #else
  556. newEntry( text, sz )
  557. char *text;
  558. int sz;
  559. #endif
  560. {
  561.     Entry *p;
  562.     require(text!=NULL, "new: NULL terminal");
  563.     
  564.     if ( (p = (Entry *) calloc(1,sz)) == 0 )
  565.     {
  566.         fatal("newEntry: out of memory for terminals\n");
  567.         exit(1);
  568.     }
  569.     p->str = mystrdup(text);
  570.     
  571.     return(p);
  572. }
  573.  
  574. /*
  575.  * add an element to a list.
  576.  *
  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.
  580.  */
  581. void
  582. #ifdef __STDC__
  583. list_add( ListNode **list, void *e )
  584. #else
  585. list_add( list, e )
  586. ListNode **list;
  587. void *e;
  588. #endif
  589. {
  590.     ListNode *p, *tail;
  591.     require(e!=NULL, "list_add: attempting to add NULL list element");
  592.  
  593.     p = newListNode;
  594.     require(p!=NULL, "list_add: cannot alloc new list node");
  595.     p->elem = e;
  596.     if ( *list == NULL )
  597.     {
  598.         ListNode *sentinel = newListNode;
  599.         require(sentinel!=NULL, "list_add: cannot alloc sentinel node");
  600.         *list=sentinel;
  601.         sentinel->next = p;
  602.         sentinel->elem = (char *)p;        /* set tail pointer */
  603.     }
  604.     else                                /* find end of list */
  605.     {
  606.         tail = (ListNode *) (*list)->elem;    /* get tail pointer */
  607.         tail->next = p;
  608.         (*list)->elem = (char *) p;        /* reset tail */
  609.     }
  610. }
  611.  
  612. void
  613. #ifdef __STDC__
  614. list_apply( ListNode *list, void (*f)(void *) )
  615. #else
  616. list_apply( list, f )
  617. ListNode *list;
  618. void (*f)();
  619. #endif
  620. {
  621.     ListNode *p;
  622.     require(f!=NULL, "list_apply: NULL function to apply");
  623.  
  624.     if ( list == NULL ) return;
  625.     for (p = list->next; p!=NULL; p=p->next) (*f)( p->elem );
  626. }
  627.  
  628.             /* F O L L O W  C y c l e  S t u f f */
  629.         
  630. /* make a key based upon (rulename, computation, k value).
  631.  * Computation values are 'i'==FIRST, 'o'==FOLLOW.
  632.  */
  633. char *
  634. #ifdef __STDC__
  635. Fkey( char *rule, int computation, int k )
  636. #else
  637. Fkey( rule, computation, k )
  638. char *rule;
  639. int computation;
  640. int k;
  641. #endif
  642. {
  643.     static char key[MaxRuleName+2+1];
  644.     int i;
  645.     
  646.     if ( k > 255 ) 
  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) );
  650.     strcpy(key,rule);
  651.     key[i] = (int) computation;
  652.     key[i+1] = (char) ((unsigned int) k);
  653.     key[i+2] = '\0';
  654.     return key;
  655. }
  656.  
  657. /* Push a rule onto the kth FOLLOW stack */
  658. void
  659. #ifdef __STDC__
  660. FoPush( char *rule, int k )
  661. #else
  662. FoPush( rule, k )
  663. char *rule;
  664. int k;
  665. #endif
  666. {
  667.     RuleEntry *r;
  668.     require(rule!=NULL, "FoPush: tried to push NULL rule");
  669.     require(k<=CLL_k,    "FoPush: tried to access non-existent stack");
  670.  
  671.     /*fprintf(stderr, "FoPush(%s)\n", rule);*/
  672.     r = (RuleEntry *) hash_get(Rname, rule);
  673.     if ( r == NULL ) {fatal( eMsg1("rule %s must be defined but isn't", rule) );}
  674.     if ( FoStack[k] == NULL )        /* Does the kth stack exist yet? */
  675.     {
  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");
  679.     }
  680.     if ( FoTOS[k] == NULL )
  681.     {
  682.         FoTOS[k]=FoStack[k];
  683.         *(FoTOS[k]) = r->rulenum;
  684.     }
  685.     else
  686.     {
  687. #ifdef MEMCHK
  688.         require(valid(FoStack[k]), "FoPush: invalid FoStack");
  689. #endif
  690.         if ( FoTOS[k] >= &(FoStack[k][FoStackSize-1]) )
  691.             fatal( eMsgd("exceeded max depth of FOLLOW recursion (%d)\n",
  692.                         FoStackSize) );
  693.         require(FoTOS[k]>=FoStack[k],
  694.                 eMsg1("FoPush: FoStack stack-ptr is playing out of its sandbox",
  695.                       rule));
  696.         ++(FoTOS[k]);
  697.         *(FoTOS[k]) = r->rulenum;
  698.     }
  699.     {
  700.         /*
  701.         int *p;
  702.         fprintf(stderr, "FoStack[k=%d]:\n", k);
  703.         for (p=FoStack[k]; p<=FoTOS[k]; p++)
  704.         {
  705.             fprintf(stderr, "\t%s\n", RulePtr[*p]->rname);
  706.         }
  707.         */
  708.     }
  709. }
  710.  
  711. /* Pop one rule off of the FOLLOW stack.  TOS ptr is NULL if empty. */
  712. void
  713. #ifdef __STDC__
  714. FoPop( int k )
  715. #else
  716. FoPop( k )
  717. int k;
  718. #endif
  719. {
  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;
  725.     else (FoTOS[k])--;
  726. }
  727.  
  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)
  733.  *
  734.  * e.g. (Fo means "FOLLOW of", "-->" means requires or depends on)
  735.  *
  736.  *        Fo(x)-->Fo(a)-->Fo(b)-->Fo(c)-->Fo(x)
  737.  *                                           ^----Infinite recursion (cycle)
  738.  *
  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.
  743.  */
  744. void
  745. #ifdef __STDC__
  746. RegisterCycle( char *rule, int k )
  747. #else
  748. RegisterCycle( rule, k )
  749. char *rule;
  750. int k;
  751. #endif
  752. {
  753.     CacheEntry *f;
  754.     Cycle *c;
  755.     int *p;
  756.     RuleEntry *r;
  757.     require(rule!=NULL, "RegisterCycle: tried to register NULL rule");
  758.     require(k<=CLL_k,    "RegisterCycle: tried to access non-existent stack");
  759.  
  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",
  766.                   rule));
  767. /*    if ( FoTOS[k]<FoStack[k]||FoTOS[k]>&(FoStack[k][FoStackSize-1]) )
  768.     {
  769.         fprintf(stderr, "RegisterCycle(%s): FoStack stack-ptr is playing out of its sandbox\n",
  770.                         rule);
  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(1);
  774.     }
  775. */
  776. #ifdef MEMCHK
  777.     require(valid(FoStack[k]), "RegisterCycle: invalid FoStack");
  778. #endif
  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 */
  782.     
  783.     /* compute cyclic dependents (rules in cycle except head) */
  784.     c = newCycle;
  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++)
  789.     {
  790.         /* Mark all dependent rules as incomplete */
  791.         f = (CacheEntry *) hash_get(Fcache, Fkey(RulePtr[*p]->rname,'o',k));
  792.         if ( f==NULL )
  793.         {
  794.             f = newCacheEntry( Fkey(RulePtr[*p]->rname,'o',k) );
  795.             hash_add(Fcache, Fkey(RulePtr[*p]->rname,'o',k), (Entry *)f);
  796.         }
  797.         f->incomplete = TRUE;
  798.         
  799.         set_orel(*p, &(c->cyclicDep)); /* mark rule as dependent of croot */
  800.     }
  801.     list_add(&(Cycles[k]), (void *)c);
  802. }
  803.  
  804. /* make all rules in cycle complete
  805.  *
  806.  * while ( some set has changed ) do
  807.  *        for each cycle do
  808.  *            if degree of FOLLOW set for croot > old degree then
  809.  *                update all FOLLOW sets for rules in cyclic dependency
  810.  *                change = TRUE
  811.  *            endif
  812.  *        endfor
  813.  * endwhile
  814.  */
  815. void
  816. #ifdef __STDC__
  817. ResolveFoCycles( int k )
  818. #else
  819. ResolveFoCycles( k )
  820. int k;
  821. #endif
  822. {
  823.     ListNode *p, *q;
  824.     Cycle *c;
  825.     int changed = 1;
  826.     CacheEntry *f,*g;
  827.     int r,i;
  828.     unsigned d;
  829.     
  830.     /*fprintf(stderr, "Resolving following cycles for %d\n", k);*/
  831.     while ( changed )
  832.     {
  833.         changed = 0;
  834.         i = 0;
  835.         for (p = Cycles[k]->next; p!=NULL; p=p->next)
  836.         {
  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");*/
  841.             f = (CacheEntry *)
  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 )
  845.             {
  846.                 /*fprintf(stderr, "Fo(%s) has changed\n", RulePtr[c->croot]->rname);*/
  847.                 changed = 1;
  848.                 c->deg = d;        /* update cycle FOLLOW set degree */
  849.                 while ( !set_nil(c->cyclicDep) )
  850.                 {
  851.                     r = set_int(c->cyclicDep);
  852.                     set_rm(r, c->cyclicDep);
  853.                     /*fprintf(stderr, "updating Fo(%s)\n", RulePtr[r]->rname);*/
  854.                     g = (CacheEntry *)
  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;
  859.                 }
  860.             }
  861.         }
  862.         if ( i == 1 ) changed = 0;    /* if only 1 cycle, no need to repeat */
  863.     }
  864.     /* kill Cycle list */
  865.     for (q = Cycles[k]->next; q != NULL; q=p)
  866.     {
  867.         p = q->next;
  868.         set_free( ((Cycle *)q->elem)->cyclicDep );
  869.         free(q);
  870.     }
  871.     free( Cycles[k] );
  872.     Cycles[k] = NULL;
  873. }
  874.  
  875.  
  876.             /* P r i n t i n g  S y n t a x  D i a g r a m s */
  877.  
  878. static void
  879. #ifdef __STDC__
  880. pBlk( Junction *q, int btype )
  881. #else
  882. pBlk( q, btype )
  883. Junction *q;
  884. int btype;
  885. #endif
  886. {
  887.     int k,a;
  888.     Junction *alt, *p;
  889.  
  890.     q->end->pvisited = TRUE;
  891.     if ( btype == aLoopBegin )
  892.     {
  893.         require(q->p2!=NULL, "pBlk: invalid ()* block");
  894.         PRINT(q->p1);
  895.         alt = (Junction *)q->p2;
  896.         PRINT(alt->p1);
  897.         if ( PrintAnnotate )
  898.         {
  899.             printf(" /* Opt ");
  900.             k = 1;
  901.             while ( !set_nil(alt->fset[k]) )
  902.             {
  903.                 s_fprT(stdout, alt->fset[k]);
  904.                 if ( k++ == CLL_k ) break;
  905.                 if ( !set_nil(alt->fset[k]) ) printf(", ");
  906.             }
  907.             printf(" */\n");
  908.         }
  909.         return;
  910.     }
  911.     for (a=1,alt=q; alt != NULL; alt= (Junction *) alt->p2, a++)
  912.     {
  913.         if ( alt->p1 != NULL ) PRINT(alt->p1);
  914.         if ( PrintAnnotate )
  915.         {
  916.             printf( " /* [%d] ", alt->altnum);
  917.             k = 1;
  918.             while ( !set_nil(alt->fset[k]) )
  919.             {
  920.                 s_fprT(stdout, alt->fset[k]);
  921.                 if ( k++ == CLL_k ) break;
  922.                 if ( !set_nil(alt->fset[k]) ) printf(", ");
  923.             }
  924.             if ( alt->p2 == NULL && btype == aOptBlk )
  925.                 printf( " (optional branch) */\n");
  926.             else printf( " */\n");
  927.         }
  928.  
  929.         /* ignore implied empty alt of Plus blocks */
  930.         if ( alt->p2 != NULL && ((Junction *)alt->p2)->ignore ) break;
  931.  
  932.         if ( alt->p2 != NULL && !(((Junction *)alt->p2)->p2==NULL && btype == aOptBlk) )
  933.         {
  934.             if ( pLevel == 1 )
  935.             {
  936.                 printf("\n");
  937.                 if ( a+1==pAlt1 || a+1==pAlt2 ) printf("=>");
  938.                 printf("\t");
  939.             }
  940.             else printf(" ");
  941.             printf("|");
  942.             if ( pLevel == 1 )
  943.             {
  944.                 p = (Junction *) ((Junction *)alt->p2)->p1;
  945.                 while ( p!=NULL )
  946.                 {
  947.                     if ( p->ntype==nAction )
  948.                     {
  949.                         p=(Junction *)((ActionNode *)p)->next;
  950.                         continue;
  951.                     }
  952.                     if ( p->ntype!=nJunction )
  953.                     {
  954.                         break;
  955.                     }
  956.                     if ( p->jtype==EndBlk || p->jtype==EndRule )
  957.                     {
  958.                         p = NULL;
  959.                         break;
  960.                     }
  961.                     p = (Junction *)p->p1;
  962.                 }
  963.                 if ( p==NULL ) printf("\n\t");    /* Empty alt? */
  964.             }
  965.         }
  966.     }
  967.     q->end->pvisited = FALSE;
  968. }
  969.  
  970. /* How to print out a junction */
  971. void
  972. #ifdef __STDC__
  973. pJunc( Junction *q )
  974. #else
  975. pJunc( q )
  976. Junction *q;
  977. #endif
  978. {
  979.     int dum_k;
  980.     int doing_rule;
  981.     require(q!=NULL, "pJunc: NULL node");
  982.     require(q->ntype==nJunction, "pJunc: not junction");
  983.     
  984.     if ( q->pvisited == TRUE ) return;
  985.     q->pvisited = TRUE;
  986.     switch ( q->jtype )
  987.     {
  988.         case aSubBlk :
  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;
  992.             else doing_rule = 0;
  993.             pLevel++;
  994.             if ( pLevel==1 )
  995.             {
  996.                 if ( pAlt1==1 ) printf("=>");
  997.                 printf("\t");
  998.             }
  999.             else printf(" ");
  1000.             if ( doing_rule )
  1001.             {
  1002.                 if ( pLevel==1 ) printf(" ");
  1003.                 pBlk(q,q->jtype);
  1004.             }
  1005.             else {
  1006.                 printf("(");
  1007.                 if ( pLevel==1 ) printf(" ");
  1008.                 pBlk(q,q->jtype);
  1009.                 if ( pLevel>1 ) printf(" ");
  1010.                 printf(")");
  1011.             }
  1012.             if ( q->guess ) printf("?");
  1013.             pLevel--;
  1014.             if ( PrintAnnotate ) freeBlkFsets(q);
  1015.             if ( q->end->p1 != NULL ) PRINT(q->end->p1);
  1016.             break;
  1017.         case aOptBlk :
  1018.             if ( PrintAnnotate ) First(q, 1, q->jtype, &dum_k);
  1019.             pLevel++;
  1020.             if ( pLevel==1 )
  1021.             {
  1022.                 if ( pAlt1==1 ) printf("=>");
  1023.                 printf("\t");
  1024.             }
  1025.             else printf(" ");
  1026.             printf("{");
  1027.             if ( pLevel==1 ) printf(" ");
  1028.             pBlk(q,q->jtype);
  1029.             if ( pLevel>1 ) printf(" ");
  1030.             else printf("\n\t");
  1031.             printf("}");
  1032.             pLevel--;
  1033.             if ( PrintAnnotate ) freeBlkFsets(q);
  1034.             if ( q->end->p1 != NULL ) PRINT(q->end->p1);
  1035.             break;
  1036.         case aLoopBegin :
  1037.             if ( PrintAnnotate ) First(q, 1, q->jtype, &dum_k);
  1038.             pLevel++;
  1039.             if ( pLevel==1 )
  1040.             {
  1041.                 if ( pAlt1==1 ) printf("=>");
  1042.                 printf("\t");
  1043.             }
  1044.             else printf(" ");
  1045.             printf("(");
  1046.             if ( pLevel==1 ) printf(" ");
  1047.             pBlk(q,q->jtype);
  1048.             if ( pLevel>1 ) printf(" ");
  1049.             else printf("\n\t");
  1050.             printf(")*");
  1051.             pLevel--;
  1052.             if ( PrintAnnotate ) freeBlkFsets(q);
  1053.             if ( q->end->p1 != NULL ) PRINT(q->end->p1);
  1054.             break;
  1055.         case aLoopBlk :
  1056.             if ( PrintAnnotate ) First(q, 1, q->jtype, &dum_k);
  1057.             pBlk(q,q->jtype);
  1058.             if ( PrintAnnotate ) freeBlkFsets(q);
  1059.             break;
  1060.         case aPlusBlk :
  1061.             if ( PrintAnnotate ) First(q, 1, q->jtype, &dum_k);
  1062.             pLevel++;
  1063.             if ( pLevel==1 )
  1064.             {
  1065.                 if ( pAlt1==1 ) printf("=>");
  1066.                 printf("\t");
  1067.             }
  1068.             else printf(" ");
  1069.             printf("(");
  1070.             if ( pLevel==1 ) printf(" ");
  1071.             pBlk(q,q->jtype);
  1072.             if ( pLevel>1 ) printf(" ");
  1073.             printf(")+");
  1074.             pLevel--;
  1075.             if ( PrintAnnotate ) freeBlkFsets(q);
  1076.             if ( q->end->p1 != NULL ) PRINT(q->end->p1);
  1077.             break;
  1078.         case EndBlk :
  1079.             break;
  1080.         case RuleBlk :
  1081.             printf( "\n%s :\n", q->rname);
  1082.             PRINT(q->p1);
  1083.             if ( q->p2 != NULL ) PRINT(q->p2);
  1084.             break;
  1085.         case Generic :
  1086.             if ( q->p1 != NULL ) PRINT(q->p1);
  1087.             q->pvisited = FALSE;
  1088.             if ( q->p2 != NULL ) PRINT(q->p2);
  1089.             break;
  1090.         case EndRule :
  1091.             printf( "\n\t;\n");
  1092.             break;
  1093.     }
  1094.     q->pvisited = FALSE;
  1095. }
  1096.  
  1097. /* How to print out a rule reference node */
  1098. void
  1099. #ifdef __STDC__
  1100. pRuleRef( RuleRefNode *p )
  1101. #else
  1102. pRuleRef( p )
  1103. RuleRefNode *p;
  1104. #endif
  1105. {
  1106.     require(p!=NULL, "pRuleRef: NULL node");
  1107.     require(p->ntype==nRuleRef, "pRuleRef: not rule ref node");
  1108.     
  1109.     printf( " %s", p->text);
  1110.     PRINT(p->next);
  1111. }
  1112.  
  1113. /* How to print out a terminal node */
  1114. void
  1115. #ifdef __STDC__
  1116. pToken( TokNode *p )
  1117. #else
  1118. pToken( p )
  1119. TokNode *p;
  1120. #endif
  1121. {
  1122.     require(p!=NULL, "pToken: NULL node");
  1123.     require(p->ntype==nToken, "pToken: not token node");
  1124.  
  1125.     if ( p->wild_card ) printf(" .");
  1126.     printf( " %s", TerminalString(p->token));
  1127.     PRINT(p->next);
  1128. }
  1129.  
  1130. /* How to print out a terminal node */
  1131. void
  1132. #ifdef __STDC__
  1133. pAction( ActionNode *p )
  1134. #else
  1135. pAction( p )
  1136. ActionNode *p;
  1137. #endif
  1138. {
  1139.     require(p!=NULL, "pAction: NULL node");
  1140.     require(p->ntype==nAction, "pAction: not action node");
  1141.     
  1142.     PRINT(p->next);
  1143. }
  1144.  
  1145.                     /* F i l l  F o l l o w  L i s t s */
  1146.  
  1147. /*
  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.
  1150.  * i.e.
  1151.  *
  1152.  *        r: -o-R-o-->o--> Ptr to node following rule r in another rule
  1153.  *                    |
  1154.  *                    o--> Ptr to node following another reference to r.
  1155.  *
  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.
  1161.  *
  1162.  * Note that this mechanism also gives a free cross-reference mechanism.
  1163.  *
  1164.  * The entire syntax diagram is layed out like this:
  1165.  *
  1166.  * SynDiag
  1167.  *    |
  1168.  *    v
  1169.  *    o-->R1--o
  1170.  *    |
  1171.  *    o-->R2--o
  1172.  *    |
  1173.  *    ...
  1174.  *    |
  1175.  *    o-->Rn--o
  1176.  *
  1177.  */
  1178. void
  1179. #ifdef __STDC__
  1180. FoLink( Node *p )
  1181. #else
  1182. FoLink( p )
  1183. Node *p;
  1184. #endif
  1185. {
  1186.     RuleEntry *q;
  1187.     Junction *j = (Junction *) p;
  1188.     RuleRefNode *r = (RuleRefNode *) p;
  1189.  
  1190.     if ( p==NULL ) return;
  1191.     require(p->ntype>=1 && p->ntype<=NumNodeTypes,
  1192.             eMsgd("FoLink: invalid diagram node: ntype==%d",p->ntype));
  1193.     switch ( p->ntype )
  1194.     {
  1195.         case nJunction :
  1196.             if ( j->fvisited ) return;
  1197.             if ( j->jtype == EndRule ) return;
  1198.             j->fvisited = TRUE;
  1199.             FoLink( j->p1 );
  1200.             FoLink( j->p2 );
  1201.             return;
  1202.         case nRuleRef :
  1203.             if ( r->linked ) return;
  1204.             q = (RuleEntry *) hash_get(Rname, r->text);
  1205.             if ( q == NULL )
  1206.             {
  1207.                 warnFL( eMsg1("rule %s not defined",r->text), FileStr[r->file], r->line );
  1208.             }
  1209.             else
  1210.             {
  1211.                 if ( r->parms!=NULL && RulePtr[q->rulenum]->pdecl==NULL )
  1212.                 {
  1213.                     warnFL( eMsg1("rule %s accepts no parameter(s)", r->text),
  1214.                             FileStr[r->file], r->line );
  1215.                 }
  1216.                 if ( r->parms==NULL && RulePtr[q->rulenum]->pdecl!=NULL )
  1217.                 {
  1218.                     warnFL( eMsg1("rule %s requires parameter(s)", r->text),
  1219.                             FileStr[r->file], r->line );
  1220.                 }
  1221.                 if ( r->assign!=NULL && RulePtr[q->rulenum]->ret==NULL )
  1222.                 {
  1223.                     warnFL( eMsg1("rule %s yields no return value(s)", r->text),
  1224.                             FileStr[r->file], r->line );
  1225.                 }
  1226.                 if ( r->assign==NULL && RulePtr[q->rulenum]->ret!=NULL )
  1227.                 {
  1228.                     warnFL( eMsg1("rule %s returns a value(s)", r->text),
  1229.                             FileStr[r->file], r->line );
  1230.                 }
  1231.                 if ( !r->linked )
  1232.                 {
  1233.                     addFoLink(    r->next, r->rname, RulePtr[q->rulenum] );
  1234.                     r->linked = TRUE;
  1235.                 }
  1236.             }
  1237.             FoLink( r->next );
  1238.             return;
  1239.         case nToken :
  1240.             FoLink( ((TokNode *)p)->next );
  1241.             return;
  1242.         case nAction :
  1243.             FoLink( ((ActionNode *)p)->next );
  1244.             return;
  1245.         default :
  1246.             fatal("invalid node type");
  1247.     }
  1248. }
  1249.  
  1250. /*
  1251.  * Add a reference to the end of a rule.
  1252.  *
  1253.  * 'r' points to the RuleBlk node in a rule.  r->end points to the last node
  1254.  * (EndRule jtype) in a rule.
  1255.  *
  1256.  * Initial:
  1257.  *        r->end -->     o
  1258.  *
  1259.  * After:
  1260.  *        r->end -->     o-->o--> Ptr to node following rule r in another rule
  1261.  *                        |
  1262.  *                        o--> Ptr to node following another reference to r.
  1263.  *
  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).
  1267.  */
  1268. void
  1269. #ifdef __STDC__
  1270. addFoLink( Node *p, char *rname, Junction *r )
  1271. #else
  1272. addFoLink( p, rname, r )
  1273. Node *p;
  1274. char *rname;
  1275. Junction *r;
  1276. #endif
  1277. {
  1278.     Junction *j;
  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");
  1283.  
  1284.     j = newJunction();
  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 */
  1289. }
  1290.  
  1291. void
  1292. #ifdef __STDC__
  1293. GenCrossRef( Junction *p )
  1294. #else
  1295. GenCrossRef( p )
  1296. Junction *p;
  1297. #endif
  1298. {
  1299.     set a;
  1300.     Junction *j;
  1301.     RuleEntry *q;
  1302.     unsigned e;
  1303.     require(p!=NULL, "GenCrossRef: why are you passing me a null grammar?");
  1304.  
  1305.     printf("Cross Reference:\n\n");
  1306.     a = empty;
  1307.     for (; p!=NULL; p = (Junction *)p->p2)
  1308.     {
  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)
  1312.         {
  1313.             q = (RuleEntry *) hash_get(Rname, j->rname);
  1314.             require(q!=NULL, "GenCrossRef: FoLinks are screwed up");
  1315.             set_orel(q->rulenum, &a);
  1316.         }
  1317.         for (; !set_nil(a); set_rm(e, a))
  1318.         {
  1319.             e = set_int(a);
  1320.             printf(" %s", RulePtr[e]->rname);
  1321.         }
  1322.         printf(" }\n");
  1323.     }
  1324.     set_free( a );
  1325. }
  1326.