home *** CD-ROM | disk | FTP | other *** search
/ Usenet 1994 January / usenetsourcesnewsgroupsinfomagicjanuary1994.iso / sources / misc / volume36 / unpost / part03 / recomp.c < prev   
Encoding:
C/C++ Source or Header  |  1993-04-18  |  21.7 KB  |  798 lines
  1. /******************************************************************************
  2. * Module    :   Regular Expression Compiling.
  3. *
  4. * Author    :   John W. M. Stevens.
  5. *
  6. * Notes     :   Use UNIX style regular expressions.  Grammar is:
  7. *
  8. *   REG_EXPR    ::= ANCHOR
  9. *                   | ANCHOR '|' REG_EXPR
  10. *
  11. *   ANCHOR      ::= CATENATION
  12. *                   | '^' CATENATION
  13. *                   | CATENATION '$'
  14. *                   | '^' CATENATION '$'
  15. *
  16. *   CATENATION  ::= PHRASE
  17. *                   | PHRASE CATENATION
  18. *
  19. *   PHRASE      ::= UNARY
  20. *                   | UNARY ENUM_OP
  21. *
  22. *   ENUM_OP     ::= '*'
  23. *                   | '+'
  24. *                   | '?'
  25. *                   | '{' SPAN_RNG '}'
  26. *
  27. *   SPAN_RNG    ::= NUMBER
  28. *                   | NUMBER ',' NUMBER
  29. *
  30. *   UNARY       ::= '(' REG_EXPR ')'
  31. *                   | CHAR_STR
  32. *                   | '[' SET ']'
  33. *                   | '[' '^' SET ']'
  34. *                   | '.'
  35. *
  36. *   SET         ::= CHAR_STR
  37. *                   | CHAR_STR SET
  38. *                   | CHAR '-' CHAR
  39. *                   | CHAR '-' CHAR SET
  40. *
  41. *   CHAR_STR    ::= CHARACTER
  42. *                   | CHARACTER CHARACTER_STR
  43. *
  44. *   CHARACTER   ::= ' ' - '~' except for []()|{}+*? which are special without
  45. *                   being escaped.
  46. ******************************************************************************/
  47.  
  48. #include    "compiler.h"
  49.  
  50. #include    "unpost.h"
  51. #include    "sets.h"
  52. #include    "regexp.h"
  53. #include    "utils.h"
  54.  
  55. /*  Character Sets. */
  56. static  int     ReInitFlag = 0;
  57. static  char    *SpecStr = "[().|$";
  58. static  SET     SpecSet;
  59. static  char    *PostFixStr = "{*?+";
  60. static  SET     PostSet;
  61. static  char    *DecStr = "0-9";
  62. static  SET     DecSet;
  63.  
  64. static  UINT    SubExprNo;
  65.  
  66. static  REG_EXP_NODE    *Alternation(char **);
  67.  
  68. #if defined( RE_TEST )
  69.  
  70. /*-----------------------------------------------------------------------------
  71. | Routine   :   PrtReExpr() --- Print a regular expression for debugging
  72. |               purposes.  (This may be used in the configuration helper
  73. |               in a later release, so make it pretty).
  74. |
  75. | Inputs    :   Node    - Pointer to current level regular expression node.
  76. |               Level   - Current level in tree.
  77. -----------------------------------------------------------------------------*/
  78.  
  79. static
  80. void    PrtReExpr(REG_EXP_NODE  *Node,
  81.                   int           Level)
  82. {
  83.     register    int     i;
  84.     register    int     j;
  85.  
  86.     /*  Traverse right to left so that the tree can be printed
  87.     *   on a screen or page rotated 90 degrees to the left.
  88.     *
  89.     *   (Right to left == top to bottom of screen or page)
  90.     */
  91.     if ( Node->Right )
  92.         PrtReExpr(Node->Right, Level + 1);
  93.  
  94.     /*  Print indentation.  */
  95.     for (i = 0; i < Level; i++)
  96.         printf("    ");
  97.  
  98.     /*  Print node type and information.    */
  99.     switch ( Node->NodeType )
  100.     {
  101.     case OP_L_PAREN:
  102.         printf("(\n");
  103.         break;
  104.     case DATA_LEFT_ANCHOR:
  105.         printf("^\n");
  106.         break;
  107.     case DATA_RIGHT_ANCHOR:
  108.         printf("$\n");
  109.         break;
  110.     case OP_ENUM:
  111.         printf("Enum {%d, %u}\n",
  112.                 Node->MinSpan,
  113.                 Node->MaxSpan);
  114.         break;
  115.     case OP_OR:
  116.         printf("|\n");
  117.         break;
  118.     case OP_AND:
  119.         printf("&\n");
  120.         break;
  121.     case DATA_ANY:
  122.         printf(".\n");
  123.         break;
  124.     case DATA_SPAN:
  125.         printf("Span {%d, %u}\n",
  126.                 Node->MinSpan,
  127.                 Node->MaxSpan);
  128.         break;
  129.     case DATA_STRING:
  130.         printf("'%s'\n",
  131.                 Node->data.MatchStr,
  132.                 Node->SubExprNo);
  133.         break;
  134.     case DATA_SET:
  135.         printf("[");
  136.         for (j = 0; j < 128; j++)
  137.             if ( InSet(Node->data.CSet, (char) j) )
  138.             {
  139.                 if (j < 32 || j > 127)
  140.                     printf("\\x%02x");
  141.                 else
  142.                     putchar( (char) j );
  143.             }
  144.         printf("]  %d\n", Node->SubExprNo);
  145.         break;
  146.     case NODE_TYPE_NOT_SET:
  147.     default:
  148.         printf(">>>> ERROR !, no node type set.\n");
  149.         break;
  150.     }
  151.  
  152.     /*  Now print left child.   */
  153.     if ( Node->Left )
  154.         PrtReExpr(Node->Left, Level + 1);
  155. }
  156.  
  157. #endif
  158.  
  159. /*-----------------------------------------------------------------------------
  160. | Routine   :   AllocRegExpNode() --- Allocate a regular expression node.
  161. |
  162. | Returns   :   Returns a pointer to the newly allocated regular expression
  163. |               node.
  164. -----------------------------------------------------------------------------*/
  165.  
  166. static
  167. REG_EXP_NODE    *AllocRegExpNode(void)
  168. {
  169.     auto        REG_EXP_NODE    *New;
  170.     extern      FILE            *ErrFile;
  171.  
  172.     /*  Allocate the node.  */
  173.     if ((New = (REG_EXP_NODE *) calloc(1, sizeof( REG_EXP_NODE ))) == NULL)
  174.     {
  175.         fprintf(ErrFile,
  176.                 "%s %d : Out of memory.\n",
  177.                 __FILE__,
  178.                 __LINE__);
  179.         exit( 1 );
  180.     }
  181.     return( New );
  182. }
  183.  
  184. /*-----------------------------------------------------------------------------
  185. | Routine   :   GetInt() --- Get an integer number for the case of
  186. |               regular expression enumeration.
  187. |
  188. | Inputs    :   Str     - Pointer to string to get number from.
  189. | Outputs   :   Str     - Pointer to first character in string after number.
  190. |
  191. | Returns   :   Returns the integer read from the string.
  192. -----------------------------------------------------------------------------*/
  193.  
  194. static
  195. int     GetInt(char **Str)
  196. {
  197.     auto        int     i;
  198.  
  199.     /*  Strip white space.  */
  200.     while (**Str == ' ' || **Str == '\t' || **Str == '\n')
  201.         (*Str)++;
  202.  
  203.     /*  Get number. */
  204.     i = 0;
  205.     while ( InSet(DecSet, **Str) )
  206.         i = i * 10 + (*(*Str)++ - '0');
  207.  
  208.     /*  Strip trailing white space. */
  209.     while (**Str == ' ' || **Str == '\t' || **Str == '\n')
  210.         (*Str)++;
  211.  
  212.     /*  Return number.  */
  213.     return( i );
  214. }
  215.  
  216. /*-----------------------------------------------------------------------------
  217. | Routine   :   EnumOp() --- Get the enumeration modifer.
  218. |               node.
  219. |
  220. | Inputs    :   Str     - Pointer to enumeration operator.
  221. |               Root    - Pointer to regular expression node.
  222. | Outputs   :   Str     - Pointer after enumeration operator.
  223. |
  224. | Note      :   A value of zero for maximum span value indicates ANY
  225. |               number.
  226. -----------------------------------------------------------------------------*/
  227.  
  228. static
  229. void    EnumOp(char         **Str,
  230.                REG_EXP_NODE *Root)
  231. {
  232.     extern      FILE    *ErrFile;
  233.  
  234.     /*  Set up the operator and enumerator values.  */
  235.     switch ( *(*Str)++ )
  236.     {
  237.     case '+':
  238.         Root->MinSpan = 1;
  239.         Root->MaxSpan = ~0;
  240.         break;
  241.     case '*':
  242.         Root->MinSpan = 0;
  243.         Root->MaxSpan = ~0;
  244.         break;
  245.     case '?':
  246.         Root->MinSpan = 0;
  247.         Root->MaxSpan = 1;
  248.         break;
  249.     case '{':
  250.         /*  Get specifically enumerated span.   */
  251.         Root->MinSpan = GetInt( Str );
  252.         Root->MaxSpan = Root->MinSpan;
  253.  
  254.         /*  Is there a maximum number of characters?    */
  255.         if (**Str == ',')
  256.         {
  257.             /*  Get maximum span.   */
  258.             (*Str)++;
  259.  
  260.             /*  Strip white space.  */
  261.             while (**Str == ' ' || **Str == '\t' || **Str == '\n')
  262.                 (*Str)++;
  263.  
  264.             /*  Set to maximum, or get maximum. */
  265.             if (**Str == '}')
  266.                 Root->MaxSpan = ~0;
  267.             else if ( InSet(DecSet, **Str) )
  268.                 Root->MaxSpan = GetInt( Str );
  269.         }
  270.  
  271.         /*  Check for end brace.    */
  272.         if (**Str != '}')
  273.         {
  274.             fprintf(ErrFile,
  275.                     "%s %d : Error - missing '}' in regular expression.\n",
  276.                     __FILE__,
  277.                     __LINE__);
  278.             exit( 1 );
  279.         }
  280.         (*Str)++;
  281.         break;
  282.     }
  283. }
  284.  
  285. /*-----------------------------------------------------------------------------
  286. | Routine   :   Unary() --- Unary Operations.
  287. |
  288. | Inputs    :   Str - Pointer to current character in source RE string.
  289. |
  290. | Returns   :   Pointer to regular expression node.
  291. -----------------------------------------------------------------------------*/
  292.  
  293. static
  294. REG_EXP_NODE    *Unary(char **Str)
  295. {
  296.     auto        REG_EXP_NODE    *Node;
  297.     auto        char            Buffer[256];
  298.     auto        char            *Tmp;
  299.     extern      FILE            *ErrFile;
  300.  
  301.     /*  Get the regular expression atoms.   */
  302.     switch ( **Str )
  303.     {
  304.     case '.':
  305.         /*  Allocate a regular expression node. */
  306.         (*Str)++;
  307.         Node = AllocRegExpNode();
  308.         Node->NodeType = DATA_ANY;
  309.         break;
  310.     case '[':
  311.         /*  Allocate a regular expression node. */
  312.         Node = AllocRegExpNode();
  313.  
  314.         /*  Allocate a set. */
  315.         if ((Node->data.CSet = (SET_TYPE *) calloc(1, SET_SIZE *
  316.         sizeof( SET_TYPE ))) == NULL)
  317.         {
  318.             fprintf(ErrFile,
  319.                     "%s %d : Out of memory.\n",
  320.                     __FILE__,
  321.                     __LINE__);
  322.             exit( 1 );
  323.         }
  324.  
  325.         /*  Create the set. */
  326.         (*Str)++;
  327.         CrtSet(Str, Node->data.CSet);
  328.         Node->NodeType = DATA_SET;
  329.         break;
  330.     case '(':
  331.         /*  Skip parentheses. */
  332.         (*Str)++;
  333.  
  334.         /*  Allocate a regular expression node. */
  335.         Node = AllocRegExpNode();
  336.         Node->NodeType = OP_L_PAREN;
  337.  
  338.         /*  Save the sub expression number. */
  339.         if (SubExprNo > MAX_SUB_EXPRS)
  340.         {
  341.             fprintf(ErrFile,
  342.                     "%s %d : Error - To many sub-expressions.\n",
  343.                     __FILE__,
  344.                     __LINE__);
  345.             exit( 1 );
  346.         }
  347.         Node->SubExprNo = SubExprNo++;
  348.  
  349.         /*  Get sub expression. */
  350.         Node->Right = Alternation( Str );
  351.  
  352.         /*  Check for end parentheses.  */
  353.         if (**Str != ')')
  354.         {
  355.             fprintf(ErrFile,
  356.                     "%s %d : Error - missing ')' in regular expression.\n",
  357.                     __FILE__,
  358.                     __LINE__);
  359.             exit( 1 );
  360.         }
  361.         (*Str)++;
  362.         break;
  363.     default:
  364.         /*  Check for badly formed regular expression.  */
  365.         if (InSet(SpecSet, **Str) || InSet(PostSet, **Str))
  366.         {
  367.             fprintf(ErrFile,
  368.                     "%s %d : Error - badly formed regular expression.\n",
  369.                     __FILE__,
  370.                     __LINE__);
  371.             fprintf(ErrFile,
  372.                     "\tUnexpected character '%c'\n",
  373.                     **Str);
  374.             exit( 1 );
  375.         }
  376.  
  377.         /*  Allocate a regular expression node. */
  378.         Node = AllocRegExpNode();
  379.  
  380.         /*  Get characters while they are not in the set of special
  381.         *   characters.
  382.         */
  383.         for (Tmp = Buffer; **Str; )
  384.             if (**Str == '\\' && (*Str)[1])
  385.             {
  386.                 *Tmp++ = *++*Str;
  387.                 ++*Str;
  388.             }
  389.             else if (InSet(SpecSet, **Str) || InSet(PostSet, **Str))
  390.                 break;
  391.             else
  392.                 *Tmp++ = *(*Str)++;
  393.         *Tmp = '\0';
  394.         Node->NodeType = DATA_STRING;
  395.  
  396.         /*  Duplicate the string and add to the node.   */
  397.         if ((Node->data.MatchStr = StrDup( Buffer )) == NULL)
  398.         {
  399.             fprintf(ErrFile,
  400.                     "%s %d : Out of memory.\n",
  401.                     __FILE__,
  402.                     __LINE__);
  403.             exit( 1 );
  404.         }
  405.         break;
  406.     }
  407.  
  408.     /*  Return a pointer to the new node.   */
  409.     return( Node );
  410. }
  411.  
  412. /*-----------------------------------------------------------------------------
  413. | Routine   :   Enumerate() --- Enumerate a regular expression.
  414. |
  415. | Inputs    :   Str - Pointer to current character in source RE string.
  416. |
  417. | Returns   :   Pointer to regular expression node.
  418. -----------------------------------------------------------------------------*/
  419.  
  420. static
  421. REG_EXP_NODE    *Enumerate(char **Str)
  422. {
  423.     auto    REG_EXP_NODE    *Node;
  424.     auto    REG_EXP_NODE    *New;
  425.     extern  FILE            *ErrFile;
  426.  
  427.     /*  Get the regular expression. */
  428.     Node = Unary( Str );
  429.  
  430.     /*  Test for enumeration.   */
  431.     if ( InSet(PostSet, **Str) )
  432.     {
  433.         /*  Check for the special case of enumerating a '.' */
  434.         if (Node->NodeType == DATA_ANY)
  435.         {
  436.             /*  Modify it to be a DATA_SPAN type.   */
  437.             Node->NodeType = DATA_SPAN;
  438.         }
  439.         else if (Node->NodeType == OP_L_PAREN)
  440.         {
  441.             fprintf(ErrFile,
  442.                     "%s %d : Error, can not enumerate a sub expression.\n",
  443.                     __FILE__,
  444.                     __LINE__);
  445.             exit( 1 );
  446.         }
  447.         else
  448.         {
  449.             /*  Allocate an enumeration node.   */
  450.             New = AllocRegExpNode();
  451.             New->Right = Node;
  452.             New->NodeType = OP_ENUM;
  453.             Node = New;
  454.         }
  455.  
  456.         /*  Determine enumeration value.    */
  457.         EnumOp(Str, Node);
  458.     }
  459.     return( Node );
  460. }
  461.  
  462. /*-----------------------------------------------------------------------------
  463. | Routine   :   Catenation() --- Concatenate regular expressions.
  464. |
  465. | Inputs    :   Str - Pointer to current character in source RE string.
  466. |
  467. | Returns   :   Pointer to regular expression node.
  468. -----------------------------------------------------------------------------*/
  469.  
  470. static
  471. REG_EXP_NODE    *Catenation(char    **Str)
  472. {
  473.     auto        REG_EXP_NODE    *Root;
  474.     auto        REG_EXP_NODE    *SubExpr;
  475.     auto        REG_EXP_NODE    *Prev;
  476.     auto        REG_EXP_NODE    *Next;
  477.  
  478.     /*  Loop, getting concatenations (and operation) of regular
  479.     *   expressions seperated by OR's.
  480.     */
  481.     Prev = Root = NULL;
  482.     for ( ; ; )
  483.     {
  484.         /*  Get next sub expression.    */
  485.         SubExpr = Enumerate( Str );
  486.  
  487.         /*  Determine type of action to take.   */
  488.         if (**Str && **Str != '|' && **Str != ')' && **Str != '$')
  489.         {
  490.             /*  Create new node.    */
  491.             Next = AllocRegExpNode();
  492.             Next->Left = SubExpr;
  493.             Next->NodeType = OP_AND;
  494.  
  495.             /*  Link to old node.   */
  496.             if ( Prev )
  497.                 Prev->Right = Next;
  498.             else
  499.                 Root = Next;
  500.             Prev = Next;
  501.         }
  502.         else
  503.         {
  504.             /*  Determine final link type.  */
  505.             if ( Prev )
  506.                 Prev->Right = SubExpr;
  507.             else
  508.                 Root = SubExpr;
  509.  
  510.             /*  End loop.   */
  511.             break;
  512.         }
  513.     }
  514.  
  515.     /*  Return a pointer to the root node.  */
  516.     return( Root );
  517. }
  518.  
  519. /*-----------------------------------------------------------------------------
  520. | Routine   :   Anchor() --- Parse the two anchoring unary operators.
  521. |
  522. | Inputs    :   Str     - Regular expression source string.
  523. |
  524. | Returns   :   Returns a pointer to the compiled regular expression.
  525. -----------------------------------------------------------------------------*/
  526.  
  527. static
  528. REG_EXP_NODE    *Anchor(char    **Str)
  529. {
  530.     auto        REG_EXP_NODE    *Root;
  531.     auto        REG_EXP_NODE    *Node;
  532.  
  533.     /*  Check for begining of line anchor.  */
  534.     if (**Str == '^')
  535.     {
  536.         /*  Next character. */
  537.         (*Str)++;
  538.  
  539.         /*  Allocate a node.    */
  540.         Root = AllocRegExpNode();
  541.         Root->NodeType = DATA_LEFT_ANCHOR;
  542.  
  543.         /*  Get expression. */
  544.         Root->Right = Catenation( Str );
  545.     }
  546.     else
  547.         Root = Catenation( Str );
  548.  
  549.     /*  Check for end of line anchor.   */
  550.     if (**Str == '$')
  551.     {
  552.         /*  Next character. */
  553.         (*Str)++;
  554.  
  555.         /*  Allocate a node.    */
  556.         Node = AllocRegExpNode();
  557.         Node->NodeType = DATA_RIGHT_ANCHOR;
  558.         Node->Right = Root;
  559.         Root = Node;
  560.     }
  561.  
  562.     /*  Return regular expression.  */
  563.     return( Root );
  564. }
  565.  
  566. /*-----------------------------------------------------------------------------
  567. | Routine   :   Alternation() --- Parse an alternation expression.
  568. |
  569. | Inputs    :   Str - Pointer to current character in source RE string.
  570. |
  571. | Returns   :   Pointer to regular expression node.
  572. -----------------------------------------------------------------------------*/
  573.  
  574. static
  575. REG_EXP_NODE    *Alternation(char   **Str)
  576. {
  577.     auto        REG_EXP_NODE    *Root;
  578.     auto        REG_EXP_NODE    *New;
  579.  
  580.     /*  Get a concatenation of regular expressions. */
  581.     Root = Anchor( Str );
  582.  
  583.     /*  Loop, getting concatenations (and operation) of regular
  584.     *   expressions seperated by OR's.
  585.     */
  586.     while (**Str == '|')
  587.     {
  588.         /*  Next character. */
  589.         (*Str)++;
  590.  
  591.         /*  Allocate a node.    */
  592.         New = AllocRegExpNode();
  593.         New->Left = Root;
  594.         New->NodeType = OP_OR;
  595.  
  596.         /*  Get right hand of expression.   */
  597.         New->Right = Anchor( Str );
  598.         Root = New;
  599.     }
  600.  
  601.     /*  Return root of regular expression tree. */
  602.     return( Root );
  603. }
  604.  
  605. /*-----------------------------------------------------------------------------
  606. | Routine   :   ReGraph() --- Convert a regular expression tree into a graph.
  607. |
  608. | Inputs    :   Node    - Regular expression tree node.
  609. |
  610. | Returns   :   Returns a pointer to the compiled regular expression.
  611. -----------------------------------------------------------------------------*/
  612.  
  613. static
  614. REG_EXP_NODE    *ReGraph(REG_EXP_NODE   *Node,
  615.                          REG_EXP_NODE   *Link)
  616. {
  617.     auto        REG_EXP_NODE    *RetLink;
  618.     auto        REG_EXP_NODE    *New;
  619.  
  620.     /*  Determine operation type.   */
  621.     switch ( Node->NodeType )
  622.     {
  623.     case OP_L_PAREN:
  624.         /*  Allocate an end of parentheses node.    */
  625.         New = AllocRegExpNode();
  626.         New->NodeType = OP_R_PAREN;
  627.         New->SubExprNo = Node->SubExprNo;
  628.         New->Right = Link;
  629.  
  630.         /*  Continue link.  */
  631.         Node->Right = ReGraph(Node->Right, New);
  632.         RetLink = Node;
  633.         break;
  634.     case OP_ENUM:
  635.         /*  Continue link.  */
  636.         Node->Left = Node->Right;
  637.         Node->Right = Link;
  638.         RetLink = Node;
  639.         break;
  640.     case OP_AND:
  641.         /*  Traverse right, returning a pointer that can be used to
  642.         *   link the tree into a graph.
  643.         */
  644.         RetLink = ReGraph(Node->Right, Link);
  645.  
  646.         /*  Go down left and link together. */
  647.         RetLink = ReGraph(Node->Left, RetLink);
  648.  
  649.         /*  Free AND node and return the link.  */
  650.         free( Node );
  651.         break;
  652.     case OP_OR:
  653.         /*  Allocate an end of or node. */
  654.         New = AllocRegExpNode();
  655.         New->NodeType = END_OR;
  656.         New->Right = Link;
  657.  
  658.         /*  Process both.   */
  659.         Node->Right = ReGraph(Node->Right, New);
  660.         Node->Left = ReGraph(Node->Left, New);
  661.  
  662.         /*  Return pointer to OR.   */
  663.         RetLink = Node;
  664.         break;
  665.     case DATA_LEFT_ANCHOR:
  666.         Node->Right = ReGraph(Node->Right, Link);
  667.         RetLink = Node;
  668.         break;
  669.     case DATA_RIGHT_ANCHOR:
  670.         /*  Allocate an end of parentheses node.    */
  671.         New = Node->Right;
  672.         Node->Right = Link;
  673.         RetLink = ReGraph(New, Node);
  674.         break;
  675.     case DATA_ANY:
  676.     case DATA_SPAN:
  677.     case DATA_STRING:
  678.     case DATA_SET:
  679.         Node->Right = Link;
  680.         RetLink = Node;
  681.     }
  682.  
  683.     /*  Return a pointer to the tail end of the graph so far.   */
  684.     return( RetLink );
  685. }
  686.  
  687. /*-----------------------------------------------------------------------------
  688. | Routine   :   ReCompile() --- Compile a regular expression.
  689. |
  690. | Inputs    :   Str     - Regular expression source string.
  691. |
  692. | Returns   :   Returns a pointer to the compiled regular expression.
  693. -----------------------------------------------------------------------------*/
  694.  
  695. REG_EXP_NODE    *ReCompile(char *Str)
  696. {
  697.     auto        REG_EXP_NODE    *Root;
  698.  
  699.     /*  Construct sets, if not already constructed. */
  700.     if (ReInitFlag == 0)
  701.     {
  702.         auto    char    **Str;
  703.  
  704.         /*  Create the sets.    */
  705.         Str = &SpecStr;
  706.         CrtSet(Str, SpecSet);
  707.         Str = &PostFixStr;
  708.         CrtSet(Str, PostSet);
  709.         Str = &DecStr;
  710.         CrtSet(Str, DecSet);
  711.  
  712.         /*  We have initialized, so set flag saying so. */
  713.         ReInitFlag = 1;
  714.     }
  715.  
  716.     /*  Check for leading anchor.   */
  717.     SubExprNo = 1;
  718.     Root = Alternation( &Str );
  719.  
  720.      /*  Print the regular expression tree.  */
  721. #if defined( RE_TEST )
  722.     PrtReExpr(Root, 0);
  723. #endif
  724.  
  725.     /*  Convert to a graph. */
  726.     Root = ReGraph(Root, NULL);
  727.  
  728.     /*  Return pointer to regular expression.   */
  729.     return( Root );
  730. }
  731.  
  732. /*-----------------------------------------------------------------------------
  733. | Routine   :   FreeReExpr() --- Free the memory of a regular expression
  734. |               graph memory.
  735. |
  736. | Inputs    :   ReExpr  - Regular expression digraph root.
  737. -----------------------------------------------------------------------------*/
  738.  
  739. REG_EXP_NODE    *FreeReExpr(REG_EXP_NODE    *ReExpr)
  740. {
  741.     auto    REG_EXP_NODE    *Node;
  742.     auto    REG_EXP_NODE    *EndOr;
  743.     extern  FILE            *ErrFile;
  744.  
  745.     /*  Free the different node types.  */
  746.     while (ReExpr && ReExpr->NodeType != END_OR)
  747.     {
  748.         /*  Get pointer to next node.   */
  749.         Node = ReExpr->Right;
  750.  
  751.         /*  Select operation on node type.  */
  752.         switch ( ReExpr->NodeType )
  753.         {
  754.         case OP_ENUM:
  755.             (void) FreeReExpr( ReExpr->Left );
  756.             break;
  757.         case OP_OR:
  758.             /*  Free to end of OR branch.   */
  759.             (void) FreeReExpr( ReExpr->Right );
  760.  
  761.             /*  Free to end of OR branch, and get pointer to next
  762.             *   node.
  763.             */
  764.             EndOr = FreeReExpr( ReExpr->Left );
  765.             Node = EndOr->Right;
  766.             free( EndOr );
  767.             break;
  768.         case DATA_STRING:
  769.             free( ReExpr->data.MatchStr );
  770.             break;
  771.         case DATA_SET:
  772.             free( ReExpr->data.CSet );
  773.             break;
  774.         case OP_AND:
  775.         case OP_L_PAREN:
  776.         case OP_R_PAREN:
  777.         case DATA_LEFT_ANCHOR:
  778.         case DATA_RIGHT_ANCHOR:
  779.         case DATA_ANY:
  780.         case DATA_SPAN:
  781.             break;
  782.         default:
  783.             fprintf(ErrFile,
  784.                     "%s %d : Error - illegal regular expression node type.\n",
  785.                     __FILE__,
  786.                     __LINE__);
  787.             exit( 1 );
  788.         }
  789.  
  790.         /*  Move along. */
  791.         free( ReExpr );
  792.         ReExpr = Node;
  793.     }
  794.  
  795.     /*  Return pointer to end of chain. */
  796.     return( ReExpr );
  797. }
  798.