home *** CD-ROM | disk | FTP | other *** search
/ Usenet 1994 January / usenetsourcesnewsgroupsinfomagicjanuary1994.iso / sources / misc / volume36 / unpost / part05 / rematch.c < prev    next >
Encoding:
C/C++ Source or Header  |  1993-04-18  |  12.9 KB  |  411 lines
  1. /******************************************************************************
  2. * Module    :   Regular Expression Matching.
  3. *
  4. * Author    :   John W. M. Stevens.
  5. ******************************************************************************/
  6.  
  7. #include    "compiler.h"
  8.  
  9. #include    "sets.h"
  10. #include    "regexp.h"
  11. #include    "utils.h"
  12.  
  13. /*  Define sub expression list. */
  14. typedef struct  {
  15.     char        *Start;         /*  Start of sub-string in source.  */
  16.     char        *End;           /*  End of sub-string in source.  */
  17.     char        *SubStr;        /*  Pointer to sub-string.          */
  18. } SUB_EXPR;
  19. static  SUB_EXPR    SubExprs[MAX_SUB_EXPRS + 1];
  20.  
  21. static  CASE_CMP    CmpCase = CASE_SENSITIVE;
  22.  
  23. /*-----------------------------------------------------------------------------
  24. | Routine   :   ExtSubStrs() --- Extract the sub-strings from the string to
  25. |               match against.
  26. -----------------------------------------------------------------------------*/
  27.  
  28. static
  29. void    ExtSubStrs(void)
  30. {
  31.     register    int             i;
  32.     register    int             StrLen;
  33.     auto        char            *Str;
  34.     extern      FILE            *ErrFile;
  35.  
  36.     /*  Extract all sub strings from the source string. */
  37.     for (i = 0; i <= MAX_SUB_EXPRS; i++)
  38.     {
  39.         /*  Report run time error.  */
  40.         if (SubExprs[i].Start == NULL || SubExprs[i].End == NULL)
  41.             continue;
  42.         else if (SubExprs[i].Start > SubExprs[i].End)
  43.         {
  44.             fprintf(ErrFile,
  45.                     "%s %d : Error - sub expression #%d extraction failed.\n",
  46.                     __FILE__,
  47.                     __LINE__,
  48.                     i);
  49.             exit( 1 );
  50.         }
  51.  
  52.         /*  Determine length of string. */
  53.         for (StrLen = 0, Str = SubExprs[i].Start;
  54.              Str != SubExprs[i].End;
  55.              StrLen++, Str++
  56.             )
  57.              ;
  58.  
  59.         /*  Allocate space for the string.  */
  60.         if ((Str = (char *) calloc(1, StrLen + 1)) == NULL)
  61.         {
  62.             fprintf(ErrFile,
  63.                     "%s %d : Out of memory.\n",
  64.                     __FILE__,
  65.                     __LINE__);
  66.             exit( 1 );
  67.         }
  68.  
  69.         /*  Copy the string to the new space.   */
  70.         MemCopy(Str, SubExprs[i].Start, StrLen);
  71.         Str[StrLen] = '\0';
  72.  
  73.         /*  Add string to sub expression string buffer. */
  74.         SubExprs[i].SubStr = Str;
  75.     }
  76. }
  77.  
  78. /*-----------------------------------------------------------------------------
  79. | Routine   :   ReStrCmp() --- Regular expression string compare.
  80. |
  81. | Inputs    :   Str     - Pointer to string to attempt to match.
  82. |               ReStr   - Pointer to regular expression string.
  83. |
  84. | Returns   :   Returns zero for no match, non-zero for a match.
  85. -----------------------------------------------------------------------------*/
  86.  
  87. static
  88. int     ReStrCmp(char   *Str,
  89.                  char   *ReStr)
  90. {
  91.     /*  While not end of regular expression string, compare characters. */
  92.     while ( *ReStr )
  93.     {
  94.         /*  If the characters do not match, return no match.    */
  95.         if (CmpCase == IGN_CASE)
  96.         {
  97.             /*  Compare characters regardless of case.  */
  98.             if (tolower( *ReStr ) != tolower( *Str ))
  99.                 return( 0 );
  100.  
  101.             /*  They match.  Increment pointers to next characters. */
  102.             ReStr++;
  103.             Str++;
  104.         }
  105.         else if (*ReStr++ != *Str++)
  106.             return( 0 );
  107.     }
  108.     return( 1 );
  109. }
  110.  
  111. /*-----------------------------------------------------------------------------
  112. | Routine   :   ReData() --- Evaluate a regular expression data node.
  113. |
  114. | Inputs    :   SrcStart    - Start of source string (for left anchor
  115. |                             comparisons).
  116. |               Str         - Pointer to string to attempt to match.
  117. |               ReExpr      - Pointer to regular expression node.
  118. | Outputs   :   Str         - Pointer to string after matched portion, or
  119. |                             unchanged since input, if no match.
  120. |               Srch        - Pointer to search description structure.
  121. |
  122. | Returns   :   Returns 1 for a match, 0 for no match.
  123. -----------------------------------------------------------------------------*/
  124.  
  125. static
  126. int     ReData(char         *SrcStart,
  127.                char         **Str,
  128.                REG_EXP_NODE *ReExpr)
  129. {
  130.     register    int     Match;
  131.     extern      FILE    *ErrFile;
  132.  
  133.     /*  Attempt match.  */
  134.     switch ( ReExpr->NodeType )
  135.     {
  136.     case DATA_STRING:
  137.         /*  Compare string. */
  138.         if ((Match = ReStrCmp(*Str, ReExpr->data.MatchStr)) != 0)
  139.         {
  140.             /*  Bump the source string pointer. */
  141.             (*Str) += strlen( ReExpr->data.MatchStr );
  142.         }
  143.         break;
  144.     case DATA_SET:
  145.         /*  Is the current character a member of the set?  (Don't
  146.         *   forget that negated sets are already negated at this
  147.         *   point.)
  148.         */
  149.         if ((Match = InSet(ReExpr->data.CSet, **Str)) != 0)
  150.         {
  151.             /*  Bump source string pointer. */
  152.             (*Str)++;
  153.         }
  154.         break;
  155.     case DATA_ANY:
  156.         /*  Match any character except end of line. */
  157.         if ((Match = **Str && **Str != '\n') != 0)
  158.         {
  159.             /*  Bump source string pointer. */
  160.             (*Str)++;
  161.         }
  162.         break;
  163.     case DATA_LEFT_ANCHOR:
  164.         /*  Is this the start of the line?  */
  165.         Match = *Str == SrcStart;
  166.         break;
  167.     case DATA_RIGHT_ANCHOR:
  168.         /*  Is the current character an end of line character?  */
  169.         Match = **Str == '\n' || **Str == '\0';
  170.         break;
  171.     default:
  172.         fprintf(ErrFile,
  173.                 "%s %d : Error - illegal regular expression node type.\n",
  174.                 __FILE__,
  175.                 __LINE__);
  176.         exit( 1 );
  177.     }
  178.  
  179.     /*  Return match state. */
  180.     return( Match );
  181. }
  182.  
  183. /*-----------------------------------------------------------------------------
  184. | Routine   :   ReOp() --- Execute a regular expression operator.
  185. |
  186. | Inputs    :   SrcStart    - Start of source string (for left anchor
  187. |                             comparisons).
  188. |               Str         - Pointer to string to attempt to match.
  189. |               ReExpr      - Pointer to regular expression node.
  190. | Outputs   :   Str         - Pointer to string after matched portion, or
  191. |                             unchanged since input, if no match.
  192. |               Cont        - Current regular expression node pointer.
  193. |
  194. | Returns   :   Returns 1 for a match, 0 for no match.
  195. -----------------------------------------------------------------------------*/
  196.  
  197. static
  198. int     ReOp(char           *SrcStart,
  199.              char           **Str,
  200.              REG_EXP_NODE   *ReExpr,
  201.              REG_EXP_NODE   **Cont)
  202. {
  203.     register    int             i;
  204.     register    int             Match;
  205.     auto        char            *ChkPt;
  206.     auto        REG_EXP_NODE    *Tmp;
  207.     auto        REG_EXP_NODE    *Node;
  208.     extern      FILE            *ErrFile;
  209.  
  210.     /*  Do operations.  */
  211.     do
  212.     {
  213.         /*  Attempt match.  */
  214.         switch ( ReExpr->NodeType )
  215.         {
  216.         case OP_OR:
  217.             /*  Save check point for backtracking.  */
  218.             ChkPt = *Str;
  219.  
  220.             /*  Attempt left branch first.  */
  221.             if ((Match = ReOp(SrcStart,
  222.                               Str,
  223.                               ReExpr->Left,
  224.                               &Node)) == 0)
  225.             {
  226.                 /*  Attempt to match the right hand branch. */
  227.                 *Str = ChkPt;
  228.                 Match = ReOp(SrcStart, Str, ReExpr->Right, &Node);
  229.             }
  230.  
  231.             /*  Get end of OR.  */
  232.             ReExpr = Node;
  233.             break;
  234.         case DATA_SPAN:
  235.             /*  Scan for at least the minimum number of characters. */
  236.             for (Match = 1, i = 0; i < ReExpr->MinSpan; i++)
  237.                 if (**Str == '\0' || **Str == '\n')
  238.                 {
  239.                     Match = 0;
  240.                     break;
  241.                 }
  242.             if (! Match)
  243.                 break;
  244.  
  245.             /*  Skip over all control node types to see if there is
  246.             *   a terminating expression for this span.
  247.             */
  248.             for (Tmp = ReExpr->Right;
  249.                  Tmp &&
  250.                  (Tmp->NodeType == OP_L_PAREN   ||
  251.                   Tmp->NodeType == OP_R_PAREN   ||
  252.                   Tmp->NodeType == END_OR);
  253.                  Tmp = Tmp->Right)
  254.                 ;
  255.  
  256.             /*  If there is no span terminating expression, then we
  257.             *   automatically match to end of line.
  258.             */
  259.             if (Tmp == NULL)
  260.             {
  261.                 /*  Scan to end of input string.    */
  262.                 for ( ; **Str; ++*Str)
  263.                     ;
  264.  
  265.                 /*  This is a definite match.   */
  266.                 Match = 1;
  267.                 break;
  268.             }
  269.  
  270.             /*  We matched at least the minimum number.  Now attempt the
  271.             *   maximum number.
  272.             */
  273.             for (ChkPt = *Str;
  274.                  *ChkPt && i < ReExpr->MaxSpan;
  275.                  ChkPt++, i++)
  276.             {
  277.                 /*  Search forward until a match is found, or the
  278.                 *   max number of any character has been spanned.
  279.                 */
  280.                 *Str = ChkPt;
  281.                 if ((Match = ReOp(SrcStart,
  282.                                   Str,
  283.                                   ReExpr->Right,
  284.                                   &Node)) != 0)
  285.                 {
  286.                     break;
  287.                 }
  288.             }
  289.  
  290.             /*  Check for a match.  */
  291.             if (i >= ReExpr->MaxSpan)
  292.                 Match = 0;
  293.             ReExpr = Node;
  294.             break;
  295.         case OP_ENUM:
  296.             /*  Match the correct number of sub-expressions.    */
  297.             for (i = 0; i < ReExpr->MaxSpan; i++)
  298.             {
  299.                 /*  Attempt data match. */
  300.                 if ((Match = ReData(SrcStart,
  301.                                     Str,
  302.                                     ReExpr->Left)) == 0)
  303.                 {
  304.                     /*  Have we at least the minimum?   */
  305.                     if (i >= ReExpr->MinSpan)
  306.                         Match = 1;
  307.                     break;
  308.                 }
  309.             }
  310.             break;
  311.         case OP_L_PAREN:
  312.             /*  Save start of sub-expression.   */
  313.             SubExprs[ReExpr->SubExprNo].Start = *Str;
  314.             Match = 1;
  315.             break;
  316.         case OP_R_PAREN:
  317.             /*  Save start of sub-expression.   */
  318.             SubExprs[ReExpr->SubExprNo].End = *Str;
  319.             Match = 1;
  320.             break;
  321.          default:
  322.             Match = ReData(SrcStart, Str, ReExpr);
  323.             break;
  324.         }
  325.  
  326.         /*  Check for end.  */
  327.         if (ReExpr != NULL)
  328.             ReExpr = ReExpr->Right;
  329.  
  330.     } while (Match && ReExpr && ReExpr->NodeType != END_OR);
  331.  
  332.     /*  Return match.   */
  333.     *Cont = ReExpr;
  334.     return( Match );
  335. }
  336.  
  337. /*-----------------------------------------------------------------------------
  338. | Routine   :   ReMatch() --- Regular expression match.
  339. |
  340. | Inputs    :   Str         - Pointer to string to attempt to match.
  341. |               Case        - Flag for case sensitivity.
  342. |               ReExpr      - Pointer to regular expression tree root.
  343. | Outputs   :   SubStrs     - Pointer to array of returned strings.
  344. |               NoSubStrs   - Size of returned string array.
  345. |
  346. | Returns   :   Returns zero for no match, non-zero for a match.
  347. -----------------------------------------------------------------------------*/
  348.  
  349. int     ReMatch(char            *Str,
  350.                 CASE_CMP        Case,
  351.                 REG_EXP_NODE    *ReExpr,
  352.                 char            ***SubStrs)
  353. {
  354.     register    int             i;
  355.     register    int             Match;
  356.     auto        char            *tp;
  357.     auto        char            *Loop;
  358.     auto        REG_EXP_NODE    *Node;
  359.  
  360.     static      char        *RetStrs[MAX_SUB_EXPRS];
  361.     extern      FILE        *ErrFile;
  362.  
  363.     /*  Run list and free strings.  */
  364.     for (i = 1; i < MAX_SUB_EXPRS; i++)
  365.     {
  366.         /*  Free previous sub strings.  */
  367.         if (RetStrs[i] != NULL)
  368.             free( RetStrs[i] );
  369.  
  370.         /*  Initialize the sub expression list. */
  371.         RetStrs[i] = NULL;
  372.         SubExprs[i].Start = SubExprs[i].End = SubExprs[i].SubStr = NULL;
  373.     }
  374.  
  375.     /*  If the first node is a left anchor, no shifting is necesary.    */
  376.     tp = Str;
  377.     CmpCase = Case;
  378.     if (ReExpr->NodeType == DATA_LEFT_ANCHOR)
  379.         Match = ReOp(Str, &tp, ReExpr->Right, &Node);
  380.     else
  381.     {
  382.         /*  Search forward. */
  383.         for (Loop = Str; ; Loop++)
  384.         {
  385.             /*  Search for a match. */
  386.             tp = Loop;
  387.             if ((Match = ReOp(Str, &tp, ReExpr, &Node)) != 0)
  388.                 break;
  389.  
  390.             /*  Check for end of loop.  */
  391.             if (*Loop == '\0' || *Loop == '\n')
  392.                 break;
  393.         }
  394.     }
  395.  
  396.     /*  Create sub string array. */
  397.     if ( Match )
  398.     {
  399.         /*  Extract sub expression strings. */
  400.         ExtSubStrs();
  401.         for (i = 1; i < MAX_SUB_EXPRS; i++)
  402.             RetStrs[i] = SubExprs[i].SubStr;
  403.  
  404.         /*  Return sub string array.    */
  405.         *SubStrs = RetStrs;
  406.     }
  407.  
  408.     /*  Return match true or false. */
  409.     return( Match );
  410. }
  411.