为什么大家都不喜欢用正则表达式？ - 知乎1233被浏览153540分享邀请回答(?:(?:^(?:\s+)?)|(?:(?P&quote&["'])[^(?P=quote)]+?(?P=quote)[^`]*?))`(?P&shell&[^`]+)`
看上去就头晕，更没胃口去学了。多正则不光看上去奇怪，而且还分两种正则引擎DFA、NFA，更有很多流派，比如PCRE 、POSIX/GNU
BRE 、POSIX/GNU
ERE，尤其是做运维的同事，发现明明grep下可以正常匹配的正则，在awk下，就无法正常匹配了。DFA引擎的mysql、egrep、flex、awkNFA引擎的perl、java、grep、more、vi、PHP(PHP老版本里，还有三套类库)还有DFA\NFA引擎混合的逆天做法的TCL语言这.....估计很多人都掩面而逃了... 更多的是平时工作用不到，极少用到，故也懒得学。难遇到正则需求了，网上搜一个？能看懂还不行，还得会写。会写还不行，写出的正则还要精确匹配。精确匹配还不行，还得写的高效，CPU不会爆栈。记得几年前看到过淘宝的一个团队BLOG上写的java正则导致CPU100%的问题，也是正则写不到引起的(原BLOG地址可能关了，找了个复制版)。尤其是NFA回溯特性，一旦写不好，随着字符串的长度增加，回溯点将是几何级增长，CPU都累死了。其实，也还好，运维朋友，在做nginx、apache规则时，会经常接触NFA 正则写法，应该稍微熟悉点。还有就是做各种日志分析的运维，正则基础会好点。还有就是做语法扫描，做各种语言语法分析的大神，比如对mysql 的sql语句分析，对php、python、go这种语言的源码语法分析的大神，对正则更是熟悉。 比如
轮子哥对于更对向我这种脚本级屌丝程序员(我是PHP程序员，别打我。)，接触更多的是对IP、日期、邮箱等简单的字符串匹配，往往都在网上随便找找就用了，其实还是建议大家认真学学，挺有用的，也很有意思。引用一段话。发明BSD、TCP/IP、csh、vi和NFS的SUN首席科学家Bill Joy说过，在计算机体系结构领域里，缓存是唯一称得上伟大的思想的。其他的一切发明和技术不过是在不同场景下应用这一思想而已。在计算机软件领域里，情形也大体相似。如果罗列这个领域的伟大发明，绝对不超过二十项。这些包括分组交换网络、WEB、lisp、哈希算法、UNIX、编译技术、关系模型、面向对象、XML这些大名鼎鼎的家伙，而正则表达式绝对不应该被漏掉。正则这种神器，你们可以花时间吗，花点儿，哪怕瞟呢，花不了多少时间！12214 条评论分享收藏感谢收起25649 条评论分享收藏感谢收起更多7 个回答被折叠（）后使用快捷导航没有帐号？
只需一步，快速开始
查看: 23789|回复: 2
正则匹配空格的问题
UID252327在线时间 小时积分2223帖子离线17374 天注册时间
银牌会员, 积分 2223, 距离下一级还需 777 积分
现在有一个问题：
蓝 色&&理& &想
复制代码
之间的空格不固定，比如有一个空格的也有2个空格还有3个空格的，
我如何用正则把他弄成都是一个空格的，结果如：
蓝 色 理 想
复制代码
UID299514在线时间 小时积分258帖子离线17374 天注册时间
中级会员, 积分 258, 距离下一级还需 242 积分
var text1=&蓝
var text2=text1.replace(/\s+/g,& &)
document.write(text2)
&提示：您可以先修改部分代码再运行
UID252327在线时间 小时积分2223帖子离线17374 天注册时间
银牌会员, 积分 2223, 距离下一级还需 777 积分
谢谢楼上，我自己尝试写了个：
&!DOCTYPE html PUBLIC &-//W3C//DTD XHTML 1.0 Transitional//EN& &http://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd&&
&html xmlns=&http://www.w3.org/1999/xhtml&&
&meta http-equiv=&Content-Type& content=&text/ charset=gb2312& /&
&title&无标题文档&/title&
&script language=&javascript& type=&text/javascript&&
var str = &搜 索
var reg = /\s{2,}/g;
var arr = str.replace(reg,& &);
alert(arr);
&提示：您可以先修改部分代码再运行
Powered by温馨提示！由于新浪微博认证机制调整，您的新浪微博帐号绑定已过期，请重新绑定！&&|&&
LOFTER精选
网易考拉推荐
用微信&&“扫一扫”
将文章分享到朋友圈。
用易信&&“扫一扫”
将文章分享到朋友圈。
Author:Russ Cox
Email:rsc January 2007[说明：本文由phylips@bmy翻译自英文文章Regular Expression Matching Can Be Simple And Fast&(but is slow in Java, Perl, PHP, Python, Ruby, ...)，原文地址：导引这篇文章介绍了正则表达式匹配的两种方法。一种被广泛应用在很多语言的标准解释器里，比如perl。另一个仅仅在一些地方使用，主要是大部分的awk和grep实现里使用。这两个方法在性能上具有很大的区别。我们使用上标来代表字符重复，比如 a?^3a^3 代表 a?a?a?aaa。上面两个图是使用上面两种方法来匹配模式串a?^na^n 和字符串a^n。可以注意到perl需要超过60秒时间来匹配一个29字符的字符串。另一种方法，标注了Thompson NFA的那个，只需要20 ms就可以完成匹配。这个不是一个打印错误，事实就是如此。perl的图时间是以秒为单位，而Thompson NFA的则是以ms为单位：可以看出Thompson NFA实现的速度是perl实现的成百上千倍。图的发展趋势可以看出：Thompson NFA 处理一个100个字符的字符串200ms内就可以完成，但是perl则需要1o^15年。(perl仅仅是使用这种算法的一个最流行的一个语言；上面的图也可能是python,php,ruby或者其他语言。文章后面还会有更细节化的图提供了其他实现的相关数据)很难相信上面的图形，或许你使用过perl，但是可能从没有碰到正则表达式匹配会匹配的如此之慢。实际上大多数时间，perl的正则表达式匹配是足够快速的。正如图形所展示的，尽管很可能写出上面那样的病态正则表达式会让perl的匹配非常慢。与此不同的是，对于Thompson NFA实现来说，并不存在这样的病态正则表达式。这就引出了另外一个问题，"为什么perl不使用Thompson NFA方法呢"，它可以，它也应该，这也是我们这篇文章剩余内容要说明的。从历史上来看，正则表达式是计算机科学领域里关于理论如何帮助产生好程序的一个出色的例子。最初它们只是被看做一种简单的计算模型进行理论性的研究，但是Ken Thompson通过他实现的文本编辑器QED把它们介绍给程序员。 Dennis Ritchie 后来又将它移植到GE-TSS系统上的QED。Thompson and Ritchie创建了UNIX，他们又把正则表达式引入了UNIX。直到1970s，正则表达式逐步成为unix领域的关键特点，广泛应用在各种工具里，比如ed,sed,grep,egrep,awk和lex中。今天，正则表达式已经成为忽略好的理论将导致坏程序的一个良好例证。今天的那些流行工具所使用的正则表达式实现很明显速度低于30年前的那些Unix工具使用的正则表达式匹配引擎。这篇文章将会回顾那些好的理论：正则表达式，自动机，由Ken Thompson在19世纪60年代中期发明的正则表达式搜索算法。还会将这些理论实现出来，描述了Thompson的一个简单实现。该实现，少于400行c代码，上面图中我们与perl对比的那个程序就是使用的这个实现。它要比perl,python,pcre这些软件使用的实现性能表现得要好。这篇文章主要讨论在现实实现中，理论是如何转化为实际应用的。正则表达式正则表达式是一种描述字符串集合的记法。如果一个字符串属于正则表达式描述的集合，那么我们就说正则表达式与这个字符串匹配。最简单的正则表达式是一个单字符。除了特殊的元字符*+?|,字符都是与它们本身匹配的。为了匹配一个元字符，需要增加一个转义字符"\",比如\+匹配一个"+"。两个正则表达式可以通过选择，连接形成一个新的正则表达式。如果e1匹配s，e2匹配t，那么e1|e2就匹配s或者t，e1e2就陪陪st。元字符*+和?是重复操作符，e1*匹配0个或者更多个字符串e1；e1+匹配一个或者多个；e1?匹配0个或者1个。操作符优先级，从最弱到最强的绑定顺序，第一个是选择，然后是连接，最后是重复。显式的括号可以被用来改变优先级，就像算术表达式那样。ab|cd等价于(ab)|(cd);ab*等价于a(b*)。直到目前为止，前面描述的符号只是传统unix正则表达式符号集的一个子集。这个子集足够描述所有的正则语言。 loosely speaking, a regular language is a set of strings that can be matched in a&single pass through the text using only a fixed amount of memory.新的正则表达式语言(尤其是perl和那些使用perl的)已经添加了很多新的操作符和转义序列。这些新添加的特点，使得正则表达式语言更加准确，虽然显得更复杂，但并没有显得更强大：这些新的正则表达式通常都可以在旧的那里找到更长的等价表示方法。有一个通用的正则表达式扩展增加了正则表达式的能力，叫做前向引用。一个前向引用比如\1 \2匹配前一个括号里的表达式匹配的字符串。再比如(cat|dog)\1 匹配catcat,dogdog但是并不与catdog,dogcat匹配。实际上含有前向引用的正则表达式已经超出了通常的正则表达式的概念范畴。增加的前向引用这个功能也带来了很大的花费：最坏情况下，现有已知的最好实现也需要指数级搜索算法，就像perl使用的那个。Perl现在并没有去掉反向引用支持，当然如果正则表达式中不包含前向引用它们实际也可以使用更快的算法，比如上面提到的那个。本文就是介绍这些更快的算法的。有限自动机另一种描述字符集的方式是使用有限自动机。有限自动机也被称为状态机，“automaton” 和 “machine”这两个单词意思一致，通常可以相互替换。作为一个简单的例子，下面这个状态机就可以识别正则表达式a(bb)+a所代表的字符串集合。有限自动机，通常用一个环代表一个状态(环里的标号是为了让讨论起来更方便，它们并不是自动机操作的一部分)。当读取字符串的同时，它读一个字符就从一个状态转换到另一个状态。状态机里有两个特殊状态：开始状态s0和匹配状态s4。开始状态有一个"&"指向它们，匹配状态用一个双环表示。状态机一次从输入字符串里读取一个字符，沿着指向状态图中的指针从一个状态转换到另一个状态。比较假设输入字符串是abbbba。当状态机读取第一个字符a的时候，它处在开始状态s0.然后它沿着指针到达状态s1。之后接着不断读入b到达s2,读入b到达s3，读入b到达s3，最后到达s4。状态机结束在s4，匹配状态，所以它可以匹配这个字符串。如果状态机结束在一个非匹配状态，那说明它与字符串不匹配。如果在状态机执行过程中的任何一点，针对当前输入字符，没有任何指针了，那麽状态机的执行就可以提前结束了。现在为止我们看到的都叫做确定性有限自动机(DFA)，因为在任何状态，每个可能的输入字符最多转向一个新状态。我们也可以创建具有多个可能的下一个状态的状态机。比如，下面这个状态机等价于前面那个，但是不是确定性的：状态机不是确定性的，因为如果在状态s2读入一个字符b，下一个状态就有多种选择。它可以去状态s1，也可以到达状态s3。因为状态机不能提前看到字符串的剩余部分，也就无法判断哪一个状态是正确决定。在这个情况下，如果能让状态机总是猜的正确的也是很有挑战的。这样的状态机称为非确定性有限自动机(NFAs或者NDFAs)。如果输入字符串能够通过NFA中的某条路径到达最终的匹配状态，那么就说明字符串与该NFA匹配。有时如果让NFA包含没有相应输入字符的指针，会很方便，我们称这些指针是未标记的。一个NFA，在任意时刻，不用读入任何输入就可以选择一个未标记的指针到达下一个状态。下面这个NFA等价于前面两个，但是未标记指针使得图形与a(bb)+a的对应关系更明显了：将正则表达式转换为NFAs正则表达式与NFAs可以相互进行等价变换：每一个正则表达式都有一个等价的NFA(它们匹配相同的字符集)(现已证明DFAs与NFAs在表达能力上也是等价的，后面我们也可以看到这点)。有多种方法将正则表达式转换成NFAs。这里描述的方法最初由Thompson在1968年发表在CACM上的。一个正则表达式的NFAs是逐步由一个子表达式对应的那些NFAs分块构建起来的，不同的操作符具有不同的构建方式。这种NFAs分块没有匹配状态:但是它们倒有一个或者多个悬空指针(未指向任何状态)。整个构建过程将以将这些指针指向一个匹配状态结束。NFAs对于一个单字符的匹配如下；对于链接e1e2,需要将e1的终结指针指向e2的状态机的开始状态；对于选择e1|e2,需要增加一个新的开始状态，这个状态有两个指针指向e1和e2；对于e?，修改e状态增加一个新状态，并添加一条空指针；对于e*，使用类似e?相同的改变，但是还要将e的结束指针回指到这个新状态；对于e+，因为要至少通过e一次，所以做一些改变。如下所示：数一下上面图中的新状态，可以看到通过这种技术，正则表达式中的每个元字符刚好对应NFA的一个状态(除了括号)。因此最终的NFAs里的状态数目最多等于原始正则表达式串的长度。观察上面的图示，我们还可以发现一个特点：每个子片段实际上对外只有开始状态和输出指针是可见的，而上面这些运算，所需要的操作不外乎要么增加一个新的开始状态，将新片段的输出指针指向另一个片段的开始状态，要么修改原来的输出指针，总之只涉及到输出指针和开始状态的操作。正如先前描述的NFA例子，很容易消除掉未标记的指针，也很容易一开始就生成不包含未标记指针的NFA。但是引用如果加上这个未标记指针，会让我们的NFA更容易理解和阅读，也能让c代码更简单，所以我们将保留它。正则表达式搜索算法现在我们有了一种方法来判断一个正则表达式与一个字符串是否匹配：将正则表达式转换为NFA然后通过字符串输入运行NFA。为了让普通的计算机运行NFA，我们必须找到一种模拟NFA运行的方式。一种模拟这种完美猜测的方式是首先猜一个选择，如果它不成功则尝试另一个。比如考虑abab|abbb对应的NFA，如果输入abbb,则整个过程如下:在step0，NFA首先做一个选择：尝试匹配abab还是abbb?在图中，NFA尝试abab，但是在第3步就失败了。然后NFA尝试另一个选择，到达step4然后匹配成功。这种回溯策略有一个简单的递归实现但是在成功之前可能会多次读入输入字符串。如果字符串不匹配，在放弃之前状态机就会尝试所有可能的执行路径。在这个例子里，NFA只尝试了两个路径，但最坏情况下，所有可能的执行路径将会是指数级的，这样会导致极低的运行时间。一个更有效但是更复杂的方式是通过并行猜测所有的选择来模拟这个猜测的过程。在这种策略里，这个模拟过程允许这个状态机一次处于多个状态。为了处理每个字符，它让所有的状态沿着这个字符对应的指针前进。如下：状态机从开始状态以及那些所有从开始状态通过未标注指针可以到达的状态开始。在step1和2，NFA并行地处在两个状态。仅仅在step3减少到一个状态。多状态策略由于在同一时刻尝试两条可能路径，所有只需要读取输入一次。最坏情况下，NFA每一步可能处在所有的状态，但是这个结果最坏情况下也是与字符串长度常数级系数关系，所以即使很大的输入字符串也可以在线性时间内处理。与需要回溯的指数级复杂度相比，这已经是一个很大的进步了。这个效率来自于追踪所有的可达状态集，但是并不是那些可能的路径数目。在一个n节点的NFA里，每一步可能有n个可达状态，但是NFA里可能存在2^n个路径。所谓的并行执行，不过是一个在NFA状态图中的开始状态开始不断进行广度优先搜索的过程，我们每次记录当前的所有可达状态集合，然后根据下一个输入得到下一个可达状态集合，这样可达状态集合就更新为新计算的这个集合，然后继续进行上面的迭代过程。
阅读(5839)|
用微信&&“扫一扫”
将文章分享到朋友圈。
用易信&&“扫一扫”
将文章分享到朋友圈。
历史上的今天
在LOFTER的更多文章
loftPermalink:'',
id:'fks_080068',
blogTitle:'正则表达式匹配也可以简单快速(上：原理部分)',
blogAbstract:'--------------------------虽然在java perl php python ruby里它很慢Author:Russ Cox
Email:rsc January 2007[说明：本文由phylips@bmy翻译自英文文章Regular Expression Matching Can Be Simple And Fast&(but is slow in Java, Perl, PHP, Python, Ruby, ...)，原文地址：'
{list a as x}
{if x.moveFrom=='wap'}
{elseif x.moveFrom=='iphone'}
{elseif x.moveFrom=='android'}
{elseif x.moveFrom=='mobile'}
${a.selfIntro|escape}{if great260}${suplement}{/if}
{list a as x}
推荐过这篇日志的人：
{list a as x}
{if !!b&&b.length>0}
他们还推荐了：
{list b as y}
转载记录：
{list d as x}
{list a as x}
{list a as x}
{list a as x}
{list a as x}
{if x_index>4}{break}{/if}
${fn2(x.publishTime,'yyyy-MM-dd HH:mm:ss')}
{list a as x}
{if !!(blogDetail.preBlogPermalink)}
{if !!(blogDetail.nextBlogPermalink)}
{list a as x}
{if defined('newslist')&&newslist.length>0}
{list newslist as x}
{if x_index>7}{break}{/if}
{list a as x}
{var first_option =}
{list x.voteDetailList as voteToOption}
{if voteToOption==1}
{if first_option==false},{/if}&&“${b[voteToOption_index]}”&&
{if (x.role!="-1") },“我是${c[x.role]}”&&{/if}
&&&&&&&&${fn1(x.voteTime)}
{if x.userName==''}{/if}
网易公司版权所有&&
{list x.l as y}
{if defined('wl')}
{list wl as x}{/list}到底什么是正则表达式？在编写处理字符串的程序或网页时，经常有查找符合某些复杂规则的字符串的需要。正则表达式就是用于描述这些规则的工具。换句话说，正则表达式就是记录文本规则的代码。常用元字符代码说明.匹配除换行符以外的任意字符\w匹配字母或数字或下划线\s匹配任意的空白符\d匹配数字\b匹配单词的开始或结束^匹配字符串的开始$匹配字符串的结束常用限定符代码/语法说明*重复零次或更多次+重复一次或更多次?重复零次或一次{n}重复n次{n,}重复n次或更多次{n,m}重复n到m次常用反义词代码/语法说明\W匹配任意不是字母，数字，下划线，汉字的字符\S匹配任意不是空白符的字符\D匹配任意非数字的字符\B匹配不是单词开头或结束的位置[^x]匹配除了x以外的任意字符[^aeiou]匹配除了aeiou这几个字母以外的任意字符
配色/在线汉字}