4 * Compute FIRST sets for full LL(k)
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.
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
28 * Parr Research Corporation
29 * with Purdue University and AHPCRC, University of Minnesota
37 #ifdef PCCTS_USE_STDARG
49 /* ick! globals. Used by permute() to track which elements of a set have been used */
52 set
*fset
; /* MR11 make global */
53 static unsigned **ftbl
;
54 static set
*constrain
; /* pts into fset. constrains tToken() to 'constrain' */
56 int maxk
; /* set to initial k upon tree construction request */
57 /* MR11 make global */
58 static Tree
*FreeList
= NULL
;
61 static int tmember_of_context(Tree
*, Predicate
*);
63 static int tmember_of_context();
67 set set_of_tnodes_in_use
;
68 int stop_on_tnode_seq_number
=(-1); /* (-1) to disable */
77 preorder( Tree
*tree
)
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
);
89 if ( tree
->down
!= NULL
) fprintf(stderr
, " )");
90 preorder(tree
->right
);
94 int MR_tree_matches_constraints(int k
,set
* constrain
,Tree
*t
)
96 int MR_tree_matches_constraints(k
,constrain
,t
)
105 if (k
== 0) return 1;
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.
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
)) {
128 /* check the depth of each primary sibling to see that it is exactly
137 * Remove all branches <= k deep.
139 * Added by TJP 9-23-92 to make the LL(k) constraint mechanism to work.
142 static int pruneCount
=0;
143 static int prunePeak
=200;
147 prune( Tree
*t
, int k
)
155 if (pruneCount
> prunePeak
+100) {
156 prunePeak
=pruneCount
;
158 *** fprintf(stderr
,"pruneCount=%d\n",pruneCount
);
159 /*** preorder(t); ***/
160 *** fprintf(stderr
,"\n",pruneCount
);
167 if ( t
->token
== ALT
) fatal_internal("prune: ALT node in FIRST tree");
168 if ( t
->right
!=NULL
) t
->right
= prune(t
->right
, k
);
171 if ( t
->down
!=NULL
) t
->down
= prune(t
->down
, k
-1);
172 if ( t
->down
== NULL
)
185 /* build a tree (root child1 child2 ... NULL) */
186 #ifdef PCCTS_USE_STDARG
187 Tree
*tmake(Tree
*root
, ...)
189 Tree
*tmake(va_alist
)
195 Tree
*child
, *sibling
=NULL
, *tail
=NULL
;
196 #ifndef PCCTS_USE_STDARG
200 #ifdef PCCTS_USE_STDARG
204 root
= va_arg(ap
, Tree
*);
206 child
= va_arg(ap
, Tree
*);
207 while ( child
!= NULL
)
210 /* added "find end of child" thing TJP March 1994 */
211 for (w
=child
; w
->right
!=NULL
; w
=w
->right
) {;} /* find end of child */
216 if ( sibling
== NULL
) {sibling
= child
; tail
= w
;}
217 else {tail
->right
= child
; tail
= w
;}
218 child
= va_arg(ap
, Tree
*);
221 /* was "root->down = sibling;" */
222 if ( root
==NULL
) root
= sibling
;
223 else root
->down
= sibling
;
240 if ( FreeList
== NULL
)
242 /*fprintf(stderr, "tnode: %d more nodes\n", TreeBlockAllocSize);*/
243 if ( TreeResourceLimit
> 0 )
245 if ( (n
+TreeBlockAllocSize
) >= TreeResourceLimit
)
247 fprintf(stderr
, ErrHdr
, FileStr
[CurAmbigfile
], CurAmbigline
);
248 fprintf(stderr
, " hit analysis resource limit while analyzing alts %d and %d %s\n",
252 exit(PCCTS_EXIT_FAILURE
);
255 newblk
= (Tree
*)calloc(TreeBlockAllocSize
, sizeof(Tree
));
256 if ( newblk
== NULL
)
258 fprintf(stderr
, ErrHdr
, FileStr
[CurAmbigfile
], CurAmbigline
);
259 fprintf(stderr
, " out of memory while analyzing alts %d and %d %s\n",
263 exit(PCCTS_EXIT_FAILURE
);
265 n
+= TreeBlockAllocSize
;
266 for (p
=newblk
; p
<&(newblk
[TreeBlockAllocSize
]); p
++)
268 p
->right
= FreeList
; /* add all new Tree nodes to Free List */
273 FreeList
= FreeList
->right
; /* remove a tree node */
274 p
->right
= NULL
; /* zero out ptrs */
278 TnodesAllocated
++; /* MR10 */
279 TnodesInUse
++; /* MR10 */
280 if (TnodesInUse
> TnodesPeak
) TnodesPeak
=TnodesInUse
; /* MR10 */
283 require(!p
->in_use
, "tnode: node in use!");
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
);
308 t
= tmake(tnode((TokenInd
!=NULL
?TokenInd
[EofToken
]:EofToken
)), t
, NULL
);
326 if (t
->seq
== stop_on_tnode_seq_number
) {
327 fprintf(stderr
,"\n*** just freed tnode #%d ***\n",t
->seq
);
329 require(t
->in_use
, "_Tfree: node not in use!");
331 set_rm( (unsigned) t
->seq
,set_of_tnodes_in_use
);
335 TnodesInUse
--; /* MR10 */
350 if ( t
== NULL
) return NULL
;
353 u
->right
= tdup(t
->right
);
354 u
->down
= tdup(t
->down
);
358 /* tree duplicate (assume tree is a chain downwards) */
361 tdup_chain( Tree
*t
)
369 if ( t
== NULL
) return NULL
;
372 u
->down
= tdup(t
->down
);
378 tappend( Tree
*t
, Tree
*u
)
387 /*** fprintf(stderr, "tappend(");
388 *** preorder(t); fprintf(stderr, ",");
389 *** preorder(u); fprintf(stderr, " )\n");
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
) {;}
398 /* dealloc all nodes in a tree */
407 if ( t
== NULL
) return;
413 /* find all children (alts) of t that require remaining_k nodes to be LL_k
418 * a1--a2--...--an <-- LL(1) tokens
420 * b1 b2 ... bn <-- LL(2) tokens
424 * z1 z2 ... zn <-- LL(LL_k) tokens
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).
431 tlink( Tree
*t
, Tree
*u
, int remaining_k
)
433 tlink( t
, u
, remaining_k
)
440 require(remaining_k
!=0, "tlink: bad tree");
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
)
446 require(t
->down
==NULL
, "tlink: invalid tree");
448 /* MR10 */ Tree
*tt
=t
->right
;
449 /* MR10 */ _Tfree(t
);
450 /* MR10 */ return tt
;
457 t
->down
= tlink(t
->down
, u
, remaining_k
);
458 t
->right
= tlink(t
->right
, u
, remaining_k
);
462 /* remove as many ALT nodes as possible while still maintaining semantics */
471 if ( t
== NULL
) return NULL
;
472 t
->down
= tshrink( t
->down
);
473 t
->right
= tshrink( t
->right
);
474 if ( t
->down
== NULL
)
476 if ( t
->token
== ALT
)
480 return u
; /* remove useless alts */
485 /* (? (ALT (? ...)) s) ==> (? (? ...) s) where s = sibling, ? = match any */
486 if ( t
->token
== ALT
&& t
->down
->right
== NULL
)
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
)
496 Tree
*u
= t
->down
->down
;
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
;
517 if ( t
->token
== ALT
)
520 /* find tail of children */
521 for (u
=t
->down
; u
->right
!=NULL
; u
=u
->right
) {;}
532 tJunc( Junction
*p
, int k
, set
*rk
)
540 Tree
*t
=NULL
, *u
=NULL
;
545 fprintf(stderr
, "tJunc(%d): %s in rule %s\n", k
,
546 decodeJType
[p
->jtype
], ((Junction
*)p
)->rname
);
549 /* MR14 */ if (AlphaBetaTrace
&& p
->alpha_beta_guess_end
) {
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();
556 /* MR14 */ if (p
->alpha_beta_guess_end
) {
557 /* MR14 */ return NULL
;
560 if ( p
->jtype
==aLoopBlk
|| p
->jtype
==RuleBlk
||
561 p
->jtype
==aPlusBlk
|| p
->jtype
==aSubBlk
|| p
->jtype
==aOptBlk
)
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
;
569 /* MR10 */ if (MR_MaintainBackTrace
) {
570 /* MR10 */ if (p
->jtype
!= Generic
) MR_pointerStackPush(&MR_BackTraceStack
,p
);
573 TRAV(p
->p1
, k
, rk
, tail
);
575 /* MR10 */ if (MR_MaintainBackTrace
) {
576 /* MR10 */ if (p
->jtype
!= Generic
) MR_pointerStackPop(&MR_BackTraceStack
);
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
)
583 /* if this is one of the added optional alts for (...)+ then break */
584 if ( alt
->ignore
) break;
586 if ( tail
==NULL
) {TRAV(alt
->p1
, k
, rk
, tail
); r
->down
= tail
;}
589 /* MR10 */ if (MR_MaintainBackTrace
) {
590 /* MR10 */ if (p
->jtype
!= Generic
) MR_pointerStackPush(&MR_BackTraceStack
,p
);
593 TRAV(alt
->p1
, k
, rk
, tail
->right
);
595 /* MR10 */ if (MR_MaintainBackTrace
) {
596 /* MR10 */ if (p
->jtype
!= Generic
) MR_pointerStackPop(&MR_BackTraceStack
);
598 if ( tail
->right
!= NULL
) tail
= tail
->right
;
601 if ( p
->jtype
!=aSubBlk
&& p
->jtype
!=aOptBlk
) p
->lock
[k
] = FALSE
;
603 fprintf(stderr
, "blk(%s) returns:",((Junction
*)p
)->rname
); preorder(r
); fprintf(stderr
, "\n");
605 if ( r
->down
== NULL
) {_Tfree(r
); return NULL
;}
609 if ( p
->jtype
==EndRule
)
611 if ( p
->halt
) /* don't want FOLLOW here? */
613 /**** if ( ContextGuardTRAV ) return NULL; ****/
614 set_orel( (unsigned) k
, rk
); /* indicate this k value needed */ /* MR10 cast */
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
);
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
;
632 /* MR14 */ p
->guess_analysis_point
=guess_point
;
638 /* MR10 */ if (MR_MaintainBackTrace
) {
639 /* MR10 */ if (p
->jtype
!= Generic
) MR_pointerStackPush(&MR_BackTraceStack
,p
);
642 /* M14 */ if (p
->guess_analysis_point
!= NULL
) {
643 /* M14 */ TRAV(p
->guess_analysis_point
, k
, rk
,t
);
645 TRAV(p
->p1
, k
, rk
,t
);
648 /* MR10 */ if (MR_MaintainBackTrace
) {
649 /* MR10 */ if (p
->jtype
!= Generic
) MR_pointerStackPop(&MR_BackTraceStack
);
652 if ( p
->jtype
==EndRule
) p
->lock
[k
]=FALSE
;
656 /* MR10 */ if (MR_MaintainBackTrace
) {
657 /* MR10 */ if (p
->jtype
!= Generic
) MR_pointerStackPush(&MR_BackTraceStack
,p
);
660 /* M14 */ if (p
->guess_analysis_point
!= NULL
) {
661 /* M14 */ TRAV(p
->guess_analysis_point
, k
, rk
,t
);
663 TRAV(p
->p1
, k
, rk
,t
);
666 /* MR10 */ if (MR_MaintainBackTrace
) {
667 /* MR10 */ if (p
->jtype
!= Generic
) MR_pointerStackPop(&MR_BackTraceStack
);
670 if ( p
->jtype
!=RuleBlk
&& /* MR14 */ !p
->guess
) TRAV(p
->p2
, k
, rk
, u
);
672 if ( p
->jtype
==EndRule
) p
->lock
[k
] = FALSE
;/* unlock node */
674 if ( t
==NULL
) return tmake(tnode(ALT
), u
, NULL
);
675 return tmake(tnode(ALT
), t
, u
, NULL
);
680 tRuleRef( RuleRefNode
*p
, int k
, set
*rk_out
)
682 tRuleRef( p
, k
, rk_out
)
689 Tree
*t
=NULL
, *u
=NULL
;
693 RuleEntry
*q
= (RuleEntry
*) hash_get(Rname
, p
->text
);
696 fprintf(stderr
, "tRuleRef: %s\n", p
->text
);
700 TRAV(p
->next
, k
, rk_out
, t
);/* ignore undefined rules */
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 */
710 /* MR10 */ if (MR_MaintainBackTrace
) {
711 /* MR10 */ MR_pointerStackPush(&MR_BackTraceStack
,p
);
716 /* MR10 */ if (MR_MaintainBackTrace
) {
717 /* MR10 */ MR_pointerStackPop(&MR_BackTraceStack
);
720 r
->end
->halt
= save_halt
;
722 fprintf(stderr
, "after ruleref, t is:"); preorder(t
); fprintf(stderr
, "\n");
725 while ( !set_nil(rk
) ) { /* any k left to do? if so, link onto tree */
729 /* MR10 */ if (MR_MaintainBackTrace
) {
730 /* MR10 */ MR_pointerStackPush(&MR_BackTraceStack
,p
);
733 TRAV(p
->next
, k2
, &rk2
, u
);
735 /* MR10 */ if (MR_MaintainBackTrace
) {
736 /* MR10 */ MR_pointerStackPop(&MR_BackTraceStack
);
739 t
= tlink(t
, u
, k2
); /* any alts missing k2 toks, add u onto end */
742 set_free(rk
); /* rk is empty, but free its memory */
743 set_orin(rk_out
, rk2
); /* remember what we couldn't do */
750 tToken( TokNode
*p
, int k
, set
*rk
)
758 Tree
*t
=NULL
, *tset
=NULL
, *u
;
760 if (ConstrainSearch
) {
761 if (MR_AmbSourceSearch
) {
762 require(constrain
>=fset
&&constrain
<=&(fset
[CLL_k
]),"tToken: constrain is not a valid set");
764 require(constrain
>=fset
&&constrain
<=&(fset
[LL_k
]),"tToken: constrain is not a valid set");
766 constrain
= &fset
[maxk
-k
+1];
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");
776 /* is it a meta token (set of tokens)? */
778 if ( !set_nil(p
->tset
) )
782 Tree
*n
, *tail
= NULL
;
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 */
791 a
= set_dup(p
->tset
);
794 for (; !set_nil(a
); set_rm(e
, a
))
798 if ( tset
==NULL
) { tset
= n
; tail
= n
; }
799 else { tail
->right
= n
; tail
= n
; }
803 else if ( ConstrainSearch
&& !set_el(p
->token
, *constrain
) )
805 /* fprintf(stderr, "ignoring token %s(%d)\n", TerminalString(p->token),
810 tset
= tnode( p
->token
);
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();
819 /* MR10 */ MR_backTraceReport();
821 /* MR10 */ MR_pointerStackPop(&MR_BackTraceStack
);
822 /* MR11 */ Tfree(tset
);
823 /* MR11 */ return NULL
;
827 if ( k
== 1 ) return tset
;
829 if (MR_MaintainBackTrace
) {
830 MR_pointerStackPush(&MR_BackTraceStack
,p
);
833 TRAV(p
->next
, k
-1, rk
, t
);
835 if (MR_MaintainBackTrace
) {
838 MR_pointerStackPop(&MR_BackTraceStack
);
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.
846 if ( t
== NULL
&& !ContextGuardTRAV
) /* tree will be too shallow */
848 if ( tset
!=NULL
) Tfree( tset
);
852 fprintf(stderr
, "tToken(%d)->next:",k
); preorder(t
); fprintf(stderr
, "\n");
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 */
858 if (tset
->right
== NULL
) return tmake(tset
, t
, NULL
); /* MR10 */
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 ) )
863 for (u
=tset
; u
!=NULL
; u
=u
->right
)
865 /* make a copy of t and hook it onto bottom of u */
870 fprintf(stderr
, "range is:"); preorder(tset
); fprintf(stderr
, "\n");
877 tAction( ActionNode
*p
, int k
, set
*rk
)
889 /* fprintf(stderr, "tAction\n"); */
891 /* An MR_SuppressSearch is looking for things that can be
892 reached even when the predicate is false.
894 There are three kinds of predicates:
896 guarded: r1: (A)? => <<p>>? r2
897 ampersand style: r1: (A)? && <<p>>? r2
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*
906 if (p
->is_predicate
&& MR_SuppressSearch
) {
908 Predicate
*pred
=p
->guardpred
;
914 constrain
= &fset
[maxk
-k
+1];
917 dif
=set_dif(*constrain
,pred
->scontext
[1]);
925 if (MR_tree_matches_constraints(k
,constrain
,pred
->tcontext
)) {
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
936 r1: (A)? && <<p>>? r2 ;
939 In this case first[1] of r1 is A, even
940 though first[1] of r2 is {A B}.
943 if (p
->is_predicate
&& p
->ampersandPred
!= NULL
) {
945 Predicate
*pred
=p
->ampersandPred
;
950 if (MR_MaintainBackTrace
) MR_pointerStackPush(&MR_BackTraceStack
,p
);
951 TRAV(p
->guardNodes
,k
,rk
,t
);
952 if (MR_MaintainBackTrace
) MR_pointerStackPop(&MR_BackTraceStack
);
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");
961 require(constrain
>=fset
&&constrain
<=&(fset
[LL_k
]),
962 "tToken: constrain is not a valid set");
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
]);
970 constrain
= &fset
[maxk
-k
+1];
971 set_andin(constrain
,pred
->scontext
[1]);
972 if (set_nil(*constrain
)) {
977 constrain
= &fset
[maxk
-k
+1];
978 if (! MR_tree_matches_constraints(pred
->k
,constrain
,pred
->tcontext
)) {
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 */
986 TRAV(p
->next
,k
,rk
,t
);
992 if (pred
->tcontext
!= NULL
) {
993 tAND
=MR_computeTreeAND(t
,pred
->tcontext
);
995 tset
=MR_make_tree_from_set(pred
->scontext
[1]);
996 tAND
=MR_computeTreeAND(t
,tset
);
1004 }; /* end if on ampersand predicate */
1006 TRAV(p
->next
,k
,rk
,t
);
1009 if (save_fset
!= NULL
) {
1010 for (i
=1 ; i
<= CLL_k
; i
++) {
1012 fset
[i
]=save_fset
[i
];
1014 free ( (char *) save_fset
);
1019 /* see if e exists in s as a possible input permutation (e is always a chain) */
1023 tmember( Tree
*e
, Tree
*s
)
1030 if ( e
==NULL
||s
==NULL
) return 0;
1031 /** fprintf(stderr, "tmember(");
1032 *** preorder(e); fprintf(stderr, ",");
1033 *** preorder(s); fprintf(stderr, " )\n");
1035 if ( s
->token
== ALT
&& s
->right
== NULL
) return tmember(e
, s
->down
);
1036 if ( e
->token
!=s
->token
)
1038 if ( s
->right
==NULL
) return 0;
1039 return tmember(e
, s
->right
);
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
);
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
1053 tmember_constrained( Tree
*e
, Tree
*s
)
1055 tmember_constrained( e
, s
)
1060 if ( e
==NULL
||s
==NULL
) return 0;
1061 /** fprintf(stderr, "tmember_constrained(");
1062 *** preorder(e); fprintf(stderr, ",");
1063 *** preorder(s); fprintf(stderr, " )\n");
1065 if ( s
->token
== ALT
&& s
->right
== NULL
)
1066 return tmember_constrained(e
, s
->down
);
1067 if ( e
->token
!=s
->token
)
1069 if ( s
->right
==NULL
) return 0;
1070 return tmember_constrained(e
, s
->right
);
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
);
1078 /* combine (? (A t) ... (A u) ...) into (? (A t u)) */
1081 tleft_factor( Tree
*t
)
1087 Tree
*u
, *v
, *trail
, *w
;
1089 /* left-factor what is at this level */
1090 if ( t
== NULL
) return NULL
;
1091 for (u
=t
; u
!=NULL
; u
=u
->right
)
1097 if ( u
->token
== v
->token
)
1099 if ( u
->down
!=NULL
)
1101 for (w
=u
->down
; w
->right
!=NULL
; w
=w
->right
) {;}
1102 w
->right
= v
->down
; /* link children together */
1104 else u
->down
= v
->down
;
1105 trail
->right
= v
->right
; /* unlink factored node */
1109 else {trail
= v
; v
=v
->right
;}
1112 /* left-factor what is below */
1113 for (u
=t
; u
!=NULL
; u
=u
->right
) u
->down
= tleft_factor( u
->down
);
1117 /* remove the permutation p from t if present */
1120 trm_perm( Tree
*t
, Tree
*p
)
1128 fprintf(stderr, "trm_perm(");
1129 preorder(t); fprintf(stderr, ",");
1130 preorder(p); fprintf(stderr, " )\n");
1132 if ( t
== NULL
|| p
== NULL
) return NULL
;
1133 if ( t
->token
== ALT
)
1135 t
->down
= trm_perm(t
->down
, p
);
1136 if ( t
->down
== NULL
) /* nothing left below, rm cur node */
1140 return trm_perm(u
, p
);
1142 t
->right
= trm_perm(t
->right
, p
); /* look for more instances of p */
1145 if ( p
->token
!= t
->token
) /* not found, try a sibling */
1147 t
->right
= trm_perm(t
->right
, p
);
1150 t
->down
= trm_perm(t
->down
, p
->down
);
1151 if ( t
->down
== NULL
) /* nothing left below, rm cur node */
1155 return trm_perm(u
, p
);
1157 t
->right
= trm_perm(t
->right
, p
); /* look for more instances of p */
1161 /* add the permutation 'perm' to the LL_k sets in 'fset' */
1164 tcvt( set
*fset
, Tree
*perm
)
1171 if ( perm
==NULL
) return;
1172 set_orel(perm
->token
, fset
);
1173 tcvt(fset
+1, perm
->down
);
1176 /* for each element of ftbl[k], make it the root of a tree with permute(ftbl[k+1])
1181 permute( int k
, int max_k
)
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? */
1195 (findex
[k
])++; /* try next token at this k */
1196 return permute(k
, max_k
);
1199 u
= tmake(tnode(ftbl
[k
][findex
[k
]]), t
, NULL
);
1200 if ( k
== max_k
) (findex
[k
])++;
1204 /* Compute LL(k) trees for alts alt1 and alt2 of p.
1205 * function result is tree of ambiguous input permutations
1207 * ALGORITHM may change to look for something other than LL_k size
1208 * trees ==> maxk will have to change.
1212 VerifyAmbig( Junction
*alt1
, Junction
*alt2
, unsigned **ft
, set
*fs
, Tree
**t
, Tree
**u
, int *numAmbig
)
1214 VerifyAmbig( alt1
, alt2
, ft
, fs
, t
, u
, numAmbig
)
1225 Tree
*perm
, *ambig
=NULL
;
1228 int tnodes_at_start
=TnodesAllocated
;
1234 save_fs
=(set
*) calloc(CLL_k
+1,sizeof(set
));
1235 require(save_fs
!= NULL
,"save_fs calloc");
1237 for (j
=0; j
<= CLL_k
; j
++) save_fs
[j
]=set_dup(fs
[j
]);
1239 maxk
= LL_k
; /* NOTE: for now, we look for LL_k */
1242 constrain
= &(fset
[1]);
1243 findex
= (int *) calloc(LL_k
+1, sizeof(int));
1244 if ( findex
== NULL
)
1246 fprintf(stderr
, ErrHdr
, FileStr
[CurAmbigfile
], CurAmbigline
);
1247 fprintf(stderr
, " out of memory while analyzing alts %d and %d of %s\n",
1251 exit(PCCTS_EXIT_FAILURE
);
1253 for (k
=1; k
<=LL_k
; k
++) findex
[k
] = 0;
1256 ConstrainSearch
= 1; /* consider only tokens in ambig sets */
1258 p
= analysis_point((Junction
*)alt1
->p1
);
1259 TRAV(p
, LL_k
, &rk
, *t
);
1261 *t
= tflatten( *t
);
1262 *t
= tleft_factor( *t
); /* MR10 */
1263 *t
= prune(*t
, LL_k
);
1264 *t
= tleft_factor( *t
);
1266 /*** fprintf(stderr, "after shrink&flatten&prune&left_factor:"); preorder(*t); fprintf(stderr, "\n");*/
1269 /*** fprintf(stderr, "TreeIncomplete --> no LL(%d) ambiguity\n", LL_k);*/
1270 Tfree( *t
); /* kill if impossible to have ambig */
1274 p
= analysis_point((Junction
*)alt2
->p1
);
1276 TRAV(p
, LL_k
, &rk
, *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");*/
1285 /* fprintf(stderr, "TreeIncomplete --> no LL(%d) ambiguity\n", LL_k);*/
1290 for (k
=1; k
<=LL_k
; k
++) set_clr( fs
[k
] );
1294 if ( *t
!=NULL
&& *u
!=NULL
)
1296 while ( (perm
=permute(1,LL_k
))!=NULL
)
1298 /* fprintf(stderr, "chk perm:"); preorder(perm); fprintf(stderr, "\n");*/
1299 if ( tmember(perm
, *t
) && tmember(perm
, *u
) )
1301 /* fprintf(stderr, "ambig upon"); preorder(perm); fprintf(stderr, "\n");*/
1304 perm
->right
= ambig
->down
;
1306 tcvt(&(fs
[1]), perm
);
1312 for (j
=0; j
<= CLL_k
; j
++) fs
[j
]=save_fs
[j
];
1313 free( (char *) save_fs
);
1315 tnodes_at_end
=TnodesAllocated
;
1316 tnodes_used
=tnodes_at_end
- tnodes_at_start
;
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
]);
1329 fprintf(stdout
,"\n");
1333 if ( ambig
->down
== NULL
) {_Tfree(ambig
); ambig
= NULL
;}
1334 free( (char *)findex
);
1335 /* fprintf(stderr, "final ambig:"); preorder(ambig); fprintf(stderr, "\n");*/
1341 bottom_of_chain( Tree
*t
)
1343 bottom_of_chain( t
)
1347 if ( t
==NULL
) return NULL
;
1348 for (; t
->down
!= NULL
; t
=t
->down
) {;}
1353 * Make a tree from k sets where the degree of the first k-1 sets is 1.
1357 make_tree_from_sets( set
*fset1
, set
*fset2
)
1359 make_tree_from_sets( fset1
, fset2
)
1366 Tree
*t
=NULL
, *n
, *u
;
1368 require(LL_k
>1, "make_tree_from_sets: LL_k must be > 1");
1370 /* do the degree 1 sets first */
1371 for (i
=1; i
<=LL_k
-1; i
++)
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
);
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 */
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.
1405 tdif( Tree
*ambig_tuples
, Predicate
*p
, set
*fset1
, set
*fset2
)
1407 tdif( ambig_tuples
, p
, fset1
, fset2
)
1420 if ( p
== NULL
) return tdup(ambig_tuples
);
1422 ft
= (unsigned **) calloc(CLL_k
+1, sizeof(unsigned *));
1423 require(ft
!=NULL
, "cannot allocate ft");
1424 for (i
=1; i
<=CLL_k
; i
++)
1426 b
= set_and(fset1
[i
], fset2
[i
]);
1430 findex
= (int *) calloc(LL_k
+1, sizeof(int));
1431 if ( findex
== NULL
)
1433 fatal_internal("out of memory in tdif while checking predicates");
1435 for (k
=1; k
<=LL_k
; k
++) findex
[k
] = 0;
1438 fprintf(stderr
, "tdif_%d[", p
->k
);
1439 preorder(ambig_tuples
);
1440 fprintf(stderr
, ",");
1441 preorder(p
->tcontext
);
1442 fprintf(stderr
, "] =");
1446 while ( (perm
=permute(1,p
->k
))!=NULL
)
1449 fprintf(stderr
, "test perm:"); preorder(perm
); fprintf(stderr
, "\n");
1451 if ( tmember_constrained(perm
, ambig_tuples
) &&
1452 !tmember_of_context(perm
, p
) )
1455 fprintf(stderr
, "satisfied upon"); preorder(perm
); fprintf(stderr
, "\n");
1458 if ( dif
==NULL
) dif
= perm
;
1470 fprintf(stderr
, "\n");
1473 for (i
=1; i
<=CLL_k
; i
++) free( (char *)ft
[i
] );
1475 free((char *)findex
);
1480 /* is lookahead sequence t a member of any context tree for any
1485 tmember_of_context( Tree
*t
, Predicate
*p
)
1487 tmember_of_context( t
, p
)
1492 for (; p
!=NULL
; p
=p
->right
)
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;
1504 is_single_tuple( Tree
*t
)
1506 is_single_tuple( t
)
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
);
1517 /* MR10 Check that a context guard contains only allowed things */
1518 /* MR10 (mainly token references). */
1521 int contextGuardOK(Node
*p
,int h
,int *hmax
)
1523 int contextGuardOK(p
,h
,hmax
)
1532 if (p
== NULL
) return 1;
1533 if (p
->ntype
== nToken
) {
1535 if (h
> *hmax
) *hmax
=h
;
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
);
1541 return contextGuardOK( ( (TokNode
*) p
)->next
,h
,hmax
);
1542 } else if (p
->ntype
== nAction
) {
1544 } else if (p
->ntype
== nRuleRef
) {
1547 require (p
->ntype
== nJunction
,"Unexpected ntype");
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
);
1558 /* do both p1 and p2 so use | rather than || */
1559 return contextGuardOK(j
->p2
,h
,hmax
) | contextGuardOK(j
->p1
,h
,hmax
);
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
);
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.
1580 computePredFromContextGuard(Graph blk
,int *msgDone
) /* MR10 */
1582 computePredFromContextGuard(blk
,msgDone
) /* MR10 */
1584 int *msgDone
; /* MR10 */
1587 Junction
*junc
= (Junction
*)blk
.left
, *p
;
1589 Predicate
*pred
= NULL
;
1594 require(junc
!=NULL
&& junc
->ntype
== nJunction
, "bad context guard");
1596 /* MR10 Check for anything other than Tokens and generic junctions */
1598 *msgDone
=0; /* MR10 */
1599 ok
=contextGuardOK( (Node
*)junc
,0,&hmax
); /* MR10 */
1600 if (! ok
) { /* MR10 */
1601 *msgDone
=1; /* MR10 */
1602 return NULL
; /* MR10 */
1605 errFL("guard is 0 tokens long",FileStr
[junc
->file
],junc
->line
); /* MR11 */
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 */
1620 pred
->k
= hmax
; /* MR10 should be CLL_k, not LLK ? */
1621 if (hmax
> 1 ) /* MR10 was LL_k */
1623 ConstrainSearch
= 0;
1624 ContextGuardTRAV
= 1;
1625 TRAV(p
, hmax
, &rk
, t
); /* MR10 was LL_k */
1626 ContextGuardTRAV
= 0;
1630 t
= tleft_factor( t
);
1632 fprintf(stderr, "ctx guard:");
1634 fprintf(stderr, "\n");
1640 REACH(p
, 1, &rk
, scontext
);
1641 require(set_nil(rk
), "rk != nil");
1644 fprintf(stderr, "LL(1) ctx guard is:");
1645 s_fprT(stderr, scontext);
1646 fprintf(stderr, "\n");
1648 pred
->scontext
[1] = scontext
;
1651 list_add(&ContextGuardPredicateList
,pred
); /* MR13 */
1657 When the context guard is originally computed the
1658 meta-tokens are not known.
1662 void recomputeContextGuard(Predicate
*pred
)
1664 void recomputeContextGuard(pred
)
1671 ActionNode
* actionNode
;
1674 actionNode
=pred
->source
;
1675 require (actionNode
!= NULL
,"context predicate's source == NULL");
1677 p
=actionNode
->guardNodes
;
1678 require (p
!= NULL
,"context predicate's guardNodes == NULL");
1683 ConstrainSearch
= 0;
1684 ContextGuardTRAV
= 1;
1685 TRAV(p
, pred
->k
, &rk
, t
);
1686 ContextGuardTRAV
= 0;
1690 t
= tleft_factor( t
);
1691 Tfree(pred
->tcontext
);
1696 REACH(p
, 1, &rk
, scontext
);
1697 require(set_nil(rk
), "rk != nil");
1699 set_free(pred
->scontext
[1]);
1700 pred
->scontext
[1] = scontext
;
1704 /* MR11 - had enough of flags yet ? */
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;
1712 static set
*matchSets
[2]={NULL
,NULL
};
1713 static int *tokensInChain
=NULL
;
1714 static Junction
*MR_AmbSourceSearchJ
[2];
1716 void MR_traceAmbSourceKclient()
1720 int save_ConstrainSearch
;
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");
1731 for (i
=1 ; i
<= MR_AmbSourceSearchLimit
; i
++) {
1732 set_clr(matchSets
[0][i
]);
1733 set_orel( (unsigned) tokensInChain
[i
],
1735 set_clr(matchSets
[1][i
]);
1736 set_orel( (unsigned) tokensInChain
[i
],
1741 save_ConstrainSearch
=ConstrainSearch
;
1745 for (i
=0 ; i
< 2 ; i
++) {
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
]));
1754 ** fprintf(stdout
,")\n\n");
1759 MR_AmbSourceSearch
=1;
1760 MR_MaintainBackTrace
=1;
1761 MR_AmbSourceSearchChoice
=i
;
1764 maxk
= MR_AmbSourceSearchLimit
;
1769 constrain
= &(fset
[1]);
1770 MR_pointerStackReset(&MR_BackTraceStack
);
1772 TRAV(MR_AmbSourceSearchJ
[i
],maxk
,&incomplete
,t
);
1776 require (set_nil(incomplete
),"MR_traceAmbSourceK TRAV incomplete");
1777 require (MR_BackTraceStack
.count
== 0,"K: MR_BackTraceStack.count != 0");
1779 set_free(incomplete
);
1782 ConstrainSearch
=save_ConstrainSearch
;
1784 MR_AmbSourceSearch
=0;
1785 MR_MaintainBackTrace
=0;
1786 MR_AmbSourceSearchChoice
=0;
1790 Tree
*tTrunc(Tree
*t
,int depth
)
1792 Tree
*tTrunc(t
,depth
)
1798 require ( ! (t
== NULL
&& depth
> 0),"tree too short");
1800 if (depth
== 0) return NULL
;
1802 if (t
->token
== ALT
) {
1803 u
=tTrunc(t
->down
,depth
);
1806 u
->down
=tTrunc(t
->down
,depth
-1);
1808 if (t
->right
!= NULL
) u
->right
=tTrunc(t
->right
,depth
);
1813 void MR_iterateOverTree(Tree
*t
,int chain
[])
1815 void MR_iterateOverTree(t
,chain
)
1820 if (t
== NULL
) return;
1822 if (t
->down
!= NULL
) {
1823 MR_iterateOverTree(t
->down
,&chain
[1]);
1825 MR_traceAmbSourceKclient();
1827 MR_iterateOverTree(t
->right
,&chain
[0]);
1832 void MR_traceAmbSourceK(Tree
*t
,Junction
*alt1
,Junction
*alt2
)
1834 void MR_traceAmbSourceK(t
,alt1
,alt2
)
1843 Tree
*truncatedTree
;
1845 if (MR_AmbAidRule
== NULL
) return;
1848 strcmp(MR_AmbAidRule
,alt1
->rname
) == 0 ||
1849 strcmp(MR_AmbAidRule
,alt2
->rname
) == 0 ||
1850 MR_AmbAidLine
==alt1
->line
||
1851 MR_AmbAidLine
==alt2
->line
1855 MR_matched_AmbAidRule
++;
1857 /* there are no token sets in trees, only in TokNodes */
1859 MR_AmbSourceSearchJ
[0]=analysis_point( (Junction
*) alt1
->p1
);
1860 MR_AmbSourceSearchJ
[1]=analysis_point( (Junction
*) alt2
->p1
);
1862 if (tokensInChain
== NULL
) {
1863 tokensInChain
=(int *) calloc (CLL_k
+1,sizeof(int));
1864 require (tokensInChain
!= NULL
,"tokensInChain alloc");
1867 MR_AmbSourceSearchGroup
=0;
1869 fprintf(stdout
,"\n");
1870 fprintf(stdout
," Ambiguity Aid ");
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"),
1877 (MR_AmbAidMultiple
? "-aam" : ""),
1880 for (i
=0 ; i
< 2 ; i
++) {
1881 fprintf(stdout
," Choice %d: %-25s line %d file %s\n",
1883 MR_ruleNamePlusOffset( (Node
*) MR_AmbSourceSearchJ
[i
]),
1884 MR_AmbSourceSearchJ
[i
]->line
,
1885 FileStr
[MR_AmbSourceSearchJ
[i
]->file
]);
1888 fprintf(stdout
,"\n");
1890 if (MR_AmbAidDepth
< LL_k
) {
1891 maxDepth
=MR_AmbAidDepth
;
1896 for (depth
=1 ; depth
<= maxDepth
; depth
++) {
1897 MR_AmbSourceSearchLimit
=depth
;
1899 truncatedTree
=tTrunc(t
,depth
);
1900 truncatedTree
=tleft_factor(truncatedTree
);
1901 MR_iterateOverTree(truncatedTree
,&tokensInChain
[1]); /* <===== */
1902 Tfree(truncatedTree
);
1904 MR_iterateOverTree(t
,tokensInChain
); /* <===== */
1910 fprintf(stdout
,"\n");
1911 MR_AmbSourceSearch
=0;
1912 MR_MaintainBackTrace
=0;
1913 MR_AmbSourceSearchGroup
=0;
1914 MR_AmbSourceSearchChoice
=0;
1915 MR_AmbSourceSearchLimit
=0;
1920 /* this if for k=1 grammars only
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
1928 void MR_traceAmbSource(set
*matchSets
,Junction
*alt1
, Junction
*alt2
)
1930 void MR_traceAmbSource(matchSets
,alt1
,alt2
)
1946 if (MR_AmbAidRule
== NULL
) return;
1948 strcmp(MR_AmbAidRule
,alt1
->rname
) == 0 ||
1949 strcmp(MR_AmbAidRule
,alt2
->rname
) == 0 ||
1950 MR_AmbAidLine
==alt1
->line
||
1951 MR_AmbAidLine
==alt2
->line
1955 MR_matched_AmbAidRule
++;
1959 dup_matchSets
=(set
*) calloc(CLL_k
+1,sizeof(set
));
1960 require (dup_matchSets
!= NULL
,"Can't allocate dup_matchSets");
1962 p
[0]=analysis_point( (Junction
*) alt1
->p1
);
1963 p
[1]=analysis_point( (Junction
*) alt2
->p1
);
1965 fprintf(stdout
,"\n");
1967 fprintf(stdout
," Ambiguity Aid ");
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"),
1974 (MR_AmbAidMultiple
? "-aam" : ""),
1977 for (i
=0 ; i
< 2 ; i
++) {
1978 fprintf(stdout
," Choice %d: %-25s line %d file %s\n",
1980 MR_ruleNamePlusOffset( (Node
*) p
[i
]),
1981 p
[i
]->line
,FileStr
[p
[i
]->file
]);
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
);
1991 fprintf(stdout
,"\n");
1993 require (1 <= MR_AmbAidDepth
&& MR_AmbAidDepth
<= CLL_k
,
1994 "illegal MR_AmbAidDepth");
1996 MR_AmbSourceSearchGroup
=0;
1997 for (depth
=1; depth
<= MR_AmbAidDepth
; depth
++) {
1998 MR_AmbSourceSearchLimit
=depth
;
1999 for (i
=0 ; i
< 2 ; i
++) {
2001 /*** fprintf(stdout," Choice:%d Depth:%d\n\n",i+1,depth); ***/
2003 for (j
=0 ; j
<= CLL_k
; j
++) { dup_matchSets
[j
]=set_dup(matchSets
[j
]); };
2009 MR_AmbSourceSearch
=1;
2010 MR_MaintainBackTrace
=1;
2011 MR_AmbSourceSearchChoice
=i
;
2017 constrain
= &(fset
[1]);
2018 MR_pointerStackReset(&MR_BackTraceStack
);
2020 REACH(p
[i
],depth
,&incomplete
,tokensUsed
);
2025 require (set_nil(incomplete
),"MR_traceAmbSource REACH incomplete");
2026 require (MR_BackTraceStack
.count
== 0,"1: MR_BackTraceStack.count != 0");
2028 set_free(incomplete
);
2029 set_free(tokensUsed
);
2031 for (j
=0 ; j
<= CLL_k
; j
++) { set_free(dup_matchSets
[j
]); };
2035 fprintf(stdout
,"\n");
2037 MR_AmbSourceSearch
=0;
2038 MR_MaintainBackTrace
=0;
2039 MR_AmbSourceSearchGroup
=0;
2040 MR_AmbSourceSearchChoice
=0;
2041 MR_AmbSourceSearchLimit
=0;
2044 free ( (char *) dup_matchSets
);
2047 static int itemCount
;
2049 void MR_backTraceDumpItemReset() {
2054 void MR_backTraceDumpItem(FILE *f
,int skip
,Node
*n
)
2056 void MR_backTraceDumpItem(f
,skip
,n
)
2069 itemCount
++; if (skip
) goto EXIT
;
2071 if (set_nil(tn
->tset
)) {
2072 fprintf(f
," %2d #token %-23s",itemCount
,TerminalString(tn
->token
));
2074 fprintf(f
," %2d #tokclass %-20s",itemCount
,TerminalString(tn
->token
));
2078 itemCount
++; if (skip
) goto EXIT
;
2079 rrn
=(RuleRefNode
*)n
;
2080 fprintf(f
," %2d to %-27s",itemCount
,rrn
->text
);
2092 itemCount
++; if (skip
) goto EXIT
;
2093 fprintf(f
," %2d %-30s",itemCount
,"in (...)? block at");
2096 /****** fprintf(f," %2d %-32s",itemCount,"in (...) block at"); *******/
2097 /****** break; *******/
2100 itemCount
++; if (skip
) goto EXIT
;
2101 fprintf(f
," %2d %-30s",itemCount
,"in {...} block");
2104 itemCount
++; if (skip
) goto EXIT
;
2105 fprintf(f
," %2d %-30s",itemCount
,"in (...)* block");
2108 if (j
->alpha_beta_guess_end
) {
2109 itemCount
++; if (skip
) goto EXIT
;
2110 fprintf(f
," %2d %-30s",itemCount
,"end (...)? block at");
2114 /****** fprintf(f," %2d %-32s",itemCount,"end of a block at"); *****/
2115 /****** break; *****/
2117 itemCount
++; if (skip
) goto EXIT
;
2118 fprintf(f
," %2d %-30s",itemCount
,j
->rname
);
2123 itemCount
++; if (skip
) goto EXIT
;
2124 fprintf (f
," %2d end %-26s",itemCount
,j
->rname
);
2127 itemCount
++; if (skip
) goto EXIT
;
2128 fprintf(f
," %2d %-30s",itemCount
,"in (...)+ block");
2135 fprintf(f
," %-23s line %-4d %s\n",MR_ruleNamePlusOffset(n
),n
->line
,FileStr
[n
->file
]);
2141 static PointerStack previousBackTrace
={0,0,NULL
};
2144 void MR_backTraceReport(void)
2146 void MR_backTraceReport()
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
2167 for (i
=0; i
< MR_BackTraceStack
.count
; i
++) {
2168 p
=(Node
*) MR_BackTraceStack
.data
[i
];
2169 if (p
->ntype
== nToken
) depth
++;
2172 /* MR14 */ if (MR_AmbSourceSearch
) {
2173 /* MR14 */ require (depth
<= MR_AmbSourceSearchLimit
,"depth > MR_AmbSourceSearchLimit");
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) */
2179 if (MR_AmbSourceSearchLimit
== 0 || depth
< MR_AmbSourceSearchLimit
) {
2183 MR_backTraceDumpItemReset();
2185 limitMatch
=MR_BackTraceStack
.count
;
2186 if (limitMatch
> previousBackTrace
.count
) {
2187 limitMatch
=previousBackTrace
.count
;
2190 for (match
=0; match
< limitMatch
; match
++) {
2191 if (MR_BackTraceStack
.data
[match
] !=
2192 previousBackTrace
.data
[match
]) {
2197 /* not sure at the moment why there would be duplicates */
2199 if (match
!= MR_BackTraceStack
.count
) {
2201 fprintf(stdout
," Choice:%d Depth:%d Group:%d",
2202 (MR_AmbSourceSearchChoice
+1),
2203 MR_AmbSourceSearchLimit
,
2204 ++MR_AmbSourceSearchGroup
);
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;
2212 if (depth
!= 0) fprintf(stdout
," ");
2213 fprintf(stdout
, "%s", TerminalString(tn
->token
));
2215 if (! MR_AmbAidMultiple
) {
2216 if (set_nil(tn
->tset
)) {
2217 set_rm( (unsigned) tn
->token
,fset
[depth
]);
2219 remainder
=set_dif(fset
[depth
],tn
->tset
);
2220 set_free(fset
[depth
]);
2221 fset
[depth
]=remainder
;
2225 fprintf(stdout
,")\n");
2227 for (i
=0; i
< MR_BackTraceStack
.count
; i
++) {
2228 MR_backTraceDumpItem(stdout
, (i
<match
) ,(Node
*) MR_BackTraceStack
.data
[i
]);
2230 fprintf(stdout
,"\n");
2233 MR_pointerStackReset(&previousBackTrace
);
2235 for (i
=0; i
< MR_BackTraceStack
.count
; i
++) {
2236 MR_pointerStackPush(&previousBackTrace
,MR_BackTraceStack
.data
[i
]);
2243 void MR_setConstrainPointer(set
* newConstrainValue
)
2245 void MR_setConstrainPointer(newConstrainValue
)
2246 set
* newConstrainValue
;
2249 constrain
=newConstrainValue
;