home *** CD-ROM | disk | FTP | other *** search
/ OS/2 Shareware BBS: 10 Tools / 10-Tools.zip / pccts1.zip / ANTLR / PRED.C < prev    next >
C/C++ Source or Header  |  1993-09-02  |  9KB  |  375 lines
  1. /*
  2.  * pred.c -- source for predicate detection, manipulation
  3.  *
  4.  * $Id: pred.c,v 1.6 1993/08/24 14:44:32 pccts Exp pccts $
  5.  * $Revision: 1.6 $
  6.  *
  7.  * SOFTWARE RIGHTS
  8.  *
  9.  * We reserve no LEGAL rights to the Purdue Compiler Construction Tool
  10.  * Set (PCCTS) -- PCCTS is in the public domain.  An individual or
  11.  * company may do whatever they wish with source code distributed with
  12.  * PCCTS or the code generated by PCCTS, including the incorporation of
  13.  * PCCTS, or its output, into commerical software.
  14.  * 
  15.  * We encourage users to develop software with PCCTS.  However, we do ask
  16.  * that credit is given to us for developing PCCTS.  By "credit",
  17.  * we mean that if you incorporate our source code into one of your
  18.  * programs (commercial product, research project, or otherwise) that you
  19.  * acknowledge this fact somewhere in the documentation, research report,
  20.  * etc...  If you like PCCTS and have developed a nice tool with the
  21.  * output, please mention that you developed it using PCCTS.  In
  22.  * addition, we ask that this header remain intact in our source code.
  23.  * As long as these guidelines are kept, we expect to continue enhancing
  24.  * this system and expect to make other tools available as they are
  25.  * completed.
  26.  *
  27.  * ANTLR 1.10
  28.  * Terence Parr
  29.  * Purdue University
  30.  * 1989-1993
  31.  */
  32. #include <stdio.h>
  33. #ifdef __cplusplus
  34. #ifndef __STDC__
  35. #define __STDC__
  36. #endif
  37. #endif
  38. #include "set.h"
  39. #include "syn.h"
  40. #include "hash.h"
  41. #include "generic.h"
  42. #include "dlgdef.h"
  43.  
  44. #ifdef __STDC__
  45. static Predicate *new_pred(void);
  46. static void complete_context_sets(RuleRefNode *, Predicate *);
  47. static void complete_context_trees(RuleRefNode *, Predicate *);
  48. #else
  49. static Predicate *new_pred();
  50. static void complete_context_sets();
  51. static void complete_context_trees();
  52. #endif
  53.  
  54. static Predicate pred_empty = {NULL,NULL,set_init,{set_init,set_init}};
  55.  
  56. /* Look for a predicate;
  57.  *
  58.  * Do not pass anything but Junction nodes; no Actions, Tokens, RuleRefs.
  59.  * This means that a "hoisting distance" of zero is the only distance
  60.  * allowable.  Init actions are ignored.
  61.  *
  62.  * WARNING:
  63.  *        Assumes no (..)? block after predicate for the moment.
  64.  *        Does not check to see if pred is in production that can generate
  65.  *            a sequence contained in the set of ambiguous tuples.
  66.  *
  67.  * Return the predicate found if any.
  68.  */
  69. Predicate *
  70. #ifdef __STDC__
  71. find_predicates( Node *alt )
  72. #else
  73. find_predicates( alt )
  74. Node *alt;
  75. #endif
  76. {
  77. #ifdef DBG_PRED
  78.     Junction *j;
  79.     RuleRefNode *r;
  80.     TokNode *t;
  81. #endif
  82.     Predicate *pred;
  83.     int max_k=0;
  84.  
  85.     if ( alt==NULL ) return NULL;
  86.  
  87. #ifdef DBG_PRED
  88.     switch ( alt->ntype )
  89.     {
  90.         case nJunction :
  91.             j = (Junction *) alt;
  92.             fprintf(stderr, "Junction(in %s)", j->rname);
  93.             switch ( j->jtype )
  94.             {
  95.                 case aSubBlk :
  96.                     fprintf(stderr,"aSubBlk\n");
  97.                     break;
  98.                 case aOptBlk :
  99.                     fprintf(stderr,"aOptBlk\n");
  100.                     break;
  101.                 case aLoopBegin :
  102.                     fprintf(stderr,"aLoopBeginBlk\n");
  103.                     break;
  104.                 case aLoopBlk :
  105.                     fprintf(stderr,"aLoopBlk\n");
  106.                     break;
  107.                 case aPlusBlk :
  108.                     fprintf(stderr,"aPlusBlk\n");
  109.                     break;
  110.                 case EndBlk :
  111.                     fprintf(stderr,"EndBlk\n");
  112.                     break;
  113.                 case RuleBlk :
  114.                     fprintf(stderr,"RuleBlk\n");
  115.                     break;
  116.                 case Generic :
  117.                     fprintf(stderr,"Generic\n");
  118.                     break;
  119.                 case EndRule :
  120.                     fprintf(stderr,"EndRule\n");
  121.                     break;
  122.             }
  123.             break;
  124.         case nRuleRef :
  125.             r = (RuleRefNode *) alt;
  126.             fprintf(stderr, "RuleRef(in %s)\n", r->rname);
  127.             break;
  128.         case nToken :
  129.             t = (TokNode *) alt;
  130.             fprintf(stderr, "TokenNode(in %s)%s\n", t->rname, TokenStr[t->token]);
  131.             break;
  132.         case nAction :
  133.             fprintf(stderr, "Action\n");
  134.             break;
  135.     }
  136. #endif
  137.  
  138.     switch ( alt->ntype )
  139.     {
  140.         case nJunction :
  141.         {
  142.             Predicate *a, *b, *c;
  143.             Junction *p = (Junction *) alt;    
  144.             if ( p->jtype == EndRule )
  145.             {
  146.                 return NULL;
  147.             }
  148.             if ( p->jtype==aLoopBlk || p->jtype==RuleBlk ||
  149.                  p->jtype==aPlusBlk || p->jtype==EndRule )
  150.             {
  151.                 require(p->pred_lock!=NULL, "rJunc: lock array is NULL");
  152.                 if ( p->pred_lock[1] )
  153.                 {
  154.                     return NULL;
  155.                 }
  156.                 p->pred_lock[1] = TRUE;
  157.             }
  158.             a = find_predicates(p->p1);
  159.             /* don't follow p2 link as that points to next rule */
  160.             if ( p->jtype==RuleBlk ) {p->pred_lock[1] = FALSE; return a;}
  161.  
  162.             b = find_predicates(p->p2);
  163.             /* link p2 predicates to others */
  164.             if ( a==NULL ) a = b;
  165.             else
  166.             {
  167.                 for (c=a; c->next!=NULL; c=c->next) {;}
  168.                 c->next = b;
  169.             }
  170.             
  171.             if ( p->jtype==aLoopBlk || p->jtype==RuleBlk ||
  172.                  p->jtype==aPlusBlk || p->jtype==EndRule )
  173.             {
  174.                 p->pred_lock[1] = FALSE;
  175.             }
  176.             return a;
  177.         }
  178.         case nAction :
  179.         {
  180.             Predicate *a;
  181.             ActionNode *p = (ActionNode *) alt;
  182.             if ( p->init_action ) return find_predicates(p->next);
  183.             if ( p->is_predicate )
  184.             {
  185.                 Tree *t;
  186. #ifdef DBG_PRED
  187.                 fprintf(stderr, "predicate: <<%s>>?\n", p->action);
  188. #endif
  189.                 pred = new_pred();
  190.                 if ( HoistPredicateContext && LL_k > 1 )
  191.                 {
  192.                     if ( first_item_is_guess_block((Junction *)p->next) )
  193.                     {
  194.                         warnFL("cannot compute context of predicate in front of (..)? block", FileStr[p->file], p->line);
  195.                     }
  196.                     else
  197.                     {
  198.                         ConstrainSearch = 0;
  199.                         TRAV(p->next, LL_k, &(pred->completion), t);
  200.                         t = tshrink( t );
  201.                         t = tflatten( t );
  202.                         t = tleft_factor( t );
  203.                         pred->tcontext = t;
  204. #ifdef DBG_PRED
  205.                         fprintf(stderr, "LL(%d) context:", LL_k);
  206.                         preorder(t);
  207.                         fprintf(stderr, "\n");
  208. #endif
  209.                     }
  210.                 }
  211.                 else if ( HoistPredicateContext && LL_k == 1 )
  212.                 {
  213.                     pred->scontext[1] = empty;
  214.                     if ( first_item_is_guess_block((Junction *)p->next) )
  215.                     {
  216.                         warnFL("cannot compute context of predicate in front of (..)? block", FileStr[p->file], p->line);
  217.                     }
  218.                     else
  219.                     {
  220.                         REACH((Junction *)p->next, 1, &(pred->completion), pred->scontext[1]);
  221. #ifdef DBG_PRED
  222.                         fprintf(stderr, "LL(1) context:");
  223.                         s_fprT(stderr, pred->scontext[1]);
  224.                         fprintf(stderr, "\n");
  225. #endif
  226.                     }
  227.                 }
  228.                 pred->expr = p->action;
  229.                 a = find_predicates(p->next);
  230.                 pred->next = a;
  231.                 return pred;
  232.             }
  233.             return NULL;
  234.         }
  235.         case nRuleRef :
  236.         {
  237.             Predicate *a;
  238.             RuleRefNode *p = (RuleRefNode *) alt;
  239.             Junction *r;
  240.             int save_halt;
  241.             RuleEntry *q = (RuleEntry *) hash_get(Rname, p->text);
  242.             if ( q == NULL )
  243.             {
  244.                 warnNoFL( eMsg1("rule %s not defined",p->text) );
  245.                 return NULL;
  246.             }
  247.             r = RulePtr[q->rulenum];
  248.             if ( r->pred_lock[1] )
  249.             {
  250.                 /* infinite left-recursion; ignore 'cause LL sup 1 (k) analysis
  251.                  * must have seen it earlier.
  252.                  */
  253.                 return NULL;
  254.             }
  255.             save_halt = r->end->halt;
  256.             r->end->halt = TRUE;
  257. /*            a = find_predicates((Node *)r->p1);*/
  258.             a = find_predicates((Node *)r);
  259.             r->end->halt = save_halt;
  260.             if ( a==NULL ) return NULL;
  261.  
  262.             /* attempt to compute the "local" FOLLOW just like in normal lookahead
  263.              * computation if needed
  264.              */
  265.             if ( LL_k==1 ) {complete_context_sets(p,a); return a;}
  266.             complete_context_trees(p,a); return a;
  267.         }
  268.         case nToken :
  269.             break;
  270.     }
  271.  
  272.     return NULL;
  273. }
  274.  
  275. static Predicate *
  276. #ifdef __STDC__
  277. new_pred( void )
  278. #else
  279. new_pred( )
  280. #endif
  281. {
  282.     Predicate *p = (Predicate *) malloc(sizeof(Predicate));
  283.     require(p!=NULL, "new_pred: cannot alloc predicate");
  284.     *p = pred_empty;
  285.     return p;
  286. }
  287.  
  288. static void
  289. #ifdef __STDC__
  290. complete_context_sets( RuleRefNode *p, Predicate *a )
  291. #else
  292. complete_context_sets( p, a )
  293. RuleRefNode *p;
  294. Predicate *a;
  295. #endif
  296. {
  297.     set rk2, b;
  298.     int k2;
  299.  
  300.     for (; a!=NULL; a=a->next)
  301.     {
  302.         rk2 = b = empty;
  303.         while ( !set_nil(a->completion) )
  304.         {
  305.             k2 = set_int(a->completion);
  306.             set_rm(k2, a->completion);
  307.             REACH(p->next, k2, &rk2, b);
  308.             set_orin(&(a->scontext[1]), b);
  309.             set_free(b);
  310.         }
  311.         set_orin(&(a->completion), rk2);/* remember what we couldn't do */
  312.         set_free(rk2);
  313. #ifdef DBG_PRED
  314.         fprintf(stderr, "LL(1) context after ruleref:");
  315.         s_fprT(stderr, a->scontext[1]);
  316.         fprintf(stderr, "\n");
  317. #endif
  318.     }
  319. }
  320.  
  321. static void
  322. #ifdef __STDC__
  323. complete_context_trees( RuleRefNode *p, Predicate *a )
  324. #else
  325. complete_context_trees( p, a )
  326. RuleRefNode *p;
  327. Predicate *a;
  328. #endif
  329. {
  330.     set rk2;
  331.     int k2;
  332.     Tree *u;
  333.  
  334.     for (; a!=NULL; a=a->next)
  335.     {
  336.         rk2 = empty;
  337.         /* any k left to do? if so, link onto tree */
  338.         while ( !set_nil(a->completion) )
  339.         {    
  340.             k2 = set_int(a->completion);
  341.             set_rm(k2, a->completion);
  342.             u = NULL;
  343.             TRAV(p->next, k2, &rk2, u);
  344.             /* any subtrees missing k2 tokens, add u onto end */
  345.             a->tcontext = tlink(a->tcontext, u, k2);
  346.         }
  347.         set_orin(&(a->completion), rk2);/* remember what we couldn't do */
  348.         set_free(rk2);
  349. #ifdef DBG_PRED
  350.         fprintf(stderr, "LL(%d) context after ruleref:", LL_k);
  351.         preorder(a->tcontext);
  352.         fprintf(stderr, "\n");
  353. #endif
  354.     }
  355. }
  356.  
  357. /* Walk a list of predicates and return the set of all tokens in scontext[1]'s */
  358. set
  359. #ifdef __STDC__
  360. covered_set( Predicate *p )
  361. #else
  362. covered_set( p )
  363. Predicate *p;
  364. #endif
  365. {
  366.     set a;
  367.  
  368.     a = empty;
  369.     for (; p!=NULL; p=p->next)
  370.     {
  371.         set_orin(&a, p->scontext[1]);
  372.     }
  373.     return a;
  374. }
  375.