fset.c 54 KB

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