4 * Compute FIRST and FOLLOW sets.
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
46 static void ensure_predicates_cover_ambiguous_lookahead_sequences
47 (Junction
*, Junction
*, char *, Tree
*);
49 static void ensure_predicates_cover_ambiguous_lookahead_sequences();
53 * What tokens are k tokens away from junction q?
55 * Follow both p1 and p2 paths (unless RuleBlk) to collect the tokens k away from this
57 * We lock the junction according to k--the lookahead. If we have been at this
58 * junction before looking for the same, k, number of lookahead tokens, we will
59 * do it again and again...until we blow up the stack. Locks are only used on aLoopBlk,
60 * RuleBlk, aPlusBlk and EndRule junctions to remove/detect infinite recursion from
61 * FIRST and FOLLOW calcs.
63 * If p->jtype == EndRule we are going to attempt a FOLLOW. (FOLLOWs are really defined
64 * in terms of FIRST's, however). To proceed with the FOLLOW, p->halt cannot be
65 * set. p->halt is set to indicate that a reference to the current rule is in progress
66 * and the FOLLOW is not desirable.
68 * If we attempt a FOLLOW and find that there is no FOLLOW or REACHing beyond the EndRule
69 * junction yields an empty set, replace the empty set with EOF. No FOLLOW means that
70 * only EOF can follow the current rule. This normally occurs only on the start symbol
71 * since all other rules are referenced by another rule somewhere.
73 * Normally, both p1 and p2 are followed. However, checking p2 on a RuleBlk node is
74 * the same as checking the next rule which is clearly incorrect.
76 * Cycles in the FOLLOW sense are possible. e.g. Fo(c) requires Fo(b) which requires
77 * Fo(c). Both Fo(b) and Fo(c) are defined to be Fo(b) union Fo(c). Let's say
78 * Fo(c) is attempted first. It finds all of the FOLLOW symbols and then attempts
79 * to do Fo(b) which finds of its FOLLOW symbols. So, we have:
85 * a set Fo(c) .....Hmmmm..... Infinite recursion!
87 * The 2nd Fo(c) is not attempted and Fo(b) is left deficient, but Fo(c) is now
88 * correctly Fo(c) union Fo(b). We wish to pick up where we left off, so the fact
89 * that Fo(b) terminated early means that we lack Fo(c) in the Fo(b) set already
90 * laying around. SOOOOoooo, we track FOLLOW cycles. All FOLLOW computations are
91 * cached in a hash table. After the sequence of FOLLOWs finish, we reconcile all
92 * cycles --> correct all Fo(rule) sets in the cache.
94 * Confused? Good! Read my MS thesis [Purdue Technical Report TR90-30].
95 * TJP 8/93 -- can now read PhD thesis from Purdue.
97 * Also, FIRST sets are cached in the hash table. Keys are (rulename,Fi/Fo,k).
98 * Only FIRST sets, for which the FOLLOW is not included, are stored.
100 * SPECIAL CASE of (...)+ blocks:
101 * I added an optional alt so that the alts could see what
102 * was behind the (...)+ block--thus using enough lookahead
103 * to branch out rather than just enough to distinguish
104 * between alts in the (...)+. However, when the FIRST("(...)+") is
105 * is needed, must not use this last "optional" alt. This routine
106 * turns off this path by setting a new 'ignore' flag for
107 * the alt and then resetting it afterwards.
112 rJunc( Junction
*p
, int k
, set
*rk
)
122 require(p
!=NULL
, "rJunc: NULL node");
123 require(p
->ntype
==nJunction
, "rJunc: not junction");
126 if ( p
->jtype
== RuleBlk
) fprintf(stderr
, "FIRST(%s,%d) \n",((Junction
*)p
)->rname
,k
);
127 else fprintf(stderr
, "rJunc: %s in rule %s\n",
128 decodeJType
[p
->jtype
], ((Junction
*)p
)->rname
);
130 /* if this is one of the added optional alts for (...)+ then return */
132 /* no need to pop backtrace - hasn't been pushed */
134 if ( p
->ignore
) return empty
;
136 if (MR_MaintainBackTrace
) MR_pointerStackPush(&MR_BackTraceStack
,p
);
138 /* MR14 */ if (AlphaBetaTrace
&& p
->alpha_beta_guess_end
) {
140 /* MR14 */ "not possible to compute follow set for alpha in an \"(alpha)? beta\" block. ",
141 /* MR14 */ FileStr
[p
->file
],p
->line
);
142 /* MR14 */ MR_alphaBetaTraceReport();
145 /* MR14 */ if (p
->alpha_beta_guess_end
) {
146 /* MR14 */ if (MR_MaintainBackTrace
) MR_pointerStackPop(&MR_BackTraceStack
);
147 /* MR14 */ return empty
;
150 /* locks are valid for aLoopBlk,aPlusBlk,RuleBlk,EndRule junctions only */
151 if ( p
->jtype
==aLoopBlk
|| p
->jtype
==RuleBlk
||
152 p
->jtype
==aPlusBlk
|| p
->jtype
==EndRule
)
154 require(p
->lock
!=NULL
, "rJunc: lock array is NULL");
157 if ( p
->jtype
== EndRule
) /* FOLLOW cycle? */
160 fprintf(stderr
, "FOLLOW cycle to %s: panic!\n", p
->rname
);
162 if (! MR_AmbSourceSearch
) RegisterCycle(p
->rname
, k
);
164 if (MR_MaintainBackTrace
) MR_pointerStackPop(&MR_BackTraceStack
);
167 if ( p
->jtype
== RuleBlk
&&
169 ! MR_AmbSourceSearch
) /* check for FIRST cache */
171 CacheEntry
*q
= (CacheEntry
*) hash_get(Fcache
, Fkey(p
->rname
,'i',k
));
175 if (MR_MaintainBackTrace
) MR_pointerStackPop(&MR_BackTraceStack
);
176 return set_dup( q
->fset
);
179 if ( p
->jtype
== EndRule
&&
180 !p
->halt
&& /* MR11 was using cache even when halt set */
181 ! MR_AmbSourceSearch
) /* FOLLOW set cached already? */
183 CacheEntry
*q
= (CacheEntry
*) hash_get(Fcache
, Fkey(p
->rname
,'o',k
));
187 fprintf(stderr
, "cache for FOLLOW(%s,%d):", p
->rname
,k
);
188 s_fprT(stderr
, q
->fset
);
189 if ( q
->incomplete
) fprintf(stderr
, " (incomplete)");
190 fprintf(stderr
, "\n");
192 if ( !q
->incomplete
)
194 if (MR_MaintainBackTrace
) MR_pointerStackPop(&MR_BackTraceStack
);
195 return set_dup( q
->fset
);
199 p
->lock
[k
] = TRUE
; /* This rule is busy */
204 if ( p
->jtype
== EndRule
)
206 if (p
->halt
) /* don't want FOLLOW here? */ /* unless MR10 hoisting */
209 set_orel(k
, rk
); /* indicate this k value needed */
210 if (MR_MaintainBackTrace
) MR_pointerStackPop(&MR_BackTraceStack
);
213 if (! MR_AmbSourceSearch
) FoPush(p
->rname
, k
); /* Attempting FOLLOW */
214 if ( p
->p1
== NULL
) set_orel((TokenInd
!=NULL
?TokenInd
[EofToken
]:EofToken
), &a
);/* if no FOLLOW assume EOF */
216 fprintf(stderr
, "-->FOLLOW(%s,%d)\n", p
->rname
,k
);
220 if ( p
->p1
!= NULL
) {
221 /* MR14 */ if (p
->guess
) {
222 /* MR14 */ if (p
->guess_analysis_point
== NULL
) {
223 /* MR14 */ Node
* guess_point
;
224 /* MR14 */ guess_point
=(Node
*)analysis_point(p
);
225 /* MR14 */ if (guess_point
== (Node
*)p
) {
226 /* MR14 */ guess_point
=p
->p1
;
228 /* MR14 */ p
->guess_analysis_point
=guess_point
;
230 /* MR14 */ REACH(p
->guess_analysis_point
, k
, rk
, a
);
232 REACH(p
->p1
, k
, rk
, a
);
236 /* C a c h e R e s u l t s */
238 if ( p
->jtype
== RuleBlk
&& p
->end
->halt
&& ! MR_AmbSourceSearch
) /* can save FIRST set? */
240 CacheEntry
*q
= newCacheEntry( Fkey(p
->rname
,'i',k
) );
241 /*fprintf(stderr, "Caching %s FIRST %d\n", p->rname, k);*/
242 hash_add(Fcache
, Fkey(p
->rname
,'i',k
), (Entry
*)q
);
243 q
->fset
= set_dup( a
);
244 q
->rk
= set_dup( *rk
);
247 if ( p
->jtype
== EndRule
&&
248 !p
->halt
&& /* MR11 was using cache even with halt set */
249 ! MR_AmbSourceSearch
) /* just completed FOLLOW? */
251 /* Cache Follow set */
252 CacheEntry
*q
= (CacheEntry
*) hash_get(Fcache
, Fkey(p
->rname
,'o',k
));
255 q
= newCacheEntry( Fkey(p
->rname
,'o',k
) );
256 hash_add(Fcache
, Fkey(p
->rname
,'o',k
), (Entry
*)q
);
258 /*fprintf(stderr, "Caching %s FOLLOW %d\n", p->rname, k);*/
259 if ( set_nil(a
) && !q
->incomplete
)
261 /* Don't ever save a nil set as complete.
262 * Turn it into an eof set.
264 set_orel(EofToken
, &a
);
266 set_orin(&(q
->fset
), a
);
268 if ( FoTOS
[k
] == NULL
&& Cycles
[k
] != NULL
) ResolveFoCycles(k
);
270 fprintf(stderr
, "saving FOLLOW(%s,%d):", p
->rname
, k
);
271 s_fprT(stderr
, q
->fset
);
272 if ( q
->incomplete
) fprintf(stderr
, " (incomplete)");
273 fprintf(stderr
, "\n");
277 if (p
->jtype
!= RuleBlk
&& p
->p2
!= NULL
&& /* MR14 */ ! p
->guess
) {
278 REACH(p
->p2
, k
, rk
, b
);
281 if ( p
->jtype
==aLoopBlk
|| p
->jtype
==RuleBlk
||
282 p
->jtype
==aPlusBlk
|| p
->jtype
==EndRule
)
283 p
->lock
[k
] = FALSE
; /* unlock node */
287 if (MR_MaintainBackTrace
) MR_pointerStackPop(&MR_BackTraceStack
);
293 rRuleRef( RuleRefNode
*p
, int k
, set
*rk_out
)
295 rRuleRef( p
, k
, rk_out
)
306 RuleEntry
*q
= (RuleEntry
*) hash_get(Rname
, p
->text
);
307 require(p
!=NULL
, "rRuleRef: NULL node");
308 require(p
->ntype
==nRuleRef
, "rRuleRef: not rule ref");
311 fprintf(stderr
, "rRuleRef: %s\n", p
->text
);
314 if (MR_MaintainBackTrace
) MR_pointerStackPush(&MR_BackTraceStack
,p
);
318 warnFL( eMsg1("rule %s not defined",p
->text
), FileStr
[p
->file
], p
->line
);
319 REACH(p
->next
, k
, rk_out
, a
);
320 if (MR_MaintainBackTrace
) MR_pointerStackPop(&MR_BackTraceStack
);
325 /* MR9 Problems with rule references in guarded predicates */
326 /* MR9 Perhaps can use hash table to find rule ? */
328 /* MR9 */ if (RulePtr
== NULL
) {
329 /* MR9 */ fatalFL(eMsg2("Rule %s uses rule %s via RulePtr before it has been initialized",
330 /* MR9 */ p
->rname
,q
->str
),FileStr
[p
->file
],p
->line
);
333 r
= RulePtr
[q
->rulenum
];
336 errNoFL( eMsg2("infinite left-recursion to rule %s from rule %s",
337 r
->rname
, p
->rname
) );
339 if (MR_MaintainBackTrace
) MR_pointerStackPop(&MR_BackTraceStack
);
344 save_halt
= r
->end
->halt
;
345 r
->end
->halt
= TRUE
; /* don't let reach fall off end of rule here */
348 r
->end
->halt
= save_halt
;
349 while ( !set_nil(rk
) ) {
350 k2
= set_int(rk
); /* MR11 this messes up the ambiguity search routine */
352 REACH(p
->next
, k2
, &rk2
, b
); /* MR11 by changing the value of k */
356 set_free(rk
); /* this has no members, but free its memory */
357 set_orin(rk_out
, rk2
); /* remember what we couldn't do */
359 if (MR_MaintainBackTrace
) MR_pointerStackPop(&MR_BackTraceStack
);
364 * Return FIRST sub k ( token_node )
366 * TJP 10/11/93 modified this so that token nodes that are actually
367 * ranges (T1..T2) work.
371 rToken( TokNode
*p
, int k
, set
*rk
)
381 require(p
!=NULL
, "rToken: NULL node");
382 require(p
->ntype
==nToken
, "rToken: not token node");
385 fprintf(stderr
, "rToken: %s\n", (TokenString(p
->token
)!=NULL
)?TokenString(p
->token
):
386 ExprString(p
->token
));
390 if (MR_MaintainBackTrace
) MR_pointerStackPush(&MR_BackTraceStack
,p
);
392 if (MR_AmbSourceSearch
&& (k
-1) == 0) {
397 localConstrain
=fset
[maxk
-k
+1];
399 if (! set_nil(p
->tset
)) {
400 intersection
=set_and(localConstrain
,p
->tset
);
401 if (! set_nil(intersection
)) {
402 MR_backTraceReport();
404 set_free(intersection
);
406 if (set_el( (unsigned) p
->token
,localConstrain
)) {
407 MR_backTraceReport();
414 if (MR_MaintainBackTrace
) MR_pointerStackPop(&MR_BackTraceStack
);
416 if ( !set_nil(p
->tset
) ) {
417 return set_dup(p
->tset
);
419 return set_of(p
->token
);
423 REACH(p
->next
, k
-1, rk
, a
);
425 if (MR_MaintainBackTrace
) MR_pointerStackPop(&MR_BackTraceStack
);
432 rAction( ActionNode
*p
, int k
, set
*rk
)
442 require(p
!=NULL
, "rJunc: NULL node");
443 require(p
->ntype
==nAction
, "rJunc: not action");
445 /* MR11 */ if (p
->is_predicate
&& p
->ampersandPred
!= NULL
) {
446 /* MR11 */ Predicate
*pred
=p
->ampersandPred
;
447 /* MR11 */ if (k
<= pred
->k
) {
448 /* MR11 */ REACH(p
->guardNodes
,k
,rk
,a
);
453 /* it might be a good idea when doing an MR_AmbSourceSearch
454 to *not* look behind predicates under some circumstances
455 we'll look into that later
458 REACH(p
->next
, k
, rk
, a
); /* ignore actions */
462 /* A m b i g u i t y R e s o l u t i o n */
467 dumpAmbigMsg( set
*fset
, FILE *f
, int want_nls
)
469 dumpAmbigMsg( fset
, f
, want_nls
)
479 if ( want_nls
) fprintf(f
, "\n\t");
480 else fprintf(f
, " ");
482 for (i
=1; i
<=CLL_k
; i
++)
484 copy
=set_dup(fset
[i
]); /* MR11 */
488 if ( !want_nls
) fprintf(f
, ", ");
490 if ( set_deg(copy
) > 3 && elevel
== 1 )
497 fprintf(f
, " %s", TerminalString(e
));
500 fprintf(f
, " ... }");
502 else s_fprT(f
, copy
);
503 if ( want_nls
) fprintf(f
, "\n\t");
512 verify_context(Predicate
*predicate
)
514 verify_context(predicate
)
515 Predicate
*predicate
;
518 if ( predicate
== NULL
) return;
520 if ( predicate
->expr
== PRED_OR_LIST
||
521 predicate
->expr
== PRED_AND_LIST
)
523 verify_context(predicate
->down
);
524 verify_context(predicate
->right
); /* MR10 */
528 if ( !predicate
->source
->ctxwarned
&& predicate
->source
->guardpred
==NULL
&&
529 ((predicate
->k
> 1 &&
530 !is_single_tuple(predicate
->tcontext
)) ||
531 ( predicate
->k
== 1 &&
532 set_deg(predicate
->scontext
[1])>1 )) )
535 /* MR9 Suppress annoying messages caused by our own clever(?) fix */
537 fprintf(stderr
, ErrHdr
, FileStr
[predicate
->source
->file
],
538 predicate
->source
->line
);
539 fprintf(stderr
, " warning: predicate applied for >1 lookahead %d-sequences\n", predicate
->k
);
540 fprintf(stderr
, ErrHdr
, FileStr
[predicate
->source
->file
],
541 predicate
->source
->line
);
542 fprintf(stderr
, " predicate text: \"%s\"\n",
543 (predicate
->expr
== NULL
? "(null)" : predicate
->expr
) );
544 fprintf(stderr
, ErrHdr
, FileStr
[predicate
->source
->file
],
545 predicate
->source
->line
);
546 fprintf(stderr
, " You may only want one lookahead %d-sequence to apply\n", predicate
->k
);
547 fprintf(stderr
, ErrHdr
, FileStr
[predicate
->source
->file
],
548 predicate
->source
->line
);
549 fprintf(stderr
, " Try using a context guard '(...)? =>'\n");
550 predicate
->source
->ctxwarned
= 1;
552 verify_context(predicate
->right
); /* MR10 */
556 * If delta is the set of ambiguous lookahead sequences, then make sure that
557 * the predicate(s) for productions alt1,alt2 cover the sequences in delta.
560 * a : <<PRED1>>? (A B|A C)
567 * This should give a warning that (A C) predicts both productions and alt2
568 * does not have a predicate in the production that generates (A C).
570 * The warning detection is simple. Let delta = LOOK(alt1) intersection LOOK(alt2).
571 * Now, if ( delta set-difference context(predicates-for-alt1) != empty then
572 * alt1 does not "cover" all ambiguous sequences.
574 * If ambig is nonempty, then ambig in LL(k) sense -> use tree info; else use fset
575 * info. Actually, sets are used only if k=1 for this grammar.
579 ensure_predicates_cover_ambiguous_lookahead_sequences
580 ( Junction
*alt1
, Junction
*alt2
, char *sub
, Tree
*ambig
)
582 ensure_predicates_cover_ambiguous_lookahead_sequences( alt1
, alt2
, sub
, ambig
)
589 if ( !ParseWithPredicates
) return;
593 Tree
*non_covered
= NULL
;
594 if ( alt1
->predicate
!=NULL
)
595 non_covered
= tdif(ambig
, alt1
->predicate
, alt1
->fset
, alt2
->fset
);
596 if ( (non_covered
!=NULL
|| alt1
->predicate
==NULL
) && WarningLevel
>1 )
598 fprintf(stderr
, ErrHdr
, FileStr
[alt1
->file
], alt1
->line
);
599 fprintf(stderr
, " warning: alt %d %shas no predicate to resolve ambiguity",
601 if ( alt1
->predicate
!=NULL
&& non_covered
!=NULL
)
603 fprintf(stderr
, " upon");
604 preorder(non_covered
);
606 else if ( alt1
->predicate
==NULL
)
608 fprintf(stderr
, " upon");
609 preorder(ambig
->down
);
611 fprintf(stderr
, "\n");
615 if ( alt2
->predicate
!=NULL
)
616 non_covered
= tdif(ambig
, alt2
->predicate
, alt1
->fset
, alt2
->fset
);
617 if ( (non_covered
!=NULL
|| alt2
->predicate
==NULL
) && WarningLevel
>1 )
619 fprintf(stderr
, ErrHdr
, FileStr
[alt2
->file
], alt2
->line
);
620 fprintf(stderr
, " warning: alt %d %shas no predicate to resolve ambiguity",
622 if ( alt2
->predicate
!=NULL
&& non_covered
!=NULL
)
624 fprintf(stderr
, " upon");
625 preorder(non_covered
);
627 else if ( alt2
->predicate
==NULL
)
629 fprintf(stderr
, " upon");
630 preorder(ambig
->down
);
632 fprintf(stderr
, "\n");
636 else if ( !set_nil(alt1
->fset
[1]) )
638 set delta
, non_covered
;
639 delta
= set_and(alt1
->fset
[1], alt2
->fset
[1]);
640 non_covered
= set_dif(delta
, covered_set(alt1
->predicate
));
641 if ( set_deg(non_covered
)>0 && WarningLevel
>1 )
643 fprintf(stderr
, ErrHdr
, FileStr
[alt1
->file
], alt1
->line
);
644 fprintf(stderr
, " warning: alt %d %shas no predicate to resolve ambiguity",
646 if ( alt1
->predicate
!=NULL
)
648 fprintf(stderr
, " upon ");
649 s_fprT(stderr
, non_covered
);
651 fprintf(stderr
, "\n");
653 set_free( non_covered
);
654 non_covered
= set_dif(delta
, covered_set(alt2
->predicate
));
655 if ( set_deg(non_covered
)>0 && WarningLevel
>1 )
657 fprintf(stderr
, ErrHdr
, FileStr
[alt2
->file
], alt2
->line
);
658 fprintf(stderr
, " warning: alt %d %shas no predicate to resolve ambiguity",
660 if ( alt2
->predicate
!=NULL
)
662 fprintf(stderr
, " upon ");
663 s_fprT(stderr
, non_covered
);
665 fprintf(stderr
, "\n");
667 set_free( non_covered
);
670 else fatal_internal("productions have no lookahead in predicate checking routine");
674 void MR_doPredicatesHelp(int inGuessBlock
,Junction
*alt1
,Junction
*alt2
,int jtype
,char *sub
)
676 void MR_doPredicatesHelp(inGuessBlock
,alt1
,alt2
,jtype
,sub
)
687 Junction
*parentRule
=MR_nameToRuleBlk(alt1
->rname
);
689 if (inGuessBlock
&& WarningLevel
<= 1) return;
691 /* let antlr give the usual error message */
693 if (alt1
->predicate
== NULL
&& alt2
->predicate
== NULL
) return;
695 if ( (jtype
== RuleBlk
|| jtype
== aSubBlk
)
696 && (alt1
->predicate
== NULL
&& alt2
->predicate
!= NULL
)) {
697 fprintf(stderr
, ErrHdr
, FileStr
[parentRule
->file
],parentRule
->line
);
698 fprintf(stderr
," warning: alt %d line %d and alt %d line %d of %s\n%s%s%s",
704 " These alts have ambig lookahead sequences resolved by a predicate for\n",
705 " the second choice. The second choice may not be reachable.\n",
706 " You may want to use a complementary predicate or rearrange the alts\n"
711 /* first do the easy comparison. then do the hard one */
713 if (MR_comparePredicates(alt1
->predicate
,alt2
->predicate
)) {
715 if (jtype
== aLoopBegin
|| jtype
== aPlusBlk
) {
717 /* I'm not sure this code is reachable.
718 Predicates following a (...)+ or (...)* block are probably
719 considered validation predicates and therefore not
720 participate in the predication expression
723 fprintf(stderr
, ErrHdr
,FileStr
[parentRule
->file
],parentRule
->line
);
724 fprintf(stderr
," warning: %s of %s in rule %s\n (file %s alt %d line %d and alt %d line %d)\n%s",
725 "the predicates used to disambiguate optional/exit paths of ",
733 " are identical and have no resolving power\n");
735 fprintf(stderr
, ErrHdr
, FileStr
[parentRule
->file
], parentRule
->line
);
736 fprintf(stderr
," warning: %s rule %s\n (file %s alt %d line %d and alt %d line %d)\n%s",
737 "the predicates used to disambiguate",
744 " are identical and have no resolving power\n");
747 p1
=predicate_dup_without_context(alt1
->predicate
);
749 MR_clearPredEntry(p1
);
750 MR_simplifyInverted(p1
,0);
751 p1
=MR_predSimplifyALL(p1
);
752 p2
=predicate_dup_without_context(alt2
->predicate
);
754 MR_clearPredEntry(p2
);
755 MR_simplifyInverted(p2
,0);
756 p2
=MR_predSimplifyALL(p2
);
757 if (MR_comparePredicates(p1
,p2
)) {
758 if (jtype
== aLoopBegin
|| jtype
== aPlusBlk
) {
759 fprintf(stderr
, ErrHdr
, FileStr
[parentRule
->file
], parentRule
->line
);
760 fprintf(stderr
," warning: %s of %s in rule %s\n (file %s alt %d line %d and alt %d line %d)\n%s%s",
761 "the predicates used to disambiguate optional/exit paths of ",
769 " are identical when compared without context and may have no\n",
770 " resolving power for some lookahead sequences.\n");
772 fprintf(stderr
, ErrHdr
, FileStr
[parentRule
->file
], parentRule
->line
);
773 fprintf(stderr
," warning: %s rule %s\n (file %s alt %d line %d and alt %d line %d)\n%s%s",
774 "the predicates used to disambiguate",
781 " are identical when compared without context and may have no\n",
782 " resolving power for some lookahead sequences.\n");
785 fprintf(output
,"\n#if 0\n\n");
786 fprintf(output
,"The following predicates are identical when compared without\n");
787 fprintf(output
," lookahead context information. For some ambiguous lookahead\n");
788 fprintf(output
," sequences they may not have any power to resolve the ambiguity.\n");
789 fprintf(output
,"\n");
791 fprintf(output
,"Choice 1: %s alt %d line %d file %s\n\n",
792 MR_ruleNamePlusOffset( (Node
*) alt1
),
795 FileStr
[alt1
->file
]);
796 fprintf(output
," The original predicate for choice 1 with available context information:\n\n");
797 MR_dumpPred1(2,alt1
->predicate
,1);
798 fprintf(output
," The predicate for choice 1 after expansion (but without context information):\n\n");
799 MR_dumpPred1(2,p1
,0);
802 fprintf(output
," The predicate for choice 1 after expansion (but before simplification)\n\n");
803 phelp
=predicate_dup_without_context(alt1
->predicate
);
804 phelp
=MR_unfold(phelp
);
805 MR_clearPredEntry(phelp
);
806 MR_simplifyInverted(phelp
,0);
807 phelp
=MR_predSimplifyALLX(phelp
,1);
808 MR_dumpPred1(2,phelp
,0);
809 predicate_free(phelp
);
811 fprintf(output
,"\n");
813 fprintf(output
,"Choice 2: %s alt %d line %d file %s\n\n",
814 MR_ruleNamePlusOffset( (Node
*) alt2
),
817 FileStr
[alt2
->file
]);
818 fprintf(output
," The original predicate for choice 2 with available context information:\n\n");
819 MR_dumpPred1(1,alt2
->predicate
,1);
820 fprintf(output
," The predicate for choice 2 after expansion (but without context information):\n\n");
821 MR_dumpPred1(1,p2
,0);
824 fprintf(output
," The predicate for choice 2 after expansion (but before simplification)\n\n");
825 phelp
=predicate_dup_without_context(alt2
->predicate
);
826 phelp
=MR_unfold(phelp
);
827 MR_clearPredEntry(phelp
);
828 MR_simplifyInverted(phelp
,0);
829 phelp
=MR_predSimplifyALLX(phelp
,1);
830 MR_dumpPred1(2,phelp
,0);
831 predicate_free(phelp
);
833 fprintf(output
,"\n#endif\n");
835 } else if (MR_secondPredicateUnreachable(p1
,p2
)) {
836 if (jtype
== aLoopBegin
|| jtype
== aPlusBlk
) {
837 fprintf(stderr
, ErrHdr
, FileStr
[parentRule
->file
], parentRule
->line
);
838 fprintf(stderr
," warning: %s of %s in rule %s\n (file %s alt %d line %d and alt %d line %d)\n%s%s",
839 "the predicate used to disambiguate the first choice of the optional/exit paths of ",
847 " appears to \"cover\" the second predicate when compared without context.\n",
848 " The second predicate may have no resolving power for some lookahead sequences.\n");
850 fprintf(stderr
, ErrHdr
, FileStr
[parentRule
->file
], parentRule
->line
);
851 fprintf(stderr
," warning: %s rule %s\n (file %s alt %d line %d and alt %d line %d)\n%s%s",
852 "the predicate used to disambiguate the first choice of",
859 " appears to \"cover\" the second predicate when compared without context.\n",
860 " The second predicate may have no resolving power for some lookahead sequences.\n");
863 fprintf(output
,"\n#if 0\n\n");
864 fprintf(output
,"The first predicate appears to \"cover\" the second predicate when they\n");
865 fprintf(output
," are compared without lookahead context information. For some ambiguous\n");
866 fprintf(output
," lookahead sequences the second predicate may not have any power to\n");
867 fprintf(output
," resolve the ambiguity.\n");
868 fprintf(output
,"\n");
869 fprintf(output
,"Choice 1: %s alt %d line %d file %s\n\n",
870 MR_ruleNamePlusOffset( (Node
*) alt1
),
873 FileStr
[alt1
->file
]);
874 fprintf(output
," The original predicate for choice 1 with available context information:\n\n");
875 MR_dumpPred1(2,alt1
->predicate
,1);
876 fprintf(output
," The predicate for choice 1 after expansion (but without context information):\n\n");
877 MR_dumpPred1(2,p1
,0);
880 fprintf(output
," The predicate for choice 1 after expansion (but before simplification)\n\n");
881 phelp
=predicate_dup_without_context(alt1
->predicate
);
882 phelp
=MR_unfold(phelp
);
883 MR_clearPredEntry(phelp
);
884 MR_simplifyInverted(phelp
,0);
885 phelp
=MR_predSimplifyALLX(phelp
,1);
886 MR_dumpPred1(2,phelp
,0);
887 predicate_free(phelp
);
889 fprintf(output
,"\n");
891 fprintf(output
,"Choice 2: %s alt %d line %d file %s\n\n",
892 MR_ruleNamePlusOffset( (Node
*) alt2
),
895 FileStr
[alt2
->file
]);
896 fprintf(output
," The original predicate for choice 2 with available context information:\n\n");
897 MR_dumpPred1(1,alt2
->predicate
,1);
898 fprintf(output
," The predicate for choice 2 after expansion (but without context information):\n\n");
899 MR_dumpPred1(1,p2
,0);
902 fprintf(output
," The predicate for choice 2 after expansion (but before simplification)\n\n");
903 phelp
=predicate_dup_without_context(alt2
->predicate
);
904 phelp
=MR_unfold(phelp
);
905 MR_clearPredEntry(phelp
);
906 MR_simplifyInverted(phelp
,0);
907 phelp
=MR_predSimplifyALLX(phelp
,1);
908 MR_dumpPred1(2,phelp
,0);
909 predicate_free(phelp
);
911 fprintf(output
,"\n#endif\n");
919 static int totalOverflow
=0; /* MR9 */
923 HandleAmbiguity( Junction
*block
, Junction
*alt1
, Junction
*alt2
, int jtype
)
925 HandleAmbiguity( block
, alt1
, alt2
, jtype
)
935 Tree
*ambig
=NULL
, *t
, *u
;
938 int thisOverflow
=0; /* MR9 */
939 long set_deg_value
; /* MR10 */
940 long threshold
; /* MR10 */
942 require(block
!=NULL
, "NULL block");
943 require(block
->ntype
==nJunction
, "invalid block");
945 /* These sets are used to constrain LL_k set, but are made CLL_k long anyway */
946 fset
= (set
*) calloc(CLL_k
+1, sizeof(set
));
947 require(fset
!=NULL
, "cannot allocate fset");
948 ftbl
= (unsigned **) calloc(CLL_k
+1, sizeof(unsigned *));
949 require(ftbl
!=NULL
, "cannot allocate ftbl");
951 /* create constraint table and count number of possible ambiguities (use<=LL_k) */
952 for (n
=1,i
=1; i
<=CLL_k
; i
++)
954 b
= set_and(alt1
->fset
[i
], alt2
->fset
[i
]);
955 /* MR9 */ set_deg_value
= set_deg(b
);
956 /* MR10 */ if (n
> 0) {
957 /* MR10 */ threshold
= LONG_MAX
/ n
;
958 /* MR10 */ if (set_deg_value
<= threshold
) {
959 /* MR10 */ n
*= set_deg_value
;
961 /* MR10 */ n
=LONG_MAX
;
962 /* MR9 */ if (totalOverflow
== 0) {
964 /* MR10 comment this out because it just makes users worry */
966 /* MR9 */ warnNoFL("Overflow in computing number of possible ambiguities in HandleAmbiguity\n");
969 /* MR9 */ thisOverflow
++;
970 /* MR9 */ totalOverflow
++;
973 /* MR10 */ n
*= set_deg_value
;
975 fset
[i
] = set_dup(b
);
976 ftbl
[i
] = set_pdq(b
);
982 case aSubBlk
: sub
= "of (..) "; break;
983 case aOptBlk
: sub
= "of {..} "; break;
984 case aLoopBegin
: sub
= "of (..)* "; break;
985 case aLoopBlk
: sub
= "of (..)* "; break;
986 case aPlusBlk
: sub
= "of (..)+ "; break;
987 case RuleBlk
: sub
= "of the rule itself "; break;
988 default : sub
= ""; break;
991 /* If the block is marked as a compressed lookahead only block, then
992 * simply return; ambiguity warning is given only at warning level 2.
994 if ( block
->approx
>0 )
996 if ( ParseWithPredicates
)
998 if (alt1
->predicate
!= NULL
) predicate_free(alt1
->predicate
); /* MR12 */
999 if (alt2
->predicate
!= NULL
) predicate_free(alt2
->predicate
); /* MR12 */
1001 require(MR_PredRuleRefStack
.count
== 0,"PredRuleRef stack not empty");
1002 alt1
->predicate
= MR_find_predicates_and_supp((Node
*)alt1
->p1
);
1003 require(MR_PredRuleRefStack
.count
== 0,"PredRuleRef stack not empty");
1004 require (MR_predicate_context_completed(alt1
->predicate
),"predicate alt 1 not completed");
1005 alt1
->predicate
=MR_predSimplifyALL(alt1
->predicate
);
1007 require(MR_PredRuleRefStack
.count
== 0,"PredRuleRef stack not empty");
1008 alt2
->predicate
= MR_find_predicates_and_supp((Node
*)alt2
->p1
);
1009 require(MR_PredRuleRefStack
.count
== 0,"PredRuleRef stack not empty");
1010 require (MR_predicate_context_completed(alt2
->predicate
),"predicate alt 2 not completed");
1011 alt2
->predicate
=MR_predSimplifyALL(alt2
->predicate
);
1013 MR_doPredicatesHelp(0,alt1
,alt2
,jtype
,sub
);
1015 if ( HoistPredicateContext
1016 && (alt1
->predicate
!=NULL
||alt2
->predicate
!=NULL
) )
1018 verify_context(alt1
->predicate
);
1019 verify_context(alt2
->predicate
);
1022 if ( HoistPredicateContext
1023 && (alt1
->predicate
!=NULL
||alt2
->predicate
!=NULL
)
1025 ensure_predicates_cover_ambiguous_lookahead_sequences(alt1
, alt2
, sub
, ambig
);
1028 if ( WarningLevel
>1 )
1030 fprintf(stderr
, ErrHdr
, FileStr
[alt1
->file
], alt1
->line
);
1031 if ( jtype
== aLoopBegin
|| jtype
== aPlusBlk
)
1032 fprintf(stderr
, " warning: optional/exit path and alt(s) %sambiguous upon", sub
);
1034 fprintf(stderr
, " warning(approx): alts %d and %d %sambiguous upon",
1035 alt1
->altnum
, alt2
->altnum
, sub
);
1036 dumpAmbigMsg(fset
, stderr
, 0);
1037 MR_traceAmbSource(fset
,alt1
,alt2
);
1039 for (i
=1; i
<=CLL_k
; i
++) set_free( fset
[i
] );
1041 for (i
=1; i
<=CLL_k
; i
++) free( (char *)ftbl
[i
] );
1046 /* if all sets have degree 1 for k<LL_k, then must be ambig upon >=1 permutation;
1047 * don't bother doing full LL(k) analysis.
1048 * (This "if" block handles the LL(1) case)
1052 for (i
=1; i
<LL_k
; i
++) n2
+= set_deg(alt1
->fset
[i
])+set_deg(alt2
->fset
[i
]);
1054 /* here STARTS the special case in which the lookahead sets for alt1 and alt2
1055 all have degree 1 for k<LL_k (including LL_k=1)
1058 if ( n2
==2*(LL_k
-1) )
1061 /* TJP: added to fix the case where LL(1) and syntactic predicates didn't
1062 * work. It now recognizes syntactic predicates, but does not like combo:
1063 * LL(1)/syn/sem predicates. (10/24/93)
1066 if ( first_item_is_guess_block_extra((Junction
*)alt1
->p1
)!=NULL
)
1068 if ( WarningLevel
==1 )
1070 for (i
=1; i
<=CLL_k
; i
++) set_free( fset
[i
] );
1072 for (i
=1; i
<=CLL_k
; i
++) free( (char *)ftbl
[i
] );
1077 fprintf(stderr
, ErrHdr
, FileStr
[alt1
->file
], alt1
->line
);
1078 if ( jtype
== aLoopBegin
|| jtype
== aPlusBlk
)
1079 fprintf(stderr
, " warning: optional/exit path and alt(s) %sambiguous upon", sub
);
1081 fprintf(stderr
, " warning: alts %d and %d %sambiguous upon",
1082 alt1
->altnum
, alt2
->altnum
, sub
);
1083 dumpAmbigMsg(fset
, stderr
, 0);
1084 MR_traceAmbSource(fset
,alt1
,alt2
);
1088 if ( LL_k
>1 ) ambig
= make_tree_from_sets(alt1
->fset
, alt2
->fset
);
1089 if ( ParseWithPredicates
)
1091 if (alt1
->predicate
!= NULL
) predicate_free(alt1
->predicate
); /* MR12 */
1092 if (alt2
->predicate
!= NULL
) predicate_free(alt2
->predicate
); /* MR12 */
1094 require(MR_PredRuleRefStack
.count
== 0,"PredRuleRef stack not empty");
1095 alt1
->predicate
= MR_find_predicates_and_supp((Node
*)alt1
->p1
);
1096 require(MR_PredRuleRefStack
.count
== 0,"PredRuleRef stack not empty");
1097 require (MR_predicate_context_completed(alt1
->predicate
),"predicate alt 1 not completed");
1098 alt1
->predicate
=MR_predSimplifyALL(alt1
->predicate
);
1100 require(MR_PredRuleRefStack
.count
== 0,"PredRuleRef stack not empty");
1101 alt2
->predicate
= MR_find_predicates_and_supp((Node
*)alt2
->p1
);
1102 require(MR_PredRuleRefStack
.count
== 0,"PredRuleRef stack not empty");
1103 require (MR_predicate_context_completed(alt2
->predicate
),"predicate alt 2 not completed");
1104 alt2
->predicate
=MR_predSimplifyALL(alt2
->predicate
);
1106 MR_doPredicatesHelp(0,alt1
,alt2
,jtype
,sub
);
1108 if ( HoistPredicateContext
&& (alt1
->predicate
!=NULL
||alt2
->predicate
!=NULL
) )
1110 verify_context(alt1
->predicate
);
1111 verify_context(alt2
->predicate
);
1113 if (HoistPredicateContext
&&(alt1
->predicate
!=NULL
||alt2
->predicate
!=NULL
) && WarningLevel
>1)
1114 ensure_predicates_cover_ambiguous_lookahead_sequences(alt1
, alt2
, sub
, ambig
);
1115 if ( WarningLevel
== 1 &&
1116 (alt1
->predicate
!=NULL
||alt2
->predicate
!=NULL
))
1118 for (i
=1; i
<=CLL_k
; i
++) set_free( fset
[i
] );
1120 for (i
=1; i
<=CLL_k
; i
++) free( (char *)ftbl
[i
] );
1126 /* end TJP (10/24/93) */
1128 fprintf(stderr
, ErrHdr
, FileStr
[alt1
->file
], alt1
->line
);
1129 if ( jtype
== aLoopBegin
|| jtype
== aPlusBlk
)
1130 fprintf(stderr
, " warning: optional/exit path and alt(s) %sambiguous upon", sub
);
1132 fprintf(stderr
, " warning: alts %d and %d %sambiguous upon",
1133 alt1
->altnum
, alt2
->altnum
, sub
);
1134 if ( elevel
== 3 && LL_k
>1 )
1137 fprintf(stderr
, "\n");
1138 for (i
=1; i
<=CLL_k
; i
++) set_free( fset
[i
] );
1140 for (i
=1; i
<=CLL_k
; i
++) free( (char *)ftbl
[i
] );
1147 dumpAmbigMsg(fset
, stderr
, 0);
1149 /* because this is a special case in which both alt1 and alt2 have
1150 lookahead sets of degree 1 for k<LL_k (including k=1) the linear
1151 lookahead style search is adequate
1154 MR_traceAmbSource(fset
,alt1
,alt2
);
1156 for (i
=1; i
<=CLL_k
; i
++) set_free( fset
[i
] );
1158 for (i
=1; i
<=CLL_k
; i
++) free( (char *)ftbl
[i
] );
1163 /* here ENDS the special case in which the lookahead sets for alt1 and alt2
1164 all have degree 1 for k<LL_k (including LL_k=1)
1167 /* in case tree construction runs out of memory, set info to make good err msg */
1169 CurAmbigAlt1
= alt1
->altnum
;
1170 CurAmbigAlt2
= alt2
->altnum
;
1171 CurAmbigbtype
= sub
;
1172 CurAmbigfile
= alt1
->file
;
1173 CurAmbigline
= alt1
->line
;
1175 /* Don't do full LL(n) analysis if (...)? block because the block,
1176 by definition, defies LL(n) analysis.
1177 If guess (...)? block and ambiguous then don't remove anything from
1178 2nd alt to resolve ambig.
1179 Want to predict with LL sup 1 ( n ) decision not LL(n) if guess block
1180 since it is much cheaper than LL(n). LL sup 1 ( n ) "covers" the LL(n)
1181 lookahead information.
1183 Note: LL(n) context cannot be computed for semantic predicates when
1186 If (..)? then we scream "AAAHHHH! No LL(n) analysis will help"
1188 Is 'ambig' always defined if we enter this if? I hope so
1189 because the 'ensure...()' func references it. TJP Nov 1993.
1192 /* THM MR30: Instead of using first_item_is_guss_block we use
1193 first_item_is_guess_block_extra which will look inside a
1194 loop block for a guess block. In other words ( (...)? )*.
1195 It there is an ambiguity in this circumstance then we suppress
1196 the normal methods of resolving ambiguities.
1199 if ( first_item_is_guess_block_extra((Junction
*)alt1
->p1
)!=NULL
)
1201 if ( ParseWithPredicates
)
1203 if (alt1
->predicate
!= NULL
) predicate_free(alt1
->predicate
); /* MR12 */
1204 if (alt2
->predicate
!= NULL
) predicate_free(alt2
->predicate
); /* MR12 */
1205 require(MR_PredRuleRefStack
.count
== 0,"PredRuleRef stack not empty");
1206 alt1
->predicate
= MR_find_predicates_and_supp((Node
*)alt1
->p1
);
1207 require(MR_PredRuleRefStack
.count
== 0,"PredRuleRef stack not empty");
1208 require (MR_predicate_context_completed(alt1
->predicate
),"predicate alt 1 not completed");
1209 alt1
->predicate
=MR_predSimplifyALL(alt1
->predicate
);
1211 require(MR_PredRuleRefStack
.count
== 0,"PredRuleRef stack not empty");
1212 alt2
->predicate
= MR_find_predicates_and_supp((Node
*)alt2
->p1
);
1213 require(MR_PredRuleRefStack
.count
== 0,"PredRuleRef stack not empty");
1214 require (MR_predicate_context_completed(alt2
->predicate
),"predicate alt 2 not completed");
1215 alt2
->predicate
=MR_predSimplifyALL(alt2
->predicate
);
1217 MR_doPredicatesHelp(1,alt1
,alt2
,jtype
,sub
);
1219 if ( HoistPredicateContext
&& (alt1
->predicate
!=NULL
||alt2
->predicate
!=NULL
) )
1221 verify_context(alt1
->predicate
);
1222 verify_context(alt2
->predicate
);
1224 if ( HoistPredicateContext
&& (alt1
->predicate
!=NULL
||alt2
->predicate
!=NULL
) && WarningLevel
>1 )
1225 ensure_predicates_cover_ambiguous_lookahead_sequences(alt1
, alt2
, sub
, ambig
);
1226 if ( WarningLevel
==1 &&
1227 (alt1
->predicate
!=NULL
||alt2
->predicate
!=NULL
))
1229 for (i
=1; i
<=CLL_k
; i
++) set_free( fset
[i
] );
1231 for (i
=1; i
<=CLL_k
; i
++) free( (char *)ftbl
[i
] );
1237 if ( WarningLevel
>1 )
1239 fprintf(stderr
, ErrHdr
, FileStr
[alt1
->file
], alt1
->line
);
1240 if ( jtype
== aLoopBegin
|| jtype
== aPlusBlk
)
1241 fprintf(stderr
, " warning: optional/exit path and alt(s) %sambiguous upon", sub
);
1243 fprintf(stderr
, " warning: alts %d and %d %sambiguous upon",
1244 alt1
->altnum
, alt2
->altnum
, sub
);
1245 dumpAmbigMsg(fset
, stderr
, 0);
1246 MR_traceAmbSource(fset
,alt1
,alt2
);
1249 for (i
=1; i
<=CLL_k
; i
++) set_free( fset
[i
] );
1251 for (i
=1; i
<=CLL_k
; i
++) free( (char *)ftbl
[i
] );
1256 /* Not resolved with (..)? block. Do full LL(n) analysis */
1258 /* ambig is the set of k-tuples truly in common between alt 1 and alt 2 */
1259 /* MR11 VerifyAmbig once used fset destructively */
1261 ambig
= VerifyAmbig(alt1
, alt2
, ftbl
, fset
, &t
, &u
, &numAmbig
);
1263 /* are all things in intersection really ambigs? */
1265 if (thisOverflow
|| numAmbig
< n
) /* MR9 */
1269 /* remove ambig permutation from 2nd alternative to resolve ambig;
1270 * We want to compute the set of artificial tuples, arising from
1271 * LL sup 1 (n) compression, that collide with real tuples from the
1272 * 2nd alternative. This is the set of "special case" tuples that
1273 * the LL sup 1 (n) decision template maps incorrectly.
1276 /* when generating code in genExpr() it does
1278 * if ( genExprSets(j->fset) && !genExprTree(j->ftree)) {...
1280 * Sooooo the j->ftree is the tree of alt2
1281 * after removal of conflicts, not alt1 !
1286 /* at the top of ambig is an ALT node */
1288 for (v
=ambig
->down
; v
!=NULL
; v
=v
->right
)
1290 u
= trm_perm(u
, v
); /* remove v FROM u */
1292 /* fprintf(stderr, "after rm alt2:"); preorder(u); fprintf(stderr, "\n");*/
1295 alt1
->ftree
= tappend(alt1
->ftree
, u
);
1296 alt1
->ftree
= tleft_factor(alt1
->ftree
);
1301 for (i
=1; i
<=CLL_k
; i
++) set_free( fset
[i
] );
1303 for (i
=1; i
<=CLL_k
; i
++) free( (char *)ftbl
[i
] );
1308 ambig
= tleft_factor(ambig
);
1311 * At this point, we surely have an LL(k) ambiguity. Check for predicates
1313 if ( ParseWithPredicates
)
1315 if (alt1
->predicate
!= NULL
) predicate_free(alt1
->predicate
); /* MR12 */
1316 if (alt2
->predicate
!= NULL
) predicate_free(alt2
->predicate
); /* MR12 */
1317 require(MR_PredRuleRefStack
.count
== 0,"PredRuleRef stack not empty");
1318 alt1
->predicate
= MR_find_predicates_and_supp((Node
*)alt1
->p1
);
1319 require(MR_PredRuleRefStack
.count
== 0,"PredRuleRef stack not empty");
1320 require (MR_predicate_context_completed(alt1
->predicate
),"predicate alt 1 not completed");
1321 alt1
->predicate
=MR_predSimplifyALL(alt1
->predicate
);
1323 require(MR_PredRuleRefStack
.count
== 0,"PredRuleRef stack not empty");
1324 alt2
->predicate
= MR_find_predicates_and_supp((Node
*)alt2
->p1
);
1325 require(MR_PredRuleRefStack
.count
== 0,"PredRuleRef stack not empty");
1326 require (MR_predicate_context_completed(alt2
->predicate
),"predicate alt 2 not completed");
1327 alt2
->predicate
=MR_predSimplifyALL(alt2
->predicate
);
1329 MR_doPredicatesHelp(0,alt1
,alt2
,jtype
,sub
);
1331 if ( HoistPredicateContext
&& (alt1
->predicate
!=NULL
||alt2
->predicate
!=NULL
) )
1333 verify_context(alt1
->predicate
);
1334 verify_context(alt2
->predicate
);
1336 if ( HoistPredicateContext
&& (alt1
->predicate
!=NULL
||alt2
->predicate
!=NULL
) && WarningLevel
>1 )
1337 ensure_predicates_cover_ambiguous_lookahead_sequences(alt1
, alt2
, sub
, ambig
);
1338 if ( WarningLevel
==1 &&
1339 (alt1
->predicate
!=NULL
||alt2
->predicate
!=NULL
))
1342 /* We found at least one pred for at least one of the alts;
1343 * If warnings are low, just return.
1347 for (i
=1; i
<=CLL_k
; i
++) set_free( fset
[i
] );
1349 for (i
=1; i
<=CLL_k
; i
++) free( (char *)ftbl
[i
] );
1353 /* else we're gonna give a warning */
1355 /* end TJP addition */
1357 fprintf(stderr
, ErrHdr
, FileStr
[alt1
->file
], alt1
->line
);
1358 if ( jtype
== aLoopBegin
|| jtype
== aPlusBlk
)
1359 fprintf(stderr
, " warning: optional/exit path and alt(s) %sambiguous upon", sub
);
1361 fprintf(stderr
, " warning: alts %d and %d %sambiguous upon",
1362 alt1
->altnum
, alt2
->altnum
, sub
);
1365 preorder(ambig
->down
); /* <===== k>1 ambiguity message data */
1366 fprintf(stderr
, "\n");
1368 MR_skipped_e3_report
=1;
1369 dumpAmbigMsg(fset
, stderr
, 0);
1372 MR_traceAmbSourceK(ambig
,alt1
,alt2
); /* <====== k>1 ambiguity aid */
1376 for (i
=1; i
<=CLL_k
; i
++) set_free( fset
[i
] );
1378 for (i
=1; i
<=CLL_k
; i
++) free( (char *)ftbl
[i
] );
1382 /* Don't analyze alpha block of (alpha)?beta; if (alpha)? then analyze
1383 * Return the 1st node of the beta block if present else return j.
1387 analysis_point( Junction
*j
)
1395 /* MR13b When there was an action/predicate preceding a guess block
1396 the guess block became invisible at the analysis_point.
1398 first_item_is_guess_block accepts any kind of node,
1399 despite the fact that the formal is a junction. But
1400 I don't want to have to change it all over the place
1401 until I know it works.
1404 if ( j
->ntype
!= nJunction
&& j
->ntype
!= nAction
) return j
;
1406 gblock
= first_item_is_guess_block((Junction
*)j
);
1410 Junction
*past
= gblock
->end
;
1412 require(past
!=NULL
, "analysis_point: no end block on (...)? block");
1414 for (p
=(Junction
*)past
->p1
; p
!=NULL
; )
1416 if ( p
->ntype
==nAction
)
1418 p
=(Junction
*)((ActionNode
*)p
)->next
;
1421 if ( p
->ntype
!=nJunction
)
1423 past
->alpha_beta_guess_end
=1; /* MR14 */
1424 return (Junction
*)past
->p1
;
1426 if ( p
->jtype
==EndBlk
|| p
->jtype
==EndRule
)
1431 /* MR6 A guess block is of the form "(alpha)? beta" or "(alpha)?". */
1432 /* MR6 When beta is omitted (second form) this means "(alpha)? alpha". */
1433 /* MR6 The program does not store another copy of alpha in this case. */
1434 /* MR6 During analysis when the program needs to know what follows the */
1435 /* MR6 guess clause. It calls this routine. */
1437 /* MR6 If it is of the form "(alpha)? beta" it returns a pointer to beta.*/
1439 /* MR6 If it is of the form "(alpha)?" it returns a pointer to the guess */
1440 /* MR6 block itself thereby reusing the junction tree. */
1442 /* MR6 It works by searching the "next in sequence" chain (skipping actions) */
1443 /* MR6 searching for a RuleRef or Token node. (Those are the only 4 kinds */
1444 /* MR6 of nodes: Junctions, RuleRef, Token, and Action.) */
1446 /* MR6 This won't work for the special case "(alpha)? ()" because it has no */
1447 /* MR6 rule references or token nodes. It eventually encounters a */
1448 /* MR6 junction of type EndBlk or EndRule and says to its caller: nothing */
1449 /* MR6 more here to analyze - must be of the form "(alpha)?". */
1451 /* MR6 In the case of "(alpha)? ()" it should return a pointer to "()" */
1455 if ( p
->jtype
!=Generic
) { /* MR6 */
1456 past
->alpha_beta_guess_end
=1; /* MR14 */
1457 return (Junction
*)past
->p1
; /* MR6 */
1459 p
=(Junction
*)p
->p1
;
1467 First( Junction
*j
, int k
, int jtype
, int *max_k
)
1469 First( j
, k
, jtype
, max_k
)
1476 Junction
*alt1
, *alt2
;
1481 int save_maintainBackTrace
;
1483 require(j
->ntype
==nJunction
, "First: non junction passed");
1485 /* C o m p u t e F I R S T s e t w i t h k l o o k a h e a d */
1486 fCurBlk
= rk
= empty
;
1487 for (alt1
=j
; alt1
!=NULL
; alt1
= (Junction
*)alt1
->p2
)
1489 Junction
* p
= NULL
;
1490 Junction
* p1junction
= NULL
;
1491 p
= analysis_point((Junction
*)alt1
->p1
);
1492 p1junction
= (Junction
*) (alt1
->p1
);
1494 if (p
!= p1junction
) {
1495 fprintf(stdout
,"Analysis point for #%d is #%d", p1junction
->seq
, p
->seq
); /* debug */
1498 REACH(p
, k
, &rk
, alt1
->fset
[k
]);
1499 require(set_nil(rk
), "rk != nil");
1501 set_orin(&fCurBlk
, alt1
->fset
[k
]);
1504 /* D e t e c t A m b i g u i t i e s */
1506 for (p1
=1,alt1
=j
; alt1
!=NULL
; alt1
= (Junction
*)alt1
->p2
, p1
++)
1508 for (p2
=1,alt2
=(Junction
*)alt1
->p2
; alt2
!=NULL
; alt2
= (Junction
*)alt2
->p2
, p2
++)
1511 a
= set_and(alt1
->fset
[k
], alt2
->fset
[k
]);
1512 while ( !set_nil(a
) )
1514 /* if we have hit the max k requested, just give warning */
1515 if ( j
->approx
==k
) {
1521 *** int save_LL_k
= LL_k
;
1522 *** int save_CLL_k
= CLL_k
;
1523 *** /* Get new LL_k from interactive feature if enabled */
1525 *** AmbiguityDialog(j
, jtype
, alt1
, alt2
, &CLL_k
, &LL_k
);
1528 save_maintainBackTrace
=MR_MaintainBackTrace
;
1529 if (AlphaBetaTrace
) MR_MaintainBackTrace
=0;
1530 HandleAmbiguity(j
, alt1
, alt2
, jtype
);
1531 MR_MaintainBackTrace
=save_maintainBackTrace
;
1536 Junction
*p
= analysis_point((Junction
*)alt1
->p1
);
1537 Junction
*q
= analysis_point((Junction
*)alt2
->p1
);
1538 k
++; /* attempt ambig alts again with more lookahead */
1540 REACH(p
, k
, &rk
, alt1
->fset
[k
]);
1541 require(set_nil(rk
), "rk != nil");
1542 REACH(q
, k
, &rk
, alt2
->fset
[k
]);
1543 require(set_nil(rk
), "rk != nil");
1545 a
= set_and(alt1
->fset
[k
], alt2
->fset
[k
]);
1546 if ( k
> *max_k
) *max_k
= k
;