测试

为了测试引擎的正确性以及评估效率,测试程序(TestRunner)是必须的。

手工创建一个测试数据集是不现实的,项目的测试程序需要一个正则表达式的集合,对于每一个正则表达式,程序使用Generex根据正则表达式生成指定数量的随机字符串,同时,程序对得到的字符串进行随机替换字符、增加字符、删除字符来获得“错误字符串”的测试数据。程序使用String类的match方法来验证匹配结果的正确性,使用System的nanoTime方法来计时。

运行

NFA

编译得到了NFA,那么可以直接运行NFA(Pattern)。

  • 开始:创建一个集合,将开始状态以及可以通过空转换到达的所有状态加入到集合中

  • 运行:每次从字符串获取一个字符a,然后根据这个字符来更新集合,对于集合中的某个状态

    • 如果状态对于字符a没有后继状态,那么丢弃改状态

    • 如果状态对于字符a转换到一个普通状态,那么将普通状态加入新的集合

    • 如果状态对于字符a转换到一个分支状态,那么将分支状态可以通过空转换到达的普通状态全部加入新的集合

  • 结束:检查最终得到的集合中是否存在匹配状态,如果存在匹配状态那么匹配成功,否则匹配失败

DFA缓存

识别正则表达式对应的字符串除了创建一个NFA以外,还可以使用DFA来识别字符串,但是由于将NFA转换为DFA需要一些时间,如果正则表达式只需要匹配少量的字符串,那么从NFA到DFA的转换的花费是不太划算的。

一种方法来加快正则表达式匹配的速度就是采用一个DFA缓存(Pattern),NFA运行过程中每个状态集合都对应着DFA中的一个状态,那么在每次匹配的时候可以将每个状态集合缓存作为DFA的状态,实现了在匹配的同时生成DFA。

DFA缓存使用DState来表示,DState包含一个NFA状态集合以及保存每个输入字符的转换到状态的Map转换表。

在运行的过程中,需要维护一个NFA集合到DFA状态的映射。

  • 开始:创建一个NFA开始状态集合,并以NFA开始状态集合创建一个开始DFA状态,在NFA集合到DFA状态映射中记录

  • 运行:每次从字符串获取一个字符a,然后查看当然的DFA状态的转换表中是否存在后继DFA状态

    • 如果存在后继DFA状态,那么将后继DFA状态设为当前DFA状态

    • 如果不存在后继DFA状态,那么求解输入字符a后,当前DFA状态的NFA状态集的后继NFA状态集,查找NFA集合到DFA状态映射:

      • 如果后继NFA状态集已经有对应的DFA状态,那么将其设为当前DFA状态

      • 如果后继NFA状态集没有对应的DFA状态,那么创建一个新的DFA状态集,在NFA集合到DFA状态映射中记录

  • 结束:检查最终得到DFA状态的集合中是否存在NFA匹配状态,如果存在NFA匹配状态那么匹配成功,否则匹配失败

效率对比

50条正则表达式,每条匹配1,000,000条“正确”字符串和1,000,000条“错误”字符串,匹配花费的时间如下:

正则表达式 NFA DFA缓存
[0-9]* 3248.369820ms 1181.475664ms
(0|[1-9][0-9]*) 1115.118540ms 1239.720798ms
([1-9][0-9]*)+(.[0-9]{1,2})? 1432.123887ms 3043.118492ms
(-)?\d+(\.\d{1,2})? 1281.132252ms 1002.347608ms
(-|\+)?\d+(\.\d+)? 2877.424149ms 1565.420089ms
[0-9]+(.[0-9]{2})? 1011.038440ms 980.673435ms
[0-9]+(.[0-9]{1,3})? 1344.435265ms 1382.108434ms
\+?[1-9][0-9]* 1254.425364ms 992.539468ms
-[1-9]\d* 2449.877165ms 772.605105ms
[1-9]\d*|0 1100.737495ms 1225.044649ms
((-\d+)|(0+)) 1758.647538ms 1021.054639ms
[1-9]\d*\.\d*|0\.\d*[1-9]\d*|0?\.0+|0 2135.412110ms 1598.832028ms
(-([1-9]\d*\.\d*|0\.\d*[1-9]\d*))|0?\.0+|0 3097.017593ms 1458.259876ms
(([0-9]+\.[0-9]*[1-9][0-9]*)|([0-9]*[1-9][0-9]*\.[0-9]+)|([0-9]*[1-9][0-9]*)) 3225.456332ms 1753.514791ms
(-(([0-9]+\.[0-9]*[1-9][0-9]*)|([0-9]*[1-9][0-9]*\.[0-9]+)|([0-9]*[1-9][0-9]*))) 2968.593472ms 1196.789934ms
-?([1-9]\d*\.\d*|0\.\d*[1-9]\d*|0?\.0+|0) 1847.559913ms 1667.214050ms
[\u4e00-\u9fa5]{0,} 409.147764ms 825.478439ms
[A-Za-z0-9]{4,40} 11048.292736ms 1076.344197ms
.{3,20} 6261.563385ms 2950.912412ms
[A-Za-z]+ 1315.031963ms 718.012986ms
[A-Za-z0-9]+ 1113.064751ms 859.847529ms
\w{3,20} 6454.282155ms 1250.905484ms
[\u4E00-\u9FA5A-Za-z0-9_]+ 953.676926ms 767.338907ms
[\u4E00-\u9FA5A-Za-z0-9]{2,20} 5542.953582ms 1276.405422ms
\w+([\-+.]\w+)*@\w+([\-.]\w+)*\.\w+([\-.]\w+)* 1451.791331ms 7004.477345ms
[a-zA-Z0-9][\-a-zA-Z0-9]{0,62}(/.[a-zA-Z0-9][\-a-zA-Z0-9]{0,62})+/.? 153719.715527ms 3923.539469ms
http://([\w\-]+\.)+[\w\-]+(/[\w\-./?%&=]*)? 1882.863760ms 1371.026083ms
(13[0-9]|14[57]|15[0-9]|18[0-9])\d{8} 2665.917080ms 1841.488264ms
(\d{3,4}-)?\d{7,8} 3629.888351ms 1392.925596ms
\d{3}-\d{8}|\d{4}-\d{7} 3704.542675ms 2725.788092ms
\d{15}|\d{18} 5698.673851ms 1477.183358ms
\d{8,18}|[0-9x]{8,18}|[0-9X]{8,18}? 7804.994578ms 2108.265730ms
[a-zA-Z][a-zA-Z0-9_]{4,15} 5264.606120ms 1147.577645ms
[a-zA-Z]\w{5,17} 6010.602110ms 1201.945454ms
\d{4}-\d{1,2}-\d{1,2} 3670.441104ms 1579.027453ms
(0?[1-9]|1[0-2]) 1192.741961ms 1407.114285ms
((0?[1-9])|((1|2)[0-9])|30|31) 1110.423738ms 1624.276991ms
[1-9][0-9]* 1379.046544ms 824.430343ms
(0|[1-9][0-9]*) 1436.854078ms 921.568423ms
(0|-?[1-9][0-9]*) 1786.390173ms 2422.465078ms
[0-9]+(.[0-9]+)? 1374.571747ms 1067.603207ms
[0-9]+(.[0-9]{2})? 1280.793922ms 966.881534ms
[0-9]+(.[0-9]{1,2})? 2760.459637ms 1067.276411ms
[0-9]{1,3}(,[0-9]{3})*(.[0-9]{1,2})? 1319.441551ms 1747.746857ms
([0-9]+|[0-9]{1,3}(,[0-9]{3})*)(.[0-9]{1,2})? 2049.082540ms 1956.539187ms
([a-zA-Z]+-?)+[a-zA-Z0-9]+\\.[xX][mM][lL] 4285.764569ms 1647.830339ms
[\u4e00-\u9fa5] 465.763439ms 682.037961ms
[\x00-\xff] 1136.996068ms 670.085364ms
[1-9][0-9]{4,} 3625.462829ms 886.284568ms
\d+\.\d+\.\d+\.\d+ 4147.255974ms 1127.045931ms
总计 290100.467854ms 76598.395404ms

虽然对于个别情况,似乎直接运行NFA效率更高,但从总体上看,添加了DFA缓存效率更高。

总结

这是我大二下学期的创新课程项目,那个时候没有没有学过编译原理,项目结构非常混乱。在学习了编译原理之后,对项目进行重构,使得项目的结构更加清晰,扩展性更好。同时,使用了Bison生成的文法分析器来代替手写的分析器,增加了DFA缓存、字符集合、重复等功能的支持。

参考资料

  1. Implementing Regular Expressions

  2. google/re2