pd.if.org Git - pccts/blob - antlr/misc.c

   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.33
  43  * Terence Parr
  44  * Parr Research Corporation
  45  * with Purdue University and AHPCRC, University of Minnesota
  46  * 1989-1995
  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((char *)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((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;
 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_internal("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_internal("newEntry: out of memory for terminals\n");
 567                 exit(PCCTS_EXIT_FAILURE);
 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_internal( 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(PCCTS_EXIT_FAILURE);
 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((char *)q);
 870         }
 871         free( (char *)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_internal("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 }