写在前面

做码农的，应该基本都写过正则表达式吧？匹配合法的邮箱手机号之类的都会用到正则表达式匹配。正则表达式语法非常简单，但是功能很强大，几乎能匹配所有格式的字符串。正则表达式几乎是所有现代语言都有支持库的，在所有语言里都可以使用。功能强大，应用广泛，是现代码农的必备技能之一。

正则表达式是啥？

正则表达式（regular expression）简称regex，又叫规则表达式。是一套描述字符串匹配模式的符号集。常见的如同“+”,"*","?"等，都是非常常用的符号。

正则表达式最早是一些数学研究里用来表示某种模型的符号集，后来被Ken Thompson大神，也就是unix操作系统以及c语言之父，将这套符号表示用在了自己开发的编辑器QED里面。随着unix的流行，正则表达式也逐渐在unix类系统里面应用广泛，比如vi，grep，awk等等命令，都支持正则表达式。只不过有些命令支持得比较简单，有些则比较完备。

后来随着perl语言的流行，perl里将正则表达式作为了一直内置的类型，而且使用起来非常简单，对正则表达式进行了扩展，支持的功能更加强大。perl很长一段时间，都是*nix类系统下面的主流脚本语言。对正则表达式的支持，使得perl字符串处理能力非常强大，也是它流行的重要原因之一。

因为perl对正则表达式的扩展十分强大，以至于后来原本IEEE组织制定了正则表达式的Posix标准之后，因为perl的扩展又分出一个perl样式正则表达式的分支PCRE(Perl Compatible Regular Expressions)，相信大家都听说过。事实上大部分编程语言里的regex是PCRE，当然也有posix和PCRE都支持的，而*nix工具里则主要是使用posix标准。PCRE同时也是一个大名鼎鼎的正则表达式库的名字，相信关注过的同学都知道。

除了少数语法上的区别，posix和PCRE大部分语法是一致的。有些不同，像PCRE支持反向引用，posix标准里没确定是否支持，但是大多数实现里都支持。

正则表达式怎么实现的？

有人肯定好奇于这么强大的工具到底如何实现的。其实也不难，一般是把正则表达式转化为NFA

或DFA，然后学过编译原理的同学肯定知道下面该如何做了，一般就是构建解析表之类的。但是也有把正则表达式作为一种微型语言，编译成虚拟机opcode，然后通过虚拟器去执行，这样虽然麻烦，但好处就是很容易优化，甚至通过jit转化为机器码执行。

下面附带Rob Pike大神曾经写过的一个极简的正则表达式引擎，只支持'^','#39;,'.','*'几种符号，不过也能满足不少简单需求了，代码不过30来行。

int match(char *regexp,char *text)  
{  
 if(regexp[0] == '^')  
  return matchhere(regexp+1,text);  
 do{ 
  if (matchhere(regexp,text))  
   return 1;  
 }while (*text++!= '\0');  
 return 0;  
}  

int matchhere(char *regexp,char *text)  
{  
 if (regexp[0] == '\0')  
  return 1;  
 if (regexp[1] == '*')  
  return matchstar(regexp[0],regexp+2,text);  
 if (regexp[0] == '#39; && regexp[1]=='\0')  
  return *text == '\0';  
 if (*text!='\0' && (regexp[0]=='.' || regexp[0]==*text))  
  return matchhere(regexp+1,text+1);  
 return 0;  
}  

int matchstar (int c,char *regexp,char *text)  
{  
 do { 
  if (matchhere(regexp,text))  
   return 1;  
 }while (*text!='\0' && (*text++ ==c || c== '.'));  
 return 0;  
}