分析实现一个简易的正则表达式引擎)
首先给出博主自己编写的正则表达式文法(在编译器构造中自底向上的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转义元字符 * ? $ . ( ) : ! lt; | [ ] { }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地址:GitHub - naturerun/RTNWSK-RE-ENGINE: 用C实现的正则表达式引擎支持子表达式反向引用简单的预查语法一些字符类非贪婪匹配和边界匹配自己编写的正则表达式引擎可能有未知的缺陷、错误和漏洞博主自己没有那么多精力进行详尽的测试和维护如果发现错误愿意提就提出谢谢大家2019.4.25更新新增对非贪婪匹配的支持 LALR(1)分析实现一个简易的正则表达式引擎
首先给出博主自己编写的正则表达式文法(在编译器构造中自底向上的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转义元字符 * ? $ . ( ) : ! lt; | [ ] { }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地址:GitHub - naturerun/RTNWSK-RE-ENGINE: 用C实现的正则表达式引擎支持子表达式反向引用简单的预查语法一些字符类非贪婪匹配和边界匹配自己编写的正则表达式引擎可能有未知的缺陷、错误和漏洞博主自己没有那么多精力进行详尽的测试和维护如果发现错误愿意提就提出谢谢大家2019.4.25更新新增对非贪婪匹配的支持