1 /*
2  * fset2.c
3  *
4  * Compute FIRST sets for full LL(k)
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.33
27  * Terence Parr
28  * Parr Research Corporation
29  * with Purdue University and AHPCRC, University of Minnesota
30  * 1989-2001
31  */
32 
33 #include <stdio.h>
34 #include "pcctscfg.h"
35 #include <stdlib.h>
36 
37 #ifdef PCCTS_USE_STDARG
38 #include <stdarg.h>
39 #else
40 #include <varargs.h>
41 #endif
42 
43 #include "set.h"
44 #include "syn.h"
45 #include "hash.h"
46 #include "generic.h"
47 #include "dlgdef.h"
48 
49 /* ick! globals.  Used by permute() to track which elements of a set have been used */
50 
51 static int *findex;
52 set *fset;              /* MR11 make global */
53 static unsigned **ftbl;
54 static set *constrain; /* pts into fset. constrains tToken() to 'constrain' */
55 int ConstrainSearch;
56 int maxk;               /* set to initial k upon tree construction request */
57                         /* MR11 make global */
58 static Tree *FreeList = NULL;
59 
60 #ifdef __USE_PROTOS
61 static int tmember_of_context(Tree *, Predicate *);
62 #else
63 static int tmember_of_context();
64 #endif
65 
66 #if TREE_DEBUG
67 set     set_of_tnodes_in_use;
68 int     stop_on_tnode_seq_number=(-1);     /* (-1) to disable */
69 #endif
70 
71 /* Do root
72  * Then each sibling
73  */
74 
75 void
76 #ifdef __USE_PROTOS
preorder(Tree * tree)77 preorder( Tree *tree )
78 #else
79 preorder( tree )
80 Tree *tree;
81 #endif
82 {
83 	if ( tree == NULL ) return;
84 	if ( tree->down != NULL ) fprintf(stderr, " (");
85 	if ( tree->token == ALT ) fprintf(stderr, " ALT");
86 	else fprintf(stderr, " %s", TerminalString(tree->token));
87 	if ( tree->token==EpToken ) fprintf(stderr, "(%d)", tree->v.rk);
88 	preorder(tree->down);
89 	if ( tree->down != NULL ) fprintf(stderr, " )");
90 	preorder(tree->right);
91 }
92 
93 #ifdef __USE_PROTOS
MR_tree_matches_constraints(int k,set * constrain,Tree * t)94 int MR_tree_matches_constraints(int k,set * constrain,Tree *t)
95 #else
96 int MR_tree_matches_constraints(k,constrain,t)
97   int       k;
98   set *     constrain;
99   Tree *    t;
100 #endif
101 {
102   int       i;
103   Tree      *u;
104 
105   if (k == 0) return 1;
106 
107   /* for testing guard predicates: if the guard tree is shorter
108      than the constraint then it is a match.  The reason is that
109      a guard of (A B) should be equivalent to a guard of (A B . . .)
110      where "." matches every token.  Thus a match which runs out
111      of tree before constraint is a match.
112   */
113 
114   if (t == NULL) return 1;
115   require (set_deg(constrain[0]) == 1,
116             "MR_tree_matches_constraints: set_deg != 1");
117   i=set_int(constrain[0]);
118   if (t->token != i) return 0;
119   if (k-1 == 0) return 1;
120   for (u=t->down; u != NULL; u=u->right) {
121     if (MR_tree_matches_constraints(k-1,&constrain[1],u)) {
122        return 1;
123     };
124   };
125   return 0;
126 }
127 
128 /* check the depth of each primary sibling to see that it is exactly
129  * k deep. e.g.;
130  *
131  *	ALT
132  *   |
133  *   A ------- B
134  *   |         |
135  *   C -- D    E
136  *
137  * Remove all branches <= k deep.
138  *
139  * Added by TJP 9-23-92 to make the LL(k) constraint mechanism to work.
140  */
141 
142 static int pruneCount=0;
143 static int prunePeak=200;
144 
145 Tree *
146 #ifdef __USE_PROTOS
prune(Tree * t,int k)147 prune( Tree *t, int k )
148 #else
149 prune( t, k )
150 Tree *t;
151 int k;
152 #endif
153 {
154     pruneCount++;
155     if (pruneCount > prunePeak+100) {
156       prunePeak=pruneCount;
157 #if 0
158 ***   fprintf(stderr,"pruneCount=%d\n",pruneCount);
159 /***  preorder(t);   ***/
160 ***   fprintf(stderr,"\n",pruneCount);
161 #endif
162     };
163     if ( t == NULL ) {
164         pruneCount--;
165         return NULL;
166     };
167     if ( t->token == ALT ) fatal_internal("prune: ALT node in FIRST tree");
168     if ( t->right!=NULL ) t->right = prune(t->right, k);
169     if ( k>1 )
170 	{
171 		if ( t->down!=NULL ) t->down = prune(t->down, k-1);
172 		if ( t->down == NULL )
173 		{
174 			Tree *r = t->right;
175 			t->right = NULL;
176 			Tfree(t);
177             pruneCount--;
178 			return r;
179 		}
180 	}
181     pruneCount--;
182     return t;
183 }
184 
185 /* build a tree (root child1 child2 ... NULL) */
186 #ifdef PCCTS_USE_STDARG
tmake(Tree * root,...)187 Tree *tmake(Tree *root, ...)
188 #else
189 Tree *tmake(va_alist)
190 va_dcl
191 #endif
192 {
193 	Tree *w;
194 	va_list ap;
195 	Tree *child, *sibling=NULL, *tail=NULL;
196 #ifndef PCCTS_USE_STDARG
197 	Tree *root;
198 #endif
199 
200 #ifdef PCCTS_USE_STDARG
201 	va_start(ap, root);
202 #else
203 	va_start(ap);
204 	root = va_arg(ap, Tree *);
205 #endif
206 	child = va_arg(ap, Tree *);
207 	while ( child != NULL )
208 	{
209 #ifdef DUM
210 		/* added "find end of child" thing TJP March 1994 */
211 		for (w=child; w->right!=NULL; w=w->right) {;} /* find end of child */
212 #else
213 		w = child;
214 #endif
215 
216 		if ( sibling == NULL ) {sibling = child; tail = w;}
217 		else {tail->right = child; tail = w;}
218 		child = va_arg(ap, Tree *);
219 	}
220 
221 	/* was "root->down = sibling;" */
222 	if ( root==NULL ) root = sibling;
223 	else root->down = sibling;
224 
225 	va_end(ap);
226 	return root;
227 }
228 
229 Tree *
230 #ifdef __USE_PROTOS
tnode(int tok)231 tnode( int tok )
232 #else
233 tnode( tok )
234 int tok;
235 #endif
236 {
237 	Tree *p, *newblk;
238 	static int n=0;
239 
240 	if ( FreeList == NULL )
241 	{
242 		/*fprintf(stderr, "tnode: %d more nodes\n", TreeBlockAllocSize);*/
243 		if ( TreeResourceLimit > 0 )
244 		{
245 			if ( (n+TreeBlockAllocSize) >= TreeResourceLimit )
246 			{
247 				fprintf(stderr, ErrHdr, FileStr[CurAmbigfile], CurAmbigline);
248 				fprintf(stderr, " hit analysis resource limit while analyzing alts %d and %d %s\n",
249 								CurAmbigAlt1,
250 								CurAmbigAlt2,
251 								CurAmbigbtype);
252 				exit(PCCTS_EXIT_FAILURE);
253 			}
254 		}
255 		newblk = (Tree *)calloc(TreeBlockAllocSize, sizeof(Tree));
256 		if ( newblk == NULL )
257 		{
258 			fprintf(stderr, ErrHdr, FileStr[CurAmbigfile], CurAmbigline);
259 			fprintf(stderr, " out of memory while analyzing alts %d and %d %s\n",
260 							CurAmbigAlt1,
261 							CurAmbigAlt2,
262 							CurAmbigbtype);
263 			exit(PCCTS_EXIT_FAILURE);
264 		}
265 		n += TreeBlockAllocSize;
266 		for (p=newblk; p<&(newblk[TreeBlockAllocSize]); p++)
267 		{
268 			p->right = FreeList;	/* add all new Tree nodes to Free List */
269 			FreeList = p;
270 		}
271 	}
272 	p = FreeList;
273 	FreeList = FreeList->right;		/* remove a tree node */
274 	p->right = NULL;				/* zero out ptrs */
275 	p->down = NULL;
276 	p->token = tok;
277 
278     TnodesAllocated++;                                      /* MR10 */
279     TnodesInUse++;                                          /* MR10 */
280     if (TnodesInUse > TnodesPeak) TnodesPeak=TnodesInUse;   /* MR10 */
281 
282 #ifdef TREE_DEBUG
283 	require(!p->in_use, "tnode: node in use!");
284 	p->in_use = 1;
285     p->seq=TnodesAllocated;
286     set_orel( (unsigned) TnodesAllocated,&set_of_tnodes_in_use);
287     if (stop_on_tnode_seq_number == p->seq) {
288       fprintf(stderr,"\n*** just allocated tnode #%d ***\n",
289             stop_on_tnode_seq_number);
290     };
291 #endif
292 	return p;
293 }
294 
295 static Tree *
296 #ifdef __USE_PROTOS
eofnode(int k)297 eofnode( int k )
298 #else
299 eofnode( k )
300 int k;
301 #endif
302 {
303 	Tree *t=NULL;
304 	int i;
305 
306 	for (i=1; i<=k; i++)
307 	{
308 		t = tmake(tnode((TokenInd!=NULL?TokenInd[EofToken]:EofToken)), t, NULL);
309 	}
310 	return t;
311 }
312 
313 
314 
315 void
316 #ifdef __USE_PROTOS
_Tfree(Tree * t)317 _Tfree( Tree *t )
318 #else
319 _Tfree( t )
320 Tree *t;
321 #endif
322 {
323 	if ( t!=NULL )
324 	{
325 #ifdef TREE_DEBUG
326         if (t->seq == stop_on_tnode_seq_number) {
327            fprintf(stderr,"\n*** just freed tnode #%d ***\n",t->seq);
328         };
329 		require(t->in_use, "_Tfree: node not in use!");
330 		t->in_use = 0;
331         set_rm( (unsigned) t->seq,set_of_tnodes_in_use);
332 #endif
333 		t->right = FreeList;
334 		FreeList = t;
335         TnodesInUse--;                   /* MR10 */
336 	}
337 }
338 
339 /* tree duplicate */
340 Tree *
341 #ifdef __USE_PROTOS
tdup(Tree * t)342 tdup( Tree *t )
343 #else
344 tdup( t )
345 Tree *t;
346 #endif
347 {
348 	Tree *u;
349 
350 	if ( t == NULL ) return NULL;
351 	u = tnode(t->token);
352 	u->v.rk = t->v.rk;
353 	u->right = tdup(t->right);
354 	u->down = tdup(t->down);
355 	return u;
356 }
357 
358 /* tree duplicate (assume tree is a chain downwards) */
359 Tree *
360 #ifdef __USE_PROTOS
tdup_chain(Tree * t)361 tdup_chain( Tree *t )
362 #else
363 tdup_chain( t )
364 Tree *t;
365 #endif
366 {
367 	Tree *u;
368 
369 	if ( t == NULL ) return NULL;
370 	u = tnode(t->token);
371 	u->v.rk = t->v.rk;
372 	u->down = tdup(t->down);
373 	return u;
374 }
375 
376 Tree *
377 #ifdef __USE_PROTOS
tappend(Tree * t,Tree * u)378 tappend( Tree *t, Tree *u )
379 #else
380 tappend( t, u )
381 Tree *t;
382 Tree *u;
383 #endif
384 {
385 	Tree *w;
386 
387 /*** fprintf(stderr, "tappend(");
388  *** preorder(t); fprintf(stderr, ",");
389  *** preorder(u); fprintf(stderr, " )\n");
390 */
391 	if ( t == NULL ) return u;
392 	if ( t->token == ALT && t->right == NULL ) return tappend(t->down, u);
393 	for (w=t; w->right!=NULL; w=w->right) {;}
394 	w->right = u;
395 	return t;
396 }
397 
398 /* dealloc all nodes in a tree */
399 void
400 #ifdef __USE_PROTOS
Tfree(Tree * t)401 Tfree( Tree *t )
402 #else
403 Tfree( t )
404 Tree *t;
405 #endif
406 {
407 	if ( t == NULL ) return;
408 	Tfree( t->down );
409 	Tfree( t->right );
410 	_Tfree( t );
411 }
412 
413 /* find all children (alts) of t that require remaining_k nodes to be LL_k
414  * tokens long.
415  *
416  * t-->o
417  *     |
418  *     a1--a2--...--an		<-- LL(1) tokens
419  *     |   |        |
420  *     b1  b2  ...  bn		<-- LL(2) tokens
421  *     |   |        |
422  *     .   .        .
423  *     .   .        .
424  *     z1  z2  ...  zn		<-- LL(LL_k) tokens
425  *
426  * We look for all [Ep] needing remaining_k nodes and replace with u.
427  * u is not destroyed or actually used by the tree (a copy is made).
428  */
429 Tree *
430 #ifdef __USE_PROTOS
tlink(Tree * t,Tree * u,int remaining_k)431 tlink( Tree *t, Tree *u, int remaining_k )
432 #else
433 tlink( t, u, remaining_k )
434 Tree *t;
435 Tree *u;
436 int remaining_k;
437 #endif
438 {
439 	Tree *p;
440 	require(remaining_k!=0, "tlink: bad tree");
441 
442 	if ( t==NULL ) return NULL;
443 	/*fprintf(stderr, "tlink: u is:"); preorder(u); fprintf(stderr, "\n");*/
444 	if ( t->token == EpToken && t->v.rk == remaining_k )
445 	{
446 		require(t->down==NULL, "tlink: invalid tree");
447 		if ( u == NULL ) {
448 /* MR10 */  Tree  *tt=t->right;
449 /* MR10 */  _Tfree(t);
450 /* MR10 */  return tt;
451         };
452 		p = tdup( u );
453 		p->right = t->right;
454 		_Tfree( t );
455 		return p;
456 	}
457 	t->down = tlink(t->down, u, remaining_k);
458 	t->right = tlink(t->right, u, remaining_k);
459 	return t;
460 }
461 
462 /* remove as many ALT nodes as possible while still maintaining semantics */
463 Tree *
464 #ifdef __USE_PROTOS
tshrink(Tree * t)465 tshrink( Tree *t )
466 #else
467 tshrink( t )
468 Tree *t;
469 #endif
470 {
471 	if ( t == NULL ) return NULL;
472 	t->down = tshrink( t->down );
473 	t->right = tshrink( t->right );
474 	if ( t->down == NULL )
475 	{
476 		if ( t->token == ALT )
477 		{
478 			Tree *u = t->right;
479 			_Tfree(t);
480 			return u;			/* remove useless alts */
481 		}
482 		return t;
483 	}
484 
485 	/* (? (ALT (? ...)) s) ==> (? (? ...) s) where s = sibling, ? = match any */
486 	if ( t->token == ALT && t->down->right == NULL)
487 	{
488 		Tree *u = t->down;
489 		u->right = t->right;
490 		_Tfree( t );
491 		return u;
492 	}
493 	/* (? (A (ALT t)) s) ==> (? (A t) s) where A is a token; s,t siblings */
494 	if ( t->token != ALT && t->down->token == ALT && t->down->right == NULL )
495 	{
496 		Tree *u = t->down->down;
497 		_Tfree( t->down );
498 		t->down = u;
499 		return t;
500 	}
501 	return t;
502 }
503 
504 Tree *
505 #ifdef __USE_PROTOS
tflatten(Tree * t)506 tflatten( Tree *t )
507 #else
508 tflatten( t )
509 Tree *t;
510 #endif
511 {
512 	if ( t == NULL ) return NULL;
513 	t->down = tflatten( t->down );
514 	t->right = tflatten( t->right );
515 	if ( t->down == NULL ) return t;
516 
517 	if ( t->token == ALT )
518 	{
519 		Tree *u;
520 		/* find tail of children */
521 		for (u=t->down; u->right!=NULL; u=u->right) {;}
522 		u->right = t->right;
523 		u = t->down;
524 		_Tfree( t );
525 		return u;
526 	}
527 	return t;
528 }
529 
530 Tree *
531 #ifdef __USE_PROTOS
tJunc(Junction * p,int k,set * rk)532 tJunc( Junction *p, int k, set *rk )
533 #else
534 tJunc( p, k, rk )
535 Junction *p;
536 int k;
537 set *rk;
538 #endif
539 {
540 	Tree *t=NULL, *u=NULL;
541 	Junction *alt;
542 	Tree *tail=NULL, *r;
543 
544 #ifdef DBG_TRAV
545 	fprintf(stderr, "tJunc(%d): %s in rule %s\n", k,
546 			decodeJType[p->jtype], ((Junction *)p)->rname);
547 #endif
548 
549 /* MR14 */    if (AlphaBetaTrace && p->alpha_beta_guess_end) {
550 /* MR14 */         warnFL(
551 /* MR14 */           "not possible to compute follow set for alpha in an \"(alpha)? beta\" block.  ",
552 /* MR14 */                 FileStr[p->file],p->line);
553 /* MR14 */         MR_alphaBetaTraceReport();
554 /* MR14 */    };
555 
556 /* MR14 */    if (p->alpha_beta_guess_end) {
557 /* MR14 */      return NULL;
558 /* MR14 */    }
559 
560 	if ( p->jtype==aLoopBlk || p->jtype==RuleBlk ||
561 		 p->jtype==aPlusBlk || p->jtype==aSubBlk || p->jtype==aOptBlk )
562 	{
563 		if ( p->jtype!=aSubBlk && p->jtype!=aOptBlk ) {
564 			require(p->lock!=NULL, "rJunc: lock array is NULL");
565 			if ( p->lock[k] ) return NULL;
566 			p->lock[k] = TRUE;
567 		}
568 
569 /* MR10 */    if (MR_MaintainBackTrace) {
570 /* MR10 */      if (p->jtype != Generic) MR_pointerStackPush(&MR_BackTraceStack,p);
571 /* MR10 */    };
572 
573 		TRAV(p->p1, k, rk, tail);
574 
575 /* MR10 */    if (MR_MaintainBackTrace) {
576 /* MR10 */      if (p->jtype != Generic) MR_pointerStackPop(&MR_BackTraceStack);
577 /* MR10 */    };
578 
579 		if ( p->jtype==RuleBlk ) {p->lock[k] = FALSE; return tail;}
580 		r = tmake(tnode(ALT), tail, NULL);
581 		for (alt=(Junction *)p->p2; alt!=NULL; alt = (Junction *)alt->p2)
582 		{
583 			/* if this is one of the added optional alts for (...)+ then break */
584 			if ( alt->ignore ) break;
585 
586 			if ( tail==NULL ) {TRAV(alt->p1, k, rk, tail); r->down = tail;}
587 			else
588 			{
589 /* MR10 */    if (MR_MaintainBackTrace) {
590 /* MR10 */      if (p->jtype != Generic) MR_pointerStackPush(&MR_BackTraceStack,p);
591 /* MR10 */    };
592 
593 				TRAV(alt->p1, k, rk, tail->right);
594 
595 /* MR10 */    if (MR_MaintainBackTrace) {
596 /* MR10 */      if (p->jtype != Generic) MR_pointerStackPop(&MR_BackTraceStack);
597 /* MR10 */    };
598 				if ( tail->right != NULL ) tail = tail->right;
599 			}
600 		}
601 		if ( p->jtype!=aSubBlk && p->jtype!=aOptBlk ) p->lock[k] = FALSE;
602 #ifdef DBG_TREES
603 		fprintf(stderr, "blk(%s) returns:",((Junction *)p)->rname); preorder(r); fprintf(stderr, "\n");
604 #endif
605 		if ( r->down == NULL ) {_Tfree(r); return NULL;}
606 		return r;
607 	}
608 
609 	if ( p->jtype==EndRule )
610 	{
611 		if ( p->halt )						/* don't want FOLLOW here? */
612 		{
613 /****		if ( ContextGuardTRAV ) return NULL; ****/
614 			set_orel( (unsigned) k, rk);	/* indicate this k value needed */ /* MR10 cast */
615 			t = tnode(EpToken);
616 			t->v.rk = k;
617 			return t;
618 		}
619 		require(p->lock!=NULL, "rJunc: lock array is NULL");
620 		if ( p->lock[k] ) return NULL;
621 		/* if no FOLLOW assume k EOF's */
622 		if ( p->p1 == NULL ) return eofnode(k);
623 		p->lock[k] = TRUE;
624 	}
625 
626 /* MR14 */	if (p->p1 != NULL && p->guess &&  p->guess_analysis_point == NULL) {
627 /* MR14 */    Node * guess_point;
628 /* MR14 */    guess_point=(Node *)analysis_point(p);
629 /* MR14 */    if (guess_point == (Node *)p) {
630 /* MR14 */      guess_point=p->p1;
631 /* MR14 */    }
632 /* MR14 */    p->guess_analysis_point=guess_point;
633 /* MR14 */  }
634 
635 	if ( p->p2 == NULL )
636 	{
637 
638 /* MR10 */    if (MR_MaintainBackTrace) {
639 /* MR10 */      if (p->jtype != Generic) MR_pointerStackPush(&MR_BackTraceStack,p);
640 /* MR10 */    };
641 
642 /* M14 */        if (p->guess_analysis_point != NULL) {
643 /* M14 */ 		   TRAV(p->guess_analysis_point, k, rk,t);
644 /* M14 */        } else {
645         		   TRAV(p->p1, k, rk,t);
646 /* M14 */        }
647 
648 /* MR10 */    if (MR_MaintainBackTrace) {
649 /* MR10 */      if (p->jtype != Generic) MR_pointerStackPop(&MR_BackTraceStack);
650 /* MR10 */    };
651 
652 		if ( p->jtype==EndRule ) p->lock[k]=FALSE;
653 		return t;
654 	}
655 
656 /* MR10 */    if (MR_MaintainBackTrace) {
657 /* MR10 */      if (p->jtype != Generic) MR_pointerStackPush(&MR_BackTraceStack,p);
658 /* MR10 */    };
659 
660 /* M14 */        if (p->guess_analysis_point != NULL) {
661 /* M14 */ 		   TRAV(p->guess_analysis_point, k, rk,t);
662 /* M14 */        } else {
663         		   TRAV(p->p1, k, rk,t);
664 /* M14 */        }
665 
666 /* MR10 */    if (MR_MaintainBackTrace) {
667 /* MR10 */      if (p->jtype != Generic) MR_pointerStackPop(&MR_BackTraceStack);
668 /* MR10 */    };
669 
670 	if ( p->jtype!=RuleBlk && /* MR14 */ !p->guess) TRAV(p->p2, k, rk, u);
671 
672 	if ( p->jtype==EndRule ) p->lock[k] = FALSE;/* unlock node */
673 
674 	if ( t==NULL ) return tmake(tnode(ALT), u, NULL);
675 	return tmake(tnode(ALT), t, u, NULL);
676 }
677 
678 Tree *
679 #ifdef __USE_PROTOS
tRuleRef(RuleRefNode * p,int k,set * rk_out)680 tRuleRef( RuleRefNode *p, int k, set *rk_out )
681 #else
682 tRuleRef( p, k, rk_out )
683 RuleRefNode *p;
684 int k;
685 set *rk_out;
686 #endif
687 {
688 	int k2;
689 	Tree *t=NULL, *u=NULL;
690 	Junction *r;
691 	set rk, rk2;
692 	int save_halt;
693 	RuleEntry *q = (RuleEntry *) hash_get(Rname, p->text);
694 
695 #ifdef DBG_TRAV
696 	fprintf(stderr, "tRuleRef: %s\n", p->text);
697 #endif
698 	if ( q == NULL )
699 	{
700 		TRAV(p->next, k, rk_out, t);/* ignore undefined rules */
701 		return t;
702 	}
703 	rk = rk2 = empty;
704     if (RulePtr == NULL) fatal("RulePtr==NULL");
705 	r = RulePtr[q->rulenum];
706 	if ( r->lock[k] ) return NULL;
707 	save_halt = r->end->halt;
708 	r->end->halt = TRUE;		/* don't let reach fall off end of rule here */
709 
710 /* MR10 */    if (MR_MaintainBackTrace) {
711 /* MR10 */      MR_pointerStackPush(&MR_BackTraceStack,p);
712 /* MR10 */    };
713 
714 	TRAV(r, k, &rk, t);
715 
716 /* MR10 */    if (MR_MaintainBackTrace) {
717 /* MR10 */      MR_pointerStackPop(&MR_BackTraceStack);
718 /* MR10 */    };
719 
720 	r->end->halt = save_halt;
721 #ifdef DBG_TREES
722 	fprintf(stderr, "after ruleref, t is:"); preorder(t); fprintf(stderr, "\n");
723 #endif
724 	t = tshrink( t );
725 	while ( !set_nil(rk) ) {	/* any k left to do? if so, link onto tree */
726 		k2 = set_int(rk);
727 		set_rm(k2, rk);
728 
729 /* MR10 */    if (MR_MaintainBackTrace) {
730 /* MR10 */      MR_pointerStackPush(&MR_BackTraceStack,p);
731 /* MR10 */    };
732 
733 		TRAV(p->next, k2, &rk2, u);
734 
735 /* MR10 */    if (MR_MaintainBackTrace) {
736 /* MR10 */      MR_pointerStackPop(&MR_BackTraceStack);
737 /* MR10 */    };
738 
739 		t = tlink(t, u, k2);	/* any alts missing k2 toks, add u onto end */
740         Tfree(u);               /* MR10 */
741 	}
742 	set_free(rk);				/* rk is empty, but free it's memory */
743 	set_orin(rk_out, rk2);		/* remember what we couldn't do */
744 	set_free(rk2);
745 	return t;
746 }
747 
748 Tree *
749 #ifdef __USE_PROTOS
tToken(TokNode * p,int k,set * rk)750 tToken( TokNode *p, int k, set *rk )
751 #else
752 tToken( p, k, rk )
753 TokNode *p;
754 int k;
755 set *rk;
756 #endif
757 {
758 	Tree *t=NULL, *tset=NULL, *u;
759 
760 	if (ConstrainSearch) {
761       if (MR_AmbSourceSearch) {
762 		require(constrain>=fset&&constrain<=&(fset[CLL_k]),"tToken: constrain is not a valid set");
763       } else {
764 		require(constrain>=fset&&constrain<=&(fset[LL_k]),"tToken: constrain is not a valid set");
765       };
766       constrain = &fset[maxk-k+1];
767 	}
768 
769 #ifdef DBG_TRAV
770         	fprintf(stderr, "tToken(%d): %s\n", k, TerminalString(p->token));
771         	if ( ConstrainSearch ) {
772         		fprintf(stderr, "constrain is:"); s_fprT(stderr, *constrain); fprintf(stderr, "\n");
773         	}
774 #endif
775 
776 	/* is it a meta token (set of tokens)? */
777 
778 	if ( !set_nil(p->tset) )
779 	{
780 		unsigned e=0;
781 		set a;
782 		Tree *n, *tail = NULL;
783 
784 		if ( ConstrainSearch ) {
785           a = set_and(p->tset, *constrain);
786           if (set_nil(a)) {         /* MR10 */
787             set_free(a);            /* MR11 */
788             return NULL;            /* MR10 */
789           };                        /* MR10 */
790 		} else {
791           a = set_dup(p->tset);
792         };
793 
794 		for (; !set_nil(a); set_rm(e, a))
795 		{
796 			e = set_int(a);
797 			n = tnode(e);
798 			if ( tset==NULL ) { tset = n; tail = n; }
799 			else { tail->right = n; tail = n; }
800 		}
801 		set_free( a );
802 	}
803 	else if ( ConstrainSearch && !set_el(p->token, *constrain) )
804     {
805 /*      fprintf(stderr, "ignoring token %s(%d)\n", TerminalString(p->token),
806                 k);*/
807         return NULL;
808     }
809 	else {
810         tset = tnode( p->token );
811     };
812 
813 /* MR10 */    if (MR_MaintainBackTrace) {
814 /* MR10 */      if (k == 1) {
815 /* MR10 */        MR_pointerStackPush(&MR_BackTraceStack,p);
816 /* MR13 */        if (MR_SuppressSearch) {
817 /* MR13 */          MR_suppressSearchReport();
818 /* MR13 */        } else {
819 /* MR10 */          MR_backTraceReport();
820 /* MR13 */        };
821 /* MR10 */        MR_pointerStackPop(&MR_BackTraceStack);
822 /* MR11 */        Tfree(tset);
823 /* MR11 */        return NULL;
824 /* MR10 */      };
825 /* MR10 */    };
826 
827 	if ( k == 1 ) return tset;
828 
829     if (MR_MaintainBackTrace) {
830       MR_pointerStackPush(&MR_BackTraceStack,p);
831     };
832 
833 	TRAV(p->next, k-1, rk, t);
834 
835     if (MR_MaintainBackTrace) {
836       Tfree(t);
837       Tfree(tset);
838       MR_pointerStackPop(&MR_BackTraceStack);
839       return NULL;
840     };
841 
842 	/* here, we are positive that, at least, this tree will not contribute
843 	 * to the LL(2) tree since it will be too shallow, IF t==NULL.
844 	 * If doing a context guard walk, then don't prune.
845 	 */
846 	if ( t == NULL && !ContextGuardTRAV )	/* tree will be too shallow */
847 	{
848 		if ( tset!=NULL ) Tfree( tset );
849 		return NULL;
850 	}
851 #ifdef DBG_TREES
852 	fprintf(stderr, "tToken(%d)->next:",k); preorder(t); fprintf(stderr, "\n");
853 #endif
854 
855 	/* if single token root, then just make new tree and return */
856     /* MR10 - set_nil(p->tset) isn't a good test because of ConstraintSearch */
857 
858 	if (tset->right == NULL) return tmake(tset, t, NULL);    /* MR10 */
859 
860 	/* here we must make a copy of t as a child of each element of the tset;
861 	 * e.g., "T1..T3 A" would yield ( nil ( T1 A ) ( T2 A ) ( T3 A ) )
862 	 */
863 	for (u=tset; u!=NULL; u=u->right)
864 	{
865 		/* make a copy of t and hook it onto bottom of u */
866 		u->down = tdup(t);
867 	}
868 	Tfree( t );
869 #ifdef DBG_TREES
870 	fprintf(stderr, "range is:"); preorder(tset); fprintf(stderr, "\n");
871 #endif
872 	return tset;
873 }
874 
875 Tree *
876 #ifdef __USE_PROTOS
tAction(ActionNode * p,int k,set * rk)877 tAction( ActionNode *p, int k, set *rk )
878 #else
879 tAction( p, k, rk )
880 ActionNode *p;
881 int k;
882 set *rk;
883 #endif
884 {
885 	Tree        *t=NULL;
886     set         *save_fset=NULL;
887     int         i;
888 
889 	/* fprintf(stderr, "tAction\n"); */
890 
891 /*  An MR_SuppressSearch is looking for things that can be
892       reached even when the predicate is false.
893 
894     There are three kinds of predicates:
895         plain:              r1: <<p>>? r2
896         guarded:            r1: (A)? => <<p>>? r2
897         ampersand style:    r1: (A)? && <<p>>? r2
898 
899     Of the three kinds of predicates, only a guard predicate
900       has things which are reachable even when the predicate
901       is false.  To be reachable the constraint must *not*
902       match the guard.
903 
904 */
905 
906     if (p->is_predicate && MR_SuppressSearch) {
907 
908       Predicate     *pred=p->guardpred;
909 
910       if (pred == NULL) {
911         t=NULL;
912         goto EXIT;
913       };
914       constrain = &fset[maxk-k+1];
915       if (pred->k == 1) {
916         set     dif;
917         dif=set_dif(*constrain,pred->scontext[1]);
918         if (set_nil(dif)) {
919           set_free(dif);
920           t=NULL;
921           goto EXIT;
922         };
923         set_free(dif);
924       } else {
925         if (MR_tree_matches_constraints(k,constrain,pred->tcontext)) {
926           t=NULL;
927           goto EXIT;
928         };
929       }
930     };
931 
932     /* The ampersand predicate differs from the
933          other predicates because its first set
934          is a subset of the first set behind the predicate
935 
936             r1: (A)? && <<p>>? r2 ;
937             r2: A | B;
938 
939        In this case first[1] of r1 is A, even
940          though first[1] of r2 is {A B}.
941     */
942 
943     if (p->is_predicate && p->ampersandPred != NULL) {
944 
945       Predicate     *pred=p->ampersandPred;
946       Tree          *tAND;
947       Tree          *tset;
948 
949       if (k <= pred->k) {
950         if (MR_MaintainBackTrace) MR_pointerStackPush(&MR_BackTraceStack,p);
951         TRAV(p->guardNodes,k,rk,t);
952         if (MR_MaintainBackTrace) MR_pointerStackPop(&MR_BackTraceStack);
953         return t;
954       } else {
955         require (k>1,"tAction for ampersandpred: k <= 1");
956         if (ConstrainSearch) {
957           if (MR_AmbSourceSearch) {
958     		require(constrain>=fset&&constrain<=&(fset[CLL_k]),
959                                 "tToken: constrain is not a valid set");
960           } else {
961     		require(constrain>=fset&&constrain<=&(fset[LL_k]),
962                                 "tToken: constrain is not a valid set");
963           };
964           save_fset=(set *) calloc (CLL_k+1,sizeof(set));
965           require (save_fset != NULL,"tAction save_fset alloc");
966           for (i=1; i <= CLL_k ; i++) {
967             save_fset[i]=set_dup(fset[i]);
968           };
969           if (pred->k == 1) {
970             constrain = &fset[maxk-k+1];
971             set_andin(constrain,pred->scontext[1]);
972             if (set_nil(*constrain)) {
973               t=NULL;
974               goto EXIT;
975             };
976           } else {
977             constrain = &fset[maxk-k+1];
978             if (! MR_tree_matches_constraints(pred->k,constrain,pred->tcontext)) {
979                t=NULL;
980                goto EXIT;
981             };  /* end loop on i          */
982           }; /* end loop on pred scontext/tcontext */
983         }; /* end if on k > pred->k     */
984       }; /* end if on constrain search  */
985 
986       TRAV(p->next,k,rk,t);
987 
988       if (t != NULL) {
989         t=tshrink(t);
990         t=tflatten(t);
991         t=tleft_factor(t);
992         if (pred->tcontext != NULL) {
993           tAND=MR_computeTreeAND(t,pred->tcontext);
994         } else {
995           tset=MR_make_tree_from_set(pred->scontext[1]);
996           tAND=MR_computeTreeAND(t,tset);
997           Tfree(tset);
998         };
999         Tfree(t);
1000         t=tAND;
1001       };
1002       goto EXIT;
1003 
1004     }; /* end if on ampersand predicate */
1005 
1006     TRAV(p->next,k,rk,t);
1007 
1008 EXIT:
1009     if (save_fset != NULL) {
1010       for (i=1 ; i <= CLL_k ; i++) {
1011         set_free(fset[i]);
1012         fset[i]=save_fset[i];
1013       };
1014       free ( (char *) save_fset);
1015     };
1016 	return t;
1017 }
1018 
1019 /* see if e exists in s as a possible input permutation (e is always a chain) */
1020 
1021 int
1022 #ifdef __USE_PROTOS
tmember(Tree * e,Tree * s)1023 tmember( Tree *e, Tree *s )
1024 #else
1025 tmember( e, s )
1026 Tree *e;
1027 Tree *s;
1028 #endif
1029 {
1030 	if ( e==NULL||s==NULL ) return 0;
1031 /** fprintf(stderr, "tmember(");
1032 ***	preorder(e); fprintf(stderr, ",");
1033 ***	preorder(s); fprintf(stderr, " )\n");
1034 */
1035 	if ( s->token == ALT && s->right == NULL ) return tmember(e, s->down);
1036 	if ( e->token!=s->token )
1037 	{
1038 		if ( s->right==NULL ) return 0;
1039 		return tmember(e, s->right);
1040 	}
1041 	if ( e->down==NULL && s->down == NULL ) return 1;
1042 	if ( tmember(e->down, s->down) ) return 1;
1043 	if ( s->right==NULL ) return 0;
1044 	return tmember(e, s->right);
1045 }
1046 
1047 /* see if e exists in s as a possible input permutation (e is always a chain);
1048  * Only check s to the depth of e.  In other words, 'e' can be a shorter
1049  * sequence than s.
1050  */
1051 int
1052 #ifdef __USE_PROTOS
tmember_constrained(Tree * e,Tree * s)1053 tmember_constrained( Tree *e, Tree *s)
1054 #else
1055 tmember_constrained( e, s )
1056 Tree *e;
1057 Tree *s;
1058 #endif
1059 {
1060 	if ( e==NULL||s==NULL ) return 0;
1061 /**	fprintf(stderr, "tmember_constrained(");
1062 ***	preorder(e); fprintf(stderr, ",");
1063 ***	preorder(s); fprintf(stderr, " )\n");
1064 **/
1065 	if ( s->token == ALT && s->right == NULL )
1066 		return tmember_constrained(e, s->down);
1067 	if ( e->token!=s->token )
1068 	{
1069 		if ( s->right==NULL ) return 0;
1070 		return tmember_constrained(e, s->right);
1071 	}
1072 	if ( e->down == NULL ) return 1; /* if s is matched to depth of e return */
1073 	if ( tmember_constrained(e->down, s->down) ) return 1;
1074 	if ( s->right==NULL ) return 0;
1075 	return tmember_constrained(e, s->right);
1076 }
1077 
1078 /* combine (? (A t) ... (A u) ...) into (? (A t u)) */
1079 Tree *
1080 #ifdef __USE_PROTOS
tleft_factor(Tree * t)1081 tleft_factor( Tree *t )
1082 #else
1083 tleft_factor( t )
1084 Tree *t;
1085 #endif
1086 {
1087 	Tree *u, *v, *trail, *w;
1088 
1089 	/* left-factor what is at this level */
1090 	if ( t == NULL ) return NULL;
1091 	for (u=t; u!=NULL; u=u->right)
1092 	{
1093 		trail = u;
1094 		v=u->right;
1095 		while ( v!=NULL )
1096 		{
1097 			if ( u->token == v->token )
1098 			{
1099 				if ( u->down!=NULL )
1100 				{
1101 					for (w=u->down; w->right!=NULL; w=w->right) {;}
1102 					w->right = v->down;	/* link children together */
1103 				}
1104 				else u->down = v->down;
1105 				trail->right = v->right;		/* unlink factored node */
1106 				_Tfree( v );
1107 				v = trail->right;
1108 			}
1109 			else {trail = v; v=v->right;}
1110 		}
1111 	}
1112 	/* left-factor what is below */
1113 	for (u=t; u!=NULL; u=u->right) u->down = tleft_factor( u->down );
1114 	return t;
1115 }
1116 
1117 /* remove the permutation p from t if present */
1118 Tree *
1119 #ifdef __USE_PROTOS
trm_perm(Tree * t,Tree * p)1120 trm_perm( Tree *t, Tree *p )
1121 #else
1122 trm_perm( t, p )
1123 Tree *t;
1124 Tree *p;
1125 #endif
1126 {
1127 	/*
1128 	fprintf(stderr, "trm_perm(");
1129 	preorder(t); fprintf(stderr, ",");
1130 	preorder(p); fprintf(stderr, " )\n");
1131 	*/
1132 	if ( t == NULL || p == NULL ) return NULL;
1133 	if ( t->token == ALT )
1134 	{
1135 		t->down = trm_perm(t->down, p);
1136 		if ( t->down == NULL ) 				/* nothing left below, rm cur node */
1137 		{
1138 			Tree *u = t->right;
1139 			_Tfree( t );
1140 			return trm_perm(u, p);
1141 		}
1142 		t->right = trm_perm(t->right, p);	/* look for more instances of p */
1143 		return t;
1144 	}
1145 	if ( p->token != t->token )				/* not found, try a sibling */
1146 	{
1147 		t->right = trm_perm(t->right, p);
1148 		return t;
1149 	}
1150 	t->down = trm_perm(t->down, p->down);
1151 	if ( t->down == NULL ) 					/* nothing left below, rm cur node */
1152 	{
1153 		Tree *u = t->right;
1154 		_Tfree( t );
1155 		return trm_perm(u, p);
1156 	}
1157 	t->right = trm_perm(t->right, p);		/* look for more instances of p */
1158 	return t;
1159 }
1160 
1161 /* add the permutation 'perm' to the LL_k sets in 'fset' */
1162 void
1163 #ifdef __USE_PROTOS
tcvt(set * fset,Tree * perm)1164 tcvt( set *fset, Tree *perm )
1165 #else
1166 tcvt( fset, perm )
1167 set *fset;
1168 Tree *perm;
1169 #endif
1170 {
1171 	if ( perm==NULL ) return;
1172 	set_orel(perm->token, fset);
1173 	tcvt(fset+1, perm->down);
1174 }
1175 
1176 /* for each element of ftbl[k], make it the root of a tree with permute(ftbl[k+1])
1177  * as a child.
1178  */
1179 Tree *
1180 #ifdef __USE_PROTOS
permute(int k,int max_k)1181 permute( int k, int max_k )
1182 #else
1183 permute( k, max_k )
1184 int k, max_k;
1185 #endif
1186 {
1187 	Tree *t, *u;
1188 
1189 	if ( k>max_k ) return NULL;
1190 	if ( ftbl[k][findex[k]] == nil ) return NULL;
1191 	t = permute(k+1, max_k);
1192 	if ( t==NULL&&k<max_k )		/* no permutation left below for k+1 tokens? */
1193 	{
1194 		findex[k+1] = 0;
1195 		(findex[k])++;			/* try next token at this k */
1196 		return permute(k, max_k);
1197 	}
1198 
1199 	u = tmake(tnode(ftbl[k][findex[k]]), t, NULL);
1200 	if ( k == max_k ) (findex[k])++;
1201 	return u;
1202 }
1203 
1204 /* Compute LL(k) trees for alts alt1 and alt2 of p.
1205  * function result is tree of ambiguous input permutations
1206  *
1207  * ALGORITHM may change to look for something other than LL_k size
1208  * trees ==> maxk will have to change.
1209  */
1210 Tree *
1211 #ifdef __USE_PROTOS
VerifyAmbig(Junction * alt1,Junction * alt2,unsigned ** ft,set * fs,Tree ** t,Tree ** u,int * numAmbig)1212 VerifyAmbig( Junction *alt1, Junction *alt2, unsigned **ft, set *fs, Tree **t, Tree **u, int *numAmbig )
1213 #else
1214 VerifyAmbig( alt1, alt2, ft, fs, t, u, numAmbig )
1215 Junction *alt1;
1216 Junction *alt2;
1217 unsigned **ft;
1218 set *fs;
1219 Tree **t;
1220 Tree **u;
1221 int *numAmbig;
1222 #endif
1223 {
1224 	set rk;
1225 	Tree *perm, *ambig=NULL;
1226 	Junction *p;
1227 	int k;
1228     int    tnodes_at_start=TnodesAllocated;
1229     int    tnodes_at_end;
1230     int    tnodes_used;
1231     set    *save_fs;
1232     int    j;
1233 
1234     save_fs=(set *) calloc(CLL_k+1,sizeof(set));
1235     require(save_fs != NULL,"save_fs calloc");
1236 
1237     for (j=0; j <= CLL_k ; j++) save_fs[j]=set_dup(fs[j]);
1238 
1239 	maxk = LL_k;				/* NOTE: for now, we look for LL_k */
1240 	ftbl = ft;
1241 	fset = fs;
1242 	constrain = &(fset[1]);
1243 	findex = (int *) calloc(LL_k+1, sizeof(int));
1244 	if ( findex == NULL )
1245 	{
1246 		fprintf(stderr, ErrHdr, FileStr[CurAmbigfile], CurAmbigline);
1247 		fprintf(stderr, " out of memory while analyzing alts %d and %d of %s\n",
1248 						CurAmbigAlt1,
1249 						CurAmbigAlt2,
1250 						CurAmbigbtype);
1251 		exit(PCCTS_EXIT_FAILURE);
1252 	}
1253 	for (k=1; k<=LL_k; k++) findex[k] = 0;
1254 
1255 	rk = empty;
1256 	ConstrainSearch = 1;	/* consider only tokens in ambig sets */
1257 
1258 	p = analysis_point((Junction *)alt1->p1);
1259 	TRAV(p, LL_k, &rk, *t);
1260 	*t = tshrink( *t );
1261 	*t = tflatten( *t );
1262 	*t = tleft_factor( *t );    /* MR10 */
1263 	*t = prune(*t, LL_k);
1264 	*t = tleft_factor( *t );
1265 
1266 /***	fprintf(stderr, "after shrink&flatten&prune&left_factor:"); preorder(*t); fprintf(stderr, "\n");*/
1267 	if ( *t == NULL )
1268 	{
1269 /***	fprintf(stderr, "TreeIncomplete --> no LL(%d) ambiguity\n", LL_k);*/
1270 		Tfree( *t );	/* kill if impossible to have ambig */
1271 		*t = NULL;
1272 	}
1273 
1274 	p = analysis_point((Junction *)alt2->p1);
1275 
1276 	TRAV(p, LL_k, &rk, *u);
1277 	*u = tshrink( *u );
1278 	*u = tflatten( *u );
1279 	*t = tleft_factor( *t );    /* MR10 */
1280 	*u = prune(*u, LL_k);
1281 	*u = tleft_factor( *u );
1282 /*	fprintf(stderr, "after shrink&flatten&prune&lfactor:"); preorder(*u); fprintf(stderr, "\n");*/
1283 	if ( *u == NULL )
1284 	{
1285 /*		fprintf(stderr, "TreeIncomplete --> no LL(%d) ambiguity\n", LL_k);*/
1286 		Tfree( *u );
1287 		*u = NULL;
1288 	}
1289 
1290 	for (k=1; k<=LL_k; k++) set_clr( fs[k] );
1291 
1292 	ambig = tnode(ALT);
1293 	k = 0;
1294 	if ( *t!=NULL && *u!=NULL )
1295 	{
1296 		while ( (perm=permute(1,LL_k))!=NULL )
1297 		{
1298 /*			fprintf(stderr, "chk perm:"); preorder(perm); fprintf(stderr, "\n");*/
1299 			if ( tmember(perm, *t) && tmember(perm, *u) )
1300 			{
1301 /*				fprintf(stderr, "ambig upon"); preorder(perm); fprintf(stderr, "\n");*/
1302 
1303 				k++;
1304 				perm->right = ambig->down;
1305 				ambig->down = perm;
1306 				tcvt(&(fs[1]), perm);
1307 			}
1308 			else Tfree( perm );
1309 		}
1310 	}
1311 
1312     for (j=0; j <= CLL_k ; j++) fs[j]=save_fs[j];
1313     free( (char *) save_fs);
1314 
1315     tnodes_at_end=TnodesAllocated;
1316     tnodes_used=tnodes_at_end - tnodes_at_start;
1317 
1318     if (TnodesReportThreshold > 0 && tnodes_used > TnodesReportThreshold) {
1319       fprintf(stdout,"There were %d tuples whose ambiguity could not be resolved by full lookahead\n",k);
1320       fprintf(stdout,"There were %d tnodes created to resolve ambiguity between:\n\n",tnodes_used);
1321       fprintf(stdout,"  Choice 1: %s  line %d  file %s\n",
1322                                  MR_ruleNamePlusOffset( (Node *) alt1),alt1->line,FileStr[alt1->file]);
1323       fprintf(stdout,"  Choice 2: %s  line %d  file %s\n",
1324                                  MR_ruleNamePlusOffset( (Node *) alt2),alt2->line,FileStr[alt2->file]);
1325       for (j=1; j <= CLL_k ; j++) {
1326         fprintf(stdout,"\n    Intersection of lookahead[%d] sets:\n",j);
1327         MR_dumpTokenSet(stdout,2,fs[j]);
1328       };
1329       fprintf(stdout,"\n");
1330     };
1331 
1332 	*numAmbig = k;
1333 	if ( ambig->down == NULL ) {_Tfree(ambig); ambig = NULL;}
1334 	free( (char *)findex );
1335 /*	fprintf(stderr, "final ambig:"); preorder(ambig); fprintf(stderr, "\n");*/
1336 	return ambig;
1337 }
1338 
1339 static Tree *
1340 #ifdef __USE_PROTOS
bottom_of_chain(Tree * t)1341 bottom_of_chain( Tree *t )
1342 #else
1343 bottom_of_chain( t )
1344 Tree *t;
1345 #endif
1346 {
1347     if ( t==NULL ) return NULL;
1348     for (; t->down != NULL; t=t->down) {;}
1349     return t;
1350 }
1351 
1352 /*
1353  * Make a tree from k sets where the degree of the first k-1 sets is 1.
1354  */
1355 Tree *
1356 #ifdef __USE_PROTOS
make_tree_from_sets(set * fset1,set * fset2)1357 make_tree_from_sets( set *fset1, set *fset2 )
1358 #else
1359 make_tree_from_sets( fset1, fset2 )
1360 set *fset1;
1361 set *fset2;
1362 #endif
1363 {
1364 	set inter;
1365 	int i;
1366 	Tree *t=NULL, *n, *u;
1367 	unsigned *p,*q;
1368 	require(LL_k>1, "make_tree_from_sets: LL_k must be > 1");
1369 
1370 	/* do the degree 1 sets first */
1371 	for (i=1; i<=LL_k-1; i++)
1372 	{
1373 		inter = set_and(fset1[i], fset2[i]);
1374 		require(set_deg(inter)==1, "invalid set to tree conversion");
1375 		n = tnode(set_int(inter));
1376 		if (t==NULL) t=n; else tmake(t, n, NULL);
1377 		set_free(inter);
1378 	}
1379 
1380 	/* now add the chain of tokens at depth k */
1381 	u = bottom_of_chain(t);
1382 	inter = set_and(fset1[LL_k], fset2[LL_k]);
1383 	if ( (q=p=set_pdq(inter)) == NULL ) fatal_internal("Can't alloc space for set_pdq");
1384 	/* first one is linked to bottom, then others are sibling linked */
1385 	n = tnode(*p++);
1386 	u->down = n;
1387 	u = u->down;
1388 	while ( *p != nil )
1389 	{
1390 		n = tnode(*p);
1391 		u->right = n;
1392 		u = u->right;
1393 		p++;
1394 	}
1395 	free((char *)q);
1396 
1397 	return t;
1398 }
1399 
1400 /* create and return the tree of lookahead k-sequences that are in t, but not
1401  * in the context of predicates in predicate list p.
1402  */
1403 Tree *
1404 #ifdef __USE_PROTOS
tdif(Tree * ambig_tuples,Predicate * p,set * fset1,set * fset2)1405 tdif( Tree *ambig_tuples, Predicate *p, set *fset1, set *fset2 )
1406 #else
1407 tdif( ambig_tuples, p, fset1, fset2 )
1408 Tree *ambig_tuples;
1409 Predicate *p;
1410 set *fset1;
1411 set *fset2;
1412 #endif
1413 {
1414 	unsigned **ft;
1415 	Tree *dif=NULL;
1416 	Tree *perm;
1417 	set b;
1418 	int i,k;
1419 
1420 	if ( p == NULL ) return tdup(ambig_tuples);
1421 
1422 	ft = (unsigned **) calloc(CLL_k+1, sizeof(unsigned *));
1423 	require(ft!=NULL, "cannot allocate ft");
1424 	for (i=1; i<=CLL_k; i++)
1425 	{
1426 		b = set_and(fset1[i], fset2[i]);
1427 		ft[i] = set_pdq(b);
1428 		set_free(b);
1429 	}
1430 	findex = (int *) calloc(LL_k+1, sizeof(int));
1431 	if ( findex == NULL )
1432 	{
1433 		fatal_internal("out of memory in tdif while checking predicates");
1434 	}
1435 	for (k=1; k<=LL_k; k++) findex[k] = 0;
1436 
1437 #ifdef DBG_TRAV
1438 	fprintf(stderr, "tdif_%d[", p->k);
1439 	preorder(ambig_tuples);
1440 	fprintf(stderr, ",");
1441 	preorder(p->tcontext);
1442 	fprintf(stderr, "] =");
1443 #endif
1444 
1445 	ftbl = ft;
1446 	while ( (perm=permute(1,p->k))!=NULL )
1447 	{
1448 #ifdef DBG_TRAV
1449 		fprintf(stderr, "test perm:"); preorder(perm); fprintf(stderr, "\n");
1450 #endif
1451 		if ( tmember_constrained(perm, ambig_tuples) &&
1452 			 !tmember_of_context(perm, p) )
1453 		{
1454 #ifdef DBG_TRAV
1455 			fprintf(stderr, "satisfied upon"); preorder(perm); fprintf(stderr, "\n");
1456 #endif
1457 			k++;
1458 			if ( dif==NULL ) dif = perm;
1459 			else
1460 			{
1461 				perm->right = dif;
1462 				dif = perm;
1463 			}
1464 		}
1465 		else Tfree( perm );
1466 	}
1467 
1468 #ifdef DBG_TRAV
1469 	preorder(dif);
1470 	fprintf(stderr, "\n");
1471 #endif
1472 
1473 	for (i=1; i<=CLL_k; i++) free( (char *)ft[i] );
1474 	free((char *)ft);
1475 	free((char *)findex);
1476 
1477 	return dif;
1478 }
1479 
1480 /* is lookahead sequence t a member of any context tree for any
1481  * predicate in p?
1482  */
1483 static int
1484 #ifdef __USE_PROTOS
tmember_of_context(Tree * t,Predicate * p)1485 tmember_of_context( Tree *t, Predicate *p )
1486 #else
1487 tmember_of_context( t, p )
1488 Tree *t;
1489 Predicate *p;
1490 #endif
1491 {
1492 	for (; p!=NULL; p=p->right)
1493 	{
1494 		if ( p->expr==PRED_AND_LIST || p->expr==PRED_OR_LIST )
1495 			return tmember_of_context(t, p->down);
1496 		if ( tmember_constrained(t, p->tcontext) ) return 1;
1497 		if ( tmember_of_context(t, p->down) ) return 1;
1498 	}
1499 	return 0;
1500 }
1501 
1502 int
1503 #ifdef __USE_PROTOS
is_single_tuple(Tree * t)1504 is_single_tuple( Tree *t )
1505 #else
1506 is_single_tuple( t )
1507 Tree *t;
1508 #endif
1509 {
1510 	if ( t == NULL ) return 0;
1511 	if ( t->right != NULL ) return 0;
1512 	if ( t->down == NULL ) return 1;
1513 	return is_single_tuple(t->down);
1514 }
1515 
1516 
1517 /* MR10 Check that a context guard contains only allowed things */
1518 /* MR10   (mainly token references).                            */
1519 
1520 #ifdef __USE_PROTOS
contextGuardOK(Node * p,int h,int * hmax)1521 int contextGuardOK(Node *p,int h,int *hmax)
1522 #else
1523 int contextGuardOK(p,h,hmax)
1524   Node  *p;
1525   int   h;
1526   int   *hmax;
1527 #endif
1528 {
1529     Junction     *j;
1530     TokNode      *tn;
1531 
1532     if (p == NULL) return 1;
1533     if (p->ntype == nToken) {
1534       h++;
1535       if (h > *hmax) *hmax=h;
1536       tn=(TokNode *)p;
1537       if (tn->el_label != NULL) {
1538         warnFL(eMsg1("a label (\"%s\") for a context guard element is meaningless",tn->el_label),
1539                              FileStr[p->file],p->line);
1540       };
1541       return contextGuardOK( ( (TokNode *) p)->next,h,hmax);
1542     } else if (p->ntype == nAction) {
1543       goto Fail;
1544     } else if (p->ntype == nRuleRef) {
1545       goto Fail;
1546     } else {
1547       require (p->ntype == nJunction,"Unexpected ntype");
1548       j=(Junction *) p;
1549       if (j->jtype != Generic &&
1550           j->jtype != aSubBlk &&        /* pretty sure this one is allowed */
1551 /****     j->jtype != aOptBlk && ****/  /* pretty sure this one is allowed */ /* MR11 not any more ! */
1552           j->jtype != EndBlk) {
1553         errFL("A context guard may not contain an option block: {...} or looping block: (...)* or (...)+",
1554                   FileStr[p->file],p->line);
1555         contextGuardOK(j->p1,h,hmax);
1556         return 0;
1557       };
1558       /* do both p1 and p2 so use | rather than ||  */
1559       return contextGuardOK(j->p2,h,hmax) | contextGuardOK(j->p1,h,hmax);
1560     };
1561 Fail:
1562     errFL("A context guard may contain only Token references - guard will be ignored",
1563                              FileStr[p->file],p->line);
1564     contextGuardOK( ( (ActionNode *) p)->next,h,hmax);
1565     return 0;
1566 }
1567 
1568 /*
1569  * Look at a (...)? generalized-predicate context-guard and compute
1570  * either a lookahead set (k==1) or a lookahead tree for k>1.  The
1571  * k level is determined by the guard itself rather than the LL_k
1572  * variable.  For example, ( A B )? is an LL(2) guard and ( ID )?
1573  * is an LL(1) guard.  For the moment, you can only have a single
1574  * tuple in the guard.  Physically, the block must look like this
1575  *   --o-->TOKEN-->o-->o-->TOKEN-->o-- ... -->o-->TOKEN-->o--
1576  * An error is printed for any other type.
1577  */
1578 Predicate *
1579 #ifdef __USE_PROTOS
computePredFromContextGuard(Graph blk,int * msgDone)1580 computePredFromContextGuard(Graph blk,int *msgDone)    /* MR10 */
1581 #else
1582 computePredFromContextGuard(blk,msgDone)               /* MR10 */
1583   Graph     blk;
1584   int       *msgDone;                                       /* MR10 */
1585 #endif
1586 {
1587     Junction *junc = (Junction *)blk.left, *p;
1588     Tree        *t=NULL;
1589 	Predicate   *pred = NULL;
1590 	set         scontext, rk;
1591     int         ok;
1592     int         hmax=0;
1593 
1594     require(junc!=NULL && junc->ntype == nJunction, "bad context guard");
1595 
1596 /* MR10 Check for anything other than Tokens and generic junctions */
1597 
1598     *msgDone=0;                                             /* MR10 */
1599     ok=contextGuardOK( (Node *)junc,0,&hmax);               /* MR10 */
1600     if (! ok) {                                             /* MR10 */
1601       *msgDone=1;                                           /* MR10 */
1602       return NULL;                                          /* MR10 */
1603     };                                                      /* MR10 */
1604     if (hmax == 0) {
1605 errFL("guard is 0 tokens long",FileStr[junc->file],junc->line);          /* MR11 */
1606       *msgDone=1;
1607       return NULL;
1608     };
1609     if (hmax > CLL_k) {                                     /* MR10 */
1610 errFL(eMsgd2("guard is %d tokens long - lookahead is limited to max(k,ck)==%d", /* MR10 */
1611         hmax,CLL_k),                                        /* MR10 */
1612         FileStr[junc->file],junc->line);                    /* MR10 */
1613       *msgDone=1;                                           /* MR10 */
1614       return NULL;                                          /* MR10 */
1615     };                                                      /* MR10 */
1616 
1617 	rk = empty;
1618 	p = junc;
1619 	pred = new_pred();
1620 	pred->k = hmax;     /* MR10 should be CLL_k, not LLK ? */
1621 	if (hmax > 1 )      /* MR10 was LL_k                   */
1622 	{
1623 		ConstrainSearch = 0;
1624 		ContextGuardTRAV = 1;
1625 		TRAV(p, hmax, &rk, t);  /* MR10 was LL_k */
1626 		ContextGuardTRAV = 0;
1627 		set_free(rk);
1628 		t = tshrink( t );
1629 		t = tflatten( t );
1630 		t = tleft_factor( t );
1631 /*
1632 		fprintf(stderr, "ctx guard:");
1633 		preorder(t);
1634 		fprintf(stderr, "\n");
1635 */
1636 		pred->tcontext = t;
1637 	}
1638 	else
1639 	{
1640 		REACH(p, 1, &rk, scontext);
1641 		require(set_nil(rk), "rk != nil");
1642 		set_free(rk);
1643 /*
1644 		fprintf(stderr, "LL(1) ctx guard is:");
1645 		s_fprT(stderr, scontext);
1646 		fprintf(stderr, "\n");
1647 */
1648 		pred->scontext[1] = scontext;
1649 	}
1650 
1651     list_add(&ContextGuardPredicateList,pred);     /* MR13 */
1652 
1653 	return pred;
1654 }
1655 
1656 /* MR13
1657    When the context guard is originally computed the
1658    meta-tokens are not known.
1659 */
1660 
1661 #ifdef __USE_PROTOS
recomputeContextGuard(Predicate * pred)1662 void recomputeContextGuard(Predicate *pred)
1663 #else
1664 void recomputeContextGuard(pred)
1665     Predicate   *pred;
1666 #endif
1667 {
1668     Tree *          t=NULL;
1669 	set             scontext;
1670     set             rk;
1671     ActionNode *    actionNode;
1672     Junction *      p;
1673 
1674     actionNode=pred->source;
1675     require (actionNode != NULL,"context predicate's source == NULL");
1676 
1677     p=actionNode->guardNodes;
1678     require (p != NULL,"context predicate's guardNodes == NULL");
1679 
1680 	rk = empty;
1681 	if (pred->k > 1 )
1682 	{
1683 		ConstrainSearch = 0;
1684 		ContextGuardTRAV = 1;
1685 		TRAV(p, pred->k, &rk, t);
1686 		ContextGuardTRAV = 0;
1687 		set_free(rk);
1688 		t = tshrink( t );
1689 		t = tflatten( t );
1690 		t = tleft_factor( t );
1691         Tfree(pred->tcontext);
1692 		pred->tcontext = t;
1693 	}
1694 	else
1695 	{
1696 		REACH(p, 1, &rk, scontext);
1697 		require(set_nil(rk), "rk != nil");
1698 		set_free(rk);
1699         set_free(pred->scontext[1]);
1700 		pred->scontext[1] = scontext;
1701 	}
1702 }
1703 
1704 /* MR11 - had enough of flags yet ? */
1705 
1706 int     MR_AmbSourceSearch=0;
1707 int     MR_AmbSourceSearchGroup=0;
1708 int     MR_AmbSourceSearchChoice=0;
1709 int     MR_AmbSourceSearchLimit=0;
1710 int     MR_matched_AmbAidRule=0;
1711 
1712 static    set         *matchSets[2]={NULL,NULL};
1713 static    int         *tokensInChain=NULL;
1714 static    Junction    *MR_AmbSourceSearchJ[2];
1715 
MR_traceAmbSourceKclient()1716 void MR_traceAmbSourceKclient()
1717 {
1718   int       i;
1719   set       *save_fset;
1720   int       save_ConstrainSearch;
1721   set       incomplete;
1722   Tree      *t;
1723 
1724   if (matchSets[0] == NULL) {
1725     matchSets[0]=(set *) calloc (CLL_k+1,sizeof(set));
1726     require (matchSets[0] != NULL,"matchSets[0] alloc");
1727     matchSets[1]=(set *) calloc (CLL_k+1,sizeof(set));
1728     require (matchSets[1] != NULL,"matchSets[1] alloc");
1729   };
1730 
1731   for (i=1 ; i <= MR_AmbSourceSearchLimit ; i++) {
1732     set_clr(matchSets[0][i]);
1733     set_orel( (unsigned) tokensInChain[i],
1734                               &matchSets[0][i]);
1735     set_clr(matchSets[1][i]);
1736     set_orel( (unsigned) tokensInChain[i],
1737                               &matchSets[1][i]);
1738   };
1739 
1740   save_fset=fset;
1741   save_ConstrainSearch=ConstrainSearch;
1742 
1743 
1744 
1745   for (i=0 ; i < 2 ; i++) {
1746 
1747 #if 0
1748 **    fprintf(stdout,"  Choice:%d  Depth:%d  ",i+1,MR_AmbSourceSearchLimit);
1749 **    fprintf(stdout,"(");
1750 **    for (j=1 ; j <= MR_AmbSourceSearchLimit ; j++) {
1751 **      if (j != 1) fprintf(stdout," ");
1752 **      fprintf(stdout,"%s",TerminalString(tokensInChain[j]));
1753 **    };
1754 **    fprintf(stdout,")\n\n");
1755 #endif
1756 
1757     fset=matchSets[i];
1758 
1759     MR_AmbSourceSearch=1;
1760     MR_MaintainBackTrace=1;
1761     MR_AmbSourceSearchChoice=i;
1762     ConstrainSearch=1;
1763 
1764     maxk = MR_AmbSourceSearchLimit;
1765 
1766     incomplete=empty;
1767     t=NULL;
1768 
1769     constrain = &(fset[1]);
1770     MR_pointerStackReset(&MR_BackTraceStack);
1771 
1772     TRAV(MR_AmbSourceSearchJ[i],maxk,&incomplete,t);
1773 
1774     Tfree(t);
1775 
1776     require (set_nil(incomplete),"MR_traceAmbSourceK TRAV incomplete");
1777     require (MR_BackTraceStack.count == 0,"K: MR_BackTraceStack.count != 0");
1778 
1779     set_free(incomplete);
1780   };
1781 
1782   ConstrainSearch=save_ConstrainSearch;
1783   fset=save_fset;
1784   MR_AmbSourceSearch=0;
1785   MR_MaintainBackTrace=0;
1786   MR_AmbSourceSearchChoice=0;
1787 }
1788 
1789 #ifdef __USE_PROTOS
tTrunc(Tree * t,int depth)1790 Tree *tTrunc(Tree *t,int depth)
1791 #else
1792 Tree *tTrunc(t,depth)
1793   Tree  *t;
1794 #endif
1795 {
1796     Tree    *u;
1797 
1798     require ( ! (t == NULL && depth > 0),"tree too short");
1799 
1800     if (depth == 0) return NULL;
1801 
1802     if (t->token == ALT) {
1803       u=tTrunc(t->down,depth);
1804     } else {
1805       u=tnode(t->token);
1806       u->down=tTrunc(t->down,depth-1);
1807     };
1808     if (t->right != NULL) u->right=tTrunc(t->right,depth);
1809     return u;
1810 }
1811 
1812 #ifdef __USE_PROTOS
MR_iterateOverTree(Tree * t,int chain[])1813 void MR_iterateOverTree(Tree *t,int chain[])
1814 #else
1815 void MR_iterateOverTree(t,chain)
1816   Tree          *t;
1817   int           chain[];
1818 #endif
1819 {
1820   if (t == NULL) return;
1821   chain[0]=t->token;
1822   if (t->down != NULL) {
1823     MR_iterateOverTree(t->down,&chain[1]);
1824   } else {
1825     MR_traceAmbSourceKclient();
1826   };
1827   MR_iterateOverTree(t->right,&chain[0]);
1828   chain[0]=0;
1829 }
1830 
1831 #ifdef __USE_PROTOS
MR_traceAmbSourceK(Tree * t,Junction * alt1,Junction * alt2)1832 void MR_traceAmbSourceK(Tree *t,Junction *alt1,Junction *alt2)
1833 #else
1834 void MR_traceAmbSourceK(t,alt1,alt2)
1835   Tree      *t;
1836   Junction  *alt1;
1837   Junction  *alt2;
1838 #endif
1839 {
1840     int         i;
1841     int         depth;
1842     int         maxDepth;
1843     Tree        *truncatedTree;
1844 
1845     if (MR_AmbAidRule == NULL) return;
1846 
1847     if ( ! (
1848             strcmp(MR_AmbAidRule,alt1->rname) == 0 ||
1849             strcmp(MR_AmbAidRule,alt2->rname) == 0 ||
1850             MR_AmbAidLine==alt1->line ||
1851             MR_AmbAidLine==alt2->line
1852            )
1853        ) return;
1854 
1855     MR_matched_AmbAidRule++;
1856 
1857     /* there are no token sets in trees, only in TokNodes */
1858 
1859     MR_AmbSourceSearchJ[0]=analysis_point( (Junction *) alt1->p1);
1860     MR_AmbSourceSearchJ[1]=analysis_point( (Junction *) alt2->p1);
1861 
1862     if (tokensInChain == NULL) {
1863       tokensInChain=(int *) calloc (CLL_k+1,sizeof(int));
1864       require (tokensInChain != NULL,"tokensInChain alloc");
1865     };
1866 
1867     MR_AmbSourceSearchGroup=0;
1868 
1869     fprintf(stdout,"\n");
1870     fprintf(stdout,"  Ambiguity Aid                 ");
1871     fprintf(stdout,
1872                 (MR_AmbAidDepth <= LL_k ?
1873                     "(-k %d  -aa %s  %s  -aad %d)\n\n" :
1874                         "(-k %d  -aa %s  %s  [-k value limits -aad %d])\n\n"),
1875                 LL_k,
1876                 MR_AmbAidRule,
1877                 (MR_AmbAidMultiple ? "-aam" : ""),
1878                 MR_AmbAidDepth);
1879 
1880     for (i=0 ; i < 2 ; i++) {
1881       fprintf(stdout,"    Choice %d: %-25s  line %d  file %s\n",
1882                   (i+1),
1883                   MR_ruleNamePlusOffset( (Node *) MR_AmbSourceSearchJ[i]),
1884                   MR_AmbSourceSearchJ[i]->line,
1885                   FileStr[MR_AmbSourceSearchJ[i]->file]);
1886     };
1887 
1888     fprintf(stdout,"\n");
1889 
1890     if (MR_AmbAidDepth < LL_k) {
1891       maxDepth=MR_AmbAidDepth;
1892     } else {
1893       maxDepth=LL_k;
1894     };
1895 
1896     for (depth=1 ; depth <= maxDepth; depth++) {
1897       MR_AmbSourceSearchLimit=depth;
1898       if (depth < LL_k) {
1899         truncatedTree=tTrunc(t,depth);
1900         truncatedTree=tleft_factor(truncatedTree);
1901         MR_iterateOverTree(truncatedTree,&tokensInChain[1]);    /* <===== */
1902         Tfree(truncatedTree);
1903       } else {
1904         MR_iterateOverTree(t,tokensInChain);                /* <===== */
1905       };
1906       fflush(stdout);
1907       fflush(stderr);
1908     };
1909 
1910     fprintf(stdout,"\n");
1911     MR_AmbSourceSearch=0;
1912     MR_MaintainBackTrace=0;
1913     MR_AmbSourceSearchGroup=0;
1914     MR_AmbSourceSearchChoice=0;
1915     MR_AmbSourceSearchLimit=0;
1916 
1917 }
1918 
1919 
1920 /* this if for k=1 grammars only
1921 
1922    this is approximate only because of the limitations of linear
1923    approximation lookahead.  Don't want to do a k=3 search when
1924    the user only specified a ck=3 grammar
1925 */
1926 
1927 #ifdef __USE_PROTOS
MR_traceAmbSource(set * matchSets,Junction * alt1,Junction * alt2)1928 void MR_traceAmbSource(set *matchSets,Junction *alt1, Junction *alt2)
1929 #else
1930 void MR_traceAmbSource(matchSets,alt1,alt2)
1931   set       *matchSets;
1932   Junction  *alt1;
1933   Junction  *alt2;
1934 #endif
1935 {
1936     set         *save_fset;
1937     Junction    *p[2];
1938     int         i;
1939     int         j;
1940     set         *dup_matchSets;
1941     set         intersection;
1942     set         incomplete;
1943     set         tokensUsed;
1944     int         depth;
1945 
1946     if (MR_AmbAidRule == NULL) return;
1947     if ( ! (
1948             strcmp(MR_AmbAidRule,alt1->rname) == 0 ||
1949             strcmp(MR_AmbAidRule,alt2->rname) == 0 ||
1950             MR_AmbAidLine==alt1->line ||
1951             MR_AmbAidLine==alt2->line
1952            )
1953        ) return;
1954 
1955     MR_matched_AmbAidRule++;
1956 
1957     save_fset=fset;
1958 
1959     dup_matchSets=(set *) calloc(CLL_k+1,sizeof(set));
1960     require (dup_matchSets != NULL,"Can't allocate dup_matchSets");
1961 
1962     p[0]=analysis_point( (Junction *) alt1->p1);
1963     p[1]=analysis_point( (Junction *) alt2->p1);
1964 
1965     fprintf(stdout,"\n");
1966 
1967     fprintf(stdout,"  Ambiguity Aid                 ");
1968     fprintf(stdout,
1969                 (MR_AmbAidDepth <= CLL_k ?
1970                     "(-ck %d  -aa %s  %s  -aad %d)\n\n" :
1971                         "(-ck %d  -aa %s  %s  [-ck value limits -aad %d])\n\n"),
1972                 CLL_k,
1973                 MR_AmbAidRule,
1974                 (MR_AmbAidMultiple ? "-aam" : ""),
1975                 MR_AmbAidDepth);
1976 
1977     for (i=0 ; i < 2 ; i++) {
1978       fprintf(stdout,"    Choice %d: %-25s  line %d  file %s\n",
1979                             (i+1),
1980                             MR_ruleNamePlusOffset( (Node *) p[i]),
1981                             p[i]->line,FileStr[p[i]->file]);
1982     };
1983 
1984     for (j=1; j <= CLL_k ; j++) {
1985       fprintf(stdout,"\n    Intersection of lookahead[%d] sets:\n",j);
1986       intersection=set_and(alt1->fset[j],alt2->fset[j]);
1987       MR_dumpTokenSet(stdout,2,intersection);
1988       set_free(intersection);
1989     };
1990 
1991     fprintf(stdout,"\n");
1992 
1993     require (1 <= MR_AmbAidDepth && MR_AmbAidDepth <= CLL_k,
1994                 "illegal MR_AmbAidDepth");
1995 
1996     MR_AmbSourceSearchGroup=0;
1997     for (depth=1; depth <= MR_AmbAidDepth; depth++) {
1998         MR_AmbSourceSearchLimit=depth;
1999         for (i=0 ; i < 2 ; i++) {
2000 
2001 /***        fprintf(stdout,"  Choice:%d  Depth:%d\n\n",i+1,depth);  ***/
2002 
2003             for (j=0 ; j <= CLL_k ; j++) { dup_matchSets[j]=set_dup(matchSets[j]); };
2004             fset=dup_matchSets;
2005 
2006             fflush(output);
2007             fflush(stdout);
2008 
2009             MR_AmbSourceSearch=1;
2010             MR_MaintainBackTrace=1;
2011             MR_AmbSourceSearchChoice=i;
2012 
2013             maxk = depth;
2014             tokensUsed=empty;
2015             incomplete=empty;
2016 
2017             constrain = &(fset[1]);
2018             MR_pointerStackReset(&MR_BackTraceStack);
2019 
2020             REACH(p[i],depth,&incomplete,tokensUsed);
2021 
2022             fflush(output);
2023             fflush(stdout);
2024 
2025             require (set_nil(incomplete),"MR_traceAmbSource REACH incomplete");
2026             require (MR_BackTraceStack.count == 0,"1: MR_BackTraceStack.count != 0");
2027 
2028             set_free(incomplete);
2029             set_free(tokensUsed);
2030 
2031             for (j=0 ; j <= CLL_k ; j++) { set_free(dup_matchSets[j]); };
2032         };
2033     };
2034 
2035     fprintf(stdout,"\n");
2036 
2037     MR_AmbSourceSearch=0;
2038     MR_MaintainBackTrace=0;
2039     MR_AmbSourceSearchGroup=0;
2040     MR_AmbSourceSearchChoice=0;
2041     MR_AmbSourceSearchLimit=0;
2042 
2043     fset=save_fset;
2044     free ( (char *) dup_matchSets);
2045 }
2046 
2047 static int itemCount;
2048 
MR_backTraceDumpItemReset()2049 void MR_backTraceDumpItemReset() {
2050   itemCount=0;
2051 }
2052 
2053 #ifdef __USE_PROTOS
MR_backTraceDumpItem(FILE * f,int skip,Node * n)2054 void MR_backTraceDumpItem(FILE *f,int skip,Node *n)
2055 #else
2056 void MR_backTraceDumpItem(f,skip,n)
2057   FILE      *f;
2058   int       skip;
2059   Node      *n;
2060 #endif
2061 {
2062   TokNode       *tn;
2063   RuleRefNode   *rrn;
2064   Junction      *j;
2065   ActionNode    *a;
2066 
2067   switch (n->ntype) {
2068     case nToken:
2069         itemCount++; if (skip) goto EXIT;
2070         tn=(TokNode *)n;
2071         if (set_nil(tn->tset)) {
2072           fprintf(f,"  %2d #token %-23s",itemCount,TerminalString(tn->token));
2073         } else {
2074           fprintf(f,"  %2d #tokclass %-20s",itemCount,TerminalString(tn->token));
2075         };
2076         break;
2077     case nRuleRef:
2078         itemCount++; if (skip) goto EXIT;
2079         rrn=(RuleRefNode *)n;
2080         fprintf(f,"  %2d to %-27s",itemCount,rrn->text);
2081         break;
2082     case nAction:
2083         a=(ActionNode *)n;
2084         goto EXIT;
2085     case nJunction:
2086 
2087       j=(Junction *)n;
2088 
2089       switch (j->jtype) {
2090         case aSubBlk:
2091             if (j->guess) {
2092               itemCount++; if (skip) goto EXIT;
2093               fprintf(f,"  %2d %-30s",itemCount,"in (...)? block at");
2094               break;
2095             };
2096 /******     fprintf(f,"  %2d %-32s",itemCount,"in (...) block at");  *******/
2097 /******     break;                                                          *******/
2098             goto EXIT;
2099         case aOptBlk:
2100             itemCount++; if (skip) goto EXIT;
2101             fprintf(f,"  %2d %-30s",itemCount,"in {...} block");
2102             break;
2103         case aLoopBlk:
2104             itemCount++; if (skip) goto EXIT;
2105             fprintf(f,"  %2d %-30s",itemCount,"in (...)* block");
2106             break;
2107         case EndBlk:
2108             if (j->alpha_beta_guess_end) {
2109               itemCount++; if (skip) goto EXIT;
2110               fprintf(f,"  %2d %-30s",itemCount,"end (...)? block at");
2111               break;
2112             };
2113             goto EXIT;
2114 /******     fprintf(f,"  %2d %-32s",itemCount,"end of a block at");     *****/
2115 /******     break;                                                             *****/
2116         case RuleBlk:
2117             itemCount++; if (skip) goto EXIT;
2118             fprintf(f,"  %2d %-30s",itemCount,j->rname);
2119             break;
2120         case Generic:
2121             goto EXIT;
2122         case EndRule:
2123             itemCount++; if (skip) goto EXIT;
2124             fprintf (f,"  %2d end %-26s",itemCount,j->rname);
2125             break;
2126         case aPlusBlk:
2127             itemCount++; if (skip) goto EXIT;
2128             fprintf(f,"  %2d %-30s",itemCount,"in (...)+ block");
2129             break;
2130         case aLoopBegin:
2131             goto EXIT;
2132       };
2133       break;
2134   };
2135   fprintf(f," %-23s line %-4d  %s\n",MR_ruleNamePlusOffset(n),n->line,FileStr[n->file]);
2136 EXIT:
2137   return;
2138 }
2139 
2140 
2141 static PointerStack     previousBackTrace={0,0,NULL};
2142 
2143 #ifdef __USE_PROTOS
MR_backTraceReport(void)2144 void MR_backTraceReport(void)
2145 #else
2146 void MR_backTraceReport()
2147 #endif
2148 {
2149   int       i;
2150   int       match = 0;
2151   int       limitMatch;
2152 
2153   Node      *p;
2154   TokNode   *tn;
2155   set       remainder;
2156   int       depth;
2157 
2158   /* Even when doing a k=2 search this routine can get
2159        called when there is only 1 token on the stack.
2160      This is because something like rRuleRef can change
2161        the search value of k from 2 to 1 temporarily.
2162      It does this because the it wants to know the k=1
2163        first set before it does a k=2 search
2164   */
2165 
2166   depth=0;
2167   for (i=0; i < MR_BackTraceStack.count ; i++) {
2168     p=(Node *) MR_BackTraceStack.data[i];
2169     if (p->ntype == nToken) depth++;
2170   };
2171 
2172 /* MR14 */  if (MR_AmbSourceSearch) {
2173 /* MR14 */     require (depth <= MR_AmbSourceSearchLimit,"depth > MR_AmbSourceSearchLimit");
2174 /* MR14 */  }
2175 
2176   /* MR23 THM - Traceback report was being called at the wrong time for -alpha reports */
2177   /*            Reported by Arpad Beszedes (beszedes@inf.u-szeged.hu)                  */
2178 
2179   if (MR_AmbSourceSearchLimit == 0 || depth < MR_AmbSourceSearchLimit) {
2180     return;
2181   };
2182 
2183   MR_backTraceDumpItemReset();
2184 
2185   limitMatch=MR_BackTraceStack.count;
2186   if (limitMatch > previousBackTrace.count) {
2187     limitMatch=previousBackTrace.count;
2188   };
2189 
2190   for (match=0; match < limitMatch; match++) {
2191     if (MR_BackTraceStack.data[match] !=
2192         previousBackTrace.data[match]) {
2193       break;
2194     };
2195   };
2196 
2197   /* not sure at the moment why there would be duplicates */
2198 
2199   if (match != MR_BackTraceStack.count) {
2200 
2201     fprintf(stdout,"     Choice:%d  Depth:%d  Group:%d",
2202         (MR_AmbSourceSearchChoice+1),
2203         MR_AmbSourceSearchLimit,
2204         ++MR_AmbSourceSearchGroup);
2205 
2206     depth=0;
2207     fprintf(stdout,"  (");
2208     for (i=0; i < MR_BackTraceStack.count ; i++) {
2209       p=(Node *) MR_BackTraceStack.data[i];
2210       if (p->ntype != nToken) continue;
2211       tn=(TokNode *)p;
2212       if (depth != 0) fprintf(stdout," ");
2213       fprintf(stdout,TerminalString(tn->token));
2214       depth++;
2215       if (! MR_AmbAidMultiple) {
2216         if (set_nil(tn->tset)) {
2217           set_rm( (unsigned) tn->token,fset[depth]);
2218         } else {
2219           remainder=set_dif(fset[depth],tn->tset);
2220           set_free(fset[depth]);
2221           fset[depth]=remainder;
2222         };
2223       };
2224     };
2225     fprintf(stdout,")\n");
2226 
2227     for (i=0; i < MR_BackTraceStack.count ; i++) {
2228       MR_backTraceDumpItem(stdout, (i<match) ,(Node *) MR_BackTraceStack.data[i]);
2229     };
2230     fprintf(stdout,"\n");
2231     fflush(stdout);
2232 
2233     MR_pointerStackReset(&previousBackTrace);
2234 
2235     for (i=0; i < MR_BackTraceStack.count ; i++) {
2236       MR_pointerStackPush(&previousBackTrace,MR_BackTraceStack.data[i]);
2237     };
2238 
2239   };
2240 }
2241 
2242 #ifdef __USE_PROTOS
MR_setConstrainPointer(set * newConstrainValue)2243 void MR_setConstrainPointer(set * newConstrainValue)
2244 #else
2245 void MR_setConstrainPointer(newConstrainValue)
2246   set * newConstrainValue;
2247 #endif
2248 {
2249 	constrain=newConstrainValue;
2250 }
2251