首先给出博主自己编写的正则表达式文法(在编译器构造中自底向上的LALR(1)语法分析的语法分析表生成的实现这篇文章里已经出现过)：

#1b S' S preSurvey E T M F G outSquare B V C B' inSquare inSquareRange #1e
#2b \\ SPECTRANMETA POSITIVE-SURE-PRE POSITIVE-NEGA-PRE NEGATIVE-SURE-PRE NEGATIVE-NEGA-PRE ) | CLOSURE ? GIVEN LBOUND ULBOUND CLOSURE-NONGREEDY LBOUND-NONGREEDY ULBOUND-NONGREEDY CAP NONPRECAP SPECTRAN TRANMETA UPPERALPHA LOWERALPHA DIGIT SPECMETA REVERSEREF ^ [ ] - OTHERMETA $ #2e
#3b S' S #3e
#4b
#b S' $1 S #e
#b S $1 E #e
#b S $1 preSurvey #e
#b preSurvey $1 E $2 POSITIVE-SURE-PRE $1 E $2 ) #e
#b preSurvey $1 E $2 POSITIVE-NEGA-PRE $1 E $2 ) #e
#b preSurvey $2 NEGATIVE-SURE-PRE $1 E $2 ) $1 E #e
#b preSurvey $2 NEGATIVE-NEGA-PRE $1 E $2 ) $1 E #e
#b E $1 E $2 | $1 T #e
#b E $1 T #e
#b T $1 T $1 M #e
#b T $1 M #e
#b M $1 M $2 CLOSURE #e
#b M $1 M $2 ? #e
#b M $1 M $2 GIVEN #e
#b M $1 M $2 LBOUND #e
#b M $1 M $2 ULBOUND #e
#b M $1 M $2 CLOSURE-NONGREEDY #e
#b M $1 M $2 LBOUND-NONGREEDY #e
#b M $1 M $2 ULBOUND-NONGREEDY #e
#b M $1 F #e
#b F $2 CAP $1 E $2 ) #e
#b F $1 G #e
#b F $2 NONPRECAP $1 E $2 ) #e
#b F $1 outSquare #e
#b outSquare $2 SPECTRAN #e
#b outSquare $2 TRANMETA #e
#b outSquare $2 \\ #e
#b outSquare $2 SPECTRANMETA #e
#b outSquare $2 UPPERALPHA #e
#b outSquare $2 LOWERALPHA #e
#b outSquare $2 DIGIT #e
#b outSquare $2 SPECMETA #e
#b outSquare $2 REVERSEREF #e
#b outSquare $2 ^ #e
#b G $2 [ $1 B $1 V $1 C $2 ] #e
#b V $2 ^ #e
#b V #e
#b B $1 B $1 B' #e
#b B $1 B' #e
#b B' $1 V $1 inSquareRange $2 - $1 inSquareRange #e
#b inSquareRange $2 SPECTRAN #e
#b inSquareRange $2 SPECMETA #e
#b inSquareRange $2 OTHERMETA #e
#b inSquareRange $2 UPPERALPHA #e
#b inSquareRange $2 LOWERALPHA #e
#b inSquareRange $2 DIGIT #e
#b inSquareRange $2 CLOSURE #e
#b inSquareRange $2 \\ #e
#b inSquareRange $2 SPECTRANMETA #e
#b inSquareRange $2 ? #e
#b inSquareRange $2 CAP #e
#b inSquareRange $2 | #e
#b inSquareRange $2 ) #e
#b C $1 C $1 inSquare #e
#b C $1 inSquare #e
#b inSquare $1 inSquareRange #e
#b inSquare $2 NONPRECAP #e
#b inSquare $2 POSITIVE-SURE-PRE #e
#b inSquare $2 POSITIVE-NEGA-PRE #e
#b inSquare $2 NEGATIVE-SURE-PRE #e
#b inSquare $2 NEGATIVE-NEGA-PRE #e
#b inSquare $2 ULBOUND #e
#b inSquare $2 LBOUND #e
#b inSquare $2 ULBOUND-NONGREEDY #e
#b inSquare $2 LBOUND-NONGREEDY #e
#b inSquare $2 CLOSURE-NONGREEDY #e
#b inSquare $2 GIVEN #e
#b G $2 [ $1 B $2 ] #e
#b G $2 [ $1 V $1 C $2 ] #e
#4e

部分终结符和非终结符的含义是：

S':增广文法开始符号

S:原文法开始符号

preSurvey:预查表达式

outSquare：方括号外的直接量

inSquareRange:方括号内中 - 表示的范围的一端

inSquare：方括号内的直接量

SPECTRANMETA：特殊转义元字符 \- \^

POSITIVE-SURE-PRE：正向肯定预查运算符(?=

POSITIVE-NEGA-PRE：正向否定预查运算符(?!

NEGATIVE-SURE-PRE：反向肯定预查运算符(?<=

NEGATIVE-NEGA-PRE：反向否定预查运算符(?<!

CLOSURE：闭包*和+

GIVEN：指定重复次数{n}

LBOUND:指定最小重复次数{n, }

ULBOUND:对重复次数指定上下界{n, m}

CLOSURE-NONGREEDY:非贪婪闭包+? *?

LBOUND-NONGREEDY：指定最小重复次数的非贪婪版本{n, }?

ULBOUND-NONGREEDY：指定最大最小重复次数的非贪婪版本{n, m}?

CAP：子表达式左括号(

NONPRECAP：非捕获匹配(?:

SPECTRAN：特殊转义字符\b单词边界 \B非单词边界 \d数字 \D非数字 \f 换页 \n 换行 \r 回车 \s 空白 \S 非空白\t 制表\v 垂直制表 \w 单词字符 \W 非单词字符

TRANMETA：转义元字符 \* \+ \? \$ \. \( \) \: \= \! \< \| \[ \] \{ \}

UPPERALPHA:大写字母

LOWERALPHA：小写字母

DIGIT：数字

SPECMETA：特殊元字符 . $

REVERSEREF：反向引用

OTHERMETA：其他元字符 : = ! < { }

 了解终结符非终结符的含义后，产生式也就不难理解了

本正则表达式引擎要求方括号外的直接量只能为SPECTRAN、TRANMETA、\\、SPECTRANMETA、UPPERALPHA、LOWERALPHA、DIGIT、SPECMETA、REVERSEREF、^之一，不相符的书写形式都会报告语法错误。因此任何出现在方括号代表本身的元字符必须使用转义书写(即加\).

文法对预查的处理还是存在一些问题，因为它不支持预查表达式(不可自嵌套)和其他预查表达式以及E的任意组合，如果要支持这一点必须大改文法，且要做不少重复工作，比较麻烦，所以本引擎对预查只支持单一的没有自嵌套的预查表达式。此外对非贪婪匹配的处理还是存在一些问题的，回溯引擎处理非贪婪匹配会由少到多逐一尝试，但是本引擎并发地模拟所有可能的转移路径，回溯引擎的做法在本引擎中行不通，所以博主采用了比较笨有待斟酌的做法-闭包和指定重复次数的运算符为非贪婪时让其匹配最少的几种可能，如+?转换为NFA时将匹配1次，这种做法是有一些问题的，在回溯引擎中若匹配aaab，则a+?b和aaab匹配，但本引擎只能匹配子串ab,虽然逻辑上也讲得通，但和非贪婪匹配的预期行为不一致。暂时不知道有什么更好的解决方法，暂时就这样吧

引擎的总体执行逻辑并不复杂，语法分析器读入词法分析器传入的Token进行移入归约，在此过程中使用S属性的语法制导翻译方案将正则表达式翻译为等价NFA，每当进行一次对最右句柄的归约时，将用与句柄匹配的产生式体中非终结符的综合属性构造产生头非终结符的综合属性(可能为NFA也可能不为)，实际上就是执行与产生式关联的语义动作。当对句柄S在向前看符号$下归约即接受时,S对应的NFA即为翻译结果。随后采用模拟NFA(并发地考察所有可能的转移状态)的方法进行无回溯的匹配，得到匹配结果。

每一个子表达式的接受态都有一个指向相应开始态的指针，匹配过程中抵达子表达式接受态时使用该指针确定子匹配结果，模拟过程中可能先后多次抵达同一个子表达式的开始态，我采用开始态编号加抵达开始态时栈顶下标来唯一标识每一个到达，对于每一个到达都会生成与到达相关的传播项，该传播项沿匹配路径不断向前传播，当传播到对应子表达式接受态时就可以利用与接受态对应的传播项确定与特定子表达式开始的到达对应的子匹配结果，当该传播项流动至生成该传播项的子表达式开始态时就发生了回环，此时传播项会被杀死以阻止其进一步传播，避免其对子匹配结果的截取造成影响。另外在算法中计算出从当前字符转移至的新状态的闭包时，会检查是否有传播项从闭包中消失，如果有会在相关的数据结构中删去和消失的传播项关联的项以节省内存空间。对反向引用的处理是，保存文件指针当前位置，然后不断向前读入字符匹配反向引用，若匹配成功则把此时文件指针的位置，反向引用转移至的状态和和反向引用关联的传播项加入表，如果匹配过程中文件指针到达了相同位置，则把反向引用转移至的新状态加入会成为栈顶的newstacknode的状态集，然后将传播项并入当前传播项集合并更新相关数据结构。

最后说明一下，如果匹配成功，每一个匹配结果都是整个正则表达式所能匹配的最长子串。

另外，这个引擎写得真的很烂，博主自己就很不满意，它对预查的支持不完善，对非贪婪的处理存在问题，也未能支持一些本可以支持的特性，和google的RE2引擎实在没法比(代码量上已经输给它)，仅能满足常见的匹配需求，后续可能会继续改正

本项目的github地址:https://github.com/naturerun/RTNWSK-Regex-Engine

欢迎前来围观提出意见哟