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