用flex&bison代替正则表达式进行URL匹配(1)
其实这个标题稍显不妥，暂且不管。
需求：读取一个URL，一旦其符合某些规则，则将其转化为指定的格式。
场景：手机访问一个网站下的PC版的页面，对于某些页面，可以直接跳转到手机版本；而如果手机版没有对应的页面，则不需要跳转。通常手机版与PC版的页面的URL规划并不相同，那么就需要有一个跳转服务了——在服务器程序(如Apache)中建立一个模块，优先于路由执行，一旦判断用户是手机并且访问的URL符合规则，则直接HTTP 302跳转到对应的手机版的URL。
例：http://bigline.cn/blog/xxxx.html 需要转化为 http://wap.bigline.cn/blog/xxxx.html；
而 http://bigline.cn/blog/page/xxxx 则不需要进行转化
如何实现：最简单，最直接的方法，就是用正则表达式(什么是正则表达式?)了把。我们写几条规则，然后挨个进行判断，一旦符合其中一条规则，则立即生成并返回新的URL即可。
比如当前URL为博客页：”http://xxx.bigline.cn/liupc21/blog/item/5b39ae4bf9bc31ef83025c2c.html”
对应的规则为： “^http://xxx\\.bigline\\.cn/([^/]*)/blog/item/([^/]*).html”
匹配成功后，我们可以获得其中匹配到子串，分别为 liupc21 与 5b39ae4bf9bc31ef83025c2c ，分别表示用户名以及文章的ID
于是我们生成新的URL： ”http://wap.xxx.bigline.cn/liupc21/blog/item/5b39ae4bf9bc31ef83025c2c.html”
就是这么简单。
当然，在用户量大的时候，就什么事情都变得不简单了。
一下子蜂拥而至的请求，对任何程序的性能都是考验啊。假如我们设置了10条规则，用户每一次访问 Bigline.cn 上的任何一个网页的时候，都会进行匹配。这样，最好的情况是刚匹配到第一条规则就成功了，只需要匹配一次；最坏的情况当然是不在规则列表中了，得匹配十次。在最坏情况频频发生的时候，事情就不太好办了。
一个简单的解决策略就是，调整规则匹配的顺序，将容易成功的规则放在前面。例如bigline.cn是一个博客，那么它的博客页的访问显然是最多的，将匹配博客页的规则放在前面，(理想情况下，)将会减少平均的匹配次数。
但是这个方案总觉得不是很稳妥，特别是在需求的规则到了几十条的时候，又该怎么办。于是突然想到《编译原理》中使用到的flex&bison。
思路就是一个： 用一个DFA取代多个DFA。当然，如果你已经瞬间明白了，就可以不用往下看啦。不过有兴趣的话，可以查看两种方式执行效率对比的DEMO(点我下载)，有源代码哦~亲！
在11条规则，处理400条URL的时候，两者都判断出290条需要转换，且生成新的URL，用正则表达式消耗9毫秒，而用flex&bison居然只用了1ms。而实际上，前者的9毫秒并不包括编译正则表达式所需要的时间，由于正则表达式在程序每次执行的时候都要编译一遍先，得额外花上一些时间，当然，低于1ms。
Count ALL 400 URLs
Using Regexp time cost 9ms need jump 290
Using Flex&Bison Compiler time cost 1ms need jump 290
那么我就开始慢慢道来了。。。。
flex是词法分析生成器LEX的一个实现，扫描一段文字，并将其转化为一段TOKEN序列。例如在某种规则下，读入”this is a word”，则会得到四个TOKEN，分别是{“this”,”is”,”a”,”word”}。当然，flex的功能远比这个强大，自己定义规则之后，想怎样识别都没有问题啊。(更多介绍 点我)。
bison则是一个采用LALR(1)文法的语法分析器，配合flex简直天下无双啊。通过一系列产生式，将flex生成的TOKEN列表规约到我们需要的结果，并能在规约过程中进行各种处理，当然，编译器就是这样实现的啦。(更多介绍 点我)
而实际上，flex与bison的工作原理都是：将我们编好的规则依据某些算法，生成一个确定型的有穷自动机(DFA)。即有程序负责读取每一个字符(或TOKEN)，并跳转到对应的状态。
例如，状态A读入某字母X后能跳转到状态B，而状态B读入X则跳转到状态A，最终到达某个终止状态Z的时候，就终止读取了。当然，在某个状态读入某个X的时候，发现可以跳转到好几个状态去，那这就是NFA了。(点我看更多)
那么这个跟正则表达式有什么关系呢？真相就是，每一条正则表达式背后，都是一个默默工作着的DFA啊！在各种语言中，编译器/解释器会将每一条正则表达式编译成一个DFA，它碰到字符串输入的时候，就开始在各个状态之间跳来跳去了，当跳到某个状态表示匹配成功了，就把数据输出来。
回到最初的话题，如果我们有20条规则，那么会生成20个DFA，那么有无可能减少甚至合并成1个？BINGO！我跟你想到一块去了！
当然，直接把这些DFA进行合并不太可能——相当于重写个正则表达式的解析器，且目前网上比较出名的几个正则解析器都是经过各种精心优化的，绝对不是盖的。不过特殊情况特殊分析，在flex&bison中设置一些规则，是不是也能起到识别的作用呢？而且无论规则有多少条，编译后的DFA只有两个：一个在flex中用来扫描URL并转化成TOKEN列表，另外一个则在Bison中用于分析flex扫描得到的TOKEN序列。
理论上，这样会比直接正则表达式直接上阵快很多，具体怎么样，还是得实事求是，数据说话。
于是我分别实现了相同的11条规则下，分别用正则和编译器处理同样数据的时间消耗对比DEMO，代码在这里(点我下载)
具体怎么实现，且听下回分解。
注：可能需要根据实际情况修改Makefile，使用GCC进行编译.同时需要Flex&Bison&Regex的库，在windows下，可以去GnuWin32的主页上下载
