]>
Commit | Line | Data |
---|---|---|
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 | |
46 | static void ensure_predicates_cover_ambiguous_lookahead_sequences\r | |
47 | (Junction *, Junction *, char *, Tree *);\r | |
48 | #else\r | |
49 | static 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 | |
110 | set\r | |
111 | #ifdef __USE_PROTOS\r | |
112 | rJunc( Junction *p, int k, set *rk )\r | |
113 | #else\r | |
114 | rJunc( p, k, rk )\r | |
115 | Junction *p;\r | |
116 | int k;\r | |
117 | set *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 | |
291 | set\r | |
292 | #ifdef __USE_PROTOS\r | |
293 | rRuleRef( RuleRefNode *p, int k, set *rk_out )\r | |
294 | #else\r | |
295 | rRuleRef( p, k, rk_out )\r | |
296 | RuleRefNode *p;\r | |
297 | int k;\r | |
298 | set *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 | |
369 | set\r | |
370 | #ifdef __USE_PROTOS\r | |
371 | rToken( TokNode *p, int k, set *rk )\r | |
372 | #else\r | |
373 | rToken( p, k, rk )\r | |
374 | TokNode *p;\r | |
375 | int k;\r | |
376 | set *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 | |
430 | set\r | |
431 | #ifdef __USE_PROTOS\r | |
432 | rAction( ActionNode *p, int k, set *rk )\r | |
433 | #else\r | |
434 | rAction( p, k, rk )\r | |
435 | ActionNode *p;\r | |
436 | int k;\r | |
437 | set *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 | |
465 | void\r | |
466 | #ifdef __USE_PROTOS\r | |
467 | dumpAmbigMsg( set *fset, FILE *f, int want_nls )\r | |
468 | #else\r | |
469 | dumpAmbigMsg( fset, f, want_nls )\r | |
470 | set *fset;\r | |
471 | FILE *f;\r | |
472 | int 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 | |
510 | static void\r | |
511 | #ifdef __USE_PROTOS\r | |
512 | verify_context(Predicate *predicate)\r | |
513 | #else\r | |
514 | verify_context(predicate)\r | |
515 | Predicate *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 | |
577 | static void\r | |
578 | #ifdef __USE_PROTOS\r | |
579 | ensure_predicates_cover_ambiguous_lookahead_sequences\r | |
580 | ( Junction *alt1, Junction *alt2, char *sub, Tree *ambig )\r | |
581 | #else\r | |
582 | ensure_predicates_cover_ambiguous_lookahead_sequences( alt1, alt2, sub, ambig )\r | |
583 | Junction *alt1;\r | |
584 | Junction *alt2;\r | |
585 | char *sub;\r | |
586 | Tree *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 | |
674 | void MR_doPredicatesHelp(int inGuessBlock,Junction *alt1,Junction *alt2,int jtype,char *sub)\r | |
675 | #else\r | |
676 | void 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 | |
919 | static int totalOverflow=0; /* MR9 */\r | |
920 | \r | |
921 | void\r | |
922 | #ifdef __USE_PROTOS\r | |
923 | HandleAmbiguity( Junction *block, Junction *alt1, Junction *alt2, int jtype )\r | |
924 | #else\r | |
925 | HandleAmbiguity( block, alt1, alt2, jtype )\r | |
926 | Junction *block;\r | |
927 | Junction *alt1;\r | |
928 | Junction *alt2;\r | |
929 | int 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 | |
1385 | Junction *\r | |
1386 | #ifdef __USE_PROTOS\r | |
1387 | analysis_point( Junction *j )\r | |
1388 | #else\r | |
1389 | analysis_point( j )\r | |
1390 | Junction *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 | |
1465 | set\r | |
1466 | #ifdef __USE_PROTOS\r | |
1467 | First( Junction *j, int k, int jtype, int *max_k )\r | |
1468 | #else\r | |
1469 | First( j, k, jtype, max_k )\r | |
1470 | Junction *j;\r | |
1471 | int k;\r | |
1472 | int jtype;\r | |
1473 | int *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 |