Henry Spencer 的 Regexp 引擎回顾
4.88/5 (16投票s)
2003 年 6 月 28 日
17分钟阅读
189950
3370
一个小型、支持 Unicode 的正则表达式引擎，基于 Henry Spencer 的早期工作
引言
正则表达式（有时也称为 regexps）用于以简洁的形式描述文本模式匹配。当您需要应用此类模式匹配时，它们非常有用：输入验证、轻量级词法分析、解析电子邮件地址等等。许多脚本语言（例如 Perl 和 Python）都内置了正则表达式引擎。 .NET 框架也提供了一个。
对于 C++ 程序员来说，已经有几个正则表达式库可用。它们比这个库更快、更现代化。它们还支持更复杂的正则表达式（例如 Perl 正则表达式或 POSIX 正则表达式）。其中之一是 Boost.Regex；它甚至 在 CodeProject 上进行了文档记录，总的来说我强烈推荐它。
那么，为什么还要提供这个呢？
一个答案：代码占用空间。该库基于 Henry Spencer 早期发布的公共领域正则表达式实现。在 Linux/ELF32 系统下，与测试程序一起编译，大小约为 20 KB。在 Win32 下，发布模式下约为 19 KB 多一点。大多数完全符合 POSIX 的正则表达式引擎（例如 Boost.RegExp、PCRE、GNU Regex 或 Henry Spencer 的最新库）在类似的编译选项下通常占用约 50 KB。
在如今拥有 100 GB 硬盘和多兆字节应用程序的时代，代码占用空间似乎不是什么大问题。然而，您可能需要占用空间小的原因——例如，您可能想在 Pocket PC 上使用正则表达式，或者将其放入可下载的 ActiveX 控件中。
此外，有时您不需要完整的 POSIX 正则表达式；简单的正则表达式就足够了。或者您可能想要简单的代码，以便更容易理解其实现。在这些情况下，这个小型引擎正是您需要的。
背景
要使用此库，您需要了解基本的正则表达式语法。您可以在此页面找到一个很好的介绍。这个特定的实现是“扩展正则表达式”方言的一个超集。
基本上，以下内容可用
- 元字符 ".", "[...]" 和 "[^...]";
- "+", "*" 和 "?" 量词;
- 锚点 "^", "$", "\<" 和 "\>";
- 选择 "|" ;
- 子表达式 "(...)";
- 简易字符类 "\x"，其中 x 是一个字母，它映射到一个原始的 ctype.h 函数，如下所示
- "\m":
isalnum() - "\a":
isalpha() - "\b":
isblank()(GNU 对 ctype.h 的扩展；本质上映射空格和制表符) - "\c":
iscntrl() - "\d":
isdigit() - "\g":
isgraph() - "\l":
islower() - "\p":
isprint() - "\n":
ispunct() - "\s":
isspace() - "\u":
isupper() - "\x":
isxdigit() - "\w":
isword()(不是 ctype.h 例程，匹配isalnum()加上下划线字符)
将字母大写可获得反向匹配（例如，“\D”匹配
isdigit()返回false的所有字符） - "\m":
换句话说，它*不支持*
- 编号匹配 "{n}" 或 "{n,m}"（然而，这些可能可以添加，但会增加相对较高的内存使用量）。
- 单词开头或结尾匹配 "\b" 和 "\B"（它们映射到
isblank()字符类）；请注意，“\<”和“\>”可以起到大致相同的目的。 - 正则表达式内的反向引用（据我所知，这单独导致了 Spencer 先生重写他的库）。
- POSIX 排序元素 "[.char.]" 和 "[=char=]"。
- POSIX 字符类 "[:class:]"（然而，请参阅上面描述的简易字符类）。
- 不区分大小写的匹配和“基本”正则表达式。
- 类似 Perl 的字符类。
总的来说，该引擎支持扩展的、POSIX 前的正则表达式语法，不包含 Perl 扩展，并且添加了由我添加的字符类，作为一种有些粗糙的解决方案。
如前所述，原始的正则表达式引擎是由 Henry Spencer 编写的；我在 ftp://ftp.zoo.toronto.edu/ 上找到它，并对其进行了修改以支持宽字符（通过相应的预处理器定义）。我还将其扩展为支持任意数量的子表达式（原始代码限制为 9 个）。生成的接口接近 POSIX 正则表达式接口，但可惜不是完全相同。这使得它具有重入接口（原始接口绝对不是重入的）。我基本上调整了接口，以便可以轻松地将其与动态内存分配一起使用。
使用代码
C 接口
您有三种使用该代码的方式。C 接口（在
#include "regexp.h"
#include <string>
#include <vector>
int parse_email(const std::string& to_match,
std::string& user_name,
std::string& host_and_domain,
std::string& domain_suffix)
{
regexp* compiled; // line A
int retval = re_comp(&compiled,
"^([A-Za-z0-9]+)@(.+)\\.(\\a+)$"); // line B
if(retval < 0)
return retval; // line C
regmatch* matches = new regmatch[re_nsubexp(compiled)]; // line D
retval = re_exec(compiled,
to_match.c_str(),
re_nsubexp(compiled),
&matches[0]); // line E
re_free(compiled); // line F
if(retval < 1) // line G
{
delete[] matches;
return retval;
}
user_name = std::string(to_match.begin() + matches[1].begin,
to_match.begin() + matches[1].end); // line H
host_and_domain = std::string(to_match.begin() + matches[2].begin,
to_match.begin() + matches[2].end);
domain_suffix = std::string(to_match.begin() + matches[3].begin,
to_match.begin() + matches[3].end);
delete[] matches;
return 1;
}
int main(int argc, char* argv[])
{
if(argc >= 2)
{
std::string user_name, host_and_domain, domain_suffix;
if(parse_email(argv[1], user_name,
host_and_domain, domain_suffix) < 1)
{
printf("Not an email address\n");
return 1;
}
printf("User name: %s\nHost/domain: %s\nDomain suffix: %s\n",
user_name.c_str(),
host_and_domain.c_str(),
domain_suffix.c_str());
return 0;
}
printf("Usage: %s <email address>\n", argv[0]);
return 1;
}
上面的程序包含一个简易的电子邮件解析器（正则表达式不符合任何 RFC，它似乎只适用于我给它的两个测试地址）。它将电子邮件拆分为用户名、域名前缀和域名后缀（域名后缀，例如，地址末尾的“.com”）。
以下是对函数 parse_email() 中有趣行的解释：
- A 行：正则表达式在使用前必须编译。编译后的正则表达式通过一个不透明类型的指针
regexp返回。因此，您必须声明一个regexp*来保存编译后的正则表达式。 - B 行：此语句创建一个编译后的正则表达式。生成的编译表达式存储在
&compiled中；第二个参数是正则表达式本身。请注意，由于我们将其表示为常量 C 字符串，因此需要将表达式中的每个反斜杠加倍。该表达式的工作原理如下：首先匹配任何字母数字字符，直到“@”符号；然后，匹配一个或多个任意字符，后跟一个“.”（匹配是“贪婪”的，这意味着表达式的最后一个“.”将终止第二个子表达式）；最后，匹配一个或多个字母字符。
- C 行：
re_comp()成功时返回 0，失败时返回负数错误码。错误码定义在regexp.h 并且可以是以下任何一项：REGEXP_BADARG：无效参数REGEXP_ESIZE：正则表达式过大REGEXP_ESPACE：内存不足REGEXP_EPAREN：括号 () 不平衡REGEXP_ERANGE：无效字符范围REGEXP_EBRACK：方括号 [] 不平衡REGEXP_BADRPT：量词运算符无效REGEXP_EESCAPE：无效的转义 \ 序列REGEXP_EEND：内部错误！
- D 行：要尝试匹配编译后的正则表达式，请使用
re_exec()函数。该函数接受一个regmatch结构数组。数组中每个子表达式应该有一个元素。在 D 行，我们分配一个数组来存储匹配项。re_nsubexp()函数查询编译后的正则表达式包含的子匹配数。 - E 行：在这里，我们最终尝试匹配正则表达式。
re_exec()的第一个参数是编译后的正则表达式；然后，传递要匹配的字符串、匹配数组中的元素数量以及匹配数组的地址。如果您不关心子匹配，可以将第三个参数传递 0，最后一个参数传递NULL。确保您传递的数组中的元素数量至少等于第三个参数中传递的大小。 - F 行：完成后，您应该使用
re_free()释放编译后的模式。请不要使用free()或delete[]来释放它（但是，如果您想覆盖正则表达式引擎使用的内存分配器，请参阅自定义部分）。请注意，您应该在程序的整个生命周期内保留这些编译后的正则表达式。由于编译是一个相对缓慢的过程，因此最好在您可能再次需要编译后的表达式时将其保留。
- G 行：
re_exec()函数可以返回负数错误码（与@code{re_comp()}, 0（表示字符串未匹配正则表达式）或 1（表示字符串匹配正则表达式）相同）。 - H 行：
regmatch结构包含两个字段：begin和end。它们包含传递给re_exec()的字符串的偏移量。begin是子匹配的起始偏移量，end是子匹配结束之后一个字符的偏移量（因此，end - begin是子匹配的长度）。匹配数组的第 0 个元素始终是整个正则表达式的匹配。第 1 个元素是第一个子表达式（从左边开始计数），依此类推。
如果某个元素未匹配，其
begin和end字段将设置为 -1。在示例语句中，我们使用偏移量来计算第一个子表达式的子字符串的开始和结束迭代器。
REGEXP_UNICODE 预处理器符号的方式编译正则表达式库，您将获得 re_comp() 和 re_exec() 例程的宽字符版本。它们通过 re_comp_w() 和 re_exec_w() 例程访问。它们的工作方式与非“_w”版本完全相同，只是它们接受宽字符字符串而不是多字节字符串。这是为宽字符重写的示例函数：#define REGEXP_UNICODE
#include "regexp.h"
#include <string>
#include <vector>
int parse_email(const std::wstring& to_match,
std::wstring& user_name,
std::wstring& host_and_domain,
std::wstring& domain_suffix)
{
regexp* compiled; // line A
int retval = re_comp_w(&compiled,
L"^([A-Za-z0-9]+)@(.+)\\.(\\a+)$"); // line B
if(retval < 0)
return retval; // line C
regmatch* matches = new regmatch[re_nsubexp(compiled)]; // line D
retval = re_exec_w(compiled,
to_match.c_str(),
re_nsubexp(compiled),
&matches[0]); // line E
re_free(compiled); // line F
if(retval < 1) // line G
{
delete[] matches;
return retval;
}
user_name = std::wstring(to_match.begin() + matches[1].begin,
to_match.begin() + matches[1].end); // line H
host_and_domain = std::wstring(to_match.begin() + matches[2].begin,
to_match.begin() + matches[2].end);
domain_suffix = std::wstring(to_match.begin() + matches[3].begin,
to_match.begin() + matches[3].end);
delete[] matches;
return 1;
}
类接口
作为示例，也为了方便起见，演示代码包含一个 CRegExp 类，它可以作为库的一个不错的接口。该接口使用 WTL 中可用的 CString 类（请注意，它也可能适用于 MFC - 我只是没有测试过）。
以下是 CRegExp 类的类声明（省略了私有细节）：
class CRegExpException
{
public:
CRegExpException(int nError);
int GetError() const;
CString GetErrorString() const;
};
class CRegExp
{
public:
CRegExp(LPCTSTR pszPattern);
~CRegExp();
BOOL Exec(const CString& pszMatch);
BOOL IsMatched(int nSubExp = 0) const;
int GetMatchStart(int nSubExp = 0) const;
int GetMatchEnd(int nSubExp = 0) const;
CString GetMatch(int nSubExp = 0) const;
int GetNumberOfMatches() const;
};
每次库返回错误时，都会抛出 CRegExpException 类的一个实例； GetError() 返回错误码（如C 接口部分所述），GetErrorString() 返回与该错误相关的纯英语字符串。
CRegExp 类具有以下成员：
CRegExp::CRegExp(LPCTSTR pszPattern)
创建一个新的CRegExp对象，使用正则表达式pszPattern。int CRegExp::GetNumberOfMatches()
返回在构造时传递的模式可以预期的匹配数，这等于模式中的子表达式数 *加上一*。例如，如果模式包含两个子表达式，GetNumberOfMatches()返回 3。BOOL CRegExp::Exec(const CString& sMatch)
尝试将sMatch与构造时指定的正则表达式匹配。如果匹配表达式，则返回TRUE，否则返回FALSE。int CRegExp::GetMatchStart(int nSubExp = 0)int CRegExp::GetMatchEnd(int nSubExp = 0)CString CRegExp::GetMatch(int nSubExp = 0)BOOL CRegExp::IsMatched(int nSubExp = 0)
只能在调用CRegExp::Exec()之后调用。GetMatchStart()返回nSubExp第个子表达式的起始偏移量（0 表示整个表达式，1 表示第一个子表达式，依此类推）。GetMatchEnd()返回nSubExp第个子表达式结束之后一个字符的偏移量。GetMatch()返回匹配nSubExp第个子表达式的字符串。IsMatched()仅返回nSubExp第个子表达式是否已匹配。请注意，当您指定一个未匹配的子表达式或一个超出有效子表达式范围的子表达式时，
GetMatchStart()和GetMatchEnd()返回 -1，而GetMatch()返回一个空字符串。
这是从C 接口部分的 C 示例，已重写为包装器使用：
BOOL ParseEMail(const CString& sToMatch,
CString& sUserName,
CString& sHostAndDomain,
CString& sDomainSuffix)
{
CRegExp reEMailExpr(_T("^([A-Za-z0-9]+)@(.+)\\.(\\a+)$"));
if(reEMailExpr.Exec(sToMatch) == FALSE)
return FALSE;
// the regular expression's format should ensure that all
// three expressions match, or the expression doesn't match
// at all.
ATLASSERT(reEMailExpr.IsMatched(1) &&
reEMailExpr.IsMatched(2) &&
reEMailExpr.IsMatched(3));
sUserName = reEMailExpr.GetMatch(1);
sHostAndDomain = reEMailExpr.GetMatch(2);
sDomainSuffix = reEMailExpr.GetMatch(3);
return TRUE;
}
标准 C++ 包装器
对于那些无法访问 CString 但可以访问标准 C++ 库的人来说，你们并没有被遗忘。这里提供的包装器与 Boost.RegExp （它*非常*全面，并且针对最小的堆使用进行了优化）的类不同，但足以让 C 接口更友好。
以下是 regular_expression 类的类声明（省略了私有细节）：
class regular_expression_error : public std::runtime_error
{
public:
regular_expression_error(int error_code, regexp* re);
int code() const;
const char* message() const;
};
class regular_expression
{
public:
#ifdef REGEXP_UNICODE
typedef wchar_t CharT;
typedef std::wstring string_type;
#else
typedef char CharT;
typedef std::string string_type;
#endif
typedef typename string_type::size_type size_type;
typedef typename string_type::const_iterator const_iterator;
regular_expression(const CharT* pattern);
regular_expression(const string_type& pattern);
bool exec(const CharT* match);
bool exec(const string_type& match);
bool matched(size_type sub_exp = 0) const;
const_iterator begin(size_type sub_exp = 0) const;
const_iterator end(size_type sub_exp = 0) const;
string_type operator[](size_type sub_exp) const;
size_type size() const;
};
每次库返回错误时，都会抛出 regular_expression_exception 类的一个实例； code() 返回错误码（如C 接口部分所述），message() 返回与该错误相关的纯英语字符串。
regular_expression 模板具有以下成员：
regular_expression(const CharT* pattern)regular_expression(const string_type& pattern)
创建一个新的regular_expression对象，使用pattern中传递的正则表达式。正则表达式会被编译，并且编译后的表示形式会保留直到regular_expression实例被销毁。size_type size()
返回在构造函数中传递的模式可以预期的匹配数。这等于模式中的子表达式数 *加上一*（第 0 个匹配，即整个表达式，始终存在）。bool exec(const CharT* match)bool exec(const string_type& match)
尝试将match与对象中编译的正则表达式进行匹配。如果匹配表达式，则返回true，否则返回false。请注意，
match会在类实例内部被复制，以确保begin()、end()和operator[]能够正常工作，无论match发生什么情况。const_iterator begin(size_type sub_exp = 0)const_iterator end(size_type sub_exp = 0)bool matched(size_type sub_exp = 0)string_type operator[] (size_type sub_exp)
这些方法只能在成功调用exec()后调用。begin()返回一个指向第sub_exp个子表达式开始位置的迭代器（0 表示整个表达式，1 表示第一个子表达式，依此类推）。end()的工作方式相同，只是它返回一个指向第sub_exp个子表达式之后一个位置的迭代器。matched()返回第sub_exp个子表达式是否已匹配。最后，
operator[]等同于string_type(begin(sub_exp), end(sub_exp))，也就是说，它返回第sub_exp个匹配项。请注意，当传递一个无效的
sub_exp时（因为它不是一个匹配的子表达式，或者sub_exp大于size()），begin()和end()所代表的范围将为空，而operator[]将返回一个空的string_type。
REGEXP_UNICODE 的定义（或未定义）而具有两种行为的类。鉴于底层 C 代码没有根据字符类型进行模板化，我别无选择。这是 C 示例（如果您已经很熟悉，应该看起来*非常*熟悉，否则请参阅C 接口部分），已用标准库进行了重写：
bool parse_email(const std::string& to_match,
std::string& user_name,
std::string& host_and_domain,
std::string& domain_suffix)
{
regular_expression email_expr("^([A-Za-z0-9]+)@(.+)\\.(\\a+)$");
if(!email_expr.exec(to_match))
return false;
// the regular expression's format should ensure that all three
// expressions match, or the expression doesn't match at all.
assert(email_expr.matched(1) &&
email_expr.matched(2) &&
email_expr.matched(3));
user_name = email_expr[1];
host_and_domain = email_expr[2];
domain_suffix = email_expr[3];
return true;
}
如何将库包含到您的项目中
我没有为库本身提供项目文件，因为您可能不想将该库制成 DLL。其代码占用空间足够小，可以静态链接。
以下文件构成了库的“核心”：
- regexp.h（公共头文件）
- regexp_int.h（内部头文件）
- regexp_custom.h（内部头文件）
- regmagic.h（内部头文件）
- memory.c（内存分配例程）
- regerror.c（错误翻译函数实现）
- regexp.c（主实现文件）
- report.c （默认报告函数）
- widechar.c （Unicode 字符支持的默认实现）
以下文件是可选的，只有当您想使用“旧式”接口和替换函数时才需要：
- frontend.c
- regsub.c
最后，以下文件是从原始源文件继承的单元测试；您可能不需要它们，但为了保持一致性，它们与库的其他部分一起提供：
- try.c
- timer.c
- tests
根据您想使用的包装器，您还可以将 wtl/CRegExp.* 或 stl/stdregexp.* 文件添加到您的项目中。演示项目展示了如何做到这一点。
自定义
像这样的库往往在各种环境中被使用。因此，我试图隔离对运行时库例程的依赖，以便可以轻松地覆盖它们。
默认情况下，该库使用 malloc() 和 free() 进行内存分配。但是，如果您想使用自定义分配器，只需实现以下两个例程即可：
extern "C" void* re_malloc(size_t sz);
extern "C" void re_cfree(void* p);
这些例程应该具有与 malloc() 和 free() 相似的语义。提供的 memory.c 文件包含一个使用标准 malloc() 和 free() 的默认实现；如果您想覆盖此实现，只需提供自己的实现，而不要链接提供的 memory.c 文件。
此外，在编译 REGEXP_UNICODE 时，会尝试为使用混合宽字符/多字节字符串的人提供多字节接口。它工作得不太好（子表达式偏移量没有正确计算），但如果您有兴趣使用它，您肯定会想覆盖以下两个函数：
extern "C" wchar_t* re_ansi_to_unicode(const char* s);
extern "C" char* re_unicode_to_ansi(const wchar_t* s);
这些函数应该使用 re_malloc() 来创建一个具有适当类型的新字符串。默认情况下，使用 C 库的 mbstowcs() 和 wcstombs() 例程；但是，您可能想将它们映射到，例如，::MultiByteToWideChar() 和 ::WideCharToMultiByte()。默认实现位于 widechar.c 中；提供您自己的实现，而不要链接 widechar.c 来覆盖默认行为。请注意，如果您不使用提供的 widechar.c，您还需要提供 isblank() 和 iswblank() 的实现；有关详细信息，请参阅文件中的注释。
最后，正则表达式库调用一个函数来报告内部错误，其粒度比 REGEXP_* 错误码更细。默认情况下，通过 fprintf(stderr, ...) 进行报告。要覆盖此行为，请提供：
extern "C" void re_report(const char* error);
（请注意，错误始终以纯字符形式提供）例如，您可以提供：
extern "C" void re_report(const char* error)
{
char buffer[128];
::wsprintfA(buffer, "REGEXP ERROR: %s\n", error);
::OutputDebugStringA(buffer);
}
默认实现位于文件 report.c 中。如果您不喜欢默认实现，只需提供您自己的实现，而不要链接 report.c。
演示项目
第一个演示程序（re2demo.exe）是一个简单的 WTL 对话框应用程序，它允许您探索不同的正则表达式。顶部的字段应包含正则表达式；中间的字段应包含要匹配的字符串。一旦按下“尝试”按钮，匹配项将显示在底部的组合框中（打开组合框以查看所有子匹配项）。如果发生错误，或者字符串未匹配正则表达式，错误将作为组合框的第一个（也是唯一一个）条目打印出来。
请注意，该演示程序无意成为一个干净的 WTL 风格的演示。它主要是一个关于如何将正则表达式引擎集成到您自己的程序中的示例。
（实际上，我真的应该承认，我只是为了确保 CRegExp 类正常工作才编写它）
第二个演示程序（try.exe）是一个简单的单元测试程序，它包含在原始源代码存档中。为了方便起见，它以预编译形式提供。
未来方向
还可以相对轻松地添加一些额外的实用程序，例如字符串替换例程和全局匹配例程。为了快速发布此代码，我尚未完成此操作。
此外，我非常确定支持 {n} 和 {m,n} 量词是可能的（尽管可能在内存使用方面成本很高）。我最终可能会决定添加这个。
另外，当 REGEXP_UNICODE 定义时，普通字符版本无法正常工作的这一事实绝对是一个错误。目前的解决方法是拥有两个独立的库——一个 Unicode，一个多字节。这是一个 hack，我讨厌保留这样的东西。
最后，我似乎记得这个正则表达式引擎的某个修改版本优化了一些常见情况以获得更好的性能。我可能最终会找到它并将这些修改应用到这里提供的版本。
相关工作
有一个另一个 CRegExp 类存在。该类的作者对我实现的启发表示感谢；该类让我意识到了 Spencer 先生代码的可用性。然而，我没有做的一件事是像在另一个实现中那样，将 C 例程合并到我自己的 CRegExp 类中。主要是，我想让代码对于非 MFC 用户来说易于定制，同时还能从我的修改（Unicode 支持等）中受益。最简单的方法是保留纯 C 接口。
在我最终确定这个特定实现之前，我曾尝试提取 Spencer 先生的最新实现（它埋藏在 Tcl/Tk 代码中）。我成功地提取了它，但对代码占用空间较大感到失望。
我也考虑过 PCRE；不幸的是，当时他们的 Unicode 支持仍处于实验阶段，而且它基于 UTF-8 编码字符串而不是 UCS-2 宽字符字符串，而我需要 UCS-2。这很可惜，因为它相对较小，而且据说是非常快的库。好吧。
最后，CodeProject 上有关于同一主题的文章。它们为不同的库提供了教程。您可能想参考它们以获得替代解决方案。
结论
我们已经看到了一个关于如何使用本文提供的正则表达式包的简短教程。此外，我们还看到了如何使用 C++ 的两个类，这些类是该包的示例包装器。
从对正则表达式语法的评论来看，现在应该清楚，这不是最完整或最快的库。然而，它简单、易于理解、可移植且小巧。如果您看重这些标准中的任何一个而不是完整性和速度，那么这个库将更适合您的需求。
我希望您在使用它时和我一样享受调整其代码的乐趣。
历史
- 2003/06/28 - 初始修订
- 2003/07/03 - 向演示项目添加了丢失的文件