1 /*
2 * fset.c
3 *
4 * Compute FIRST and FOLLOW sets.
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 <stdlib.h>
35
36 #include "pcctscfg.h"
37
38 #include "set.h"
39 #include "syn.h"
40 #include "hash.h"
41 #include "generic.h"
42 #include "dlgdef.h"
43 #include "limits.h"
44
45 #ifdef __USE_PROTOS
46 static void ensure_predicates_cover_ambiguous_lookahead_sequences
47 (Junction *, Junction *, char *, Tree *);
48 #else
49 static void ensure_predicates_cover_ambiguous_lookahead_sequences();
50 #endif
51
52 /*
53 * What tokens are k tokens away from junction q?
54 *
55 * Follow both p1 and p2 paths (unless RuleBlk) to collect the tokens k away from this
56 * node.
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.
62 *
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.
67 *
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.
72 *
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.
75 *
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:
80 *
81 * Fo(c)
82 * / \
83 * a set Fo(b)
84 * / \
85 * a set Fo(c) .....Hmmmm..... Infinite recursion!
86 *
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.
93 *
94 * Confused? Good! Read my MS thesis [Purdue Technical Report TR90-30].
95 * TJP 8/93 -- can now read PhD thesis from Purdue.
96 *
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.
99 *
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.
108 */
109
110 set
111 #ifdef __USE_PROTOS
rJunc(Junction * p,int k,set * rk)112 rJunc( Junction *p, int k, set *rk )
113 #else
114 rJunc( p, k, rk )
115 Junction *p;
116 int k;
117 set *rk;
118 #endif
119 {
120 set a, b;
121
122 require(p!=NULL, "rJunc: NULL node");
123 require(p->ntype==nJunction, "rJunc: not junction");
124
125 #ifdef DBG_LL1
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);
129 #endif
130 /* if this is one of the added optional alts for (...)+ then return */
131
132 /* no need to pop backtrace - hasn't been pushed */
133
134 if ( p->ignore ) return empty;
135
136 if (MR_MaintainBackTrace) MR_pointerStackPush(&MR_BackTraceStack,p);
137
138 /* MR14 */ if (AlphaBetaTrace && p->alpha_beta_guess_end) {
139 /* MR14 */ warnFL(
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();
143 /* MR14 */ };
144
145 /* MR14 */ if (p->alpha_beta_guess_end) {
146 /* MR14 */ if (MR_MaintainBackTrace) MR_pointerStackPop(&MR_BackTraceStack);
147 /* MR14 */ return empty;
148 /* MR14 */ }
149
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 )
153 {
154 require(p->lock!=NULL, "rJunc: lock array is NULL");
155 if ( p->lock[k] )
156 {
157 if ( p->jtype == EndRule ) /* FOLLOW cycle? */
158 {
159 #ifdef DBG_LL1
160 fprintf(stderr, "FOLLOW cycle to %s: panic!\n", p->rname);
161 #endif
162 if (! MR_AmbSourceSearch) RegisterCycle(p->rname, k);
163 }
164 if (MR_MaintainBackTrace) MR_pointerStackPop(&MR_BackTraceStack);
165 return empty;
166 }
167 if ( p->jtype == RuleBlk &&
168 p->end->halt &&
169 ! MR_AmbSourceSearch) /* check for FIRST cache */
170 {
171 CacheEntry *q = (CacheEntry *) hash_get(Fcache, Fkey(p->rname,'i',k));
172 if ( q != NULL )
173 {
174 set_orin(rk, q->rk);
175 if (MR_MaintainBackTrace) MR_pointerStackPop(&MR_BackTraceStack);
176 return set_dup( q->fset );
177 }
178 }
179 if ( p->jtype == EndRule &&
180 !p->halt && /* MR11 was using cache even when halt set */
181 ! MR_AmbSourceSearch) /* FOLLOW set cached already? */
182 {
183 CacheEntry *q = (CacheEntry *) hash_get(Fcache, Fkey(p->rname,'o',k));
184 if ( q != NULL )
185 {
186 #ifdef DBG_LL1
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");
191 #endif
192 if ( !q->incomplete )
193 {
194 if (MR_MaintainBackTrace) MR_pointerStackPop(&MR_BackTraceStack);
195 return set_dup( q->fset );
196 }
197 }
198 }
199 p->lock[k] = TRUE; /* This rule is busy */
200 }
201
202 a = b = empty;
203
204 if ( p->jtype == EndRule )
205 {
206 if (p->halt ) /* don't want FOLLOW here? */ /* unless MR10 hoisting */
207 {
208 p->lock[k] = FALSE;
209 set_orel(k, rk); /* indicate this k value needed */
210 if (MR_MaintainBackTrace) MR_pointerStackPop(&MR_BackTraceStack);
211 return empty;
212 }
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 */
215 #ifdef DBG_LL1
216 fprintf(stderr, "-->FOLLOW(%s,%d)\n", p->rname,k);
217 #endif
218 }
219
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;
227 /* MR14 */ }
228 /* MR14 */ p->guess_analysis_point=guess_point;
229 /* MR14 */ }
230 /* MR14 */ REACH(p->guess_analysis_point, k, rk, a);
231 } else {
232 REACH(p->p1, k, rk, a);
233 }
234 }
235
236 /* C a c h e R e s u l t s */
237
238 if ( p->jtype == RuleBlk && p->end->halt && ! MR_AmbSourceSearch) /* can save FIRST set? */
239 {
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 );
245 }
246
247 if ( p->jtype == EndRule &&
248 !p->halt && /* MR11 was using cache even with halt set */
249 ! MR_AmbSourceSearch) /* just completed FOLLOW? */
250 {
251 /* Cache Follow set */
252 CacheEntry *q = (CacheEntry *) hash_get(Fcache, Fkey(p->rname,'o',k));
253 if ( q==NULL )
254 {
255 q = newCacheEntry( Fkey(p->rname,'o',k) );
256 hash_add(Fcache, Fkey(p->rname,'o',k), (Entry *)q);
257 }
258 /*fprintf(stderr, "Caching %s FOLLOW %d\n", p->rname, k);*/
259 if ( set_nil(a) && !q->incomplete )
260 {
261 /* Don't ever save a nil set as complete.
262 * Turn it into an eof set.
263 */
264 set_orel(EofToken, &a);
265 }
266 set_orin(&(q->fset), a);
267 FoPop( k );
268 if ( FoTOS[k] == NULL && Cycles[k] != NULL ) ResolveFoCycles(k);
269 #ifdef DBG_LL1
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");
274 #endif
275 }
276
277 if (p->jtype != RuleBlk && p->p2 != NULL && /* MR14 */ ! p->guess) {
278 REACH(p->p2, k, rk, b);
279 }
280
281 if ( p->jtype==aLoopBlk || p->jtype==RuleBlk ||
282 p->jtype==aPlusBlk || p->jtype==EndRule )
283 p->lock[k] = FALSE; /* unlock node */
284
285 set_orin(&a, b);
286 set_free(b);
287 if (MR_MaintainBackTrace) MR_pointerStackPop(&MR_BackTraceStack);
288 return a;
289 }
290
291 set
292 #ifdef __USE_PROTOS
rRuleRef(RuleRefNode * p,int k,set * rk_out)293 rRuleRef( RuleRefNode *p, int k, set *rk_out )
294 #else
295 rRuleRef( p, k, rk_out )
296 RuleRefNode *p;
297 int k;
298 set *rk_out;
299 #endif
300 {
301 set rk;
302 Junction *r;
303 int k2;
304 set a, rk2, b;
305 int save_halt;
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");
309
310 #ifdef DBG_LL1
311 fprintf(stderr, "rRuleRef: %s\n", p->text);
312 #endif
313
314 if (MR_MaintainBackTrace) MR_pointerStackPush(&MR_BackTraceStack,p);
315
316 if ( q == NULL )
317 {
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);
321 return a;
322 }
323 rk2 = empty;
324
325 /* MR9 Problems with rule references in guarded predicates */
326 /* MR9 Perhaps can use hash table to find rule ? */
327
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);
331 /* MR9 */ };
332
333 r = RulePtr[q->rulenum];
334 if ( r->lock[k] )
335 {
336 errNoFL( eMsg2("infinite left-recursion to rule %s from rule %s",
337 r->rname, p->rname) );
338
339 if (MR_MaintainBackTrace) MR_pointerStackPop(&MR_BackTraceStack);
340
341 return empty;
342 }
343
344 save_halt = r->end->halt;
345 r->end->halt = TRUE; /* don't let reach fall off end of rule here */
346 rk = empty;
347 REACH(r, k, &rk, a);
348 r->end->halt = save_halt;
349 while ( !set_nil(rk) ) {
350 k2 = set_int(rk); /* MR11 this messes up the ambiguity search routine */
351 set_rm(k2, rk);
352 REACH(p->next, k2, &rk2, b); /* MR11 by changing the value of k */
353 set_orin(&a, b);
354 set_free(b);
355 }
356 set_free(rk); /* this has no members, but free its memory */
357 set_orin(rk_out, rk2); /* remember what we couldn't do */
358 set_free(rk2);
359 if (MR_MaintainBackTrace) MR_pointerStackPop(&MR_BackTraceStack);
360 return a;
361 }
362
363 /*
364 * Return FIRST sub k ( token_node )
365 *
366 * TJP 10/11/93 modified this so that token nodes that are actually
367 * ranges (T1..T2) work.
368 */
369 set
370 #ifdef __USE_PROTOS
rToken(TokNode * p,int k,set * rk)371 rToken( TokNode *p, int k, set *rk )
372 #else
373 rToken( p, k, rk )
374 TokNode *p;
375 int k;
376 set *rk;
377 #endif
378 {
379 set a;
380
381 require(p!=NULL, "rToken: NULL node");
382 require(p->ntype==nToken, "rToken: not token node");
383
384 #ifdef DBG_LL1
385 fprintf(stderr, "rToken: %s\n", (TokenString(p->token)!=NULL)?TokenString(p->token):
386 ExprString(p->token));
387 #endif
388
389
390 if (MR_MaintainBackTrace) MR_pointerStackPush(&MR_BackTraceStack,p);
391
392 if (MR_AmbSourceSearch && (k-1) == 0) {
393
394 set localConstrain;
395 set intersection;
396
397 localConstrain=fset[maxk-k+1];
398
399 if (! set_nil(p->tset)) {
400 intersection=set_and(localConstrain,p->tset);
401 if (! set_nil(intersection)) {
402 MR_backTraceReport();
403 };
404 set_free(intersection);
405 } else {
406 if (set_el( (unsigned) p->token,localConstrain)) {
407 MR_backTraceReport();
408 }
409 };
410 };
411
412 if ( k-1 == 0 ) {
413
414 if (MR_MaintainBackTrace) MR_pointerStackPop(&MR_BackTraceStack);
415
416 if ( !set_nil(p->tset) ) {
417 return set_dup(p->tset);
418 } else {
419 return set_of(p->token);
420 };
421 }
422
423 REACH(p->next, k-1, rk, a);
424
425 if (MR_MaintainBackTrace) MR_pointerStackPop(&MR_BackTraceStack);
426
427 return a;
428 }
429
430 set
431 #ifdef __USE_PROTOS
rAction(ActionNode * p,int k,set * rk)432 rAction( ActionNode *p, int k, set *rk )
433 #else
434 rAction( p, k, rk )
435 ActionNode *p;
436 int k;
437 set *rk;
438 #endif
439 {
440 set a;
441
442 require(p!=NULL, "rJunc: NULL node");
443 require(p->ntype==nAction, "rJunc: not action");
444
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);
449 /* MR11 */ return a;
450 /* MR11 */ };
451 /* MR11 */ };
452
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
456 */
457
458 REACH(p->next, k, rk, a); /* ignore actions */
459 return a;
460 }
461
462 /* A m b i g u i t y R e s o l u t i o n */
463
464
465 void
466 #ifdef __USE_PROTOS
dumpAmbigMsg(set * fset,FILE * f,int want_nls)467 dumpAmbigMsg( set *fset, FILE *f, int want_nls )
468 #else
469 dumpAmbigMsg( fset, f, want_nls )
470 set *fset;
471 FILE *f;
472 int want_nls;
473 #endif
474 {
475 int i;
476
477 set copy; /* MR11 */
478
479 if ( want_nls ) fprintf(f, "\n\t");
480 else fprintf(f, " ");
481
482 for (i=1; i<=CLL_k; i++)
483 {
484 copy=set_dup(fset[i]); /* MR11 */
485
486 if ( i>1 )
487 {
488 if ( !want_nls ) fprintf(f, ", ");
489 }
490 if ( set_deg(copy) > 3 && elevel == 1 )
491 {
492 int e,m;
493 fprintf(f, "{");
494 for (m=1; m<=3; m++)
495 {
496 e=set_int(copy);
497 fprintf(f, " %s", TerminalString(e));
498 set_rm(e, copy);
499 }
500 fprintf(f, " ... }");
501 }
502 else s_fprT(f, copy);
503 if ( want_nls ) fprintf(f, "\n\t");
504 set_free(copy);
505 }
506 fprintf(f, "\n");
507
508 }
509
510 static void
511 #ifdef __USE_PROTOS
verify_context(Predicate * predicate)512 verify_context(Predicate *predicate)
513 #else
514 verify_context(predicate)
515 Predicate *predicate;
516 #endif
517 {
518 if ( predicate == NULL ) return;
519
520 if ( predicate->expr == PRED_OR_LIST ||
521 predicate->expr == PRED_AND_LIST )
522 {
523 verify_context(predicate->down);
524 verify_context(predicate->right); /* MR10 */
525 return;
526 }
527
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 )) )
533 {
534
535 /* MR9 Suppress annoying messages caused by our own clever(?) fix */
536
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;
551 }
552 verify_context(predicate->right); /* MR10 */
553 }
554
555 /*
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.
558 *
559 * For example,
560 * a : <<PRED1>>? (A B|A C)
561 * | b
562 * ;
563 * b : <<PRED2>>? A B
564 * | A C
565 * ;
566 *
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).
569 *
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.
573 *
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.
576 */
577 static void
578 #ifdef __USE_PROTOS
ensure_predicates_cover_ambiguous_lookahead_sequences(Junction * alt1,Junction * alt2,char * sub,Tree * ambig)579 ensure_predicates_cover_ambiguous_lookahead_sequences
580 ( Junction *alt1, Junction *alt2, char *sub, Tree *ambig )
581 #else
582 ensure_predicates_cover_ambiguous_lookahead_sequences( alt1, alt2, sub, ambig )
583 Junction *alt1;
584 Junction *alt2;
585 char *sub;
586 Tree *ambig;
587 #endif
588 {
589 if ( !ParseWithPredicates ) return;
590
591 if ( ambig!=NULL )
592 {
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 )
597 {
598 fprintf(stderr, ErrHdr, FileStr[alt1->file], alt1->line);
599 fprintf(stderr, " warning: alt %d %shas no predicate to resolve ambiguity",
600 alt1->altnum, sub);
601 if ( alt1->predicate!=NULL && non_covered!=NULL )
602 {
603 fprintf(stderr, " upon");
604 preorder(non_covered);
605 }
606 else if ( alt1->predicate==NULL )
607 {
608 fprintf(stderr, " upon");
609 preorder(ambig->down);
610 }
611 fprintf(stderr, "\n");
612 }
613 Tfree(non_covered);
614 non_covered = NULL;
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 )
618 {
619 fprintf(stderr, ErrHdr, FileStr[alt2->file], alt2->line);
620 fprintf(stderr, " warning: alt %d %shas no predicate to resolve ambiguity",
621 alt2->altnum, sub);
622 if ( alt2->predicate!=NULL && non_covered!=NULL )
623 {
624 fprintf(stderr, " upon");
625 preorder(non_covered);
626 }
627 else if ( alt2->predicate==NULL )
628 {
629 fprintf(stderr, " upon");
630 preorder(ambig->down);
631 }
632 fprintf(stderr, "\n");
633 }
634 Tfree(non_covered);
635 }
636 else if ( !set_nil(alt1->fset[1]) )
637 {
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 )
642 {
643 fprintf(stderr, ErrHdr, FileStr[alt1->file], alt1->line);
644 fprintf(stderr, " warning: alt %d %shas no predicate to resolve ambiguity",
645 alt1->altnum, sub);
646 if ( alt1->predicate!=NULL )
647 {
648 fprintf(stderr, " upon ");
649 s_fprT(stderr, non_covered);
650 }
651 fprintf(stderr, "\n");
652 }
653 set_free( non_covered );
654 non_covered = set_dif(delta, covered_set(alt2->predicate));
655 if ( set_deg(non_covered)>0 && WarningLevel>1 )
656 {
657 fprintf(stderr, ErrHdr, FileStr[alt2->file], alt2->line);
658 fprintf(stderr, " warning: alt %d %shas no predicate to resolve ambiguity",
659 alt2->altnum, sub);
660 if ( alt2->predicate!=NULL )
661 {
662 fprintf(stderr, " upon ");
663 s_fprT(stderr, non_covered);
664 }
665 fprintf(stderr, "\n");
666 }
667 set_free( non_covered );
668 set_free( delta );
669 }
670 else fatal_internal("productions have no lookahead in predicate checking routine");
671 }
672
673 #ifdef __USE_PROTOS
MR_doPredicatesHelp(int inGuessBlock,Junction * alt1,Junction * alt2,int jtype,char * sub)674 void MR_doPredicatesHelp(int inGuessBlock,Junction *alt1,Junction *alt2,int jtype,char *sub)
675 #else
676 void MR_doPredicatesHelp(inGuessBlock,alt1,alt2,jtype,sub)
677 int inGuessBlock;
678 Junction *alt1;
679 Junction *alt2;
680 int jtype;
681 char *sub;
682 #endif
683 {
684 Predicate *p1;
685 Predicate *p2;
686
687 Junction *parentRule=MR_nameToRuleBlk(alt1->rname);
688
689 if (inGuessBlock && WarningLevel <= 1) return;
690
691 /* let antlr give the usual error message */
692
693 if (alt1->predicate == NULL && alt2->predicate == NULL) return;
694
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",
699 alt1->altnum,
700 alt1->line,
701 alt2->altnum,
702 alt2->line,
703 sub,
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"
707 );
708 return;
709 };
710
711 /* first do the easy comparison. then do the hard one */
712
713 if (MR_comparePredicates(alt1->predicate,alt2->predicate)) {
714
715 if (jtype == aLoopBegin || jtype == aPlusBlk ) {
716
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
721 */
722
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 ",
726 sub,
727 CurRule,
728 FileStr[alt1->file],
729 alt1->altnum,
730 alt1->line,
731 alt2->altnum,
732 alt2->line,
733 " are identical and have no resolving power\n");
734 } else {
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",
738 CurRule,
739 FileStr[alt1->file],
740 alt1->altnum,
741 alt1->line,
742 alt2->altnum,
743 alt2->line,
744 " are identical and have no resolving power\n");
745 };
746 } else {
747 p1=predicate_dup_without_context(alt1->predicate);
748 p1=MR_unfold(p1);
749 MR_clearPredEntry(p1);
750 MR_simplifyInverted(p1,0);
751 p1=MR_predSimplifyALL(p1);
752 p2=predicate_dup_without_context(alt2->predicate);
753 p2=MR_unfold(p2);
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 ",
762 sub,
763 CurRule,
764 FileStr[alt1->file],
765 alt1->altnum,
766 alt1->line,
767 alt2->altnum,
768 alt2->line,
769 " are identical when compared without context and may have no\n",
770 " resolving power for some lookahead sequences.\n");
771 } else {
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",
775 CurRule,
776 FileStr[alt1->file],
777 alt1->altnum,
778 alt1->line,
779 alt2->altnum,
780 alt2->line,
781 " are identical when compared without context and may have no\n",
782 " resolving power for some lookahead sequences.\n");
783 };
784 if (InfoP) {
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");
790
791 fprintf(output,"Choice 1: %s alt %d line %d file %s\n\n",
792 MR_ruleNamePlusOffset( (Node *) alt1),
793 alt1->altnum,
794 alt1->line,
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);
800 if (p1 == NULL) {
801 Predicate *phelp;
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);
810 };
811 fprintf(output,"\n");
812
813 fprintf(output,"Choice 2: %s alt %d line %d file %s\n\n",
814 MR_ruleNamePlusOffset( (Node *) alt2),
815 alt2->altnum,
816 alt2->line,
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);
822 if (p2 == NULL) {
823 Predicate *phelp;
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);
832 };
833 fprintf(output,"\n#endif\n");
834 };
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 ",
840 sub,
841 CurRule,
842 FileStr[alt1->file],
843 alt1->altnum,
844 alt1->line,
845 alt2->altnum,
846 alt2->line,
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");
849 } else {
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",
853 CurRule,
854 FileStr[alt1->file],
855 alt1->altnum,
856 alt1->line,
857 alt2->altnum,
858 alt2->line,
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");
861 };
862 if (InfoP) {
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),
871 alt1->altnum,
872 alt1->line,
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);
878 if (p1 == NULL) {
879 Predicate *phelp;
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);
888 };
889 fprintf(output,"\n");
890
891 fprintf(output,"Choice 2: %s alt %d line %d file %s\n\n",
892 MR_ruleNamePlusOffset( (Node *) alt2),
893 alt2->altnum,
894 alt2->line,
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);
900 if (p2 == NULL) {
901 Predicate *phelp;
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);
910 };
911 fprintf(output,"\n#endif\n");
912 };
913 };
914 predicate_free(p1);
915 predicate_free(p2);
916 };
917 }
918
919 static int totalOverflow=0; /* MR9 */
920
921 void
922 #ifdef __USE_PROTOS
HandleAmbiguity(Junction * block,Junction * alt1,Junction * alt2,int jtype)923 HandleAmbiguity( Junction *block, Junction *alt1, Junction *alt2, int jtype )
924 #else
925 HandleAmbiguity( block, alt1, alt2, jtype )
926 Junction *block;
927 Junction *alt1;
928 Junction *alt2;
929 int jtype;
930 #endif
931 {
932 unsigned **ftbl;
933 set *fset, b;
934 int i, numAmbig,n2;
935 Tree *ambig=NULL, *t, *u;
936 char *sub = "";
937 long n;
938 int thisOverflow=0; /* MR9 */
939 long set_deg_value; /* MR10 */
940 long threshold; /* MR10 */
941
942 require(block!=NULL, "NULL block");
943 require(block->ntype==nJunction, "invalid block");
944
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");
950
951 /* create constraint table and count number of possible ambiguities (use<=LL_k) */
952 for (n=1,i=1; i<=CLL_k; i++)
953 {
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;
960 /* MR10 */ } else {
961 /* MR10 */ n=LONG_MAX;
962 /* MR9 */ if (totalOverflow == 0) {
963 #if 0
964 /* MR10 comment this out because it just makes users worry */
965
966 /* MR9 */ warnNoFL("Overflow in computing number of possible ambiguities in HandleAmbiguity\n");
967 #endif
968 /* MR9 */ };
969 /* MR9 */ thisOverflow++;
970 /* MR9 */ totalOverflow++;
971 /* MR9 */ };
972 /* MR10 */ } else {
973 /* MR10 */ n *= set_deg_value;
974 /* MR9 */ };
975 fset[i] = set_dup(b);
976 ftbl[i] = set_pdq(b);
977 set_free(b);
978 }
979
980 switch ( jtype )
981 {
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;
989 }
990
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.
993 */
994 if ( block->approx>0 )
995 {
996 if ( ParseWithPredicates )
997 {
998 if (alt1->predicate != NULL) predicate_free(alt1->predicate); /* MR12 */
999 if (alt2->predicate != NULL) predicate_free(alt2->predicate); /* MR12 */
1000
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);
1006
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);
1012
1013 MR_doPredicatesHelp(0,alt1,alt2,jtype,sub);
1014
1015 if ( HoistPredicateContext
1016 && (alt1->predicate!=NULL||alt2->predicate!=NULL) )
1017 {
1018 verify_context(alt1->predicate);
1019 verify_context(alt2->predicate);
1020 }
1021
1022 if ( HoistPredicateContext
1023 && (alt1->predicate!=NULL||alt2->predicate!=NULL)
1024 && WarningLevel>1 )
1025 ensure_predicates_cover_ambiguous_lookahead_sequences(alt1, alt2, sub, ambig);
1026 }
1027
1028 if ( WarningLevel>1 )
1029 {
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);
1033 else
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);
1038 }
1039 for (i=1; i<=CLL_k; i++) set_free( fset[i] );
1040 free((char *)fset);
1041 for (i=1; i<=CLL_k; i++) free( (char *)ftbl[i] );
1042 free((char *)ftbl);
1043 return;
1044 }
1045
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)
1049 */
1050
1051 n2 = 0;
1052 for (i=1; i<LL_k; i++) n2 += set_deg(alt1->fset[i])+set_deg(alt2->fset[i]);
1053
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)
1056 */
1057
1058 if ( n2==2*(LL_k-1) )
1059 {
1060
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)
1064 */
1065
1066 if ( first_item_is_guess_block_extra((Junction *)alt1->p1)!=NULL )
1067 {
1068 if ( WarningLevel==1 )
1069 {
1070 for (i=1; i<=CLL_k; i++) set_free( fset[i] );
1071 free((char *)fset);
1072 for (i=1; i<=CLL_k; i++) free( (char *)ftbl[i] );
1073 free((char *)ftbl);
1074 return;
1075 }
1076
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);
1080 else
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);
1085 }
1086
1087 ambig = NULL;
1088 if ( LL_k>1 ) ambig = make_tree_from_sets(alt1->fset, alt2->fset);
1089 if ( ParseWithPredicates )
1090 {
1091 if (alt1->predicate != NULL) predicate_free(alt1->predicate); /* MR12 */
1092 if (alt2->predicate != NULL) predicate_free(alt2->predicate); /* MR12 */
1093
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);
1099
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);
1105
1106 MR_doPredicatesHelp(0,alt1,alt2,jtype,sub);
1107
1108 if ( HoistPredicateContext && (alt1->predicate!=NULL||alt2->predicate!=NULL) )
1109 {
1110 verify_context(alt1->predicate);
1111 verify_context(alt2->predicate);
1112 }
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))
1117 {
1118 for (i=1; i<=CLL_k; i++) set_free( fset[i] );
1119 free((char *)fset);
1120 for (i=1; i<=CLL_k; i++) free( (char *)ftbl[i] );
1121 free((char *)ftbl);
1122 Tfree(ambig);
1123 return;
1124 }
1125 }
1126 /* end TJP (10/24/93) */
1127
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);
1131 else
1132 fprintf(stderr, " warning: alts %d and %d %sambiguous upon",
1133 alt1->altnum, alt2->altnum, sub);
1134 if ( elevel == 3 && LL_k>1 )
1135 {
1136 preorder(ambig);
1137 fprintf(stderr, "\n");
1138 for (i=1; i<=CLL_k; i++) set_free( fset[i] );
1139 free((char *)fset);
1140 for (i=1; i<=CLL_k; i++) free( (char *)ftbl[i] );
1141 free((char *)ftbl);
1142 Tfree(ambig);
1143 return;
1144 };
1145
1146 Tfree(ambig);
1147 dumpAmbigMsg(fset, stderr, 0);
1148
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
1152 */
1153
1154 MR_traceAmbSource(fset,alt1,alt2);
1155
1156 for (i=1; i<=CLL_k; i++) set_free( fset[i] );
1157 free((char *)fset);
1158 for (i=1; i<=CLL_k; i++) free( (char *)ftbl[i] );
1159 free((char *)ftbl);
1160 return;
1161 }
1162
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)
1165 */
1166
1167 /* in case tree construction runs out of memory, set info to make good err msg */
1168
1169 CurAmbigAlt1 = alt1->altnum;
1170 CurAmbigAlt2 = alt2->altnum;
1171 CurAmbigbtype = sub;
1172 CurAmbigfile = alt1->file;
1173 CurAmbigline = alt1->line;
1174
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.
1182
1183 Note: LL(n) context cannot be computed for semantic predicates when
1184 followed by (..)?.
1185
1186 If (..)? then we scream "AAAHHHH! No LL(n) analysis will help"
1187
1188 Is 'ambig' always defined if we enter this if? I hope so
1189 because the 'ensure...()' func references it. TJP Nov 1993.
1190 */
1191
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.
1197 */
1198
1199 if ( first_item_is_guess_block_extra((Junction *)alt1->p1)!=NULL )
1200 {
1201 if ( ParseWithPredicates )
1202 {
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);
1210
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);
1216
1217 MR_doPredicatesHelp(1,alt1,alt2,jtype,sub);
1218
1219 if ( HoistPredicateContext && (alt1->predicate!=NULL||alt2->predicate!=NULL) )
1220 {
1221 verify_context(alt1->predicate);
1222 verify_context(alt2->predicate);
1223 }
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))
1228 {
1229 for (i=1; i<=CLL_k; i++) set_free( fset[i] );
1230 free((char *)fset);
1231 for (i=1; i<=CLL_k; i++) free( (char *)ftbl[i] );
1232 free((char *)ftbl);
1233 return;
1234 }
1235 }
1236
1237 if ( WarningLevel>1 )
1238 {
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);
1242 else
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);
1247 }
1248
1249 for (i=1; i<=CLL_k; i++) set_free( fset[i] );
1250 free((char *)fset);
1251 for (i=1; i<=CLL_k; i++) free( (char *)ftbl[i] );
1252 free((char *)ftbl);
1253 return;
1254 }
1255
1256 /* Not resolved with (..)? block. Do full LL(n) analysis */
1257
1258 /* ambig is the set of k-tuples truly in common between alt 1 and alt 2 */
1259 /* MR11 VerifyAmbig once used fset destructively */
1260
1261 ambig = VerifyAmbig(alt1, alt2, ftbl, fset, &t, &u, &numAmbig);
1262
1263 /* are all things in intersection really ambigs? */
1264
1265 if (thisOverflow || numAmbig < n ) /* MR9 */
1266 {
1267 Tree *v;
1268
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.
1274 */
1275
1276 /* when generating code in genExpr() it does
1277 *
1278 * if ( genExprSets(j->fset) && !genExprTree(j->ftree)) {...
1279 *
1280 * Sooooo the j->ftree is the tree of alt2
1281 * after removal of conflicts, not alt1 !
1282 */
1283
1284 if ( ambig!=NULL )
1285 {
1286 /* at the top of ambig is an ALT node */
1287
1288 for (v=ambig->down; v!=NULL; v=v->right)
1289 {
1290 u = trm_perm(u, v); /* remove v FROM u */
1291 }
1292 /* fprintf(stderr, "after rm alt2:"); preorder(u); fprintf(stderr, "\n");*/
1293 }
1294 Tfree( t );
1295 alt1->ftree = tappend(alt1->ftree, u);
1296 alt1->ftree = tleft_factor(alt1->ftree);
1297 }
1298
1299 if ( ambig==NULL )
1300 {
1301 for (i=1; i<=CLL_k; i++) set_free( fset[i] );
1302 free((char *)fset);
1303 for (i=1; i<=CLL_k; i++) free( (char *)ftbl[i] );
1304 free((char *)ftbl);
1305 return;
1306 }
1307
1308 ambig = tleft_factor(ambig);
1309
1310 /* TJP:
1311 * At this point, we surely have an LL(k) ambiguity. Check for predicates
1312 */
1313 if ( ParseWithPredicates )
1314 {
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);
1322
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);
1328
1329 MR_doPredicatesHelp(0,alt1,alt2,jtype,sub);
1330
1331 if ( HoistPredicateContext && (alt1->predicate!=NULL||alt2->predicate!=NULL) )
1332 {
1333 verify_context(alt1->predicate);
1334 verify_context(alt2->predicate);
1335 }
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))
1340 {
1341
1342 /* We found at least one pred for at least one of the alts;
1343 * If warnings are low, just return.
1344 */
1345
1346 Tfree(ambig);
1347 for (i=1; i<=CLL_k; i++) set_free( fset[i] );
1348 free((char *)fset);
1349 for (i=1; i<=CLL_k; i++) free( (char *)ftbl[i] );
1350 free((char *)ftbl);
1351 return;
1352 }
1353 /* else we're gonna give a warning */
1354 }
1355 /* end TJP addition */
1356
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);
1360 else
1361 fprintf(stderr, " warning: alts %d and %d %sambiguous upon",
1362 alt1->altnum, alt2->altnum, sub);
1363 if ( elevel == 3 )
1364 {
1365 preorder(ambig->down); /* <===== k>1 ambiguity message data */
1366 fprintf(stderr, "\n");
1367 } else {
1368 MR_skipped_e3_report=1;
1369 dumpAmbigMsg(fset, stderr, 0);
1370 };
1371
1372 MR_traceAmbSourceK(ambig,alt1,alt2); /* <====== k>1 ambiguity aid */
1373
1374 Tfree(ambig);
1375
1376 for (i=1; i<=CLL_k; i++) set_free( fset[i] );
1377 free((char *)fset);
1378 for (i=1; i<=CLL_k; i++) free( (char *)ftbl[i] );
1379 free((char *)ftbl);
1380 }
1381
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.
1384 */
1385 Junction *
1386 #ifdef __USE_PROTOS
analysis_point(Junction * j)1387 analysis_point( Junction *j )
1388 #else
1389 analysis_point( j )
1390 Junction *j;
1391 #endif
1392 {
1393 Junction *gblock;
1394
1395 /* MR13b When there was an action/predicate preceding a guess block
1396 the guess block became invisible at the analysis_point.
1397
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.
1402 */
1403
1404 if ( j->ntype != nJunction && j->ntype != nAction) return j;
1405
1406 gblock = first_item_is_guess_block((Junction *)j);
1407
1408 if ( gblock!=NULL )
1409 {
1410 Junction *past = gblock->end;
1411 Junction *p;
1412 require(past!=NULL, "analysis_point: no end block on (...)? block");
1413
1414 for (p=(Junction *)past->p1; p!=NULL; )
1415 {
1416 if ( p->ntype==nAction )
1417 {
1418 p=(Junction *)((ActionNode *)p)->next;
1419 continue;
1420 }
1421 if ( p->ntype!=nJunction )
1422 {
1423 past->alpha_beta_guess_end=1; /* MR14 */
1424 return (Junction *)past->p1;
1425 }
1426 if ( p->jtype==EndBlk || p->jtype==EndRule )
1427 {
1428 return j;
1429 }
1430 /* MR6 */
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. */
1436 /* MR6 */
1437 /* MR6 If it is of the form "(alpha)? beta" it returns a pointer to beta.*/
1438 /* MR6 */
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. */
1441 /* MR6 */
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.) */
1445 /* MR6 */
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)?". */
1450 /* MR6 */
1451 /* MR6 In the case of "(alpha)? ()" it should return a pointer to "()" */
1452 /* MR6 */
1453 /* MR6 I think. */
1454 /* MR6 */
1455 if ( p->jtype!=Generic) { /* MR6 */
1456 past->alpha_beta_guess_end=1; /* MR14 */
1457 return (Junction *)past->p1; /* MR6 */
1458 }; /* MR6 */
1459 p=(Junction *)p->p1;
1460 }
1461 }
1462 return j;
1463 }
1464
1465 set
1466 #ifdef __USE_PROTOS
First(Junction * j,int k,int jtype,int * max_k)1467 First( Junction *j, int k, int jtype, int *max_k )
1468 #else
1469 First( j, k, jtype, max_k )
1470 Junction *j;
1471 int k;
1472 int jtype;
1473 int *max_k;
1474 #endif
1475 {
1476 Junction *alt1, *alt2;
1477 set a, rk, fCurBlk;
1478 int savek;
1479 int p1, p2;
1480
1481 int save_maintainBackTrace;
1482
1483 require(j->ntype==nJunction, "First: non junction passed");
1484
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 )
1488 {
1489 Junction * p = NULL;
1490 Junction * p1junction = NULL;
1491 p = analysis_point((Junction *)alt1->p1);
1492 p1junction = (Junction *) (alt1->p1);
1493 #if 0
1494 if (p != p1junction) {
1495 fprintf(stdout,"Analysis point for #%d is #%d", p1junction->seq, p->seq); /* debug */
1496 }
1497 #endif
1498 REACH(p, k, &rk, alt1->fset[k]);
1499 require(set_nil(rk), "rk != nil");
1500 set_free(rk);
1501 set_orin(&fCurBlk, alt1->fset[k]);
1502 }
1503
1504 /* D e t e c t A m b i g u i t i e s */
1505 *max_k = 1;
1506 for (p1=1,alt1=j; alt1!=NULL; alt1 = (Junction *)alt1->p2, p1++)
1507 {
1508 for (p2=1,alt2=(Junction *)alt1->p2; alt2!=NULL; alt2 = (Junction *)alt2->p2, p2++)
1509 {
1510 savek = k;
1511 a = set_and(alt1->fset[k], alt2->fset[k]);
1512 while ( !set_nil(a) )
1513 {
1514 /* if we have hit the max k requested, just give warning */
1515 if ( j->approx==k ) {
1516 }
1517
1518 if ( k==CLL_k )
1519 {
1520 #ifdef NOT_USED
1521 *** int save_LL_k = LL_k;
1522 *** int save_CLL_k = CLL_k;
1523 *** /* Get new LL_k from interactive feature if enabled */
1524 *** if ( AImode )
1525 *** AmbiguityDialog(j, jtype, alt1, alt2, &CLL_k, &LL_k);
1526 #endif
1527 *max_k = CLL_k;
1528 save_maintainBackTrace=MR_MaintainBackTrace;
1529 if (AlphaBetaTrace) MR_MaintainBackTrace=0;
1530 HandleAmbiguity(j, alt1, alt2, jtype);
1531 MR_MaintainBackTrace=save_maintainBackTrace;
1532 break;
1533 }
1534 else
1535 {
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 */
1539
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");
1544 set_free(a);
1545 a = set_and(alt1->fset[k], alt2->fset[k]);
1546 if ( k > *max_k ) *max_k = k;
1547 }
1548 }
1549 set_free(a);
1550 k = savek;
1551 }
1552 }
1553
1554 return fCurBlk;
1555 }
1556