Home | History | Annotate | Download | only in antlr
      1 /*
      2  * build.c -- functions associated with building syntax diagrams.
      3  *
      4  * SOFTWARE RIGHTS
      5  *
      6  * We reserve no LEGAL rights to the Purdue Compiler Construction Tool
      7  * Set (PCCTS) -- PCCTS is in the public domain.  An individual or
      8  * company may do whatever they wish with source code distributed with
      9  * PCCTS or the code generated by PCCTS, including the incorporation of
     10  * PCCTS, or its output, into commerical software.
     11  *
     12  * We encourage users to develop software with PCCTS.  However, we do ask
     13  * that credit is given to us for developing PCCTS.  By "credit",
     14  * we mean that if you incorporate our source code into one of your
     15  * programs (commercial product, research project, or otherwise) that you
     16  * acknowledge this fact somewhere in the documentation, research report,
     17  * etc...  If you like PCCTS and have developed a nice tool with the
     18  * output, please mention that you developed it using PCCTS.  In
     19  * addition, we ask that this header remain intact in our source code.
     20  * As long as these guidelines are kept, we expect to continue enhancing
     21  * this system and expect to make other tools available as they are
     22  * completed.
     23  *
     24  * ANTLR 1.33
     25  * Terence Parr
     26  * Parr Research Corporation
     27  * with Purdue University and AHPCRC, University of Minnesota
     28  * 1989-2001
     29  */
     30 
     31 #include <stdio.h>
     32 #include <stdlib.h>
     33 #include <ctype.h>
     34 #include "pcctscfg.h"
     35 #include "set.h"
     36 #include "syn.h"
     37 #include "hash.h"
     38 #include "generic.h"
     39 #include "dlgdef.h"
     40 
     41 #define SetBlk(g, t, approx, first_set_symbol) {         		        \
     42 			((Junction *)g.left)->jtype = t;					        \
     43 			((Junction *)g.left)->approx = approx;				        \
     44 			((Junction *)g.left)->pFirstSetSymbol = first_set_symbol;   \
     45 			((Junction *)g.left)->end = (Junction *) g.right;	        \
     46 			((Junction *)g.right)->jtype = EndBlk;}
     47 
     48 /* Add the parameter string 'parm' to the parms field of a block-type junction
     49  * g.left points to the sentinel node on a block.  i.e. g.left->p1 points to
     50  * the actual junction with its jtype == some block-type.
     51  */
     52 void
     53 #ifdef __USE_PROTOS
     54 addParm( Node *p, char *parm )
     55 #else
     56 addParm( p, parm )
     57 Node *p;
     58 char *parm;
     59 #endif
     60 {
     61 	char *q = (char *) malloc( strlen(parm) + 1 );
     62 	require(p!=NULL, "addParm: NULL object\n");
     63 	require(q!=NULL, "addParm: unable to alloc parameter\n");
     64 
     65 	strcpy(q, parm);
     66 	if ( p->ntype == nRuleRef )
     67 	{
     68 		((RuleRefNode *)p)->parms = q;
     69 	}
     70 	else if ( p->ntype == nJunction )
     71 	{
     72 		((Junction *)p)->parm = q;	/* only one parameter allowed on subrules */
     73 	}
     74 	else fatal_internal("addParm: invalid node for adding parm");
     75 }
     76 
     77 /*
     78  * Build an action node for the syntax diagram
     79  *
     80  * buildAction(ACTION) ::= --o-->ACTION-->o--
     81  *
     82  * Where o is a junction node.
     83  */
     84 Graph
     85 #ifdef __USE_PROTOS
     86 buildAction( char *action, int file, int line, int is_predicate )
     87 #else
     88 buildAction( action, file, line, is_predicate )
     89 char *action;
     90 int file;
     91 int line;
     92 int is_predicate;
     93 #endif
     94 {
     95 	Junction *j1, *j2;
     96 	Graph g;
     97 	ActionNode *a;
     98 	require(action!=NULL, "buildAction: invalid action");
     99 
    100 	j1 = newJunction();
    101 	j2 = newJunction();
    102 	a = newActionNode();
    103 	a->action = (char *) malloc( strlen(action)+1 );
    104 	require(a->action!=NULL, "buildAction: cannot alloc space for action\n");
    105 	strcpy(a->action, action);
    106 	j1->p1 = (Node *) a;
    107 	a->next = (Node *) j2;
    108 	a->is_predicate = is_predicate;
    109 
    110     if (is_predicate) {
    111         PredEntry   *predEntry;
    112         char        *t;
    113         char        *key;
    114         char        *u;
    115         int         inverted=0;
    116 
    117         t=key=(char *)calloc(1,strlen(a->action)+1);
    118 
    119         for (u=a->action; *u != '\0' ; u++) {
    120           if (*u != ' ') {
    121             if (t==key && *u=='!') {
    122               inverted=!inverted;
    123             } else {
    124               *t++=*u;
    125             };
    126           };
    127         };
    128 
    129         *t='\0';
    130 
    131 
    132         predEntry=(PredEntry *)hash_get(Pname,key);
    133         a->predEntry=predEntry;
    134         if (predEntry != NULL) a->inverted=inverted;
    135     } else {
    136 /* MR12c */      char  *strStart=a->action;
    137 /* MR12c */      char  *strEnd;
    138 /* MR12c */      strEnd=strStart+strlen(strStart)-1;
    139 /* MR12c */      for ( ; strEnd >= strStart &&  isspace(*strEnd); strEnd--) *strEnd=0;
    140 /* MR12c */      while (*strStart != '\0' && isspace(*strStart)) strStart++;
    141 /* MR12c */      if (ci_strequ(strStart,"nohoist")) {
    142 /* MR12c */        a->noHoist=1;
    143 /* MR12c */      }
    144 	}
    145 
    146 	g.left = (Node *) j1; g.right = (Node *) j2;
    147 	a->file = file;
    148 	a->line = line;
    149 	a->rname = CurRule;     /* MR10 */
    150 	return g;
    151 }
    152 
    153 /*
    154  * Build a token node for the syntax diagram
    155  *
    156  * buildToken(TOKEN) ::= --o-->TOKEN-->o--
    157  *
    158  * Where o is a junction node.
    159  */
    160 Graph
    161 #ifdef __USE_PROTOS
    162 buildToken( char *text )
    163 #else
    164 buildToken( text )
    165 char *text;
    166 #endif
    167 {
    168 	Junction *j1, *j2;
    169 	Graph g;
    170 	TokNode *t;
    171 	require(text!=NULL, "buildToken: invalid token name");
    172 
    173 	j1 = newJunction();
    174 	j2 = newJunction();
    175 	t = newTokNode();
    176 	t->altstart = CurAltStart;
    177 	if ( *text == '"' ) {t->label=FALSE; t->token = addTexpr( text );}
    178 	else {t->label=TRUE; t->token = addTname( text );}
    179 	j1->p1 = (Node *) t;
    180 	t->next = (Node *) j2;
    181 	g.left = (Node *) j1; g.right = (Node *) j2;
    182 	return g;
    183 }
    184 
    185 /*
    186  * Build a wild-card node for the syntax diagram
    187  *
    188  * buildToken(TOKEN) ::= --o-->'.'-->o--
    189  *
    190  * Where o is a junction node.
    191  */
    192 Graph
    193 #ifdef __USE_PROTOS
    194 buildWildCard( char *text )
    195 #else
    196 buildWildCard( text )
    197 char *text;
    198 #endif
    199 {
    200 	Junction *j1, *j2;
    201 	Graph g;
    202 	TokNode *t;
    203 	TCnode *w;
    204 	TermEntry *p;
    205 	require(text!=NULL, "buildWildCard: invalid token name");
    206 
    207 	j1 = newJunction();
    208 	j2 = newJunction();
    209 	t = newTokNode();
    210 
    211 	/* If the ref a wild card, make a token class for it */
    212 	if ( Tnum(WildCardString) == 0 )
    213 	{
    214 		w = newTCnode;
    215 	  	w->tok = addTname( WildCardString );
    216 		set_orel(w->tok, &imag_tokens);
    217 		set_orel(w->tok, &tokclasses);
    218 		WildCardToken = w->tok;
    219 		require((p=(TermEntry *)hash_get(Tname, WildCardString)) != NULL,
    220 				"hash table mechanism is broken");
    221 		p->classname = 1;	/* entry is class name, not token */
    222 		p->tclass = w;		/* save ptr to this tclass def */
    223 		list_add(&tclasses, (char *)w);
    224 	}
    225 	else {
    226 		p=(TermEntry *)hash_get(Tname, WildCardString);
    227 		require( p!= NULL, "hash table mechanism is broken");
    228 		w = p->tclass;
    229 	}
    230 
    231 	t->token = w->tok;
    232 	t->wild_card = 1;
    233 	t->tclass = w;
    234 
    235 	t->altstart = CurAltStart;
    236 	j1->p1 = (Node *) t;
    237 	t->next = (Node *) j2;
    238 	g.left = (Node *) j1; g.right = (Node *) j2;
    239 	return g;
    240 }
    241 
    242 void
    243 #ifdef __USE_PROTOS
    244 setUpperRange(TokNode *t, char *text)
    245 #else
    246 setUpperRange(t, text)
    247 TokNode *t;
    248 char *text;
    249 #endif
    250 {
    251 	require(t!=NULL, "setUpperRange: NULL token node");
    252 	require(text!=NULL, "setUpperRange: NULL token string");
    253 
    254 	if ( *text == '"' ) {t->upper_range = addTexpr( text );}
    255 	else {t->upper_range = addTname( text );}
    256 }
    257 
    258 /*
    259  * Build a rule reference node of the syntax diagram
    260  *
    261  * buildRuleRef(RULE) ::= --o-->RULE-->o--
    262  *
    263  * Where o is a junction node.
    264  *
    265  * If rule 'text' has been defined already, don't alloc new space to store string.
    266  * Set r->text to point to old copy in string table.
    267  */
    268 Graph
    269 #ifdef __USE_PROTOS
    270 buildRuleRef( char *text )
    271 #else
    272 buildRuleRef( text )
    273 char *text;
    274 #endif
    275 {
    276 	Junction *j1, *j2;
    277 	Graph g;
    278 	RuleRefNode *r;
    279 	RuleEntry *p;
    280 	require(text!=NULL, "buildRuleRef: invalid rule name");
    281 
    282 	j1 = newJunction();
    283 	j2 = newJunction();
    284 	r = newRNode();
    285 	r->altstart = CurAltStart;
    286 	r->assign = NULL;
    287 	if ( (p=(RuleEntry *)hash_get(Rname, text)) != NULL ) r->text = p->str;
    288 	else r->text = mystrdup( text );
    289 	j1->p1  = (Node *) r;
    290 	r->next = (Node *) j2;
    291 	g.left = (Node *) j1; g.right = (Node *) j2;
    292 	return g;
    293 }
    294 
    295 /*
    296  * Or two subgraphs into one graph via:
    297  *
    298  * Or(G1, G2) ::= --o-G1-o--
    299  *                  |    ^
    300  *					v    |
    301  *                  o-G2-o
    302  *
    303  * Set the altnum of junction starting G2 to 1 + altnum of junction starting G1.
    304  * If, however, the G1 altnum is 0, make it 1 and then
    305  * make G2 altnum = G1 altnum + 1.
    306  */
    307 Graph
    308 #ifdef __USE_PROTOS
    309 Or( Graph g1, Graph g2 )
    310 #else
    311 Or( g1, g2 )
    312 Graph g1;
    313 Graph g2;
    314 #endif
    315 {
    316 	Graph g;
    317 	require(g1.left != NULL, "Or: invalid graph");
    318 	require(g2.left != NULL && g2.right != NULL, "Or: invalid graph");
    319 
    320 	((Junction *)g1.left)->p2 = g2.left;
    321 	((Junction *)g2.right)->p1 = g1.right;
    322 	/* set altnums */
    323 	if ( ((Junction *)g1.left)->altnum == 0 ) ((Junction *)g1.left)->altnum = 1;
    324 	((Junction *)g2.left)->altnum = ((Junction *)g1.left)->altnum + 1;
    325 	g.left = g2.left;
    326 	g.right = g1.right;
    327 	return g;
    328 }
    329 
    330 /*
    331  * Catenate two subgraphs
    332  *
    333  * Cat(G1, G2) ::= --o-G1-o-->o-G2-o--
    334  * Cat(NULL,G2)::= --o-G2-o--
    335  * Cat(G1,NULL)::= --o-G1-o--
    336  */
    337 Graph
    338 #ifdef __USE_PROTOS
    339 Cat( Graph g1, Graph g2 )
    340 #else
    341 Cat( g1, g2 )
    342 Graph g1;
    343 Graph g2;
    344 #endif
    345 {
    346 	Graph g;
    347 
    348 	if ( g1.left == NULL && g1.right == NULL ) return g2;
    349 	if ( g2.left == NULL && g2.right == NULL ) return g1;
    350 	((Junction *)g1.right)->p1 = g2.left;
    351 	g.left = g1.left;
    352 	g.right = g2.right;
    353 	return g;
    354 }
    355 
    356 /*
    357  * Make a subgraph an optional block
    358  *
    359  * makeOpt(G) ::= --o-->o-G-o-->o--
    360  *                      | 	    ^
    361  *						v  	    |
    362  *					    o-------o
    363  *
    364  * Note that this constructs {A|B|...|Z} as if (A|B|...|Z|) was found.
    365  *
    366  * The node on the far right is added so that every block owns its own
    367  * EndBlk node.
    368  */
    369 Graph
    370 #ifdef __USE_PROTOS
    371 makeOpt( Graph g1, int approx, char * pFirstSetSymbol )
    372 #else
    373 makeOpt( g1, approx, pFirstSetSymbol )
    374 Graph g1;
    375 int approx;
    376 char * pFirstSetSymbol;
    377 #endif
    378 {
    379 	Junction *j1,*j2,*p;
    380 	Graph g;
    381 	require(g1.left != NULL && g1.right != NULL, "makeOpt: invalid graph");
    382 
    383 	j1 = newJunction();
    384 	j2 = newJunction();
    385 	((Junction *)g1.right)->p1 = (Node *) j2;	/* add node to G at end */
    386 
    387     /*  MR21
    388      *
    389      *  There is code in genBlk which recognizes the node created
    390      *  by emptyAlt() as a special case and bypasses it.  We don't
    391      *  want this to happen for the optBlk.
    392      */
    393 
    394 	g = emptyAlt3(); /* MR21 */
    395 	if ( ((Junction *)g1.left)->altnum == 0 ) ((Junction *)g1.left)->altnum = 1;
    396 	((Junction *)g.left)->altnum = ((Junction *)g1.left)->altnum + 1;
    397 	for(p=(Junction *)g1.left; p->p2!=NULL; p=(Junction *)p->p2)
    398 		{;}										/* find last alt */
    399 	p->p2 = g.left;								/* add optional alternative */
    400 	((Junction *)g.right)->p1 = (Node *)j2;		/* opt alt points to EndBlk */
    401 	g1.right = (Node *)j2;
    402 	SetBlk(g1, aOptBlk, approx, pFirstSetSymbol);
    403 	j1->p1 = g1.left;							/* add generic node in front */
    404 	g.left = (Node *) j1;
    405 	g.right = g1.right;
    406 	return g;
    407 }
    408 
    409 /*
    410  * Make a graph into subblock
    411  *
    412  * makeBlk(G) ::= --o-->o-G-o-->o--
    413  *
    414  * The node on the far right is added so that every block owns its own
    415  * EndBlk node.
    416  */
    417 Graph
    418 #ifdef __USE_PROTOS
    419 makeBlk( Graph g1, int approx, char * pFirstSetSymbol )
    420 #else
    421 makeBlk( g1, approx, pFirstSetSymbol )
    422 Graph g1;
    423 int approx;
    424 char * pFirstSetSymbol;
    425 #endif
    426 {
    427 	Junction *j,*j2;
    428 	Graph g;
    429 	require(g1.left != NULL && g1.right != NULL, "makeBlk: invalid graph");
    430 
    431 	j = newJunction();
    432 	j2 = newJunction();
    433 	((Junction *)g1.right)->p1 = (Node *) j2;	/* add node to G at end */
    434 	g1.right = (Node *)j2;
    435 	SetBlk(g1, aSubBlk, approx, pFirstSetSymbol);
    436 	j->p1 = g1.left;							/* add node in front */
    437 	g.left = (Node *) j;
    438 	g.right = g1.right;
    439 
    440 	return g;
    441 }
    442 
    443 /*
    444  * Make a subgraph into a loop (closure) block -- (...)*
    445  *
    446  * makeLoop(G) ::=       |---|
    447  *					     v   |
    448  *			   --o-->o-->o-G-o-->o--
    449  *                   |           ^
    450  *                   v           |
    451  *					 o-----------o
    452  *
    453  * After making loop, always place generic node out front.  It becomes
    454  * the start of enclosing block.  The aLoopBlk is the target of the loop.
    455  *
    456  * Loop blks have TWO EndBlk nodes--the far right and the node that loops back
    457  * to the aLoopBlk node.  Node with which we can branch past loop == aLoopBegin and
    458  * one which is loop target == aLoopBlk.
    459  * The branch-past (initial) aLoopBegin node has end
    460  * pointing to the last EndBlk node.  The loop-target node has end==NULL.
    461  *
    462  * Loop blocks have a set of locks (from 1..CLL_k) on the aLoopBlk node.
    463  */
    464 Graph
    465 #ifdef __USE_PROTOS
    466 makeLoop( Graph g1, int approx, char * pFirstSetSymbol )
    467 #else
    468 makeLoop( g1, approx, pFirstSetSymbol)
    469 Graph g1;
    470 int approx;
    471 char * pFirstSetSymbol;
    472 #endif
    473 {
    474 	Junction *back, *front, *begin;
    475 	Graph g;
    476 	require(g1.left != NULL && g1.right != NULL, "makeLoop: invalid graph");
    477 
    478 	back = newJunction();
    479 	front = newJunction();
    480 	begin = newJunction();
    481 	g = emptyAlt3();
    482 	((Junction *)g1.right)->p2 = g1.left;		/* add loop branch to G */
    483 	((Junction *)g1.right)->p1 = (Node *) back;	/* add node to G at end */
    484 	((Junction *)g1.right)->jtype = EndBlk;		/* mark 1st EndBlk node */
    485 	((Junction *)g1.left)->jtype = aLoopBlk;	/* mark 2nd aLoopBlk node */
    486 	((Junction *)g1.left)->end = (Junction *) g1.right;
    487 	((Junction *)g1.left)->lock = makelocks();
    488 	((Junction *)g1.left)->pred_lock = makelocks();
    489 	g1.right = (Node *) back;
    490 	begin->p1 = (Node *) g1.left;
    491 	g1.left = (Node *) begin;
    492 	begin->p2 = (Node *) g.left;				/* make bypass arc */
    493 	((Junction *)g.right)->p1 = (Node *) back;
    494 	SetBlk(g1, aLoopBegin, approx, pFirstSetSymbol);
    495 	front->p1 = g1.left;						/* add node to front */
    496 	g1.left = (Node *) front;
    497 
    498 	return g1;
    499 }
    500 
    501 /*
    502  * Make a subgraph into a plus block -- (...)+ -- 1 or more times
    503  *
    504  * makePlus(G) ::=	 |---|
    505  *					 v   |
    506  *			   --o-->o-G-o-->o--
    507  *
    508  * After making loop, always place generic node out front.  It becomes
    509  * the start of enclosing block.  The aPlusBlk is the target of the loop.
    510  *
    511  * Plus blks have TWO EndBlk nodes--the far right and the node that loops back
    512  * to the aPlusBlk node.
    513  *
    514  * Plus blocks have a set of locks (from 1..CLL_k) on the aPlusBlk node.
    515  */
    516 Graph
    517 #ifdef __USE_PROTOS
    518 makePlus( Graph g1, int approx, char * pFirstSetSymbol)
    519 #else
    520 makePlus( g1, approx, pFirstSetSymbol)
    521 Graph g1;
    522 int approx;
    523 char * pFirstSetSymbol;
    524 #endif
    525 {
    526 	int has_empty_alt_already = 0;
    527 	Graph g;
    528 	Junction *j2, *j3, *first_alt;
    529 	Junction *last_alt=NULL, *p;
    530 	require(g1.left != NULL && g1.right != NULL, "makePlus: invalid graph");
    531 
    532 	first_alt = (Junction *)g1.left;
    533 	j2 = newJunction();
    534 	j3 = newJunction();
    535 	if ( ((Junction *)g1.left)->altnum == 0 ) ((Junction *)g1.left)->altnum = 1;
    536 	((Junction *)g1.right)->p2 = g1.left;		/* add loop branch to G */
    537 	((Junction *)g1.right)->p1 = (Node *) j2;	/* add node to G at end */
    538 	((Junction *)g1.right)->jtype = EndBlk;		/* mark 1st EndBlk node */
    539 	g1.right = (Node *) j2;
    540 	SetBlk(g1, aPlusBlk, approx, pFirstSetSymbol);
    541 	((Junction *)g1.left)->lock = makelocks();
    542 	((Junction *)g1.left)->pred_lock = makelocks();
    543 	j3->p1 = g1.left;							/* add node to front */
    544 	g1.left = (Node *) j3;
    545 
    546 	/* add an optional branch which is the "exit" branch of loop */
    547 	/* FIRST, check to ensure that there does not already exist
    548 	 * an optional path.
    549 	 */
    550 	/* find last alt */
    551 	for(p=first_alt; p!=NULL; p=(Junction *)p->p2)
    552 	{
    553 		if ( p->p1->ntype == nJunction &&
    554 			 p->p1!=NULL &&
    555 			 ((Junction *)p->p1)->jtype==Generic &&
    556 			 ((Junction *)p->p1)->p1!=NULL &&
    557 			 ((Junction *)((Junction *)p->p1)->p1)->jtype==EndBlk )
    558 		{
    559 			has_empty_alt_already = 1;
    560 		}
    561 		last_alt = p;
    562 	}
    563 	if ( !has_empty_alt_already )
    564 	{
    565 		require(last_alt!=NULL, "last_alt==NULL; bad (..)+");
    566 		g = emptyAlt();
    567 		last_alt->p2 = g.left;
    568 		((Junction *)g.right)->p1 = (Node *) j2;
    569 
    570 		/* make sure lookahead computation ignores this alt for
    571 		* FIRST("(..)+"); but it's still used for computing the FIRST
    572 		* of each alternative.
    573 		*/
    574 		((Junction *)g.left)->ignore = 1;
    575 	}
    576 
    577 	return g1;
    578 }
    579 
    580 /*
    581  * Return an optional path:  --o-->o--
    582  */
    583 
    584 Graph
    585 #ifdef __USE_PROTOS
    586 emptyAlt( void )
    587 #else
    588 emptyAlt( )
    589 #endif
    590 {
    591 	Junction *j1, *j2;
    592 	Graph g;
    593 
    594 	j1 = newJunction();
    595 	j2 = newJunction();
    596 	j1->p1 = (Node *) j2;
    597 	g.left = (Node *) j1;
    598 	g.right = (Node *) j2;
    599 
    600 	return g;
    601 }
    602 
    603 /*  MR21
    604  *
    605  *  There is code in genBlk which recognizes the node created
    606  *  by emptyAlt() as a special case and bypasses it.  We don't
    607  *  want this to happen for the optBlk.
    608  */
    609 
    610 Graph
    611 #ifdef __USE_PROTOS
    612 emptyAlt3( void )
    613 #else
    614 emptyAlt3( )
    615 #endif
    616 {
    617 	Junction *j1, *j2, *j3;
    618 	Graph g;
    619 
    620 	j1 = newJunction();
    621 	j2 = newJunction();
    622     j3 = newJunction();
    623 	j1->p1 = (Node *) j2;
    624 	j2->p1 = (Node *) j3;
    625 	g.left = (Node *) j1;
    626 	g.right = (Node *) j3;
    627 
    628 	return g;
    629 }
    630 
    631 /* N o d e  A l l o c a t i o n */
    632 
    633 TokNode *
    634 #ifdef __USE_PROTOS
    635 newTokNode( void )
    636 #else
    637 newTokNode( )
    638 #endif
    639 {
    640 	static TokNode *FreeList = NULL;
    641 	TokNode *p, *newblk;
    642 
    643 	if ( FreeList == NULL )
    644 	{
    645 		newblk = (TokNode *)calloc(TokenBlockAllocSize, sizeof(TokNode));
    646 		if ( newblk == NULL )
    647 			fatal_internal(eMsg1("out of memory while building rule '%s'",CurRule));
    648 		for (p=newblk; p<&(newblk[TokenBlockAllocSize]); p++)
    649 		{
    650 			p->next = (Node *)FreeList;	/* add all new token nodes to FreeList */
    651 			FreeList = p;
    652 		}
    653 	}
    654 	p = FreeList;
    655 	FreeList = (TokNode *)FreeList->next;/* remove a TokNode node */
    656 	p->next = NULL;						/* NULL the ptr we used */
    657     memset( (char *) p, 0, sizeof(TokNode));        /* MR10 */
    658 	p->ntype = nToken;
    659 	p->rname = CurRule;
    660 	p->file = CurFile;
    661 	p->line = zzline;
    662 	p->altstart = NULL;
    663 
    664 	return p;
    665 }
    666 
    667 RuleRefNode *
    668 #ifdef __USE_PROTOS
    669 newRNode( void )
    670 #else
    671 newRNode( )
    672 #endif
    673 {
    674 	static RuleRefNode *FreeList = NULL;
    675 	RuleRefNode *p, *newblk;
    676 
    677 	if ( FreeList == NULL )
    678 	{
    679 		newblk = (RuleRefNode *)calloc(RRefBlockAllocSize, sizeof(RuleRefNode));
    680 		if ( newblk == NULL )
    681 			fatal_internal(eMsg1("out of memory while building rule '%s'",CurRule));
    682 		for (p=newblk; p<&(newblk[RRefBlockAllocSize]); p++)
    683 		{
    684 			p->next = (Node *)FreeList;	/* add all new rref nodes to FreeList */
    685 			FreeList = p;
    686 		}
    687 	}
    688 	p = FreeList;
    689 	FreeList = (RuleRefNode *)FreeList->next;/* remove a Junction node */
    690 	p->next = NULL;						/* NULL the ptr we used */
    691     memset( (char *) p, 0, sizeof(RuleRefNode));        /* MR10 */
    692 	p->ntype = nRuleRef;
    693 	p->rname = CurRule;
    694 	p->file = CurFile;
    695 	p->line = zzline;
    696 	p->astnode = ASTinclude;
    697 	p->altstart = NULL;
    698 
    699 	return p;
    700 }
    701 
    702 static int junctionSeqNumber=0;         /* MR10 */
    703 
    704 Junction *
    705 #ifdef __USE_PROTOS
    706 newJunction( void )
    707 #else
    708 newJunction( )
    709 #endif
    710 {
    711 	static Junction *FreeList = NULL;
    712 	Junction *p, *newblk;
    713 
    714 	if ( FreeList == NULL )
    715 	{
    716 		newblk = (Junction *)calloc(JunctionBlockAllocSize, sizeof(Junction));
    717 		if ( newblk == NULL )
    718 			fatal_internal(eMsg1("out of memory while building rule '%s'",CurRule));
    719 		for (p=newblk; p<&(newblk[JunctionBlockAllocSize]); p++)
    720 		{
    721 			p->p1 = (Node *)FreeList;	/* add all new Junction nodes to FreeList */
    722 			FreeList = p;
    723 		}
    724 	}
    725 	p = FreeList;
    726 	FreeList = (Junction *)FreeList->p1;/* remove a Junction node */
    727 	p->p1 = NULL;						/* NULL the ptr we used */
    728     memset( (char *) p, 0, sizeof(Junction));       /* MR10 */
    729 	p->ntype = nJunction;
    730 	p->visited = 0;
    731 	p->jtype = Generic;
    732 	p->rname = CurRule;
    733 	p->file = CurFile;
    734 	p->line = zzline;
    735 	p->exception_label = NULL;
    736 	p->fset = (set *) calloc(CLL_k+1, sizeof(set));
    737 	require(p->fset!=NULL, "cannot allocate fset in newJunction");
    738     p->seq=++junctionSeqNumber;     /* MR10 */
    739 
    740 	return p;
    741 }
    742 
    743 ActionNode *
    744 #ifdef __USE_PROTOS
    745 newActionNode( void )
    746 #else
    747 newActionNode( )
    748 #endif
    749 {
    750 	static ActionNode *FreeList = NULL;
    751 	ActionNode *p, *newblk;
    752 
    753 	if ( FreeList == NULL )
    754 	{
    755 		newblk = (ActionNode *)calloc(ActionBlockAllocSize, sizeof(ActionNode));
    756 		if ( newblk == NULL )
    757 			fatal_internal(eMsg1("out of memory while building rule '%s'",CurRule));
    758 		for (p=newblk; p<&(newblk[ActionBlockAllocSize]); p++)
    759 		{
    760 			p->next = (Node *)FreeList;	/* add all new Action nodes to FreeList */
    761 			FreeList = p;
    762 		}
    763 	}
    764 	p = FreeList;
    765 	FreeList = (ActionNode *)FreeList->next;/* remove an Action node */
    766     memset( (char *) p, 0, sizeof(ActionNode));     /* MR10 */
    767 	p->ntype = nAction;
    768 	p->next = NULL;						/* NULL the ptr we used */
    769 	p->done = 0;
    770 	p->pred_fail = NULL;
    771 	p->guardpred = NULL;
    772     p->ampersandPred = NULL;
    773 	return p;
    774 }
    775 
    776 /*
    777  * allocate the array of locks (1..CLL_k) used to inhibit infinite recursion.
    778  * Infinite recursion can occur in (..)* blocks, FIRST calcs and FOLLOW calcs.
    779  * Therefore, we need locks on aLoopBlk, RuleBlk, EndRule nodes.
    780  *
    781  * if ( lock[k]==TRUE ) then we have been here before looking for k tokens
    782  * of lookahead.
    783  */
    784 char *
    785 #ifdef __USE_PROTOS
    786 makelocks( void )
    787 #else
    788 makelocks( )
    789 #endif
    790 {
    791 	char *p = (char *) calloc(CLL_k+1, sizeof(char));
    792 	require(p!=NULL, "cannot allocate lock array");
    793 
    794 	return p;
    795 }
    796 
    797 #if 0
    798 ** #ifdef __USE_PROTOS
    799 ** void my_memset(char *p,char value,int count)
    800 ** #else
    801 ** void my_memset(p,value,count)
    802 **   char      *p;
    803 **   char      value;
    804 **   int       count;
    805 ** #endif
    806 ** {
    807 **    int      i;
    808 **
    809 **    for (i=0; i<count; i++) {
    810 **     p[i]=value;
    811 **   };
    812 ** }
    813 #endif
    814