home *** CD-ROM | disk | FTP | other *** search
/ OS/2 Shareware BBS: 10 Tools / 10-Tools.zip / pccts1.zip / ANTLR / MISC.C < prev    next >
C/C++ Source or Header  |  1993-09-02  |  28KB  |  1,128 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.10
  43.  * Terence Parr
  44.  * Purdue University
  45.  * 1989-1993
  46.  */
  47. #include <stdio.h>
  48. #ifdef __cplusplus
  49. #ifndef __STDC__
  50. #define __STDC__
  51. #endif
  52. #endif
  53. #include "set.h"
  54. #include "syn.h"
  55. #include "hash.h"
  56. #include "generic.h"
  57. #include "dlgdef.h"
  58.  
  59. static int tsize=TSChunk;        /* size of token str arrays */
  60.  
  61.                 /* T o k e n  M a n i p u l a t i o n */
  62.  
  63. /*
  64.  * add token 't' to the TokenStr/Expr array.  Make more room if necessary.
  65.  * 't' is either an expression or a token name.
  66.  *
  67.  * There is only one TokenStr array, but multiple ExprStr's.  Therefore,
  68.  * for each lex class (element of lclass) we must extend the ExprStr array.
  69.  * ExprStr's and TokenStr are always all the same size.
  70.  *
  71.  * Also, there is a Texpr hash table for each automaton.
  72.  */
  73. static void
  74. #ifdef __STDC__
  75. Ttrack( char *t )
  76. #else
  77. Ttrack( t )
  78. char *t;
  79. #endif
  80. {
  81.     if ( TokenNum >= tsize )    /* terminal table overflow? */
  82.     {
  83.         char **p;
  84.         int i, more, j;
  85.  
  86.         more = TSChunk * (1 + ((TokenNum-tsize) / TSChunk));
  87.         tsize += more;
  88.         TokenStr = (char **) realloc(TokenStr, tsize*sizeof(char *));
  89.         require(TokenStr != NULL, "Ttrack: can't extend TokenStr");
  90.         for (i=0; i<NumLexClasses; i++)
  91.         {
  92.             lclass[i].exprs = (char **)
  93.                               realloc(lclass[i].exprs, tsize*sizeof(char *));
  94.             require(lclass[i].exprs != NULL, "Ttrack: can't extend ExprStr");
  95.             for (p= &lclass[i].exprs[tsize-more],j=1; j<=more; j++) *p++ = NULL;
  96.         }
  97.         for (p= &TokenStr[tsize-more],i=1; i<=more; i++) *p++ = NULL;
  98.         lexmode( CurrentLexClass ); /* reset ExprStr in case table moved */
  99.     }
  100.     if ( *t == '"' ) ExprStr[TokenNum] = t;
  101.     else TokenStr[TokenNum] = t;
  102. }
  103.  
  104. static Expr *
  105. #ifdef __STDC__
  106. newExpr( char *e )
  107. #else
  108. newExpr( e )
  109. char *e;
  110. #endif
  111. {
  112.     Expr *p = (Expr *) calloc(1, sizeof(Expr));
  113.     require(p!=NULL, "newExpr: cannot alloc Expr node");
  114.  
  115.     p->expr = e;
  116.     p->lclass = CurrentLexClass;
  117.     return p;
  118. }
  119.  
  120. /* switch to lexical class/mode m.  This amounts to creating a new
  121.  * lex mode if one does not already exist and making ExprStr point
  122.  * to the correct char string array.  We must also switch Texpr tables.
  123.  *
  124.  * BTW, we need multiple ExprStr arrays because more than one automaton
  125.  * may have the same label for a token, but with different expressions.
  126.  * We need to track an expr for each automaton.  If we disallowed this
  127.  * feature, only one ExprStr would be required.
  128.  */
  129. void
  130. #ifdef __STDC__
  131. lexclass( char *m )
  132. #else
  133. lexclass( m )
  134. char *m;
  135. #endif
  136. {
  137.     int i;
  138.     TermEntry *p;
  139.     static char EOFSTR[] = "\"@\"";
  140.  
  141.     if ( hash_get(Tname, m) != NULL )
  142.     {
  143.         warn(eMsg1("lexclass name conflicts with token/errclass label '%s'",m));
  144.     }
  145.     /* does m already exist? */
  146.     i = LexClassIndex(m);
  147.     if ( i != -1 ) {lexmode(i); return;}
  148.     /* must make new one */
  149.     NumLexClasses++;
  150.     CurrentLexClass = NumLexClasses-1;
  151.     require(NumLexClasses<=MaxLexClasses, "number of allowable lexclasses exceeded\nIncrease MaxLexClasses in generic.h and recompile all C files");
  152.     lclass[CurrentLexClass].classnum = m;
  153.     lclass[CurrentLexClass].exprs = (char **) calloc(tsize, sizeof(char *));
  154.     require(lclass[CurrentLexClass].exprs!=NULL,
  155.             "lexclass: cannot allocate ExprStr");
  156.     lclass[CurrentLexClass].htable = newHashTable();
  157.     ExprStr = lclass[CurrentLexClass].exprs;
  158.     Texpr = lclass[CurrentLexClass].htable;
  159.     /* define EOF for each automaton */
  160.     p = newTermEntry( EOFSTR );
  161.     p->token = EofToken;
  162.     hash_add(Texpr, EOFSTR, (Entry *)p);
  163.     list_add(&ExprOrder, (void *)newExpr(EOFSTR));
  164.     ExprStr[EofToken] = EOFSTR;
  165. }
  166.  
  167. void
  168. #ifdef __STDC__
  169. lexmode( int i )
  170. #else
  171. lexmode( i )
  172. int i;
  173. #endif
  174. {
  175.     require(i<NumLexClasses, "lexmode: invalid mode");
  176.     ExprStr = lclass[i].exprs;
  177.     Texpr = lclass[i].htable;
  178.     CurrentLexClass = i;
  179. }
  180.  
  181. /* return index into lclass array of lexical class. return -1 if nonexistent */
  182. int
  183. #ifdef __STDC__
  184. LexClassIndex( char *cl )
  185. #else
  186. LexClassIndex( cl )
  187. char *cl;
  188. #endif
  189. {
  190.     int i;
  191.  
  192.     for (i=0; i<NumLexClasses; i++)
  193.     {
  194.         if ( strcmp(lclass[i].classnum, cl) == 0 ) return i;
  195.     }
  196.     return -1;
  197. }
  198.  
  199. int
  200. #ifdef __STDC__
  201. hasAction( char *expr )
  202. #else
  203. hasAction( expr )
  204. char *expr;
  205. #endif
  206. {
  207.     TermEntry *p;
  208.     require(expr!=NULL, "hasAction: invalid expr");
  209.  
  210.     p = (TermEntry *) hash_get(Texpr, expr);
  211.     require(p!=NULL, eMsg1("hasAction: expr '%s' doesn't exist",expr));
  212.     return (p->action!=NULL);
  213. }
  214.  
  215. void
  216. #ifdef __STDC__
  217. setHasAction( char *expr, char *action )
  218. #else
  219. setHasAction( expr, action )
  220. char *expr;
  221. char *action;
  222. #endif
  223. {
  224.     TermEntry *p;
  225.     require(expr!=NULL, "setHasAction: invalid expr");
  226.  
  227.     p = (TermEntry *) hash_get(Texpr, expr);
  228.     require(p!=NULL, eMsg1("setHasAction: expr '%s' doesn't exist",expr));
  229.     p->action = action;
  230. }
  231.  
  232. /*
  233.  * Add a token name.  Return the token number associated with it.  If it already
  234.  * exists, then return the token number assigned to it.
  235.  *
  236.  * Track the order in which tokens are found so that the DLG output maintains
  237.  * that order.  It also lets us map token numbers to strings.
  238.  */
  239. int
  240. #ifdef __STDC__
  241. addTname( char *token )
  242. #else
  243. addTname( token )
  244. char *token;
  245. #endif
  246. {
  247.     TermEntry *p;
  248.     require(token!=NULL, "addTname: invalid token name");
  249.  
  250.     if ( (p=(TermEntry *)hash_get(Tname, token)) != NULL ) return p->token;
  251.     p = newTermEntry( token );
  252.     Ttrack( p->str );
  253.     p->token = TokenNum++;
  254.     hash_add(Tname, token, (Entry *)p);
  255.     return p->token;
  256. }
  257.  
  258. /*
  259.  * Add a token expr.  Return the token number associated with it.  If it already
  260.  * exists, then return the token number assigned to it.
  261.  */
  262. int
  263. #ifdef __STDC__
  264. addTexpr( char *expr )
  265. #else
  266. addTexpr( expr )
  267. char *expr;
  268. #endif
  269. {
  270.     TermEntry *p;
  271.     require(expr!=NULL, "addTexpr: invalid regular expression");
  272.  
  273.     if ( (p=(TermEntry *)hash_get(Texpr, expr)) != NULL ) return p->token;
  274.     p = newTermEntry( expr );
  275.     Ttrack( p->str );
  276.     /* track the order in which they occur */
  277.     list_add(&ExprOrder, (void *)newExpr(p->str));
  278.     p->token = TokenNum++;
  279.     hash_add(Texpr, expr, (Entry *)p);
  280.     return p->token;
  281. }
  282.  
  283. /* return the token number of 'term'.  Return 0 if no 'term' exists */
  284. int
  285. #ifdef __STDC__
  286. Tnum( char *term )
  287. #else
  288. Tnum( term )
  289. char *term;
  290. #endif
  291. {
  292.     TermEntry *p;
  293.     require(term!=NULL, "Tnum: invalid terminal");
  294.     
  295.     if ( *term=='"' ) p = (TermEntry *) hash_get(Texpr, term);
  296.     else p = (TermEntry *) hash_get(Tname, term);
  297.     if ( p == NULL ) return 0;
  298.     else return p->token;
  299. }
  300.  
  301. /* associate a Name with an expr.  If both have been already assigned
  302.  * token numbers, then an error is reported.  Add the token or expr
  303.  * that has not been added if no error.  This 'represents' the #token
  304.  * ANTLR pseudo-op.  If both have not been defined, define them both
  305.  * linked to same token number.
  306.  */
  307. void
  308. #ifdef __STDC__
  309. Tklink( char *token, char *expr )
  310. #else
  311. Tklink( token, expr )
  312. char *token;
  313. char *expr;
  314. #endif
  315. {
  316.     TermEntry *p, *q;
  317.     require(token!=NULL && expr!=NULL, "Tklink: invalid token name and/or expr");
  318.  
  319.     p = (TermEntry *) hash_get(Tname, token);
  320.     q = (TermEntry *) hash_get(Texpr, expr);
  321.     if ( p != NULL && q != NULL )    /* both defined */
  322.     {
  323.         warn( eMsg2("token name %s and rexpr %s already defined; ignored",
  324.                     token, expr) );
  325.         return;
  326.     }
  327.     if ( p==NULL && q==NULL )        /* both not defined */
  328.     {
  329.         int t = addTname( token );
  330.         q = newTermEntry( expr );
  331.         hash_add(Texpr, expr, (Entry *)q);
  332.         q->token = t;
  333.         ExprStr[t] = q->str;
  334.         /* track the order in which they occur */
  335.         list_add(&ExprOrder, (void *)newExpr(q->str));
  336.         return;
  337.     }
  338.     if ( p != NULL )                /* one is defined, one is not */
  339.     {
  340.         q = newTermEntry( expr );
  341.         hash_add(Texpr, expr, (Entry *)q);
  342.         q->token = p->token;
  343.         ExprStr[p->token] = q->str;    /* both expr and token str defined now */
  344.         list_add(&ExprOrder, (void *)newExpr(q->str));
  345.     }
  346.     else                            /* trying to associate name with expr here*/
  347.     {
  348.         p = newTermEntry( token );
  349.         hash_add(Tname, token, (Entry *)p);
  350.         p->token = q->token;
  351.         TokenStr[p->token] = p->str;/* both expr and token str defined now */
  352.     }
  353. }
  354.  
  355. /*
  356.  * Given a string, this function allocates and returns a pointer to a
  357.  * hash table record of size 'sz' whose "str" pointer is reset to a position
  358.  * in the string table.
  359.  */
  360. Entry *
  361. #ifdef __STDC__
  362. newEntry( char *text, int sz )
  363. #else
  364. newEntry( text, sz )
  365. char *text;
  366. int sz;
  367. #endif
  368. {
  369.     Entry *p;
  370.     require(text!=NULL, "new: NULL terminal");
  371.     
  372.     if ( (p = (Entry *) calloc(1,sz)) == 0 )
  373.     {
  374.         fatal("newEntry: out of memory for terminals\n");
  375.         exit(1);
  376.     }
  377.     p->str = mystrdup(text);
  378.     
  379.     return(p);
  380. }
  381.  
  382. /*
  383.  * add an element to a list.
  384.  *
  385.  * Any non-empty list has a sentinel node whose 'elem' pointer is really
  386.  * a pointer to the last element.  (i.e. length(list) = #elemIn(list)+1).
  387.  * Elements are appended to the list.
  388.  */
  389. void
  390. #ifdef __STDC__
  391. list_add( ListNode **list, void *e )
  392. #else
  393. list_add( list, e )
  394. ListNode **list;
  395. void *e;
  396. #endif
  397. {
  398.     ListNode *p, *tail;
  399.     require(e!=NULL, "list_add: attempting to add NULL list element");
  400.  
  401.     p = newListNode;
  402.     require(p!=NULL, "list_add: cannot alloc new list node");
  403.     p->elem = e;
  404.     if ( *list == NULL )
  405.     {
  406.         ListNode *sentinel = newListNode;
  407.         require(sentinel!=NULL, "list_add: cannot alloc sentinel node");
  408.         *list=sentinel;
  409.         sentinel->next = p;
  410.         sentinel->elem = (char *)p;        /* set tail pointer */
  411.     }
  412.     else                                /* find end of list */
  413.     {
  414.         tail = (ListNode *) (*list)->elem;    /* get tail pointer */
  415.         tail->next = p;
  416.         (*list)->elem = (char *) p;        /* reset tail */
  417.     }
  418. }
  419.  
  420. void
  421. #ifdef __STDC__
  422. list_apply( ListNode *list, void (*f)(void *) )
  423. #else
  424. list_apply( list, f )
  425. ListNode *list;
  426. void (*f)();
  427. #endif
  428. {
  429.     ListNode *p;
  430.     require(f!=NULL, "list_apply: NULL function to apply");
  431.  
  432.     if ( list == NULL ) return;
  433.     for (p = list->next; p!=NULL; p=p->next) (*f)( p->elem );
  434. }
  435.  
  436.             /* F O L L O W  C y c l e  S t u f f */
  437.         
  438. /* make a key based upon (rulename, computation, k value).
  439.  * Computation values are 'i'==FIRST, 'o'==FOLLOW.
  440.  */
  441. char *
  442. #ifdef __STDC__
  443. Fkey( char *rule, int computation, int k )
  444. #else
  445. Fkey( rule, computation, k )
  446. char *rule;
  447. int computation;
  448. int k;
  449. #endif
  450. {
  451.     static char key[MaxRuleName+2+1];
  452.     int i;
  453.     
  454.     if ( k > 255 ) 
  455.         fatal("k>255 is too big for this implementation of ANTLR!\n");
  456.     if ( (i=strlen(rule)) > MaxRuleName )
  457.         fatal( eMsgd("rule name > max of %d\n", MaxRuleName) );
  458.     strcpy(key,rule);
  459.     key[i] = (int) computation;
  460.     key[i+1] = (char) ((unsigned int) k);
  461.     key[i+2] = '\0';
  462.     return key;
  463. }
  464.  
  465. /* Push a rule onto the kth FOLLOW stack */
  466. void
  467. #ifdef __STDC__
  468. FoPush( char *rule, int k )
  469. #else
  470. FoPush( rule, k )
  471. char *rule;
  472. int k;
  473. #endif
  474. {
  475.     RuleEntry *r;
  476.     require(rule!=NULL, "FoPush: tried to push NULL rule");
  477.     require(k<=CLL_k,    "FoPush: tried to access non-existent stack");
  478.  
  479.     /*fprintf(stderr, "FoPush(%s)\n", rule);*/
  480.     r = (RuleEntry *) hash_get(Rname, rule);
  481.     if ( r == NULL ) {fatal( eMsg1("rule %s must be defined but isn't", rule) );}
  482.     if ( FoStack[k] == NULL )        /* Does the kth stack exist yet? */
  483.     {
  484.         /*fprintf(stderr, "allocating FoStack\n");*/
  485.         FoStack[k] = (int *) calloc(FoStackSize, sizeof(int));
  486.         require(FoStack[k]!=NULL, "FoPush: cannot allocate FOLLOW stack\n");
  487.     }
  488.     if ( FoTOS[k] == NULL )
  489.     {
  490.         FoTOS[k]=FoStack[k];
  491.         *(FoTOS[k]) = r->rulenum;
  492.     }
  493.     else
  494.     {
  495. #ifdef MEMCHK
  496.         require(valid(FoStack[k]), "FoPush: invalid FoStack");
  497. #endif
  498.         if ( FoTOS[k] >= &(FoStack[k][FoStackSize-1]) )
  499.             fatal( eMsgd("exceeded max depth of FOLLOW recursion (%d)\n",
  500.                         FoStackSize) );
  501.         require(FoTOS[k]>=FoStack[k],
  502.                 eMsg1("FoPush: FoStack stack-ptr is playing out of its sandbox",
  503.                       rule));
  504.         ++(FoTOS[k]);
  505.         *(FoTOS[k]) = r->rulenum;
  506.     }
  507.     {
  508.         /*
  509.         int *p;
  510.         fprintf(stderr, "FoStack[k=%d]:\n", k);
  511.         for (p=FoStack[k]; p<=FoTOS[k]; p++)
  512.         {
  513.             fprintf(stderr, "\t%s\n", RulePtr[*p]->rname);
  514.         }
  515.         */
  516.     }
  517. }
  518.  
  519. /* Pop one rule off of the FOLLOW stack.  TOS ptr is NULL if empty. */
  520. void
  521. #ifdef __STDC__
  522. FoPop( int k )
  523. #else
  524. FoPop( k )
  525. int k;
  526. #endif
  527. {
  528.     require(k<=CLL_k, "FoPop: tried to access non-existent stack");
  529.     /*fprintf(stderr, "FoPop\n");*/
  530.     require(FoTOS[k]>=FoStack[k]&&FoTOS[k]<=&(FoStack[k][FoStackSize-1]),
  531.             "FoPop: FoStack stack-ptr is playing out of its sandbox");
  532.     if ( FoTOS[k] == FoStack[k] ) FoTOS[k] = NULL;
  533.     else (FoTOS[k])--;
  534. }
  535.  
  536. /* Compute FOLLOW cycle.
  537.  * Mark all FOLLOW sets for rules in cycle as incomplete.
  538.  * Then, save cycle on the cycle list (Cycles) for later resolution.
  539.  * The Cycle is stored in the form:
  540.  *        (head of cycle==croot, rest of rules in cycle==cyclicDep)
  541.  *
  542.  * e.g. (Fo means "FOLLOW of", "-->" means requires or depends on)
  543.  *
  544.  *        Fo(x)-->Fo(a)-->Fo(b)-->Fo(c)-->Fo(x)
  545.  *                                           ^----Infinite recursion (cycle)
  546.  *
  547.  * the cycle would be: x -> {a,b,c} or stored as (x,{a,b,c}).  Fo(x) depends
  548.  * on the FOLLOW of a,b, and c.  The root of a cycle is always complete after
  549.  * Fo(x) finishes.  Fo(a,b,c) however are not.  It turns out that all rules
  550.  * in a FOLLOW cycle have the same FOLLOW set.
  551.  */
  552. void
  553. #ifdef __STDC__
  554. RegisterCycle( char *rule, int k )
  555. #else
  556. RegisterCycle( rule, k )
  557. char *rule;
  558. int k;
  559. #endif
  560. {
  561.     CacheEntry *f;
  562.     Cycle *c;
  563.     int *p;
  564.     RuleEntry *r;
  565.     require(rule!=NULL, "RegisterCycle: tried to register NULL rule");
  566.     require(k<=CLL_k,    "RegisterCycle: tried to access non-existent stack");
  567.  
  568.     /*fprintf(stderr, "RegisterCycle(%s)\n", rule);*/
  569.     /* Find cycle start */
  570.     r = (RuleEntry *) hash_get(Rname, rule);
  571.     require(r!=NULL,eMsg1("rule %s must be defined but isn't", rule));
  572.     require(FoTOS[k]>=FoStack[k]&&FoTOS[k]<=&(FoStack[k][FoStackSize-1]),
  573.             eMsg1("RegisterCycle(%s): FoStack stack-ptr is playing out of its sandbox",
  574.                   rule));
  575. /*    if ( FoTOS[k]<FoStack[k]||FoTOS[k]>&(FoStack[k][FoStackSize-1]) )
  576.     {
  577.         fprintf(stderr, "RegisterCycle(%s): FoStack stack-ptr is playing out of its sandbox\n",
  578.                         rule);
  579.         fprintf(stderr, "RegisterCycle: sp==0x%x out of bounds 0x%x...0x%x\n",
  580.                         FoTOS[k], FoStack[k], &(FoStack[k][FoStackSize-1]));
  581.         exit(1);
  582.     }
  583. */
  584. #ifdef MEMCHK
  585.     require(valid(FoStack[k]), "RegisterCycle: invalid FoStack");
  586. #endif
  587.     for (p=FoTOS[k]; *p != r->rulenum && p >= FoStack[k]; --p) {;}
  588.     require(p>=FoStack[k], "RegisterCycle: FoStack is screwed up beyond belief");
  589.     if ( p == FoTOS[k] ) return;    /* don't worry about cycles to oneself */
  590.     
  591.     /* compute cyclic dependents (rules in cycle except head) */
  592.     c = newCycle;
  593.     require(c!=NULL, "RegisterCycle: couldn't alloc new cycle");
  594.     c->cyclicDep = empty;
  595.     c->croot = *p++;        /* record root of cycle */
  596.     for (; p<=FoTOS[k]; p++)
  597.     {
  598.         /* Mark all dependent rules as incomplete */
  599.         f = (CacheEntry *) hash_get(Fcache, Fkey(RulePtr[*p]->rname,'o',k));
  600.         if ( f==NULL )
  601.         {
  602.             f = newCacheEntry( Fkey(RulePtr[*p]->rname,'o',k) );
  603.             hash_add(Fcache, Fkey(RulePtr[*p]->rname,'o',k), (Entry *)f);
  604.         }
  605.         f->incomplete = TRUE;
  606.         
  607.         set_orel(*p, &(c->cyclicDep)); /* mark rule as dependent of croot */
  608.     }
  609.     list_add(&(Cycles[k]), (void *)c);
  610. }
  611.  
  612. /* make all rules in cycle complete
  613.  *
  614.  * while ( some set has changed ) do
  615.  *        for each cycle do
  616.  *            if degree of FOLLOW set for croot > old degree then
  617.  *                update all FOLLOW sets for rules in cyclic dependency
  618.  *                change = TRUE
  619.  *            endif
  620.  *        endfor
  621.  * endwhile
  622.  */
  623. void
  624. #ifdef __STDC__
  625. ResolveFoCycles( int k )
  626. #else
  627. ResolveFoCycles( k )
  628. int k;
  629. #endif
  630. {
  631.     ListNode *p, *q;
  632.     Cycle *c;
  633.     int changed = 1;
  634.     CacheEntry *f,*g;
  635.     int r,i;
  636.     unsigned d;
  637.     
  638.     /*fprintf(stderr, "Resolving following cycles for %d\n", k);*/
  639.     while ( changed )
  640.     {
  641.         changed = 0;
  642.         i = 0;
  643.         for (p = Cycles[k]->next; p!=NULL; p=p->next)
  644.         {
  645.             c = (Cycle *) p->elem;
  646.             /*fprintf(stderr, "cycle %d: %s -->", i++, RulePtr[c->croot]->rname);*/
  647.             /*s_fprT(stderr, c->cyclicDep);*/
  648.             /*fprintf(stderr, "\n");*/
  649.             f = (CacheEntry *)
  650.                     hash_get(Fcache, Fkey(RulePtr[c->croot]->rname,'o',k));
  651.             require(f!=NULL, eMsg1("FOLLOW(%s) must be in cache but isn't", RulePtr[c->croot]->rname) );
  652.             if ( (d=set_deg(f->fset)) > c->deg )
  653.             {
  654.                 /*fprintf(stderr, "Fo(%s) has changed\n", RulePtr[c->croot]->rname);*/
  655.                 changed = 1;
  656.                 c->deg = d;        /* update cycle FOLLOW set degree */
  657.                 while ( !set_nil(c->cyclicDep) )
  658.                 {
  659.                     r = set_int(c->cyclicDep);
  660.                     set_rm(r, c->cyclicDep);
  661.                     /*fprintf(stderr, "updating Fo(%s)\n", RulePtr[r]->rname);*/
  662.                     g = (CacheEntry *)
  663.                             hash_get(Fcache, Fkey(RulePtr[r]->rname,'o',k));
  664.                     require(g!=NULL, eMsg1("FOLLOW(%s) must be in cache but isn't", RulePtr[r]->rname) );
  665.                     set_orin(&(g->fset), f->fset);
  666.                     g->incomplete = FALSE;
  667.                 }
  668.             }
  669.         }
  670.         if ( i == 1 ) changed = 0;    /* if only 1 cycle, no need to repeat */
  671.     }
  672.     /* kill Cycle list */
  673.     for (q = Cycles[k]->next; q != NULL; q=p)
  674.     {
  675.         p = q->next;
  676.         set_free( ((Cycle *)q->elem)->cyclicDep );
  677.         free(q);
  678.     }
  679.     free( Cycles[k] );
  680.     Cycles[k] = NULL;
  681. }
  682.  
  683.  
  684.             /* P r i n t i n g  S y n t a x  D i a g r a m s */
  685.  
  686. static void
  687. #ifdef __STDC__
  688. pBlk( Junction *q, int btype )
  689. #else
  690. pBlk( q, btype )
  691. Junction *q;
  692. int btype;
  693. #endif
  694. {
  695.     int k,a;
  696.     Junction *alt, *p;
  697.  
  698.     q->end->pvisited = TRUE;
  699.     if ( btype == aLoopBegin )
  700.     {
  701.         require(q->p2!=NULL, "pBlk: invalid ()* block");
  702.         PRINT(q->p1);
  703.         alt = (Junction *)q->p2;
  704.         PRINT(alt->p1);
  705.         if ( PrintAnnotate )
  706.         {
  707.             printf(" /* Opt ");
  708.             k = 1;
  709.             while ( !set_nil(alt->fset[k]) )
  710.             {
  711.                 s_fprT(stdout, alt->fset[k]);
  712.                 if ( k++ == CLL_k ) break;
  713.                 if ( !set_nil(alt->fset[k]) ) printf(", ");
  714.             }
  715.             printf(" */\n");
  716.         }
  717.         return;
  718.     }
  719.     for (a=1,alt=q; alt != NULL; alt= (Junction *) alt->p2, a++)
  720.     {
  721.         if ( alt->p1 != NULL ) PRINT(alt->p1);
  722.         if ( PrintAnnotate )
  723.         {
  724.             printf( " /* [%d] ", alt->altnum);
  725.             k = 1;
  726.             while ( !set_nil(alt->fset[k]) )
  727.             {
  728.                 s_fprT(stdout, alt->fset[k]);
  729.                 if ( k++ == CLL_k ) break;
  730.                 if ( !set_nil(alt->fset[k]) ) printf(", ");
  731.             }
  732.             if ( alt->p2 == NULL && btype == aOptBlk )
  733.                 printf( " (optional branch) */\n");
  734.             else printf( " */\n");
  735.         }
  736.         if ( alt->p2 != NULL && !(((Junction *)alt->p2)->p2==NULL && btype == aOptBlk) )
  737.         {
  738.             if ( pLevel == 1 )
  739.             {
  740.                 printf("\n");
  741.                 if ( a+1==pAlt1 || a+1==pAlt2 ) printf("=>");
  742.                 printf("\t");
  743.             }
  744.             else printf(" ");
  745.             printf("|");
  746.             if ( pLevel == 1 )
  747.             {
  748.                 p = (Junction *) ((Junction *)alt->p2)->p1;
  749.                 while ( p!=NULL )
  750.                 {
  751.                     if ( p->ntype==nAction )
  752.                     {
  753.                         p=(Junction *)((ActionNode *)p)->next;
  754.                         continue;
  755.                     }
  756.                     if ( p->ntype!=nJunction )
  757.                     {
  758.                         break;
  759.                     }
  760.                     if ( p->jtype==EndBlk || p->jtype==EndRule )
  761.                     {
  762.                         p = NULL;
  763.                         break;
  764.                     }
  765.                     p = (Junction *)p->p1;
  766.                 }
  767.                 if ( p==NULL ) printf("\n\t");    /* Empty alt? */
  768.             }
  769.         }
  770.     }
  771.     q->end->pvisited = FALSE;
  772. }
  773.  
  774. /* How to print out a junction */
  775. void
  776. #ifdef __STDC__
  777. pJunc( Junction *q )
  778. #else
  779. pJunc( q )
  780. Junction *q;
  781. #endif
  782. {
  783.     int dum_k;
  784.     int doing_rule;
  785.     require(q!=NULL, "pJunc: NULL node");
  786.     require(q->ntype==nJunction, "pJunc: not junction");
  787.     
  788.     if ( q->pvisited == TRUE ) return;
  789.     q->pvisited = TRUE;
  790.     switch ( q->jtype )
  791.     {
  792.         case aSubBlk :
  793.             if ( PrintAnnotate ) First(q, 1, q->jtype, &dum_k);
  794.             if ( q->end->p1 != NULL && ((Junction *)q->end->p1)->ntype==nJunction &&
  795.                  ((Junction *)q->end->p1)->jtype == EndRule ) doing_rule = 1;
  796.             else doing_rule = 0;
  797.             pLevel++;
  798.             if ( pLevel==1 )
  799.             {
  800.                 if ( pAlt1==1 ) printf("=>");
  801.                 printf("\t");
  802.             }
  803.             else printf(" ");
  804.             if ( doing_rule )
  805.             {
  806.                 if ( pLevel==1 ) printf(" ");
  807.                 pBlk(q,q->jtype);
  808.             }
  809.             else {
  810.                 printf("(");
  811.                 if ( pLevel==1 ) printf(" ");
  812.                 pBlk(q,q->jtype);
  813.                 if ( pLevel>1 ) printf(" ");
  814.                 printf(")");
  815.             }
  816.             if ( q->guess ) printf("?");
  817.             pLevel--;
  818.             if ( PrintAnnotate ) freeBlkFsets(q);
  819.             if ( q->end->p1 != NULL ) PRINT(q->end->p1);
  820.             break;
  821.         case aOptBlk :
  822.             if ( PrintAnnotate ) First(q, 1, q->jtype, &dum_k);
  823.             pLevel++;
  824.             if ( pLevel==1 )
  825.             {
  826.                 if ( pAlt1==1 ) printf("=>");
  827.                 printf("\t");
  828.             }
  829.             else printf(" ");
  830.             printf("{");
  831.             if ( pLevel==1 ) printf(" ");
  832.             pBlk(q,q->jtype);
  833.             if ( pLevel>1 ) printf(" ");
  834.             else printf("\n\t");
  835.             printf("}");
  836.             pLevel--;
  837.             if ( PrintAnnotate ) freeBlkFsets(q);
  838.             if ( q->end->p1 != NULL ) PRINT(q->end->p1);
  839.             break;
  840.         case aLoopBegin :
  841.             if ( PrintAnnotate ) First(q, 1, q->jtype, &dum_k);
  842.             pLevel++;
  843.             if ( pLevel==1 )
  844.             {
  845.                 if ( pAlt1==1 ) printf("=>");
  846.                 printf("\t");
  847.             }
  848.             else printf(" ");
  849.             printf("(");
  850.             if ( pLevel==1 ) printf(" ");
  851.             pBlk(q,q->jtype);
  852.             if ( pLevel>1 ) printf(" ");
  853.             else printf("\n\t");
  854.             printf(")*");
  855.             pLevel--;
  856.             if ( PrintAnnotate ) freeBlkFsets(q);
  857.             if ( q->end->p1 != NULL ) PRINT(q->end->p1);
  858.             break;
  859.         case aLoopBlk :
  860.             if ( PrintAnnotate ) First(q, 1, q->jtype, &dum_k);
  861.             pBlk(q,q->jtype);
  862.             if ( PrintAnnotate ) freeBlkFsets(q);
  863.             break;
  864.         case aPlusBlk :
  865.             if ( PrintAnnotate ) First(q, 1, q->jtype, &dum_k);
  866.             pLevel++;
  867.             if ( pLevel==1 )
  868.             {
  869.                 if ( pAlt1==1 ) printf("=>");
  870.                 printf("\t");
  871.             }
  872.             else printf(" ");
  873.             printf("(");
  874.             if ( pLevel==1 ) printf(" ");
  875.             pBlk(q,q->jtype);
  876.             if ( pLevel>1 ) printf(" ");
  877.             printf(")+");
  878.             pLevel--;
  879.             if ( PrintAnnotate ) freeBlkFsets(q);
  880.             if ( q->end->p1 != NULL ) PRINT(q->end->p1);
  881.             break;
  882.         case EndBlk :
  883.             break;
  884.         case RuleBlk :
  885.             printf( "\n%s :\n", q->rname);
  886.             PRINT(q->p1);
  887.             if ( q->p2 != NULL ) PRINT(q->p2);
  888.             break;
  889.         case Generic :
  890.             if ( q->p1 != NULL ) PRINT(q->p1);
  891.             q->pvisited = FALSE;
  892.             if ( q->p2 != NULL ) PRINT(q->p2);
  893.             break;
  894.         case EndRule :
  895.             printf( "\n\t;\n");
  896.             break;
  897.     }
  898.     q->pvisited = FALSE;
  899. }
  900.  
  901. /* How to print out a rule reference node */
  902. void
  903. #ifdef __STDC__
  904. pRuleRef( RuleRefNode *p )
  905. #else
  906. pRuleRef( p )
  907. RuleRefNode *p;
  908. #endif
  909. {
  910.     require(p!=NULL, "pRuleRef: NULL node");
  911.     require(p->ntype==nRuleRef, "pRuleRef: not rule ref node");
  912.     
  913.     printf( " %s", p->text);
  914.     PRINT(p->next);
  915. }
  916.  
  917. /* How to print out a terminal node */
  918. void
  919. #ifdef __STDC__
  920. pToken( TokNode *p )
  921. #else
  922. pToken( p )
  923. TokNode *p;
  924. #endif
  925. {
  926.     require(p!=NULL, "pToken: NULL node");
  927.     require(p->ntype==nToken, "pToken: not token node");
  928.  
  929.     printf( " %s", TerminalString(p->token));
  930.     PRINT(p->next);
  931. }
  932.  
  933. /* How to print out a terminal node */
  934. void
  935. #ifdef __STDC__
  936. pAction( ActionNode *p )
  937. #else
  938. pAction( p )
  939. ActionNode *p;
  940. #endif
  941. {
  942.     require(p!=NULL, "pAction: NULL node");
  943.     require(p->ntype==nAction, "pAction: not action node");
  944.     
  945.     PRINT(p->next);
  946. }
  947.  
  948.                     /* F i l l  F o l l o w  L i s t s */
  949.  
  950. /*
  951.  * Search all rules for all rule reference nodes, q to rule, r.
  952.  * Add q->next to follow list dangling off of rule r.
  953.  * i.e.
  954.  *
  955.  *        r: -o-R-o-->o--> Ptr to node following rule r in another rule
  956.  *                    |
  957.  *                    o--> Ptr to node following another reference to r.
  958.  *
  959.  * This is the data structure employed to avoid FOLLOW set computation.  We
  960.  * simply compute the FIRST (reach) of the EndRule Node which follows the
  961.  * list found at the end of all rules which are referenced elsewhere.  Rules
  962.  * not invoked by other rules have no follow list (r->end->p1==NULL).
  963.  * Generally, only start symbols are not invoked by another rule.
  964.  *
  965.  * Note that this mechanism also gives a free cross-reference mechanism.
  966.  *
  967.  * The entire syntax diagram is layed out like this:
  968.  *
  969.  * SynDiag
  970.  *    |
  971.  *    v
  972.  *    o-->R1--o
  973.  *    |
  974.  *    o-->R2--o
  975.  *    |
  976.  *    ...
  977.  *    |
  978.  *    o-->Rn--o
  979.  *
  980.  */
  981. void
  982. #ifdef __STDC__
  983. FoLink( Node *p )
  984. #else
  985. FoLink( p )
  986. Node *p;
  987. #endif
  988. {
  989.     RuleEntry *q;
  990.     Junction *j = (Junction *) p;
  991.     RuleRefNode *r = (RuleRefNode *) p;
  992.  
  993.     if ( p==NULL ) return;
  994.     require(p->ntype>=1 && p->ntype<=NumNodeTypes,    "FoLink: invalid diagram node");
  995.     switch ( p->ntype )
  996.     {
  997.         case nJunction :
  998.             if ( j->visited ) return;
  999.             if ( j->jtype == EndRule ) return;
  1000.             j->visited = TRUE;
  1001.             FoLink( j->p1 );
  1002.             FoLink( j->p2 );
  1003.             j->visited = FALSE;
  1004.             return;
  1005.         case nRuleRef :
  1006.             q = (RuleEntry *) hash_get(Rname, r->text);
  1007.             if ( q == NULL )
  1008.             {
  1009.                 warnNoFL( eMsg1("rule %s not defined",r->text) );
  1010.             }
  1011.             else
  1012.             {
  1013.                 if ( r->parms!=NULL && RulePtr[q->rulenum]->pdecl==NULL )
  1014.                 {
  1015.                     warnFL( eMsg1("rule %s accepts no parameter(s)", r->text),
  1016.                             FileStr[r->file], r->line );
  1017.                 }
  1018.                 if ( r->parms==NULL && RulePtr[q->rulenum]->pdecl!=NULL )
  1019.                 {
  1020.                     warnFL( eMsg1("rule %s requires parameter(s)", r->text),
  1021.                             FileStr[r->file], r->line );
  1022.                 }
  1023.                 if ( r->assign!=NULL && RulePtr[q->rulenum]->ret==NULL )
  1024.                 {
  1025.                     warnFL( eMsg1("rule %s yields no return value(s)", r->text),
  1026.                             FileStr[r->file], r->line );
  1027.                 }
  1028.                 if ( r->assign==NULL && RulePtr[q->rulenum]->ret!=NULL )
  1029.                 {
  1030.                     warnFL( eMsg1("rule %s returns a value(s)", r->text),
  1031.                             FileStr[r->file], r->line );
  1032.                 }
  1033.                 if ( !r->linked )
  1034.                 {
  1035.                     addFoLink(    r->next, r->rname, RulePtr[q->rulenum] );
  1036.                     r->linked = TRUE;
  1037.                 }
  1038.             }
  1039.             FoLink( r->next );
  1040.             return;
  1041.         case nToken :
  1042.             FoLink( ((TokNode *)p)->next );
  1043.             return;
  1044.         case nAction :
  1045.             FoLink( ((ActionNode *)p)->next );
  1046.             return;
  1047.         default :
  1048.             fatal("invalid node type");
  1049.     }
  1050. }
  1051.  
  1052. /*
  1053.  * Add a reference to the end of a rule.
  1054.  *
  1055.  * 'r' points to the RuleBlk node in a rule.  r->end points to the last node
  1056.  * (EndRule jtype) in a rule.
  1057.  *
  1058.  * Initial:
  1059.  *        r->end -->     o
  1060.  *
  1061.  * After:
  1062.  *        r->end -->     o-->o--> Ptr to node following rule r in another rule
  1063.  *                        |
  1064.  *                        o--> Ptr to node following another reference to r.
  1065.  *
  1066.  * Note that the links are added to the head of the list so that r->end->p1
  1067.  * always points to the most recently added follow-link.  At the end, it should
  1068.  * point to the last reference found in the grammar (starting from the 1st rule).
  1069.  */
  1070. void
  1071. #ifdef __STDC__
  1072. addFoLink( Node *p, char *rname, Junction *r )
  1073. #else
  1074. addFoLink( p, rname, r )
  1075. Node *p;
  1076. char *rname;
  1077. Junction *r;
  1078. #endif
  1079. {
  1080.     Junction *j;
  1081.     require(r!=NULL,                "addFoLink: incorrect rule graph");
  1082.     require(r->end!=NULL,            "addFoLink: incorrect rule graph");
  1083.     require(r->end->jtype==EndRule,    "addFoLink: incorrect rule graph");
  1084.     require(p!=NULL,                "addFoLink: NULL FOLLOW link");
  1085.  
  1086.     j = newJunction();
  1087.     j->rname = rname;            /* rname on follow links point to target rule */
  1088.     j->p1 = p;                    /* link to other rule */
  1089.     j->p2 = (Node *) r->end->p1;/* point to head of list */
  1090.     r->end->p1 = (Node *) j;    /* reset head to point to new node */
  1091. }
  1092.  
  1093. void
  1094. #ifdef __STDC__
  1095. GenCrossRef( Junction *p )
  1096. #else
  1097. GenCrossRef( p )
  1098. Junction *p;
  1099. #endif
  1100. {
  1101.     set a;
  1102.     Junction *j;
  1103.     RuleEntry *q;
  1104.     unsigned e;
  1105.     require(p!=NULL, "GenCrossRef: why are you passing me a null grammar?");
  1106.  
  1107.     printf("Cross Reference:\n\n");
  1108.     a = empty;
  1109.     for (; p!=NULL; p = (Junction *)p->p2)
  1110.     {
  1111.         printf("Rule %11s referenced by {", p->rname);
  1112.         /* make a set of rules for uniqueness */
  1113.         for (j = (Junction *)(p->end)->p1; j!=NULL; j = (Junction *)j->p2)
  1114.         {
  1115.             q = (RuleEntry *) hash_get(Rname, j->rname);
  1116.             require(q!=NULL, "GenCrossRef: FoLinks are screwed up");
  1117.             set_orel(q->rulenum, &a);
  1118.         }
  1119.         for (; !set_nil(a); set_rm(e, a))
  1120.         {
  1121.             e = set_int(a);
  1122.             printf(" %s", RulePtr[e]->rname);
  1123.         }
  1124.         printf(" }\n");
  1125.     }
  1126.     set_free( a );
  1127. }
  1128.