神马文学网正则表达式及其他
来源：百度文库 编辑：神马文学网 时间：2024/04/27 21:49:22
正则表达式及其他
2004年6月29日 16:10
什么是正则表达式呢？正则表达式实际上是一个主要用来描述字符串匹配的工具，当然也可以用来匹配其它的东西例如二进制数据，用在字符串方面可能是最常见的。说到这里，可能大家会联想到如下几个主题：
怎么排除恶意的脚本代码？要写一个脚本语言引擎或者编译器，是否可以用正则表达式来完成？编译原理？
实际上要说清楚这里面的所有问题也许已经超出了我的能力范围了，但是我还是要写下来，再不写下来也许哪天我就真的忘得一干二净了。
首先说正则表达式吧。正则表达式实际上使用的是一个不确定有穷自动机，Non-deterministic finite automaton，简称NFA。而编译原理一般使用的是确定有穷自动机（一般就叫有穷自动机，或者有限自动机，其他的说法还包括确定的有限状态自动机），Deterministic finite automaton，简称DFA。关于这几个概念的简单解释，随便Goo一下有穷自动机就能够找到一大堆，这里推荐一个。NFA和DFA有什么区别呢？最简单的区别就是NFA对同一个字符串输入完全有可能有多种理解方式，而DFA则只有唯一的一种理解方式。从这里我们可以简单的理解到NFA所能够接受的规则并不一定都能够转化为DFA所理解的规则。事实上区别在NFA和DFA的分析过程当中就能够体现出来了，对于NFA来说，很可能需要探测某一种接受方式，当出现不接受的时候就可能需要退出一层，尝试另外一种可能的接受方式。而对于DFA则不一样，因为只可能有一种确定的理解方式，因此一旦不匹配，就不需要再做别的尝试，而可以直截了当的说“不匹配”。因此反过来说，由于DFA只有一种理解方式，所以效率明显应该比NFA要高。在上面的推荐的地方给出了更为简洁的说法：NFA和DFA的唯一区别就在于状态转移函数不一样。
编译器进行词法分析时所用到的分析公式实际上看起来应该跟正则表达式很相似，那么这个表达式应该是一个什么样的样子呢？实际上我们都很熟悉这样的东西：
S -> A
A -> aA|B
B -> b
上面则三条式子就是状态转移函数了，或者你可以理解成推导公式。里面的SABab就是所有有可能的状态集合，其中SAB三个是非终结符，ab两个是终结符，S是初始状态。对于上面这样的推导公式，可以知道这个系统只接受两种输入：a...a或者a...ab。为什么这里要引入A、B这样的非终结符呢？因为很多时候我们要描述这样一个系统的时候，会经常地遇到一些重复的可定义的部分，就比如一个到多个空格\s+，我们完全可以把这些东西直接写出来，甚至直接用一条式子表达出来，但是这样做就会非常的麻烦和困难。为了简便，很多时候都会将一些重复的，或者比较冗长的，或者比较重要的部分归纳成一个非终结符。非终结符的定义也不是随随便便的，而是有一定的规则的，这个规则这里就不讨论了。
对于编译器来说，主要有两种构造DFA的方式，一种是LL分析方法，另外一种是LR分析方法。这两种都是基于输入预测的分析方法，但是分析的方法却大有不同，LL属于推导的方式，LR则属于归纳的方式。如果这么说不好记，那么就记住LL指的是从左向右输入，从左向右推导；LR是从左向右输入，从右向左归纳。LL比较符合人的思维方式，但是却有一些局限性。LR则比较难理解，但是适用范围却比LL要广泛一点，效率也高一点。
说了半天好像跟正则表达式搭不上边，其实那些使一些准备知识，下面来仔细的说正则表达式。大家看上面我给的那三条推导公式，实际上如果全部用终结符来表示，那么应该是：
a*(a|b)
这就是正则表达式了。因为给整个机器定义一大堆的规则和状态转移函数是比较复杂和不必要的，对于一般的字符串匹配来说，因此给正则表达式的执行机构提供一个简单的、完全用终结符描述出来的匹配字符串就足够了。
但是这并不代表着我们也应该直接用终结符来构造整个的正则表达式，这样做会非常复杂和痛苦的，因为一个稍微复杂一点的匹配，正则表达式就会复杂到让你看不明白，或者看的头痛。光是括号的配对就足够让你忙上半天的了，还有转义符等其他的东西呢。因此，我们完全有必要像上面说的那样，定义出非终结符，高效率的创造正则表达式的关键就在于此。然而很可惜的是正则表达式本身并没有这样的定义，而.NET也没有给我们提供这样的定义接口。更可惜的是，绝大部分在那里制作正则表达式创建工具的人，根本就没有想到这一点。拿上一次我提到的Regulator来说，有Analyzer把整个的表达式翻译成英语，有Snippet提供编写的便利性，还有很好的文本编辑器，不过仅此而已。Analyzer对于看懂一个正则表达式也许是有帮助的，但是它对于你想自己构造一个正则表达式没有什么帮助。Snippet是仿照C#2.0里面的先进东西，然而构造正则表达式不是写程序，写几个括号尖括号等等并不是最影响效率的问题，同时正则表达式也没有什么Pattern的问题，因此实际上Snippet对于构造一个正则表达式也没有什么帮助。而那个很完美的文本编辑器更是没有跳出用终结符来构造的框框，也不会对提高效率有什么帮助。大家可以试一下用我的正则表达式构造器就知道我所提出的概念是什么意思了。
那么构造正则表达式需要注意一些什么呢？虽然说NFA因为不确定，所以限制比DFA要少，构造起来也比较方便一点。但是不好的构造方式会引起效率低下的问题，因此要尽量：
1、避免不确定的情况发生。解决的办法是尽可能使用(?>A|B)来代替A|B或者(?:A|B)这样的形式。（A、B代表一个很长的正则表达式字符串）
2、尽量避免递归层次过高的情况。eg:
a*(b*(c|d)|b*(e|f)|b*(g|h))|a*(b*(i*(j|k)|i*(l|m)|i*(n|o))
这样对于一个a...b...i...o 这样的字符串将会是一件非常痛苦的事情，因为匹配的过程将会经历：
a*b*c -> a*b* ->a*b*d -> a* -> a*b*e -> a*b* -> a*b*f -> a* -> a*b*g ->... 这样一系列的分析->回溯的过程，才能够到达a*b*i*o这个匹配。上述表达式最好能够改造成：a*b*(c|d|e|f|g|h|i*(j|k|l|m|n|o)) 这种形式。如果因为需要通过“组”来归类，那么建议你修改你的“语言格式”，或者尽量减少分组的情况，或者通过匹配之后再用程序代码来确定实际的分类情况。
3、如果可以的话，比如你要处理的问题比较复杂，就进行简单的分步处理，以减少表达式的复杂度。表达式越简单，就越有可能效率高，而设计失误的可能性也比较少。分布也不要太多，毕竟一次分析也是需要花费时间的。
反馈
# 回复: 正则表达式及其他
2004-6-29 17:49 by
我的感觉正则表达式我可以花上1天半天的时间学的很熟,但是过了10天半个月又忘的差不多了,只记得几个最简单的规则,对于高级一点的则完全模糊...如此反复,很是郁闷,该如何学习效果才能更好一些呢？
# 回复: 正则表达式及其他
2004-6-30 10:18 bysumtec
我不知道你绝不觉得，当你学完了高数之后，也许你会把高数给忘得差不多了，但是加减法会不会忘了这个你肯定不会再担心的了。所以，如果你想不要忘记某样知识，那你就深究下去，学到你实在学不懂了，这个时候大概你想记住的东西已经记忆很深刻了。
# 回复: 正则表达式及其他
2004-6-30 10:44 by
好的学习方法，我有时也是这样学习的。
这篇文章使我想起了大学时学习编译原理的情景，回忆ing
# 回复: 正则表达式及其他
2004-6-30 10:49 by重粒子
似乎没有写完啊。继续继续。。。鼓掌
# re: 正则表达式及其他
2004-9-9 23:36 bylaily
good
# re: 正则表达式及其他
2004-11-9 9:44 by
谁有正则表达式相关的资料,能给些吗?
wqb119@126.com
# re: 正则表达式及其他
2005-1-20 13:24 by
I spent a long time on it. but at last,I realized that it was not writen for beginner but for anyone who have know this.
# re: 正则表达式及其他
2005-3-15 20:42 by
我写了个正则表达式、正则文法、有穷自动机的互相转换程序，愿意提交上来，绝对免费，大家互相研究研究，有需要的吗？
# re: 正则表达式及其他
2005-3-15 20:42 by
我写了个正则表达式、正则文法、有穷自动机的互相转换程序，愿意提交上来，绝对免费，大家互相研究研究，有需要的吗？
# re: 正则表达式及其他
2005-5-9 21:15 by
有需要。提交上来大家看看啊。
# re: 正则表达式及其他
2005-5-16 10:14 by
提交上来啊,兄弟!我正需要呢!或者请发到我的email:linuxzhou@sohu.com
# re: 正则表达式及其他
2005-5-16 12:13 by
very good.give me a copy.it is my email: ajian101@163.com
thank you!!
# re: 正则表达式及其他
2005-6-2 14:01 by
我需要啊，能发给我一份吗？谢谢！
pic310@163.com
# re: 正则表达式及其他
2005-6-18 16:45 by
S -> A
A -> aA|B
B -> b
他们能导出的所有字符串似乎是a*b,阁下的a*(a|b).......
# re: 正则表达式及其他
2005-9-16 20:46 by
大虾 能给我一份你的正则表达式、正则文法、有穷自动机的互相转换程序吗 ？
我要远程序 我的邮箱 是 cuiwenhaichao@yahoo.com.cn
# re: 正则表达式及其他
2005-9-27 10:05 by
我正急用，师兄，给一个吧：mazy0925@hotmail.com
先谢了！
2004年6月29日 16:10
什么是正则表达式呢？正则表达式实际上是一个主要用来描述字符串匹配的工具，当然也可以用来匹配其它的东西例如二进制数据，用在字符串方面可能是最常见的。说到这里，可能大家会联想到如下几个主题：
怎么排除恶意的脚本代码？要写一个脚本语言引擎或者编译器，是否可以用正则表达式来完成？编译原理？
实际上要说清楚这里面的所有问题也许已经超出了我的能力范围了，但是我还是要写下来，再不写下来也许哪天我就真的忘得一干二净了。
首先说正则表达式吧。正则表达式实际上使用的是一个不确定有穷自动机，Non-deterministic finite automaton，简称NFA。而编译原理一般使用的是确定有穷自动机（一般就叫有穷自动机，或者有限自动机，其他的说法还包括确定的有限状态自动机），Deterministic finite automaton，简称DFA。关于这几个概念的简单解释，随便Goo一下有穷自动机就能够找到一大堆，这里推荐一个。NFA和DFA有什么区别呢？最简单的区别就是NFA对同一个字符串输入完全有可能有多种理解方式，而DFA则只有唯一的一种理解方式。从这里我们可以简单的理解到NFA所能够接受的规则并不一定都能够转化为DFA所理解的规则。事实上区别在NFA和DFA的分析过程当中就能够体现出来了，对于NFA来说，很可能需要探测某一种接受方式，当出现不接受的时候就可能需要退出一层，尝试另外一种可能的接受方式。而对于DFA则不一样，因为只可能有一种确定的理解方式，因此一旦不匹配，就不需要再做别的尝试，而可以直截了当的说“不匹配”。因此反过来说，由于DFA只有一种理解方式，所以效率明显应该比NFA要高。在上面的推荐的地方给出了更为简洁的说法：NFA和DFA的唯一区别就在于状态转移函数不一样。
编译器进行词法分析时所用到的分析公式实际上看起来应该跟正则表达式很相似，那么这个表达式应该是一个什么样的样子呢？实际上我们都很熟悉这样的东西：
S -> A
A -> aA|B
B -> b
上面则三条式子就是状态转移函数了，或者你可以理解成推导公式。里面的SABab就是所有有可能的状态集合，其中SAB三个是非终结符，ab两个是终结符，S是初始状态。对于上面这样的推导公式，可以知道这个系统只接受两种输入：a...a或者a...ab。为什么这里要引入A、B这样的非终结符呢？因为很多时候我们要描述这样一个系统的时候，会经常地遇到一些重复的可定义的部分，就比如一个到多个空格\s+，我们完全可以把这些东西直接写出来，甚至直接用一条式子表达出来，但是这样做就会非常的麻烦和困难。为了简便，很多时候都会将一些重复的，或者比较冗长的，或者比较重要的部分归纳成一个非终结符。非终结符的定义也不是随随便便的，而是有一定的规则的，这个规则这里就不讨论了。
对于编译器来说，主要有两种构造DFA的方式，一种是LL分析方法，另外一种是LR分析方法。这两种都是基于输入预测的分析方法，但是分析的方法却大有不同，LL属于推导的方式，LR则属于归纳的方式。如果这么说不好记，那么就记住LL指的是从左向右输入，从左向右推导；LR是从左向右输入，从右向左归纳。LL比较符合人的思维方式，但是却有一些局限性。LR则比较难理解，但是适用范围却比LL要广泛一点，效率也高一点。
说了半天好像跟正则表达式搭不上边，其实那些使一些准备知识，下面来仔细的说正则表达式。大家看上面我给的那三条推导公式，实际上如果全部用终结符来表示，那么应该是：
a*(a|b)
这就是正则表达式了。因为给整个机器定义一大堆的规则和状态转移函数是比较复杂和不必要的，对于一般的字符串匹配来说，因此给正则表达式的执行机构提供一个简单的、完全用终结符描述出来的匹配字符串就足够了。
但是这并不代表着我们也应该直接用终结符来构造整个的正则表达式，这样做会非常复杂和痛苦的，因为一个稍微复杂一点的匹配，正则表达式就会复杂到让你看不明白，或者看的头痛。光是括号的配对就足够让你忙上半天的了，还有转义符等其他的东西呢。因此，我们完全有必要像上面说的那样，定义出非终结符，高效率的创造正则表达式的关键就在于此。然而很可惜的是正则表达式本身并没有这样的定义，而.NET也没有给我们提供这样的定义接口。更可惜的是，绝大部分在那里制作正则表达式创建工具的人，根本就没有想到这一点。拿上一次我提到的Regulator来说，有Analyzer把整个的表达式翻译成英语，有Snippet提供编写的便利性，还有很好的文本编辑器，不过仅此而已。Analyzer对于看懂一个正则表达式也许是有帮助的，但是它对于你想自己构造一个正则表达式没有什么帮助。Snippet是仿照C#2.0里面的先进东西，然而构造正则表达式不是写程序，写几个括号尖括号等等并不是最影响效率的问题，同时正则表达式也没有什么Pattern的问题，因此实际上Snippet对于构造一个正则表达式也没有什么帮助。而那个很完美的文本编辑器更是没有跳出用终结符来构造的框框，也不会对提高效率有什么帮助。大家可以试一下用我的正则表达式构造器就知道我所提出的概念是什么意思了。
那么构造正则表达式需要注意一些什么呢？虽然说NFA因为不确定，所以限制比DFA要少，构造起来也比较方便一点。但是不好的构造方式会引起效率低下的问题，因此要尽量：
1、避免不确定的情况发生。解决的办法是尽可能使用(?>A|B)来代替A|B或者(?:A|B)这样的形式。（A、B代表一个很长的正则表达式字符串）
2、尽量避免递归层次过高的情况。eg:
a*(b*(c|d)|b*(e|f)|b*(g|h))|a*(b*(i*(j|k)|i*(l|m)|i*(n|o))
这样对于一个a...b...i...o 这样的字符串将会是一件非常痛苦的事情，因为匹配的过程将会经历：
a*b*c -> a*b* ->a*b*d -> a* -> a*b*e -> a*b* -> a*b*f -> a* -> a*b*g ->... 这样一系列的分析->回溯的过程，才能够到达a*b*i*o这个匹配。上述表达式最好能够改造成：a*b*(c|d|e|f|g|h|i*(j|k|l|m|n|o)) 这种形式。如果因为需要通过“组”来归类，那么建议你修改你的“语言格式”，或者尽量减少分组的情况，或者通过匹配之后再用程序代码来确定实际的分类情况。
3、如果可以的话，比如你要处理的问题比较复杂，就进行简单的分步处理，以减少表达式的复杂度。表达式越简单，就越有可能效率高，而设计失误的可能性也比较少。分布也不要太多，毕竟一次分析也是需要花费时间的。
反馈
# 回复: 正则表达式及其他
2004-6-29 17:49 by
我的感觉正则表达式我可以花上1天半天的时间学的很熟,但是过了10天半个月又忘的差不多了,只记得几个最简单的规则,对于高级一点的则完全模糊...如此反复,很是郁闷,该如何学习效果才能更好一些呢？
# 回复: 正则表达式及其他
2004-6-30 10:18 bysumtec
我不知道你绝不觉得，当你学完了高数之后，也许你会把高数给忘得差不多了，但是加减法会不会忘了这个你肯定不会再担心的了。所以，如果你想不要忘记某样知识，那你就深究下去，学到你实在学不懂了，这个时候大概你想记住的东西已经记忆很深刻了。
# 回复: 正则表达式及其他
2004-6-30 10:44 by
好的学习方法，我有时也是这样学习的。
这篇文章使我想起了大学时学习编译原理的情景，回忆ing
# 回复: 正则表达式及其他
2004-6-30 10:49 by重粒子
似乎没有写完啊。继续继续。。。鼓掌
# re: 正则表达式及其他
2004-9-9 23:36 bylaily
good
# re: 正则表达式及其他
2004-11-9 9:44 by
谁有正则表达式相关的资料,能给些吗?
wqb119@126.com
# re: 正则表达式及其他
2005-1-20 13:24 by
I spent a long time on it. but at last,I realized that it was not writen for beginner but for anyone who have know this.
# re: 正则表达式及其他
2005-3-15 20:42 by
我写了个正则表达式、正则文法、有穷自动机的互相转换程序，愿意提交上来，绝对免费，大家互相研究研究，有需要的吗？
# re: 正则表达式及其他
2005-3-15 20:42 by
我写了个正则表达式、正则文法、有穷自动机的互相转换程序，愿意提交上来，绝对免费，大家互相研究研究，有需要的吗？
# re: 正则表达式及其他
2005-5-9 21:15 by
有需要。提交上来大家看看啊。
# re: 正则表达式及其他
2005-5-16 10:14 by
提交上来啊,兄弟!我正需要呢!或者请发到我的email:linuxzhou@sohu.com
# re: 正则表达式及其他
2005-5-16 12:13 by
very good.give me a copy.it is my email: ajian101@163.com
thank you!!
# re: 正则表达式及其他
2005-6-2 14:01 by
我需要啊，能发给我一份吗？谢谢！
pic310@163.com
# re: 正则表达式及其他
2005-6-18 16:45 by
S -> A
A -> aA|B
B -> b
他们能导出的所有字符串似乎是a*b,阁下的a*(a|b).......
# re: 正则表达式及其他
2005-9-16 20:46 by
大虾 能给我一份你的正则表达式、正则文法、有穷自动机的互相转换程序吗 ？
我要远程序 我的邮箱 是 cuiwenhaichao@yahoo.com.cn
# re: 正则表达式及其他
2005-9-27 10:05 by
我正急用，师兄，给一个吧：mazy0925@hotmail.com
先谢了！