]> git.proxmox.com Git - mirror_edk2.git/blame - Tools/CodeTools/TianoTools/Pccts/antlr/fset.c
projects / mirror_edk2.git / blame
? search:
summary | shortlog | log | commit | commitdiff | tree
blob | blame (incremental) | history | HEAD
Restructuring for better separation of Tool packages.
[mirror_edk2.git] / Tools / CodeTools / TianoTools / Pccts / antlr / fset.c
CommitLineData
878ddf1f 1/*\r
2 * fset.c\r
3 *\r
4 * Compute FIRST and FOLLOW sets.\r
5 *\r
6 * SOFTWARE RIGHTS\r
7 *\r
8 * We reserve no LEGAL rights to the Purdue Compiler Construction Tool\r
9 * Set (PCCTS) -- PCCTS is in the public domain. An individual or\r
10 * company may do whatever they wish with source code distributed with\r
11 * PCCTS or the code generated by PCCTS, including the incorporation of\r
12 * PCCTS, or its output, into commerical software.\r
13 *\r
14 * We encourage users to develop software with PCCTS. However, we do ask\r
15 * that credit is given to us for developing PCCTS. By "credit",\r
16 * we mean that if you incorporate our source code into one of your\r
17 * programs (commercial product, research project, or otherwise) that you\r
18 * acknowledge this fact somewhere in the documentation, research report,\r
19 * etc... If you like PCCTS and have developed a nice tool with the\r
20 * output, please mention that you developed it using PCCTS. In\r
21 * addition, we ask that this header remain intact in our source code.\r
22 * As long as these guidelines are kept, we expect to continue enhancing\r
23 * this system and expect to make other tools available as they are\r
24 * completed.\r
25 *\r
26 * ANTLR 1.33\r
27 * Terence Parr\r
28 * Parr Research Corporation\r
29 * with Purdue University and AHPCRC, University of Minnesota\r
30 * 1989-2001\r
31 */\r
32\r
33#include <stdio.h>\r
34#include <stdlib.h>\r
35\r
36#include "pcctscfg.h"\r
37\r
38#include "set.h"\r
39#include "syn.h"\r
40#include "hash.h"\r
41#include "generic.h"\r
42#include "dlgdef.h"\r
43#include "limits.h"\r
44\r
45#ifdef __USE_PROTOS\r
46static void ensure_predicates_cover_ambiguous_lookahead_sequences\r
47 (Junction *, Junction *, char *, Tree *);\r
48#else\r
49static void ensure_predicates_cover_ambiguous_lookahead_sequences();\r
50#endif\r
51\r
52/*\r
53 * What tokens are k tokens away from junction q?\r
54 *\r
55 * Follow both p1 and p2 paths (unless RuleBlk) to collect the tokens k away from this\r
56 * node.\r
57 * We lock the junction according to k--the lookahead. If we have been at this\r
58 * junction before looking for the same, k, number of lookahead tokens, we will\r
59 * do it again and again...until we blow up the stack. Locks are only used on aLoopBlk,\r
60 * RuleBlk, aPlusBlk and EndRule junctions to remove/detect infinite recursion from\r
61 * FIRST and FOLLOW calcs.\r
62 *\r
63 * If p->jtype == EndRule we are going to attempt a FOLLOW. (FOLLOWs are really defined\r
64 * in terms of FIRST's, however). To proceed with the FOLLOW, p->halt cannot be\r
65 * set. p->halt is set to indicate that a reference to the current rule is in progress\r
66 * and the FOLLOW is not desirable.\r
67 *\r
68 * If we attempt a FOLLOW and find that there is no FOLLOW or REACHing beyond the EndRule\r
69 * junction yields an empty set, replace the empty set with EOF. No FOLLOW means that\r
70 * only EOF can follow the current rule. This normally occurs only on the start symbol\r
71 * since all other rules are referenced by another rule somewhere.\r
72 *\r
73 * Normally, both p1 and p2 are followed. However, checking p2 on a RuleBlk node is\r
74 * the same as checking the next rule which is clearly incorrect.\r
75 *\r
76 * Cycles in the FOLLOW sense are possible. e.g. Fo(c) requires Fo(b) which requires\r
77 * Fo(c). Both Fo(b) and Fo(c) are defined to be Fo(b) union Fo(c). Let's say\r
78 * Fo(c) is attempted first. It finds all of the FOLLOW symbols and then attempts\r
79 * to do Fo(b) which finds of its FOLLOW symbols. So, we have:\r
80 *\r
81 * Fo(c)\r
82 * / \\r
83 * a set Fo(b)\r
84 * / \\r
85 * a set Fo(c) .....Hmmmm..... Infinite recursion!\r
86 *\r
87 * The 2nd Fo(c) is not attempted and Fo(b) is left deficient, but Fo(c) is now\r
88 * correctly Fo(c) union Fo(b). We wish to pick up where we left off, so the fact\r
89 * that Fo(b) terminated early means that we lack Fo(c) in the Fo(b) set already\r
90 * laying around. SOOOOoooo, we track FOLLOW cycles. All FOLLOW computations are\r
91 * cached in a hash table. After the sequence of FOLLOWs finish, we reconcile all\r
92 * cycles --> correct all Fo(rule) sets in the cache.\r
93 *\r
94 * Confused? Good! Read my MS thesis [Purdue Technical Report TR90-30].\r
95 * TJP 8/93 -- can now read PhD thesis from Purdue.\r
96 *\r
97 * Also, FIRST sets are cached in the hash table. Keys are (rulename,Fi/Fo,k).\r
98 * Only FIRST sets, for which the FOLLOW is not included, are stored.\r
99 *\r
100 * SPECIAL CASE of (...)+ blocks:\r
101 * I added an optional alt so that the alts could see what\r
102 * was behind the (...)+ block--thus using enough lookahead\r
103 * to branch out rather than just enough to distinguish\r
104 * between alts in the (...)+. However, when the FIRST("(...)+") is\r
105 * is needed, must not use this last "optional" alt. This routine\r
106 * turns off this path by setting a new 'ignore' flag for\r
107 * the alt and then resetting it afterwards.\r
108 */\r
109\r
110set\r
111#ifdef __USE_PROTOS\r
112rJunc( Junction *p, int k, set *rk )\r
113#else\r
114rJunc( p, k, rk )\r
115Junction *p;\r
116int k;\r
117set *rk;\r
118#endif\r
119{\r
120 set a, b;\r
121\r
122 require(p!=NULL, "rJunc: NULL node");\r
123 require(p->ntype==nJunction, "rJunc: not junction");\r
124\r
125#ifdef DBG_LL1\r
126 if ( p->jtype == RuleBlk ) fprintf(stderr, "FIRST(%s,%d) \n",((Junction *)p)->rname,k);\r
127 else fprintf(stderr, "rJunc: %s in rule %s\n",\r
128 decodeJType[p->jtype], ((Junction *)p)->rname);\r
129#endif\r
130 /* if this is one of the added optional alts for (...)+ then return */\r
131\r
132 /* no need to pop backtrace - hasn't been pushed */\r
133\r
134 if ( p->ignore ) return empty;\r
135\r
136 if (MR_MaintainBackTrace) MR_pointerStackPush(&MR_BackTraceStack,p);\r
137\r
138/* MR14 */ if (AlphaBetaTrace && p->alpha_beta_guess_end) {\r
139/* MR14 */ warnFL(\r
140/* MR14 */ "not possible to compute follow set for alpha in an \"(alpha)? beta\" block. ",\r
141/* MR14 */ FileStr[p->file],p->line);\r
142/* MR14 */ MR_alphaBetaTraceReport();\r
143/* MR14 */ };\r
144\r
145/* MR14 */ if (p->alpha_beta_guess_end) {\r
146/* MR14 */ if (MR_MaintainBackTrace) MR_pointerStackPop(&MR_BackTraceStack);\r
147/* MR14 */ return empty;\r
148/* MR14 */ }\r
149\r
150 /* locks are valid for aLoopBlk,aPlusBlk,RuleBlk,EndRule junctions only */\r
151 if ( p->jtype==aLoopBlk || p->jtype==RuleBlk ||\r
152 p->jtype==aPlusBlk || p->jtype==EndRule )\r
153 {\r
154 require(p->lock!=NULL, "rJunc: lock array is NULL");\r
155 if ( p->lock[k] )\r
156 {\r
157 if ( p->jtype == EndRule ) /* FOLLOW cycle? */\r
158 {\r
159#ifdef DBG_LL1\r
160 fprintf(stderr, "FOLLOW cycle to %s: panic!\n", p->rname);\r
161#endif\r
162 if (! MR_AmbSourceSearch) RegisterCycle(p->rname, k);\r
163 }\r
164 if (MR_MaintainBackTrace) MR_pointerStackPop(&MR_BackTraceStack);\r
165 return empty;\r
166 }\r
167 if ( p->jtype == RuleBlk &&\r
168 p->end->halt &&\r
169 ! MR_AmbSourceSearch) /* check for FIRST cache */\r
170 {\r
171 CacheEntry *q = (CacheEntry *) hash_get(Fcache, Fkey(p->rname,'i',k));\r
172 if ( q != NULL )\r
173 {\r
174 set_orin(rk, q->rk);\r
175 if (MR_MaintainBackTrace) MR_pointerStackPop(&MR_BackTraceStack);\r
176 return set_dup( q->fset );\r
177 }\r
178 }\r
179 if ( p->jtype == EndRule &&\r
180 !p->halt && /* MR11 was using cache even when halt set */\r
181 ! MR_AmbSourceSearch) /* FOLLOW set cached already? */\r
182 {\r
183 CacheEntry *q = (CacheEntry *) hash_get(Fcache, Fkey(p->rname,'o',k));\r
184 if ( q != NULL )\r
185 {\r
186#ifdef DBG_LL1\r
187 fprintf(stderr, "cache for FOLLOW(%s,%d):", p->rname,k);\r
188 s_fprT(stderr, q->fset);\r
189 if ( q->incomplete ) fprintf(stderr, " (incomplete)");\r
190 fprintf(stderr, "\n");\r
191#endif\r
192 if ( !q->incomplete )\r
193 {\r
194 if (MR_MaintainBackTrace) MR_pointerStackPop(&MR_BackTraceStack);\r
195 return set_dup( q->fset );\r
196 }\r
197 }\r
198 }\r
199 p->lock[k] = TRUE; /* This rule is busy */\r
200 }\r
201\r
202 a = b = empty;\r
203\r
204 if ( p->jtype == EndRule )\r
205 {\r
206 if (p->halt ) /* don't want FOLLOW here? */ /* unless MR10 hoisting */\r
207 {\r
208 p->lock[k] = FALSE;\r
209 set_orel(k, rk); /* indicate this k value needed */\r
210 if (MR_MaintainBackTrace) MR_pointerStackPop(&MR_BackTraceStack);\r
211 return empty;\r
212 }\r
213 if (! MR_AmbSourceSearch) FoPush(p->rname, k); /* Attempting FOLLOW */\r
214 if ( p->p1 == NULL ) set_orel((TokenInd!=NULL?TokenInd[EofToken]:EofToken), &a);/* if no FOLLOW assume EOF */\r
215#ifdef DBG_LL1\r
216 fprintf(stderr, "-->FOLLOW(%s,%d)\n", p->rname,k);\r
217#endif\r
218 }\r
219\r
220 if ( p->p1 != NULL ) {\r
221/* MR14 */ if (p->guess) {\r
222/* MR14 */ if (p->guess_analysis_point == NULL) {\r
223/* MR14 */ Node * guess_point;\r
224/* MR14 */ guess_point=(Node *)analysis_point(p);\r
225/* MR14 */ if (guess_point == (Node *)p) {\r
226/* MR14 */ guess_point=p->p1;\r
227/* MR14 */ }\r
228/* MR14 */ p->guess_analysis_point=guess_point;\r
229/* MR14 */ }\r
230/* MR14 */ REACH(p->guess_analysis_point, k, rk, a);\r
231 } else {\r
232 REACH(p->p1, k, rk, a);\r
233 }\r
234 } \r
235\r
236 /* C a c h e R e s u l t s */\r
237\r
238 if ( p->jtype == RuleBlk && p->end->halt && ! MR_AmbSourceSearch) /* can save FIRST set? */\r
239 {\r
240 CacheEntry *q = newCacheEntry( Fkey(p->rname,'i',k) );\r
241 /*fprintf(stderr, "Caching %s FIRST %d\n", p->rname, k);*/\r
242 hash_add(Fcache, Fkey(p->rname,'i',k), (Entry *)q);\r
243 q->fset = set_dup( a );\r
244 q->rk = set_dup( *rk );\r
245 }\r
246\r
247 if ( p->jtype == EndRule &&\r
248 !p->halt && /* MR11 was using cache even with halt set */\r
249 ! MR_AmbSourceSearch) /* just completed FOLLOW? */\r
250 {\r
251 /* Cache Follow set */\r
252 CacheEntry *q = (CacheEntry *) hash_get(Fcache, Fkey(p->rname,'o',k));\r
253 if ( q==NULL )\r
254 {\r
255 q = newCacheEntry( Fkey(p->rname,'o',k) );\r
256 hash_add(Fcache, Fkey(p->rname,'o',k), (Entry *)q);\r
257 }\r
258 /*fprintf(stderr, "Caching %s FOLLOW %d\n", p->rname, k);*/\r
259 if ( set_nil(a) && !q->incomplete )\r
260 {\r
261 /* Don't ever save a nil set as complete.\r
262 * Turn it into an eof set.\r
263 */\r
264 set_orel(EofToken, &a);\r
265 }\r
266 set_orin(&(q->fset), a);\r
267 FoPop( k );\r
268 if ( FoTOS[k] == NULL && Cycles[k] != NULL ) ResolveFoCycles(k);\r
269#ifdef DBG_LL1\r
270 fprintf(stderr, "saving FOLLOW(%s,%d):", p->rname, k);\r
271 s_fprT(stderr, q->fset);\r
272 if ( q->incomplete ) fprintf(stderr, " (incomplete)");\r
273 fprintf(stderr, "\n");\r
274#endif\r
275 }\r
276 \r
277 if (p->jtype != RuleBlk && p->p2 != NULL && /* MR14 */ ! p->guess) {\r
278 REACH(p->p2, k, rk, b);\r
279 } \r
280\r
281 if ( p->jtype==aLoopBlk || p->jtype==RuleBlk ||\r
282 p->jtype==aPlusBlk || p->jtype==EndRule )\r
283 p->lock[k] = FALSE; /* unlock node */\r
284\r
285 set_orin(&a, b);\r
286 set_free(b);\r
287 if (MR_MaintainBackTrace) MR_pointerStackPop(&MR_BackTraceStack);\r
288 return a;\r
289}\r
290\r
291set\r
292#ifdef __USE_PROTOS\r
293rRuleRef( RuleRefNode *p, int k, set *rk_out )\r
294#else\r
295rRuleRef( p, k, rk_out )\r
296RuleRefNode *p;\r
297int k;\r
298set *rk_out;\r
299#endif\r
300{\r
301 set rk;\r
302 Junction *r;\r
303 int k2;\r
304 set a, rk2, b;\r
305 int save_halt;\r
306 RuleEntry *q = (RuleEntry *) hash_get(Rname, p->text);\r
307 require(p!=NULL, "rRuleRef: NULL node");\r
308 require(p->ntype==nRuleRef, "rRuleRef: not rule ref");\r
309\r
310#ifdef DBG_LL1\r
311 fprintf(stderr, "rRuleRef: %s\n", p->text);\r
312#endif\r
313\r
314 if (MR_MaintainBackTrace) MR_pointerStackPush(&MR_BackTraceStack,p);\r
315\r
316 if ( q == NULL )\r
317 {\r
318 warnFL( eMsg1("rule %s not defined",p->text), FileStr[p->file], p->line );\r
319 REACH(p->next, k, rk_out, a);\r
320 if (MR_MaintainBackTrace) MR_pointerStackPop(&MR_BackTraceStack);\r
321 return a;\r
322 }\r
323 rk2 = empty;\r
324\r
325/* MR9 Problems with rule references in guarded predicates */\r
326/* MR9 Perhaps can use hash table to find rule ? */\r
327\r
328/* MR9 */ if (RulePtr == NULL) {\r
329/* MR9 */ fatalFL(eMsg2("Rule %s uses rule %s via RulePtr before it has been initialized",\r
330/* MR9 */ p->rname,q->str),FileStr[p->file],p->line);\r
331/* MR9 */ };\r
332\r
333 r = RulePtr[q->rulenum];\r
334 if ( r->lock[k] )\r
335 {\r
336 errNoFL( eMsg2("infinite left-recursion to rule %s from rule %s",\r
337 r->rname, p->rname) );\r
338\r
339 if (MR_MaintainBackTrace) MR_pointerStackPop(&MR_BackTraceStack);\r
340\r
341 return empty;\r
342 }\r
343\r
344 save_halt = r->end->halt;\r
345 r->end->halt = TRUE; /* don't let reach fall off end of rule here */\r
346 rk = empty;\r
347 REACH(r, k, &rk, a);\r
348 r->end->halt = save_halt;\r
349 while ( !set_nil(rk) ) {\r
350 k2 = set_int(rk); /* MR11 this messes up the ambiguity search routine */\r
351 set_rm(k2, rk);\r
352 REACH(p->next, k2, &rk2, b); /* MR11 by changing the value of k */\r
353 set_orin(&a, b);\r
354 set_free(b);\r
355 }\r
356 set_free(rk); /* this has no members, but free it's memory */\r
357 set_orin(rk_out, rk2); /* remember what we couldn't do */\r
358 set_free(rk2);\r
359 if (MR_MaintainBackTrace) MR_pointerStackPop(&MR_BackTraceStack);\r
360 return a;\r
361}\r
362\r
363/*\r
364 * Return FIRST sub k ( token_node )\r
365 *\r
366 * TJP 10/11/93 modified this so that token nodes that are actually\r
367 * ranges (T1..T2) work.\r
368 */\r
369set\r
370#ifdef __USE_PROTOS\r
371rToken( TokNode *p, int k, set *rk )\r
372#else\r
373rToken( p, k, rk )\r
374TokNode *p;\r
375int k;\r
376set *rk;\r
377#endif\r
378{\r
379 set a;\r
380\r
381 require(p!=NULL, "rToken: NULL node");\r
382 require(p->ntype==nToken, "rToken: not token node");\r
383\r
384#ifdef DBG_LL1\r
385 fprintf(stderr, "rToken: %s\n", (TokenString(p->token)!=NULL)?TokenString(p->token):\r
386 ExprString(p->token));\r
387#endif\r
388\r
389\r
390 if (MR_MaintainBackTrace) MR_pointerStackPush(&MR_BackTraceStack,p);\r
391\r
392 if (MR_AmbSourceSearch && (k-1) == 0) {\r
393\r
394 set localConstrain;\r
395 set intersection;\r
396\r
397 localConstrain=fset[maxk-k+1];\r
398\r
399 if (! set_nil(p->tset)) {\r
400 intersection=set_and(localConstrain,p->tset);\r
401 if (! set_nil(intersection)) {\r
402 MR_backTraceReport();\r
403 };\r
404 set_free(intersection);\r
405 } else {\r
406 if (set_el( (unsigned) p->token,localConstrain)) {\r
407 MR_backTraceReport();\r
408 }\r
409 };\r
410 };\r
411\r
412 if ( k-1 == 0 ) {\r
413\r
414 if (MR_MaintainBackTrace) MR_pointerStackPop(&MR_BackTraceStack);\r
415\r
416 if ( !set_nil(p->tset) ) {\r
417 return set_dup(p->tset);\r
418 } else {\r
419 return set_of(p->token);\r
420 };\r
421 }\r
422\r
423 REACH(p->next, k-1, rk, a);\r
424 \r
425 if (MR_MaintainBackTrace) MR_pointerStackPop(&MR_BackTraceStack);\r
426\r
427 return a;\r
428}\r
429\r
430set\r
431#ifdef __USE_PROTOS\r
432rAction( ActionNode *p, int k, set *rk )\r
433#else\r
434rAction( p, k, rk )\r
435ActionNode *p;\r
436int k;\r
437set *rk;\r
438#endif\r
439{\r
440 set a;\r
441\r
442 require(p!=NULL, "rJunc: NULL node");\r
443 require(p->ntype==nAction, "rJunc: not action");\r
444 \r
445/* MR11 */ if (p->is_predicate && p->ampersandPred != NULL) {\r
446/* MR11 */ Predicate *pred=p->ampersandPred;\r
447/* MR11 */ if (k <= pred->k) {\r
448/* MR11 */ REACH(p->guardNodes,k,rk,a);\r
449/* MR11 */ return a;\r
450/* MR11 */ };\r
451/* MR11 */ };\r
452\r
453 /* it might be a good idea when doing an MR_AmbSourceSearch\r
454 to *not* look behind predicates under some circumstances\r
455 we'll look into that later\r
456 */\r
457\r
458 REACH(p->next, k, rk, a); /* ignore actions */\r
459 return a;\r
460}\r
461\r
462 /* A m b i g u i t y R e s o l u t i o n */\r
463\r
464\r
465void\r
466#ifdef __USE_PROTOS\r
467dumpAmbigMsg( set *fset, FILE *f, int want_nls )\r
468#else\r
469dumpAmbigMsg( fset, f, want_nls )\r
470set *fset;\r
471FILE *f;\r
472int want_nls;\r
473#endif\r
474{\r
475 int i;\r
476\r
477 set copy; /* MR11 */\r
478\r
479 if ( want_nls ) fprintf(f, "\n\t");\r
480 else fprintf(f, " ");\r
481\r
482 for (i=1; i<=CLL_k; i++)\r
483 {\r
484 copy=set_dup(fset[i]); /* MR11 */\r
485\r
486 if ( i>1 )\r
487 {\r
488 if ( !want_nls ) fprintf(f, ", ");\r
489 }\r
490 if ( set_deg(copy) > 3 && elevel == 1 )\r
491 {\r
492 int e,m;\r
493 fprintf(f, "{");\r
494 for (m=1; m<=3; m++)\r
495 {\r
496 e=set_int(copy);\r
497 fprintf(f, " %s", TerminalString(e));\r
498 set_rm(e, copy);\r
499 }\r
500 fprintf(f, " ... }");\r
501 }\r
502 else s_fprT(f, copy);\r
503 if ( want_nls ) fprintf(f, "\n\t");\r
504 set_free(copy);\r
505 }\r
506 fprintf(f, "\n");\r
507\r
508}\r
509\r
510static void\r
511#ifdef __USE_PROTOS\r
512verify_context(Predicate *predicate)\r
513#else\r
514verify_context(predicate)\r
515Predicate *predicate;\r
516#endif\r
517{\r
518 if ( predicate == NULL ) return;\r
519\r
520 if ( predicate->expr == PRED_OR_LIST ||\r
521 predicate->expr == PRED_AND_LIST )\r
522 {\r
523 verify_context(predicate->down);\r
524 verify_context(predicate->right); /* MR10 */\r
525 return;\r
526 }\r
527\r
528 if ( !predicate->source->ctxwarned && predicate->source->guardpred==NULL &&\r
529 ((predicate->k > 1 &&\r
530 !is_single_tuple(predicate->tcontext)) ||\r
531 ( predicate->k == 1 &&\r
532 set_deg(predicate->scontext[1])>1 )) )\r
533 {\r
534\r
535/* MR9 Suppress annoying messages caused by our own clever(?) fix */\r
536\r
537 fprintf(stderr, ErrHdr, FileStr[predicate->source->file],\r
538 predicate->source->line);\r
539 fprintf(stderr, " warning: predicate applied for >1 lookahead %d-sequences\n", predicate->k);\r
540 fprintf(stderr, ErrHdr, FileStr[predicate->source->file],\r
541 predicate->source->line);\r
542 fprintf(stderr, " predicate text: \"%s\"\n",\r
543 (predicate->expr == NULL ? "(null)" : predicate->expr) );\r
544 fprintf(stderr, ErrHdr, FileStr[predicate->source->file],\r
545 predicate->source->line);\r
546 fprintf(stderr, " You may only want one lookahead %d-sequence to apply\n", predicate->k);\r
547 fprintf(stderr, ErrHdr, FileStr[predicate->source->file],\r
548 predicate->source->line);\r
549 fprintf(stderr, " Try using a context guard '(...)? =>'\n");\r
550 predicate->source->ctxwarned = 1;\r
551 }\r
552 verify_context(predicate->right); /* MR10 */\r
553}\r
554\r
555/*\r
556 * If delta is the set of ambiguous lookahead sequences, then make sure that\r
557 * the predicate(s) for productions alt1,alt2 cover the sequences in delta.\r
558 *\r
559 * For example,\r
560 * a : <<PRED1>>? (A B|A C)\r
561 * | b\r
562 * ;\r
563 * b : <<PRED2>>? A B\r
564 * | A C\r
565 * ;\r
566 *\r
567 * This should give a warning that (A C) predicts both productions and alt2\r
568 * does not have a predicate in the production that generates (A C).\r
569 *\r
570 * The warning detection is simple. Let delta = LOOK(alt1) intersection LOOK(alt2).\r
571 * Now, if ( delta set-difference context(predicates-for-alt1) != empty then\r
572 * alt1 does not "cover" all ambiguous sequences.\r
573 *\r
574 * If ambig is nonempty, then ambig in LL(k) sense -> use tree info; else use fset\r
575 * info. Actually, sets are used only if k=1 for this grammar.\r
576 */\r
577static void\r
578#ifdef __USE_PROTOS\r
579ensure_predicates_cover_ambiguous_lookahead_sequences\r
580 ( Junction *alt1, Junction *alt2, char *sub, Tree *ambig )\r
581#else\r
582ensure_predicates_cover_ambiguous_lookahead_sequences( alt1, alt2, sub, ambig )\r
583Junction *alt1;\r
584Junction *alt2;\r
585char *sub;\r
586Tree *ambig;\r
587#endif\r
588{\r
589 if ( !ParseWithPredicates ) return;\r
590\r
591 if ( ambig!=NULL )\r
592 {\r
593 Tree *non_covered = NULL;\r
594 if ( alt1->predicate!=NULL )\r
595 non_covered = tdif(ambig, alt1->predicate, alt1->fset, alt2->fset);\r
596 if ( (non_covered!=NULL || alt1->predicate==NULL) && WarningLevel>1 )\r
597 {\r
598 fprintf(stderr, ErrHdr, FileStr[alt1->file], alt1->line);\r
599 fprintf(stderr, " warning: alt %d %shas no predicate to resolve ambiguity",\r
600 alt1->altnum, sub);\r
601 if ( alt1->predicate!=NULL && non_covered!=NULL )\r
602 {\r
603 fprintf(stderr, " upon");\r
604 preorder(non_covered);\r
605 }\r
606 else if ( alt1->predicate==NULL )\r
607 {\r
608 fprintf(stderr, " upon");\r
609 preorder(ambig->down);\r
610 }\r
611 fprintf(stderr, "\n");\r
612 }\r
613 Tfree(non_covered);\r
614 non_covered = NULL;\r
615 if ( alt2->predicate!=NULL )\r
616 non_covered = tdif(ambig, alt2->predicate, alt1->fset, alt2->fset);\r
617 if ( (non_covered!=NULL || alt2->predicate==NULL) && WarningLevel>1 )\r
618 {\r
619 fprintf(stderr, ErrHdr, FileStr[alt2->file], alt2->line);\r
620 fprintf(stderr, " warning: alt %d %shas no predicate to resolve ambiguity",\r
621 alt2->altnum, sub);\r
622 if ( alt2->predicate!=NULL && non_covered!=NULL )\r
623 {\r
624 fprintf(stderr, " upon");\r
625 preorder(non_covered);\r
626 }\r
627 else if ( alt2->predicate==NULL )\r
628 {\r
629 fprintf(stderr, " upon");\r
630 preorder(ambig->down);\r
631 }\r
632 fprintf(stderr, "\n");\r
633 }\r
634 Tfree(non_covered);\r
635 }\r
636 else if ( !set_nil(alt1->fset[1]) )\r
637 {\r
638 set delta, non_covered;\r
639 delta = set_and(alt1->fset[1], alt2->fset[1]);\r
640 non_covered = set_dif(delta, covered_set(alt1->predicate));\r
641 if ( set_deg(non_covered)>0 && WarningLevel>1 )\r
642 {\r
643 fprintf(stderr, ErrHdr, FileStr[alt1->file], alt1->line);\r
644 fprintf(stderr, " warning: alt %d %shas no predicate to resolve ambiguity",\r
645 alt1->altnum, sub);\r
646 if ( alt1->predicate!=NULL )\r
647 {\r
648 fprintf(stderr, " upon ");\r
649 s_fprT(stderr, non_covered);\r
650 }\r
651 fprintf(stderr, "\n");\r
652 }\r
653 set_free( non_covered );\r
654 non_covered = set_dif(delta, covered_set(alt2->predicate));\r
655 if ( set_deg(non_covered)>0 && WarningLevel>1 )\r
656 {\r
657 fprintf(stderr, ErrHdr, FileStr[alt2->file], alt2->line);\r
658 fprintf(stderr, " warning: alt %d %shas no predicate to resolve ambiguity",\r
659 alt2->altnum, sub);\r
660 if ( alt2->predicate!=NULL )\r
661 {\r
662 fprintf(stderr, " upon ");\r
663 s_fprT(stderr, non_covered);\r
664 }\r
665 fprintf(stderr, "\n");\r
666 }\r
667 set_free( non_covered );\r
668 set_free( delta );\r
669 }\r
670 else fatal_internal("productions have no lookahead in predicate checking routine");\r
671}\r
672\r
673#ifdef __USE_PROTOS\r
674void MR_doPredicatesHelp(int inGuessBlock,Junction *alt1,Junction *alt2,int jtype,char *sub)\r
675#else\r
676void MR_doPredicatesHelp(inGuessBlock,alt1,alt2,jtype,sub)\r
677 int inGuessBlock;\r
678 Junction *alt1;\r
679 Junction *alt2;\r
680 int jtype;\r
681 char *sub;\r
682#endif\r
683{\r
684 Predicate *p1;\r
685 Predicate *p2;\r
686\r
687 Junction *parentRule=MR_nameToRuleBlk(alt1->rname);\r
688\r
689 if (inGuessBlock && WarningLevel <= 1) return;\r
690\r
691 /* let antlr give the usual error message */\r
692\r
693 if (alt1->predicate == NULL && alt2->predicate == NULL) return;\r
694\r
695 if ( (jtype == RuleBlk || jtype == aSubBlk)\r
696 && (alt1->predicate == NULL && alt2->predicate != NULL)) {\r
697 fprintf(stderr, ErrHdr, FileStr[parentRule->file],parentRule->line);\r
698 fprintf(stderr," warning: alt %d line %d and alt %d line %d of %s\n%s%s%s",\r
699 alt1->altnum,\r
700 alt1->line,\r
701 alt2->altnum,\r
702 alt2->line,\r
703 sub,\r
704 " These alts have ambig lookahead sequences resolved by a predicate for\n",\r
705 " the second choice. The second choice may not be reachable.\n",\r
706 " You may want to use a complementary predicate or rearrange the alts\n"\r
707 );\r
708 return;\r
709 };\r
710\r
711 /* first do the easy comparison. then do the hard one */\r
712\r
713 if (MR_comparePredicates(alt1->predicate,alt2->predicate)) {\r
714\r
715 if (jtype == aLoopBegin || jtype == aPlusBlk ) {\r
716\r
717 /* I'm not sure this code is reachable.\r
718 Predicates following a (...)+ or (...)* block are probably\r
719 considered validation predicates and therefore not\r
720 participate in the predication expression\r
721 */\r
722\r
723 fprintf(stderr, ErrHdr,FileStr[parentRule->file],parentRule->line);\r
724 fprintf(stderr," warning: %s of %s in rule %s\n (file %s alt %d line %d and alt %d line %d)\n%s",\r
725 "the predicates used to disambiguate optional/exit paths of ",\r
726 sub,\r
727 CurRule,\r
728 FileStr[alt1->file],\r
729 alt1->altnum,\r
730 alt1->line,\r
731 alt2->altnum,\r
732 alt2->line,\r
733 " are identical and have no resolving power\n");\r
734 } else {\r
735 fprintf(stderr, ErrHdr, FileStr[parentRule->file], parentRule->line);\r
736 fprintf(stderr," warning: %s rule %s\n (file %s alt %d line %d and alt %d line %d)\n%s",\r
737 "the predicates used to disambiguate",\r
738 CurRule,\r
739 FileStr[alt1->file],\r
740 alt1->altnum,\r
741 alt1->line,\r
742 alt2->altnum,\r
743 alt2->line,\r
744 " are identical and have no resolving power\n");\r
745 };\r
746 } else {\r
747 p1=predicate_dup_without_context(alt1->predicate);\r
748 p1=MR_unfold(p1);\r
749 MR_clearPredEntry(p1);\r
750 MR_simplifyInverted(p1,0);\r
751 p1=MR_predSimplifyALL(p1);\r
752 p2=predicate_dup_without_context(alt2->predicate);\r
753 p2=MR_unfold(p2);\r
754 MR_clearPredEntry(p2);\r
755 MR_simplifyInverted(p2,0);\r
756 p2=MR_predSimplifyALL(p2);\r
757 if (MR_comparePredicates(p1,p2)) {\r
758 if (jtype == aLoopBegin || jtype == aPlusBlk ) {\r
759 fprintf(stderr, ErrHdr, FileStr[parentRule->file], parentRule->line);\r
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",\r
761 "the predicates used to disambiguate optional/exit paths of ",\r
762 sub,\r
763 CurRule,\r
764 FileStr[alt1->file],\r
765 alt1->altnum,\r
766 alt1->line,\r
767 alt2->altnum,\r
768 alt2->line,\r
769 " are identical when compared without context and may have no\n",\r
770 " resolving power for some lookahead sequences.\n");\r
771 } else {\r
772 fprintf(stderr, ErrHdr, FileStr[parentRule->file], parentRule->line);\r
773 fprintf(stderr," warning: %s rule %s\n (file %s alt %d line %d and alt %d line %d)\n%s%s",\r
774 "the predicates used to disambiguate",\r
775 CurRule,\r
776 FileStr[alt1->file],\r
777 alt1->altnum,\r
778 alt1->line,\r
779 alt2->altnum,\r
780 alt2->line,\r
781 " are identical when compared without context and may have no\n",\r
782 " resolving power for some lookahead sequences.\n");\r
783 };\r
784 if (InfoP) {\r
785 fprintf(output,"\n#if 0\n\n");\r
786 fprintf(output,"The following predicates are identical when compared without\n");\r
787 fprintf(output," lookahead context information. For some ambiguous lookahead\n");\r
788 fprintf(output," sequences they may not have any power to resolve the ambiguity.\n");\r
789 fprintf(output,"\n");\r
790\r
791 fprintf(output,"Choice 1: %s alt %d line %d file %s\n\n",\r
792 MR_ruleNamePlusOffset( (Node *) alt1),\r
793 alt1->altnum,\r
794 alt1->line,\r
795 FileStr[alt1->file]);\r
796 fprintf(output," The original predicate for choice 1 with available context information:\n\n");\r
797 MR_dumpPred1(2,alt1->predicate,1);\r
798 fprintf(output," The predicate for choice 1 after expansion (but without context information):\n\n");\r
799 MR_dumpPred1(2,p1,0);\r
800 if (p1 == NULL) {\r
801 Predicate *phelp;\r
802 fprintf(output," The predicate for choice 1 after expansion (but before simplification)\n\n");\r
803 phelp=predicate_dup_without_context(alt1->predicate);\r
804 phelp=MR_unfold(phelp);\r
805 MR_clearPredEntry(phelp);\r
806 MR_simplifyInverted(phelp,0);\r
807 phelp=MR_predSimplifyALLX(phelp,1);\r
808 MR_dumpPred1(2,phelp,0);\r
809 predicate_free(phelp);\r
810 };\r
811 fprintf(output,"\n");\r
812\r
813 fprintf(output,"Choice 2: %s alt %d line %d file %s\n\n",\r
814 MR_ruleNamePlusOffset( (Node *) alt2),\r
815 alt2->altnum,\r
816 alt2->line,\r
817 FileStr[alt2->file]);\r
818 fprintf(output," The original predicate for choice 2 with available context information:\n\n");\r
819 MR_dumpPred1(1,alt2->predicate,1);\r
820 fprintf(output," The predicate for choice 2 after expansion (but without context information):\n\n");\r
821 MR_dumpPred1(1,p2,0);\r
822 if (p2 == NULL) {\r
823 Predicate *phelp;\r
824 fprintf(output," The predicate for choice 2 after expansion (but before simplification)\n\n");\r
825 phelp=predicate_dup_without_context(alt2->predicate);\r
826 phelp=MR_unfold(phelp);\r
827 MR_clearPredEntry(phelp);\r
828 MR_simplifyInverted(phelp,0);\r
829 phelp=MR_predSimplifyALLX(phelp,1);\r
830 MR_dumpPred1(2,phelp,0);\r
831 predicate_free(phelp);\r
832 };\r
833 fprintf(output,"\n#endif\n");\r
834 };\r
835 } else if (MR_secondPredicateUnreachable(p1,p2)) {\r
836 if (jtype == aLoopBegin || jtype == aPlusBlk ) {\r
837 fprintf(stderr, ErrHdr, FileStr[parentRule->file], parentRule->line);\r
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",\r
839 "the predicate used to disambiguate the first choice of the optional/exit paths of ",\r
840 sub,\r
841 CurRule,\r
842 FileStr[alt1->file],\r
843 alt1->altnum,\r
844 alt1->line,\r
845 alt2->altnum,\r
846 alt2->line,\r
847 " appears to \"cover\" the second predicate when compared without context.\n",\r
848 " The second predicate may have no resolving power for some lookahead sequences.\n");\r
849 } else {\r
850 fprintf(stderr, ErrHdr, FileStr[parentRule->file], parentRule->line);\r
851 fprintf(stderr," warning: %s rule %s\n (file %s alt %d line %d and alt %d line %d)\n%s%s",\r
852 "the predicate used to disambiguate the first choice of",\r
853 CurRule,\r
854 FileStr[alt1->file],\r
855 alt1->altnum,\r
856 alt1->line,\r
857 alt2->altnum,\r
858 alt2->line,\r
859 " appears to \"cover\" the second predicate when compared without context.\n",\r
860 " The second predicate may have no resolving power for some lookahead sequences.\n");\r
861 };\r
862 if (InfoP) {\r
863 fprintf(output,"\n#if 0\n\n");\r
864 fprintf(output,"The first predicate appears to \"cover\" the second predicate when they\n");\r
865 fprintf(output," are compared without lookahead context information. For some ambiguous\n");\r
866 fprintf(output," lookahead sequences the second predicate may not have any power to\n");\r
867 fprintf(output," resolve the ambiguity.\n");\r
868 fprintf(output,"\n");\r
869 fprintf(output,"Choice 1: %s alt %d line %d file %s\n\n",\r
870 MR_ruleNamePlusOffset( (Node *) alt1),\r
871 alt1->altnum,\r
872 alt1->line,\r
873 FileStr[alt1->file]);\r
874 fprintf(output," The original predicate for choice 1 with available context information:\n\n");\r
875 MR_dumpPred1(2,alt1->predicate,1);\r
876 fprintf(output," The predicate for choice 1 after expansion (but without context information):\n\n");\r
877 MR_dumpPred1(2,p1,0);\r
878 if (p1 == NULL) {\r
879 Predicate *phelp;\r
880 fprintf(output," The predicate for choice 1 after expansion (but before simplification)\n\n");\r
881 phelp=predicate_dup_without_context(alt1->predicate);\r
882 phelp=MR_unfold(phelp);\r
883 MR_clearPredEntry(phelp);\r
884 MR_simplifyInverted(phelp,0);\r
885 phelp=MR_predSimplifyALLX(phelp,1);\r
886 MR_dumpPred1(2,phelp,0);\r
887 predicate_free(phelp);\r
888 };\r
889 fprintf(output,"\n");\r
890\r
891 fprintf(output,"Choice 2: %s alt %d line %d file %s\n\n",\r
892 MR_ruleNamePlusOffset( (Node *) alt2),\r
893 alt2->altnum,\r
894 alt2->line,\r
895 FileStr[alt2->file]);\r
896 fprintf(output," The original predicate for choice 2 with available context information:\n\n");\r
897 MR_dumpPred1(1,alt2->predicate,1);\r
898 fprintf(output," The predicate for choice 2 after expansion (but without context information):\n\n");\r
899 MR_dumpPred1(1,p2,0);\r
900 if (p2 == NULL) {\r
901 Predicate *phelp;\r
902 fprintf(output," The predicate for choice 2 after expansion (but before simplification)\n\n");\r
903 phelp=predicate_dup_without_context(alt2->predicate);\r
904 phelp=MR_unfold(phelp);\r
905 MR_clearPredEntry(phelp);\r
906 MR_simplifyInverted(phelp,0);\r
907 phelp=MR_predSimplifyALLX(phelp,1);\r
908 MR_dumpPred1(2,phelp,0);\r
909 predicate_free(phelp);\r
910 };\r
911 fprintf(output,"\n#endif\n");\r
912 };\r
913 };\r
914 predicate_free(p1);\r
915 predicate_free(p2);\r
916 };\r
917}\r
918\r
919static int totalOverflow=0; /* MR9 */\r
920\r
921void\r
922#ifdef __USE_PROTOS\r
923HandleAmbiguity( Junction *block, Junction *alt1, Junction *alt2, int jtype )\r
924#else\r
925HandleAmbiguity( block, alt1, alt2, jtype )\r
926Junction *block;\r
927Junction *alt1;\r
928Junction *alt2;\r
929int jtype;\r
930#endif\r
931{\r
932 unsigned **ftbl;\r
933 set *fset, b;\r
934 int i, numAmbig,n2;\r
935 Tree *ambig=NULL, *t, *u;\r
936 char *sub = "";\r
937 long n;\r
938 int thisOverflow=0; /* MR9 */\r
939 long set_deg_value; /* MR10 */\r
940 long threshhold; /* MR10 */\r
941\r
942 require(block!=NULL, "NULL block");\r
943 require(block->ntype==nJunction, "invalid block");\r
944\r
945 /* These sets are used to constrain LL_k set, but are made CLL_k long anyway */\r
946 fset = (set *) calloc(CLL_k+1, sizeof(set));\r
947 require(fset!=NULL, "cannot allocate fset");\r
948 ftbl = (unsigned **) calloc(CLL_k+1, sizeof(unsigned *));\r
949 require(ftbl!=NULL, "cannot allocate ftbl");\r
950\r
951 /* create constraint table and count number of possible ambiguities (use<=LL_k) */\r
952 for (n=1,i=1; i<=CLL_k; i++)\r
953 {\r
954 b = set_and(alt1->fset[i], alt2->fset[i]);\r
955/* MR9 */ set_deg_value = set_deg(b);\r
956/* MR10 */ if (n > 0) {\r
957/* MR10 */ threshhold = LONG_MAX / n;\r
958/* MR10 */ if (set_deg_value <= threshhold) {\r
959/* MR10 */ n *= set_deg_value;\r
960/* MR10 */ } else {\r
961/* MR10 */ n=LONG_MAX;\r
962/* MR9 */ if (totalOverflow == 0) {\r
963#if 0\r
964 /* MR10 comment this out because it just makes users worry */\r
965\r
966/* MR9 */ warnNoFL("Overflow in computing number of possible ambiguities in HandleAmbiguity\n");\r
967#endif\r
968/* MR9 */ };\r
969/* MR9 */ thisOverflow++;\r
970/* MR9 */ totalOverflow++;\r
971/* MR9 */ };\r
972/* MR10 */ } else {\r
973/* MR10 */ n *= set_deg_value;\r
974/* MR9 */ };\r
975 fset[i] = set_dup(b);\r
976 ftbl[i] = set_pdq(b);\r
977 set_free(b);\r
978 }\r
979\r
980 switch ( jtype )\r
981 {\r
982 case aSubBlk: sub = "of (..) "; break;\r
983 case aOptBlk: sub = "of {..} "; break;\r
984 case aLoopBegin: sub = "of (..)* "; break;\r
985 case aLoopBlk: sub = "of (..)* "; break;\r
986 case aPlusBlk: sub = "of (..)+ "; break;\r
987 case RuleBlk: sub = "of the rule itself "; break;\r
988 default : sub = ""; break;\r
989 }\r
990\r
991 /* If the block is marked as a compressed lookahead only block, then\r
992 * simply return; ambiguity warning is given only at warning level 2.\r
993 */\r
994 if ( block->approx>0 )\r
995 {\r
996 if ( ParseWithPredicates )\r
997 {\r
998 if (alt1->predicate != NULL) predicate_free(alt1->predicate); /* MR12 */\r
999 if (alt2->predicate != NULL) predicate_free(alt2->predicate); /* MR12 */\r
1000\r
1001 require(MR_PredRuleRefStack.count == 0,"PredRuleRef stack not empty");\r
1002 alt1->predicate = MR_find_predicates_and_supp((Node *)alt1->p1);\r
1003 require(MR_PredRuleRefStack.count == 0,"PredRuleRef stack not empty");\r
1004 require (MR_predicate_context_completed(alt1->predicate),"predicate alt 1 not completed");\r
1005 alt1->predicate=MR_predSimplifyALL(alt1->predicate);\r
1006\r
1007 require(MR_PredRuleRefStack.count == 0,"PredRuleRef stack not empty");\r
1008 alt2->predicate = MR_find_predicates_and_supp((Node *)alt2->p1);\r
1009 require(MR_PredRuleRefStack.count == 0,"PredRuleRef stack not empty");\r
1010 require (MR_predicate_context_completed(alt2->predicate),"predicate alt 2 not completed");\r
1011 alt2->predicate=MR_predSimplifyALL(alt2->predicate);\r
1012\r
1013 MR_doPredicatesHelp(0,alt1,alt2,jtype,sub);\r
1014\r
1015 if ( HoistPredicateContext\r
1016 && (alt1->predicate!=NULL||alt2->predicate!=NULL) )\r
1017 {\r
1018 verify_context(alt1->predicate);\r
1019 verify_context(alt2->predicate);\r
1020 }\r
1021\r
1022 if ( HoistPredicateContext\r
1023 && (alt1->predicate!=NULL||alt2->predicate!=NULL)\r
1024 && WarningLevel>1 )\r
1025 ensure_predicates_cover_ambiguous_lookahead_sequences(alt1, alt2, sub, ambig);\r
1026 }\r
1027\r
1028 if ( WarningLevel>1 )\r
1029 {\r
1030 fprintf(stderr, ErrHdr, FileStr[alt1->file], alt1->line);\r
1031 if ( jtype == aLoopBegin || jtype == aPlusBlk )\r
1032 fprintf(stderr, " warning: optional/exit path and alt(s) %sambiguous upon", sub);\r
1033 else\r
1034 fprintf(stderr, " warning(approx): alts %d and %d %sambiguous upon",\r
1035 alt1->altnum, alt2->altnum, sub);\r
1036 dumpAmbigMsg(fset, stderr, 0);\r
1037 MR_traceAmbSource(fset,alt1,alt2);\r
1038 }\r
1039 for (i=1; i<=CLL_k; i++) set_free( fset[i] );\r
1040 free((char *)fset);\r
1041 for (i=1; i<=CLL_k; i++) free( (char *)ftbl[i] );\r
1042 free((char *)ftbl);\r
1043 return;\r
1044 }\r
1045\r
1046 /* if all sets have degree 1 for k<LL_k, then must be ambig upon >=1 permutation;\r
1047 * don't bother doing full LL(k) analysis.\r
1048 * (This "if" block handles the LL(1) case)\r
1049 */\r
1050\r
1051 n2 = 0;\r
1052 for (i=1; i<LL_k; i++) n2 += set_deg(alt1->fset[i])+set_deg(alt2->fset[i]);\r
1053\r
1054 /* here STARTS the special case in which the lookahead sets for alt1 and alt2\r
1055 all have degree 1 for k<LL_k (including LL_k=1)\r
1056 */\r
1057\r
1058 if ( n2==2*(LL_k-1) )\r
1059 {\r
1060\r
1061 /* TJP: added to fix the case where LL(1) and syntactic predicates didn't\r
1062 * work. It now recognizes syntactic predicates, but does not like combo:\r
1063 * LL(1)/syn/sem predicates. (10/24/93)\r
1064 */\r
1065\r
1066 if ( first_item_is_guess_block_extra((Junction *)alt1->p1)!=NULL )\r
1067 {\r
1068 if ( WarningLevel==1 )\r
1069 {\r
1070 for (i=1; i<=CLL_k; i++) set_free( fset[i] );\r
1071 free((char *)fset);\r
1072 for (i=1; i<=CLL_k; i++) free( (char *)ftbl[i] );\r
1073 free((char *)ftbl);\r
1074 return;\r
1075 }\r
1076\r
1077 fprintf(stderr, ErrHdr, FileStr[alt1->file], alt1->line);\r
1078 if ( jtype == aLoopBegin || jtype == aPlusBlk )\r
1079 fprintf(stderr, " warning: optional/exit path and alt(s) %sambiguous upon", sub);\r
1080 else\r
1081 fprintf(stderr, " warning: alts %d and %d %sambiguous upon",\r
1082 alt1->altnum, alt2->altnum, sub);\r
1083 dumpAmbigMsg(fset, stderr, 0);\r
1084 MR_traceAmbSource(fset,alt1,alt2);\r
1085 }\r
1086\r
1087 ambig = NULL;\r
1088 if ( LL_k>1 ) ambig = make_tree_from_sets(alt1->fset, alt2->fset);\r
1089 if ( ParseWithPredicates )\r
1090 {\r
1091 if (alt1->predicate != NULL) predicate_free(alt1->predicate); /* MR12 */\r
1092 if (alt2->predicate != NULL) predicate_free(alt2->predicate); /* MR12 */\r
1093\r
1094 require(MR_PredRuleRefStack.count == 0,"PredRuleRef stack not empty");\r
1095 alt1->predicate = MR_find_predicates_and_supp((Node *)alt1->p1);\r
1096 require(MR_PredRuleRefStack.count == 0,"PredRuleRef stack not empty");\r
1097 require (MR_predicate_context_completed(alt1->predicate),"predicate alt 1 not completed");\r
1098 alt1->predicate=MR_predSimplifyALL(alt1->predicate);\r
1099\r
1100 require(MR_PredRuleRefStack.count == 0,"PredRuleRef stack not empty");\r
1101 alt2->predicate = MR_find_predicates_and_supp((Node *)alt2->p1);\r
1102 require(MR_PredRuleRefStack.count == 0,"PredRuleRef stack not empty");\r
1103 require (MR_predicate_context_completed(alt2->predicate),"predicate alt 2 not completed");\r
1104 alt2->predicate=MR_predSimplifyALL(alt2->predicate);\r
1105\r
1106 MR_doPredicatesHelp(0,alt1,alt2,jtype,sub);\r
1107\r
1108 if ( HoistPredicateContext && (alt1->predicate!=NULL||alt2->predicate!=NULL) )\r
1109 {\r
1110 verify_context(alt1->predicate);\r
1111 verify_context(alt2->predicate);\r
1112 }\r
1113 if (HoistPredicateContext&&(alt1->predicate!=NULL||alt2->predicate!=NULL) && WarningLevel>1)\r
1114 ensure_predicates_cover_ambiguous_lookahead_sequences(alt1, alt2, sub, ambig);\r
1115 if ( WarningLevel == 1 &&\r
1116 (alt1->predicate!=NULL||alt2->predicate!=NULL))\r
1117 {\r
1118 for (i=1; i<=CLL_k; i++) set_free( fset[i] );\r
1119 free((char *)fset);\r
1120 for (i=1; i<=CLL_k; i++) free( (char *)ftbl[i] );\r
1121 free((char *)ftbl);\r
1122 Tfree(ambig);\r
1123 return;\r
1124 }\r
1125 }\r
1126/* end TJP (10/24/93) */\r
1127\r
1128 fprintf(stderr, ErrHdr, FileStr[alt1->file], alt1->line);\r
1129 if ( jtype == aLoopBegin || jtype == aPlusBlk )\r
1130 fprintf(stderr, " warning: optional/exit path and alt(s) %sambiguous upon", sub);\r
1131 else\r
1132 fprintf(stderr, " warning: alts %d and %d %sambiguous upon",\r
1133 alt1->altnum, alt2->altnum, sub);\r
1134 if ( elevel == 3 && LL_k>1 )\r
1135 {\r
1136 preorder(ambig);\r
1137 fprintf(stderr, "\n");\r
1138 for (i=1; i<=CLL_k; i++) set_free( fset[i] );\r
1139 free((char *)fset);\r
1140 for (i=1; i<=CLL_k; i++) free( (char *)ftbl[i] );\r
1141 free((char *)ftbl);\r
1142 Tfree(ambig);\r
1143 return;\r
1144 };\r
1145\r
1146 Tfree(ambig);\r
1147 dumpAmbigMsg(fset, stderr, 0);\r
1148\r
1149 /* because this is a special case in which both alt1 and alt2 have\r
1150 lookahead sets of degree 1 for k<LL_k (including k=1) the linear\r
1151 lookahead style search is adequate\r
1152 */\r
1153\r
1154 MR_traceAmbSource(fset,alt1,alt2);\r
1155\r
1156 for (i=1; i<=CLL_k; i++) set_free( fset[i] );\r
1157 free((char *)fset);\r
1158 for (i=1; i<=CLL_k; i++) free( (char *)ftbl[i] );\r
1159 free((char *)ftbl);\r
1160 return;\r
1161 }\r
1162\r
1163 /* here ENDS the special case in which the lookahead sets for alt1 and alt2\r
1164 all have degree 1 for k<LL_k (including LL_k=1)\r
1165 */\r
1166\r
1167 /* in case tree construction runs out of memory, set info to make good err msg */\r
1168\r
1169 CurAmbigAlt1 = alt1->altnum;\r
1170 CurAmbigAlt2 = alt2->altnum;\r
1171 CurAmbigbtype = sub;\r
1172 CurAmbigfile = alt1->file;\r
1173 CurAmbigline = alt1->line;\r
1174 \r
1175 /* Don't do full LL(n) analysis if (...)? block because the block,\r
1176 by definition, defies LL(n) analysis.\r
1177 If guess (...)? block and ambiguous then don't remove anything from\r
1178 2nd alt to resolve ambig.\r
1179 Want to predict with LL sup 1 ( n ) decision not LL(n) if guess block\r
1180 since it is much cheaper than LL(n). LL sup 1 ( n ) "covers" the LL(n)\r
1181 lookahead information.\r
1182\r
1183 Note: LL(n) context cannot be computed for semantic predicates when\r
1184 followed by (..)?.\r
1185\r
1186 If (..)? then we scream "AAAHHHH! No LL(n) analysis will help"\r
1187\r
1188 Is 'ambig' always defined if we enter this if? I hope so\r
1189 because the 'ensure...()' func references it. TJP Nov 1993.\r
1190 */\r
1191\r
1192 /* THM MR30: Instead of using first_item_is_guss_block we use\r
1193 first_item_is_guess_block_extra which will look inside a\r
1194 loop block for a guess block. In other words ( (...)? )*.\r
1195 It there is an ambiguity in this circumstance then we suppress\r
1196 the normal methods of resolving ambiguities.\r
1197 */\r
1198\r
1199 if ( first_item_is_guess_block_extra((Junction *)alt1->p1)!=NULL )\r
1200 {\r
1201 if ( ParseWithPredicates )\r
1202 {\r
1203 if (alt1->predicate != NULL) predicate_free(alt1->predicate); /* MR12 */\r
1204 if (alt2->predicate != NULL) predicate_free(alt2->predicate); /* MR12 */\r
1205 require(MR_PredRuleRefStack.count == 0,"PredRuleRef stack not empty");\r
1206 alt1->predicate = MR_find_predicates_and_supp((Node *)alt1->p1);\r
1207 require(MR_PredRuleRefStack.count == 0,"PredRuleRef stack not empty");\r
1208 require (MR_predicate_context_completed(alt1->predicate),"predicate alt 1 not completed");\r
1209 alt1->predicate=MR_predSimplifyALL(alt1->predicate);\r
1210\r
1211 require(MR_PredRuleRefStack.count == 0,"PredRuleRef stack not empty");\r
1212 alt2->predicate = MR_find_predicates_and_supp((Node *)alt2->p1);\r
1213 require(MR_PredRuleRefStack.count == 0,"PredRuleRef stack not empty");\r
1214 require (MR_predicate_context_completed(alt2->predicate),"predicate alt 2 not completed");\r
1215 alt2->predicate=MR_predSimplifyALL(alt2->predicate);\r
1216\r
1217 MR_doPredicatesHelp(1,alt1,alt2,jtype,sub);\r
1218\r
1219 if ( HoistPredicateContext && (alt1->predicate!=NULL||alt2->predicate!=NULL) )\r
1220 {\r
1221 verify_context(alt1->predicate);\r
1222 verify_context(alt2->predicate);\r
1223 }\r
1224 if ( HoistPredicateContext && (alt1->predicate!=NULL||alt2->predicate!=NULL) && WarningLevel>1 )\r
1225 ensure_predicates_cover_ambiguous_lookahead_sequences(alt1, alt2, sub, ambig);\r
1226 if ( WarningLevel==1 &&\r
1227 (alt1->predicate!=NULL||alt2->predicate!=NULL))\r
1228 {\r
1229 for (i=1; i<=CLL_k; i++) set_free( fset[i] );\r
1230 free((char *)fset);\r
1231 for (i=1; i<=CLL_k; i++) free( (char *)ftbl[i] );\r
1232 free((char *)ftbl);\r
1233 return;\r
1234 }\r
1235 }\r
1236\r
1237 if ( WarningLevel>1 )\r
1238 {\r
1239 fprintf(stderr, ErrHdr, FileStr[alt1->file], alt1->line);\r
1240 if ( jtype == aLoopBegin || jtype == aPlusBlk )\r
1241 fprintf(stderr, " warning: optional/exit path and alt(s) %sambiguous upon", sub);\r
1242 else\r
1243 fprintf(stderr, " warning: alts %d and %d %sambiguous upon",\r
1244 alt1->altnum, alt2->altnum, sub);\r
1245 dumpAmbigMsg(fset, stderr, 0);\r
1246 MR_traceAmbSource(fset,alt1,alt2);\r
1247 }\r
1248\r
1249 for (i=1; i<=CLL_k; i++) set_free( fset[i] );\r
1250 free((char *)fset);\r
1251 for (i=1; i<=CLL_k; i++) free( (char *)ftbl[i] );\r
1252 free((char *)ftbl);\r
1253 return;\r
1254 }\r
1255 \r
1256 /* Not resolved with (..)? block. Do full LL(n) analysis */\r
1257 \r
1258 /* ambig is the set of k-tuples truly in common between alt 1 and alt 2 */\r
1259 /* MR11 VerifyAmbig once used fset destructively */\r
1260\r
1261 ambig = VerifyAmbig(alt1, alt2, ftbl, fset, &t, &u, &numAmbig);\r
1262\r
1263 /* are all things in intersection really ambigs? */\r
1264\r
1265 if (thisOverflow || numAmbig < n ) /* MR9 */\r
1266 {\r
1267 Tree *v;\r
1268\r
1269 /* remove ambig permutation from 2nd alternative to resolve ambig;\r
1270 * We want to compute the set of artificial tuples, arising from\r
1271 * LL sup 1 (n) compression, that collide with real tuples from the\r
1272 * 2nd alternative. This is the set of "special case" tuples that\r
1273 * the LL sup 1 (n) decision template maps incorrectly.\r
1274 */\r
1275\r
1276 /* when generating code in genExpr() it does\r
1277 *\r
1278 * if ( genExprSets(j->fset) && !genExprTree(j->ftree)) {...\r
1279 *\r
1280 * Sooooo the j->ftree is the tree of alt2\r
1281 * after removal of conflicts, not alt1 !\r
1282 */\r
1283\r
1284 if ( ambig!=NULL )\r
1285 {\r
1286 /* at the top of ambig is an ALT node */\r
1287\r
1288 for (v=ambig->down; v!=NULL; v=v->right)\r
1289 {\r
1290 u = trm_perm(u, v); /* remove v FROM u */\r
1291 }\r
1292/* fprintf(stderr, "after rm alt2:"); preorder(u); fprintf(stderr, "\n");*/\r
1293 }\r
1294 Tfree( t );\r
1295 alt1->ftree = tappend(alt1->ftree, u);\r
1296 alt1->ftree = tleft_factor(alt1->ftree);\r
1297 }\r
1298\r
1299 if ( ambig==NULL )\r
1300 {\r
1301 for (i=1; i<=CLL_k; i++) set_free( fset[i] );\r
1302 free((char *)fset);\r
1303 for (i=1; i<=CLL_k; i++) free( (char *)ftbl[i] );\r
1304 free((char *)ftbl);\r
1305 return;\r
1306 }\r
1307\r
1308 ambig = tleft_factor(ambig);\r
1309\r
1310/* TJP:\r
1311 * At this point, we surely have an LL(k) ambiguity. Check for predicates\r
1312 */\r
1313 if ( ParseWithPredicates )\r
1314 {\r
1315 if (alt1->predicate != NULL) predicate_free(alt1->predicate); /* MR12 */\r
1316 if (alt2->predicate != NULL) predicate_free(alt2->predicate); /* MR12 */\r
1317 require(MR_PredRuleRefStack.count == 0,"PredRuleRef stack not empty");\r
1318 alt1->predicate = MR_find_predicates_and_supp((Node *)alt1->p1);\r
1319 require(MR_PredRuleRefStack.count == 0,"PredRuleRef stack not empty");\r
1320 require (MR_predicate_context_completed(alt1->predicate),"predicate alt 1 not completed");\r
1321 alt1->predicate=MR_predSimplifyALL(alt1->predicate);\r
1322\r
1323 require(MR_PredRuleRefStack.count == 0,"PredRuleRef stack not empty");\r
1324 alt2->predicate = MR_find_predicates_and_supp((Node *)alt2->p1);\r
1325 require(MR_PredRuleRefStack.count == 0,"PredRuleRef stack not empty");\r
1326 require (MR_predicate_context_completed(alt2->predicate),"predicate alt 2 not completed");\r
1327 alt2->predicate=MR_predSimplifyALL(alt2->predicate);\r
1328\r
1329 MR_doPredicatesHelp(0,alt1,alt2,jtype,sub);\r
1330\r
1331 if ( HoistPredicateContext && (alt1->predicate!=NULL||alt2->predicate!=NULL) )\r
1332 {\r
1333 verify_context(alt1->predicate);\r
1334 verify_context(alt2->predicate);\r
1335 }\r
1336 if ( HoistPredicateContext && (alt1->predicate!=NULL||alt2->predicate!=NULL) && WarningLevel>1 )\r
1337 ensure_predicates_cover_ambiguous_lookahead_sequences(alt1, alt2, sub, ambig);\r
1338 if ( WarningLevel==1 &&\r
1339 (alt1->predicate!=NULL||alt2->predicate!=NULL))\r
1340 {\r
1341\r
1342 /* We found at least one pred for at least one of the alts;\r
1343 * If warnings are low, just return.\r
1344 */\r
1345\r
1346 Tfree(ambig);\r
1347 for (i=1; i<=CLL_k; i++) set_free( fset[i] );\r
1348 free((char *)fset);\r
1349 for (i=1; i<=CLL_k; i++) free( (char *)ftbl[i] );\r
1350 free((char *)ftbl);\r
1351 return;\r
1352 }\r
1353 /* else we're gonna give a warning */\r
1354 }\r
1355/* end TJP addition */\r
1356\r
1357 fprintf(stderr, ErrHdr, FileStr[alt1->file], alt1->line);\r
1358 if ( jtype == aLoopBegin || jtype == aPlusBlk )\r
1359 fprintf(stderr, " warning: optional/exit path and alt(s) %sambiguous upon", sub);\r
1360 else\r
1361 fprintf(stderr, " warning: alts %d and %d %sambiguous upon",\r
1362 alt1->altnum, alt2->altnum, sub);\r
1363 if ( elevel == 3 )\r
1364 {\r
1365 preorder(ambig->down); /* <===== k>1 ambiguity message data */\r
1366 fprintf(stderr, "\n");\r
1367 } else {\r
1368 MR_skipped_e3_report=1;\r
1369 dumpAmbigMsg(fset, stderr, 0);\r
1370 };\r
1371\r
1372 MR_traceAmbSourceK(ambig,alt1,alt2); /* <====== k>1 ambiguity aid */\r
1373\r
1374 Tfree(ambig);\r
1375\r
1376 for (i=1; i<=CLL_k; i++) set_free( fset[i] );\r
1377 free((char *)fset);\r
1378 for (i=1; i<=CLL_k; i++) free( (char *)ftbl[i] );\r
1379 free((char *)ftbl);\r
1380}\r
1381\r
1382/* Don't analyze alpha block of (alpha)?beta; if (alpha)? then analyze\r
1383 * Return the 1st node of the beta block if present else return j.\r
1384 */\r
1385Junction *\r
1386#ifdef __USE_PROTOS\r
1387analysis_point( Junction *j )\r
1388#else\r
1389analysis_point( j )\r
1390Junction *j;\r
1391#endif\r
1392{\r
1393 Junction *gblock;\r
1394\r
1395 /* MR13b When there was an action/predicate preceding a guess block\r
1396 the guess block became invisible at the analysis_point.\r
1397\r
1398 first_item_is_guess_block accepts any kind of node,\r
1399 despite the fact that the formal is a junction. But\r
1400 I don't want to have to change it all over the place\r
1401 until I know it works.\r
1402 */\r
1403\r
1404 if ( j->ntype != nJunction && j->ntype != nAction) return j;\r
1405\r
1406 gblock = first_item_is_guess_block((Junction *)j);\r
1407\r
1408 if ( gblock!=NULL )\r
1409 {\r
1410 Junction *past = gblock->end;\r
1411 Junction *p;\r
1412 require(past!=NULL, "analysis_point: no end block on (...)? block");\r
1413\r
1414 for (p=(Junction *)past->p1; p!=NULL; )\r
1415 {\r
1416 if ( p->ntype==nAction )\r
1417 {\r
1418 p=(Junction *)((ActionNode *)p)->next;\r
1419 continue;\r
1420 }\r
1421 if ( p->ntype!=nJunction )\r
1422 {\r
1423 past->alpha_beta_guess_end=1; /* MR14 */\r
1424 return (Junction *)past->p1;\r
1425 }\r
1426 if ( p->jtype==EndBlk || p->jtype==EndRule )\r
1427 {\r
1428 return j;\r
1429 }\r
1430/* MR6 */\r
1431/* MR6 A guess block is of the form "(alpha)? beta" or "(alpha)?". */\r
1432/* MR6 When beta is omitted (second form) this means "(alpha)? alpha". */\r
1433/* MR6 The program does not store another copy of alpha in this case. */\r
1434/* MR6 During analysis when the program needs to know what follows the */\r
1435/* MR6 guess clause. It calls this routine. */\r
1436/* MR6 */\r
1437/* MR6 If it is of the form "(alpha)? beta" it returns a pointer to beta.*/\r
1438/* MR6 */\r
1439/* MR6 If it is of the form "(alpha)?" it returns a pointer to the guess */\r
1440/* MR6 block itself thereby reusing the junction tree. */\r
1441/* MR6 */\r
1442/* MR6 It works by searching the "next in sequence" chain (skipping actions) */\r
1443/* MR6 searching for a RuleRef or Token node. (Those are the only 4 kinds */\r
1444/* MR6 of nodes: Junctions, RuleRef, Token, and Action.) */\r
1445/* MR6 */\r
1446/* MR6 This won't work for the special case "(alpha)? ()" because it has no */\r
1447/* MR6 rule references or token nodes. It eventually encounters a */\r
1448/* MR6 junction of type EndBlk or EndRule and says to its caller: nothing */\r
1449/* MR6 more here to analyze - must be of the form "(alpha)?". */\r
1450/* MR6 */\r
1451/* MR6 In the case of "(alpha)? ()" it should return a pointer to "()" */\r
1452/* MR6 */\r
1453/* MR6 I think. */\r
1454/* MR6 */\r
1455 if ( p->jtype!=Generic) { /* MR6 */\r
1456 past->alpha_beta_guess_end=1; /* MR14 */\r
1457 return (Junction *)past->p1; /* MR6 */\r
1458 }; /* MR6 */\r
1459 p=(Junction *)p->p1;\r
1460 }\r
1461 }\r
1462 return j;\r
1463}\r
1464\r
1465set\r
1466#ifdef __USE_PROTOS\r
1467First( Junction *j, int k, int jtype, int *max_k )\r
1468#else\r
1469First( j, k, jtype, max_k )\r
1470Junction *j;\r
1471int k;\r
1472int jtype;\r
1473int *max_k;\r
1474#endif\r
1475{\r
1476 Junction *alt1, *alt2;\r
1477 set a, rk, fCurBlk;\r
1478 int savek;\r
1479 int p1, p2;\r
1480\r
1481 int save_maintainBackTrace;\r
1482\r
1483 require(j->ntype==nJunction, "First: non junction passed");\r
1484\r
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 */\r
1486 fCurBlk = rk = empty;\r
1487 for (alt1=j; alt1!=NULL; alt1 = (Junction *)alt1->p2 )\r
1488 {\r
1489 Junction * p = NULL;\r
1490 Junction * p1junction = NULL;\r
1491 p = analysis_point((Junction *)alt1->p1);\r
1492 p1junction = (Junction *) (alt1->p1);\r
1493#if 0\r
1494 if (p != p1junction) {\r
1495 fprintf(stdout,"Analysis point for #%d is #%d", p1junction->seq, p->seq); /* debug */\r
1496 }\r
1497#endif\r
1498 REACH(p, k, &rk, alt1->fset[k]);\r
1499 require(set_nil(rk), "rk != nil");\r
1500 set_free(rk);\r
1501 set_orin(&fCurBlk, alt1->fset[k]);\r
1502 }\r
1503\r
1504 /* D e t e c t A m b i g u i t i e s */\r
1505 *max_k = 1;\r
1506 for (p1=1,alt1=j; alt1!=NULL; alt1 = (Junction *)alt1->p2, p1++)\r
1507 {\r
1508 for (p2=1,alt2=(Junction *)alt1->p2; alt2!=NULL; alt2 = (Junction *)alt2->p2, p2++)\r
1509 {\r
1510 savek = k;\r
1511 a = set_and(alt1->fset[k], alt2->fset[k]);\r
1512 while ( !set_nil(a) )\r
1513 {\r
1514 /* if we have hit the max k requested, just give warning */\r
1515 if ( j->approx==k ) {\r
1516 }\r
1517\r
1518 if ( k==CLL_k )\r
1519 {\r
1520#ifdef NOT_USED\r
1521*** int save_LL_k = LL_k;\r
1522*** int save_CLL_k = CLL_k;\r
1523*** /* Get new LL_k from interactive feature if enabled */\r
1524*** if ( AImode )\r
1525*** AmbiguityDialog(j, jtype, alt1, alt2, &CLL_k, &LL_k);\r
1526#endif\r
1527 *max_k = CLL_k;\r
1528 save_maintainBackTrace=MR_MaintainBackTrace;\r
1529 if (AlphaBetaTrace) MR_MaintainBackTrace=0;\r
1530 HandleAmbiguity(j, alt1, alt2, jtype);\r
1531 MR_MaintainBackTrace=save_maintainBackTrace;\r
1532 break;\r
1533 }\r
1534 else\r
1535 {\r
1536 Junction *p = analysis_point((Junction *)alt1->p1);\r
1537 Junction *q = analysis_point((Junction *)alt2->p1);\r
1538 k++; /* attempt ambig alts again with more lookahead */\r
1539\r
1540 REACH(p, k, &rk, alt1->fset[k]);\r
1541 require(set_nil(rk), "rk != nil");\r
1542 REACH(q, k, &rk, alt2->fset[k]);\r
1543 require(set_nil(rk), "rk != nil");\r
1544 set_free(a);\r
1545 a = set_and(alt1->fset[k], alt2->fset[k]);\r
1546 if ( k > *max_k ) *max_k = k;\r
1547 }\r
1548 }\r
1549 set_free(a);\r
1550 k = savek;\r
1551 }\r
1552 }\r
1553\r
1554 return fCurBlk;\r
1555}\r
EFI Development Kit II mirror for PVE