Hooopo
- 浏览: 328547 次
- 性别:
- 来自: 北京
-
文章分类
最新评论
1.历史：
引用
正则表达式萌芽于1940年代的神经生理学研究，由著名数学家Stephen Kleene第一个正式描述。具体地说，Kleene归纳了前述的神经生理学研究，在一篇题为《正则集代数》的论文中定义了“正则集”，并在其上定义了一个代数系统，并且引入了一种记号系统来描述正则集，这种记号系统被他称为“正则表达式”。在理论数学的圈子里被研究了几十年之后，1968年，后来发明了UNIX系统的Ken Thompson第一个把正则表达式用于计算机领域，开发了qed和grep两个实用文本处理工具，取得了巨大成功。在此后十几年里，一大批一流计算机科学家和黑客对正则表达式进行了密集的研究和实践。在1980年代早期，UNIX运动的两个中心贝尔实验室和加州大学伯克利分校分别围绕grep工具对正则表达式引擎进行了研究和实现。与之同时，编译器“龙书”的作者Alfred Aho开发了Egrep工具，大大扩展和增强了正则表达式的功能。此后，他又与《C程序设计语言》的作者Brian Kernighan等三人一起发明了流行的awk文本编辑语言。到了1986年，正则表达式迎来了一次飞跃。先是C语言顶级黑客Henry Spencer以源代码形式发布了一个用C语言写成的正则表达式程序库（当时还不叫open source），从而把正则表达式的奥妙带入寻常百姓家，然后是技术怪杰Larry Wall横空出世，发布了Perl语言的第一个版本。自那以后，Perl一直是正则表达式的旗手，可以说，今天正则表达式的标准和地位是由Perl塑造的。Perl 5.x发布以后，正则表达式进入了稳定成熟期，其强大能力已经征服了几乎所有主流语言平台，成为每个专业开发者都必须掌握的基本工具。
2.DFA和NFA
引用
理解DFA和NFA
正则表达式引擎分成两类，一类称为DFA（确定性有穷自动机），另一类称为NFA（非确定性有穷自动机）。两类引擎要顺利工作，都必须有一个正则式和一个文本串，一个捏在手里，一个吃下去。DFA捏着文本串去比较正则式，看到一个子正则式，就把可能的匹配串全标注出来，然后再看正则式的下一个部分，根据新的匹配结果更新标注。而NFA是捏着正则式去比文本，吃掉一个字符，就把它跟正则式比较，匹配就记下来：“某年某月某日在某处匹配上了！”，然后接着往下干。一旦不匹配，就把刚吃的这个字符吐出来，一个个的吐，直到回到上一次匹配的地方。
DFA与NFA机制上的不同带来5个影响：
1. DFA对于文本串里的每一个字符只需扫描一次，比较快，但特性较少；NFA要翻来覆去吃字符、吐字符，速度慢，但是特性丰富，所以反而应用广泛，当今主要的正则表达式引擎，如Perl、Ruby、Python的re模块、Java和.NET的regex库，都是NFA的。
2. 只有NFA才支持lazy和backreference等特性；
3. NFA急于邀功请赏，所以最左子正则式优先匹配成功，因此偶尔会错过最佳匹配结果；DFA则是“最长的左子正则式优先匹配成功”。
4. NFA缺省采用greedy量词（见item 4）；
5. NFA可能会陷入递归调用的陷阱而表现得性能极差。
我这里举一个例子来说明第3个影响。
例如用正则式/perl|perlman/来匹配文本 ‘perlman book’。如果是NFA，则以正则式为导向，手里捏着正则式，眼睛看着文本，一个字符一个字符的吃，吃完 ‘perl’ 以后，跟第一个子正则式/perl/已经匹配上了，于是记录在案，往下再看，吃进一个 ‘m’，这下糟了，跟子式/perl/不匹配了，于是把m吐出来，向上汇报说成功匹配 ‘perl’，不再关心其他，也不尝试后面那个子正则式/perlman/，自然也就看不到那个更好的答案了。
如果是DFA，它是以文本为导向，手里捏着文本，眼睛看着正则式，一口一口的吃。吃到/p/，就在手里的 ‘p’ 上打一个钩，记上一笔，说这个字符已经匹配上了，然后往下吃。当看到 /perl/ 之后，DFA不会停，会尝试再吃一口。这时候，第一个子正则式已经山穷水尽了，没得吃了，于是就甩掉它，去吃第二个子正则式的/m/。这一吃好了，因为又匹配上了，于是接着往下吃。直到把正则式吃完，心满意足往上报告说成功匹配了 ‘perlman’。
由此可知，要让NFA正确工作，应该使用 /perlman|perl/ 模式。
通过以上例子，可以理解为什么NFA是最左子式匹配，而DFA是最长左子式匹配。实际上，如果仔细分析，关于NFA和DFA的不同之处，都可以找出道理。而明白这些道理，对于有效应用正则表达式是非常有意义的。
正则表达式引擎分成两类，一类称为DFA（确定性有穷自动机），另一类称为NFA（非确定性有穷自动机）。两类引擎要顺利工作，都必须有一个正则式和一个文本串，一个捏在手里，一个吃下去。DFA捏着文本串去比较正则式，看到一个子正则式，就把可能的匹配串全标注出来，然后再看正则式的下一个部分，根据新的匹配结果更新标注。而NFA是捏着正则式去比文本，吃掉一个字符，就把它跟正则式比较，匹配就记下来：“某年某月某日在某处匹配上了！”，然后接着往下干。一旦不匹配，就把刚吃的这个字符吐出来，一个个的吐，直到回到上一次匹配的地方。
DFA与NFA机制上的不同带来5个影响：
1. DFA对于文本串里的每一个字符只需扫描一次，比较快，但特性较少；NFA要翻来覆去吃字符、吐字符，速度慢，但是特性丰富，所以反而应用广泛，当今主要的正则表达式引擎，如Perl、Ruby、Python的re模块、Java和.NET的regex库，都是NFA的。
2. 只有NFA才支持lazy和backreference等特性；
3. NFA急于邀功请赏，所以最左子正则式优先匹配成功，因此偶尔会错过最佳匹配结果；DFA则是“最长的左子正则式优先匹配成功”。
4. NFA缺省采用greedy量词（见item 4）；
5. NFA可能会陷入递归调用的陷阱而表现得性能极差。
我这里举一个例子来说明第3个影响。
例如用正则式/perl|perlman/来匹配文本 ‘perlman book’。如果是NFA，则以正则式为导向，手里捏着正则式，眼睛看着文本，一个字符一个字符的吃，吃完 ‘perl’ 以后，跟第一个子正则式/perl/已经匹配上了，于是记录在案，往下再看，吃进一个 ‘m’，这下糟了，跟子式/perl/不匹配了，于是把m吐出来，向上汇报说成功匹配 ‘perl’，不再关心其他，也不尝试后面那个子正则式/perlman/，自然也就看不到那个更好的答案了。
如果是DFA，它是以文本为导向，手里捏着文本，眼睛看着正则式，一口一口的吃。吃到/p/，就在手里的 ‘p’ 上打一个钩，记上一笔，说这个字符已经匹配上了，然后往下吃。当看到 /perl/ 之后，DFA不会停，会尝试再吃一口。这时候，第一个子正则式已经山穷水尽了，没得吃了，于是就甩掉它，去吃第二个子正则式的/m/。这一吃好了，因为又匹配上了，于是接着往下吃。直到把正则式吃完，心满意足往上报告说成功匹配了 ‘perlman’。
由此可知，要让NFA正确工作，应该使用 /perlman|perl/ 模式。
通过以上例子，可以理解为什么NFA是最左子式匹配，而DFA是最长左子式匹配。实际上，如果仔细分析，关于NFA和DFA的不同之处，都可以找出道理。而明白这些道理，对于有效应用正则表达式是非常有意义的。
写道
正则表达式的形式定义故意非常精简，避免定义多余的量词 ? 和 +，它们可以被表达为: a+ = aa* 和 a? = (a|ε)。有时增加补算子 ~ ；~R 指示在 Σ* 上的不在 R 中的所有字符串的集合。补算子是多余的，因为它使用其他算子来表达(尽管计算这种表示的过程是复杂的，而结果可能指数性的增大)。
这种意义上的正则表达式可以表达正则语言，精确的是可被有限状态自动机接受的语言类。但是在简洁性上有重要区别。某类正则语言只能用大小指数增长的自动机来描述，而要求的正则表达式的长度只线性的增长。正则表达式对应于乔姆斯基层级的类型-3文法。在另一方面，在正则表达式和不导致这种大小上的爆炸的非确定有限状态自动机(NFA)之间有简单的映射；为此 NFA 经常被用作正则表达式的替代表示。
我们还要在这种形式化中研究表达力。如下面例子所展示的，不同的正则表达式可以表达同样的语言: 这种形式化中存在着冗余。
有可能对两个给定正则表达式写一个算法来判定它们所描述的语言是否本质上相等，简约每个表达式到极小确定有限自动机，确定它们是否同构（等价）。
这种冗余可以消减到什么程度? 我们可以找到仍有完全表达力的正则表达式的有趣的子集吗? Kleene 星号和并集明显是需要的，但是我们或许可以限制它们的使用。这提出了一个令人惊奇的困难问题。因为正则表达式如此简单，没有办法在语法上把它重写成某种规范形式。过去公理化的缺乏导致了星号高度问题。最近 Dexter Kozen 用克莱尼代数公理化了正则表达式。
很多现实世界的“正则表达式”引擎实现了不能用正则表达式代数表达的特征。
这种意义上的正则表达式可以表达正则语言，精确的是可被有限状态自动机接受的语言类。但是在简洁性上有重要区别。某类正则语言只能用大小指数增长的自动机来描述，而要求的正则表达式的长度只线性的增长。正则表达式对应于乔姆斯基层级的类型-3文法。在另一方面，在正则表达式和不导致这种大小上的爆炸的非确定有限状态自动机(NFA)之间有简单的映射；为此 NFA 经常被用作正则表达式的替代表示。
我们还要在这种形式化中研究表达力。如下面例子所展示的，不同的正则表达式可以表达同样的语言: 这种形式化中存在着冗余。
有可能对两个给定正则表达式写一个算法来判定它们所描述的语言是否本质上相等，简约每个表达式到极小确定有限自动机，确定它们是否同构（等价）。
这种冗余可以消减到什么程度? 我们可以找到仍有完全表达力的正则表达式的有趣的子集吗? Kleene 星号和并集明显是需要的，但是我们或许可以限制它们的使用。这提出了一个令人惊奇的困难问题。因为正则表达式如此简单，没有办法在语法上把它重写成某种规范形式。过去公理化的缺乏导致了星号高度问题。最近 Dexter Kozen 用克莱尼代数公理化了正则表达式。
很多现实世界的“正则表达式”引擎实现了不能用正则表达式代数表达的特征。
目前正则引擎支持的语言种类：
| 引擎类型 | 程序 |
| DFA | awk(大多数版本)、egrep（大多数版本）、flex、lex、MySQL、Procmail |
| 传统型 NFA | GNU Emacs、Java、grep（大多数版本）、less、more、.NET语言、PCRE library、Perl、PHP（所有三套正则库）、Python、Ruby、set（大多数版本）、vi |
| POSIX NFA | mawk、Mortice Lern System's utilities、GUN Emacs（明确指定时使用） |
| DFA/NFA混合 | GNU awk、 GNU grep/egrep、 Tcl |
分享到：
评论
11 楼
check
2009-12-15
Hooopo 写道
night_stalker 写道
我来插楼： 100 行的 ruby DFA
http://www.koders.com/ruby/fid3D6C74C34F619645FAADFC8DCA360240A0652548.aspx
http://www.koders.com/ruby/fid3D6C74C34F619645FAADFC8DCA360240A0652548.aspx
问个问题。。。看了http://www.iteye.com/topic/336577这个帖子，说是用正则搞敏感词过滤是不可行的，原因是现在编程语言的正则都是nfa引擎...
于是偶就想用ruby调用awk egrep这样的dfa引擎的正则可以吗？
ps:由于还不熟悉awk和grep，尚未实践..
这个贴主的基本功还有待加强。首先，DFA可以多项式时间内还原(polynomial time reducible)成NFA。NFA/DFA所能描述的语言称为正则语言(Regular Languages)，正则表达式所能描述的语言等价于NFA/DFA所能描述的语言。如果是多个敏感字，所生成的NFA同样可以用正则来描述，虽然对于人来说可读性会很糟糕。
所以这个帖子的作者完全混淆各种概念。建议你去看KMP algorithm，然后再看aho corasick algorithm。应该就会有比较正确的理解了。
10 楼
Hooopo
2009-12-15
引用
条件操作符
a w k条件操作符
操作符描述操作符描述
< 小于> = 大于等于
< = 小于等于~ 匹配正则表达式
= = 等于!~ 不匹配正则表达式
!= 不等于
1. 匹配
为使一域号匹配正则表达式，使用符号‘～’后紧跟正则表达式，也可以用i f语句。a w k中i f后面的条件用（）括起来。
观察文件g r a d e . t x t，如果只要显示b r o w n腰带级别可知其所在域为f i e l d - 4，这样可以写出表达式{if($4~/brown/) print }意即如果f i e l d - 4包含b r o w n，打印它。如果条件满足，则打印匹配记录行。可以编写下面脚本，因为这是一个动作，必须用花括号{ }括起来。
[root@Linux_chenwy sam]# awk '{if($4~/Brown/) print $0}' grade.txt
J.Troll 07/99 4842 Brown-3 12 26 26
L.Tansl 05/99 4712 Brown-2 12 30 28
匹配记录找到时，如果不特别声明， a w k缺省打印整条记录。使用i f语句开始有点难，但不要着急，因为有许多方法可以跳过它，并仍保持同样结果。下面例子意即如果记录包含模式b r o w n，就打印它：
[root@Linux_chenwy sam]# awk '$0 ~ /Brown/' grade.txt
J.Troll 07/99 4842 Brown-3 12 26 26
L.Tansl 05/99 4712 Brown-2 12 30 28
2. 精确匹配
假定要使字符串精确匹配，比如说查看学生序号4 8，文件中有许多学生序号包含4 8，如果在f i e l d - 3中查询序号4 8，a w k将返回所有序号带4 8的记录：
[root@Linux_chenwy sam]# awk '{if($3~/48/) print$0}' grade.txt
M.Tans 5/99 48311 Green 8 40 44
J.Lulu 06/99 48317 green 9 24 26
P.Bunny 02/99 48 Yellow 12 35 28
J.Troll 07/99 4842 Brown-3 12 26 26
为精确匹配4 8，使用等号= =，并用单引号括起条件。例如$ 3
[root@Linux_chenwy sam]# awk '$3=="48" {print$0}' grade.txt
P.Bunny 02/99 48 Yellow 12 35 28
[root@Linux_chenwy sam]# awk '{if($3=="48") print$0}' grade.txt
P.Bunny 02/99 48 Yellow 12 35 28
3. 不匹配
有时要浏览信息并抽取不匹配操作的记录，与~相反的符号是!~，意即不匹配。像原来使用查询b r o w n腰带级别的匹配操作一样，现在看看不匹配情况。表达式$0 !~/brown/，意即查询不包含模式b r o w n腰带级别的记录并打印它。
注意，缺省情况下， a w k将打印所有匹配记录，因此这里不必加入动作部分。
[root@Linux_chenwy sam]# awk '$0 !~ /Brown/' grade.txt
M.Tans 5/99 48311 Green 8 40 44
J.Lulu 06/99 48317 green 9 24 26
P.Bunny 02/99 48 Yellow 12 35 28
可以只对f i e l d - 4进行不匹配操作，方法如下：
[root@Linux_chenwy sam]# awk '{if($4~/Brown/) print $0}' grade.txt
J.Troll 07/99 4842 Brown-3 12 26 26
L.Tansl 05/99 4712 Brown-2 12 30 28
如果只使用命令awk$4 !="brown"{print $0} grade.txt，将返回错误结果，因为用引号括起了b r o w n，将只匹配‘b r o w n而不匹配b r o w n - 2和b r o w n - 3，当然，如果想要查询非b r o w n - 2的腰带级别，可做如下操作：
[root@Linux_chenwy sam]# awk '$4!="Brown-2" {print $0}' grade.txt
M.Tans 5/99 48311 Green 8 40 44
J.Lulu 06/99 48317 green 9 24 26
P.Bunny 02/99 48 Yellow 12 35 28
4. 小于
看看哪些学生可以获得升段机会。测试这一点即判断目前级别分f i e l d - 6是否小于最高分f i e l d - 7，在输出结果中，加入这一改动很容易。
[root@Linux_chenwy sam]# awk '{if($6 < $7) print $0}' grade.txt
M.Tans 5/99 48311 Green 8 40 44
J.Lulu 06/99 48317 green 9 24 26
5. 小于等于
对比小于，小于等于只在操作符上做些小改动，满足此条件的记录也包括上面例子中的输出情况。
[root@Linux_chenwy sam]# awk '{if($6 <= $7) print $1}' grade.txt
M.Tans
J.Lulu
J.Troll
6. 大于
[root@Linux_chenwy sam]# awk '{if($6 > $7) print $1}' grade.txt
P.Bunny
L.Tansl
7. 设置大小写
为查询大小写信息，可使用[ ]符号。在测试正则表达式时提到可匹配[ ]内任意字符或单词，因此若查询文件中级别为g r e e n的所有记录，不论其大小写，表达式应为‘ / [ G g ] r e e n /’
[root@Linux_chenwy sam]# awk '/[Gg]reen/' grade.txt
M.Tans 5/99 48311 Green 8 40 44
J.Lulu 06/99 48317 green 9 24 26
8. 任意字符
抽取名字，其记录第一域的第四个字符是a，使用句点.。表达式/ ^ . . . a /意为行首前三个字符任意，第四个是a，尖角符号代表行首。
[root@Linux_chenwy sam]# awk '$1 ~ /^...a/' grade.txt
M.Tans 5/99 48311 Green 8 40 44
L.Tansl 05/99 4712 Brown-2 12 30 28
9. 或关系匹配
为抽取级别为y e l l o w或b r o w n的记录，使用竖线符|。意为匹配| 两边模式之一。注意，使用竖线符时，语句必须用圆括号括起来。
[root@Linux_chenwy sam]# awk '$0 ~/(Yellow|Brown)/' grade.txt
P.Bunny 02/99 48 Yellow 12 35 28
J.Troll 07/99 4842 Brown-3 12 26 26
L.Tansl 05/99 4712 Brown-2 12 30 28
上面例子输出所有级别为Ye l l o w或B r o w n的记录。
使用这种方法在查询级别为G r e e n或g r e e n时，可以得到与使用[ ]表达式相同的结果。
[root@Linux_chenwy sam]# awk '/^M/' grade.txt
M.Tans 5/99 48311 Green 8 40 44
10. 行首
不必总是使用域号。如果查询文本文件行首包含M的代码，可简单使用下面^符号：
[root@Linux_chenwy sam]# awk '/^M/' grade.txt
复合表达式即为模式间通过使用下述各表达式互相结合起来的表达式：
引用：&& AND : 语句两边必须同时匹配为真。
|| O R：语句两边同时或其中一边匹配为真。
! 非求逆
11. AND
打印记录，使其名字为‘ P. B u n n y且级别为Ye l l o w，使用表达式( $ 1 = = " P. B u n n y " & &$ 4 = = " Ye l l o w " )，意为& &两边匹配均为真。完整命令如下：
[root@Linux_chenwy sam]# awk '{if ($1=="P.Bunny" && $4=="Yellow") print $0}' grade.txt
P.Bunny 02/99 48 Yellow 12 35 28
12. Or
如果查询级别为Ye l l o w或B r o w n，使用或命令。意为“ | |”符号两边的匹配模式之一或全部为真。
[root@Linux_chenwy sam]# awk '{if ($4=="Yellow" || $4~/Brown/) print $0}' grade.txt
P.Bunny 02/99 48 Yellow 12 35 28
J.Troll 07/99 4842 Brown-3 12 26 26
L.Tansl 05/99 4712 Brown-2 12 30 28
原来不一定得加print,下面我自己对例一二做了一下
1
[root@Linux_chenwy sam]# awk '$4~/Brown/' grade.txt
J.Troll 07/99 4842 Brown-3 12 26 26
L.Tansl 05/99 4712 Brown-2 12 30 28
2
[root@Linux_chenwy sam]# awk '$3=="48"' grade.txt
P.Bunny 02/99 48 Yellow 12 35 28
[root@Linux_chenwy sam]# awk '$3="48"' grade.txt
M.Tans 5/99 48 Green 8 40 44
J.Lulu 06/99 48 green 9 24 26
P.Bunny 02/99 48 Yellow 12 35 28
J.Troll 07/99 48 Brown-3 12 26 26
a w k条件操作符
操作符描述操作符描述
< 小于> = 大于等于
< = 小于等于~ 匹配正则表达式
= = 等于!~ 不匹配正则表达式
!= 不等于
1. 匹配
为使一域号匹配正则表达式，使用符号‘～’后紧跟正则表达式，也可以用i f语句。a w k中i f后面的条件用（）括起来。
观察文件g r a d e . t x t，如果只要显示b r o w n腰带级别可知其所在域为f i e l d - 4，这样可以写出表达式{if($4~/brown/) print }意即如果f i e l d - 4包含b r o w n，打印它。如果条件满足，则打印匹配记录行。可以编写下面脚本，因为这是一个动作，必须用花括号{ }括起来。
[root@Linux_chenwy sam]# awk '{if($4~/Brown/) print $0}' grade.txt
J.Troll 07/99 4842 Brown-3 12 26 26
L.Tansl 05/99 4712 Brown-2 12 30 28
匹配记录找到时，如果不特别声明， a w k缺省打印整条记录。使用i f语句开始有点难，但不要着急，因为有许多方法可以跳过它，并仍保持同样结果。下面例子意即如果记录包含模式b r o w n，就打印它：
[root@Linux_chenwy sam]# awk '$0 ~ /Brown/' grade.txt
J.Troll 07/99 4842 Brown-3 12 26 26
L.Tansl 05/99 4712 Brown-2 12 30 28
2. 精确匹配
假定要使字符串精确匹配，比如说查看学生序号4 8，文件中有许多学生序号包含4 8，如果在f i e l d - 3中查询序号4 8，a w k将返回所有序号带4 8的记录：
[root@Linux_chenwy sam]# awk '{if($3~/48/) print$0}' grade.txt
M.Tans 5/99 48311 Green 8 40 44
J.Lulu 06/99 48317 green 9 24 26
P.Bunny 02/99 48 Yellow 12 35 28
J.Troll 07/99 4842 Brown-3 12 26 26
为精确匹配4 8，使用等号= =，并用单引号括起条件。例如$ 3
[root@Linux_chenwy sam]# awk '$3=="48" {print$0}' grade.txt
P.Bunny 02/99 48 Yellow 12 35 28
[root@Linux_chenwy sam]# awk '{if($3=="48") print$0}' grade.txt
P.Bunny 02/99 48 Yellow 12 35 28
3. 不匹配
有时要浏览信息并抽取不匹配操作的记录，与~相反的符号是!~，意即不匹配。像原来使用查询b r o w n腰带级别的匹配操作一样，现在看看不匹配情况。表达式$0 !~/brown/，意即查询不包含模式b r o w n腰带级别的记录并打印它。
注意，缺省情况下， a w k将打印所有匹配记录，因此这里不必加入动作部分。
[root@Linux_chenwy sam]# awk '$0 !~ /Brown/' grade.txt
M.Tans 5/99 48311 Green 8 40 44
J.Lulu 06/99 48317 green 9 24 26
P.Bunny 02/99 48 Yellow 12 35 28
可以只对f i e l d - 4进行不匹配操作，方法如下：
[root@Linux_chenwy sam]# awk '{if($4~/Brown/) print $0}' grade.txt
J.Troll 07/99 4842 Brown-3 12 26 26
L.Tansl 05/99 4712 Brown-2 12 30 28
如果只使用命令awk$4 !="brown"{print $0} grade.txt，将返回错误结果，因为用引号括起了b r o w n，将只匹配‘b r o w n而不匹配b r o w n - 2和b r o w n - 3，当然，如果想要查询非b r o w n - 2的腰带级别，可做如下操作：
[root@Linux_chenwy sam]# awk '$4!="Brown-2" {print $0}' grade.txt
M.Tans 5/99 48311 Green 8 40 44
J.Lulu 06/99 48317 green 9 24 26
P.Bunny 02/99 48 Yellow 12 35 28
4. 小于
看看哪些学生可以获得升段机会。测试这一点即判断目前级别分f i e l d - 6是否小于最高分f i e l d - 7，在输出结果中，加入这一改动很容易。
[root@Linux_chenwy sam]# awk '{if($6 < $7) print $0}' grade.txt
M.Tans 5/99 48311 Green 8 40 44
J.Lulu 06/99 48317 green 9 24 26
5. 小于等于
对比小于，小于等于只在操作符上做些小改动，满足此条件的记录也包括上面例子中的输出情况。
[root@Linux_chenwy sam]# awk '{if($6 <= $7) print $1}' grade.txt
M.Tans
J.Lulu
J.Troll
6. 大于
[root@Linux_chenwy sam]# awk '{if($6 > $7) print $1}' grade.txt
P.Bunny
L.Tansl
7. 设置大小写
为查询大小写信息，可使用[ ]符号。在测试正则表达式时提到可匹配[ ]内任意字符或单词，因此若查询文件中级别为g r e e n的所有记录，不论其大小写，表达式应为‘ / [ G g ] r e e n /’
[root@Linux_chenwy sam]# awk '/[Gg]reen/' grade.txt
M.Tans 5/99 48311 Green 8 40 44
J.Lulu 06/99 48317 green 9 24 26
8. 任意字符
抽取名字，其记录第一域的第四个字符是a，使用句点.。表达式/ ^ . . . a /意为行首前三个字符任意，第四个是a，尖角符号代表行首。
[root@Linux_chenwy sam]# awk '$1 ~ /^...a/' grade.txt
M.Tans 5/99 48311 Green 8 40 44
L.Tansl 05/99 4712 Brown-2 12 30 28
9. 或关系匹配
为抽取级别为y e l l o w或b r o w n的记录，使用竖线符|。意为匹配| 两边模式之一。注意，使用竖线符时，语句必须用圆括号括起来。
[root@Linux_chenwy sam]# awk '$0 ~/(Yellow|Brown)/' grade.txt
P.Bunny 02/99 48 Yellow 12 35 28
J.Troll 07/99 4842 Brown-3 12 26 26
L.Tansl 05/99 4712 Brown-2 12 30 28
上面例子输出所有级别为Ye l l o w或B r o w n的记录。
使用这种方法在查询级别为G r e e n或g r e e n时，可以得到与使用[ ]表达式相同的结果。
[root@Linux_chenwy sam]# awk '/^M/' grade.txt
M.Tans 5/99 48311 Green 8 40 44
10. 行首
不必总是使用域号。如果查询文本文件行首包含M的代码，可简单使用下面^符号：
[root@Linux_chenwy sam]# awk '/^M/' grade.txt
复合表达式即为模式间通过使用下述各表达式互相结合起来的表达式：
引用：&& AND : 语句两边必须同时匹配为真。
|| O R：语句两边同时或其中一边匹配为真。
! 非求逆
11. AND
打印记录，使其名字为‘ P. B u n n y且级别为Ye l l o w，使用表达式( $ 1 = = " P. B u n n y " & &$ 4 = = " Ye l l o w " )，意为& &两边匹配均为真。完整命令如下：
[root@Linux_chenwy sam]# awk '{if ($1=="P.Bunny" && $4=="Yellow") print $0}' grade.txt
P.Bunny 02/99 48 Yellow 12 35 28
12. Or
如果查询级别为Ye l l o w或B r o w n，使用或命令。意为“ | |”符号两边的匹配模式之一或全部为真。
[root@Linux_chenwy sam]# awk '{if ($4=="Yellow" || $4~/Brown/) print $0}' grade.txt
P.Bunny 02/99 48 Yellow 12 35 28
J.Troll 07/99 4842 Brown-3 12 26 26
L.Tansl 05/99 4712 Brown-2 12 30 28
原来不一定得加print,下面我自己对例一二做了一下
1
[root@Linux_chenwy sam]# awk '$4~/Brown/' grade.txt
J.Troll 07/99 4842 Brown-3 12 26 26
L.Tansl 05/99 4712 Brown-2 12 30 28
2
[root@Linux_chenwy sam]# awk '$3=="48"' grade.txt
P.Bunny 02/99 48 Yellow 12 35 28
[root@Linux_chenwy sam]# awk '$3="48"' grade.txt
M.Tans 5/99 48 Green 8 40 44
J.Lulu 06/99 48 green 9 24 26
P.Bunny 02/99 48 Yellow 12 35 28
J.Troll 07/99 48 Brown-3 12 26 26
9 楼
Hooopo
2009-12-14
night_stalker 写道
我来插楼： 100 行的 ruby DFA
http://www.koders.com/ruby/fid3D6C74C34F619645FAADFC8DCA360240A0652548.aspx
http://www.koders.com/ruby/fid3D6C74C34F619645FAADFC8DCA360240A0652548.aspx
问个问题。。。看了http://www.iteye.com/topic/336577这个帖子，说是用正则搞敏感词过滤是不可行的，原因是现在编程语言的正则都是nfa引擎...
于是偶就想用ruby调用awk egrep这样的dfa引擎的正则可以吗？
ps:由于还不熟悉awk和grep，尚未实践..
8 楼
night_stalker
2009-12-14
我来插楼： 100 行的 ruby DFA
http://www.koders.com/ruby/fid3D6C74C34F619645FAADFC8DCA360240A0652548.aspx
http://www.koders.com/ruby/fid3D6C74C34F619645FAADFC8DCA360240A0652548.aspx
7 楼
Hooopo
2009-12-14
引用
兼具DFA的速度和NFA的功能：正则表达式的终极境界
我已经多次说过，DFA不能支持捕获括号和反向引用。这无疑是对的，但这并不是说，我们不能组合不同的技术，以达到正则表达式的终极境界。180页的补充内容描述了NFA为了追求更强大的功能，如何脱离了纯理论的道路和限制，DFA的情况也是如此。受自身结构的限制，DFA进行这种突破更加困难，但并非不可能。
GNU grep采取了一种简单但有效的策略。它尽可能多地使用DFA，在需要反向引用的时候，才切换到NFA。GNU awk的办法也差不多——在进行“是否匹配”的检查时，它采用GNU grep的DFA引擎，如果需要知道具体的匹配文本的内容，就采用不同的引擎。这里的“不同的引擎”就是NFA，利用自己的gensub函数，GNU awk能够很方便地提供捕获括号。
Tcl的正则引擎由Henry Spencer（你或许记得，这个人在正则表达式的早期发展和流行中扮演了重要的角色）开发，它也是混合型的。Tcl引擎有时候像NFA——它支持环视、捕获括号、反向引用和忽略优先量词。但是，它也确实能提供POSIX的最左最长匹配（177），但没有我们将在第6章看到的NFA的问题。这点确实很棒。
DFA与NFA：实现难度的差异
尽管存在限制，但简单的DFA和NFA引擎都很容易理解和实现。对效率（包括时间和空间效率）和增强性能的追求，令实现越来越复杂。
用代码长度来衡量的话，支持NFA正则表达式的ed Version 7（1979年1月发布）只有不到350行的C代码（所以，整个grep只有区区478行代码）。Henry Spencer1986年免费提供的Version 8正则程序差不多有1 900行C代码，1992年Tom Lord的POSIX NFA package rx（被GNU sed和其他工具采用）长达9 700行。
为了糅合DFA和NFA的优点，GNU egrep Version 2.4.2使用了两个功能完整的引擎（差不多8 900行代码），Tcl的DFA/NFA混合引擎（请看上一页的补充内容）更是长达9 500行。
某些实现很简单，但这并不是说它们支持的功能有限。我曾经想要用Pascal的正则表达式来处理某些文本。从毕业以后我就没用过Pascal了，但是写个简单的NFA引擎并不需要太多工夫。它并不追求花哨，也不追求速度，但是提供了相对全面的功能，非常实用。
我已经多次说过，DFA不能支持捕获括号和反向引用。这无疑是对的，但这并不是说，我们不能组合不同的技术，以达到正则表达式的终极境界。180页的补充内容描述了NFA为了追求更强大的功能，如何脱离了纯理论的道路和限制，DFA的情况也是如此。受自身结构的限制，DFA进行这种突破更加困难，但并非不可能。
GNU grep采取了一种简单但有效的策略。它尽可能多地使用DFA，在需要反向引用的时候，才切换到NFA。GNU awk的办法也差不多——在进行“是否匹配”的检查时，它采用GNU grep的DFA引擎，如果需要知道具体的匹配文本的内容，就采用不同的引擎。这里的“不同的引擎”就是NFA，利用自己的gensub函数，GNU awk能够很方便地提供捕获括号。
Tcl的正则引擎由Henry Spencer（你或许记得，这个人在正则表达式的早期发展和流行中扮演了重要的角色）开发，它也是混合型的。Tcl引擎有时候像NFA——它支持环视、捕获括号、反向引用和忽略优先量词。但是，它也确实能提供POSIX的最左最长匹配（177），但没有我们将在第6章看到的NFA的问题。这点确实很棒。
DFA与NFA：实现难度的差异
尽管存在限制，但简单的DFA和NFA引擎都很容易理解和实现。对效率（包括时间和空间效率）和增强性能的追求，令实现越来越复杂。
用代码长度来衡量的话，支持NFA正则表达式的ed Version 7（1979年1月发布）只有不到350行的C代码（所以，整个grep只有区区478行代码）。Henry Spencer1986年免费提供的Version 8正则程序差不多有1 900行C代码，1992年Tom Lord的POSIX NFA package rx（被GNU sed和其他工具采用）长达9 700行。
为了糅合DFA和NFA的优点，GNU egrep Version 2.4.2使用了两个功能完整的引擎（差不多8 900行代码），Tcl的DFA/NFA混合引擎（请看上一页的补充内容）更是长达9 500行。
某些实现很简单，但这并不是说它们支持的功能有限。我曾经想要用Pascal的正则表达式来处理某些文本。从毕业以后我就没用过Pascal了，但是写个简单的NFA引擎并不需要太多工夫。它并不追求花哨，也不追求速度，但是提供了相对全面的功能，非常实用。
6 楼
Hooopo
2009-12-14
引用
GREP
1. grep简介
grep （global search regular expression(RE) and print out the line,全面搜索正则表达式并把行打印出来）是一种强大的文本搜索工具，它能使用正则表达式搜索文本，并把匹配的行打印出来。Unix的grep家族包括grep、egrep和fgrep。egrep和fgrep的命令只跟grep有很小不同。egrep是grep的扩展，支持更多的re元字符， fgrep就是fixed grep或fast grep，它们把所有的字母都看作单词，也就是说，正则表达式中的元字符表示回其自身的字面意义，不再特殊。linux使用GNU版本的grep。它功能更强，可以通过-G、-E、-F命令行选项来使用egrep和fgrep的功能。
grep的工作方式是这样的，它在一个或多个文件中搜索字符串模板。如果模板包括空格，则必须被引用，模板后的所有字符串被看作文件名。搜索的结果被送到屏幕，不影响原文件内容。
grep可用于shell脚本，因为grep通过返回一个状态值来说明搜索的状态，如果模板搜索成功，则返回0，如果搜索不成功，则返回1，如果搜索的文件不存在，则返回2。我们利用这些返回值就可进行一些自动化的文本处理工作。
2. grep正则表达式元字符集（基本集）
^
锚定行的开始 如：'^grep'匹配所有以grep开头的行。
$
锚定行的结束 如：'grep$'匹配所有以grep结尾的行。
.
匹配一个非换行符的字符 如：'gr.p'匹配gr后接一个任意字符，然后是p。
*
匹配零个或多个先前字符 如：'*grep'匹配所有一个或多个空格后紧跟grep的行。 .*一起用代表任意字符。
[]
匹配一个指定范围内的字符，如'[Gg]rep'匹配Grep和grep。
[^]
匹配一个不在指定范围内的字符，如：'[^A-FH-Z]rep'匹配不包含A-R和T-Z的一个字母开头，紧跟rep的行。
\(..\)
标记匹配字符，如'\(love\)'，love被标记为1。
\<
锚定单词的开始，如:'\<grep'匹配包含以grep开头的单词的行。
\>
锚定单词的结束，如'grep\>'匹配包含以grep结尾的单词的行。
x\{m\}
重复字符x，m次，如：'o\{5\}'匹配包含5个o的行。
x\{m,\}
重复字符x,至少m次，如：'o\{5,\}'匹配至少有5个o的行。
x\{m,n\}
重复字符x，至少m次，不多于n次，如：'o\{5,10\}'匹配5--10个o的行。
\w
匹配文字和数字字符，也就是[A-Za-z0-9]，如：'G\w*p'匹配以G后跟零个或多个文字或数字字符，然后是p。
\W
\w的反置形式，匹配一个或多个非单词字符，如点号句号等。
\b
单词锁定符，如: '\bgrep\b'只匹配grep。
3. 用于egrep和 grep -E的元字符扩展集
+
匹配一个或多个先前的字符。如：'[a-z]+able'，匹配一个或多个小写字母后跟able的串，如loveable,enable,disable等。
?
匹配零个或多个先前的字符。如：'gr?p'匹配gr后跟一个或没有字符，然后是p的行。
a|b|c
匹配a或b或c。如：grep|sed匹配grep或sed
()
分组符号，如：love(able|rs)ov+匹配loveable或lovers，匹配一个或多个ov。
x,x{m,},x{m,n}
作用同x\{m\},x\{m,\},x\{m,n\}
4. POSIX字符类
为了在不同国家的字符编码中保持一至，POSIX(The Portable Operating System Interface)增加了特殊的字符类，如[:alnum:]是A-Za-z0-9的另一个写法。要把它们放到[]号内才能成为正则表达式，如[A- Za-z0-9]或[[:alnum:]]。在linux下的grep除fgrep外，都支持POSIX的字符类。
[:alnum:]
文字数字字符
[:alpha:]
文字字符
[:digit:]
数字字符
[:graph:]
非空字符（非空格、控制字符）
[:lower:]
小写字符
[:cntrl:]
控制字符
[:print:]
非空字符（包括空格）
[:punct:]
标点符号
[:space:]
所有空白字符（新行，空格，制表符）
[:upper:]
大写字符
[:xdigit:]
十六进制数字（0-9，a-f，A-F）
5. Grep命令选项
-?
同时显示匹配行上下的？行，如：grep -2 pattern filename同时显示匹配行的上下2行。
-b，--byte-offset
打印匹配行前面打印该行所在的块号码。
-c,--count
只打印匹配的行数，不显示匹配的内容。
-f File，--file=File
从文件中提取模板。空文件中包含0个模板，所以什么都不匹配。
-h，--no-filename
当搜索多个文件时，不显示匹配文件名前缀。
-i，--ignore-case
忽略大小写差别。
-q，--quiet
取消显示，只返回退出状态。0则表示找到了匹配的行。
-l，--files-with-matches
打印匹配模板的文件清单。
-L，--files-without-match
打印不匹配模板的文件清单。
-n，--line-number
在匹配的行前面打印行号。
-s，--silent
不显示关于不存在或者无法读取文件的错误信息。
-v，--revert-match
反检索，只显示不匹配的行。
-w，--word-regexp
如果被\<和\>引用，就把表达式做为一个单词搜索。
-V，--version
显示软件版本信息。
6. 实例
要用好grep这个工具，其实就是要写好正则表达式，所以这里不对grep的所有功能进行实例讲解，只列几个例子，讲解一个正则表达式的写法。
$ ls -l | grep '^a'
通过管道过滤ls -l输出的内容，只显示以a开头的行。
$ grep 'test' d*
显示所有以d开头的文件中包含test的行。
$ grep 'test' aa bb cc
显示在aa，bb，cc文件中匹配test的行。
$ grep '[a-z]\{5\}' aa
显示所有包含每个字符串至少有5个连续小写字符的字符串的行。
$ grep 'w\(es\)t.*\1' aa
如果west被匹配，则es就被存储到内存中，并标记为1，然后搜索任意个字符（.*），这些字符后面紧跟着另外一个es（\1），找到就显示该行。如果用egrep或grep -E，就不用"\"号进行转义，直接写成'w(es)t.*\1'就可以了。
7.注意
在某些机器上，要使用-E参数才能够进行逻辑匹配(详见下)
grep "a|b" (匹配包含字符样式为"a|b"的行)
grep -E "a|b" (匹配包含字符样式为"a"或"b"的行)
man grep里面关于-E参数的说明是
-E
Treats each pattern specified as an extended regular expression (ERE). A NULL value for the ERE matches every
line.
Note: The grep command with the -E flag is the same as the egrep command, except that error and usage messages
are different and the -s flag functions differently.
1. grep简介
grep （global search regular expression(RE) and print out the line,全面搜索正则表达式并把行打印出来）是一种强大的文本搜索工具，它能使用正则表达式搜索文本，并把匹配的行打印出来。Unix的grep家族包括grep、egrep和fgrep。egrep和fgrep的命令只跟grep有很小不同。egrep是grep的扩展，支持更多的re元字符， fgrep就是fixed grep或fast grep，它们把所有的字母都看作单词，也就是说，正则表达式中的元字符表示回其自身的字面意义，不再特殊。linux使用GNU版本的grep。它功能更强，可以通过-G、-E、-F命令行选项来使用egrep和fgrep的功能。
grep的工作方式是这样的，它在一个或多个文件中搜索字符串模板。如果模板包括空格，则必须被引用，模板后的所有字符串被看作文件名。搜索的结果被送到屏幕，不影响原文件内容。
grep可用于shell脚本，因为grep通过返回一个状态值来说明搜索的状态，如果模板搜索成功，则返回0，如果搜索不成功，则返回1，如果搜索的文件不存在，则返回2。我们利用这些返回值就可进行一些自动化的文本处理工作。
2. grep正则表达式元字符集（基本集）
^
锚定行的开始 如：'^grep'匹配所有以grep开头的行。
$
锚定行的结束 如：'grep$'匹配所有以grep结尾的行。
.
匹配一个非换行符的字符 如：'gr.p'匹配gr后接一个任意字符，然后是p。
*
匹配零个或多个先前字符 如：'*grep'匹配所有一个或多个空格后紧跟grep的行。 .*一起用代表任意字符。
[]
匹配一个指定范围内的字符，如'[Gg]rep'匹配Grep和grep。
[^]
匹配一个不在指定范围内的字符，如：'[^A-FH-Z]rep'匹配不包含A-R和T-Z的一个字母开头，紧跟rep的行。
\(..\)
标记匹配字符，如'\(love\)'，love被标记为1。
\<
锚定单词的开始，如:'\<grep'匹配包含以grep开头的单词的行。
\>
锚定单词的结束，如'grep\>'匹配包含以grep结尾的单词的行。
x\{m\}
重复字符x，m次，如：'o\{5\}'匹配包含5个o的行。
x\{m,\}
重复字符x,至少m次，如：'o\{5,\}'匹配至少有5个o的行。
x\{m,n\}
重复字符x，至少m次，不多于n次，如：'o\{5,10\}'匹配5--10个o的行。
\w
匹配文字和数字字符，也就是[A-Za-z0-9]，如：'G\w*p'匹配以G后跟零个或多个文字或数字字符，然后是p。
\W
\w的反置形式，匹配一个或多个非单词字符，如点号句号等。
\b
单词锁定符，如: '\bgrep\b'只匹配grep。
3. 用于egrep和 grep -E的元字符扩展集
+
匹配一个或多个先前的字符。如：'[a-z]+able'，匹配一个或多个小写字母后跟able的串，如loveable,enable,disable等。
?
匹配零个或多个先前的字符。如：'gr?p'匹配gr后跟一个或没有字符，然后是p的行。
a|b|c
匹配a或b或c。如：grep|sed匹配grep或sed
()
分组符号，如：love(able|rs)ov+匹配loveable或lovers，匹配一个或多个ov。
x,x{m,},x{m,n}
作用同x\{m\},x\{m,\},x\{m,n\}
4. POSIX字符类
为了在不同国家的字符编码中保持一至，POSIX(The Portable Operating System Interface)增加了特殊的字符类，如[:alnum:]是A-Za-z0-9的另一个写法。要把它们放到[]号内才能成为正则表达式，如[A- Za-z0-9]或[[:alnum:]]。在linux下的grep除fgrep外，都支持POSIX的字符类。
[:alnum:]
文字数字字符
[:alpha:]
文字字符
[:digit:]
数字字符
[:graph:]
非空字符（非空格、控制字符）
[:lower:]
小写字符
[:cntrl:]
控制字符
[:print:]
非空字符（包括空格）
[:punct:]
标点符号
[:space:]
所有空白字符（新行，空格，制表符）
[:upper:]
大写字符
[:xdigit:]
十六进制数字（0-9，a-f，A-F）
5. Grep命令选项
-?
同时显示匹配行上下的？行，如：grep -2 pattern filename同时显示匹配行的上下2行。
-b，--byte-offset
打印匹配行前面打印该行所在的块号码。
-c,--count
只打印匹配的行数，不显示匹配的内容。
-f File，--file=File
从文件中提取模板。空文件中包含0个模板，所以什么都不匹配。
-h，--no-filename
当搜索多个文件时，不显示匹配文件名前缀。
-i，--ignore-case
忽略大小写差别。
-q，--quiet
取消显示，只返回退出状态。0则表示找到了匹配的行。
-l，--files-with-matches
打印匹配模板的文件清单。
-L，--files-without-match
打印不匹配模板的文件清单。
-n，--line-number
在匹配的行前面打印行号。
-s，--silent
不显示关于不存在或者无法读取文件的错误信息。
-v，--revert-match
反检索，只显示不匹配的行。
-w，--word-regexp
如果被\<和\>引用，就把表达式做为一个单词搜索。
-V，--version
显示软件版本信息。
6. 实例
要用好grep这个工具，其实就是要写好正则表达式，所以这里不对grep的所有功能进行实例讲解，只列几个例子，讲解一个正则表达式的写法。
$ ls -l | grep '^a'
通过管道过滤ls -l输出的内容，只显示以a开头的行。
$ grep 'test' d*
显示所有以d开头的文件中包含test的行。
$ grep 'test' aa bb cc
显示在aa，bb，cc文件中匹配test的行。
$ grep '[a-z]\{5\}' aa
显示所有包含每个字符串至少有5个连续小写字符的字符串的行。
$ grep 'w\(es\)t.*\1' aa
如果west被匹配，则es就被存储到内存中，并标记为1，然后搜索任意个字符（.*），这些字符后面紧跟着另外一个es（\1），找到就显示该行。如果用egrep或grep -E，就不用"\"号进行转义，直接写成'w(es)t.*\1'就可以了。
7.注意
在某些机器上，要使用-E参数才能够进行逻辑匹配(详见下)
grep "a|b" (匹配包含字符样式为"a|b"的行)
grep -E "a|b" (匹配包含字符样式为"a"或"b"的行)
man grep里面关于-E参数的说明是
-E
Treats each pattern specified as an extended regular expression (ERE). A NULL value for the ERE matches every
line.
Note: The grep command with the -E flag is the same as the egrep command, except that error and usage messages
are different and the -s flag functions differently.
2 楼
Hooopo
2009-12-14
非常好的一个介绍正则的网站：http://iregex.org/
1 楼
Hooopo
2009-12-14
发表评论
相关推荐
自动机DFA与NFA转化和最下化的代码实现软件，相信对大家研究自动机有好处。
正则引擎：DFA和NFA.rar
从NFA的矩阵表示中可以看出，表项通常是一状态的集合，而在DFA的矩阵表示中，表项是一个状态，NFA到相应的DFA的构造的基本思路是：1.DFA的每一个状态对应NFA的一组状态. 2. DFA使用它的状态去记录在NFA读入一个输入...
编译原理实验 NFA转DFA python实现
内容：自动机编程，NFA转换DFA程序，将输入的NFA转换为DFA
its nfa-dfa converter
实现从nfa到dfa的转换，并且输出中间的状态集以及转换表
编译原理NFA到DFA的转换源码
求正规表达式到NFA（不确定的有限自动机），NFA到DFA及DFA（有限自动机）的最小化 有注释。
NFA到DFA的转化程序，Java
欢迎批评指正
这是一个可以实现正规式到NFA的转换，NFA 转换为DFA，DFA的最小化的程序
实现了DFA，NFA算法，DFA最小化，NFA转化为DFA以及正则表达式转化为NFA的算法，是有限状态自动机的初学者很不错的学习资源
nfa转dfa,c++实现，转自lingyu940的csdn微博
（2）输出相应的NFA图（要求用画图方法完成并要求是逐步逐步进行画，好象书本P47例2.12和2.13一样逐步得到结果） （3）NFA转换为DFA（得到的DFA图要求用画图方法完成并要求先产生子集构造表出来再画DFA图） （4...
中大的一个作业，关于编译原理课程的DFA程序和NFA程序的编写
NFA的确定化算法 C++实现注释清楚详细 代码简单
自动机用于建模 DFA 和 NFA 的工具
编译原理课程设计，DFA 及NFA算法实现，java界面化
编译原理设计程序，能够实现DFA_NFA_MFA的转化