开通博客赚积分
发布资源赚积分
分类

源码开发语言/平台
当前位置：首页 > 源码/资料 > 编译器/解释器 > 查看源码
fset2.c
资源名称：pccts133.zip　[点击查看]
上传用户：itx_2006
上传日期：2007-01-06
资源大小：493k
文件大小：55k
源码类别：

编译器/解释器

开发平台：

Others

fset2.c：源码内容
  1. /*
  2.  * fset2.c
  3.  *
  4.  * Compute FIRST sets for full LL(k)
  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-1998
  31.  */
  33. #include <stdio.h>
  34. #ifdef __cplusplus
  35. #ifndef __STDC__
  36. #define __STDC__
  37. #endif
  38. #endif
  39. #ifdef __STDC__
  40. #include <stdarg.h>
  41. #else
  42. #include <varargs.h>
  43. #endif
  44. #include "set.h"
  45. #include "syn.h"
  46. #include "hash.h"
  47. #include "generic.h"
  48. #include "dlgdef.h"
  50. extern char tokens[];
  52. extern char *PRED_AND_LIST;
  53. extern char *PRED_OR_LIST;
  55. /* ick! globals.  Used by permute() to track which elements of a set have been used */
  57. static int *findex;
  58. set *fset;              /* MR11 make global */
  59. static unsigned **ftbl;
  60. static set *constrain; /* pts into fset. constrains tToken() to 'constrain' */
  61. int ConstrainSearch;
  62. int maxk;               /* set to initial k upon tree construction request */
  63.                         /* MR11 make global */
  64. static Tree *FreeList = NULL;
  66. #ifdef __STDC__
  67. static int tmember_of_context(Tree *, Predicate *);
  68. #else
  69. static int tmember_of_context();
  70. #endif
  72. #if TREE_DEBUG
  73. set     set_of_tnodes_in_use;
  74. int     stop_on_tnode_seq_number=(-1);     /* (-1) to disable */
  75. #endif
  77. /* Do root
  78.  * Then each sibling
  79.  */
  81. void
  82. #ifdef __STDC__
  83. preorder( Tree *tree )
  84. #else
  85. preorder( tree )
  86. Tree *tree;
  87. #endif
  88. {
  89. if ( tree == NULL ) return;
  90. if ( tree->down != NULL ) fprintf(stderr, " (");
  91. if ( tree->token == ALT ) fprintf(stderr, " ALT");
  92. else fprintf(stderr, " %s", TerminalString(tree->token));
  93. if ( tree->token==EpToken ) fprintf(stderr, "(%d)", tree->v.rk);
  94. preorder(tree->down);
  95. if ( tree->down != NULL ) fprintf(stderr, " )");
  96. preorder(tree->right);
  97. }
  99. #ifdef __STDC__
  100. int MR_tree_matches_constraints(int k,set * constrain,Tree *t)
  101. #else
  102. int MR_tree_matches_constraints(k,constrain,t)
  103.   int       k;
  104.   set *     constrain;
  105.   Tree *    t;
  106. #endif
  107. {
  108.   int       i;
  109.   Tree      *u;
  111.   if (k == 0) return 1;
  113.   /* for testing guard predicates: if the guard tree is shorter
  114.      than the constraint then it is a match.  The reason is that
  115.      a guard of (A B) should be equivalent to a guard of (A B . . .)
  116.      where "." matches every token.  Thus a match which runs out
  117.      of tree before constraint is a match.
  118.   */
  120.   if (t == NULL) return 1;
  121.   require (set_deg(constrain[0]) == 1,
  122.             "MR_tree_matches_constraints: set_deg != 1");
  123.   i=set_int(constrain[0]);
  124.   if (t->token != i) return 0;
  125.   if (k-1 == 0) return 1;
  126.   for (u=t->down; u != NULL; u=u->right) {
  127.     if (MR_tree_matches_constraints(k-1,&constrain[1],u)) {
  128.        return 1;
  129.     };
  130.   };
  131.   return 0;
  132. }
  134. /* check the depth of each primary sibling to see that it is exactly
  135.  * k deep. e.g.;
  136.  *
  137.  * ALT
  138.  *   |
  139.  *   A ------- B
  140.  *   |         |
  141.  *   C -- D    E
  142.  *
  143.  * Remove all branches <= k deep.
  144.  *
  145.  * Added by TJP 9-23-92 to make the LL(k) constraint mechanism to work.
  146.  */
  148. static int pruneCount=0;
  149. static int prunePeak=200;
  151. Tree *
  152. #ifdef __STDC__
  153. prune( Tree *t, int k )
  154. #else
  155. prune( t, k )
  156. Tree *t;
  157. int k;
  158. #endif
  159. {
  160.     pruneCount++;
  161.     if (pruneCount > prunePeak+100) {
  162.       prunePeak=pruneCount;
  163. #if 0
  164. ***   fprintf(stderr,"pruneCount=%dn",pruneCount);
  165. /***  preorder(t);   ***/
  166. ***   fprintf(stderr,"n",pruneCount);
  167. #endif
  168.     };
  169.     if ( t == NULL ) {
  170.         pruneCount--;
  171.         return NULL;
  172.     };
  173.     if ( t->token == ALT ) fatal_internal("prune: ALT node in FIRST tree");
  174.     if ( t->right!=NULL ) t->right = prune(t->right, k);
  175.     if ( k>1 )
  176. {
  177. if ( t->down!=NULL ) t->down = prune(t->down, k-1);
  178. if ( t->down == NULL )
  179. {
  180. Tree *r = t->right;
  181. t->right = NULL;
  182. Tfree(t);
  183.             pruneCount--;
  184. return r;
  185. }
  186. }
  187.     pruneCount--;
  188.     return t;
  189. }
  191. /* build a tree (root child1 child2 ... NULL) */
  192. #ifdef __STDC__
  193. Tree *tmake(Tree *root, ...)
  194. #else
  195. Tree *tmake(va_alist)
  196. va_dcl
  197. #endif
  198. {
  199. Tree *w;
  200. va_list ap;
  201. Tree *child, *sibling=NULL, *tail=NULL;
  202. #ifndef __STDC__
  203. Tree *root;
  204. #endif
  206. #ifdef __STDC__
  207. va_start(ap, root);
  208. #else
  209. va_start(ap);
  210. root = va_arg(ap, Tree *);
  211. #endif
  212. child = va_arg(ap, Tree *);
  213. while ( child != NULL )
  214. {
  215. #ifdef DUM
  216. /* added "find end of child" thing TJP March 1994 */
  217. for (w=child; w->right!=NULL; w=w->right) {;} /* find end of child */
  218. #else
  219. w = child;
  220. #endif
  222. if ( sibling == NULL ) {sibling = child; tail = w;}
  223. else {tail->right = child; tail = w;}
  224. child = va_arg(ap, Tree *);
  225. }
  227. /* was "root->down = sibling;" */
  228. if ( root==NULL ) root = sibling;
  229. else root->down = sibling;
  231. va_end(ap);
  232. return root;
  233. }
  235. Tree *
  236. #ifdef __STDC__
  237. tnode( int tok )
  238. #else
  239. tnode( tok )
  240. int tok;
  241. #endif
  242. {
  243. Tree *p, *newblk;
  244. static int n=0;
  246. if ( FreeList == NULL )
  247. {
  248. /*fprintf(stderr, "tnode: %d more nodesn", TreeBlockAllocSize);*/
  249. if ( TreeResourceLimit > 0 )
  250. {
  251. if ( (n+TreeBlockAllocSize) >= TreeResourceLimit )
  252. {
  253. fprintf(stderr, ErrHdr, FileStr[CurAmbigfile], CurAmbigline);
  254. fprintf(stderr, " hit analysis resource limit while analyzing alts %d and %d %sn",
  255. CurAmbigAlt1,
  256. CurAmbigAlt2,
  257. CurAmbigbtype);
  258. exit(PCCTS_EXIT_FAILURE);
  259. }
  260. }
  261. newblk = (Tree *)calloc(TreeBlockAllocSize, sizeof(Tree));
  262. if ( newblk == NULL )
  263. {
  264. fprintf(stderr, ErrHdr, FileStr[CurAmbigfile], CurAmbigline);
  265. fprintf(stderr, " out of memory while analyzing alts %d and %d %sn",
  266. CurAmbigAlt1,
  267. CurAmbigAlt2,
  268. CurAmbigbtype);
  269. exit(PCCTS_EXIT_FAILURE);
  270. }
  271. n += TreeBlockAllocSize;
  272. for (p=newblk; p<&(newblk[TreeBlockAllocSize]); p++)
  273. {
  274. p->right = FreeList; /* add all new Tree nodes to Free List */
  275. FreeList = p;
  276. }
  277. }
  278. p = FreeList;
  279. FreeList = FreeList->right; /* remove a tree node */
  280. p->right = NULL; /* zero out ptrs */
  281. p->down = NULL;
  282. p->token = tok;
  284.     TnodesAllocated++;                                      /* MR10 */
  285.     TnodesInUse++;                                          /* MR10 */
  286.     if (TnodesInUse > TnodesPeak) TnodesPeak=TnodesInUse;   /* MR10 */
  288. #ifdef TREE_DEBUG
  289. require(!p->in_use, "tnode: node in use!");
  290. p->in_use = 1;
  291.     p->seq=TnodesAllocated;
  292.     set_orel( (unsigned) TnodesAllocated,&set_of_tnodes_in_use);
  293.     if (stop_on_tnode_seq_number == p->seq) {
  294.       fprintf(stderr,"n*** just allocated tnode #%d ***n",
  295.             stop_on_tnode_seq_number);
  296.     };
  297. #endif
  298. return p;
  299. }
  301. static Tree *
  302. #ifdef __STDC__
  303. eofnode( int k )
  304. #else
  305. eofnode( k )
  306. int k;
  307. #endif
  308. {
  309. Tree *t=NULL;
  310. int i;
  312. for (i=1; i<=k; i++)
  313. {
  314. t = tmake(tnode((TokenInd!=NULL?TokenInd[EofToken]:EofToken)), t, NULL);
  315. }
  316. return t;
  317. }
  321. void
  322. #ifdef __STDC__
  323. _Tfree( Tree *t )
  324. #else
  325. _Tfree( t )
  326. Tree *t;
  327. #endif
  328. {
  329. if ( t!=NULL )
  330. {
  331. #ifdef TREE_DEBUG
  332.         if (t->seq == stop_on_tnode_seq_number) {
  333.            fprintf(stderr,"n*** just freed tnode #%d ***n",t->seq);
  334.         };
  335. require(t->in_use, "_Tfree: node not in use!");
  336. t->in_use = 0;
  337.         set_rm( (unsigned) t->seq,set_of_tnodes_in_use);
  338. #endif
  339. t->right = FreeList;
  340. FreeList = t;
  341.         TnodesInUse--;                   /* MR10 */
  342. }
  343. }
  345. /* tree duplicate */
  346. Tree *
  347. #ifdef __STDC__
  348. tdup( Tree *t )
  349. #else
  350. tdup( t )
  351. Tree *t;
  352. #endif
  353. {
  354. Tree *u;
  356. if ( t == NULL ) return NULL;
  357. u = tnode(t->token);
  358. u->v.rk = t->v.rk;
  359. u->right = tdup(t->right);
  360. u->down = tdup(t->down);
  361. return u;
  362. }
  364. /* tree duplicate (assume tree is a chain downwards) */
  365. Tree *
  366. #ifdef __STDC__
  367. tdup_chain( Tree *t )
  368. #else
  369. tdup_chain( t )
  370. Tree *t;
  371. #endif
  372. {
  373. Tree *u;
  375. if ( t == NULL ) return NULL;
  376. u = tnode(t->token);
  377. u->v.rk = t->v.rk;
  378. u->down = tdup(t->down);
  379. return u;
  380. }
  382. Tree *
  383. #ifdef __STDC__
  384. tappend( Tree *t, Tree *u )
  385. #else
  386. tappend( t, u )
  387. Tree *t;
  388. Tree *u;
  389. #endif
  390. {
  391. Tree *w;
  393. /*** fprintf(stderr, "tappend(");
  394.  *** preorder(t); fprintf(stderr, ",");
  395.  *** preorder(u); fprintf(stderr, " )n");
  396. */
  397. if ( t == NULL ) return u;
  398. if ( t->token == ALT && t->right == NULL ) return tappend(t->down, u);
  399. for (w=t; w->right!=NULL; w=w->right) {;}
  400. w->right = u;
  401. return t;
  402. }
  404. /* dealloc all nodes in a tree */
  405. void
  406. #ifdef __STDC__
  407. Tfree( Tree *t )
  408. #else
  409. Tfree( t )
  410. Tree *t;
  411. #endif
  412. {
  413. if ( t == NULL ) return;
  414. Tfree( t->down );
  415. Tfree( t->right );
  416. _Tfree( t );
  417. }
  419. /* find all children (alts) of t that require remaining_k nodes to be LL_k
  420.  * tokens long.
  421.  *
  422.  * t-->o
  423.  *     |
  424.  *     a1--a2--...--an <-- LL(1) tokens
  425.  *     |   |        |
  426.  *     b1  b2  ...  bn <-- LL(2) tokens
  427.  *     |   |        |
  428.  *     .   .        .
  429.  *     .   .        .
  430.  *     z1  z2  ...  zn <-- LL(LL_k) tokens
  431.  *
  432.  * We look for all [Ep] needing remaining_k nodes and replace with u.
  433.  * u is not destroyed or actually used by the tree (a copy is made).
  434.  */
  435. Tree *
  436. #ifdef __STDC__
  437. tlink( Tree *t, Tree *u, int remaining_k )
  438. #else
  439. tlink( t, u, remaining_k )
  440. Tree *t;
  441. Tree *u;
  442. int remaining_k;
  443. #endif
  444. {
  445. Tree *p;
  446. require(remaining_k!=0, "tlink: bad tree");
  448. if ( t==NULL ) return NULL;
  449. /*fprintf(stderr, "tlink: u is:"); preorder(u); fprintf(stderr, "n");*/
  450. if ( t->token == EpToken && t->v.rk == remaining_k )
  451. {
  452. require(t->down==NULL, "tlink: invalid tree");
  453. if ( u == NULL ) {
  454. /* MR10 */  Tree  *tt=t->right;
  455. /* MR10 */  _Tfree(t);
  456. /* MR10 */  return tt;
  457.         };
  458. p = tdup( u );
  459. p->right = t->right;
  460. _Tfree( t );
  461. return p;
  462. }
  463. t->down = tlink(t->down, u, remaining_k);
  464. t->right = tlink(t->right, u, remaining_k);
  465. return t;
  466. }
  468. /* remove as many ALT nodes as possible while still maintaining semantics */
  469. Tree *
  470. #ifdef __STDC__
  471. tshrink( Tree *t )
  472. #else
  473. tshrink( t )
  474. Tree *t;
  475. #endif
  476. {
  477. if ( t == NULL ) return NULL;
  478. t->down = tshrink( t->down );
  479. t->right = tshrink( t->right );
  480. if ( t->down == NULL )
  481. {
  482. if ( t->token == ALT )
  483. {
  484. Tree *u = t->right;
  485. _Tfree(t);
  486. return u; /* remove useless alts */
  487. }
  488. return t;
  489. }
  491. /* (? (ALT (? ...)) s) ==> (? (? ...) s) where s = sibling, ? = match any */
  492. if ( t->token == ALT && t->down->right == NULL)
  493. {
  494. Tree *u = t->down;
  495. u->right = t->right;
  496. _Tfree( t );
  497. return u;
  498. }
  499. /* (? (A (ALT t)) s) ==> (? (A t) s) where A is a token; s,t siblings */
  500. if ( t->token != ALT && t->down->token == ALT && t->down->right == NULL )
  501. {
  502. Tree *u = t->down->down;
  503. _Tfree( t->down );
  504. t->down = u;
  505. return t;
  506. }
  507. return t;
  508. }
  510. Tree *
  511. #ifdef __STDC__
  512. tflatten( Tree *t )
  513. #else
  514. tflatten( t )
  515. Tree *t;
  516. #endif
  517. {
  518. if ( t == NULL ) return NULL;
  519. t->down = tflatten( t->down );
  520. t->right = tflatten( t->right );
  521. if ( t->down == NULL ) return t;
  523. if ( t->token == ALT )
  524. {
  525. Tree *u;
  526. /* find tail of children */
  527. for (u=t->down; u->right!=NULL; u=u->right) {;}
  528. u->right = t->right;
  529. u = t->down;
  530. _Tfree( t );
  531. return u;
  532. }
  533. return t;
  534. }
  536. Tree *
  537. #ifdef __STDC__
  538. tJunc( Junction *p, int k, set *rk )
  539. #else
  540. tJunc( p, k, rk )
  541. Junction *p;
  542. int k;
  543. set *rk;
  544. #endif
  545. {
  546. Tree *t=NULL, *u=NULL;
  547. Junction *alt;
  548. Tree *tail=NULL, *r;
  550. #ifdef DBG_TRAV
  551. fprintf(stderr, "tJunc(%d): %s in rule %sn", k,
  552. decodeJType[p->jtype], ((Junction *)p)->rname);
  553. #endif
  555. /* MR14 */    if (AlphaBetaTrace && p->alpha_beta_guess_end) {
  556. /* MR14 */         warnFL(
  557. /* MR14 */           "not possible to compute follow set for alpha in an "(alpha)? beta" block.  ",
  558. /* MR14 */                 FileStr[p->file],p->line);
  559. /* MR14 */         MR_alphaBetaTraceReport();
  560. /* MR14 */    };
  562. /* MR14 */    if (p->alpha_beta_guess_end) {
  563. /* MR14 */      return NULL;
  564. /* MR14 */    }
  566. if ( p->jtype==aLoopBlk || p->jtype==RuleBlk ||
  567.  p->jtype==aPlusBlk || p->jtype==aSubBlk || p->jtype==aOptBlk )
  568. {
  569. if ( p->jtype!=aSubBlk && p->jtype!=aOptBlk ) {
  570. require(p->lock!=NULL, "rJunc: lock array is NULL");
  571. if ( p->lock[k] ) return NULL;
  572. p->lock[k] = TRUE;
  573. }
  575. /* MR10 */    if (MR_MaintainBackTrace) {
  576. /* MR10 */      if (p->jtype != Generic) MR_pointerStackPush(&MR_BackTraceStack,p);
  577. /* MR10 */    };
  579. TRAV(p->p1, k, rk, tail);
  581. /* MR10 */    if (MR_MaintainBackTrace) {
  582. /* MR10 */      if (p->jtype != Generic) MR_pointerStackPop(&MR_BackTraceStack);
  583. /* MR10 */    };
  585. if ( p->jtype==RuleBlk ) {p->lock[k] = FALSE; return tail;}
  586. r = tmake(tnode(ALT), tail, NULL);
  587. for (alt=(Junction *)p->p2; alt!=NULL; alt = (Junction *)alt->p2)
  588. {
  589. /* if this is one of the added optional alts for (...)+ then break */
  590. if ( alt->ignore ) break;
  592. if ( tail==NULL ) {TRAV(alt->p1, k, rk, tail); r->down = tail;}
  593. else
  594. {
  595. /* MR10 */    if (MR_MaintainBackTrace) {
  596. /* MR10 */      if (p->jtype != Generic) MR_pointerStackPush(&MR_BackTraceStack,p);
  597. /* MR10 */    };
  599. TRAV(alt->p1, k, rk, tail->right);
  601. /* MR10 */    if (MR_MaintainBackTrace) {
  602. /* MR10 */      if (p->jtype != Generic) MR_pointerStackPop(&MR_BackTraceStack);
  603. /* MR10 */    };
  604. if ( tail->right != NULL ) tail = tail->right;
  605. }
  606. }
  607. if ( p->jtype!=aSubBlk && p->jtype!=aOptBlk ) p->lock[k] = FALSE;
  608. #ifdef DBG_TREES
  609. fprintf(stderr, "blk(%s) returns:",((Junction *)p)->rname); preorder(r); fprintf(stderr, "n");
  610. #endif
  611. if ( r->down == NULL ) {_Tfree(r); return NULL;}
  612. return r;
  613. }
  615. if ( p->jtype==EndRule )
  616. {
  617. if ( p->halt ) /* don't want FOLLOW here? */
  618. {
  619. /**** if ( ContextGuardTRAV ) return NULL; ****/
  620. set_orel( (unsigned) k, rk); /* indicate this k value needed */ /* MR10 cast */
  621. t = tnode(EpToken);
  622. t->v.rk = k;
  623. return t;
  624. }
  625. require(p->lock!=NULL, "rJunc: lock array is NULL");
  626. if ( p->lock[k] ) return NULL;
  627. /* if no FOLLOW assume k EOF's */
  628. if ( p->p1 == NULL ) return eofnode(k);
  629. p->lock[k] = TRUE;
  630. }
  632. /* MR14 */ if (p->p1 != NULL && p->guess &&  p->guess_analysis_point == NULL) {
  633. /* MR14 */    Node * guess_point;
  634. /* MR14 */    guess_point=(Node *)analysis_point(p);
  635. /* MR14 */    if (guess_point == (Node *)p) {
  636. /* MR14 */      guess_point=p->p1;
  637. /* MR14 */    }
  638. /* MR14 */    p->guess_analysis_point=guess_point;
  639. /* MR14 */  }
  641. if ( p->p2 == NULL )
  642. {
  644. /* MR10 */    if (MR_MaintainBackTrace) {
  645. /* MR10 */      if (p->jtype != Generic) MR_pointerStackPush(&MR_BackTraceStack,p);
  646. /* MR10 */    };
  648. /* M14 */        if (p->guess_analysis_point != NULL) {
  649. /* M14 */     TRAV(p->guess_analysis_point, k, rk,t);
  650. /* M14 */        } else {
  651.             TRAV(p->p1, k, rk,t);
  652. /* M14 */        }
  654. /* MR10 */    if (MR_MaintainBackTrace) {
  655. /* MR10 */      if (p->jtype != Generic) MR_pointerStackPop(&MR_BackTraceStack);
  656. /* MR10 */    };
  658. if ( p->jtype==EndRule ) p->lock[k]=FALSE;
  659. return t;
  660. }
  662. /* MR10 */    if (MR_MaintainBackTrace) {
  663. /* MR10 */      if (p->jtype != Generic) MR_pointerStackPush(&MR_BackTraceStack,p);
  664. /* MR10 */    };
  666. /* M14 */        if (p->guess_analysis_point != NULL) {
  667. /* M14 */     TRAV(p->guess_analysis_point, k, rk,t);
  668. /* M14 */        } else {
  669.             TRAV(p->p1, k, rk,t);
  670. /* M14 */        }
  672. /* MR10 */    if (MR_MaintainBackTrace) {
  673. /* MR10 */      if (p->jtype != Generic) MR_pointerStackPop(&MR_BackTraceStack);
  674. /* MR10 */    };
  676. if ( p->jtype!=RuleBlk && /* MR14 */ !p->guess) TRAV(p->p2, k, rk, u);
  678. if ( p->jtype==EndRule ) p->lock[k] = FALSE;/* unlock node */
  680. if ( t==NULL ) return tmake(tnode(ALT), u, NULL);
  681. return tmake(tnode(ALT), t, u, NULL);
  682. }
  684. Tree *
  685. #ifdef __STDC__
  686. tRuleRef( RuleRefNode *p, int k, set *rk_out )
  687. #else
  688. tRuleRef( p, k, rk_out )
  689. RuleRefNode *p;
  690. int k;
  691. set *rk_out;
  692. #endif
  693. {
  694. int k2;
  695. Tree *t=NULL, *u=NULL;
  696. Junction *r;
  697. set rk, rk2;
  698. int save_halt;
  699. RuleEntry *q = (RuleEntry *) hash_get(Rname, p->text);
  701. #ifdef DBG_TRAV
  702. fprintf(stderr, "tRuleRef: %sn", p->text);
  703. #endif
  704. if ( q == NULL )
  705. {
  706. TRAV(p->next, k, rk_out, t);/* ignore undefined rules */
  707. return t;
  708. }
  709. rk = rk2 = empty;
  710.     if (RulePtr == NULL) fatal("RulePtr==NULL");
  711. r = RulePtr[q->rulenum];
  712. if ( r->lock[k] ) return NULL;
  713. save_halt = r->end->halt;
  714. r->end->halt = TRUE; /* don't let reach fall off end of rule here */
  716. /* MR10 */    if (MR_MaintainBackTrace) {
  717. /* MR10 */      MR_pointerStackPush(&MR_BackTraceStack,p);
  718. /* MR10 */    };
  720. TRAV(r, k, &rk, t);
  722. /* MR10 */    if (MR_MaintainBackTrace) {
  723. /* MR10 */      MR_pointerStackPop(&MR_BackTraceStack);
  724. /* MR10 */    };
  726. r->end->halt = save_halt;
  727. #ifdef DBG_TREES
  728. fprintf(stderr, "after ruleref, t is:"); preorder(t); fprintf(stderr, "n");
  729. #endif
  730. t = tshrink( t );
  731. while ( !set_nil(rk) ) { /* any k left to do? if so, link onto tree */
  732. k2 = set_int(rk);
  733. set_rm(k2, rk);
  735. /* MR10 */    if (MR_MaintainBackTrace) {
  736. /* MR10 */      MR_pointerStackPush(&MR_BackTraceStack,p);
  737. /* MR10 */    };
  739. TRAV(p->next, k2, &rk2, u);
  741. /* MR10 */    if (MR_MaintainBackTrace) {
  742. /* MR10 */      MR_pointerStackPop(&MR_BackTraceStack);
  743. /* MR10 */    };
  745. t = tlink(t, u, k2); /* any alts missing k2 toks, add u onto end */
  746.         Tfree(u);               /* MR10 */
  747. }
  748. set_free(rk); /* rk is empty, but free it's memory */
  749. set_orin(rk_out, rk2); /* remember what we couldn't do */
  750. set_free(rk2);
  751. return t;
  752. }
  754. Tree *
  755. #ifdef __STDC__
  756. tToken( TokNode *p, int k, set *rk )
  757. #else
  758. tToken( p, k, rk )
  759. TokNode *p;
  760. int k;
  761. set *rk;
  762. #endif
  763. {
  764. Tree *t=NULL, *tset=NULL, *u;
  766. if (ConstrainSearch) {
  767.       if (MR_AmbSourceSearch) {
  768. require(constrain>=fset&&constrain<=&(fset[CLL_k]),"tToken: constrain is not a valid set");
  769.       } else {
  770. require(constrain>=fset&&constrain<=&(fset[LL_k]),"tToken: constrain is not a valid set");
  771.       };
  772.       constrain = &fset[maxk-k+1];
  773. }
  775. #ifdef DBG_TRAV
  776.          fprintf(stderr, "tToken(%d): %sn", k, TerminalString(p->token));
  777.          if ( ConstrainSearch ) {
  778.          fprintf(stderr, "constrain is:"); s_fprT(stderr, *constrain); fprintf(stderr, "n");
  779.          }
  780. #endif
  782. /* is it a meta token (set of tokens)? */
  784. if ( !set_nil(p->tset) )
  785. {
  786. unsigned e=0;
  787. set a;
  788. Tree *n, *tail = NULL;
  790. if ( ConstrainSearch ) {
  791.           a = set_and(p->tset, *constrain);
  792.           if (set_nil(a)) {         /* MR10 */
  793.             set_free(a);            /* MR11 */
  794.             return NULL;            /* MR10 */
  795.           };                        /* MR10 */
  796. } else {
  797.           a = set_dup(p->tset);
  798.         };
  800. for (; !set_nil(a); set_rm(e, a))
  801. {
  802. e = set_int(a);
  803. n = tnode(e);
  804. if ( tset==NULL ) { tset = n; tail = n; }
  805. else { tail->right = n; tail = n; }
  806. }
  807. set_free( a );
  808. }
  809. else if ( ConstrainSearch && !set_el(p->token, *constrain) )
  810.     {
  811. /*      fprintf(stderr, "ignoring token %s(%d)n", TerminalString(p->token),
  812.                 k);*/
  813.         return NULL;
  814.     }
  815. else {
  816.         tset = tnode( p->token );
  817.     };
  819. /* MR10 */    if (MR_MaintainBackTrace) {
  820. /* MR10 */      if (k == 1) {
  821. /* MR10 */        MR_pointerStackPush(&MR_BackTraceStack,p);
  822. /* MR13 */        if (MR_SuppressSearch) {
  823. /* MR13 */          MR_suppressSearchReport();
  824. /* MR13 */        } else {
  825. /* MR10 */          MR_backTraceReport();
  826. /* MR13 */        };
  827. /* MR10 */        MR_pointerStackPop(&MR_BackTraceStack);
  828. /* MR11 */        Tfree(tset);
  829. /* MR11 */        return NULL;
  830. /* MR10 */      };
  831. /* MR10 */    };
  833. if ( k == 1 ) return tset;
  835.     if (MR_MaintainBackTrace) {
  836.       MR_pointerStackPush(&MR_BackTraceStack,p);
  837.     };
  839. TRAV(p->next, k-1, rk, t);
  841.     if (MR_MaintainBackTrace) {
  842.       Tfree(t);
  843.       Tfree(tset);
  844.       MR_pointerStackPop(&MR_BackTraceStack);
  845.       return NULL;
  846.     };
  848. /* here, we are positive that, at least, this tree will not contribute
  849.  * to the LL(2) tree since it will be too shallow, IF t==NULL.
  850.  * If doing a context guard walk, then don't prune.
  851.  */
  852. if ( t == NULL && !ContextGuardTRAV ) /* tree will be too shallow */
  853. {
  854. if ( tset!=NULL ) Tfree( tset );
  855. return NULL;
  856. }
  857. #ifdef DBG_TREES
  858. fprintf(stderr, "tToken(%d)->next:",k); preorder(t); fprintf(stderr, "n");
  859. #endif
  861. /* if single token root, then just make new tree and return */
  862.     /* MR10 - set_nil(p->tset) isn't a good test because of ConstraintSearch */
  864. if (tset->right == NULL) return tmake(tset, t, NULL);    /* MR10 */
  866. /* here we must make a copy of t as a child of each element of the tset;
  867.  * e.g., "T1..T3 A" would yield ( nil ( T1 A ) ( T2 A ) ( T3 A ) )
  868.  */
  869. for (u=tset; u!=NULL; u=u->right)
  870. {
  871. /* make a copy of t and hook it onto bottom of u */
  872. u->down = tdup(t);
  873. }
  874. Tfree( t );
  875. #ifdef DBG_TREES
  876. fprintf(stderr, "range is:"); preorder(tset); fprintf(stderr, "n");
  877. #endif
  878. return tset;
  879. }
  881. Tree *
  882. #ifdef __STDC__
  883. tAction( ActionNode *p, int k, set *rk )
  884. #else
  885. tAction( p, k, rk )
  886. ActionNode *p;
  887. int k;
  888. set *rk;
  889. #endif
  890. {
  891. Tree        *t=NULL;
  892.     set         *save_fset=NULL;
  893.     int         i;
  895. /* fprintf(stderr, "tActionn"); */
  897. /*  An MR_SuppressSearch is looking for things that can be
  898.       reached even when the predicate is false.
  900.     There are three kinds of predicates:
  901.         plain:              r1: <<p>>? r2
  902.         guarded:            r1: (A)? => <<p>>? r2
  903.         ampersand style:    r1: (A)? && <<p>>? r2
  905.     Of the three kinds of predicates, only a guard predicate
  906.       has things which are reachable even when the predicate
  907.       is false.  To be reachable the constraint must *not*
  908.       match the guard.
  910. */
  912.     if (p->is_predicate && MR_SuppressSearch) {
  914.       Predicate     *pred=p->guardpred;
  916.       if (pred == NULL) {
  917.         t=NULL;
  918.         goto EXIT;
  919.       };
  920.       constrain = &fset[maxk-k+1];
  921.       if (pred->k == 1) {
  922.         set     dif;
  923.         dif=set_dif(*constrain,pred->scontext[1]);
  924.         if (set_nil(dif)) {
  925.           set_free(dif);
  926.           t=NULL;
  927.           goto EXIT;
  928.         };
  929.         set_free(dif);
  930.       } else {
  931.         if (MR_tree_matches_constraints(k,constrain,pred->tcontext)) {
  932.           t=NULL;
  933.           goto EXIT;
  934.         };
  935.       }
  936.     };
  938.     /* The ampersand predicate differs from the
  939.          other predicates because its first set
  940.          is a subset of the first set behind the predicate
  942.             r1: (A)? && <<p>>? r2 ;
  943.             r2: A | B;
  945.        In this case first[1] of r1 is A, even
  946.          though first[1] of r2 is {A B}.
  947.     */
  949.     if (p->is_predicate && p->ampersandPred != NULL) {
  951.       Predicate     *pred=p->ampersandPred;
  952.       Tree          *tAND;
  953.       Tree          *tset;
  955.       if (k <= pred->k) {
  956.         if (MR_MaintainBackTrace) MR_pointerStackPush(&MR_BackTraceStack,p);
  957.         TRAV(p->guardNodes,k,rk,t);
  958.         if (MR_MaintainBackTrace) MR_pointerStackPop(&MR_BackTraceStack);
  959.         return t;
  960.       } else {
  961.         require (k>1,"tAction for ampersandpred: k <= 1");
  962.         if (ConstrainSearch) {
  963.           if (MR_AmbSourceSearch) {
  964.      require(constrain>=fset&&constrain<=&(fset[CLL_k]),
  965.                                 "tToken: constrain is not a valid set");
  966.           } else {
  967.      require(constrain>=fset&&constrain<=&(fset[LL_k]),
  968.                                 "tToken: constrain is not a valid set");
  969.           };
  970.           save_fset=(set *) calloc (CLL_k+1,sizeof(set));
  971.           require (save_fset != NULL,"tAction save_fset alloc");
  972.           for (i=1; i <= CLL_k ; i++) {
  973.             save_fset[i]=set_dup(fset[i]);
  974.           };
  975.           if (pred->k == 1) {
  976.             constrain = &fset[maxk-k+1];
  977.             set_andin(constrain,pred->scontext[1]);
  978.             if (set_nil(*constrain)) {
  979.               t=NULL;
  980.               goto EXIT;
  981.             };
  982.           } else {
  983.             constrain = &fset[maxk-k+1];
  984.             if (! MR_tree_matches_constraints(pred->k,constrain,pred->tcontext)) {
  985.                t=NULL;
  986.                goto EXIT;
  987.             };  /* end loop on i          */
  988.           }; /* end loop on pred scontext/tcontext */
  989.         }; /* end if on k > pred->k     */
  990.       }; /* end if on constrain search  */
  992.       TRAV(p->next,k,rk,t);
  994.       if (t != NULL) {
  995.         t=tshrink(t);
  996.         t=tflatten(t);
  997.         t=tleft_factor(t);
  998.         if (pred->tcontext != NULL) {
  999.           tAND=MR_computeTreeAND(t,pred->tcontext);
  1000.         } else {
  1001.           tset=MR_make_tree_from_set(pred->scontext[1]);
  1002.           tAND=MR_computeTreeAND(t,tset);
  1003.           Tfree(tset);
  1004.         };
  1005.         Tfree(t);
  1006.         t=tAND;
  1007.       };
  1008.       goto EXIT;
  1010.     }; /* end if on ampersand predicate */
  1012.     TRAV(p->next,k,rk,t);
  1014. EXIT:
  1015.     if (save_fset != NULL) {
  1016.       for (i=1 ; i <= CLL_k ; i++) {
  1017.         set_free(fset[i]);
  1018.         fset[i]=save_fset[i];
  1019.       };
  1020.       free ( (char *) save_fset);
  1021.     };
  1022. return t;
  1023. }
  1025. /* see if e exists in s as a possible input permutation (e is always a chain) */
  1027. int
  1028. #ifdef __STDC__
  1029. tmember( Tree *e, Tree *s )
  1030. #else
  1031. tmember( e, s )
  1032. Tree *e;
  1033. Tree *s;
  1034. #endif
  1035. {
  1036. if ( e==NULL||s==NULL ) return 0;
  1037. /** fprintf(stderr, "tmember(");
  1038. *** preorder(e); fprintf(stderr, ",");
  1039. *** preorder(s); fprintf(stderr, " )n");
  1040. */
  1041. if ( s->token == ALT && s->right == NULL ) return tmember(e, s->down);
  1042. if ( e->token!=s->token )
  1043. {
  1044. if ( s->right==NULL ) return 0;
  1045. return tmember(e, s->right);
  1046. }
  1047. if ( e->down==NULL && s->down == NULL ) return 1;
  1048. if ( tmember(e->down, s->down) ) return 1;
  1049. if ( s->right==NULL ) return 0;
  1050. return tmember(e, s->right);
  1051. }
  1053. /* see if e exists in s as a possible input permutation (e is always a chain);
  1054.  * Only check s to the depth of e.  In other words, 'e' can be a shorter
  1055.  * sequence than s.
  1056.  */
  1057. int
  1058. #ifdef __STDC__
  1059. tmember_constrained( Tree *e, Tree *s)
  1060. #else
  1061. tmember_constrained( e, s )
  1062. Tree *e;
  1063. Tree *s;
  1064. #endif
  1065. {
  1066. if ( e==NULL||s==NULL ) return 0;
  1067. /** fprintf(stderr, "tmember_constrained(");
  1068. *** preorder(e); fprintf(stderr, ",");
  1069. *** preorder(s); fprintf(stderr, " )n");
  1070. **/
  1071. if ( s->token == ALT && s->right == NULL )
  1072. return tmember_constrained(e, s->down);
  1073. if ( e->token!=s->token )
  1074. {
  1075. if ( s->right==NULL ) return 0;
  1076. return tmember_constrained(e, s->right);
  1077. }
  1078. if ( e->down == NULL ) return 1; /* if s is matched to depth of e return */
  1079. if ( tmember_constrained(e->down, s->down) ) return 1;
  1080. if ( s->right==NULL ) return 0;
  1081. return tmember_constrained(e, s->right);
  1082. }
  1084. /* combine (? (A t) ... (A u) ...) into (? (A t u)) */
  1085. Tree *
  1086. #ifdef __STDC__
  1087. tleft_factor( Tree *t )
  1088. #else
  1089. tleft_factor( t )
  1090. Tree *t;
  1091. #endif
  1092. {
  1093. Tree *u, *v, *trail, *w;
  1095. /* left-factor what is at this level */
  1096. if ( t == NULL ) return NULL;
  1097. for (u=t; u!=NULL; u=u->right)
  1098. {
  1099. trail = u;
  1100. v=u->right;
  1101. while ( v!=NULL )
  1102. {
  1103. if ( u->token == v->token )
  1104. {
  1105. if ( u->down!=NULL )
  1106. {
  1107. for (w=u->down; w->right!=NULL; w=w->right) {;}
  1108. w->right = v->down; /* link children together */
  1109. }
  1110. else u->down = v->down;
  1111. trail->right = v->right; /* unlink factored node */
  1112. _Tfree( v );
  1113. v = trail->right;
  1114. }
  1115. else {trail = v; v=v->right;}
  1116. }
  1117. }
  1118. /* left-factor what is below */
  1119. for (u=t; u!=NULL; u=u->right) u->down = tleft_factor( u->down );
  1120. return t;
  1121. }
  1123. /* remove the permutation p from t if present */
  1124. Tree *
  1125. #ifdef __STDC__
  1126. trm_perm( Tree *t, Tree *p )
  1127. #else
  1128. trm_perm( t, p )
  1129. Tree *t;
  1130. Tree *p;
  1131. #endif
  1132. {
  1133. /*
  1134. fprintf(stderr, "trm_perm(");
  1135. preorder(t); fprintf(stderr, ",");
  1136. preorder(p); fprintf(stderr, " )n");
  1137. */
  1138. if ( t == NULL || p == NULL ) return NULL;
  1139. if ( t->token == ALT )
  1140. {
  1141. t->down = trm_perm(t->down, p);
  1142. if ( t->down == NULL )  /* nothing left below, rm cur node */
  1143. {
  1144. Tree *u = t->right;
  1145. _Tfree( t );
  1146. return trm_perm(u, p);
  1147. }
  1148. t->right = trm_perm(t->right, p); /* look for more instances of p */
  1149. return t;
  1150. }
  1151. if ( p->token != t->token ) /* not found, try a sibling */
  1152. {
  1153. t->right = trm_perm(t->right, p);
  1154. return t;
  1155. }
  1156. t->down = trm_perm(t->down, p->down);
  1157. if ( t->down == NULL )  /* nothing left below, rm cur node */
  1158. {
  1159. Tree *u = t->right;
  1160. _Tfree( t );
  1161. return trm_perm(u, p);
  1162. }
  1163. t->right = trm_perm(t->right, p); /* look for more instances of p */
  1164. return t;
  1165. }
  1167. /* add the permutation 'perm' to the LL_k sets in 'fset' */
  1168. void
  1169. #ifdef __STDC__
  1170. tcvt( set *fset, Tree *perm )
  1171. #else
  1172. tcvt( fset, perm )
  1173. set *fset;
  1174. Tree *perm;
  1175. #endif
  1176. {
  1177. if ( perm==NULL ) return;
  1178. set_orel(perm->token, fset);
  1179. tcvt(fset+1, perm->down);
  1180. }
  1182. /* for each element of ftbl[k], make it the root of a tree with permute(ftbl[k+1])
  1183.  * as a child.
  1184.  */
  1185. Tree *
  1186. #ifdef __STDC__
  1187. permute( int k, int max_k )
  1188. #else
  1189. permute( k, max_k )
  1190. int k, max_k;
  1191. #endif
  1192. {
  1193. Tree *t, *u;
  1195. if ( k>max_k ) return NULL;
  1196. if ( ftbl[k][findex[k]] == nil ) return NULL;
  1197. t = permute(k+1, max_k);
  1198. if ( t==NULL&&k<max_k ) /* no permutation left below for k+1 tokens? */
  1199. {
  1200. findex[k+1] = 0;
  1201. (findex[k])++; /* try next token at this k */
  1202. return permute(k, max_k);
  1203. }
  1205. u = tmake(tnode(ftbl[k][findex[k]]), t, NULL);
  1206. if ( k == max_k ) (findex[k])++;
  1207. return u;
  1208. }
  1210. /* Compute LL(k) trees for alts alt1 and alt2 of p.
  1211.  * function result is tree of ambiguous input permutations
  1212.  *
  1213.  * ALGORITHM may change to look for something other than LL_k size
  1214.  * trees ==> maxk will have to change.
  1215.  */
  1216. Tree *
  1217. #ifdef __STDC__
  1218. VerifyAmbig( Junction *alt1, Junction *alt2, unsigned **ft, set *fs, Tree **t, Tree **u, int *numAmbig )
  1219. #else
  1220. VerifyAmbig( alt1, alt2, ft, fs, t, u, numAmbig )
  1221. Junction *alt1;
  1222. Junction *alt2;
  1223. unsigned **ft;
  1224. set *fs;
  1225. Tree **t;
  1226. Tree **u;
  1227. int *numAmbig;
  1228. #endif
  1229. {
  1230. set rk;
  1231. Tree *perm, *ambig=NULL;
  1232. Junction *p;
  1233. int k;
  1234.     int    tnodes_at_start=TnodesAllocated;
  1235.     int    tnodes_at_end;
  1236.     int    tnodes_used;
  1237.     set    *save_fs;
  1238.     int    j;
  1240.     save_fs=(set *) calloc(CLL_k+1,sizeof(set));
  1241.     require(save_fs != NULL,"save_fs calloc");
  1243.     for (j=0; j <= CLL_k ; j++) save_fs[j]=set_dup(fs[j]);
  1245. maxk = LL_k; /* NOTE: for now, we look for LL_k */
  1246. ftbl = ft;
  1247. fset = fs;
  1248. constrain = &(fset[1]);
  1249. findex = (int *) calloc(LL_k+1, sizeof(int));
  1250. if ( findex == NULL )
  1251. {
  1252. fprintf(stderr, ErrHdr, FileStr[CurAmbigfile], CurAmbigline);
  1253. fprintf(stderr, " out of memory while analyzing alts %d and %d of %sn",
  1254. CurAmbigAlt1,
  1255. CurAmbigAlt2,
  1256. CurAmbigbtype);
  1257. exit(PCCTS_EXIT_FAILURE);
  1258. }
  1259. for (k=1; k<=LL_k; k++) findex[k] = 0;
  1261. rk = empty;
  1262. ConstrainSearch = 1; /* consider only tokens in ambig sets */
  1264. p = analysis_point((Junction *)alt1->p1);
  1265. TRAV(p, LL_k, &rk, *t);
  1266. *t = tshrink( *t );
  1267. *t = tflatten( *t );
  1268. *t = tleft_factor( *t );    /* MR10 */
  1269. *t = prune(*t, LL_k);
  1270. *t = tleft_factor( *t );
  1272. /*** fprintf(stderr, "after shrink&flatten&prune&left_factor:"); preorder(*t); fprintf(stderr, "n");*/
  1273. if ( *t == NULL )
  1274. {
  1275. /*** fprintf(stderr, "TreeIncomplete --> no LL(%d) ambiguityn", LL_k);*/
  1276. Tfree( *t ); /* kill if impossible to have ambig */
  1277. *t = NULL;
  1278. }
  1280. p = analysis_point((Junction *)alt2->p1);
  1282. TRAV(p, LL_k, &rk, *u);
  1283. *u = tshrink( *u );
  1284. *u = tflatten( *u );
  1285. *t = tleft_factor( *t );    /* MR10 */
  1286. *u = prune(*u, LL_k);
  1287. *u = tleft_factor( *u );
  1288. /* fprintf(stderr, "after shrink&flatten&prune&lfactor:"); preorder(*u); fprintf(stderr, "n");*/
  1289. if ( *u == NULL )
  1290. {
  1291. /* fprintf(stderr, "TreeIncomplete --> no LL(%d) ambiguityn", LL_k);*/
  1292. Tfree( *u );
  1293. *u = NULL;
  1294. }
  1296. for (k=1; k<=LL_k; k++) set_clr( fs[k] );
  1298. ambig = tnode(ALT);
  1299. k = 0;
  1300. if ( *t!=NULL && *u!=NULL )
  1301. {
  1302. while ( (perm=permute(1,LL_k))!=NULL )
  1303. {
  1304. /* fprintf(stderr, "chk perm:"); preorder(perm); fprintf(stderr, "n");*/
  1305. if ( tmember(perm, *t) && tmember(perm, *u) )
  1306. {
  1307. /* fprintf(stderr, "ambig upon"); preorder(perm); fprintf(stderr, "n");*/
  1309. k++;
  1310. perm->right = ambig->down;
  1311. ambig->down = perm;
  1312. tcvt(&(fs[1]), perm);
  1313. }
  1314. else Tfree( perm );
  1315. }
  1316. }
  1318.     for (j=0; j <= CLL_k ; j++) fs[j]=save_fs[j];
  1319.     free( (char *) save_fs);
  1321.     tnodes_at_end=TnodesAllocated;
  1322.     tnodes_used=tnodes_at_end - tnodes_at_start;
  1324.     if (TnodesReportThreshold > 0 && tnodes_used > TnodesReportThreshold) {
  1325.       fprintf(stdout,"There were %d tuples whose ambiguity could not be resolved by full lookaheadn",k);
  1326.       fprintf(stdout,"There were %d tnodes created to resolve ambiguity between:nn",tnodes_used);
  1327.       fprintf(stdout,"  Choice 1: %s  line %d  file %sn",
  1328.                                  MR_ruleNamePlusOffset( (Node *) alt1),alt1->line,FileStr[alt1->file]);
  1329.       fprintf(stdout,"  Choice 2: %s  line %d  file %sn",
  1330.                                  MR_ruleNamePlusOffset( (Node *) alt2),alt2->line,FileStr[alt2->file]);
  1331.       for (j=1; j <= CLL_k ; j++) {
  1332.         fprintf(stdout,"n    Intersection of lookahead[%d] sets:n",j);
  1333.         MR_dumpTokenSet(stdout,2,fs[j]);
  1334.       };
  1335.       fprintf(stdout,"n");
  1336.     };
  1338. *numAmbig = k;
  1339. if ( ambig->down == NULL ) {_Tfree(ambig); ambig = NULL;}
  1340. free( (char *)findex );
  1341. /* fprintf(stderr, "final ambig:"); preorder(ambig); fprintf(stderr, "n");*/
  1342. return ambig;
  1343. }
  1345. static Tree *
  1346. #ifdef __STDC__
  1347. bottom_of_chain( Tree *t )
  1348. #else
  1349. bottom_of_chain( t )
  1350. Tree *t;
  1351. #endif
  1352. {
  1353.     if ( t==NULL ) return NULL;
  1354.     for (; t->down != NULL; t=t->down) {;}
  1355.     return t;
  1356. }
  1358. /*
  1359.  * Make a tree from k sets where the degree of the first k-1 sets is 1.
  1360.  */
  1361. Tree *
  1362. #ifdef __STDC__
  1363. make_tree_from_sets( set *fset1, set *fset2 )
  1364. #else
  1365. make_tree_from_sets( fset1, fset2 )
  1366. set *fset1;
  1367. set *fset2;
  1368. #endif
  1369. {
  1370. set inter;
  1371. int i;
  1372. Tree *t=NULL, *n, *u;
  1373. unsigned *p,*q;
  1374. require(LL_k>1, "make_tree_from_sets: LL_k must be > 1");
  1376. /* do the degree 1 sets first */
  1377. for (i=1; i<=LL_k-1; i++)
  1378. {
  1379. inter = set_and(fset1[i], fset2[i]);
  1380. require(set_deg(inter)==1, "invalid set to tree conversion");
  1381. n = tnode(set_int(inter));
  1382. if (t==NULL) t=n; else tmake(t, n, NULL);
  1383. set_free(inter);
  1384. }
  1386. /* now add the chain of tokens at depth k */
  1387. u = bottom_of_chain(t);
  1388. inter = set_and(fset1[LL_k], fset2[LL_k]);
  1389. if ( (q=p=set_pdq(inter)) == NULL ) fatal_internal("Can't alloc space for set_pdq");
  1390. /* first one is linked to bottom, then others are sibling linked */
  1391. n = tnode(*p++);
  1392. u->down = n;
  1393. u = u->down;
  1394. while ( *p != nil )
  1395. {
  1396. n = tnode(*p);
  1397. u->right = n;
  1398. u = u->right;
  1399. p++;
  1400. }
  1401. free((char *)q);
  1403. return t;
  1404. }
  1406. /* create and return the tree of lookahead k-sequences that are in t, but not
  1407.  * in the context of predicates in predicate list p.
  1408.  */
  1409. Tree *
  1410. #ifdef __STDC__
  1411. tdif( Tree *ambig_tuples, Predicate *p, set *fset1, set *fset2 )
  1412. #else
  1413. tdif( ambig_tuples, p, fset1, fset2 )
  1414. Tree *ambig_tuples;
  1415. Predicate *p;
  1416. set *fset1;
  1417. set *fset2;
  1418. #endif
  1419. {
  1420. unsigned **ft;
  1421. Tree *dif=NULL;
  1422. Tree *perm;
  1423. set b;
  1424. int i,k;
  1426. if ( p == NULL ) return tdup(ambig_tuples);
  1428. ft = (unsigned **) calloc(CLL_k+1, sizeof(unsigned *));
  1429. require(ft!=NULL, "cannot allocate ft");
  1430. for (i=1; i<=CLL_k; i++)
  1431. {
  1432. b = set_and(fset1[i], fset2[i]);
  1433. ft[i] = set_pdq(b);
  1434. set_free(b);
  1435. }
  1436. findex = (int *) calloc(LL_k+1, sizeof(int));
  1437. if ( findex == NULL )
  1438. {
  1439. fatal_internal("out of memory in tdif while checking predicates");
  1440. }
  1441. for (k=1; k<=LL_k; k++) findex[k] = 0;
  1443. #ifdef DBG_TRAV
  1444. fprintf(stderr, "tdif_%d[", p->k);
  1445. preorder(ambig_tuples);
  1446. fprintf(stderr, ",");
  1447. preorder(p->tcontext);
  1448. fprintf(stderr, "] =");
  1449. #endif
  1451. ftbl = ft;
  1452. while ( (perm=permute(1,p->k))!=NULL )
  1453. {
  1454. #ifdef DBG_TRAV
  1455. fprintf(stderr, "test perm:"); preorder(perm); fprintf(stderr, "n");
  1456. #endif
  1457. if ( tmember_constrained(perm, ambig_tuples) &&
  1458.  !tmember_of_context(perm, p) )
  1459. {
  1460. #ifdef DBG_TRAV
  1461. fprintf(stderr, "satisfied upon"); preorder(perm); fprintf(stderr, "n");
  1462. #endif
  1463. k++;
  1464. if ( dif==NULL ) dif = perm;
  1465. else
  1466. {
  1467. perm->right = dif;
  1468. dif = perm;
  1469. }
  1470. }
  1471. else Tfree( perm );
  1472. }
  1474. #ifdef DBG_TRAV
  1475. preorder(dif);
  1476. fprintf(stderr, "n");
  1477. #endif
  1479. for (i=1; i<=CLL_k; i++) free( (char *)ft[i] );
  1480. free((char *)ft);
  1481. free((char *)findex);
  1483. return dif;
  1484. }
  1486. /* is lookahead sequence t a member of any context tree for any
  1487.  * predicate in p?
  1488.  */
  1489. static int
  1490. #ifdef __STDC__
  1491. tmember_of_context( Tree *t, Predicate *p )
  1492. #else
  1493. tmember_of_context( t, p )
  1494. Tree *t;
  1495. Predicate *p;
  1496. #endif
  1497. {
  1498. for (; p!=NULL; p=p->right)
  1499. {
  1500. if ( p->expr==PRED_AND_LIST || p->expr==PRED_OR_LIST )
  1501. return tmember_of_context(t, p->down);
  1502. if ( tmember_constrained(t, p->tcontext) ) return 1;
  1503. if ( tmember_of_context(t, p->down) ) return 1;
  1504. }
  1505. return 0;
  1506. }
  1508. int
  1509. #ifdef __STDC__
  1510. is_single_tuple( Tree *t )
  1511. #else
  1512. is_single_tuple( t )
  1513. Tree *t;
  1514. #endif
  1515. {
  1516. if ( t == NULL ) return 0;
  1517. if ( t->right != NULL ) return 0;
  1518. if ( t->down == NULL ) return 1;
  1519. return is_single_tuple(t->down);
  1520. }
  1523. /* MR10 Check that a context guard contains only allowed things */
  1524. /* MR10   (mainly token references).                            */
  1526. #ifdef __STDC__
  1527. int contextGuardOK(Node *p,int h,int *hmax)
  1528. #else
  1529. int contextGuardOK(p,h,hmax)
  1530.   Node  *p;
  1531.   int   h;
  1532.   int   *hmax;
  1533. #endif
  1534. {
  1535.     Junction     *j;
  1536.     TokNode      *tn;
  1538.     if (p == NULL) return 1;
  1539.     if (p->ntype == nToken) {
  1540.       h++;
  1541.       if (h > *hmax) *hmax=h;
  1542.       tn=(TokNode *)p;
  1543.       if (tn->el_label != NULL) {
  1544.         warnFL(eMsg1("a label ("%s") for a context guard element is meaningless",tn->el_label),
  1545.                              FileStr[p->file],p->line);
  1546.       };
  1547.       return contextGuardOK( ( (TokNode *) p)->next,h,hmax);
  1548.     } else if (p->ntype == nAction) {
  1549.       goto Fail;
  1550.     } else if (p->ntype == nRuleRef) {
  1551.       goto Fail;
  1552.     } else {
  1553.       require (p->ntype == nJunction,"Unexpected ntype");
  1554.       j=(Junction *) p;
  1555.       if (j->jtype != Generic &&
  1556.           j->jtype != aSubBlk &&        /* pretty sure this one is allowed */
  1557. /****     j->jtype != aOptBlk && ****/  /* pretty sure this one is allowed */ /* MR11 not any more ! */
  1558.           j->jtype != EndBlk) {
  1559.         errFL("A context guard may not contain an option block: {...} or looping block: (...)* or (...)+",
  1560.                   FileStr[p->file],p->line);
  1561.         contextGuardOK(j->p1,h,hmax);
  1562.         return 0;
  1563.       };
  1564.       /* do both p1 and p2 so use | rather than ||  */
  1565.       return contextGuardOK(j->p2,h,hmax) | contextGuardOK(j->p1,h,hmax);
  1566.     };
  1567. Fail:
  1568.     errFL("A context guard may contain only Token references - guard will be ignored",
  1569.                              FileStr[p->file],p->line);
  1570.     contextGuardOK( ( (ActionNode *) p)->next,h,hmax);
  1571.     return 0;
  1572. }
  1574. /*
  1575.  * Look at a (...)? generalized-predicate context-guard and compute
  1576.  * either a lookahead set (k==1) or a lookahead tree for k>1.  The
  1577.  * k level is determined by the guard itself rather than the LL_k
  1578.  * variable.  For example, ( A B )? is an LL(2) guard and ( ID )?
  1579.  * is an LL(1) guard.  For the moment, you can only have a single
  1580.  * tuple in the guard.  Physically, the block must look like this
  1581.  *   --o-->TOKEN-->o-->o-->TOKEN-->o-- ... -->o-->TOKEN-->o--
  1582.  * An error is printed for any other type.
  1583.  */
  1584. Predicate *
  1585. #ifdef __STDC__
  1586. computePredicateFromContextGuard(Graph blk,int *msgDone)    /* MR10 */
  1587. #else
  1588. computePredicateFromContextGuard(blk,msgDone)               /* MR10 */
  1589.   Graph     blk;
  1590.   int       *msgDone;                                       /* MR10 */
  1591. #endif
  1592. {
  1593.     Junction *junc = (Junction *)blk.left, *p;
  1594.     Tree        *t=NULL;
  1595. Predicate   *pred = NULL;
  1596. set         scontext, rk;
  1597.     int         ok;
  1598.     int         hmax=0;
  1600.     require(junc!=NULL && junc->ntype == nJunction, "bad context guard");
  1602. /* MR10 Check for anything other than Tokens and generic junctions */
  1604.     *msgDone=0;                                             /* MR10 */
  1605.     ok=contextGuardOK( (Node *)junc,0,&hmax);               /* MR10 */
  1606.     if (! ok) {                                             /* MR10 */
  1607.       *msgDone=1;                                           /* MR10 */
  1608.       return NULL;                                          /* MR10 */
  1609.     };                                                      /* MR10 */
  1610.     if (hmax == 0) {
  1611. errFL("guard is 0 tokens long",FileStr[junc->file],junc->line);          /* MR11 */
  1612.       *msgDone=1;
  1613.       return NULL;
  1614.     };
  1615.     if (hmax > CLL_k) {                                     /* MR10 */
  1616. errFL(eMsgd2("guard is %d tokens long - lookahead is limited to max(k,ck)==%d", /* MR10 */
  1617.         hmax,CLL_k),                                        /* MR10 */
  1618.         FileStr[junc->file],junc->line);                    /* MR10 */
  1619.       *msgDone=1;                                           /* MR10 */
  1620.       return NULL;                                          /* MR10 */
  1621.     };                                                      /* MR10 */
  1623. rk = empty;
  1624. p = junc;
  1625. pred = new_pred();
  1626. pred->k = hmax;     /* MR10 should be CLL_k, not LLK ? */
  1627. if (hmax > 1 )      /* MR10 was LL_k                   */
  1628. {
  1629. ConstrainSearch = 0;
  1630. ContextGuardTRAV = 1;
  1631. TRAV(p, hmax, &rk, t);  /* MR10 was LL_k */
  1632. ContextGuardTRAV = 0;
  1633. set_free(rk);
  1634. t = tshrink( t );
  1635. t = tflatten( t );
  1636. t = tleft_factor( t );
  1637. /*
  1638. fprintf(stderr, "ctx guard:");
  1639. preorder(t);
  1640. fprintf(stderr, "n");
  1641. */
  1642. pred->tcontext = t;
  1643. }
  1644. else
  1645. {
  1646. REACH(p, 1, &rk, scontext);
  1647. require(set_nil(rk), "rk != nil");
  1648. set_free(rk);
  1649. /*
  1650. fprintf(stderr, "LL(1) ctx guard is:");
  1651. s_fprT(stderr, scontext);
  1652. fprintf(stderr, "n");
  1653. */
  1654. pred->scontext[1] = scontext;
  1655. }
  1657.     list_add(&ContextGuardPredicateList,pred);     /* MR13 */
  1659. return pred;
  1660. }
  1662. /* MR13
  1663.    When the context guard is originally computed the
  1664.    meta-tokens are not known.
  1665. */
  1667. #ifdef __STDC__
  1668. void recomputeContextGuard(Predicate *pred)
  1669. #else
  1670. void recomputeContextGuard(pred)
  1671.     Predicate   *pred;
  1672. #endif
  1673. {
  1674.     Tree *          t=NULL;
  1675. set             scontext;
  1676.     set             rk;
  1677.     ActionNode *    actionNode;
  1678.     Junction *      p;
  1680.     actionNode=pred->source;
  1681.     require (actionNode != NULL,"context predicate's source == NULL");
  1683.     p=actionNode->guardNodes;
  1684.     require (p != NULL,"context predicate's guardNodes == NULL");
  1686. rk = empty;
  1687. if (pred->k > 1 )
  1688. {
  1689. ConstrainSearch = 0;
  1690. ContextGuardTRAV = 1;
  1691. TRAV(p, pred->k, &rk, t);
  1692. ContextGuardTRAV = 0;
  1693. set_free(rk);
  1694. t = tshrink( t );
  1695. t = tflatten( t );
  1696. t = tleft_factor( t );
  1697.         Tfree(pred->tcontext);
  1698. pred->tcontext = t;
  1699. }
  1700. else
  1701. {
  1702. REACH(p, 1, &rk, scontext);
  1703. require(set_nil(rk), "rk != nil");
  1704. set_free(rk);
  1705.         set_free(pred->scontext[1]);
  1706. pred->scontext[1] = scontext;
  1707. }
  1708. }
  1710. /* MR11 - had enough of flags yet ? */
  1712. int     MR_AmbSourceSearch=0;
  1713. int     MR_AmbSourceSearchGroup=0;
  1714. int     MR_AmbSourceSearchChoice=0;
  1715. int     MR_AmbSourceSearchLimit=0;
  1716. int     MR_matched_AmbAidRule=0;
  1718. static    set         *matchSets[2]={NULL,NULL};
  1719. static    int         *tokensInChain=NULL;
  1720. static    Junction    *MR_AmbSourceSearchJ[2];
  1722. void MR_traceAmbSourceKclient()
  1723. {
  1724.   int       i;
  1725.   set       *save_fset;
  1726.   int       save_ConstrainSearch;
  1727.   set       incomplete;
  1728.   Tree      *t;
  1730.   if (matchSets[0] == NULL) {
  1731.     matchSets[0]=(set *) calloc (CLL_k+1,sizeof(set));
  1732.     require (matchSets[0] != NULL,"matchSets[0] alloc");
  1733.     matchSets[1]=(set *) calloc (CLL_k+1,sizeof(set));
  1734.     require (matchSets[1] != NULL,"matchSets[1] alloc");
  1735.   };
  1737.   for (i=1 ; i <= MR_AmbSourceSearchLimit ; i++) {
  1738.     set_clr(matchSets[0][i]);
  1739.     set_orel( (unsigned) tokensInChain[i],
  1740.                               &matchSets[0][i]);
  1741.     set_clr(matchSets[1][i]);
  1742.     set_orel( (unsigned) tokensInChain[i],
  1743.                               &matchSets[1][i]);
  1744.   };
  1746.   save_fset=fset;
  1747.   save_ConstrainSearch=ConstrainSearch;
  1751.   for (i=0 ; i < 2 ; i++) {
  1753. #if 0
  1754. **    fprintf(stdout,"  Choice:%d  Depth:%d  ",i+1,MR_AmbSourceSearchLimit);
  1755. **    fprintf(stdout,"(");
  1756. **    for (j=1 ; j <= MR_AmbSourceSearchLimit ; j++) {
  1757. **      if (j != 1) fprintf(stdout," ");
  1758. **      fprintf(stdout,"%s",TerminalString(tokensInChain[j]));
  1759. **    };
  1760. **    fprintf(stdout,")nn");
  1761. #endif
  1763.     fset=matchSets[i];
  1765.     MR_AmbSourceSearch=1;
  1766.     MR_MaintainBackTrace=1;
  1767.     MR_AmbSourceSearchChoice=i;
  1768.     ConstrainSearch=1;
  1770.     maxk = MR_AmbSourceSearchLimit;
  1772.     incomplete=empty;
  1773.     t=NULL;
  1775.     constrain = &(fset[1]);
  1776.     MR_pointerStackReset(&MR_BackTraceStack);
  1778.     TRAV(MR_AmbSourceSearchJ[i],maxk,&incomplete,t);
  1780.     Tfree(t);
  1782.     require (set_nil(incomplete),"MR_traceAmbSourceK TRAV incomplete");
  1783.     require (MR_BackTraceStack.count == 0,"K: MR_BackTraceStack.count != 0");
  1785.     set_free(incomplete);
  1786.   };
  1788.   ConstrainSearch=save_ConstrainSearch;
  1789.   fset=save_fset;
  1790.   MR_AmbSourceSearch=0;
  1791.   MR_MaintainBackTrace=0;
  1792.   MR_AmbSourceSearchChoice=0;
  1793. }
  1795. #ifdef __STDC__
  1796. Tree *tTrunc(Tree *t,int depth)
  1797. #else
  1798. Tree *tTrunc(t,depth)
  1799.   Tree  *t;
  1800. #endif
  1801. {
  1802.     Tree    *u;
  1804.     require ( ! (t == NULL && depth > 0),"tree too short");
  1806.     if (depth == 0) return NULL;
  1808.     if (t->token == ALT) {
  1809.       u=tTrunc(t->down,depth);
  1810.     } else {
  1811.       u=tnode(t->token);
  1812.       u->down=tTrunc(t->down,depth-1);
  1813.     };
  1814.     if (t->right != NULL) u->right=tTrunc(t->right,depth);
  1815.     return u;
  1816. }
  1818. #ifdef __STDC__
  1819. void MR_iterateOverTree(Tree *t,int chain[])
  1820. #else
  1821. void MR_iterateOverTree(t,chain)
  1822.   Tree          *t;
  1823.   int           chain[];
  1824. #endif
  1825. {
  1826.   if (t == NULL) return;
  1827.   chain[0]=t->token;
  1828.   if (t->down != NULL) {
  1829.     MR_iterateOverTree(t->down,&chain[1]);
  1830.   } else {
  1831.     MR_traceAmbSourceKclient();
  1832.   };
  1833.   MR_iterateOverTree(t->right,&chain[0]);
  1834.   chain[0]=0;
  1835. }
  1837. #ifdef __STDC__
  1838. void MR_traceAmbSourceK(Tree *t,Junction *alt1,Junction *alt2)
  1839. #else
  1840. void MR_traceAmbSourceK(t,alt1,alt2)
  1841.   Tree      *t;
  1842.   Junction  *alt1;
  1843.   Junction  *alt2;
  1844. #endif
  1845. {
  1846.     int         i;
  1847.     int         depth;
  1848.     int         maxDepth;
  1849.     Tree        *truncatedTree;
  1851.     if (MR_AmbAidRule == NULL) return;
  1853.     if ( ! (
  1854.             strcmp(MR_AmbAidRule,alt1->rname) == 0 ||
  1855.             strcmp(MR_AmbAidRule,alt2->rname) == 0 ||
  1856.             MR_AmbAidLine==alt1->line ||
  1857.             MR_AmbAidLine==alt2->line
  1858.            )
  1859.        ) return;
  1861.     MR_matched_AmbAidRule++;
  1863.     /* there are no token sets in trees, only in TokNodes */
  1865.     MR_AmbSourceSearchJ[0]=analysis_point( (Junction *) alt1->p1);
  1866.     MR_AmbSourceSearchJ[1]=analysis_point( (Junction *) alt2->p1);
  1868.     if (tokensInChain == NULL) {
  1869.       tokensInChain=(int *) calloc (CLL_k+1,sizeof(int));
  1870.       require (tokensInChain != NULL,"tokensInChain alloc");
  1871.     };
  1873.     MR_AmbSourceSearchGroup=0;
  1875.     fprintf(stdout,"n");
  1876.     fprintf(stdout,"  Ambiguity Aid                 ");
  1877.     fprintf(stdout,
  1878.                 (MR_AmbAidDepth <= LL_k ?
  1879.                     "(-k %d  -aa %s  %s  -aad %d)nn" :
  1880.                         "(-k %d  -aa %s  %s  [-k value limits -aad %d])nn"),
  1881.                 LL_k,
  1882.                 MR_AmbAidRule,
  1883.                 (MR_AmbAidMultiple ? "-aam" : ""),
  1884.                 MR_AmbAidDepth);
  1886.     for (i=0 ; i < 2 ; i++) {
  1887.       fprintf(stdout,"    Choice %d: %-25s  line %d  file %sn",
  1888.                   (i+1),
  1889.                   MR_ruleNamePlusOffset( (Node *) MR_AmbSourceSearchJ[i]),
  1890.                   MR_AmbSourceSearchJ[i]->line,
  1891.                   FileStr[MR_AmbSourceSearchJ[i]->file]);
  1892.     };
  1894.     fprintf(stdout,"n");
  1896.     if (MR_AmbAidDepth < LL_k) {
  1897.       maxDepth=MR_AmbAidDepth;
  1898.     } else {
  1899.       maxDepth=LL_k;
  1900.     };
  1902.     for (depth=1 ; depth <= maxDepth; depth++) {
  1903.       MR_AmbSourceSearchLimit=depth;
  1904.       if (depth < LL_k) {
  1905.         truncatedTree=tTrunc(t,depth);
  1906.         truncatedTree=tleft_factor(truncatedTree);
  1907.         MR_iterateOverTree(truncatedTree,&tokensInChain[1]);    /* <===== */
  1908.         Tfree(truncatedTree);
  1909.       } else {
  1910.         MR_iterateOverTree(t,tokensInChain);                /* <===== */
  1911.       };
  1912.       fflush(stdout);
  1913.       fflush(stderr);
  1914.     };
  1916.     fprintf(stdout,"n");
  1917.     MR_AmbSourceSearch=0;
  1918.     MR_MaintainBackTrace=0;
  1919.     MR_AmbSourceSearchGroup=0;
  1920.     MR_AmbSourceSearchChoice=0;
  1921.     MR_AmbSourceSearchLimit=0;
  1923. }
  1926. /* this if for k=1 grammars only
  1928.    this is approximate only because of the limitations of linear
  1929.    approximation lookahead.  Don't want to do a k=3 search when
  1930.    the user only specified a ck=3 grammar
  1931. */
  1933. #ifdef __STDC__
  1934. void MR_traceAmbSource(set *matchSets,Junction *alt1, Junction *alt2)
  1935. #else
  1936. void MR_traceAmbSource(matchSets,alt1,alt2)
  1937.   set       *matchSets;
  1938.   Junction  *alt1;
  1939.   Junction  *alt2;
  1940. #endif
  1941. {
  1942.     set         *save_fset;
  1943.     Junction    *p[2];
  1944.     int         i;
  1945.     int         j;
  1946.     set         *dup_matchSets;
  1947.     set         intersection;
  1948.     set         incomplete;
  1949.     set         tokensUsed;
  1950.     int         depth;
  1952.     if (MR_AmbAidRule == NULL) return;
  1953.     if ( ! (
  1954.             strcmp(MR_AmbAidRule,alt1->rname) == 0 ||
  1955.             strcmp(MR_AmbAidRule,alt2->rname) == 0 ||
  1956.             MR_AmbAidLine==alt1->line ||
  1957.             MR_AmbAidLine==alt2->line
  1958.            )
  1959.        ) return;
  1961.     MR_matched_AmbAidRule++;
  1963.     save_fset=fset;
  1965.     dup_matchSets=(set *) calloc(CLL_k+1,sizeof(set));
  1966.     require (dup_matchSets != NULL,"Can't allocate dup_matchSets");
  1968.     p[0]=analysis_point( (Junction *) alt1->p1);
  1969.     p[1]=analysis_point( (Junction *) alt2->p1);
  1971.     fprintf(stdout,"n");
  1973.     fprintf(stdout,"  Ambiguity Aid                 ");
  1974.     fprintf(stdout,
  1975.                 (MR_AmbAidDepth <= CLL_k ?
  1976.                     "(-ck %d  -aa %s  %s  -aad %d)nn" :
  1977.                         "(-ck %d  -aa %s  %s  [-ck value limits -aad %d])nn"),
  1978.                 CLL_k,
  1979.                 MR_AmbAidRule,
  1980.                 (MR_AmbAidMultiple ? "-aam" : ""),
  1981.                 MR_AmbAidDepth);
  1983.     for (i=0 ; i < 2 ; i++) {
  1984.       fprintf(stdout,"    Choice %d: %-25s  line %d  file %sn",
  1985.                             (i+1),
  1986.                             MR_ruleNamePlusOffset( (Node *) p[i]),
  1987.                             p[i]->line,FileStr[p[i]->file]);
  1988.     };
  1990.     for (j=1; j <= CLL_k ; j++) {
  1991.       fprintf(stdout,"n    Intersection of lookahead[%d] sets:n",j);
  1992.       intersection=set_and(alt1->fset[j],alt2->fset[j]);
  1993.       MR_dumpTokenSet(stdout,2,intersection);
  1994.       set_free(intersection);
  1995.     };
  1997.     fprintf(stdout,"n");
  1999.     require (1 <= MR_AmbAidDepth && MR_AmbAidDepth <= CLL_k,
  2000.                 "illegal MR_AmbAidDepth");
  2002.     MR_AmbSourceSearchGroup=0;
  2003.     for (depth=1; depth <= MR_AmbAidDepth; depth++) {
  2004.         MR_AmbSourceSearchLimit=depth;
  2005.         for (i=0 ; i < 2 ; i++) {
  2007. /***        fprintf(stdout,"  Choice:%d  Depth:%dnn",i+1,depth);  ***/
  2009.             for (j=0 ; j <= CLL_k ; j++) { dup_matchSets[j]=set_dup(matchSets[j]); };
  2010.             fset=dup_matchSets;
  2012.             fflush(output);
  2013.             fflush(stdout);
  2015.             MR_AmbSourceSearch=1;
  2016.             MR_MaintainBackTrace=1;
  2017.             MR_AmbSourceSearchChoice=i;
  2019.             maxk = depth;
  2020.             tokensUsed=empty;
  2021.             incomplete=empty;
  2023.             constrain = &(fset[1]);
  2024.             MR_pointerStackReset(&MR_BackTraceStack);
  2026.             REACH(p[i],depth,&incomplete,tokensUsed);
  2028.             fflush(output);
  2029.             fflush(stdout);
  2031.             require (set_nil(incomplete),"MR_traceAmbSource REACH incomplete");
  2032.             require (MR_BackTraceStack.count == 0,"1: MR_BackTraceStack.count != 0");
  2034.             set_free(incomplete);
  2035.             set_free(tokensUsed);
  2037.             for (j=0 ; j <= CLL_k ; j++) { set_free(dup_matchSets[j]); };
  2038.         };
  2039.     };
  2041.     fprintf(stdout,"n");
  2043.     MR_AmbSourceSearch=0;
  2044.     MR_MaintainBackTrace=0;
  2045.     MR_AmbSourceSearchGroup=0;
  2046.     MR_AmbSourceSearchChoice=0;
  2047.     MR_AmbSourceSearchLimit=0;
  2049.     fset=save_fset;
  2050.     free ( (char *) dup_matchSets);
  2051. }
  2053. static int itemCount;
  2055. void MR_backTraceDumpItemReset() {
  2056.   itemCount=0;
  2057. }
  2059. #ifdef __STDC__
  2060. void MR_backTraceDumpItem(FILE *f,int skip,Node *n)
  2061. #else
  2062. void MR_backTraceDumpItem(f,skip,n)
  2063.   FILE      *f;
  2064.   int       skip;
  2065.   Node      *n;
  2066. #endif
  2067. {
  2068.   TokNode       *tn;
  2069.   RuleRefNode   *rrn;
  2070.   Junction      *j;
  2071.   ActionNode    *a;
  2073.   switch (n->ntype) {
  2074.     case nToken:
  2075.         itemCount++; if (skip) goto EXIT;
  2076.         tn=(TokNode *)n;
  2077.         if (set_nil(tn->tset)) {
  2078.           fprintf(f,"  %2d #token %-23s",itemCount,TerminalString(tn->token));
  2079.         } else {
  2080.           fprintf(f,"  %2d #tokclass %-20s",itemCount,TerminalString(tn->token));
  2081.         };
  2082.         break;
  2083.     case nRuleRef:
  2084.         itemCount++; if (skip) goto EXIT;
  2085.         rrn=(RuleRefNode *)n;
  2086.         fprintf(f,"  %2d to %-27s",itemCount,rrn->text);
  2087.         break;
  2088.     case nAction:
  2089.         a=(ActionNode *)n;
  2090.         goto EXIT;
  2091.     case nJunction:
  2093.       j=(Junction *)n;
  2095.       switch (j->jtype) {
  2096.         case aSubBlk:
  2097.             if (j->guess) {
  2098.               itemCount++; if (skip) goto EXIT;
  2099.               fprintf(f,"  %2d %-30s",itemCount,"in (...)? block at");
  2100.               break;
  2101.             };
  2102. /******     fprintf(f,"  %2d %-32s",itemCount,"in (...) block at");  *******/
  2103. /******     break;                                                          *******/
  2104.             goto EXIT;
  2105.         case aOptBlk:
  2106.             itemCount++; if (skip) goto EXIT;
  2107.             fprintf(f,"  %2d %-30s",itemCount,"in {...} block");
  2108.             break;
  2109.         case aLoopBlk:
  2110.             itemCount++; if (skip) goto EXIT;
  2111.             fprintf(f,"  %2d %-30s",itemCount,"in (...)* block");
  2112.             break;
  2113.         case EndBlk:
  2114.             if (j->alpha_beta_guess_end) {
  2115.               itemCount++; if (skip) goto EXIT;
  2116.               fprintf(f,"  %2d %-30s",itemCount,"end (...)? block at");
  2117.               break;
  2118.             };
  2119.             goto EXIT;
  2120. /******     fprintf(f,"  %2d %-32s",itemCount,"end of a block at");     *****/
  2121. /******     break;                                                             *****/
  2122.         case RuleBlk:
  2123.             itemCount++; if (skip) goto EXIT;
  2124.             fprintf(f,"  %2d %-30s",itemCount,j->rname);
  2125.             break;
  2126.         case Generic:
  2127.             goto EXIT;
  2128.         case EndRule:
  2129.             itemCount++; if (skip) goto EXIT;
  2130.             fprintf (f,"  %2d end %-26s",itemCount,j->rname);
  2131.             break;
  2132.         case aPlusBlk:
  2133.             itemCount++; if (skip) goto EXIT;
  2134.             fprintf(f,"  %2d %-30s",itemCount,"in (...)+ block");
  2135.             break;
  2136.         case aLoopBegin:
  2137.             goto EXIT;
  2138.       };
  2139.       break;
  2140.   };
  2141.   fprintf(f," %-23s line %-4d  %sn",MR_ruleNamePlusOffset(n),n->line,FileStr[n->file]);
  2142. EXIT:
  2143.   return;
  2144. }
  2147. static PointerStack     previousBackTrace={0,0,NULL};
  2149. #ifdef __STDC__
  2150. void MR_backTraceReport()
  2151. #else
  2152. void MR_backTraceReport()
  2153. #endif
  2154. {
  2155.   int       i;
  2156.   int       match;
  2157.   int       limitMatch;
  2158.   Node      *p;
  2159.   TokNode   *tn;
  2160.   set       remainder;
  2161.   int       depth;
  2163.   /* Even when doing a k=2 search this routine can get
  2164.        called when there is only 1 token on the stack.
  2165.      This is because something like rRuleRef can change
  2166.        the search value of k from 2 to 1 temporarily.
  2167.      It does this because the it wants to know the k=1
  2168.        first set before it does a k=2 search
  2169.   */
  2171.   depth=0;
  2172.   for (i=0; i < MR_BackTraceStack.count ; i++) {
  2173.     p=(Node *) MR_BackTraceStack.data[i];
  2174.     if (p->ntype == nToken) depth++;
  2175.   };
  2177. /* MR14 */  if (MR_AmbSourceSearch) {
  2178. /* MR14 */     require (depth <= MR_AmbSourceSearchLimit,"depth > MR_AmbSourceSearchLimit");
  2179. /* MR14 */  }
  2181.   if (depth < MR_AmbSourceSearchLimit) {
  2182.     return;
  2183.   };
  2185.   MR_backTraceDumpItemReset();
  2187.   limitMatch=MR_BackTraceStack.count;
  2188.   if (limitMatch > previousBackTrace.count) {
  2189.     limitMatch=previousBackTrace.count;
  2190.   };
  2192.   for (match=0; match < limitMatch; match++) {
  2193.     if (MR_BackTraceStack.data[match] !=
  2194.         previousBackTrace.data[match]) {
  2195.       break;
  2196.     };
  2197.   };
  2199.   /* not sure at the moment why there would be duplicates */
  2201.   if (match != MR_BackTraceStack.count) {
  2203.     fprintf(stdout,"     Choice:%d  Depth:%d  Group:%d",
  2204.         (MR_AmbSourceSearchChoice+1),
  2205.         MR_AmbSourceSearchLimit,
  2206.         ++MR_AmbSourceSearchGroup);
  2208.     depth=0;
  2209.     fprintf(stdout,"  (");
  2210.     for (i=0; i < MR_BackTraceStack.count ; i++) {
  2211.       p=(Node *) MR_BackTraceStack.data[i];
  2212.       if (p->ntype != nToken) continue;
  2213.       tn=(TokNode *)p;
  2214.       if (depth != 0) fprintf(stdout," ");
  2215.       fprintf(stdout,TerminalString(tn->token));
  2216.       depth++;
  2217.       if (! MR_AmbAidMultiple) {
  2218.         if (set_nil(tn->tset)) {
  2219.           set_rm( (unsigned) tn->token,fset[depth]);
  2220.         } else {
  2221.           remainder=set_dif(fset[depth],tn->tset);
  2222.           set_free(fset[depth]);
  2223.           fset[depth]=remainder;
  2224.         };
  2225.       };
  2226.     };
  2227.     fprintf(stdout,")n");
  2229.     for (i=0; i < MR_BackTraceStack.count ; i++) {
  2230.       MR_backTraceDumpItem(stdout, (i<match) ,(Node *) MR_BackTraceStack.data[i]);
  2231.     };
  2232.     fprintf(stdout,"n");
  2233.     fflush(stdout);
  2235.     MR_pointerStackReset(&previousBackTrace);
  2237.     for (i=0; i < MR_BackTraceStack.count ; i++) {
  2238.       MR_pointerStackPush(&previousBackTrace,MR_BackTraceStack.data[i]);
  2239.     };
  2241.   };
  2242. }