home *** CD-ROM | disk | FTP | other *** search
/ OS/2 Shareware BBS: 10 Tools / 10-Tools.zip / pccts.zip / pccts / antlr / fset.c < prev    next >
C/C++ Source or Header  |  1994-03-31  |  26KB  |  907 lines
  1. /*
  2.  * fset.c
  3.  *
  4.  * $Id: fset.c,v 1.6 1994/03/25 19:40:05 parrt Exp parrt $
  5.  * $Revision: 1.6 $
  6.  *
  7.  * Compute FIRST and FOLLOW sets.
  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. #include "set.h"
  42. #include "syn.h"
  43. #include "hash.h"
  44. #include "generic.h"
  45. #include "dlgdef.h"
  46.  
  47. #ifdef __STDC__
  48. static void ensure_predicates_cover_ambiguous_lookahead_sequences(Junction *, Junction *, char *, Tree *);
  49. #else
  50. static void ensure_predicates_cover_ambiguous_lookahead_sequences();
  51. #endif
  52.  
  53. /*
  54.  * What tokens are k tokens away from junction q?
  55.  *
  56.  * Follow both p1 and p2 paths (unless RuleBlk) to collect the tokens k away from this
  57.  * node.
  58.  * We lock the junction according to k--the lookahead.  If we have been at this
  59.  * junction before looking for the same, k, number of lookahead tokens, we will
  60.  * do it again and again...until we blow up the stack.  Locks are only used on aLoopBlk,
  61.  * RuleBlk, aPlusBlk and EndRule junctions to remove/detect infinite recursion from
  62.  * FIRST and FOLLOW calcs.
  63.  *
  64.  * If p->jtype == EndRule we are going to attempt a FOLLOW.  (FOLLOWs are really defined
  65.  * in terms of FIRST's, however).  To proceed with the FOLLOW, p->halt cannot be
  66.  * set.  p->halt is set to indicate that a reference to the current rule is in progress
  67.  * and the FOLLOW is not desirable.
  68.  *
  69.  * If we attempt a FOLLOW and find that there is no FOLLOW or REACHing beyond the EndRule
  70.  * junction yields an empty set, replace the empty set with EOF.  No FOLLOW means that
  71.  * only EOF can follow the current rule.  This normally occurs only on the start symbol
  72.  * since all other rules are referenced by another rule somewhere.
  73.  *
  74.  * Normally, both p1 and p2 are followed.  However, checking p2 on a RuleBlk node is
  75.  * the same as checking the next rule which is clearly incorrect.
  76.  *
  77.  * Cycles in the FOLLOW sense are possible.  e.g. Fo(c) requires Fo(b) which requires
  78.  * Fo(c).  Both Fo(b) and Fo(c) are defined to be Fo(b) union Fo(c).  Let's say
  79.  * Fo(c) is attempted first.  It finds all of the FOLLOW symbols and then attempts
  80.  * to do Fo(b) which finds of its FOLLOW symbols.  So, we have:
  81.  *
  82.  *                  Fo(c)
  83.  *                 /     \
  84.  *              a set    Fo(b)
  85.  *                      /     \
  86.  *                   a set    Fo(c) .....Hmmmm..... Infinite recursion!
  87.  *
  88.  * The 2nd Fo(c) is not attempted and Fo(b) is left deficient, but Fo(c) is now
  89.  * correctly Fo(c) union Fo(b).  We wish to pick up where we left off, so the fact
  90.  * that Fo(b) terminated early means that we lack Fo(c) in the Fo(b) set already
  91.  * laying around.  SOOOOoooo, we track FOLLOW cycles.  All FOLLOW computations are
  92.  * cached in a hash table.  After the sequence of FOLLOWs finish, we reconcile all
  93.  * cycles --> correct all Fo(rule) sets in the cache.
  94.  *
  95.  * Confused? Good! Read my MS thesis [Purdue Technical Report TR90-30].
  96.  * TJP 8/93 -- can now read PhD thesis from Purdue.
  97.  *
  98.  * Also, FIRST sets are cached in the hash table.  Keys are (rulename,Fi/Fo,k).
  99.  * Only FIRST sets, for which the FOLLOW is not included, are stored.
  100.  *
  101.  * SPECIAL CASE of (...)+ blocks:
  102.  * I added an optional alt so that the alts could see what
  103.  * was behind the (...)+ block--thus using enough lookahead
  104.  * to branch out rather than just enough to distinguish
  105.  * between alts in the (...)+.  However, when the FIRST("(...)+") is
  106.  * is needed, must not use this last "optional" alt.  This routine
  107.  * turns off this path by setting a new 'ignore' flag for
  108.  * the alt and then resetting it afterwards.
  109.  */
  110. set
  111. #ifdef __STDC__
  112. rJunc( Junction *p, int k, set *rk )
  113. #else
  114. rJunc( p, k, rk )
  115. Junction *p;
  116. int k;
  117. set *rk;
  118. #endif
  119. {
  120.     set a, b;
  121.     require(p!=NULL,                "rJunc: NULL node");
  122.     require(p->ntype==nJunction,    "rJunc: not junction");
  123.  
  124. #ifdef DBG_LL1
  125.     if ( p->jtype == RuleBlk ) fprintf(stderr, "FIRST(%s,%d) \n",((Junction *)p)->rname,k);
  126.     else fprintf(stderr, "rJunc: %s in rule %s\n",
  127.             decodeJType[p->jtype], ((Junction *)p)->rname);
  128. #endif
  129.     /* if this is one of the added optional alts for (...)+ then return */
  130.     if ( p->ignore ) return empty;
  131.  
  132.     /* locks are valid for aLoopBlk,aPlusBlk,RuleBlk,EndRule junctions only */
  133.     if ( p->jtype==aLoopBlk || p->jtype==RuleBlk ||
  134.          p->jtype==aPlusBlk || p->jtype==EndRule ) 
  135.     {
  136.         require(p->lock!=NULL, "rJunc: lock array is NULL");
  137.         if ( p->lock[k] )
  138.         {
  139.             if ( p->jtype == EndRule )    /* FOLLOW cycle? */
  140.             {
  141.                 /*fprintf(stderr, "FOLLOW cycle to %s: panic!\n", p->rname);*/
  142.                 RegisterCycle(p->rname, k);
  143.             }
  144.             return empty;
  145.         }
  146.         if ( p->jtype == RuleBlk && p->end->halt )    /* check for FIRST cache */
  147.         {
  148.             CacheEntry *q = (CacheEntry *) hash_get(Fcache, Fkey(p->rname,'i',k));
  149.             if ( q != NULL )
  150.             {
  151.                 set_orin(rk, q->rk);
  152.                 return set_dup( q->fset );
  153.             }
  154.         }
  155.         if ( p->jtype == EndRule )        /* FOLLOW set cached already? */
  156.         {
  157.             CacheEntry *q = (CacheEntry *) hash_get(Fcache, Fkey(p->rname,'o',k));
  158.             if ( q != NULL )
  159.             {
  160.                 /*fprintf(stderr, "<->FOLLOW(%s,%d):", p->rname,k);
  161.                 s_fprT(stderr, q->fset);
  162.                 if ( q->incomplete ) fprintf(stderr, " (incomplete)");
  163.                 fprintf(stderr, "\n");
  164.                 */
  165.                 if ( !q->incomplete )
  166.                 {
  167.                     return set_dup( q->fset );
  168.                 }
  169.             }
  170.         }
  171.         p->lock[k] = TRUE;    /* This rule is busy */
  172.     }
  173.  
  174.     a = b = empty;
  175.  
  176.     if ( p->jtype == EndRule )
  177.     {
  178.         if ( p->halt )                                /* don't want FOLLOW here? */
  179.         {
  180.             p->lock[k] = FALSE;
  181.             set_orel(k, rk);                        /* indicate this k value needed */
  182.             return empty;
  183.         }
  184.         FoPush(p->rname, k);                        /* Attempting FOLLOW */
  185.         if ( p->p1 == NULL ) set_orel((TokenInd!=NULL?TokenInd[EofToken]:EofToken), &a);/* if no FOLLOW assume EOF */
  186.         /*fprintf(stderr, "-->FOLLOW(%s,%d)\n", p->rname,k);*/
  187.     }
  188.  
  189.     if ( p->p1 != NULL ) REACH(p->p1, k, rk, a);
  190.     
  191.     /* C a c h e  R e s u l t s */
  192.     if ( p->jtype == RuleBlk && p->end->halt )        /* can save FIRST set? */
  193.     {
  194.         CacheEntry *q = newCacheEntry( Fkey(p->rname,'i',k) );
  195.         /*fprintf(stderr, "Caching %s FIRST %d\n", p->rname, k);*/
  196.         hash_add(Fcache, Fkey(p->rname,'i',k), (Entry *)q);
  197.         q->fset = set_dup( a );
  198.         q->rk = set_dup( *rk );
  199.     }
  200.  
  201.     if ( p->jtype == EndRule )                        /* just completed FOLLOW? */
  202.     {
  203.         /* Cache Follow set */
  204.         CacheEntry *q = (CacheEntry *) hash_get(Fcache, Fkey(p->rname,'o',k));
  205.         if ( q==NULL )
  206.         {
  207.             q = newCacheEntry( Fkey(p->rname,'o',k) );
  208.             hash_add(Fcache, Fkey(p->rname,'o',k), (Entry *)q);
  209.         }
  210.         /*fprintf(stderr, "Caching %s FOLLOW %d\n", p->rname, k);*/
  211.         set_orin(&(q->fset), a);
  212.         FoPop( k );
  213.         if ( FoTOS[k] == NULL && Cycles[k] != NULL ) ResolveFoCycles(k);
  214.         /*
  215.         fprintf(stderr, "<--FOLLOW(%s,%d):", p->rname, k);
  216.         s_fprT(stderr, q->fset);
  217.         if ( q->incomplete ) fprintf(stderr, " (incomplete)");
  218.         fprintf(stderr, "\n");
  219.         */
  220.     }
  221.     
  222.     if ( p->jtype != RuleBlk && p->p2 != NULL ) REACH(p->p2, k, rk, b);
  223.     if ( p->jtype==aLoopBlk || p->jtype==RuleBlk ||
  224.          p->jtype==aPlusBlk || p->jtype==EndRule ) 
  225.         p->lock[k] = FALSE;                            /* unlock node */
  226.  
  227.     set_orin(&a, b);
  228.     set_free(b);
  229.     return a;
  230. }
  231.  
  232. set
  233. #ifdef __STDC__
  234. rRuleRef( RuleRefNode *p, int k, set *rk_out )
  235. #else
  236. rRuleRef( p, k, rk_out )
  237. RuleRefNode *p;
  238. int k;
  239. set *rk_out;
  240. #endif
  241. {
  242.     set rk;
  243.     Junction *r;
  244.     int k2;
  245.     set a, rk2, b;
  246.     int save_halt;
  247.     RuleEntry *q = (RuleEntry *) hash_get(Rname, p->text);
  248.     require(p!=NULL,            "rRuleRef: NULL node");
  249.     require(p->ntype==nRuleRef,    "rRuleRef: not rule ref");
  250.  
  251. #ifdef DBG_LL1
  252.     fprintf(stderr, "rRuleRef: %s\n", p->text);
  253. #endif
  254.     if ( q == NULL )
  255.     {
  256.         warnFL( eMsg1("rule %s not defined",p->text), FileStr[p->file], p->line );
  257.         REACH(p->next, k, rk_out, a);
  258.         return a;
  259.     }
  260.     rk2 = empty;
  261.     r = RulePtr[q->rulenum];
  262.     if ( r->lock[k] )
  263.     {
  264.         errNoFL( eMsg2("infinite left-recursion to rule %s from rule %s",
  265.                         r->rname, p->rname) );
  266.         return empty;
  267.     }
  268.     save_halt = r->end->halt;
  269.     r->end->halt = TRUE;        /* don't let reach fall off end of rule here */
  270.     rk = empty;
  271.     REACH(r, k, &rk, a);
  272.     r->end->halt = save_halt;
  273.     while ( !set_nil(rk) ) {
  274.         k2 = set_int(rk);
  275.         set_rm(k2, rk);
  276.         REACH(p->next, k2, &rk2, b);
  277.         set_orin(&a, b);
  278.         set_free(b);
  279.     }
  280.     set_free(rk);                /* this has no members, but free it's memory */
  281.     set_orin(rk_out, rk2);        /* remember what we couldn't do */
  282.     set_free(rk2);
  283.     return a;
  284. }
  285.  
  286. /*
  287.  * Return FIRST sub k ( token_node )
  288.  *
  289.  * TJP 10/11/93 modified this so that token nodes that are actually
  290.  * ranges (T1..T2) work.
  291.  */
  292. set
  293. #ifdef __STDC__
  294. rToken( TokNode *p, int k, set *rk )
  295. #else
  296. rToken( p, k, rk )
  297. TokNode *p;
  298. int k;
  299. set *rk;
  300. #endif
  301. {
  302.     set a;
  303.     require(p!=NULL,            "rToken: NULL node");
  304.     require(p->ntype==nToken,    "rToken: not token node");
  305.  
  306. #ifdef DBG_LL1
  307.     fprintf(stderr, "rToken: %s\n", (TokenString(p->token)!=NULL)?TokenString(p->token):
  308.                                     ExprString(p->token));
  309. #endif
  310.     if ( k-1 == 0 )
  311.     {
  312.         if ( !set_nil(p->tset) ) return set_dup(p->tset);
  313.         return set_of(p->token);
  314.     }
  315.     REACH(p->next, k-1, rk, a);
  316.     
  317.     return a;
  318. }
  319.  
  320. set
  321. #ifdef __STDC__
  322. rAction( ActionNode *p, int k, set *rk )
  323. #else
  324. rAction( p, k, rk )
  325. ActionNode *p;
  326. int k;
  327. set *rk;
  328. #endif
  329. {
  330.     set a;
  331.     require(p!=NULL,            "rJunc: NULL node");
  332.     require(p->ntype==nAction,    "rJunc: not action");
  333.     
  334.     REACH(p->next, k, rk, a);    /* ignore actions */
  335.     return a;
  336. }
  337.  
  338.                 /* A m b i g u i t y  R e s o l u t i o n */
  339.  
  340.  
  341. void
  342. #ifdef __STDC__
  343. dumpAmbigMsg( set *fset, FILE *f, int want_nls )
  344. #else
  345. dumpAmbigMsg( fset, f, want_nls )
  346. set *fset;
  347. FILE *f;
  348. int want_nls;
  349. #endif
  350. {
  351.     int i;
  352.  
  353.     if ( want_nls ) fprintf(f, "\n\t");
  354.     else fprintf(f, " ");
  355.     for (i=1; i<=CLL_k; i++)
  356.     {
  357.         if ( i>1 )
  358.         {
  359.             if ( !want_nls ) fprintf(f, ", ");
  360.         }
  361.         if ( set_deg(fset[i]) > 3 && elevel == 1 )
  362.         {
  363.             int e,m;
  364.             fprintf(f, "{");
  365.             for (m=1; m<=3; m++)
  366.             {
  367.                 e=set_int(fset[i]);
  368.                 fprintf(f, " %s", TerminalString(e));
  369.                 set_rm(e, fset[i]);
  370.             }
  371.             fprintf(f, " ... }");
  372.         }
  373.         else s_fprT(f, fset[i]);
  374.         if ( want_nls ) fprintf(f, "\n\t");
  375.     }
  376.     fprintf(f, "\n");
  377. }
  378.  
  379. /*
  380.  * If delta is the set of ambiguous lookahead sequences, then make sure that
  381.  * the predicate(s) for productions alt1,alt2 cover the sequences in delta.
  382.  *
  383.  * For example,
  384.  *    a : <<PRED1>>? (A B|A C)
  385.  *      | b
  386.  *    ;
  387.  *    b : <<PRED2>>? A B
  388.  *      | A C
  389.  *      ;
  390.  *
  391.  * This should give a warning that (A C) predicts both productions and alt2
  392.  * does not have a predicate in the production that generates (A C).
  393.  *
  394.  * The warning detection is simple.  Let delta = LOOK(alt1) intersection LOOK(alt2).
  395.  * Now, if ( delta set-difference context(predicates-for-alt1) != empty then
  396.  * alt1 does not "cover" all ambiguous sequences.
  397.  *
  398.  * If ambig is nonempty, then ambig in LL(k) sense -> use tree info; else use fset
  399.  * info.  Actually, sets are used only if k=1 for this grammar.
  400.  */
  401. static void
  402. #ifdef __STDC__
  403. ensure_predicates_cover_ambiguous_lookahead_sequences( Junction *alt1, Junction *alt2, char *sub, Tree *ambig )
  404. #else
  405. ensure_predicates_cover_ambiguous_lookahead_sequences( alt1, alt2, sub, ambig )
  406. Junction *alt1;
  407. Junction *alt2;
  408. char *sub;
  409. Tree *ambig;
  410. #endif
  411. {
  412.     if ( !ParseWithPredicates ) return;
  413.  
  414.     if ( ambig!=NULL )
  415.     {
  416.         Tree *non_covered = NULL;
  417.         if ( alt1->predicate!=NULL )
  418.             non_covered = tdif(ambig, alt1->predicate, alt1->fset, alt2->fset);
  419.         if ( (non_covered!=NULL || alt1->predicate==NULL) && WarningLevel>1 )
  420.         {
  421.             fprintf(stderr, ErrHdr, FileStr[alt1->file], alt1->line);
  422.             fprintf(stderr, " warning: alt %d %shas no predicate to resolve ambiguity",
  423.                             alt1->altnum, sub);
  424.             if ( alt2->predicate!=NULL && non_covered!=NULL )
  425.             {
  426.                 fprintf(stderr, " upon");
  427.                 preorder(non_covered);
  428.             }
  429.             fprintf(stderr, "\n");
  430.         }
  431.         Tfree(non_covered);
  432.         if ( alt2->predicate!=NULL )
  433.             non_covered = tdif(ambig, alt2->predicate, alt1->fset, alt2->fset);
  434.         if ( (non_covered!=NULL || alt2->predicate==NULL) && WarningLevel>1 )
  435.         {
  436.             fprintf(stderr, ErrHdr, FileStr[alt2->file], alt2->line);
  437.             fprintf(stderr, " warning: alt %d %shas no predicate to resolve ambiguity",
  438.                             alt2->altnum, sub);
  439.             if ( alt2->predicate!=NULL && non_covered!=NULL )
  440.             {
  441.                 fprintf(stderr, " upon");
  442.                 preorder(non_covered);
  443.             }
  444.             fprintf(stderr, "\n");
  445.         }
  446.         Tfree(non_covered);
  447.     }
  448.     else if ( !set_nil(alt1->fset[1]) )
  449.     {
  450.         set delta, non_covered;
  451.         delta = set_and(alt1->fset[1], alt2->fset[1]);
  452.         non_covered = set_dif(delta, covered_set(alt1->predicate));
  453.         if ( set_deg(non_covered)>0 && WarningLevel>1 )
  454.         {
  455.             fprintf(stderr, ErrHdr, FileStr[alt1->file], alt1->line);
  456.             fprintf(stderr, " warning: alt %d %shas no predicate to resolve ambiguity",
  457.                             alt1->altnum, sub);
  458.             if ( alt1->predicate!=NULL )
  459.             {
  460.                 fprintf(stderr, " upon ");
  461.                 s_fprT(stderr, non_covered);
  462.             }
  463.             fprintf(stderr, "\n");
  464.         }
  465.         set_free( non_covered );
  466.         non_covered = set_dif(delta, covered_set(alt2->predicate));
  467.         if ( set_deg(non_covered)>0 && WarningLevel>1 )
  468.         {
  469.             fprintf(stderr, ErrHdr, FileStr[alt2->file], alt2->line);
  470.             fprintf(stderr, " warning: alt %d %shas no predicate to resolve ambiguity",
  471.                             alt2->altnum, sub);
  472.             if ( alt2->predicate!=NULL )
  473.             {
  474.                 fprintf(stderr, " upon ");
  475.                 s_fprT(stderr, non_covered);
  476.             }
  477.             fprintf(stderr, "\n");
  478.         }
  479.         set_free( non_covered );
  480.         set_free( delta );
  481.     }
  482.     else fatal("productions have no lookahead in predicate checking routine");
  483. }
  484.  
  485. void
  486. #ifdef __STDC__
  487. HandleAmbiguity( Junction *block, Junction *alt1, Junction *alt2, int jtype )
  488. #else
  489. HandleAmbiguity( block, alt1, alt2, jtype )
  490. Junction *block;
  491. Junction *alt1;
  492. Junction *alt2;
  493. int jtype;
  494. #endif
  495. {
  496.     unsigned **ftbl;
  497.     set *fset, b;
  498.     int i, numAmbig, n, n2;
  499.     Tree *ambig, *t, *u;
  500.     char *sub = "";
  501.     require(block!=NULL, "NULL block");
  502.     require(block->ntype==nJunction, "invalid block");
  503.  
  504.     /* These sets are used to constrain LL_k set, but are made CLL_k long anyway */
  505.     fset = (set *) calloc(CLL_k+1, sizeof(set));
  506.     require(fset!=NULL, "cannot allocate fset");
  507.     ftbl = (unsigned **) calloc(CLL_k+1, sizeof(unsigned *));
  508.     require(ftbl!=NULL, "cannot allocate ftbl");
  509.     /* create constraint table and count number of possible ambiguities (use<=LL_k) */
  510.     for (n=1,i=1; i<=CLL_k; i++)
  511.     {
  512.         b = set_and(alt1->fset[i], alt2->fset[i]);
  513.         n *= set_deg(b);
  514.         fset[i] = set_dup(b);
  515.         ftbl[i] = set_pdq(b);
  516.         set_free(b);
  517.     }
  518.  
  519.     /* If the block is marked as a compressed lookahead only block, then
  520.      * simply return; ambiguity warning is given only at warning level 2.
  521.      */
  522.     if ( block->approx>0 )
  523.     {
  524.         if ( ParseWithPredicates )
  525.         {
  526.             alt1->predicate = find_predicates((Node *)alt1->p1);
  527.             alt2->predicate = find_predicates((Node *)alt2->p1);
  528.             if ( HoistPredicateContext && (alt1->predicate!=NULL||alt2->predicate!=NULL) )
  529.             ensure_predicates_cover_ambiguous_lookahead_sequences(alt1, alt2, sub, ambig);
  530.         }
  531.  
  532.         if ( WarningLevel>1 )
  533.         {
  534.             fprintf(stderr, ErrHdr, FileStr[alt1->file], alt1->line);
  535.             if ( jtype == aLoopBegin || jtype == aPlusBlk )
  536.                 fprintf(stderr, " warning: optional/exit path and alt(s) %sambiguous upon", sub);
  537.             else
  538.                 fprintf(stderr, " warning(approx): alts %d and %d %sambiguous upon",
  539.                         alt1->altnum, alt2->altnum, sub);
  540.             dumpAmbigMsg(fset, stderr, 0);
  541.         }
  542.         for (i=1; i<=CLL_k; i++) set_free( fset[i] );
  543.         free(fset);
  544.         for (i=1; i<=CLL_k; i++) free( ftbl[i] );
  545.         free(ftbl);
  546.         return;
  547.     }
  548.  
  549.     switch ( jtype )
  550.     {
  551.         case aSubBlk: sub = "of (..) "; break;
  552.         case aOptBlk: sub = "of {..} "; break;
  553.         case aLoopBegin: sub = "of (..)* "; break;
  554.         case aLoopBlk: sub = "of (..)* "; break;
  555.         case aPlusBlk: sub = "of (..)+ "; break;
  556.         case RuleBlk: sub = "of the rule itself "; break;
  557.         default : sub = ""; break;
  558.     }
  559.  
  560.     /* if all sets have degree 1 for k<LL_k, then must be ambig upon >=1 permutation;
  561.      * don't bother doing full LL(k) analysis.
  562.      * (This "if" block handles the LL(1) case)
  563.      */
  564.     n2 = 0;
  565.     for (i=1; i<LL_k; i++) n2 += set_deg(alt1->fset[i])+set_deg(alt2->fset[i]);
  566.     if ( n2==2*(LL_k-1) )
  567.     {
  568. /* TJP: added to fix the case where LL(1) and syntactic predicates didn't
  569.  * work.  It now recognizes syntactic predicates, but does not like combo:
  570.  * LL(1)/syn/sem predicates. (10/24/93) 
  571.  */
  572.         if ( first_item_is_guess_block((Junction *)alt1->p1)!=NULL )
  573.         {
  574.             if ( WarningLevel==1 )
  575.             {
  576.                 for (i=1; i<=CLL_k; i++) set_free( fset[i] );
  577.                 free(fset);
  578.                 for (i=1; i<=CLL_k; i++) free( ftbl[i] );
  579.                 free(ftbl);
  580.                 return;
  581.             }
  582.  
  583.             fprintf(stderr, ErrHdr, FileStr[alt1->file], alt1->line);
  584.             if ( jtype == aLoopBegin || jtype == aPlusBlk )
  585.                fprintf(stderr, " warning: optional/exit path and alt(s) %sambiguous upon", sub);
  586.             else
  587.                fprintf(stderr, " warning: alts %d and %d %sambiguous upon",
  588.                        alt1->altnum, alt2->altnum, sub);
  589.             dumpAmbigMsg(fset, stderr, 0);
  590.         }
  591.  
  592.         ambig = NULL;
  593.         if ( LL_k>1 ) ambig = make_tree_from_sets(alt1->fset, alt2->fset);
  594.         if ( ParseWithPredicates )
  595.         {
  596.            /* NOTE: find_predicates() doesn't know that full LL(k) analysis is
  597.             *         not necessary.
  598.             */
  599.            alt1->predicate = find_predicates((Node *)alt1->p1);
  600.            alt2->predicate = find_predicates((Node *)alt2->p1);
  601.            if (HoistPredicateContext&&(alt1->predicate!=NULL||alt2->predicate!=NULL))
  602.               ensure_predicates_cover_ambiguous_lookahead_sequences(alt1, alt2, sub, ambig);
  603.            if ( WarningLevel == 1 &&
  604.                (alt1->predicate!=NULL||alt2->predicate!=NULL))
  605.            {
  606.               for (i=1; i<=CLL_k; i++) set_free( fset[i] );
  607.               free(fset);
  608.               for (i=1; i<=CLL_k; i++) free( ftbl[i] );
  609.               free(ftbl);
  610.               Tfree(ambig);
  611.               return;
  612.            }
  613.         }
  614. /* end TJP (10/24/93) */
  615.  
  616.         fprintf(stderr, ErrHdr, FileStr[alt1->file], alt1->line);
  617.         if ( jtype == aLoopBegin || jtype == aPlusBlk )
  618.             fprintf(stderr, " warning: optional/exit path and alt(s) %sambiguous upon", sub);
  619.         else
  620.            fprintf(stderr, " warning: alts %d and %d %sambiguous upon",
  621.                    alt1->altnum, alt2->altnum, sub);
  622.         if ( elevel == 3 && LL_k>1 )
  623.         {
  624.            preorder(ambig);
  625.            fprintf(stderr, "\n");
  626.            Tfree(ambig);
  627.            return;
  628.         }
  629.         Tfree(ambig);
  630.         dumpAmbigMsg(fset, stderr, 0);
  631.  
  632.         for (i=1; i<=CLL_k; i++) set_free( fset[i] );
  633.         free(fset);
  634.         for (i=1; i<=CLL_k; i++) free( ftbl[i] );
  635.         free(ftbl);
  636.         return;
  637.     }
  638.  
  639.     /* in case tree construction runs out of memory, set info to make good err msg */
  640.     CurAmbigAlt1 = alt1->altnum;
  641.     CurAmbigAlt2 = alt2->altnum;
  642.     CurAmbigbtype = sub;
  643.     CurAmbigfile = alt1->file;
  644.     CurAmbigline = alt1->line;
  645.     
  646.     /* Don't do full LL(n) analysis if (...)? block because the block,
  647.        by definition, defies LL(n) analysis.
  648.        If guess (...)? block and ambiguous then don't remove anything from
  649.        2nd alt to resolve ambig.
  650.        Want to predict with LL sup 1 ( n ) decision not LL(n) if guess block
  651.        since it is much cheaper than LL(n).  LL sup 1 ( n ) "covers" the LL(n)
  652.        lookahead information.
  653.  
  654.        Note: LL(n) context cannot be computed for semantic predicates when
  655.        followed by (..)?.
  656.  
  657.        If (..)? then we scream "AAAHHHH!  No LL(n) analysis will help"
  658.  
  659.        Is 'ambig' always defined if we enter this if?  I hope so
  660.        because the 'ensure...()' func references it. TJP Nov 1993.
  661.        */
  662.     if ( first_item_is_guess_block((Junction *)alt1->p1)!=NULL )
  663.     {
  664.         if ( ParseWithPredicates )
  665.         {
  666.             alt1->predicate = find_predicates((Node *)alt1->p1);
  667.             alt2->predicate = find_predicates((Node *)alt2->p1);
  668.             if ( HoistPredicateContext && (alt1->predicate!=NULL||alt2->predicate!=NULL) )
  669.                 ensure_predicates_cover_ambiguous_lookahead_sequences(alt1, alt2, sub, ambig);
  670.             if ( WarningLevel==1 &&
  671.                 (alt1->predicate!=NULL||alt2->predicate!=NULL))
  672.             {
  673.                 for (i=1; i<=CLL_k; i++) set_free( fset[i] );
  674.                 free(fset);
  675.                 for (i=1; i<=CLL_k; i++) free( ftbl[i] );
  676.                 free(ftbl);
  677.                 return;
  678.             }
  679.         }
  680.  
  681.         if ( WarningLevel>1 )
  682.         {
  683.             fprintf(stderr, ErrHdr, FileStr[alt1->file], alt1->line);
  684.             if ( jtype == aLoopBegin || jtype == aPlusBlk )
  685.                 fprintf(stderr, " warning: optional/exit path and alt(s) %sambiguous upon", sub);
  686.             else
  687.                 fprintf(stderr, " warning: alts %d and %d %sambiguous upon",
  688.                         alt1->altnum, alt2->altnum, sub);
  689.             dumpAmbigMsg(fset, stderr, 0);
  690.         }
  691.  
  692.         for (i=1; i<=CLL_k; i++) set_free( fset[i] );
  693.         free(fset);
  694.         for (i=1; i<=CLL_k; i++) free( ftbl[i] );
  695.         free(ftbl);
  696.         return;
  697.     }
  698.     
  699.     /* Not resolved with (..)? block.  Do full LL(n) analysis */
  700.     
  701.     /* ambig is the set of k-tuples truly in common between alt 1 and alt 2 */
  702.     ambig = VerifyAmbig(alt1, alt2, ftbl, fset, &t, &u, &numAmbig);
  703.     for (i=1; i<=CLL_k; i++) free( ftbl[i] );
  704.     free(ftbl);
  705.  
  706. /* TJP: to fix case when definitely LL(k>1) ambiguous and did not look for
  707.  * semantic predicates:
  708.  */
  709.     if ( ParseWithPredicates )
  710.     {
  711.         alt1->predicate = find_predicates((Node *)alt1->p1);
  712.         alt2->predicate = find_predicates((Node *)alt2->p1);
  713.         if ( HoistPredicateContext && (alt1->predicate!=NULL||alt2->predicate!=NULL) )
  714.            ensure_predicates_cover_ambiguous_lookahead_sequences(alt1, alt2, sub, ambig);
  715.         if ( WarningLevel==1 &&
  716.             (alt1->predicate!=NULL||alt2->predicate!=NULL))
  717.            {
  718.                for (i=1; i<=CLL_k; i++) set_free( fset[i] );
  719.                free(fset);
  720.                return;
  721.            }
  722.     }
  723.     
  724.     if ( WarningLevel>1 )
  725.     {
  726.        fprintf(stderr, ErrHdr, FileStr[alt1->file], alt1->line);
  727.         if ( jtype == aLoopBegin || jtype == aPlusBlk )
  728.             fprintf(stderr, " warning: optional/exit path and alt(s) %sambiguous upon", sub);
  729.        else
  730.           fprintf(stderr, " warning: alts %d and %d %sambiguous upon",
  731.                   alt1->altnum, alt2->altnum, sub);
  732.        dumpAmbigMsg(fset, stderr, 0);
  733.     }
  734. /* end TJP addition */
  735.  
  736.     /* are all things in intersection really ambigs? */
  737.     if ( numAmbig < n )
  738.     {
  739.         Tree *v;
  740.  
  741.         /* remove ambig permutation from 2nd alternative to resolve ambig;
  742.          * We want to compute the set of artificial tuples, arising from
  743.          * LL sup 1 (n) compression, that collide with real tuples from the
  744.          * 2nd alternative.  This is the set of "special case" tuples that
  745.          * the LL sup 1 (n) decision template maps incorrectly.
  746.          */
  747.         if ( ambig!=NULL )
  748.         {
  749.             for (v=ambig->down; v!=NULL; v=v->right)
  750.             {
  751.                 u = trm_perm(u, v);
  752.             }
  753.             /*fprintf(stderr, "after rm alt2:"); preorder(u); fprintf(stderr, "\n");*/
  754.         }
  755.         Tfree( t );
  756.         alt1->ftree = tappend(alt1->ftree, u);
  757.         alt1->ftree = tleft_factor(alt1->ftree);
  758.     }
  759.  
  760.     if ( ambig==NULL )
  761.     {
  762.         for (i=1; i<=CLL_k; i++) set_free( fset[i] );
  763.         free(fset);
  764.         return;
  765.     }
  766.  
  767.     ambig = tleft_factor(ambig);
  768.  
  769.     fprintf(stderr, ErrHdr, FileStr[alt1->file], alt1->line);
  770.     if ( jtype == aLoopBegin || jtype == aPlusBlk )
  771.         fprintf(stderr, " warning: optional/exit path and alt(s) %sambiguous upon", sub);
  772.     else
  773.         fprintf(stderr, " warning: alts %d and %d %sambiguous upon",
  774.                     alt1->altnum, alt2->altnum, sub);
  775.     if ( elevel == 3 )
  776.     {
  777.         preorder(ambig->down);
  778.         fprintf(stderr, "\n");
  779.         Tfree(ambig);
  780.         return;
  781.     }
  782.     Tfree(ambig);
  783.     dumpAmbigMsg(fset, stderr, 0);
  784.     for (i=1; i<=CLL_k; i++) set_free( fset[i] );
  785.     free(fset);
  786. }
  787.  
  788. /* Don't analyze alpha block of (alpha)?beta; if (alpha)? then analyze
  789.  * Return the 1st node of the beta block if present else return j.
  790.  */
  791. Junction *
  792. #ifdef __STDC__
  793. analysis_point( Junction *j )
  794. #else
  795. analysis_point( j )
  796. Junction *j;
  797. #endif
  798. {
  799.     Junction *gblock;
  800.  
  801.     if ( j->ntype!=nJunction ) return j;
  802.     gblock = first_item_is_guess_block((Junction *)j);
  803.  
  804.     if ( gblock!=NULL )
  805.     {
  806.         Junction *past = gblock->end;
  807.         Junction *p;
  808.         require(past!=NULL, "analysis_point: no end block on (...)? block");
  809.  
  810.         for (p=(Junction *)past->p1; p!=NULL; )
  811.         {
  812.             if ( p->ntype==nAction )
  813.             {
  814.                 p=(Junction *)((ActionNode *)p)->next;
  815.                 continue;
  816.             }
  817.             if ( p->ntype!=nJunction )
  818.             {
  819.                 return (Junction *)past->p1;
  820.             }
  821.             if ( p->jtype==EndBlk || p->jtype==EndRule )
  822.             {
  823.                 return j;
  824.             }
  825.             p=(Junction *)p->p1;
  826.         }
  827.     }
  828.     return j;
  829. }
  830.  
  831. set
  832. #ifdef __STDC__
  833. First( Junction *j, int k, int jtype, int *max_k )
  834. #else
  835. First( j, k, jtype, max_k )
  836. Junction *j;
  837. int k;
  838. int jtype;
  839. int *max_k;
  840. #endif
  841. {
  842.     Junction *alt1, *alt2;
  843.     set a, rk, fCurBlk;
  844.     int savek;
  845.     int p1, p2;
  846.     require(j->ntype==nJunction, "First: non junction passed");
  847.  
  848.     /* C o m p u t e  F I R S T  s e t  w i t h  k  l o o k a h e a d */
  849.     fCurBlk = rk = empty;
  850.     for (alt1=j; alt1!=NULL; alt1 = (Junction *)alt1->p2)
  851.     {
  852.         Junction *p = analysis_point((Junction *)alt1->p1);
  853.         REACH(p, k, &rk, alt1->fset[k]);
  854.         require(set_nil(rk), "rk != nil");
  855.         set_free(rk);
  856.         set_orin(&fCurBlk, alt1->fset[k]);
  857.     }
  858.  
  859.     /* D e t e c t  A m b i g u i t i e s */
  860.     *max_k = 1;
  861.     for (p1=1,alt1=j; alt1!=NULL; alt1 = (Junction *)alt1->p2, p1++)
  862.     {
  863.         for (p2=1,alt2=(Junction *)alt1->p2; alt2!=NULL; alt2 = (Junction *)alt2->p2, p2++)
  864.         {
  865.             savek = k;
  866.             a = set_and(alt1->fset[k], alt2->fset[k]);
  867.             while ( !set_nil(a) )
  868.             {
  869.                 /* if we have hit the max k requested, just give warning */
  870.                 if ( j->approx==k ) {
  871.                 }
  872.  
  873.                 if ( k==CLL_k )
  874.                 {
  875. #ifdef NOT_USED
  876.                     int save_LL_k = LL_k;
  877.                     int save_CLL_k = CLL_k;
  878.                     /* Get new LL_k from interactive feature if enabled */
  879.                     if ( AImode )
  880.                         AmbiguityDialog(j, jtype, alt1, alt2, &CLL_k, &LL_k);
  881. #endif
  882.                     *max_k = CLL_k;
  883.                     HandleAmbiguity(j, alt1, alt2, jtype);
  884.                     break;
  885.                 }
  886.                 else
  887.                 {
  888.                     Junction *p = analysis_point((Junction *)alt1->p1);
  889.                     Junction *q = analysis_point((Junction *)alt2->p1);
  890.                     k++;    /* attempt ambig alts again with more lookahead */
  891.                     REACH(p, k, &rk, alt1->fset[k]);
  892.                     require(set_nil(rk), "rk != nil");
  893.                     REACH(q, k, &rk, alt2->fset[k]);
  894.                     require(set_nil(rk), "rk != nil");
  895.                     set_free(a);
  896.                     a = set_and(alt1->fset[k], alt2->fset[k]);
  897.                     if ( k > *max_k ) *max_k = k;
  898.                 }
  899.             }
  900.             set_free(a);
  901.             k = savek;
  902.         }
  903.     }
  904.  
  905.     return fCurBlk;
  906. }
  907.