65.9K
CodeProject 正在变化。 阅读更多。
Home

快速正则表达式

Martin Holzherr
starIconstarIconstarIconstarIcon
emptyStarIcon
starIcon

4.85/5 (18投票s)

2000年10月30日

viewsIcon

387914

downloadIcon

5163

将正则表达式编译成快速的自动机。

Sample Image - RexSearch.jpg

引言

正则表达式是描述字符串模式的公认方法。下面的正则表达式定义了一个浮点数，它有一个（可能为空的）整数部分，一个非空的小数部分和一个可选的指数部分。

[0-9]* \.[0-9]+ ([Ee](\+|-)?[0-9]+)?

解释和构建此类正则表达式的规则如下。正则表达式解析器接收正则表达式和源字符串作为参数，并返回第一个匹配项的源位置。正则表达式解析器要么在运行时解释搜索模式，要么将正则表达式编译成一种高效的内部形式（称为确定性有限自动机）。此处描述的正则表达式解析器属于第二类。除了速度相当快之外，它还支持正则表达式字典。通过定义 $Int= [0-9]、$Frac= \.[0-9]+ 和 $Exp= ([Ee](\+|-)?[0-9]+)，上述浮点数正则表达式可以缩写为 $Int* $Frac $Exp?。

接口

我将算法问题与接口问题分开了。文件 RexAlgorithm.h 和 RexAlgorithm.cpp 使用标准的 C++（依赖 STL）实现了正则表达式解析器，而文件 RexInterface.h 和 RexInterface.cpp 包含面向最终用户的接口。目前只有一个接口，由类 REXI_Search 实现。将来计划发布用于替换功能和编程语言扫描器的接口。

struct REXI_DefErr{
        enum{eNoErr,eErrInName,eErrInRegExp} eErrCode;
        string  strErrMsg;
        int     nErrOffset;
};
class REXI_Search : public REXI_Base
{ 
public:
    REXI_Search(char cEos='\0');

    REXI_DefErr
            AddRegDef   (string strName,string strRegExp);
    inline  REXI_DefErr  
            SetRegexp  (string strRegExp);
    bool    MatchHere   (const char*& rpcszSrc, int& nMatchLen,bool& bEos);
    bool    Find        (const char*& rpcszSrc, int& nMatchLen,bool& bEos);
private:
    bool    MatchHereImpl();
    int     m_nIdAnswer;
};

Example usage

int main(int argc, char* argv[])
{
    const char szTestSrc[]= "3.1415 is the same as 31415e-4";
    const int ncOk= REXI_DefErr::eNoErr;
    
    REXI_Search rexs; 
    REXI_DefErr err;
    err= rexs.AddRegDef("$Int","[0-9]+");  assert(err.eErrCode==ncOk);
    err= rexs.AddRegDef("$Frac","\\.[0-9]+"); assert(err.eErrCode==ncOk);
    err= rexs.AddRegDef("$Exp","([Ee](\\+|-)?[0-9]+)"); 
                                assert(err.eErrCode==ncOk);
    err= rexs.SetRegexp("($Int? $Frac $Exp?|$Int \\. $Exp?|$Int $Exp)[fFlL]?");
                                assert(err.eErrCode==ncOk);

    const char*     pCur= szTestSrc;
    int             nMatchLen;
    bool            bEosFound= false;
    cout    <<  "Source text is: \""    <<  szTestSrc   << "\"" <<  endl;
    while(rexs.Find(pCur,nMatchLen,bEosFound)){
           cout <<  "Floating point number found  at position "       
                <<  ((pCur-szTestSrc)-nMatchLen)    
                <<  " having length "  <<  nMatchLen  <<  endl;
    }
    int i;
    cin >> i;
    return 0;
}

性能问题

调用成员函数 REXI_Search::SetRegexp(strRegExp) 会涉及大量的计算。正则表达式 strRegExp 被分析，经过几个步骤后转换为编译形式。由于这种预处理工作（在解释型正则表达式解析器的情况下不需要），该正则表达式解析器仅在您将其应用于大型输入字符串或反复搜索同一个正则表达式时才显示其效率。一个典型的受益于此解析器所需预处理的应用程序是搜索目录中所有文件的实用程序。

限制

目前不支持 Unicode。这没有根本原因，我认为未来的版本会纠正这一点。我只是还没有找到一种支持 Unicode 的正则表达式编译后的有效表示方法。

构建正则表达式

正则表达式可以由字符和特殊符号构建。正则表达式与算术表达式之间存在一些相似之处。算术表达式最基本元素是数字和用括号括起来的表达式（）。正则表达式最基本元素是字符、用括号括起来的正则表达式（）和字符集。在下一个更高层级上，算术表达式具有 '*' 和 '/' 运算符，而正则表达式具有表示前面元素数量的运算符。

正则表达式最基本元素

  • 单个字符。 例如，“h”是一个正则表达式。在字符串“this home”中，它匹配“home”的开头。对于不可打印字符，必须使用 \xhh 的表示法（其中 h 表示十六进制数字）或 C 语言已知的转义序列 \n \r \t \v。由于字符 * + ? . | [ ] ( ) - $ ^ 在正则表达式中有特殊含义，因此必须使用转义序列来字面指定这些字符：\*  \+  \?  \.  \|  \[  \]  \(  \)  \-  \$  \^ 。此外，使用 '\ ' 表示空格，因为此实现会跳过空格以支持更易读的样式。
  • 方括号 [] 括起来的字符集。 例如，“[A-Za-z_$]”匹配任何字母字符、下划线和美元符号（连字符 (-) 表示范围），例如 [A-Za-z$_] 匹配“B”、“b”、“_”、“$”等。字符集 '[' 后紧跟的 ^ 表示“形成反向字符集”。例如，“[^0-9A-Za-z]”匹配非字母数字字符。
  • 圆括号 () 括起来的表达式。 任何正则表达式都可以通过用圆括号括起来的方式用在最低级别。
  • 点 . 表示“匹配任何字符”。
  • 前面带有 $ 的标识符。 它引用一个已定义的正则表达式。例如，“$Ident”代表之前定义的、用户定义的正则表达式。可以将其视为用圆括号括起来的正则表达式，它有一个名称。

表示前面元素数量的运算符

以上五个基本正则表达式中的任何一个后面都可以跟特殊字符 * + ? /i 中的一个。

  • * 表示重复（可能零次）；例如，“[0-9]*”不仅匹配“8”，还匹配“87576”，甚至空字符串“”。
  • + 表示至少一次出现；例如，“[0-9]+”匹配“8”、“9185278”，但不匹配空字符串。
  • ? 表示最多一次出现；例如，“[$_A-Z]?”匹配“_”、“U”、“$”等以及空字符串“”。
  • \i 表示忽略大小写

正则表达式的连接

上述正则表达式可以连接起来形成更长的正则表达式。例如，“[_A-Za-z][_A-Za-z0-9]*”是一个匹配编程语言“C”中任何标识符的正则表达式，即第一个字符必须是字母或下划线，后面的字符必须是字母数字或下划线。“[0-9]*\.[0-9]+”描述了一个浮点数，小数点前有任意数量的数字，小数点后至少有一个数字。（小数点前必须有一个反斜杠，否则点将表示“在此处接受任何字符”）。“(Hallo (,how are you\?)?)\i”以不区分大小写的方式匹配“Hallo”以及“Hallo, how are you?”。

备选正则表达式

最后——在顶层——正则表达式可以用 | 字符分隔。| 左右两侧的两个正则表达式是备选项，意味着左侧表达式或右侧表达式应匹配源文本。例如，“[0-9]+ | [A-Za-z_][A-Za-z_0-9]*”匹配一个整数或一个“C”标识符。

一个复杂的例子

编程语言“C”的浮点常量定义如下：浮点常量具有以下部分：整数部分、小数点、小数部分、指数部分（以 e 或 E 开头，后跟一个可选符号和数字）以及可选的类型后缀（由 f、F、l、L 中的一个字符组成）。整数部分或小数部分可以省略（但不能同时省略）。小数点或指数部分可以省略（但不能同时省略）。

相应的正则表达式相当复杂，但可以通过使用以下定义来简化

$Int = "[0-9]+."
$Frac= "\.[0-9]+".
$Exp = "([Ee](\+|-)?[0-9]+)".

因此，我们得到以下浮点常量表达式

($Int? $Frac $Exp?|$Int \. $Exp?|$Int $Exp)[fFlL]?
© . All rights reserved.