home *** CD-ROM | disk | FTP | other *** search
/ The World of Computer Software / World_Of_Computer_Software-02-385-Vol-1of3.iso / p / pccts.zip / antlr / gen.c < prev    next >
C/C++ Source or Header  |  1992-12-08  |  30KB  |  1,202 lines
  1. /*
  2.  * gen.c
  3.  *
  4.  * Generate C code (ANSI or K&R)
  5.  *
  6.  * SOFTWARE RIGHTS
  7.  *
  8.  * We reserve no LEGAL rights to the Purdue Compiler Construction Tool
  9.  * Set (PCCTS) -- PCCTS is in the public domain.  An individual or
  10.  * company may do whatever they wish with source code distributed with
  11.  * PCCTS or the code generated by PCCTS, including the incorporation of
  12.  * PCCTS, or its output, into commerical software.
  13.  * 
  14.  * We encourage users to develop software with PCCTS.  However, we do ask
  15.  * that credit is given to us for developing PCCTS.  By "credit",
  16.  * we mean that if you incorporate our source code into one of your
  17.  * programs (commercial product, research project, or otherwise) that you
  18.  * acknowledge this fact somewhere in the documentation, research report,
  19.  * etc...  If you like PCCTS and have developed a nice tool with the
  20.  * output, please mention that you developed it using PCCTS.  In
  21.  * addition, we ask that this header remain intact in our source code.
  22.  * As long as these guidelines are kept, we expect to continue enhancing
  23.  * this system and expect to make other tools available as they are
  24.  * completed.
  25.  *
  26.  * ANTLR 1.06
  27.  * Terence Parr
  28.  * Purdue University
  29.  * 1989-1992
  30.  */
  31. #include <stdio.h>
  32. #include <ctype.h>
  33. #include "set.h"
  34. #include "syn.h"
  35. #include "hash.h"
  36. #include "generic.h"
  37. #include "dlgdef.h"
  38.  
  39.                     /* T r a n s l a t i o n  T a b l e s */
  40.  
  41. /* C_Trans[node type] == pointer to function that knows how to translate that node. */
  42. void (*C_Trans[NumNodeTypes+1])() = {
  43.     NULL,
  44.     NULL,                    /* See next table.  Junctions have many types */
  45.     genRuleRef,
  46.     genToken,
  47.     genAction
  48. };
  49.  
  50. /* C_JTrans[Junction type] == pointer to function that knows how to translate that
  51.  * kind of junction node.
  52.  */
  53. void (*C_JTrans[NumJuncTypes+1])() = {
  54.     NULL,
  55.     genSubBlk,
  56.     genOptBlk,
  57.     genLoopBlk,
  58.     genEndBlk,
  59.     genRule,
  60.     genJunction,
  61.     genEndRule,
  62.     genPlusBlk,
  63.     genLoopBegin
  64. };
  65.  
  66. #define PastWhiteSpace(s)    while (*(s) == ' ' || *(s) == '\t' || *(s) == '\n') {s++;}
  67.  
  68. static int tabs = 0;
  69. #define TAB { int i; for (i=0; i<tabs; i++) putc('\t', output); }
  70. static void tab() TAB
  71.  
  72. #ifdef __STDC__
  73. static ActionNode *findImmedAction( Node * );
  74. static void dumpRetValAssign(char *, char *);
  75. static dumpAfterActions(FILE *output);
  76. static set ComputeErrorSet(Junction *, int);
  77. static void makeErrorClause(Junction *, set, int);
  78. static void DumpFuncHeader( Junction *, RuleEntry * );
  79. #else
  80. static ActionNode *findImmedAction();
  81. static void dumpRetValAssign();
  82. static dumpAfterActions();
  83. static set ComputeErrorSet();
  84. static void makeErrorClause();
  85. static void DumpFuncHeader();
  86. #endif
  87.  
  88. #define gen(s)            {tab(); fprintf(output, s);}
  89. #define gen1(s,a)        {tab(); fprintf(output, s,a);}
  90. #define gen2(s,a,b)        {tab(); fprintf(output, s,a,b);}
  91. #define gen3(s,a,b,c)    {tab(); fprintf(output, s,a,b,c);}
  92. #define gen4(s,a,b,c,d)    {tab(); fprintf(output, s,a,b,c,d);}
  93. #define gen5(s,a,b,c,d,e)    {tab(); fprintf(output, s,a,b,c,d,e);}
  94. #define gen6(s,a,b,c,d,e,f)    {tab(); fprintf(output, s,a,b,c,d,e,f);}
  95.  
  96. #define _gen(s)            {fprintf(output, s);}
  97. #define _gen1(s,a)        {fprintf(output, s,a);}
  98. #define _gen2(s,a,b)    {fprintf(output, s,a,b);}
  99. #define _gen3(s,a,b,c)    {fprintf(output, s,a,b,c);}
  100. #define _gen4(s,a,b,c,d){fprintf(output, s,a,b,c,d);}
  101. #define _gen5(s,a,b,c,d,e){fprintf(output, s,a,b,c,d,e);}
  102.  
  103. void
  104. freeBlkFsets(q)
  105. Junction *q;
  106. {
  107.     int i;
  108.     Junction *alt;
  109.     require(q!=NULL, "freeBlkFsets: invalid node");
  110.  
  111.     for (alt=q; alt != NULL; alt= (Junction *) alt->p2 )
  112.     {
  113.         for (i=1; i<=LL_k; i++) set_free(alt->fset[i]);
  114.     }
  115. }
  116.  
  117. static void
  118. BLOCK_Head()
  119. {
  120.     gen("{\n");
  121.     tabs++;
  122.     gen1("zzBLOCK(zztasp%d);\n", BlkLevel);
  123. }
  124.  
  125. static void
  126. BLOCK_Tail()
  127. {
  128.     gen1("zzEXIT(zztasp%d);\n", BlkLevel);
  129.     gen("}\n");
  130.     tabs--;
  131.     gen("}\n");
  132. }
  133.  
  134. static void
  135. BLOCK_Preamble(q)
  136. Junction *q;
  137. {
  138.     ActionNode *a;
  139.  
  140.     BLOCK_Head();
  141.     if ( q->jtype == aPlusBlk ) gen("int zzcnt=1;\n");
  142.     if ( q->parm != NULL ) gen1("zzaPush(%s);\n", q->parm)
  143.     else gen("zzMake0;\n");
  144.     gen("{\n");
  145.     if ( q->jtype == aLoopBegin )
  146.         a = findImmedAction( ((Junction *)q->p1)->p1 );    /* look at aLoopBlk */
  147.     else
  148.         a = findImmedAction( q->p1 );
  149.     if ( a!=NULL && !a->is_predicate ) {
  150.         dumpAction(a->action, output, tabs, a->file, a->line, 1);
  151.         a->done = 1;    /* remove action. We have already handled it */
  152.     }
  153. }
  154.  
  155. static void
  156. genExprTree(t,k)
  157. Tree *t;
  158. int k;
  159. {
  160.     require(t!=NULL, "genExprTree: NULL tree");
  161.     
  162.     if ( t->token == ALT )
  163.     {
  164.         _gen("("); genExprTree(t->down, k); _gen(")");
  165.         if ( t->right!=NULL )
  166.         {
  167.             _gen("||");
  168.             _gen("("); genExprTree(t->right, k); _gen(")");
  169.         }
  170.         return;
  171.     }
  172.     if ( t->down!=NULL ) _gen("(");
  173.     _gen1("LA(%d)==",k);
  174.     if ( TokenStr[t->token] == NULL ) _gen1("%d", t->token)
  175.     else _gen1("%s", TokenStr[t->token]);
  176.     if ( t->down!=NULL )
  177.     {
  178.         _gen("&&");
  179.         _gen("("); genExprTree(t->down, k+1); _gen(")");
  180.     }
  181.     if ( t->down!=NULL ) _gen(")");
  182.     if ( t->right!=NULL )
  183.     {
  184.         _gen("||");
  185.         _gen("("); genExprTree(t->right, k); _gen(")");
  186.     }
  187. }
  188.  
  189. /*
  190.  * Generate LL(k) type expressions of the form:
  191.  *
  192.  *         (LA(1) == T1 || LA(1) == T2 || ... || LA(1) == Tn) &&
  193.  *         (LA(2) == T1 || LA(2) == T2 || ... || LA(2) == Tn) &&
  194.  *            .....
  195.  *         (LA(k) == T1 || LA(k) == T2 || ... || LA(k) == Tn)
  196.  *
  197.  * If GenExprSets generate:
  198.  *
  199.  *        (setwdi[LA(1)]&(1<<j)) && (setwdi[LA(2)]&(1<<j)) ...
  200.  *
  201.  * where n is set_deg(expr) and Ti is some random token and k is the last nonempty
  202.  * set in fset.
  203.  * k=1..LL_k where LL_k >= 1.
  204.  * This routine is visible only to this file and cannot answer a TRANS message.
  205.  *
  206.  * TJP Oct '92: If predicates are allowed in parsing expressions:
  207.  *
  208.  * (    <<pred>>? production 1
  209.  * |    production 2
  210.  * ...
  211.  * |    production n
  212.  * )
  213.  *
  214.  * Generates:
  215.  *
  216.  * if ( pred && (production 1 prediction) ) {
  217.  *         ...
  218.  * }
  219.  * else if ( production 2 prediction ) {
  220.  *         ...
  221.  * }
  222.  * ...
  223.  */
  224. static int
  225. genExpr(j)
  226. Junction *j;
  227. {
  228.     int k = 1;
  229.     int max_k = 0;
  230.     unsigned *e, *g, firstTime=1;
  231.     set *fset = j->fset;
  232.  
  233.     if ( ParseWithPredicates && j->predicate.expr!=NULL )
  234.     {
  235.         _gen("((");
  236.         dumpAction(j->predicate.expr, output, 0, j->file, j->line, 0);
  237.         _gen(") && (");
  238. #ifdef COMPUTE_CONTEXT
  239.         require(j->predicate.context!=NULL, "no context for predicate");
  240.         genExprTree(j->predicate.context, 1);
  241. #else
  242.         _gen("1");
  243. #endif
  244.         _gen(")) && (");
  245.     }
  246.     if ( GenExprSets )
  247.     {
  248.         while ( !set_nil(fset[k]) )
  249.         {
  250.             if ( set_deg(fset[k])==1 )    /* too simple for a set? */
  251.             {
  252.                 int e;
  253.                 _gen1("(LA(%d)==",k);
  254.                 e = set_int(fset[k]);
  255.                 if ( TokenStr[e] == NULL ) _gen1("%d)", e)
  256.                 else _gen1("%s)", TokenStr[e]);
  257.             }
  258.             else
  259.             {
  260.                 NewSet();
  261.                 FillSet( fset[k] );
  262.                 _gen3("(setwd%d[LA(%d)]&0x%x)", wordnum, k, 1<<setnum);
  263.             }
  264.             if ( k>max_k ) max_k = k;
  265.             if ( k == LL_k ) break;
  266.             k++;
  267.             if ( !set_nil(fset[k]) ) _gen(" && ");
  268.         }
  269.         if ( j->ftree != NULL )
  270.         {
  271.             /*fprintf(stderr, "genExpr ftree:"); preorder(j->ftree); fprintf(stderr, "\n");
  272.             */
  273.             _gen(" && !("); genExprTree(j->ftree, 1); _gen(")");
  274.         }
  275.         if ( ParseWithPredicates && j->predicate.expr!=NULL ) _gen(")");
  276.         return max_k;
  277.     }
  278.  
  279.     while ( !set_nil(fset[k]) )
  280.     {
  281.         if ( (e=g=set_pdq(fset[k])) == NULL ) fatal("genExpr: cannot allocate IF expr pdq set");
  282.         for (; *e!=nil; e++)
  283.         {
  284.             if ( !firstTime ) _gen(" || ") else { _gen("("); firstTime = 0; }
  285.             _gen1("LA(%d)==",k);
  286.             if ( TokenStr[*e] == NULL ) _gen1("%d", *e)
  287.             else _gen1("%s", TokenStr[*e]);
  288.         }
  289.         free( g );
  290.         _gen(")");
  291.         if ( k>max_k ) max_k = k;
  292.         if ( k == LL_k ) break;
  293.         k++;
  294.         if ( !set_nil(fset[k]) ) { firstTime=1; _gen(" && "); }
  295.     }
  296.     if ( j->ftree != NULL )
  297.     {
  298. /*        fprintf(stderr, "genExpr ftree:"); preorder(j->ftree); fprintf(stderr, "\n");
  299.  */
  300.         _gen(" && !("); genExprTree(j->ftree, 1); _gen(")");
  301.     }
  302.     if ( ParseWithPredicates && j->predicate.expr!=NULL ) _gen(")");
  303.     return max_k;
  304. }
  305.  
  306. /*
  307.  * Generate code for any type of block.  If the last alternative in the block is
  308.  * empty (not even an action) don't bother doing it.  This permits us to handle
  309.  * optional and loop blocks as well.
  310.  *
  311.  * Only do this block, return after completing the block.
  312.  * This routine is visible only to this file and cannot answer a TRANS message.
  313.  */
  314. static set
  315. genBlk(q,jtype,max_k)
  316. Junction *q;
  317. int jtype, *max_k;
  318. {
  319.     set f;
  320.     Junction *alt;
  321.     require(q!=NULL,                "genBlk: invalid node");
  322.     require(q->ntype == nJunction,    "genBlk: not junction");
  323.  
  324.     if ( q->p2 == NULL )    /* only one alternative?  Then don't need if */
  325.     {    
  326.         TRANS(q->p1);
  327.         return empty;        /* no decision to be made-->no error set */
  328.     }
  329.     f = First(q, 1, jtype, max_k);
  330.     for (alt=q; alt != NULL; alt= (Junction *) alt->p2 )
  331.     {
  332.         if ( alt->p2 == NULL )                    /* chk for empty alt */
  333.         {    
  334.             Node *p = alt->p1;
  335.             if ( p->ntype == nJunction )
  336.             {
  337.                 /* we have empty alt */
  338.                 if ( ((Junction *)p)->p1 == (Node *)q->end )
  339.                 {
  340.                     break;                        /* don't do this one, quit */
  341.                 }
  342.             }
  343.         }
  344.         if ( alt != q ) gen("else ")
  345.         else
  346.         {
  347.             if ( DemandLookahead ) gen1("LOOK(%d);\n", *max_k);
  348.             tab();
  349.         }
  350.         _gen("if ( ");
  351.         genExpr(alt);
  352.         _gen(" ) ");
  353.         _gen("{\n");
  354.         tabs++;
  355.         TRANS(alt->p1);
  356.         --tabs;
  357.         gen("}\n");
  358.     }
  359.     return f;
  360. }
  361.  
  362. /* Generate an action.  Don't if action is NULL which means that it was already
  363.  * handled as an init action.
  364.  */
  365. void
  366. genAction(p)
  367. ActionNode *p;
  368. {
  369.     require(p!=NULL,            "genAction: invalid node and/or rule");
  370.     require(p->ntype==nAction,    "genAction: not action");
  371.     
  372.     if ( !p->done )
  373.     {
  374.         if ( p->is_predicate )
  375.         {
  376.             gen("if (!(");
  377.             dumpAction(p->action, output, 0, p->file, p->line, 0);
  378.             if ( p->pred_fail != NULL ) {_gen1(")) {{%s}; exit(-1);}\n", p->pred_fail);}
  379.             else _gen1(")) {fprintf(stderr, \"semantic error; failed predicate: '%s'\\n\"); exit(-1);}\n",p->action);
  380.         }
  381.         else
  382.         {
  383.             dumpAction(p->action, output, tabs, p->file, p->line, 1);
  384.         }
  385.         p->done = 1;
  386.     }
  387.     TRANS(p->next)
  388. }
  389.  
  390. /*
  391.  *        if invoking rule has !noAST pass zzSTR to rule ref and zzlink it in
  392.  *        else pass addr of temp root ptr (&_ast) (don't zzlink it in).
  393.  *
  394.  *        if ! modifies rule-ref, then never link it in and never pass zzSTR.
  395.  *        Always pass address of temp root ptr.
  396.  */
  397. void
  398. genRuleRef(p)
  399. RuleRefNode *p;
  400. {
  401.     Junction *q;
  402.     RuleEntry *r, *r2;
  403.     char *parm = "";
  404.     require(p!=NULL,            "genRuleRef: invalid node and/or rule");
  405.     require(p->ntype==nRuleRef, "genRuleRef: not rule reference");
  406.     
  407.     r = (RuleEntry *) hash_get(Rname, p->text);
  408.     if ( r == NULL ) {warnNoFL( eMsg1("rule %s not defined", p->text) ); return;}
  409.     r2 = (RuleEntry *) hash_get(Rname, p->rname);
  410.     if ( r2 == NULL ) {warnNoFL("Rule hash table is screwed up beyond belief"); return;}
  411.  
  412.     tab();
  413.     if ( GenAST )
  414.     {
  415.         if ( r2->noAST || p->astnode==ASTexclude )
  416.         {
  417.             _gen("_ast = NULL; ");
  418.             parm = "&_ast";
  419.         }
  420.         else parm = "zzSTR";
  421.         if ( p->assign!=NULL )
  422.         {
  423.             if ( !HasComma(p->assign) ) {_gen1("%s = ",p->assign);}
  424.             else _gen1("{ struct _rv%d _trv; _trv = ", r->rulenum);
  425.         }
  426.         _gen5("%s%s(%s%s%s);", RulePrefix,
  427.                                p->text,
  428.                                parm,
  429.                                (p->parms!=NULL)?",":"",
  430.                                (p->parms!=NULL)?p->parms:"");
  431.         if ( !r2->noAST && p->astnode == ASTinclude )
  432.         {
  433.             _gen(" zzlink(_root, &_sibling, &_tail);");
  434.         }
  435.     }
  436.     else
  437.     {
  438.         if ( p->assign!=NULL )
  439.         {
  440.             if ( !HasComma(p->assign) ) {_gen1("%s = ",p->assign);}
  441.             else _gen1("{ struct _rv%d _trv; _trv = ", r->rulenum);
  442.         }
  443.         _gen2("%s(%s);", p->text, (p->parms!=NULL)?p->parms:"");
  444.     }
  445.     q = RulePtr[r->rulenum];    /* find definition of ref'd rule */
  446.     if ( p->assign!=NULL )
  447.         if ( HasComma(p->assign) )
  448.         {
  449.             dumpRetValAssign(p->assign, q->ret);
  450.             _gen("}");
  451.         }
  452.     _gen("\n");
  453.     TRANS(p->next)
  454. }
  455.  
  456. /*
  457.  * Generate code to match a token.
  458.  *
  459.  * Getting the next token is tricky.  We want to ensure that any action
  460.  * following a token is executed before the next GetToken();
  461.  */ 
  462. void
  463. genToken(p)
  464. TokNode *p;
  465. {
  466.     RuleEntry *r;
  467.     ActionNode *a;
  468.     require(p!=NULL,            "genToken: invalid node and/or rule");
  469.     require(p->ntype==nToken,    "genToken: not token");
  470.     
  471.     r = (RuleEntry *) hash_get(Rname, p->rname);
  472.     if ( r == NULL ) {warnNoFL("Rule hash table is screwed up beyond belief"); return;}
  473.     if ( TokenStr[p->token]!=NULL ) gen1("zzmatch(%s);", TokenStr[p->token])
  474.     else gen1("zzmatch(%d);", p->token);
  475.     a = findImmedAction( p->next );
  476.     if ( GenAST )
  477.     {
  478.         if ( !r->noAST )
  479.         {
  480.             if ( p->astnode==ASTchild )
  481.                 {_gen(" zzsubchild(_root, &_sibling, &_tail);");}
  482.             else if ( p->astnode==ASTroot )
  483.                 {_gen(" zzsubroot(_root, &_sibling, &_tail);");}
  484.             else
  485.                 {_gen(" zzastDPush;");}
  486.         }
  487.         else _gen(" zzastDPush;");
  488.     }
  489.     if ( a != NULL )
  490.     {
  491.         /* delay next token fetch until after action */
  492.         _gen("\n");
  493.         if ( a->is_predicate )
  494.         {
  495.             gen("if (!(");
  496.             dumpAction(a->action, output, 0, a->file, a->line, 0);
  497.             _gen1(")) {fprintf(stderr, \"failed predicate: '%s'\n\"); exit(-1);}\n",a->action);
  498.         }
  499.         else
  500.         {
  501.             dumpAction(a->action, output, tabs, a->file, a->line, 1);
  502.         }
  503.         a->done = 1;
  504.         if ( !DemandLookahead ) {gen(" zzCONSUME;\n");}
  505.         else gen("\n");
  506.         TRANS( a->next );
  507.     }
  508.     else
  509.     {
  510.         if ( !DemandLookahead ) {_gen(" zzCONSUME;\n");}
  511.         else gen("\n");
  512.         TRANS(p->next);
  513.     }
  514. }
  515.  
  516. void
  517. genOptBlk(q)
  518. Junction *q;
  519. {
  520.     int max_k;
  521.     set f;
  522.     require(q!=NULL,                "genOptBlk: invalid node and/or rule");
  523.     require(q->ntype == nJunction,    "genOptBlk: not junction");
  524.     require(q->jtype == aOptBlk,    "genOptBlk: not optional block");
  525.  
  526.     BLOCK_Preamble(q);
  527.     BlkLevel++;
  528.     f = genBlk(q, aOptBlk, &max_k);
  529.     set_free(f);
  530.     freeBlkFsets(q);
  531.     BlkLevel--;
  532.     BLOCK_Tail();
  533.     if (q->end->p1 != NULL) TRANS(q->end->p1);
  534. }
  535.  
  536. /*
  537.  * Generate code for a loop blk of form:
  538.  *
  539.  *                 |---|
  540.  *                 v   |
  541.  *               --o-G-o-->o--
  542.  */
  543. void
  544. genLoopBlk(q,begin,max_k)
  545. Junction *q, *begin;
  546. int max_k;
  547. {
  548.     int dum_k;
  549.     set f;
  550.     require(q->ntype == nJunction,    "genLoopBlk: not junction");
  551.     require(q->jtype == aLoopBlk,    "genLoopBlk: not loop block");
  552.  
  553.     if ( q->visited ) return;
  554.     q->visited = TRUE;
  555.     if ( q->p2 == NULL )    /* only one alternative? */
  556.     {
  557.         f = First(q, 1, aLoopBlk, &dum_k);
  558.         if ( DemandLookahead ) gen1("LOOK(%d);\n", max_k);
  559.         gen("while ( ");
  560.         if ( begin!=NULL )
  561.         {
  562.             genExpr(begin);
  563.         }
  564.         else genExpr(q);
  565.         _gen(" ) {\n");
  566.         tabs++;
  567.         TRANS(q->p1);
  568.         gen1("zzLOOP(zztasp%d);\n", BlkLevel-1);
  569.         if ( DemandLookahead ) gen1("LOOK(%d);\n", max_k);
  570.         --tabs;
  571.         gen("}\n");
  572.         freeBlkFsets(q);
  573.         set_free(f);
  574.         q->visited = FALSE;
  575.         return;
  576.     }
  577.     gen("while ( 1 ) {\n");
  578.     tabs++;
  579.     if ( begin!=NULL )
  580.     {
  581.         if ( DemandLookahead ) gen1("LOOK(%d);\n",max_k);
  582.         gen("if ( ");
  583.         genExpr((Junction *)begin->p2);
  584.         _gen(" ) break;\n");
  585.     }
  586.     f = genBlk(q, aLoopBlk, &max_k);
  587.     set_free(f);
  588.     freeBlkFsets(q);
  589.     if ( begin==NULL ) gen("else break;\n");        /* code for exiting loop */
  590.     gen1("zzLOOP(zztasp%d);\n", BlkLevel-1);
  591.     --tabs;
  592.     gen("}\n");
  593.     q->visited = FALSE;
  594. }
  595.  
  596. /*
  597.  * Generate code for a loop blk of form:
  598.  *
  599.  *                          |---|
  600.  *                         v   |
  601.  *               --o-->o-->o-G-o-->o--
  602.  *                   |           ^
  603.  *                   v           |
  604.  *                     o-----------o
  605.  *
  606.  * q->end points to the last node (far right) in the blk.  Note that q->end->jtype
  607.  * must be 'EndBlk'.
  608.  *
  609.  * Generate code roughly of the following form:
  610.  *
  611.  *    do {
  612.  *        ... code for alternatives ...
  613.  *  } while ( First Set of aLoopBlk );
  614.  *
  615.  *    OR if > 1 alternative
  616.  *
  617.  *    do {
  618.  *        ... code for alternatives ...
  619.  *        else break;
  620.  *  } while ( 1 );
  621.  */
  622. void
  623. genLoopBegin(q)
  624. Junction *q;
  625. {
  626.     set f;
  627.     int i;
  628.     int max_k;
  629.     require(q!=NULL,                "genLoopBegin: invalid node and/or rule");
  630.     require(q->ntype == nJunction,    "genLoopBegin: not junction");
  631.     require(q->jtype == aLoopBegin,    "genLoopBegin: not loop block");
  632.     require(q->p2!=NULL,            "genLoopBegin: invalid Loop Graph");
  633.  
  634.     BLOCK_Preamble(q);
  635.     BlkLevel++;
  636.     f = First(q, 1, aLoopBegin, &max_k);
  637.     if ( LL_k>1 )
  638.     {
  639.         if ( !set_nil(q->fset[2]) )    genLoopBlk( (Junction *)q->p1, q, max_k );
  640.         else genLoopBlk( (Junction *)q->p1, NULL, max_k );
  641.     }
  642.     else genLoopBlk( (Junction *)q->p1, NULL, max_k );
  643.     for (i=1; i<=LL_k; i++) set_free(q->fset[i]);
  644.     for (i=1; i<=LL_k; i++) set_free(((Junction *)q->p2)->fset[i]);
  645.     --BlkLevel;
  646.     BLOCK_Tail();
  647.     set_free(f);
  648.     if (q->end->p1 != NULL) TRANS(q->end->p1);
  649. }
  650.  
  651. /*
  652.  * Generate code for a loop blk of form:
  653.  *
  654.  *                      |---|
  655.  *                     v   |
  656.  *                   --o-G-o-->o--
  657.  *
  658.  * q->end points to the last node (far right) in the blk.  Note that q->end->jtype
  659.  * must be 'EndBlk'.
  660.  *
  661.  * Generate code roughly of the following form:
  662.  *
  663.  *    do {
  664.  *        ... code for alternatives ...
  665.  *  } while ( First Set of aPlusBlk );
  666.  *
  667.  *    OR if > 1 alternative
  668.  *
  669.  *    do {
  670.  *        ... code for alternatives ...
  671.  *        else if not 1st time through, break;
  672.  *  } while ( 1 );
  673.  */
  674. void
  675. genPlusBlk(q)
  676. Junction *q;
  677. {
  678.     int max_k;
  679.     set f;
  680.     require(q!=NULL,                "genPlusBlk: invalid node and/or rule");
  681.     require(q->ntype == nJunction,    "genPlusBlk: not junction");
  682.     require(q->jtype == aPlusBlk,    "genPlusBlk: not Plus block");
  683.  
  684.     if ( q->visited ) return;
  685.     q->visited = TRUE;
  686.     BLOCK_Preamble(q);
  687.     BlkLevel++;
  688.     if ( q->p2 == NULL )    /* only one alternative? */
  689.     {
  690.         gen("do {\n");
  691.         tabs++;
  692.         TRANS(q->p1);
  693.         gen1("zzLOOP(zztasp%d);\n", BlkLevel-1);
  694.         f = First(q, 1, aPlusBlk, &max_k);
  695.         if ( DemandLookahead ) gen1("LOOK(%d);\n", max_k);
  696.         --tabs;
  697.         gen("} while ( ");
  698.         genExpr(q);
  699.         _gen(" );\n");
  700.         --BlkLevel;
  701.         BLOCK_Tail();
  702.         q->visited = FALSE;
  703.         freeBlkFsets(q);
  704.         set_free(f);
  705.         if (q->end->p1 != NULL) TRANS(q->end->p1);
  706.         return;
  707.     }
  708.     gen("do {\n");
  709.     tabs++;
  710.     f = genBlk(q, aPlusBlk, &max_k);
  711.     gen("else if ( zzcnt>1 ) break; ");/* code for exiting loop */
  712.     makeErrorClause(q,f,max_k);
  713.     freeBlkFsets(q);
  714.     gen1("zzcnt++; zzLOOP(zztasp%d);\n", BlkLevel-1);
  715.     if ( DemandLookahead ) gen1("LOOK(%d);\n", max_k);
  716.     --tabs;
  717.     gen("} while ( 1 );\n");
  718.     --BlkLevel;
  719.     BLOCK_Tail();
  720.     q->visited = FALSE;
  721.     if (q->end->p1 != NULL) TRANS(q->end->p1);
  722. }
  723.  
  724. /*
  725.  * Generate code for a sub blk of alternatives of form:
  726.  *
  727.  *                   --o-G1--o--
  728.  *                     |     ^
  729.  *                     v    /|
  730.  *                     o-G2-o|
  731.  *                     |     ^
  732.  *                     v     |
  733.  *                   ..........
  734.  *                     |     ^
  735.  *                     v    /
  736.  *                     o-Gn-o
  737.  *
  738.  * q points to the 1st junction of blk (upper-left).
  739.  * q->end points to the last node (far right) in the blk.  Note that q->end->jtype
  740.  * must be 'EndBlk'.
  741.  * The last node in every alt points to q->end.
  742.  *
  743.  * Generate code of the following form:
  744.  *    if ( First(G1) ) {
  745.  *        ...code for G1...
  746.  *    }
  747.  *    else if ( First(G2) ) {
  748.  *        ...code for G2...
  749.  *    }
  750.  *    ...
  751.  *    else {
  752.  *        ...code for Gn...
  753.  *    }
  754.  */
  755. void
  756. genSubBlk(q)
  757. Junction *q;
  758. {
  759.     int max_k;
  760.     set f;
  761.     require(q->ntype == nJunction,    "genSubBlk: not junction");
  762.     require(q->jtype == aSubBlk,    "genSubBlk: not subblock");
  763.  
  764.     BLOCK_Preamble(q);
  765.     BlkLevel++;
  766.     f = genBlk(q, aSubBlk, &max_k);
  767.     if ( q->p2 != NULL ) {tab(); makeErrorClause(q,f,max_k);}
  768.     freeBlkFsets(q);
  769.     --BlkLevel;
  770.     BLOCK_Tail();
  771.     if (q->end->p1 != NULL) TRANS(q->end->p1);
  772. }
  773.  
  774. /*
  775.  * Generate code for a rule.
  776.  *
  777.  *        rule--> o-->o-Alternatives-o-->o
  778.  * Or,
  779.  *        rule--> o-->o-Alternative-o-->o
  780.  *
  781.  * The 1st junction is a RuleBlk.  The second can be a SubBlk or just a junction
  782.  * (one alternative--no block), the last is EndRule.
  783.  * The second to last is EndBlk if more than one alternative exists in the rule.
  784.  *
  785.  * To get to the init-action for a rule, we must bypass the RuleBlk,
  786.  * and possible SubBlk.
  787.  * Mark any init-action as generated so genBlk() does not regenerate it.
  788.  */
  789. void
  790. genRule(q)
  791. Junction *q;
  792. {
  793.     int max_k;
  794.     set follow, rk, f;
  795.     ActionNode *a;
  796.     RuleEntry *r;
  797.     static int file = -1;
  798.     require(q->ntype == nJunction,    "genRule: not junction");
  799.     require(q->jtype == RuleBlk,    "genRule: not rule");
  800.  
  801.     r = (RuleEntry *) hash_get(Rname, q->rname);
  802.     if ( r == NULL ) warnNoFL("Rule hash table is screwed up beyond belief");
  803.     if ( q->file != file )        /* open new output file if need to */
  804.     {
  805.         if ( output != NULL ) fclose( output );
  806.         output = fopen(outname(FileStr[q->file]), "w");
  807.         require(output != NULL, "genRule: can't open output file");
  808.         if ( file == -1 ) genHdr1(q->file);
  809.         else genHdr(q->file);
  810.         file = q->file;
  811.     }
  812.     DumpFuncHeader(q,r);
  813.     tabs++;
  814.     if ( q->ret!=NULL )
  815.     {
  816.         if ( HasComma(q->ret) ) {gen1("struct _rv%d _retv;\n",r->rulenum);}
  817.         else
  818.         {
  819.             tab();
  820.             DumpType(q->ret, output);
  821.             gen(" _retv;\n");
  822.         }
  823.     }
  824.     gen("zzRULE;\n");
  825.     gen1("zzBLOCK(zztasp%d);\n", BlkLevel);
  826.     gen("zzMake0;\n");
  827.     gen("{\n");
  828.     
  829.     /* L o o k  F o r  I n i t  A c t i o n */
  830.     if ( ((Junction *)q->p1)->jtype == aSubBlk )
  831.         a = findImmedAction( ((Junction *)q->p1)->p1 );
  832.     else
  833.         a = findImmedAction( q->p1 );    /* only one alternative in rule */
  834.     if ( a!=NULL && !a->is_predicate )
  835.     {
  836.         dumpAction(a->action, output, tabs, a->file, a->line, 1);
  837.         a->done = 1;    /* ignore action. We have already handled it */
  838.     }
  839.     if ( TraceGen ) gen1("zzTRACEIN(\"%s\");\n", q->rname);
  840.  
  841.     BlkLevel++;
  842.     q->visited = TRUE;                /* mark RULE as visited for FIRST/FOLLOW */
  843.     f = genBlk((Junction *)q->p1, RuleBlk, &max_k);
  844.     if ( q->p1 != NULL )
  845.         if ( ((Junction *)q->p1)->p2 != NULL )
  846.             {tab(); makeErrorClause((Junction *)q->p1,f,max_k);}
  847.     freeBlkFsets((Junction *)q->p1);
  848.     q->visited = FALSE;
  849.     --BlkLevel;
  850.     gen1("zzEXIT(zztasp%d);\n", BlkLevel);
  851.  
  852.     if ( TraceGen ) gen1("zzTRACEOUT(\"%s\");\n", q->rname);
  853.  
  854.     if ( q->ret!=NULL ) gen("return _retv;\n") else gen("return;\n");
  855.     /* E r r o r  R e c o v e r y */
  856.     NewSet();
  857.     rk = empty;
  858.     REACH(q->end, 1, &rk, follow);
  859.     FillSet( follow );
  860.     set_free( follow );
  861.     _gen("fail:\n");
  862.     gen("zzEXIT(zztasp1);\n");
  863.     if ( q->erraction!=NULL )
  864.         dumpAction(q->erraction, output, tabs, q->file, q->line, 1);
  865.     gen1("zzsyn(zzMissText, zzBadTok, %s, zzMissSet, zzMissTok, zzErrk, zzBadText);\n", r->egroup==NULL?"\"\"":r->egroup);
  866.     gen2("zzresynch(setwd%d, 0x%x);\n", wordnum, 1<<setnum);
  867.  
  868.     if ( TraceGen ) gen1("zzTRACEOUT(\"%s\");\n", q->rname);
  869.  
  870.     if ( q->ret!=NULL ) gen("return _retv;\n");
  871.     gen("}\n");
  872.     tabs--;
  873.     gen("}\n");
  874.     if ( q->p2 != NULL ) {TRANS(q->p2);} /* generate code for next rule too */
  875.     else dumpAfterActions( output );
  876. }
  877.  
  878. static void
  879. DumpFuncHeader(q, r)
  880. Junction *q;
  881. RuleEntry *r;
  882. {
  883.     /* A N S I */
  884.     _gen("\n#ifdef __STDC__\n");
  885.     if ( q->ret!=NULL )
  886.     {
  887.         if ( HasComma(q->ret) ) {gen1("struct _rv%d\n",r->rulenum);}
  888.         else
  889.         {
  890.             DumpType(q->ret, output);
  891.             gen("\n");
  892.         }
  893.     }
  894.     else
  895.     {
  896.         _gen("void\n");
  897.     }
  898.     gen2("%s%s(", RulePrefix, q->rname);
  899.     if ( GenAST )
  900.     {
  901.         _gen("AST **_root");
  902.         if ( q->pdecl!=NULL ) _gen(",");
  903.     }
  904.     _gen1("%s)\n", (q->pdecl!=NULL)?q->pdecl:"");
  905.  
  906.     /* K & R */
  907.     gen("#else\n");
  908.     if ( q->ret!=NULL )
  909.     {
  910.         if ( HasComma(q->ret) ) {gen1("struct _rv%d\n",r->rulenum);}
  911.         else
  912.         {
  913.             DumpType(q->ret, output);
  914.             gen("\n");
  915.         }
  916.     }
  917.     gen2("%s%s(", RulePrefix, q->rname);
  918.     if ( GenAST )
  919.     {
  920.         _gen("_root");
  921.         if ( q->pdecl!=NULL ) _gen(",");
  922.     }
  923.  
  924.     DumpListOfParmNames( q->pdecl, output );
  925.     gen(")\n");
  926.     if ( GenAST ) gen("AST **_root;\n");
  927.     DumpOldStyleParms( q->pdecl, output );
  928.     gen("#endif\n");
  929.     gen("{\n");
  930. }
  931.  
  932. void
  933. genJunction(q)
  934. Junction *q;
  935. {
  936.     require(q->ntype == nJunction,    "genJunction: not junction");
  937.     require(q->jtype == Generic,    "genJunction: not generic junction");
  938.  
  939.     if ( q->p1 != NULL ) TRANS(q->p1);
  940.     if ( q->p2 != NULL ) TRANS(q->p2);
  941. }
  942.  
  943. void
  944. genEndBlk(q)
  945. Junction *q;
  946. {
  947. }
  948.  
  949. void
  950. genEndRule(q)
  951. Junction *q;
  952. {
  953. }
  954.  
  955. void
  956. genHdr(file)
  957. int file;
  958. {
  959.     _gen("/*\n");
  960.     _gen(" * A n t l r  T r a n s l a t i o n  H e a d e r\n");
  961.     _gen(" *\n");
  962.     _gen(" * Terence Parr, Hank Dietz and Will Cohen: 1989-1992\n");
  963.     _gen(" * Purdue University Electrical Engineering\n");
  964.     _gen1(" * ANTLR Version %s\n", Version);
  965.     _gen(" */\n");
  966.     _gen("#include <stdio.h>\n");
  967.     if ( GenLineInfo ) _gen2(LineInfoFormatStr, 1, FileStr[file]);
  968.     if ( HdrAction != NULL ) dumpAction( HdrAction, output, 0, -1, 0, 1);
  969.     if ( LL_k > 1 ) _gen1("#define LL_K %d\n", OutputLL_k);
  970.     if ( GenAST ) _gen("#define GENAST\n\n");
  971.     if ( DemandLookahead ) _gen("#define DEMAND_LOOK\n\n");
  972.     _gen("#include \"antlr.h\"\n");
  973.     if ( GenAST ) _gen("#include \"ast.h\"\n\n");
  974.     _gen1("#include \"%s\"\n", DefFileName);
  975.     _gen("#include \"dlgdef.h\"\n");
  976.     _gen("#include \"mode.h\"\n");
  977. }
  978.  
  979. void
  980. genHdr1(file)
  981. int file;
  982. {
  983.     ListNode *p;
  984.  
  985.     genHdr(file);
  986.     if ( GenAST )
  987.     {
  988.         _gen("#include \"ast.c\"\n");
  989.         _gen("zzASTgvars\n\n");
  990.     }
  991.     _gen("ANTLR_INFO\n");
  992.     if ( BeforeActions != NULL )
  993.     {
  994.         for (p = BeforeActions->next; p!=NULL; p=p->next)
  995.             dumpAction( p->elem, output, 0, -1, 0, 1);
  996.     }
  997. }
  998.  
  999. void
  1000. genStdPCCTSIncludeFile(f)
  1001. FILE *f;
  1002. {
  1003.     fprintf(f,"/*\n");
  1004.     fprintf(f," * %s -- P C C T S  I n c l u d e\n", stdpccts);
  1005.     fprintf(f," *\n");
  1006.     fprintf(f," * Terence Parr, Hank Dietz and Will Cohen: 1989-1992\n");
  1007.     fprintf(f," * Purdue University Electrical Engineering\n");
  1008.     fprintf(f," * ANTLR Version %s\n", Version);
  1009.     fprintf(f," */\n");
  1010.     fprintf(f,"#include <stdio.h>\n");
  1011.     if ( HdrAction != NULL ) dumpAction( HdrAction, f, 0, -1, 0, 1);
  1012.     if ( LL_k > 1 ) fprintf(f,"#define LL_K %d\n", OutputLL_k);
  1013.     if ( GenAST ) fprintf(f,"#define GENAST\n");
  1014.     if ( DemandLookahead ) fprintf(f,"#define DEMAND_LOOK\n");
  1015.     fprintf(f,"#include \"antlr.h\"\n");
  1016.     if ( GenAST ) fprintf(f,"#include \"ast.h\"\n");
  1017.     fprintf(f,"#include \"%s\"\n", DefFileName);
  1018.     fprintf(f,"#include \"dlgdef.h\"\n");
  1019.     fprintf(f,"#include \"mode.h\"\n");
  1020. }
  1021.  
  1022. /* dump action 's' to file 'output' starting at "local" tab 'tabs'
  1023.    Dump line information in front of action if GenLineInfo is set
  1024.    If file == -1 then GenLineInfo is ignored.
  1025.    The user may redefine the LineInfoFormatStr to his/her liking
  1026.    most compilers will like the default, however.
  1027. */
  1028. void
  1029. dumpAction(s,output,tabs,file,line,final_newline)
  1030. char *s;
  1031. FILE *output;
  1032. int tabs, file, line;
  1033. int final_newline;
  1034. {
  1035.     int inDQuote, inSQuote;
  1036.     require(s!=NULL,         "dumpAction: NULL action");
  1037.     require(output!=NULL,    eMsg1("dumpAction: output FILE is NULL for %s",s));
  1038.  
  1039.     if ( GenLineInfo && file != -1 )
  1040.     {
  1041.         fprintf(output, LineInfoFormatStr, line, FileStr[file]);
  1042.     }
  1043.     TAB;
  1044.     PastWhiteSpace( s );
  1045.     inDQuote = inSQuote = FALSE;
  1046.     while ( *s != '\0' )
  1047.     {
  1048.         if ( *s == '\\' )
  1049.         {
  1050.             putc( *s++, output ); /* Avoid '"' Case */
  1051.             if ( *s == '\0' ) return;
  1052.             if ( *s == '\'' ) putc( *s++, output );
  1053.             if ( *s == '\"' ) putc( *s++, output );
  1054.         }
  1055.         if ( *s == '\'' )
  1056.         {
  1057.             if ( !inDQuote ) inSQuote = !inSQuote;
  1058.         }
  1059.         if ( *s == '"' )
  1060.         {
  1061.             if ( !inSQuote ) inDQuote = !inDQuote;
  1062.         }
  1063.         if ( *s == '\n' )
  1064.         {
  1065.             putc('\n', output);
  1066.             PastWhiteSpace( s );
  1067.             if ( *s == '}' )
  1068.             {
  1069.                 --tabs;
  1070.                 TAB;
  1071.                 putc( *s++, output );
  1072.                 continue;
  1073.             }
  1074.             if ( *s == '\0' ) return;
  1075.             if ( *s != '#' )    /* #define, #endif etc.. start at col 1 */
  1076.             {
  1077.                 TAB;
  1078.             }
  1079.         }
  1080.         if ( *s == '}' && !(inSQuote || inDQuote) )
  1081.         {
  1082.             --tabs;            /* Indent one fewer */
  1083.         }
  1084.         if ( *s == '{' && !(inSQuote || inDQuote) )
  1085.         {
  1086.             tabs++;            /* Indent one more */
  1087.         }
  1088.         putc( *s, output );
  1089.         s++;
  1090.     }
  1091.     if ( final_newline ) putc('\n', output);
  1092. }
  1093.  
  1094. static
  1095. dumpAfterActions(output)
  1096. FILE *output;
  1097. {
  1098.     ListNode *p;
  1099.     require(output!=NULL, "dumpAfterActions: output file was NULL for some reason");
  1100.     if ( AfterActions != NULL )
  1101.     {
  1102.         for (p = AfterActions->next; p!=NULL; p=p->next)
  1103.             dumpAction( p->elem, output, 0, -1, 0, 1 );
  1104.     }
  1105.     fclose( output );
  1106. }
  1107.  
  1108. /*
  1109.  * Find the next action in the stream of execution.  Do not pass
  1110.  * junctions with more than one path leaving them.
  1111.  * Only pass generic junctions.
  1112.  *
  1113.  *    Scan forward while (generic junction with p2==NULL)
  1114.  *    If we stop on an action, return ptr to the action
  1115.  *    else return NULL;
  1116.  */
  1117. static ActionNode *
  1118. findImmedAction(q)
  1119. Node *q;
  1120. {
  1121.     Junction *j;
  1122.     require(q!=NULL, "findImmedAction: NULL node");
  1123.     require(q->ntype>=1 && q->ntype<=NumNodeTypes, "findImmedAction: invalid node");
  1124.     
  1125.     while ( q->ntype == nJunction )
  1126.     {
  1127.         j = (Junction *)q;
  1128.         if ( j->jtype != Generic || j->p2 != NULL ) return NULL;
  1129.         q = j->p1;
  1130.         if ( q == NULL ) return NULL;
  1131.     }
  1132.     if ( q->ntype == nAction ) return (ActionNode *)q;
  1133.     return NULL;
  1134. }
  1135.  
  1136. static void
  1137. dumpRetValAssign(retval, ret_def)
  1138. char *retval, *ret_def;
  1139. {
  1140.     char *q = ret_def;
  1141.     
  1142.     tab();
  1143.     while ( *retval != '\0' )
  1144.     {
  1145.         while ( isspace((*retval)) ) retval++;
  1146.         while ( *retval!=',' && *retval!='\0' ) putc(*retval++, output);
  1147.         fprintf(output, " = _trv.");
  1148.         
  1149.         DumpNextNameInDef(&q, output);
  1150.         putc(';', output); putc(' ', output);
  1151.         if ( *retval == ',' ) retval++;
  1152.     }
  1153. }
  1154.  
  1155. /* This function computes the set of tokens that can possibly be seen k
  1156.  * tokens in the future from point j
  1157.  */
  1158. static set
  1159. ComputeErrorSet(j,k)
  1160. Junction *j;
  1161. int k;
  1162. {
  1163.     Junction *alt1;
  1164.     set a, rk, f;
  1165.     require(j->ntype==nJunction, "ComputeErrorSet: non junction passed");
  1166.  
  1167.     f = rk = empty;
  1168.     for (alt1=j; alt1!=NULL; alt1 = (Junction *)alt1->p2)
  1169.     {
  1170.         REACH(alt1->p1, k, &rk, a);
  1171.         require(set_nil(rk), "ComputeErrorSet: rk != nil");
  1172.         set_orin(&f, a);
  1173.     }
  1174.     return f;
  1175. }
  1176.  
  1177. static void
  1178. makeErrorClause(q, f, max_k)
  1179. Junction *q;
  1180. set f;
  1181. int max_k;
  1182. {
  1183.     if ( max_k == 1 )
  1184.     {
  1185.         _gen1("else {zzFAIL(1,zzerr%d", DefErrSet(&f))
  1186.         set_free(f);
  1187.     }
  1188.     else
  1189.     {
  1190.         int i;
  1191.         set_free(f);
  1192.         _gen1("else {zzFAIL(%d", max_k);
  1193.         for (i=1; i<=max_k; i++)
  1194.         {
  1195.             f = ComputeErrorSet(q, i);
  1196.             _gen1(",zzerr%d", DefErrSet( &f ));
  1197.             set_free(f);
  1198.         }
  1199.     }
  1200.     _gen(",&zzMissSet,&zzMissText,&zzBadTok,&zzBadText,&zzErrk); goto fail;}\n");
  1201. }
  1202.