home *** CD-ROM | disk | FTP | other *** search
/ OS/2 Shareware BBS: 10 Tools / 10-Tools.zip / pccts1.zip / ANTLR / BUILD.C < prev    next >
C/C++ Source or Header  |  1993-09-02  |  15KB  |  594 lines
  1. /*
  2.  * build.c -- functions associated with building syntax diagrams.
  3.  *
  4.  * $Id: build.c,v 1.4 1993/08/10 17:10:00 pccts Exp pccts $
  5.  * $Revision: 1.4 $
  6.  *
  7.  * SOFTWARE RIGHTS
  8.  *
  9.  * We reserve no LEGAL rights to the Purdue Compiler Construction Tool
  10.  * Set (PCCTS) -- PCCTS is in the public domain.  An individual or
  11.  * company may do whatever they wish with source code distributed with
  12.  * PCCTS or the code generated by PCCTS, including the incorporation of
  13.  * PCCTS, or its output, into commerical software.
  14.  * 
  15.  * We encourage users to develop software with PCCTS.  However, we do ask
  16.  * that credit is given to us for developing PCCTS.  By "credit",
  17.  * we mean that if you incorporate our source code into one of your
  18.  * programs (commercial product, research project, or otherwise) that you
  19.  * acknowledge this fact somewhere in the documentation, research report,
  20.  * etc...  If you like PCCTS and have developed a nice tool with the
  21.  * output, please mention that you developed it using PCCTS.  In
  22.  * addition, we ask that this header remain intact in our source code.
  23.  * As long as these guidelines are kept, we expect to continue enhancing
  24.  * this system and expect to make other tools available as they are
  25.  * completed.
  26.  *
  27.  * ANTLR 1.10
  28.  * Terence Parr
  29.  * Purdue University
  30.  * 1989-1993
  31.  */
  32. #include <stdio.h>
  33. #ifdef __cplusplus
  34. #ifndef __STDC__
  35. #define __STDC__
  36. #endif
  37. #endif
  38. #include "set.h"
  39. #include "syn.h"
  40. #include "hash.h"
  41. #include "generic.h"
  42. #include "dlgdef.h"
  43.  
  44. #define SetBlk(g, t) {                                               \
  45.             ((Junction *)g.left)->jtype = t;                    \
  46.             ((Junction *)g.left)->end = (Junction *) g.right;    \
  47.             ((Junction *)g.right)->jtype = EndBlk;}
  48.  
  49. /* Add the parameter string 'parm' to the parms field of a block-type junction
  50.  * g.left points to the sentinel node on a block.  i.e. g.left->p1 points to
  51.  * the actual junction with its jtype == some block-type.
  52.  */
  53. void
  54. #ifdef __STDC__
  55. addParm( Node *p, char *parm )
  56. #else
  57. addParm( p, parm )
  58. Node *p;
  59. char *parm;
  60. #endif
  61. {
  62.     char *q = (char *) malloc( strlen(parm) + 1 );
  63.     require(p!=NULL, "addParm: NULL object\n");
  64.     require(q!=NULL, "addParm: unable to alloc parameter\n");
  65.  
  66.     strcpy(q, parm);
  67.     if ( p->ntype == nRuleRef )
  68.     {
  69.         ((RuleRefNode *)p)->parms = q;
  70.     }
  71.     else if ( p->ntype == nJunction )
  72.     {
  73.         ((Junction *)p)->parm = q;    /* only one parameter allowed on subrules */
  74.     }
  75.     else fatal("addParm: invalid node for adding parm");
  76. }
  77.  
  78. /*
  79.  * Build an action node for the syntax diagram
  80.  *
  81.  * buildAction(ACTION) ::= --o-->ACTION-->o--
  82.  *
  83.  * Where o is a junction node.
  84.  */
  85. Graph
  86. #ifdef __STDC__
  87. buildAction( char *action, int file, int line, int is_predicate )
  88. #else
  89. buildAction( action, file, line, is_predicate )
  90. char *action;
  91. int file;
  92. int line;
  93. int is_predicate;
  94. #endif
  95. {
  96.     Junction *j1, *j2;
  97.     Graph g;
  98.     ActionNode *a;
  99.     require(action!=NULL, "buildAction: invalid action");
  100.     
  101.     j1 = newJunction();
  102.     j2 = newJunction();
  103.     a = newActionNode();
  104.     a->action = (char *) malloc( strlen(action)+1 );
  105.     require(a->action!=NULL, "buildAction: cannot alloc space for action\n");
  106.     strcpy(a->action, action);
  107.     j1->p1 = (Node *) a;
  108.     a->next = (Node *) j2;
  109.     a->is_predicate = is_predicate;
  110.     g.left = (Node *) j1; g.right = (Node *) j2;
  111.     a->file = file;
  112.     a->line = line;
  113.     return g;
  114. }
  115.  
  116. /*
  117.  * Build a token node for the syntax diagram
  118.  *
  119.  * buildToken(TOKEN) ::= --o-->TOKEN-->o--
  120.  *
  121.  * Where o is a junction node.
  122.  */
  123. Graph
  124. #ifdef __STDC__
  125. buildToken( char *text )
  126. #else
  127. buildToken( text )
  128. char *text;
  129. #endif
  130. {
  131.     Junction *j1, *j2;
  132.     Graph g;
  133.     TokNode *t;
  134.     require(text!=NULL, "buildToken: invalid token name");
  135.     
  136.     j1 = newJunction();
  137.     j2 = newJunction();
  138.     t = newTokNode();
  139.     if ( *text == '"' ) {t->label=FALSE; t->token = addTexpr( text );}
  140.     else {t->label=TRUE; t->token = addTname( text );}
  141.     j1->p1 = (Node *) t;
  142.     t->next = (Node *) j2;
  143.     g.left = (Node *) j1; g.right = (Node *) j2;
  144.     return g;
  145. }
  146.  
  147. /*
  148.  * Build a rule reference node of the syntax diagram
  149.  *
  150.  * buildRuleRef(RULE) ::= --o-->RULE-->o--
  151.  *
  152.  * Where o is a junction node.
  153.  *
  154.  * If rule 'text' has been defined already, don't alloc new space to store string.
  155.  * Set r->text to point to old copy in string table.
  156.  */
  157. Graph
  158. #ifdef __STDC__
  159. buildRuleRef( char *text )
  160. #else
  161. buildRuleRef( text )
  162. char *text;
  163. #endif
  164. {
  165.     Junction *j1, *j2;
  166.     Graph g;
  167.     RuleRefNode *r;
  168.     RuleEntry *p;
  169.     require(text!=NULL, "buildRuleRef: invalid rule name");
  170.     
  171.     j1 = newJunction();
  172.     j2 = newJunction();
  173.     r = newRNode();
  174.     r->assign = NULL;
  175.     if ( (p=(RuleEntry *)hash_get(Rname, text)) != NULL ) r->text = p->str;
  176.     else r->text = mystrdup( text );
  177.     j1->p1  = (Node *) r;
  178.     r->next = (Node *) j2;
  179.     g.left = (Node *) j1; g.right = (Node *) j2;
  180.     return g;
  181. }
  182.  
  183. /*
  184.  * Or two subgraphs into one graph via:
  185.  *
  186.  * Or(G1, G2) ::= --o-G1-o--
  187.  *                  |    ^
  188.  *                    v    |
  189.  *                  o-G2-o
  190.  *
  191.  * Set the altnum of junction starting G2 to 1 + altnum of junction starting G1.
  192.  * If, however, the G1 altnum is 0, make it 1 and then
  193.  * make G2 altnum = G1 altnum + 1.
  194.  */
  195. Graph
  196. #ifdef __STDC__
  197. Or( Graph g1, Graph g2 )
  198. #else
  199. Or( g1, g2 )
  200. Graph g1;
  201. Graph g2;
  202. #endif
  203. {
  204.     Graph g;
  205.     require(g1.left != NULL, "Or: invalid graph");
  206.     require(g2.left != NULL && g2.right != NULL, "Or: invalid graph");
  207.  
  208.     ((Junction *)g1.left)->p2 = g2.left;
  209.     ((Junction *)g2.right)->p1 = g1.right;
  210.     /* set altnums */
  211.     if ( ((Junction *)g1.left)->altnum == 0 ) ((Junction *)g1.left)->altnum = 1;
  212.     ((Junction *)g2.left)->altnum = ((Junction *)g1.left)->altnum + 1;
  213.     g.left = g2.left;
  214.     g.right = g1.right;
  215.     return g;
  216. }
  217.  
  218. /*
  219.  * Catenate two subgraphs
  220.  *
  221.  * Cat(G1, G2) ::= --o-G1-o-->o-G2-o--
  222.  * Cat(NULL,G2)::= --o-G2-o--
  223.  * Cat(G1,NULL)::= --o-G1-o--
  224.  */
  225. Graph
  226. #ifdef __STDC__
  227. Cat( Graph g1, Graph g2 )
  228. #else
  229. Cat( g1, g2 )
  230. Graph g1;
  231. Graph g2;
  232. #endif
  233. {
  234.     Graph g;
  235.     
  236.     if ( g1.left == NULL && g1.right == NULL ) return g2;
  237.     if ( g2.left == NULL && g2.right == NULL ) return g1;
  238.     ((Junction *)g1.right)->p1 = g2.left;
  239.     g.left = g1.left;
  240.     g.right = g2.right;
  241.     return g;
  242. }
  243.  
  244. /*
  245.  * Make a subgraph an optional block
  246.  *
  247.  * makeOpt(G) ::= --o-->o-G-o-->o--
  248.  *                      |         ^
  249.  *                        v          |
  250.  *                        o-------o
  251.  *
  252.  * Note that this constructs {A|B|...|Z} as if (A|B|...|Z|) was found.
  253.  *
  254.  * The node on the far right is added so that every block owns its own
  255.  * EndBlk node.
  256.  */
  257. Graph
  258. #ifdef __STDC__
  259. makeOpt( Graph g1 )
  260. #else
  261. makeOpt( g1 )
  262. Graph g1;
  263. #endif
  264. {
  265.     Junction *j1,*j2,*p;
  266.     Graph g;
  267.     require(g1.left != NULL && g1.right != NULL, "makeOpt: invalid graph");
  268.  
  269.     j1 = newJunction();
  270.     j2 = newJunction();
  271.     ((Junction *)g1.right)->p1 = (Node *) j2;    /* add node to G at end */
  272.     g = emptyAlt();
  273.     if ( ((Junction *)g1.left)->altnum == 0 ) ((Junction *)g1.left)->altnum = 1;
  274.     ((Junction *)g.left)->altnum = ((Junction *)g1.left)->altnum + 1;
  275.     for(p=(Junction *)g1.left; p->p2!=NULL; p=(Junction *)p->p2)
  276.         {;}                                        /* find last alt */
  277.     p->p2 = g.left;                                /* add optional alternative */
  278.     ((Junction *)g.right)->p1 = (Node *)j2;        /* opt alt points to EndBlk */
  279.     g1.right = (Node *)j2;
  280.     SetBlk(g1, aOptBlk);
  281.     j1->p1 = g1.left;                            /* add generic node in front */
  282.     g.left = (Node *) j1;
  283.     g.right = g1.right;
  284.  
  285.     return g;
  286. }
  287.  
  288. /*
  289.  * Make a graph into subblock
  290.  *
  291.  * makeBlk(G) ::= --o-->o-G-o-->o--
  292.  *
  293.  * The node on the far right is added so that every block owns its own
  294.  * EndBlk node.
  295.  */
  296. Graph
  297. #ifdef __STDC__
  298. makeBlk( Graph g1 )
  299. #else
  300. makeBlk( g1 )
  301. Graph g1;
  302. #endif
  303. {
  304.     Junction *j,*j2;
  305.     Graph g;
  306.     require(g1.left != NULL && g1.right != NULL, "makeBlk: invalid graph");
  307.  
  308.     j = newJunction();
  309.     j2 = newJunction();
  310.     ((Junction *)g1.right)->p1 = (Node *) j2;    /* add node to G at end */
  311.     g1.right = (Node *)j2;
  312.     SetBlk(g1, aSubBlk);
  313.     j->p1 = g1.left;                            /* add node in front */
  314.     g.left = (Node *) j;
  315.     g.right = g1.right;
  316.  
  317.     return g;
  318. }
  319.  
  320. /*
  321.  * Make a subgraph into a loop (closure) block -- (...)*
  322.  *
  323.  * makeLoop(G) ::=       |---|
  324.  *                         v   |
  325.  *               --o-->o-->o-G-o-->o--
  326.  *                   |           ^
  327.  *                   v           |
  328.  *                     o-----------o
  329.  *
  330.  * After making loop, always place generic node out front.  It becomes
  331.  * the start of enclosing block.  The aLoopBlk is the target of the loop.
  332.  *
  333.  * Loop blks have TWO EndBlk nodes--the far right and the node that loops back
  334.  * to the aLoopBlk node.  Node with which we can branch past loop == aLoopBegin and
  335.  * one which is loop target == aLoopBlk.
  336.  * The branch-past (initial) aLoopBegin node has end
  337.  * pointing to the last EndBlk node.  The loop-target node has end==NULL.
  338.  *
  339.  * Loop blocks have a set of locks (from 1..CLL_k) on the aLoopBlk node.
  340.  */
  341. Graph
  342. #ifdef __STDC__
  343. makeLoop( Graph g1 )
  344. #else
  345. makeLoop( g1 )
  346. Graph g1;
  347. #endif
  348. {
  349.     Junction *back, *front, *begin;
  350.     Graph g;
  351.     require(g1.left != NULL && g1.right != NULL, "makeLoop: invalid graph");
  352.  
  353.     back = newJunction();
  354.     front = newJunction();
  355.     begin = newJunction();
  356.     g = emptyAlt();
  357.     ((Junction *)g1.right)->p2 = g1.left;        /* add loop branch to G */
  358.     ((Junction *)g1.right)->p1 = (Node *) back;    /* add node to G at end */
  359.     ((Junction *)g1.right)->jtype = EndBlk;        /* mark 1st EndBlk node */
  360.     ((Junction *)g1.left)->jtype = aLoopBlk;    /* mark 2nd aLoopBlk node */
  361.     ((Junction *)g1.left)->end = (Junction *) g1.right;
  362.     ((Junction *)g1.left)->lock = makelocks();
  363.     ((Junction *)g1.left)->pred_lock = makelocks();
  364.     g1.right = (Node *) back;
  365.     begin->p1 = (Node *) g1.left;
  366.     g1.left = (Node *) begin;
  367.     begin->p2 = (Node *) g.left;                /* make bypass arc */
  368.     ((Junction *)g.right)->p1 = (Node *) back;
  369.     SetBlk(g1, aLoopBegin);
  370.     front->p1 = g1.left;                        /* add node to front */
  371.     g1.left = (Node *) front;
  372.  
  373.     return g1;
  374. }
  375.  
  376. /*
  377.  * Make a subgraph into a plus block -- (...)+ -- 1 or more times
  378.  *
  379.  * makeLoop(G) ::=     |---|
  380.  *                     v   |
  381.  *               --o-->o-G-o-->o--
  382.  *
  383.  * After making loop, always place generic node out front.  It becomes
  384.  * the start of enclosing block.  The aPlusBlk is the target of the loop.
  385.  *
  386.  * Plus blks have TWO EndBlk nodes--the far right and the node that loops back
  387.  * to the aPlusBlk node.
  388.  *
  389.  * Plus blocks have a set of locks (from 1..CLL_k) on the aPlusBlk node.
  390.  */
  391. Graph
  392. #ifdef __STDC__
  393. makePlus( Graph g1 )
  394. #else
  395. makePlus( g1 )
  396. Graph g1;
  397. #endif
  398. {
  399.     Junction *j2, *j3;
  400.     require(g1.left != NULL && g1.right != NULL, "makePlus: invalid graph");
  401.  
  402.     j2 = newJunction();
  403.     j3 = newJunction();
  404.     if ( ((Junction *)g1.left)->altnum == 0 ) ((Junction *)g1.left)->altnum = 1;
  405.     ((Junction *)g1.right)->p2 = g1.left;        /* add loop branch to G */
  406.     ((Junction *)g1.right)->p1 = (Node *) j2;    /* add node to G at end */
  407.     ((Junction *)g1.right)->jtype = EndBlk;        /* mark 1st EndBlk node */
  408.     g1.right = (Node *) j2;
  409.     SetBlk(g1, aPlusBlk);
  410.     ((Junction *)g1.left)->lock = makelocks();
  411.     ((Junction *)g1.left)->pred_lock = makelocks();
  412.     j3->p1 = g1.left;                            /* add node to front */
  413.     g1.left = (Node *) j3;
  414.     
  415.     return g1;
  416. }
  417.  
  418. /*
  419.  * Return an optional path:  --o-->o--
  420.  */
  421. Graph
  422. #ifdef __STDC__
  423. emptyAlt( void )
  424. #else
  425. emptyAlt( )
  426. #endif
  427. {
  428.     Junction *j1, *j2;
  429.     Graph g;
  430.  
  431.     j1 = newJunction();
  432.     j2 = newJunction();
  433.     j1->p1 = (Node *) j2;
  434.     g.left = (Node *) j1;
  435.     g.right = (Node *) j2;
  436.     
  437.     return g;
  438. }
  439.  
  440. /* N o d e  A l l o c a t i o n */
  441.  
  442. TokNode *
  443. #ifdef __STDC__
  444. newTokNode( void )
  445. #else
  446. newTokNode( )
  447. #endif
  448. {
  449.     static TokNode *FreeList = NULL;
  450.     TokNode *p, *newblk;
  451.  
  452.     if ( FreeList == NULL )
  453.     {
  454.         newblk = (TokNode *)calloc(TokenBlockAllocSize, sizeof(TokNode));
  455.         if ( newblk == NULL )
  456.             fatal(eMsg1("out of memory while building rule '%s'",CurRule));
  457.         for (p=newblk; p<&(newblk[TokenBlockAllocSize]); p++)
  458.         {
  459.             p->next = (Node *)FreeList;    /* add all new token nodes to FreeList */
  460.             FreeList = p;
  461.         }
  462.     }
  463.     p = FreeList;
  464.     FreeList = (TokNode *)FreeList->next;/* remove a Junction node */
  465.     p->next = NULL;                        /* NULL the ptr we used */
  466.  
  467.     p->ntype = nToken;
  468.     p->rname = CurRule;
  469.     p->file = CurFile;
  470.     p->line = zzline;
  471.     
  472.     return p;
  473. }
  474.  
  475. RuleRefNode *
  476. #ifdef __STDC__
  477. newRNode( void )
  478. #else
  479. newRNode( )
  480. #endif
  481. {
  482.     static RuleRefNode *FreeList = NULL;
  483.     RuleRefNode *p, *newblk;
  484.  
  485.     if ( FreeList == NULL )
  486.     {
  487.         newblk = (RuleRefNode *)calloc(RRefBlockAllocSize, sizeof(RuleRefNode));
  488.         if ( newblk == NULL )
  489.             fatal(eMsg1("out of memory while building rule '%s'",CurRule));
  490.         for (p=newblk; p<&(newblk[RRefBlockAllocSize]); p++)
  491.         {
  492.             p->next = (Node *)FreeList;    /* add all new rref nodes to FreeList */
  493.             FreeList = p;
  494.         }
  495.     }
  496.     p = FreeList;
  497.     FreeList = (RuleRefNode *)FreeList->next;/* remove a Junction node */
  498.     p->next = NULL;                        /* NULL the ptr we used */
  499.  
  500.     p->ntype = nRuleRef;
  501.     p->rname = CurRule;
  502.     p->file = CurFile;
  503.     p->line = zzline;
  504.     p->astnode = ASTinclude;
  505.     
  506.     return p;
  507. }
  508.  
  509. Junction *
  510. #ifdef __STDC__
  511. newJunction( void )
  512. #else
  513. newJunction( )
  514. #endif
  515. {
  516.     static Junction *FreeList = NULL;
  517.     Junction *p, *newblk;
  518.  
  519.     if ( FreeList == NULL )
  520.     {
  521.         newblk = (Junction *)calloc(JunctionBlockAllocSize, sizeof(Junction));
  522.         if ( newblk == NULL )
  523.             fatal(eMsg1("out of memory while building rule '%s'",CurRule));
  524.         for (p=newblk; p<&(newblk[JunctionBlockAllocSize]); p++)
  525.         {
  526.             p->p1 = (Node *)FreeList;    /* add all new Junction nodes to FreeList */
  527.             FreeList = p;
  528.         }
  529.     }
  530.     p = FreeList;
  531.     FreeList = (Junction *)FreeList->p1;/* remove a Junction node */
  532.     p->p1 = NULL;                        /* NULL the ptr we used */
  533.  
  534.     p->ntype = nJunction;    p->visited = 0;
  535.     p->jtype = Generic;
  536.     p->rname = CurRule;
  537.     p->file = CurFile;
  538.     p->line = zzline;
  539.     p->fset = (set *) calloc(CLL_k+1, sizeof(set));
  540.     require(p->fset!=NULL, "cannot allocate fset in newJunction");
  541.  
  542.     return p;
  543. }
  544.  
  545. ActionNode *
  546. #ifdef __STDC__
  547. newActionNode( void )
  548. #else
  549. newActionNode( )
  550. #endif
  551. {
  552.     static ActionNode *FreeList = NULL;
  553.     ActionNode *p, *newblk;
  554.  
  555.     if ( FreeList == NULL )
  556.     {
  557.         newblk = (ActionNode *)calloc(ActionBlockAllocSize, sizeof(ActionNode));
  558.         if ( newblk == NULL )
  559.             fatal(eMsg1("out of memory while building rule '%s'",CurRule));
  560.         for (p=newblk; p<&(newblk[ActionBlockAllocSize]); p++)
  561.         {
  562.             p->next = (Node *)FreeList;    /* add all new Action nodes to FreeList */
  563.             FreeList = p;
  564.         }
  565.     }
  566.     p = FreeList;
  567.     FreeList = (ActionNode *)FreeList->next;/* remove a Junction node */
  568.     p->next = NULL;                        /* NULL the ptr we used */
  569.     
  570.     p->ntype = nAction;
  571.     return p;
  572. }
  573.  
  574. /*
  575.  * allocate the array of locks (1..CLL_k) used to inhibit infinite recursion.
  576.  * Infinite recursion can occur in (..)* blocks, FIRST calcs and FOLLOW calcs.
  577.  * Therefore, we need locks on aLoopBlk, RuleBlk, EndRule nodes.
  578.  *
  579.  * if ( lock[k]==TRUE ) then we have been here before looking for k tokens
  580.  * of lookahead.
  581.  */
  582. char *
  583. #ifdef __STDC__
  584. makelocks( void )
  585. #else
  586. makelocks( )
  587. #endif
  588. {
  589.     char *p = (char *) calloc(CLL_k+1, sizeof(char));
  590.     require(p!=NULL, "cannot allocate lock array");
  591.     
  592.     return p;
  593. }
  594.