这个工具使用了一个非常高效的算法，用来匹配多个高级正则表达式。经过预处理，仅用 O(n) 的时间复杂度，就可以识别出一个输入字符串（长度为n）能匹配哪些（可能是多个）正则表达式。算法的详细内容可参见：

1. 多正则表达式匹配(Multiple Regular Expression Matching)
2. 多正则表达式匹配(Multiple Regular Expression Matching) 中的动态 DFA 算法

算法的原理请参考： 多正则表达式匹配(Multiple Regular Expression Matching)。

作为一个完整的解决方案，这个程序包括两部分：

• 一个离线 Build 程序：regex_build
  1. regex_build 会把输入的正则表达式编译成一个 DFA  ( 正则表达式的编译使用了 re2 的前端 Parser )
  2. 如果使用二进制模式，还会生成一个 binmeta 文本文件，用来描述 DFA 的元信息
     • 该文件生成后不可被更改，否则会产生未定义行为
     • 目前应该首选二进制模式

• 一个动态库，提供匹配接口
  1. 从 (regex_build生成的) DFA 文件 和 binmeta(二进制模式) 文件 加载 并 创建出 用来执行匹配 的 对象
  2. 在二进制模式下，构造 MultiRegexFullMatch 对象执行全匹配，此时不获取 Submatch，仅返回能匹配上的正则表达式 ID：MultiRegexFullMatch示例程序
     • FullMatch 匹配完成与 google.re2.set 相同的功能，但效率要高得多
     • 性能测试：re2bench/setmatch.cpp 使用 re2.set, 产生与 MultiRegexFullMatch示例程序 相同格式的输出，以做比对
  3. 在二进制模式下，构造 MultiRegexSubmatch 对象执行匹配：MultiRegexSubmatch示例程序
     • MultiRegexSubmatch 仅能获取 one-pass 正则的 submatch
     • one-pass 正则的判断直接调用了 re2 的判断函数 IsOnePass
       • 很不幸，该函数会将正则表达式 从([^到]+)到([^怎]+)怎么走 判为非 one-pass，但实际上，在 unicode 字符集内，它的确是 one-pass，只是 re2 的底层引擎是基于字节的，所以它认不出来
       • 如果你愿意冒险，regex_build 给你一个选择，将所有的正则表达式标为 one-pass，MultiRegexSubmatch::match_utf8 在搜索完之后，会按 utf8 编码规则做一个边界修正，就可以正确提取出 从([^到]+)到([^怎]+)怎么走 中的 submatch 了

• 该程序对大规模的规则系统（例如100万个正则表达式）会非常有用：多正则表达式匹配的应用

Compile (现在已闭源，只能下载编译好的程序)

regex_builder 使用方法

regex_builder.exe 将很多个正则表达式 offline build成一个DFA文件，online程序使用时，先加载DFA文件，当匹配文本时，可以获知匹配到了哪些正则表达式，同一个文本可能匹配多个正则表达式。

匹配接口分文本接口于二进制接口两种，目前二进制接口已经有了很友好的封装，推荐使用。

文本接口的使用方法与之前的DFA词表完全相同（match_key接口）。

该程序使用 re2 的parser前端，生成 febird 自己的 DFA 文件

命令行选项与参数

命令行： regex_build.exe Options [Regex-TXT-File]

关于 -d 选项    该选项现在已删除，不再支持

一开始 febird DFA 通过 match_key 接口来实现正则表达式匹配，必须在 byte 的取值范围 [0, 256) 之间取一个作为分隔符。后来，经过仔细考虑，通过扩充自动机的字符集(r1303)，从而 delimeter 可以在 [0, 256) 之外取值，于是就不再需要从 [0, 256) 取一个特殊值来作为分隔符。

这样，正则表达式匹配就可以有更广的适用范围。另一方面，表面上看，似乎去除一个特殊byte值作为delimeter会影响二进制模式的匹配，其实一点也不会。正则表达式相当于key，正则表达式的 id 相当于是 value，delimeter 不能出现在 key 中，但可以出现在 value 中，从而，value可以是任意二进制数据。实际上，二进制匹配接口的实现是先于 r1303 的。

Regex-TXT-File

如果命令行未指定 Regex-TXT-File，就从标准输入读取

Regex-TXT-File 的格式：  composed regexp \t id

第一列是正则表达式（re2语法），如果行首字符是 *，表示忽略该正则表达式的 one pass 属性，无条件获取 submatch，用 * 做标志的原因是以 * 开头的正则表达式是非法的正则，从而不会引发歧义，也不会减少表达能力。

第二列是正则表达式的id，该id可以是任意字符串，用来标识这条规则。多个正则表达式可以有相同的id，此时等效于将多个正则表达式或起来放在一行。

2014-8-31 日新加了一个功能，就是上面强调的 composed regexp：可以是多个正则表达式的并交差，还有连接和重复，语法很简单：

Inter 表示 Intersection 或 Difference，求交集(&&)，或者差集(&!)，Union 表示求并集(||)，所有操作符都是左结合，重复（?,*,+,{min,max}）的优先级最高，接下来是连接，连接不需要操作符，然后是集合操作，&& 和 &! 的优先级相同，比 || 高，圆括号 ( ) 用来强制结合。

值得一提的是，{{ 和 }}，用来括住正则表达式(re2语法)，一个语法正确并且规范的正则表达式中不会出现 {{ 和 }}，只有一个例外：\{{，这个例外很容易处理。其实严格讲，语法正确的正则表达式中可以出现 {{ 和 }}，但这样正则表达式往往是有问题的，{ 和 } 用作非元字符时，需要转义（\{和\}），而 { 和 } 不转义时是元字符，不会出现 {{ 和 }}。这样，composed regexp 中的 composed 部分的编译可以和 regexp 部分的编译完全分离开来，composed 部分用简单地递归下降就可以解决，regexp部分直接用re2的前端。整个 composed regexp 中可以没有 {{ 和 }} ，此时它就是一个简单正则，简单正则支持取括号（submatch）， composed regexp 则不支持取括号。

最开始我用{{{和}}}表示正则语法的分界，并且只实现了并交差，但后来要增加连接和重复，发现{{{和}}}在视觉上太别扭，就简化成了{{和}}，并处理例外情况。

一个示例的Regex.txt :

这其中有多个 composed regexp，为了便于测试，我做了一个页面： 正则表达式图形化

非常重要！注意事项！

谨慎使用 .* ，特别是当 .* 处于正则表达式开头时

普通字符串（不包括正则表达式的元字符）也可以放进Regex.txt，可以为所有普通字符串赋予一个相同的id，这样就将正则表达式和普通字符串build到同一个DFA中了，普通字符串在DFA中占的空间相对要小得多，如果普通字符串很多，可以尝试用 -t x选项，看生成的DFA文件是否更小。

匹配接口: 二进制模式

MultiRegexFullMatch

参考 MultiRegexFullMatch示例程序

MultiRegexSubMatch

参考 MultiRegexSubmatch示例程序

匹配接口: 文本模式（现在已删除，不再支持）

匹配接口使用方法可以参考 DFA_Interface::match_key 示例程序

直接去 febird-trunk/samples/automata/abstract_api/ 目录运行 make即可编译，编译输出在 rls 和 dbg 目录下

编译出来的 match_key 程序可用来测验匹配（match_key程序使用的 delimiter是 \t ）:

febird-trunk/samples/automata/abstract_api/rls/match_key -t abcccb < samples.dfa 输出：

输出的 str=1 str=2 str= a-dot-star-b就是匹配到了id为1、2、a-dot-star-b的正则表达式

使用 match_key 接口，正则表达式匹配和词典匹配就完全相同。