- 引论
- 正则语言本身属于3型语言，原本按道理只需要一个简单的实现就可以了，但是这部分的水其实非常的深。
- 强化正则有back reference。
- 需不需要支持jit
- 要兼容POSIX标准？
- 要做online parsing么？
- 实现打算怎么做？
- 常见实现方式
- 回溯
- 性能可能会非常差，ReDOS的元凶。
- NFA
- 很容易把正则语言parse成NFA，然而这样就很难做backreference了。
- m-gram index
- 空间换时间
- DFA
- 马马虎虎，也有NFA的局部问题。
- 回溯
- 正则语言本身属于3型语言，原本按道理只需要一个简单的实现就可以了，但是这部分的水其实非常的深。
- SuccinctStore Regex
- SuccinctStore Regex选择把底层依赖的SuccinctStore当成BlackBox，因为SuccinctStore的Compressed Suffix Array的实现，其效果和m-gram时间复杂度差不多，但是因为SuccinctStore无需耗费多余的空间做index，其本身就是index，所以其在空间和时间中找到了比较好的平衡。
- 参考资料
- Russ Cox的blog提及了很多Regex的实现方面的好文章。
- 《Parsing Technology》讲的也很透。