您所在位置：主题：[原创]正则表达式的简单解说
toyasimple
[专家分：820] 发布于 2007-04-05 20:58:00
正则表达式的简单解说
正则表达式（regular expression）描述了一种字符串匹配的格式,在很多地方都很有用。比如在一个编辑器中可以用来查找和替换字符串。另外在一些网站中也可以用正则表达式进行搜索。在C++的Boost库中也有一个正则表达式的类。Perl，Java也需要用到正则表达式。
正则表达式的写法很是奇特，初看起来还有点乱糟遭的感觉。在这里我只想简单的说说它的描述格式。要是不知道什么是正则表达式，我想你对这帖子也没有什么兴趣的了。可以不看。现在转入正题。
//>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>
大家都应该知道集合的概念了，我的介绍是从集合开始。
假如有一个正则表达式r，如果有一个字符串符合它描述的格式，我们就称字符串匹配了表达式。所有匹配正则表达式的字符串组成一个集合，记为L(r).
定义一个集合,里面的元素是单个的字符,比如{a, b, c, d}，这个集合称为正则表达式的字母表，这个集合是可以随意定义的。可以判断你用的字符是否合法。
基本正则表达式。也就是上面定义集合中的单个字符的字串。比如a, b, c, d, 还有一个空字符串,记为NULL(本来是用个希腊字母来表示的，不过打不出来,用这个替代)。这样有L(a) = {a}. L(b)={b}. L(NULL)={NULL}. 基本正则表达式是一个合法的正则表达式。
在正则表达式上有三种基本的运算：选择，连接，重复。一个有效的正则表达式经过有限次的运算，也是一个有效的正则表达式。
注: 上面的定义有点怪，不过很多都是为了逻辑上的严谨，其实不难，想通了就很自然了。想一想我们以前学有理式的定义，也是这样的。一个字母就是一个有效的有理式，有理式经过有限次的四则运算，也是一个有理式。还有Lisp语言中表的定义，一个字串称为原子，一个原子是一个表，表排在一起，也是一个表。
好，想通了之后，跟着定义我们正则表达式的基本运算。只有三个。
(1)选择。r和s都是正则表达式，这运算记为r|s。选择就是说，假如一个字串可以匹配r或者可以匹配s，就一定可以匹配r|s。再解释一下，L(r)表示所有匹配r的字串的集合，L(s)表示所有匹配s的字串的集合，L(r|s)表示所有匹配r|s的字串的集合。有 L(r|s)=L(r)并L(s)。理解正则表达式可以试试用集合的角度。比如L(a)={a}, L(b)={b}, L(a|b)={a, b}.
(2)连结。没有什么，就是两个正则表达式连在一起，就写成rs。从集合的角度，就是L(rs)=L(r)L(s)。比如 (a|b)c代表的集合是 {a,b}{c}={ac, bc}. 集合的连接很难说清楚，不过举个例子就可以了，比如{a, b}{c, d} = {ac, ad, bc, bd}.
(3)重复。将一个正则表达式重复任意次，包括0次，记为r* 。重复2次就是自身连结两次，重复3次就是自身连结三次。还是不太明白，举个例子。L(a*)={NULL,a,aa,aaa,aaaa,aaaaa,......}。因为它可以重复任意多次，包括0次(重复0次就是NULL), 这样的话 a, aaa, aaaa都可以匹配 a* .
//>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>
上面的三种运算要好好想一下，所有的复杂的正则表达式都是由上面三种运算构成。既然有运算，就会牵涉到运算的优先问题，现在规定几个运算合在一起，先算重复运算，再算连结，再算选择。而括号可以改变优先，有括号先算括号里面的。
好啦，现在来看一个简单的例子，用正则表达式来表示所有的整数
(NULL|+|-)(0|1|2.....|9)(0|1|2|3....9)*
这样也太麻烦了，要是我们再设一个规则，就是可以给正则表达式取个名字，之后这个名字就代表了这个表达式。上面的式子可以写成
sign = NULL | + | -
digit = 0|1|2....|9
integer = (sign)(digit)(digit)*
(digit)(digit)* 的意思是保证数字至少要出现一次。
//>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>
其实上面定义的三种运算已经可以写出所有的正则表达式了，不过你看到，有些地方单纯用上面的运算，不是很方便。因此，再定义其他的一些运算，称为正则表达式运算的扩展（不同的语言，不同的场合可能包括不同的扩展,举些常用的)。不过你要知道，所有的其他运算都可以用上面选择，连结、重复的运算表达出来, 那三种运算是基本中的基本。知道了基本，其他的运算就很容易掌握了。
(1)重复一次或者多次，记为r+。最基本的重复的运算是可以重复0次的，不过0次并非是典型的情况，至少要重复一次才是比较常用的。可以知道r+等效于 rr*, 上面的例子也就可以写成 (NULL|+|-)(0|1|2.....|9)+
(2)重复n次, 记为r{n},比如L(a{2}={aa}). 而重复i次到j次，就是 r{i,j}, 比如L(a{1,3})={a, aa, aaa}。至少重复n次，就是r{n,}。比如L(a{3,})={aaa, aaaa, aaaaa,.....}
(3)任意字符，记为 .(也就是小数点)。这个等效于整个字母表作选择运算。比如一个字串至少要包括一个b，可以写成 .*b.*
(4)字符范围, 比如[0-9]，表示可以取0到9任意一个，等效于0|1|2|3....|9。经常需要写出一定的字符范围，设想你刚开始定义的字母表按照一定的顺序排列，这个式子就在字母表上划了一个范围。通常我们用的编程语言按照ASCII排列。另外[]还有个用法，[akgs]等效于a|k|g|s, 所有的字母抽一个可以写成[A-Za-z]，应该可以看明白，不解释了。这时候列出所有的整数可以写成 [(NULL)+-][0-9]+
(5)不在给定集合中的任意字符。这其实是一个取补运算，用~表示。比如~(a|b|c)就是除了a,b,c之外的任意字符~(NULL)就是定义的字母表，等效于 . 。不过更多时候，这个运算用^表示，比如[^abc], [^(NULL)].
(6)可选的子表达式。用?表示。比如[ab]? 就等效于[(NULL)ab],也等效于[ab]{0,1}也就是说，可以选择a,可以选择b,也可以都不选择。所以所有的整数可以表示为 ([-+]?)[0-9]+
..........
//>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>
当然，不同的语言符号可能也不尽不同，还会有另外的规则，比如C++中还要注意一下转义字符。最先定义的三个运算最为重要,要先掌握。只要将上面说的基本运算综合起来，正则表达式可以表现很复杂的字符格式，表示起来也很灵活。自己再慢慢研究吧。
不过正则表达式也不是所有的字符集合都可以表示出来。比如
S={b, aba, aabaa, aaabaaa....}={(a^n)b(a^n) | n != 0}就没有办法统一表示。
主要参考：
《揭开正则表达式的神秘面纱》百度上搜搜，很多。
<编译原理及实际>(Kenneth C Louden) P23-32. (我只不过将它的意思再写一下）
正则表达式（regular expression）描述了一种字符串匹配的格式,在很多地方都很有用。比如在一个编辑器中可以用来查找和替换字符串。另外在一些网站中也可以用正则表达式进行搜索。在C++的Boost库中也有一个正则表达式的类。Perl，Java也需要用到正则表达式。
正则表达式的写法很是奇特，初看起来还有点乱糟遭的感觉。在这里我只想简单的说说它的描述格式。要是不知道什么是正则表达式，我想你对这帖子也没有什么兴趣的了。可以不看。现在转入正题。
//>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>
大家都应该知道集合的概念了，我的介绍是从集合开始。
假如有一个正则表达式r，如果有一个字符串符合它描述的格式，我们就称字符串匹配了表达式。所有匹配正则表达式的字符串组成一个集合，记为L(r).
定义一个集合,里面的元素是单个的字符,比如{a, b, c, d}，这个集合称为正则表达式的字母表，这个集合是可以随意定义的。可以判断你用的字符是否合法。
基本正则表达式。也就是上面定义集合中的单个字符的字串。比如a, b, c, d, 还有一个空字符串,记为NULL(本来是用个希腊字母来表示的，不过打不出来,用这个替代)。这样有L(a) = {a}. L(b)={b}. L(NULL)={NULL}. 基本正则表达式是一个合法的正则表达式。
在正则表达式上有三种基本的运算：选择，连接，重复。一个有效的正则表达式经过有限次的运算，也是一个有效的正则表达式。
注: 上面的定义有点怪，不过很多都是为了逻辑上的严谨，其实不难，想通了就很自然了。想一想我们以前学有理式的定义，也是这样的。一个字母就是一个有效的有理式，有理式经过有限次的四则运算，也是一个有理式。还有Lisp语言中表的定义，一个字串称为原子，一个原子是一个表，表排在一起，也是一个表。
好，想通了之后，跟着定义我们正则表达式的基本运算。只有三个。
(1)选择。r和s都是正则表达式，这运算记为r|s。选择就是说，假如一个字串可以匹配r或者可以匹配s，就一定可以匹配r|s。再解释一下，L(r)表示所有匹配r的字串的集合，L(s)表示所有匹配s的字串的集合，L(r|s)表示所有匹配r|s的字串的集合。有 L(r|s)=L(r)并L(s)。理解正则表达式可以试试用集合的角度。比如L(a)={a}, L(b)={b}, L(a|b)={a, b}.
(2)连结。没有什么，就是两个正则表达式连在一起，就写成rs。从集合的角度，就是L(rs)=L(r)L(s)。比如 (a|b)c代表的集合是 {a,b}{c}={ac, bc}. 集合的连接很难说清楚，不过举个例子就可以了，比如{a, b}{c, d} = {ac, ad, bc, bd}.
(3)重复。将一个正则表达式重复任意次，包括0次，记为r* 。重复2次就是自身连结两次，重复3次就是自身连结三次。还是不太明白，举个例子。L(a*)={NULL,a,aa,aaa,aaaa,aaaaa,......}。因为它可以重复任意多次，包括0次(重复0次就是NULL), 这样的话 a, aaa, aaaa都可以匹配 a* .
//>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>
上面的三种运算要好好想一下，所有的复杂的正则表达式都是由上面三种运算构成。既然有运算，就会牵涉到运算的优先问题，现在规定几个运算合在一起，先算重复运算，再算连结，再算选择。而括号可以改变优先，有括号先算括号里面的。
好啦，现在来看一个简单的例子，用正则表达式来表示所有的整数
(NULL|+|-)(0|1|2.....|9)(0|1|2|3....9)*
这样也太麻烦了，要是我们再设一个规则，就是可以给正则表达式取个名字，之后这个名字就代表了这个表达式。上面的式子可以写成
sign = NULL | + | -
digit = 0|1|2....|9
integer = (sign)(digit)(digit)*
(digit)(digit)* 的意思是保证数字至少要出现一次。
//>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>
其实上面定义的三种运算已经可以写出所有的正则表达式了，不过你看到，有些地方单纯用上面的运算，不是很方便。因此，再定义其他的一些运算，称为正则表达式运算的扩展（不同的语言，不同的场合可能包括不同的扩展,举些常用的)。不过你要知道，所有的其他运算都可以用上面选择，连结、重复的运算表达出来, 那三种运算是基本中的基本。知道了基本，其他的运算就很容易掌握了。
(1)重复一次或者多次，记为r+。最基本的重复的运算是可以重复0次的，不过0次并非是典型的情况，至少要重复一次才是比较常用的。可以知道r+等效于 rr*, 上面的例子也就可以写成 (NULL|+|-)(0|1|2.....|9)+
(2)重复n次, 记为r{n},比如L(a{2}={aa}). 而重复i次到j次，就是 r{i,j}, 比如L(a{1,3})={a, aa, aaa}。至少重复n次，就是r{n,}。比如L(a{3,})={aaa, aaaa, aaaaa,.....}
(3)任意字符，记为 .(也就是小数点)。这个等效于整个字母表作选择运算。比如一个字串至少要包括一个b，可以写成 .*b.*
(4)字符范围, 比如[0-9]，表示可以取0到9任意一个，等效于0|1|2|3....|9。经常需要写出一定的字符范围，设想你刚开始定义的字母表按照一定的顺序排列，这个式子就在字母表上划了一个范围。通常我们用的编程语言按照ASCII排列。另外[]还有个用法，[akgs]等效于a|k|g|s, 所有的字母抽一个可以写成[A-Za-z]，应该可以看明白，不解释了。这时候列出所有的整数可以写成 [(NULL)+-][0-9]+
(5)不在给定集合中的任意字符。这其实是一个取补运算，用~表示。比如~(a|b|c)就是除了a,b,c之外的任意字符~(NULL)就是定义的字母表，等效于 . 。不过更多时候，这个运算用^表示，比如[^abc], [^(NULL)].
(6)可选的子表达式。用?表示。比如[ab]? 就等效于[(NULL)ab],也等效于[ab]{0,1}也就是说，可以选择a,可以选择b,也可以都不选择。所以所有的整数可以表示为 ([-+]?)[0-9]+
..........
//>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>
当然，不同的语言符号可能也不尽不同，还会有另外的规则，比如C++中还要注意一下转义字符。最先定义的三个运算最为重要,要先掌握。只要将上面说的基本运算综合起来，正则表达式可以表现很复杂的字符格式，表示起来也很灵活。自己再慢慢研究吧。
不过正则表达式也不是所有的字符集合都可以表示出来。比如
S={b, aba, aabaa, aaabaaa....}={(a^n)b(a^n) | n != 0}就没有办法统一表示。
主要参考：
《揭开正则表达式的神秘面纱》百度上搜搜，很多。
<编译原理及实际>(Kenneth C Louden) P23-32. (我只不过将它的意思再写一下）
