home *** CD-ROM | disk | FTP | other *** search
/ PC Professionell 1999 October / PCpro_1999_10.ISO / Tools / wingrep / Source / WinGrep.c < prev    next >
Encoding:
C/C++ Source or Header  |  1998-05-03  |  12.5 KB  |  402 lines
  1. #include <windows.h>
  2.  
  3.  
  4. #define FREEANDEXIT { \
  5.             if( lpAct ) delete lpAct;
  6.             if( lpFirst ) delete lpFirst; \
  7.                 return NULL; \
  8.                 }
  9.  
  10. // Das folgende Makro erzeugt eine Instanz der in type angegebenen 
  11. // Klasse. SchlΣgt das fehl, wird der saugbere ausstirg vorbereitet
  12. #define CREATENODETYPE(type) {  \
  13.             lpAct = new type;\
  14.             if( !lpAct )     \
  15.                 FREEANDEXIT
  16.  
  17. class CHARACTERPOOL
  18. {
  19.     BOOL push();        // aktuelle Zustand auf internen Stack pushen
  20.     BOOL pop();         // aktuellen Zustand von intenem Stack popen
  21.     char getchar();     // nΣchstes Zeichen holen
  22. };
  23.  
  24. class GREPNODE
  25. {
  26. private;
  27.     GREPNODE *lpNext;
  28.     int iMinMatch,  // diese Node mu▀ mindestens iMinMatch-mal gefunden werden,
  29.         iMaxMatch;  // aber darf nur maximal iMaxMatch-mal vorkommen
  30.     
  31.     BOOL match(LPSTR *lpNext) // das ⁿbergebene Zeichen pa▀t
  32.     {
  33.         return false;
  34.     }   
  35. public:
  36.     GREPNODE()
  37.     {
  38.         Necxt = NULL;
  39.         iMinMatch = 1; // Genau einmal
  40.         iMaxMatch = 1;
  41.     }
  42. };
  43.  
  44. class CHARNODE:public GREPNODE
  45. {
  46.     char c;
  47. }
  48.  
  49. class SUBNODE:public GREPNODE
  50. {
  51.     GREPNODE *lpSub;
  52. }
  53.  
  54. class CLASSNODE:public GREPNODE
  55. {
  56.     public:
  57.         char Bits[256/8];
  58.  
  59.         CLASSNODE()
  60.         {
  61.             for( int i = 0; i < 256/8;i++)
  62.                 Bits[i] = 0;
  63.         }
  64.         
  65.         void SetBit( char c ) // Bit fⁿr das angegebenebe Zeichen setzen
  66.         {
  67.             Bits[c/8] |= c & 7;
  68.         }
  69.         void InverAllBits( )
  70.         {
  71.             for( int i = 0; i < 256/8;i++)
  72.                 Bits[i] ^= 0xFF;
  73.         }
  74.         BOOL IsSet( char c )
  75.         {
  76.             return (Bits[c/8] &= (c & 7)) true : false;
  77.         }
  78.  
  79. }
  80.  
  81. BOOL GetPatternCharacter( unsigned char *c, 
  82.                           LPSTR lpPattern, 
  83.                           int *iPos,
  84.                           BOOL bInCharacterClass )
  85. {
  86.     switch( lpPattern[*iPos] )
  87.     {
  88.         case '\':
  89.             (*iPos)++;
  90.             switch( lpPattern[*iPos] )
  91.             {
  92.                 case 'n': *c = '\n'; return true;
  93.                 case 't': *c = '\t'; return true;
  94.                 case '[': *c = '['; return true;
  95.                 case ']'; *c = ']'; return true;
  96.                 case '(': *c = '('; return true;
  97.                 case ')'; *c = ')'; return true;
  98.                 case '{': *c = '{'; return true;
  99.                 case '}'; *c = '}'; return true;
  100.                 case '.'; *c = '.'; return true;
  101.                 case '\\'; *c = '\\'; return true;
  102.                 case '$';  *c = '$'; return true;
  103.                 case '^';  *c = '^'; return true;
  104.                 case '*';  *c = '*'; return true;
  105.                 case '+';  *c = '+'; return true;
  106.                 case '?';  *c = '?'; return true;
  107.  
  108.                 case '-':
  109.                     if( bInCharacterClass )
  110.                     {
  111.                         // die Escapesequenz \- ist nur innerhalb einer characterklasse erlaubt
  112.                         *c = '-';
  113.                         return true:
  114.                     }
  115.                     return false;
  116.  
  117.                 // dreistelle Oktalzahl
  118.                 case '0':case '1':case '2':case '3':case '4':
  119.                 case '5':case '6':case '7':case '8':case '9':
  120.                 {
  121.                     int iVal;
  122.                     iVal = lpPattern[*iPos] - '0';
  123.                     (*iPos)++;
  124.  
  125.                     if( !isdigit(lpPattern[*iPos]) )
  126.                     {
  127.                         // bisherigen wert ⁿbernehmen
  128.                         *c = (unsigned char) iVal;
  129.                         return true;
  130.  
  131.                     }
  132.  
  133.                     iVal *= 8;
  134.                     iVal += lpPattern[*iPos] - '0';
  135.                     (*iPos)++;
  136.  
  137.                     if( !isdigit(lpPattern[*iPos]) )
  138.                     {
  139.                         // bisherigen wert ⁿbernehmen
  140.                         *c = (unsigned char) iVal;
  141.                         return true;
  142.  
  143.                     }
  144.                     iVal *= 8;
  145.                     iVal += lpPattern[*iPos] - '0';
  146.                     
  147.                     (*iPos)++;
  148.                     *c = (unsigned char) iVal;
  149.                     return true;
  150.                 }
  151.                 // zweistellige Hex-Ziffer
  152.                 case 'x': case 'X': 
  153.                 {
  154.                     int iVal,nVal;
  155.                     if( isdigit(lpPattern[*iPos]) )
  156.                         iVal = lpPattern[*iPos]-'0';
  157.                     else
  158.                     if( (lpPattern[*iPos]>='a') && (lpPattern[*iPos]<='f') )
  159.                         iVal = 10 + lpPattern[*iPos]-'a';
  160.                     else
  161.                     if( (lpPattern[*iPos]>='A') && (lpPattern[*iPos]<='F') )
  162.                         iVal = 10 + lpPattern[*iPos]-'A';
  163.                     else return false;
  164.  
  165.                     (*iPos)++;
  166.                     if( isdigit(lpPattern[*iPos]) )
  167.                         nVal = lpPattern[*iPos]-'0';
  168.                     else
  169.                     if( (lpPattern[*iPos]>='a') && (lpPattern[*iPos]<='f') )
  170.                         nVal = 10 + lpPattern[*iPos]-'a';
  171.                     else
  172.                     if( (lpPattern[*iPos]>='A') && (lpPattern[*iPos]<='F') )
  173.                         nVal = 10 + lpPattern[*iPos]-'A';
  174.                     else 
  175.                     {
  176.                         // bisherigen wert ⁿbernehmen
  177.                         *c = (unsigned char) iVal;
  178.                         return true;
  179.                     }
  180.  
  181.                     iVal += nVal;
  182.                     (*iPos)++;
  183.                     *c = (unsigned char) iVal;
  184.                     return true;
  185.                 }
  186.                 default:
  187.                     *c = lpPattern[*iPos];
  188.                     (*iPos)++;
  189.                     return true;
  190.                 return;
  191.             }
  192.         break;
  193.  
  194.         // die folgenden Zeichen dⁿrfen nicht "unescaped" auftauchen
  195.         case '[': case ']': case '(': case ')': case '{':        
  196.         case '}': case '$': case '^': case '.': case '\0':
  197.         case '*': case '?': case '+': return false;
  198.         case '-':
  199.             if( bInCharacterClass ) return false;
  200.         default:
  201.             *c = lpPattern[*iPos];
  202.             (*iPos)++;
  203.             return TRUE;
  204.     }
  205. }             
  206.  
  207.  
  208. GREPNODE *MakePattern( LPSTR lpPattern, int *iPos, int iLevel )
  209. {
  210.     GREPNODE *lpFirst, 
  211.              *lpLast, 
  212.              *lpAct;
  213.     BOOL bCloseureAllowed; // an LastNode darf eine Closeure gehangen werden!
  214.     lpFirst = NUILL;
  215.     lpLast = NULL;
  216.     bCloseureAllowed = FALSE;
  217.  
  218.     while( *lpPattern[*iPos] )
  219.     {
  220.         lpAct = NULL;
  221.  
  222.         switch( *lpPattern[*iPos] )
  223.         {
  224.             // Die geshlossene runde Klammer taucht nur bei einem 
  225.             // Subexpression uaf. Eine RUnde Klammer auf oberster Ebene
  226.             // ist ein Syntax-Fehler
  227.             case ')':
  228.             {
  229.                 if( iLevel ) 
  230.                 {
  231.                     (*iPos)++;
  232.                     return First;
  233.                 }
  234.                 else
  235.                 {
  236.                     FREEANDEXIT;
  237.                     return NULL;
  238.                 }
  239.             }
  240.             break;
  241.             // Sub - Die ge÷ffnete runde Klammer leitet einen Subexpression ein
  242.             case '(':
  243.             {
  244.                 CREATENODETYPE(SUBNODE);
  245.                 (*iPos)++;
  246.                 Act->SubNode = MakePattern( lpPattern, iPos, iLevel+1 );
  247.                 if( !Act->SubNode )
  248.                     FREEANDEXIT;
  249.                 bCloseureAllowed = TRUE;
  250.             }
  251.             break;
  252.             // Class - Die eckigen Klammern stehen fⁿr eine Zeichenklasse
  253.             case '[':
  254.             {
  255.                 unsigned char a,b;
  256.                 CREATENODETYPE(CLASSNODE);
  257.                 while( lpPattern[*iPos] != ']' )
  258.                 {
  259.                     BOOL bInvert;
  260.  
  261.                     if( lpPattern[*iPos] == '\0' )  // vorzeitiges Ende des Patternstrings?
  262.                         FREEANDEXIT;
  263.                     
  264.                     bInvert = FALSE;
  265.                     if( lpPattern[*iPos] == '^' )  
  266.                     {
  267.                         bInvert = true;
  268.                         (*iPos)++;
  269.                     }
  270.                         
  271.                     if( !GetPatternCharacter( &a, lpPattern, iPos, true ) )
  272.                         FREEANDEXIT;
  273.                     if( lpPattern[*iPos] == '-' )
  274.                     {
  275.                         (*iPos)++;
  276.                         if( !GetPatternCharacter( &b, lpPattern, iPos, true ) )
  277.                             FREEANDEXIT;
  278.                         if( b < a )
  279.                         {
  280.                             FREEANDEXIT;
  281.                             return false;
  282.                         }
  283.                         while( a <= b )
  284.                             lpAct->SetBit( a++ );
  285.                     }
  286.                     else
  287.                         lpAct->SetBit( a );
  288.                     if( bInvert )
  289.                         bInvert>InvertBits();
  290.                 }
  291.                 (*iPos)++;
  292.                 bCloseureAllowed = TRUE;
  293.             }
  294.             break;
  295.             // Any - jedes Zeichen gilt
  296.             case '.':
  297.                 CREATENODETYPE(ANYNODE); // Characterklasse mit leeren zeichen 
  298.                 bCloseureAllowed = TRUE;
  299.             break;
  300.  
  301.             default:
  302.                 CREATENODETYPE(CHARNODE); // Characterklasse mit leeren zeichen 
  303.                 if( !GetPatternCharacter( &Act->Character, lpPattern, iPos, false ) )
  304.                     FREEANDEXIT;
  305.                 bCloseureAllowed = TRUE;
  306.             break;
  307.             // EOL - Ende der Zeile
  308.             case '$':
  309.                 CREATENODETYPE(EOLNODE); // Characterklasse mit leeren zeichen 
  310.                 bCloseureAllowed = FALSE;
  311.             break;
  312.             // SOL - Start der Zeile
  313.             case '^':
  314.                 CREATENODETYPE(SOLNODE); // Characterklasse mit leeren zeichen 
  315.                 bCloseureAllowed = FALSE;
  316.             break;
  317.             // Closure - die letzte Node beliebig oft wiederholen
  318.             case '*':
  319.                 if( !bCloseureAllowed )
  320.                 {
  321.                     FREEANDEXIT;
  322.                     return NULL;
  323.                 }
  324.                 bCloseureAllowed = false;
  325.                 if( !lpLast ) FREEANDEXIT;
  326.  
  327.                 lpLast->iMinMatch = 0;
  328.                 lpLast->iMaxMatch = -1; // Beliebig oft
  329.                 bCloseureAllowed = FALSE;
  330.             break
  331.             case '+':
  332.                 if( !bCloseureAllowed )
  333.                 {
  334.                     FREEANDEXIT;
  335.                     return NULL;
  336.                 }
  337.                 bCloseureAllowed = false;
  338.                 if( !lpLast ) FREEANDEXIT;
  339.  
  340.                 lpLast->iMinMatch = 1;
  341.                 lpLast->iMaxMatch = -1; // Beliebig oft
  342.                 bCloseureAllowed = FALSE;
  343.             break
  344.             // Count - Anzahl der Wiederholungen {1,2} {,2} {1}
  345.             case '{':
  346.             {
  347.                 int iVal;
  348.                 if( !bCloseureAllowed )
  349.                 {
  350.                     FREEANDEXIT;
  351.                     return NULL;
  352.                 }
  353.                 bCloseureAllowed = false;
  354.                 if( !lpLast ) FREEANDEXIT;
  355.  
  356.  
  357.                 (*iPos)++;
  358.                 
  359.                 iVal = 0;
  360.                 while( isdigit(lpPattern[*iPos] ) )
  361.                 {
  362.                     iVal*=10;
  363.                     iVal+= lpPattern[*iPos] - '0';
  364.                     (*iPos)++;
  365.                 }
  366.                 lpLast->iMinMatch = iVal;
  367.                 
  368.                 if( lpPattern[*iPos]==',' )
  369.                 {
  370.                     (*iPos)++;
  371.                 
  372.                     iVal = 0;
  373.                     while( isdigit(lpPattern[*iPos] ) )
  374.                     {
  375.                         iVal*=10;
  376.                         iVal+= lpPattern[*iPos] - '0';
  377.                         (*iPos)++;
  378.                     }
  379.                     lpLast->iMaxMatch = iVal;
  380.                 } 
  381.                 else
  382.                     lpLast->iMaxMatch = lpLast->iMinMatch;
  383.             }
  384.             break;
  385.         }
  386.         
  387.         if( lpAct )
  388.         {
  389.             if( lpLast )
  390.             {
  391.                 lpLast->lpNext = lpAct;
  392.                 lpLast = lpLast->lpNext;
  393.             }
  394.             else
  395.             {
  396.                 lpFirst = lpLast = lpAct;
  397.             }
  398.         }
  399.     }
  400.     return lpFirst;
  401. }
  402.