home *** CD-ROM | disk | FTP | other *** search
/ Garbo / Garbo.cdr / pc / unix / dgrep.arc / CALCPOS.C < prev    next >
Encoding:
C/C++ Source or Header  |  1990-01-15  |  8.2 KB  |  335 lines
  1. /**********************************************************************\
  2.  *
  3.  *    CALCPOS.C
  4.  *
  5.  * Calculates firstpos, lastpos and followpos from syntax tree.
  6.  *
  7.  * Author: Jarmo Ruuth 15-Mar-1988
  8.  *
  9.  * Copyright (C) 1988-90 by Jarmo Ruuth
  10.  * May be freely copied for any non-commercial usage.
  11. \**********************************************************************/
  12.  
  13. #include "system.h"
  14. #include "dfa.h"
  15.  
  16. /**********************************************************************
  17.  *
  18.  *    nullable
  19.  *
  20.  * Sets nullable TRUE or FALSE for given node.
  21.  * Nullable is TRUE for such nodes that are the roots of subexpressions
  22.  * that generate languages that include the empty string.
  23.  */
  24. static void nullable(REG1 node_t* tnode)
  25. {
  26.     switch (tnode->type) {
  27.         case EMPTY_ID:
  28.             tnode->nullable = TRUE;
  29.             break;
  30.         case CLASS_ID:
  31.         case ID:
  32.             tnode->nullable = FALSE;
  33.             break;
  34.         case OR:
  35.             tnode->nullable = 
  36.                 rbuf.tree[tnode->val.next.left].nullable
  37.                 || rbuf.tree[tnode->val.next.right].nullable;
  38.             break;
  39.         case CAT:
  40.             tnode->nullable =
  41.                 rbuf.tree[tnode->val.next.left].nullable
  42.                 && rbuf.tree[tnode->val.next.right].nullable;
  43.             break;
  44.         case CLOSURE:
  45.             tnode->nullable = TRUE;
  46.             break;
  47.     }
  48. }
  49.  
  50. /**********************************************************************
  51.  *
  52.  *    firstpos
  53.  *
  54.  * Fills firstpos-field in syntax tree. Here we suppose, that all
  55.  * nodes below current node are already visited (depth-first traversal).
  56.  * Firstpos is a set of positions that can match the first symbol of a 
  57.  * string generated by the subexpression rooted by node.
  58.  */
  59. static void firstpos(REG1 int node, REG2 node_t* tnode)
  60. {
  61.     switch (tnode->type) {
  62.         case EMPTY_ID:
  63.             set_clear(tnode->firstpos, rbuf.setsize);
  64.             break;
  65.         case CLASS_ID:
  66.         case ID:
  67.             add_set(tnode->firstpos, node);
  68.             break;
  69.         case OR:
  70.             set_union(tnode->firstpos,
  71.                 rbuf.tree[tnode->val.next.left].firstpos,
  72.             rbuf.tree[tnode->val.next.right].firstpos,
  73.             rbuf.setsize);
  74.             break;
  75.         case CAT:
  76.             if (rbuf.tree[tnode->val.next.left].nullable)
  77.             set_union(tnode->firstpos,
  78.                 rbuf.tree[tnode->val.next.left].firstpos,
  79.                 rbuf.tree[tnode->val.next.right].firstpos,
  80.                 rbuf.setsize);
  81.             else
  82.             set_copy(tnode->firstpos,
  83.                 rbuf.tree[tnode->val.next.left].firstpos,
  84.                 rbuf.setsize);
  85.             break;
  86.         case CLOSURE:
  87.             set_copy(tnode->firstpos,
  88.                  rbuf.tree[tnode->val.next.left].firstpos,
  89.                  rbuf.setsize);
  90.             break;
  91.     }
  92. }
  93.     
  94. /**********************************************************************
  95.  *
  96.  *    lastpos
  97.  *
  98.  * Fills lastpos-field in syntax tree. Here we suppose, that all
  99.  * nodes below current node are already visited (depth-first traversal).
  100.  * Lastpos is a set of positions that can match the last symbol of a 
  101.  * string generated by the subexpression rooted by node.
  102.  */
  103. static void lastpos(int node, REG1 node_t* tnode)
  104. {
  105.     switch (tnode->type) {
  106.         case EMPTY_ID:
  107.             set_clear(tnode->lastpos, rbuf.setsize);
  108.             break;
  109.         case CLASS_ID:
  110.         case ID:
  111.             add_set(tnode->lastpos, node);
  112.             break;
  113.         case OR:
  114.             set_union(tnode->lastpos,
  115.               rbuf.tree[tnode->val.next.left].lastpos,
  116.               rbuf.tree[tnode->val.next.right].lastpos,
  117.               rbuf.setsize);
  118.             break;
  119.         case CAT:
  120.             if (rbuf.tree[tnode->val.next.right].nullable)
  121.                 set_union(tnode->lastpos,
  122.                 rbuf.tree[tnode->val.next.left].lastpos,
  123.                 rbuf.tree[tnode->val.next.right].lastpos,
  124.                 rbuf.setsize);
  125.             else
  126.             set_copy(tnode->lastpos,
  127.                     rbuf.tree[tnode->val.next.right].lastpos,
  128.                     rbuf.setsize);
  129.             break;
  130.         case CLOSURE:
  131.             set_copy(tnode->lastpos,
  132.                 rbuf.tree[tnode->val.next.left].lastpos,
  133.                 rbuf.setsize);
  134.             break;
  135.     }
  136. }
  137.     
  138. /**********************************************************************
  139.  *
  140.  *    set_pos
  141.  *
  142.  * Sets nullable, firstpos and lastpos in whole tree.
  143.  */
  144. static bool set_pos(void)
  145. {
  146.     REG1 int    i;
  147.     REG2 node_t*    tnode = rbuf.tree;
  148.     
  149.     for (i = 0; i <= rbuf.root; i++, tnode++) {
  150.         nullable(tnode);
  151.         if ((tnode->firstpos = calloc(rbuf.setsize, 1)) == NULL)
  152.             return FALSE;
  153.         firstpos(i, tnode);
  154.         if ((tnode->lastpos = calloc(rbuf.setsize, 1)) == NULL)
  155.             return FALSE;
  156.         lastpos(i, tnode);
  157.     }
  158.     return TRUE;
  159. }
  160.  
  161. /**********************************************************************
  162.  *
  163.  *    followpos
  164.  *
  165.  * Creates followpos array using depth-first traversal.
  166.  * Followpos(i) is the set of positions j such that there is some input 
  167.  * string ...cd... such that i corresponds to this occurence of c and 
  168.  * j to this occurence of d. So for example for a subexpression cd each 
  169.  * lastpos of c is followed by firstpos of d, or for c* each lastpos of
  170.  * c is followed by firstpos in c.
  171.  */
  172. static bool followpos(void)
  173. {
  174.     REG1 int    i; 
  175.     REG2 int    j;
  176.     REG3 node_t*    inode;
  177.     REG4 node_t*    jnode;
  178.     REG5 set_t**    followptr;
  179.     
  180.     if ((followptr = calloc((rbuf.root+1) * sizeof(set_t *), 1)) == NULL)
  181.         return FALSE;
  182.     rbuf.follow_array = followptr;
  183.     inode = rbuf.tree;
  184.     for (i = 0; i <= rbuf.root; i++, inode++, followptr++) {
  185.         if (inode->type != ID && inode->type != CLASS_ID ) {
  186.             *followptr = NULL;
  187.             continue;
  188.         }
  189.         if ((*followptr = calloc(rbuf.setsize, 1)) == NULL)
  190.             return FALSE;
  191.         jnode = &rbuf.tree[i+1];
  192.         for (j = i+1; j <= rbuf.root; j++, jnode++) {
  193.             switch (jnode->type) {
  194.                 case CAT:
  195.                 if (in_set(rbuf.tree[jnode->val.next.left].
  196.                     lastpos, i))
  197.                     set_union(
  198.                       *followptr,
  199.                       *followptr,
  200.                       rbuf.tree[jnode->val.next.right].firstpos,
  201.                       rbuf.setsize);
  202.                 break;
  203.                 case CLOSURE:
  204.                 if (in_set(jnode->lastpos, i))
  205.                     set_union(
  206.                       *followptr,
  207.                       *followptr,
  208.                       jnode->firstpos,
  209.                       rbuf.setsize);
  210.                 break;
  211.                 default:
  212.                 break;
  213.             }
  214.         }
  215.     }
  216.     return TRUE;
  217. }
  218.  
  219. /**********************************************************************
  220.  *
  221.  *    free_posmem
  222.  *
  223.  * Frees memory, that is not needed to create transition table.
  224.  */
  225. static void free_posmem(void)
  226. {
  227.     REG1 int    i;
  228.     REG2 node_t*    tnode = &rbuf.tree[rbuf.root];
  229.  
  230.     d_free(&tnode->lastpos);
  231.     --tnode;
  232.     for (i = rbuf.root-1; i-- >= 0; tnode--) {
  233.         d_free(&tnode->firstpos);
  234.         d_free(&tnode->lastpos);
  235.     }
  236. }
  237.  
  238. #ifdef TEST
  239.  
  240. extern    int debug;
  241.  
  242. /**********************************************************************
  243.  *
  244.  *    print_tree
  245.  */
  246. static void print_tree(void)
  247. {
  248.     REG1 int    i,j;
  249.     char*        char_image(int c);
  250.     
  251.     for (i = 0; i <= rbuf.root; i++) {
  252.         printf("%2d ",i);
  253.         switch (rbuf.tree[i].type) {
  254.             case CAT:
  255.                 printf("CAT %2d %2d", 
  256.                     rbuf.tree[i].val.next.left,
  257.                     rbuf.tree[i].val.next.right);
  258.                 break;
  259.             case OR:
  260.                 printf("OR  %2d %2d",
  261.                     rbuf.tree[i].val.next.left,
  262.                     rbuf.tree[i].val.next.right);
  263.                 break;
  264.             case CLOSURE:
  265.                 printf("CLO %2d   ",
  266.                     rbuf.tree[i].val.next.left);
  267.                 break;
  268.             case ID:
  269.                 printf("ID %3s   ", 
  270.                     char_image(rbuf.tree[i].val.item));
  271.                 break;
  272.             case EMPTY_ID:
  273.                 printf("EMPTY_ID ");
  274.                 break;
  275.             case CLASS_ID:
  276.                 printf("CLASS ID ");
  277.                 break;
  278.         }
  279.         printf(" f");
  280.         for (j = 0; j <= rbuf.root; j++)
  281.             if (in_set(rbuf.tree[i].firstpos, j))
  282.                 printf(" %2d",j);
  283.         printf("\tl");
  284.         for (j = 0; j <= rbuf.root; j++)
  285.             if (in_set(rbuf.tree[i].lastpos, j))
  286.                 printf(" %2d",j);
  287.         printf("\n");
  288.     }
  289.     fflush(stdout);
  290. }
  291.  
  292. /**********************************************************************
  293.  *
  294.  *    print_followpos
  295.  */
  296. static void print_followpos(void)
  297. {
  298.     REG1 int    i, j;
  299.     
  300.     printf("Followpositions:\n");
  301.     for (i = 0; i <= rbuf.root; i++) {
  302.         if (rbuf.follow_array[i] == NULL)
  303.             continue;
  304.         printf("%2d:", i);
  305.         for (j = 0; j <= rbuf.root; j++)
  306.             if (in_set(rbuf.follow_array[i], j))
  307.                 printf(" %d", j);
  308.         printf("\n");
  309.     }
  310.     fflush(stdout);
  311. }
  312.  
  313. #endif /* TEST */
  314.  
  315. /**********************************************************************
  316.  *
  317.  *    calcpos
  318.  */
  319. bool calcpos(void)
  320. {
  321.     rbuf.setsize = set_bytesize(rbuf.root+1);
  322.     if (!set_pos() || !followpos()) {
  323.         free_posmem();
  324.         return FALSE;
  325.     }
  326. #ifdef TEST
  327.     if (debug > 1) {
  328.         print_tree();
  329.         print_followpos();
  330.     }
  331. #endif
  332.     free_posmem();
  333.     return TRUE;
  334. }
  335.