终于赶在 2015 年内填了一个 12 年的老坑 —— tinyre 正则引擎

零点已过，今天是 2015 年最后一天。诸位新年好。

最近我花了不少力气，搞了一个说不好有什么卵用的轮子，一个正则表达式引擎……

快捷测试入口： http://rpgame.net:11002/

## **为啥会搞这个**

其实这个坑早在 2012 年就开了，当时我是个小白，刚刚懂点 python ，丝毫没有听说过编译原理是什么东西。于是理所当然的遭遇了数次可耻的失败。

至于当时为啥会开这个坑呢？

经常有人问初学编程能做什么，觉得编程是一件很有意思的事情是什么时候。

对我而言，那个改变一切的时刻就是：

```python
import re
import urllb2
```

是的，爬虫。那个时候，我清晰的感受到了数据在我指尖流动，感受到了代码的魔力。

与我以前弄的 console 程序不同，与我写过的拖控件的 Form 程序也不同。我发现我能够用自己的方式来获取和重组数据，能够对一些简单的投票程序生杀予夺。

那时的我，左手握着 Python 法杖，右手手持正则魔典，脚下踏着一个名叫 HTML 的入门怪物，方法、函数和规则环绕着我，我感受到了力量，征服了曾经的不可知之地，攫取到了胜利。

后来 urllib2 换了 requests ， Python2 换了 Python3 ，而 re 始终是 re ，如此的严谨美丽。

获得了这种力量之后，我便想办法搞清楚他是怎么运行的，但我也没有想到会隔了这么久。

## **那么，搞得怎么样**

其实正则引擎的实现是很有趣的，基础规则十分的简单。

很容易就可以写一个屌丝版，但要费一番力气才能升级到高配版。

不断升级的过程中还会遇到新旧升级不相兼容，于是就得推倒重来弄一个兼容的架构设计。

**最终的结果大概是这样吧：**

* 3000 行左右， c99 ，无依赖， gcc4.8/vs2013 编译通过

* 支持了绝大部分 SRE 的语法

* 原生 UTF8 支持，中文无压力

* 底层支持了除了八进制之外的转义语法（\x \u \U ）

* 当前的匹配函数只有 match 一个

* 编程完后用 Valgrind 进行过一轮内存泄漏检查，状况应该比较良好

* 我去搞了一个 Python3.5.1 的正则模块的测试用例，关于 match 的大部分正则测试都在修修补补之中过掉了。

* 额外支持了一个最大回溯次数限制，我们知道 DFA 在遇到 **'a?'*n+'a'*n** 匹配 **'a'*n** 的时候会不停回溯，等待时间的延长是指数级别的，回溯次数上千万上亿都是没问题的。于是超过限制次数后就会直接停止，并直接当作不匹配。

**然后是不支持的部分：**

* 不支持 LOCALE UNICODE 两个 flag ，因为只匹配 UNICODE

* 不支持 VERBOSE 这个 flag ，我没太搞懂干啥用的

* 不支持八进制，因为实在是太乱了，后向引用和八进制混一块，拿头用

* 发现 SRE 竟然有一些全角半角字符的大小写和匹配，比如ｋ匹配 k ，日狗，这有卵用？

* SRE 还有一些貌似是其他外文字母大小写的匹配，再次表示日狗，并不会支持。

* 不支持 \A \Z ，很少用，我也还不太懂他们和 ^ $ 的区别，怕搞错。同时还有 \b \B 也暂不支持

* 暂不支持 (?<=\1) 这一类组的语法，因为我翻 test 的时候才第一次见到！之前参考的手册里没有！

## **所以，能不能用，怎么用？**

目前来说，**不建议在生产环境中使用**（我估计也不会有人这么搞）。
首先是功能缺了好几样， replace 、 findall 啥的都没得用。
其次，还需要优化，回溯的时候大量使用 malloc/free ，遇到回溯次数极多的情况效率低下。
然后初始时候跨平台考虑不周， utf32 用的是 int ，其实应该选 uint32_t 的，目前还没改过来。
最后，还需要测试和完善。

编译：
编辑 CMakefile.txt ，手动改一下 build_target 为 demo 或者 py3lib

```bash
cd tinyre
mkdir build
cd build
cmake ..
make
```

C 语言的话，引用头文件就好，所有外部接口都在这一个头文件

```C
#include "tinyre.h"

tre_Pattern* pattern;
tre_Match* match;

pattern = tre_compile("^(bb)*a", FLAG_NONE);
match = tre_match(pattern, "bbbbabc", 0);
```

match 对象里面有个 utf32 字符串，拿出来用即可。

Python ，首先也是编译，拿到 _tinyre.so 之后和 src/tre.py 放一块，然后就可以：

```Python
import tre
tre.match(r'test', 'test')
```

目前只支持 Python3 ，因为我用 3 比较多。

在线的那个入口试出毛病的话欢迎反馈！

## **~~最后，很关键~~**

诸君，请在 2015 年最后一天带我完成 Github 100 stars 成就！

咱这个 Tornado 项目生成器本身已经有 87 个星星了： https://github.com/fy0/fpage

讲道理挺好用的……测试入口就是用它生成后速撸出来的。