home *** CD-ROM | disk | FTP | other *** search
/ OS/2 Shareware BBS: 10 Tools / 10-Tools.zip / pccts1.zip / ANTLR / FSET2.C < prev    next >
C/C++ Source or Header  |  1993-09-02  |  22KB  |  1,023 lines
  1. /*
  2.  * fset2.c
  3.  *
  4.  * $Id: fset2.c,v 1.8 1993/08/24 14:44:32 pccts Exp pccts $
  5.  * $Revision: 1.8 $
  6.  *
  7.  * Compute FIRST sets for full LL(k)
  8.  *
  9.  * SOFTWARE RIGHTS
  10.  *
  11.  * We reserve no LEGAL rights to the Purdue Compiler Construction Tool
  12.  * Set (PCCTS) -- PCCTS is in the public domain.  An individual or
  13.  * company may do whatever they wish with source code distributed with
  14.  * PCCTS or the code generated by PCCTS, including the incorporation of
  15.  * PCCTS, or its output, into commerical software.
  16.  * 
  17.  * We encourage users to develop software with PCCTS.  However, we do ask
  18.  * that credit is given to us for developing PCCTS.  By "credit",
  19.  * we mean that if you incorporate our source code into one of your
  20.  * programs (commercial product, research project, or otherwise) that you
  21.  * acknowledge this fact somewhere in the documentation, research report,
  22.  * etc...  If you like PCCTS and have developed a nice tool with the
  23.  * output, please mention that you developed it using PCCTS.  In
  24.  * addition, we ask that this header remain intact in our source code.
  25.  * As long as these guidelines are kept, we expect to continue enhancing
  26.  * this system and expect to make other tools available as they are
  27.  * completed.
  28.  *
  29.  * ANTLR 1.10
  30.  * Terence Parr
  31.  * Purdue University
  32.  * 1989-1993
  33.  */
  34. #include <stdio.h>
  35. #ifdef __cplusplus
  36. #ifndef __STDC__
  37. #define __STDC__
  38. #endif
  39. #endif
  40. #ifdef __STDC__
  41. #include <stdarg.h>
  42. #else
  43. #include <varargs.h>
  44. #endif
  45. #include "set.h"
  46. #include "syn.h"
  47. #include "hash.h"
  48. #include "generic.h"
  49. #include "dlgdef.h"
  50.  
  51. extern char tokens[];
  52.  
  53. /* ick! globals.  Used by permute() to track which elements of a set have been used */
  54. static int *findex;
  55. static set *fset;
  56. static unsigned **ftbl;
  57. static set *constrain; /* pts into fset. constrains tToken() to 'constrain' */
  58. int ConstrainSearch;
  59. static int maxk; /* set to initial k upon tree construction request */
  60. static Tree *FreeList = NULL;
  61.  
  62. #ifdef __STDC__
  63. Tree *tmake(Tree *root, ...);
  64. static int tmember_of_context(Tree *, Predicate *);
  65. #else
  66. Tree *tmake();
  67. static int tmember_of_context();
  68. #endif
  69.  
  70. /* Do root
  71.  * Then each sibling
  72.  */
  73. void
  74. #ifdef __STDC__
  75. preorder( Tree *tree )
  76. #else
  77. preorder( tree )
  78. Tree *tree;
  79. #endif
  80. {
  81.     if ( tree == NULL ) return;
  82.     if ( tree->down != NULL ) fprintf(stderr, " (");
  83.     if ( tree->token == ALT ) fprintf(stderr, " J");
  84.     else fprintf(stderr, " %s", TerminalString(tree->token));
  85.     if ( tree->token==EpToken ) fprintf(stderr, "(%d)", tree->v.rk);
  86.     preorder(tree->down);
  87.     if ( tree->down != NULL ) fprintf(stderr, " )");
  88.     preorder(tree->right);
  89. }
  90.  
  91. /* check the depth of each primary sibling to see that it is exactly
  92.  * k deep. e.g.;
  93.  *
  94.  *    ALT
  95.  *   |
  96.  *   A ------- B
  97.  *   |         |
  98.  *   C -- D    E
  99.  *
  100.  * Remove all branches <= k deep.
  101.  *
  102.  * Added by TJP 9-23-92 to correct the LL(k) constraint mechanism to work.
  103.  */
  104. Tree *
  105. #ifdef __STDC__
  106. prune( Tree *t, int k )
  107. #else
  108. prune( t, k )
  109. Tree *t;
  110. int k;
  111. #endif
  112. {
  113.     if ( t == NULL ) return NULL;
  114.     if ( t->token == ALT ) fatal("prune: ALT node in FIRST tree");
  115.     t->right = prune(t->right, k);
  116.     t->down = prune(t->down, k-1);
  117.     if ( t->down == NULL && k > 1 )
  118.     {
  119.         Tree *r = t->right;
  120.         t->right = NULL;
  121.         Tfree(t);
  122.         return r;
  123.     }
  124.     return t;
  125. }
  126.  
  127. /* build a tree (root child1 child2 ... NULL) */
  128. #ifdef __STDC__
  129. Tree *tmake(Tree *root, ...)
  130. #else
  131. Tree *tmake(va_alist)
  132. va_dcl
  133. #endif
  134. {
  135.     va_list ap;
  136.     Tree *child, *sibling=NULL, *tail;
  137. #ifndef __STDC__
  138.     Tree *root;
  139. #endif
  140. #ifdef __STDC__
  141.     require(root!=NULL, "tmake: NULL root impossible");
  142. #endif
  143.  
  144. #ifdef __STDC__
  145.     va_start(ap, root);
  146. #else
  147.     va_start(ap);
  148.     root = va_arg(ap, Tree *);
  149. #endif
  150.     child = va_arg(ap, Tree *);
  151.     while ( child != NULL )
  152.     {
  153.         if ( sibling == NULL ) sibling = tail = child;
  154.         else {tail->right = child; tail = child;}
  155.         child = va_arg(ap, Tree *);
  156.     }
  157.     root->down = sibling;
  158.     va_end(ap);
  159.     return root;
  160. }
  161.  
  162. Tree *
  163. #ifdef __STDC__
  164. tnode( int tok )
  165. #else
  166. tnode( tok )
  167. int tok;
  168. #endif
  169. {
  170.     Tree *p, *newblk;
  171.     static int n=0;
  172.     
  173.     if ( FreeList == NULL )
  174.     {
  175.         /*fprintf(stderr, "tnode: %d more nodes\n", TreeBlockAllocSize);*/
  176.         if ( TreeResourceLimit > 0 )
  177.         {
  178.             if ( (n+TreeBlockAllocSize) >= TreeResourceLimit )
  179.             {
  180.                 fprintf(stderr, ErrHdr, FileStr[CurAmbigfile], CurAmbigline);
  181.                 fprintf(stderr, " hit analysis resource limit while analyzing alts %d and %d %s\n",
  182.                                 CurAmbigAlt1,
  183.                                 CurAmbigAlt2,
  184.                                 CurAmbigbtype);
  185.                 exit(1);
  186.             }
  187.         }
  188.         newblk = (Tree *)calloc(TreeBlockAllocSize, sizeof(Tree));
  189.         if ( newblk == NULL )
  190.         {
  191.             fprintf(stderr, ErrHdr, FileStr[CurAmbigfile], CurAmbigline);
  192.             fprintf(stderr, " out of memory while analyzing alts %d and %d %s\n",
  193.                             CurAmbigAlt1,
  194.                             CurAmbigAlt2,
  195.                             CurAmbigbtype);
  196.             exit(1);
  197.         }
  198.         n += TreeBlockAllocSize;
  199.         for (p=newblk; p<&(newblk[TreeBlockAllocSize]); p++)
  200.         {
  201.             p->right = FreeList;    /* add all new Tree nodes to Free List */
  202.             FreeList = p;
  203.         }
  204.     }
  205.     p = FreeList;
  206.     FreeList = FreeList->right;        /* remove a tree node */
  207.     p->right = NULL;                /* zero out ptrs */
  208.     p->down = NULL;
  209.     p->token = tok;
  210.     return p;
  211. }
  212.  
  213. static Tree *
  214. #ifdef __STDC__
  215. eofnode( int k )
  216. #else
  217. eofnode( k )
  218. int k;
  219. #endif
  220. {
  221.     Tree *t=NULL;
  222.     int i;
  223.  
  224.     for (i=1; i<=k; i++)
  225.     {
  226.         t = tmake(tnode(EofToken), t, NULL);
  227.     }
  228.     return t;
  229. }
  230.  
  231.  
  232.  
  233. void
  234. #ifdef __STDC__
  235. _Tfree( Tree *t )
  236. #else
  237. _Tfree( t )
  238. Tree *t;
  239. #endif
  240. {
  241.     if ( t!=NULL )
  242.     {
  243.         t->right = FreeList;
  244.         FreeList = t;
  245.     }
  246. }
  247.  
  248. /* tree duplicate */
  249. Tree *
  250. #ifdef __STDC__
  251. tdup( Tree *t )
  252. #else
  253. tdup( t )
  254. Tree *t;
  255. #endif
  256. {
  257.     Tree *u;
  258.     
  259.     if ( t == NULL ) return NULL;
  260.     u = tnode(t->token);
  261.     u->v.rk = t->v.rk;
  262.     u->right = tdup(t->right);
  263.     u->down = tdup(t->down);
  264.     return u;
  265. }
  266.  
  267. /* tree duplicate (assume tree is a chain downwards) */
  268. Tree *
  269. #ifdef __STDC__
  270. tdup_chain( Tree *t )
  271. #else
  272. tdup_chain( t )
  273. Tree *t;
  274. #endif
  275. {
  276.     Tree *u;
  277.     
  278.     if ( t == NULL ) return NULL;
  279.     u = tnode(t->token);
  280.     u->v.rk = t->v.rk;
  281.     u->down = tdup(t->down);
  282.     return u;
  283. }
  284.  
  285. Tree *
  286. #ifdef __STDC__
  287. tappend( Tree *t, Tree *u )
  288. #else
  289. tappend( t, u )
  290. Tree *t;
  291. Tree *u;
  292. #endif
  293. {
  294.     Tree *w;
  295.  
  296.     /*fprintf(stderr, "tappend(");
  297.     preorder(t); fprintf(stderr, ",");
  298.     preorder(u); fprintf(stderr, " )\n");*/
  299.     if ( t == NULL ) return u;
  300.     if ( t->token == ALT && t->right == NULL ) return tappend(t->down, u);
  301.     for (w=t; w->right!=NULL; w=w->right) {;}
  302.     w->right = u;
  303.     return t;
  304. }
  305.  
  306. /* dealloc all nodes in a tree */
  307. void
  308. #ifdef __STDC__
  309. Tfree( Tree *t )
  310. #else
  311. Tfree( t )
  312. Tree *t;
  313. #endif
  314. {
  315.     if ( t == NULL ) return;
  316.     Tfree( t->down );
  317.     Tfree( t->right );
  318.     _Tfree( t );
  319. }
  320.  
  321. /* find all children (alts) of t that require remaining_k nodes to be LL_k
  322.  * tokens long.
  323.  *
  324.  * t-->o
  325.  *     |
  326.  *     a1--a2--...--an        <-- LL(1) tokens
  327.  *     |   |        |
  328.  *     b1  b2  ...  bn        <-- LL(2) tokens
  329.  *     |   |        |
  330.  *     .   .        .
  331.  *     .   .        .
  332.  *     z1  z2  ...  zn        <-- LL(LL_k) tokens
  333.  *
  334.  * We look for all [Ep] needing remaining_k nodes and replace with u.
  335.  * u is not destroyed or actually used by the tree (a copy is made).
  336.  */
  337. Tree *
  338. #ifdef __STDC__
  339. tlink( Tree *t, Tree *u, int remaining_k )
  340. #else
  341. tlink( t, u, remaining_k )
  342. Tree *t;
  343. Tree *u;
  344. int remaining_k;
  345. #endif
  346. {
  347.     Tree *p;
  348.     require(remaining_k!=0, "tlink: bad tree");
  349.  
  350.     if ( t==NULL ) return NULL;
  351.     /*fprintf(stderr, "tlink: u is:"); preorder(u); fprintf(stderr, "\n");*/
  352.     if ( t->token == EpToken && t->v.rk == remaining_k )
  353.     {
  354.         require(t->down==NULL, "tlink: invalid tree");
  355.         if ( u == NULL ) return t->right;
  356.         p = tdup( u );
  357.         p->right = t->right;
  358.         _Tfree( t );
  359.         return p;
  360.     }
  361.     t->down = tlink(t->down, u, remaining_k);
  362.     t->right = tlink(t->right, u, remaining_k);
  363.     return t;
  364. }
  365.  
  366. /* remove as many ALT nodes as possible while still maintaining semantics */
  367. Tree *
  368. #ifdef __STDC__
  369. tshrink( Tree *t )
  370. #else
  371. tshrink( t )
  372. Tree *t;
  373. #endif
  374. {
  375.     if ( t == NULL ) return NULL;
  376.     t->down = tshrink( t->down );
  377.     t->right = tshrink( t->right );
  378.     if ( t->down == NULL )
  379.     {
  380.         if ( t->token == ALT )
  381.         {
  382.             Tree *u = t->right;
  383.             _Tfree(t);
  384.             return u;            /* remove useless alts */
  385.         }
  386.         return t;
  387.     }
  388.  
  389.     /* (? (ALT (? ...)) s) ==> (? (? ...) s) where s = sibling, ? = match any */
  390.     if ( t->token == ALT && t->down->right == NULL)
  391.     {
  392.         Tree *u = t->down;
  393.         u->right = t->right;
  394.         _Tfree( t );
  395.         return u;
  396.     }
  397.     /* (? (A (ALT t)) s) ==> (? (A t) s) where A is a token; s,t siblings */
  398.     if ( t->token != ALT && t->down->token == ALT && t->down->right == NULL )
  399.     {
  400.         Tree *u = t->down->down;
  401.         _Tfree( t->down );
  402.         t->down = u;
  403.         return t;
  404.     }
  405.     return t;
  406. }
  407.  
  408. Tree *
  409. #ifdef __STDC__
  410. tflatten( Tree *t )
  411. #else
  412. tflatten( t )
  413. Tree *t;
  414. #endif
  415. {
  416.     if ( t == NULL ) return NULL;
  417.     t->down = tflatten( t->down );
  418.     t->right = tflatten( t->right );
  419.     if ( t->down == NULL ) return t;
  420.     
  421.     if ( t->token == ALT )
  422.     {
  423.         Tree *u;
  424.         /* find tail of children */
  425.         for (u=t->down; u->right!=NULL; u=u->right) {;}
  426.         u->right = t->right;
  427.         u = t->down;
  428.         _Tfree( t );
  429.         return u;
  430.     }
  431.     return t;
  432. }
  433.  
  434. Tree *
  435. #ifdef __STDC__
  436. tJunc( Junction *p, int k, set *rk )
  437. #else
  438. tJunc( p, k, rk )
  439. Junction *p;
  440. int k;
  441. set *rk;
  442. #endif
  443. {
  444.     Tree *t=NULL, *u=NULL;
  445.     Junction *alt;
  446.     Tree *tail, *r;
  447.  
  448. #ifdef DBG_TRAV
  449.     fprintf(stderr, "tJunc(%d): %s in rule %s\n", k,
  450.             decodeJType[p->jtype], ((Junction *)p)->rname);
  451. #endif
  452.     if ( p->jtype==aLoopBlk || p->jtype==RuleBlk ||
  453.          p->jtype==aPlusBlk || p->jtype==aSubBlk || p->jtype==aOptBlk )
  454.     {
  455.         if ( p->jtype!=aSubBlk && p->jtype!=aOptBlk ) {
  456.             require(p->lock!=NULL, "rJunc: lock array is NULL");
  457.             if ( p->lock[k] ) return NULL;
  458.             p->lock[k] = TRUE;
  459.         }
  460.         TRAV(p->p1, k, rk, tail);
  461.         if ( p->jtype==RuleBlk ) {p->lock[k] = FALSE; return tail;}
  462.         r = tmake(tnode(ALT), tail, NULL);
  463.         for (alt=(Junction *)p->p2; alt!=NULL; alt = (Junction *)alt->p2)
  464.         {
  465.             if ( tail==NULL ) {TRAV(alt->p1, k, rk, tail); r->down = tail;}
  466.             else
  467.             {
  468.                 TRAV(alt->p1, k, rk, tail->right);
  469.                 /* TJP -- lost info when tail->right was NULL
  470.                 tail = tail->right;*/
  471.                 if ( tail->right != NULL ) tail = tail->right;
  472.             }
  473.         }
  474.         if ( p->jtype!=aSubBlk && p->jtype!=aOptBlk ) p->lock[k] = FALSE;
  475. #ifdef DBG_TREES
  476.         fprintf(stderr, "blk(%s) returns:",((Junction *)p)->rname); preorder(r); fprintf(stderr, "\n");
  477. #endif
  478.         if ( r->down == NULL ) {_Tfree(r); return NULL;}
  479.         return r;
  480.     }
  481.  
  482.     if ( p->jtype==EndRule )
  483.     {
  484.         if ( p->halt )                        /* don't want FOLLOW here? */
  485.         {
  486.             set_orel(k, rk);                /* indicate this k value needed */
  487.             t = tnode(EpToken);
  488.             t->v.rk = k;
  489.             return t;
  490.         }
  491.         require(p->lock!=NULL, "rJunc: lock array is NULL");
  492.         if ( p->lock[k] ) return NULL;
  493.         /* if no FOLLOW assume k EOF's */
  494.         if ( p->p1 == NULL ) return eofnode(k);
  495.         p->lock[k] = TRUE;
  496.     }
  497.  
  498.     if ( p->p2 == NULL )
  499.     {
  500.         TRAV(p->p1, k, rk,t);
  501.         if ( p->jtype==EndRule ) p->lock[k]=FALSE;
  502.         return t;
  503.     }
  504.     TRAV(p->p1, k, rk, t);
  505.     if ( p->jtype!=RuleBlk ) TRAV(p->p2, k, rk, u);
  506.     if ( p->jtype==EndRule ) p->lock[k] = FALSE;/* unlock node */
  507.  
  508.     if ( t==NULL ) return tmake(tnode(ALT), u, NULL);
  509.     return tmake(tnode(ALT), t, u, NULL);
  510. }
  511.  
  512. Tree *
  513. #ifdef __STDC__
  514. tRuleRef( RuleRefNode *p, int k, set *rk_out )
  515. #else
  516. tRuleRef( p, k, rk_out )
  517. RuleRefNode *p;
  518. int k;
  519. set *rk_out;
  520. #endif
  521. { 
  522.     int k2;
  523.     Tree *t, *u;
  524.     Junction *r;
  525.     set rk, rk2;
  526.     int save_halt;
  527.     RuleEntry *q = (RuleEntry *) hash_get(Rname, p->text);
  528.     
  529. #ifdef DBG_TRAV
  530.     fprintf(stderr, "tRuleRef: %s\n", p->text);
  531. #endif
  532.     if ( q == NULL )
  533.     {
  534.         TRAV(p->next, k, rk_out, t);/* ignore undefined rules */
  535.         return t;
  536.     }
  537.     rk = rk2 = empty;
  538.     r = RulePtr[q->rulenum];
  539.     if ( r->lock[k] ) return NULL;
  540.     save_halt = r->end->halt;
  541.     r->end->halt = TRUE;        /* don't let reach fall off end of rule here */
  542.     TRAV(r, k, &rk, t);
  543.     r->end->halt = save_halt;
  544. #ifdef DBG_TREES
  545.     fprintf(stderr, "after ruleref, t is:"); preorder(t); fprintf(stderr, "\n");
  546. #endif
  547.     t = tshrink( t );
  548.     while ( !set_nil(rk) ) {    /* any k left to do? if so, link onto tree */
  549.         k2 = set_int(rk);
  550.         set_rm(k2, rk);
  551.         TRAV(p->next, k2, &rk2, u);
  552.         t = tlink(t, u, k2);    /* any alts missing k2 toks, add u onto end */
  553.     }
  554.     set_free(rk);                /* rk is empty, but free it's memory */
  555.     set_orin(rk_out, rk2);        /* remember what we couldn't do */
  556.     set_free(rk2);
  557.     return t;
  558. }
  559.  
  560. Tree *
  561. #ifdef __STDC__
  562. tToken( TokNode *p, int k, set *rk )
  563. #else
  564. tToken( p, k, rk )
  565. TokNode *p;
  566. int k;
  567. set *rk;
  568. #endif
  569. {
  570.     Tree *t;
  571.  
  572.     if ( ConstrainSearch )
  573.     {
  574.         require(constrain>=fset&&constrain<=&(fset[LL_k]),"tToken: constrain is not a valid set");
  575.         constrain = &fset[maxk-k+1];
  576.     }
  577.  
  578. #ifdef DBG_TRAV
  579.     fprintf(stderr, "tToken(%d): %s\n", k, TerminalString(p->token));
  580.     if ( ConstrainSearch ) {
  581.         fprintf(stderr, "constrain is:"); s_fprT(stderr, *constrain); fprintf(stderr, "\n");
  582.     }
  583. #endif
  584.     if ( ConstrainSearch )
  585.         if ( !set_el(p->token, *constrain) )
  586.         {
  587. /*            fprintf(stderr, "ignoring token %s(%d)\n", TerminalString(p->token),
  588.                             k);*/
  589.             return NULL;
  590.         }
  591.     if ( k == 1 ) return tnode(p->token);
  592.     TRAV(p->next, k-1, rk, t);
  593.     /* here, we are positive that, at least, this tree will not contribute
  594.      * to the LL(2) tree since it will be too shallow, IF t==NULL
  595.      */
  596.     if ( t == NULL )    /* tree will be too shallow */
  597.     {
  598.         return NULL;
  599.     }
  600. #ifdef DBG_TREES
  601.     fprintf(stderr, "tToken(%d)->next:",k); preorder(t); fprintf(stderr, "\n");
  602. #endif
  603.     return tmake(tnode(p->token), t, NULL);
  604. }
  605.  
  606. Tree *
  607. #ifdef __STDC__
  608. tAction( ActionNode *p, int k, set *rk )
  609. #else
  610. tAction( p, k, rk )
  611. ActionNode *p;
  612. int k;
  613. set *rk;
  614. #endif
  615. {
  616.     Tree *t;
  617.     
  618.     /*fprintf(stderr, "tAction\n");*/
  619.     TRAV(p->next, k, rk, t);
  620.     return t;
  621. }
  622.  
  623. /* see if e exists in s as a possible input permutation (e is always a chain) */
  624. int
  625. #ifdef __STDC__
  626. tmember( Tree *e, Tree *s )
  627. #else
  628. tmember( e, s )
  629. Tree *e;
  630. Tree *s;
  631. #endif
  632. {
  633.     if ( e==NULL||s==NULL ) return 0;
  634.     /*fprintf(stderr, "tmember(");
  635.     preorder(e); fprintf(stderr, ",");
  636.     preorder(s); fprintf(stderr, " )\n");*/
  637.     if ( s->token == ALT && s->right == NULL ) return tmember(e, s->down);
  638.     if ( e->token!=s->token )
  639.     {
  640.         if ( s->right==NULL ) return 0;
  641.         return tmember(e, s->right);
  642.     }
  643.     if ( e->down==NULL && s->down == NULL ) return 1;
  644.     if ( tmember(e->down, s->down) ) return 1;
  645.     if ( s->right==NULL ) return 0;
  646.     return tmember(e, s->right);
  647. }
  648.  
  649. /* combine (? (A t) ... (A u) ...) into (? (A t u)) */
  650. Tree *
  651. #ifdef __STDC__
  652. tleft_factor( Tree *t )
  653. #else
  654. tleft_factor( t )
  655. Tree *t;
  656. #endif
  657. {
  658.     Tree *u, *v, *trail, *w;
  659.  
  660.     /* left-factor what is at this level */
  661.     if ( t == NULL ) return NULL;
  662.     for (u=t; u!=NULL; u=u->right)
  663.     {
  664.         trail = u;
  665.         v=u->right;
  666.         while ( v!=NULL )
  667.         {
  668.             if ( u->token == v->token )
  669.             {
  670.                 if ( u->down!=NULL )
  671.                 {
  672.                     for (w=u->down; w->right!=NULL; w=w->right) {;}
  673.                     w->right = v->down;    /* link children together */
  674.                 }
  675.                 else u->down = v->down;
  676.                 trail->right = v->right;        /* unlink factored node */
  677.                 _Tfree( v );
  678.                 v = trail->right;
  679.             }
  680.             else {trail = v; v=v->right;}
  681.         }
  682.     }
  683.     /* left-factor what is below */
  684.     for (u=t; u!=NULL; u=u->right) u->down = tleft_factor( u->down );
  685.     return t;
  686. }
  687.  
  688. /* remove the permutation p from t if present */
  689. Tree *
  690. #ifdef __STDC__
  691. trm_perm( Tree *t, Tree *p )
  692. #else
  693. trm_perm( t, p )
  694. Tree *t;
  695. Tree *p;
  696. #endif
  697. {
  698.     /*
  699.     fprintf(stderr, "trm_perm(");
  700.     preorder(t); fprintf(stderr, ",");
  701.     preorder(p); fprintf(stderr, " )\n");
  702.     */
  703.     if ( t == NULL || p == NULL ) return NULL;
  704.     if ( t->token == ALT )
  705.     {
  706.         t->down = trm_perm(t->down, p);
  707.         if ( t->down == NULL )                 /* nothing left below, rm cur node */
  708.         {
  709.             Tree *u = t->right;
  710.             _Tfree( t );
  711.             return trm_perm(u, p);
  712.         }
  713.         t->right = trm_perm(t->right, p);    /* look for more instances of p */
  714.         return t;
  715.     }
  716.     if ( p->token != t->token )                /* not found, try a sibling */
  717.     {
  718.         t->right = trm_perm(t->right, p);
  719.         return t;
  720.     }
  721.     t->down = trm_perm(t->down, p->down);
  722.     if ( t->down == NULL )                     /* nothing left below, rm cur node */
  723.     {
  724.         Tree *u = t->right;
  725.         _Tfree( t );
  726.         return trm_perm(u, p);
  727.     }
  728.     t->right = trm_perm(t->right, p);        /* look for more instances of p */
  729.     return t;
  730. }
  731.  
  732. /* add the permutation 'perm' to the LL_k sets in 'fset' */
  733. void
  734. #ifdef __STDC__
  735. tcvt( set *fset, Tree *perm )
  736. #else
  737. tcvt( fset, perm )
  738. set *fset;
  739. Tree *perm;
  740. #endif
  741. {
  742.     if ( perm==NULL ) return;
  743.     set_orel(perm->token, fset);
  744.     tcvt(fset+1, perm->down);
  745. }
  746.  
  747. /* for each element of ftbl[k], make it the root of a tree with permute(ftbl[k+1])
  748.  * as a child.
  749.  */
  750. Tree *
  751. #ifdef __STDC__
  752. permute( int k )
  753. #else
  754. permute( k )
  755. int k;
  756. #endif
  757. {
  758.     Tree *t, *u;
  759.     
  760.     if ( k>LL_k ) return NULL;
  761.     if ( ftbl[k][findex[k]] == nil ) return NULL;
  762.     t = permute(k+1);
  763.     if ( t==NULL&&k<LL_k )        /* no permutation left below for k+1 tokens? */
  764.     {
  765.         findex[k+1] = 0;
  766.         (findex[k])++;            /* try next token at this k */
  767.         return permute(k);
  768.     }
  769.     
  770.     u = tmake(tnode(ftbl[k][findex[k]]), t, NULL);
  771.     if ( k == LL_k ) (findex[k])++;
  772.     return u;
  773. }
  774.  
  775. /* Compute LL(k) trees for alts alt1 and alt2 of p.
  776.  * function result is tree of ambiguous input permutations
  777.  *
  778.  * ALGORITHM may change to look for something other than LL_k size
  779.  * trees ==> maxk will have to change.
  780.  */
  781. Tree *
  782. #ifdef __STDC__
  783. VerifyAmbig( Junction *alt1, Junction *alt2, unsigned **ft, set *fs, Tree **t, Tree **u, int *numAmbig )
  784. #else
  785. VerifyAmbig( alt1, alt2, ft, fs, t, u, numAmbig )
  786. Junction *alt1;
  787. Junction *alt2;
  788. unsigned **ft;
  789. set *fs;
  790. Tree **t;
  791. Tree **u;
  792. int *numAmbig;
  793. #endif
  794. {
  795.     set rk;
  796.     Tree *perm, *ambig=NULL;
  797.     Junction *p;
  798.     int k;
  799.  
  800.     maxk = LL_k;                /* NOTE: for now, we look for LL_k */
  801.     ftbl = ft;
  802.     fset = fs;
  803.     constrain = &(fset[1]);
  804.     findex = (int *) calloc(LL_k+1, sizeof(int));
  805.     if ( findex == NULL )
  806.     {
  807.         fprintf(stderr, ErrHdr, CurAmbigfile, CurAmbigline);
  808.         fprintf(stderr, " out of memory while analyzing alts %d and %d of %s\n",
  809.                         CurAmbigAlt1,
  810.                         CurAmbigAlt2,
  811.                         CurAmbigbtype);
  812.         exit(1);
  813.     }
  814.     for (k=1; k<=LL_k; k++) findex[k] = 0;
  815.  
  816.     rk = empty;
  817.     ConstrainSearch = 1;    /* consider only tokens in ambig sets */
  818.  
  819.     p = analysis_point((Junction *)alt1->p1);
  820.     TRAV(p, LL_k, &rk, *t);
  821.     *t = tshrink( *t );
  822.     *t = tflatten( *t );
  823.     *t = prune(*t, LL_k);
  824.     *t = tleft_factor( *t );
  825. /*    fprintf(stderr, "after shrink&flatten&prune&left_factor:"); preorder(*t); fprintf(stderr, "\n");*/
  826.     if ( *t == NULL )
  827.     {
  828. /*        fprintf(stderr, "TreeIncomplete --> no LL(%d) ambiguity\n", LL_k);*/
  829.         Tfree( *t );    /* kill if impossible to have ambig */
  830.         *t = NULL;
  831.     }
  832.  
  833.     p = analysis_point((Junction *)alt2->p1);
  834.     TRAV(p, LL_k, &rk, *u);
  835.     *u = tshrink( *u );
  836.     *u = tflatten( *u );
  837.     *u = prune(*u, LL_k);
  838.     *u = tleft_factor( *u );
  839. /*    fprintf(stderr, "after shrink&flatten&prune&lfactor:"); preorder(*u); fprintf(stderr, "\n");*/
  840.     if ( *u == NULL )
  841.     {
  842. /*        fprintf(stderr, "TreeIncomplete --> no LL(%d) ambiguity\n", LL_k);*/
  843.         Tfree( *u );
  844.         *u = NULL;
  845.     }
  846.  
  847.     for (k=1; k<=LL_k; k++) set_clr( fs[k] );
  848.  
  849.     ambig = tnode(ALT);
  850.     k = 0;
  851.     if ( *t!=NULL && *u!=NULL )
  852.     {
  853.         while ( (perm=permute(1))!=NULL )
  854.         {
  855. /*            fprintf(stderr, "chk perm:"); preorder(perm); fprintf(stderr, "\n");*/
  856.             if ( tmember(perm, *t) && tmember(perm, *u) )
  857.             {
  858. /*                fprintf(stderr, "ambig upon"); preorder(perm); fprintf(stderr, "\n");*/
  859.                 k++;
  860.                 perm->right = ambig->down;
  861.                 ambig->down = perm;
  862.                 tcvt(&(fs[1]), perm);
  863.             }
  864.             else Tfree( perm );
  865.         }
  866.     }
  867.  
  868.     *numAmbig = k;
  869.     if ( ambig->down == NULL ) {_Tfree(ambig); ambig = NULL;}
  870.     free( findex );
  871.     /*fprintf(stderr, "final ambig:"); preorder(ambig); fprintf(stderr, "\n");*/
  872.     return ambig;
  873. }
  874.  
  875. static Tree *
  876. #ifdef __STDC__
  877. bottom_of_chain( Tree *t )
  878. #else
  879. bottom_of_chain( t )
  880. Tree *t;
  881. #endif
  882. {
  883.     if ( t==NULL ) return NULL;
  884.     for (; t->down != NULL; t=t->down) {;}
  885.     return t;
  886. }
  887.  
  888. /*
  889.  * Make a tree from k sets where the degree of the first k-1 sets is 1.
  890.  */
  891. Tree *
  892. #ifdef __STDC__
  893. make_tree_from_sets( set *fset1, set *fset2 )
  894. #else
  895. make_tree_from_sets( fset1, fset2 )
  896. set *fset1;
  897. set *fset2;
  898. #endif
  899. {
  900.     set inter;
  901.     int i;
  902.     Tree *t=NULL, *n, *u;
  903.     unsigned *p,*q;
  904.     require(LL_k>1, "make_tree_from_sets: LL_k must be > 1");
  905.  
  906.     /* do the degree 1 sets first */
  907.     for (i=1; i<=LL_k-1; i++)
  908.     {
  909.         inter = set_and(fset1[i], fset2[i]);
  910.         require(set_deg(inter)==1, "invalid set to tree conversion");
  911.         n = tnode(set_int(inter));
  912.         if (t==NULL) t=n; else tmake(t, n, NULL);
  913.         set_free(inter);
  914.     }
  915.  
  916.     /* now add the chain of tokens at depth k */
  917.     u = bottom_of_chain(t);
  918.     inter = set_and(fset1[LL_k], fset2[LL_k]);
  919.     if ( (q=p=set_pdq(inter)) == NULL ) fatal("Can't alloc space for set_pdq");
  920.     /* first one is linked to bottom, then others are sibling linked */
  921.     n = tnode(*p++);
  922.     u->down = n;
  923.     u = u->down;
  924.     while ( *p != nil )
  925.     {
  926.         n = tnode(*p);
  927.         u->right = n;
  928.         u = u->right;
  929.         p++;
  930.     }
  931.     free(q);
  932.  
  933.     return t;
  934. }
  935.  
  936. /* create and return the tree of lookahead k-sequences that are in t, but not
  937.  * in the context of predicates in predicate list p.
  938.  */
  939. Tree *
  940. #ifdef __STDC__
  941. tdif( Tree *t, Predicate *p, set *fset1, set *fset2 )
  942. #else
  943. tdif( t, p, fset1, fset2 )
  944. Tree *t;
  945. Predicate *p;
  946. set *fset1;
  947. set *fset2;
  948. #endif
  949. {
  950.     unsigned **ft;
  951.     Tree *dif=NULL, *last=NULL;
  952.     Tree *perm;
  953.     set b;
  954.     int i,k;
  955.  
  956.     if ( p == NULL ) return tdup(t);
  957.  
  958.     ft = (unsigned **) calloc(CLL_k+1, sizeof(unsigned *));
  959.     require(ft!=NULL, "cannot allocate ft");
  960.     for (i=1; i<=CLL_k; i++)
  961.     {
  962.         b = set_and(fset1[i], fset2[i]);
  963.         ft[i] = set_pdq(b);
  964.         set_free(b);
  965.     }
  966.     findex = (int *) calloc(LL_k+1, sizeof(int));
  967.     if ( findex == NULL )
  968.     {
  969.         fatal("out of memory in tdif while checking predicates");
  970.     }
  971.     for (k=1; k<=LL_k; k++) findex[k] = 0;
  972.  
  973. /*    fprintf(stderr, "tdif[");
  974.     preorder(t);
  975.     fprintf(stderr, ",");
  976.     preorder(p->tcontext);
  977.     fprintf(stderr, "] =");*/
  978.  
  979.     ftbl = ft;
  980.     while ( (perm=permute(1))!=NULL )
  981.     {
  982. /*        fprintf(stderr, "test perm:"); preorder(perm); fprintf(stderr, "\n");*/
  983.         if ( tmember(perm, t) && !tmember_of_context(perm, p) )
  984.         {
  985. /*            fprintf(stderr, "satisfied upon"); preorder(perm); fprintf(stderr, "\n");*/
  986.             k++;
  987.             if ( dif==NULL ) dif = perm;
  988.             else
  989.             {
  990.                 perm->right = dif;
  991.                 dif = perm;
  992.             }
  993.         }
  994.         else Tfree( perm );
  995.     }
  996.  
  997. /*    preorder(dif);
  998.     fprintf(stderr, "\n");*/
  999.  
  1000.     for (i=1; i<=CLL_k; i++) free( ft[i] );
  1001.     free(ft);
  1002.     free(findex);
  1003.  
  1004.     return dif;
  1005. }
  1006.  
  1007. /* is lookahead sequence t a member of any context tree for any predicate in p? */
  1008. static int
  1009. #ifdef __STDC__
  1010. tmember_of_context( Tree *t, Predicate *p )
  1011. #else
  1012. tmember_of_context( t, p )
  1013. Tree *t;
  1014. Predicate *p;
  1015. #endif
  1016. {
  1017.     for (; p!=NULL; p=p->next)
  1018.     {
  1019.         if ( tmember(t, p->tcontext) ) return 1;
  1020.     }
  1021.     return 0;
  1022. }
  1023.