关于正则表达式引擎
2014-01-26
这本书讲了不少关于正则表达式引擎的东西,并且花费了很大力气讲解基于回溯的NFA引擎。好像回溯是实现正则引擎的唯一算法。
事实上,有很多更高效的算法,我自己就实现过一个正则引擎,专门针对正则表达式集合的匹配,也就是说,给定很多个正则表达式(比如100万个),对输入仅扫描一遍,就能知道匹配了“哪些”正则表达式。
对于这个问题,基于回溯的算法是无能为力的。
这个需求在实际中有非常广泛的应用,在大多数情况下,程序员都会通过一些技巧去避免这个问题,比如抽取在正则中必然会出现的字符串,先过滤一遍,缩小搜索范围,然后在过滤后的小集合中逐个匹配。
所以,对于这本书中讲到的正则引擎部分,了解一下即可,不要太过认真。