神奇的regex
2012-03-17
主要看了前六章，重点是三四章，JS和Perl没用过，也没时间学，.Net虽然强大但根本勾不起我学习的欲望。
从这本书学到的东西已经够我去使用vim,grep,awk了，sed的多行模式还没掌握。
最大的收获其实是作者竭力想避免提及的(但还是说得很清楚了)：DFA和NFA。主要是注意到正则表达式竟然是基于一种纯数学的理论稍加修改而成的。D就是确定，N就是不确定，确定和非确定有穷状态自动机最后将产生相同的结果，但路径不同。(这跟P与NP也能扯上关系啊，NP>=P，那是不是就是说NFA还是比较强大的【其实一直不明白为什么NP>=P】。但明明是DFA先出现，而基于DFA的正则引擎却后出现。)
NFA引擎较先出现，匹配效率对表达式的质量依赖很强(所以书中说NFA是基于表达式的)，因为相当于在状态空间做了一次DFS，找到匹配之前可能已经经过了很多回溯。而DFA与表达式的质量无关，所有等价的表达式的效率都一样，它是由文本驱动的。但学习正则表达式的乐趣其实是NFA，它有更大的改进空间，而且支持反向引用(还有一个特性也是DFA不支持的现在一时想不起)。很难想像没有反向引用regex还有什么意思。
/********************************/
(与此书无关，但与regex有关)
有人总是觉得这本书讲得太详细，regex根本没必要学得这么深入。但我觉得看完还是很有收获的，Linux上几乎处处都会用到regex，从简单的支持ls(1),mv(1),到专门的grep(1),sed(1),awk(1)，这和Unix对文本的偏爱有关：很多命令的输出都是整屏的文本，配置文件都写在文本里，如果不用regex，难道要肉眼去找。
话又说回来，regex的一点点好处就已经够用了，平时写程序也用不到太复杂的。而且像很多特性，加转义和不加转义，三个环境可能有六种方案(有的可以设置成多种不同的方案，例如vim)。
/********************************/
这本书去年暑假在图书馆借的，上星期才还，终于没有看完最后几章针对具体语言的讲解。