IDC资讯中心
java与正则表达式（2年级之1）
在一年级时，我们比较轻松的了解了java & regex （是正则表达式的缩写，与java的包无关）的一些基本用法。一年级的主要任务是：
① 搞了几个可运行的程序。后面要学习的东西，我们可以用相似的程序处理。
② 我们找到了与regex相关的java类——pattern和matcher、string、stringbuffer和stringtokenizer后面我们着重学习它们。
（另外，暂时不想去搞的几个咚咚——patternsyntaxexception、java.util.scanner）。）。
③ 我们了解了regex的大致特点，一种生成字符串的字符串。不管它将会如何复杂，也不过是一个特殊的字符串，而已。
到了二年级，我们准备系统的学习，因而感到凝重起来。yqj2065发现了一个超好的工具——regulator，它是一个高级的、free regex的测试和学习工具，它让你……到这里http://regex.osherove.com/自己看，我去下载了，呵呵。
安装……问题？它需要一个什么.net framework！！！一个小小的工具要那个大大的framework干嘛，偏偏前几天我重装了系统，晕。心中又对m$反感起来。【提供了其c＃源代码。】
我又发现了一个超好的工具——editpad pro，它是一个高级的、free regex的测试和学习工具，它让你……到这里download editpad pro demo for windows 95/98/me/nt4/2000/xp (1.8 mb)自己看，我去下载了，呵呵。
问题是，它的 regex flavor is almost identical to the one used in perl 5。这使我有点不放心，因为java在其pattern文档中比较了与perl 5的异同。
本来想系统学学java& regex，可心中打着小鼓，情不自禁地脸黑黑了。【yqj2065提示：我想学习的与你想学习的可能不同。跳过你不喜欢的部分。】
全部2年级的主题： 正则表达式语法
§1正则表达式：天使 | 魔鬼
通过一年级学习，我发现，两条腿走路很不爽，一下抬起java，一下提起regex，我想一条腿走路。我蹦我蹦我蹦蹦，像三级跳远一样，专注于regex的学习。我们不要jvm，可能轻松了许多。
regular expression翻译成正则表达式，一看就是很有学问的样子。如果我说正则表达式起始于java，没有人相信；如果有人说正则表达式起始于unix系统，我们也不要相信。
1956 年, 数学家stephen kleene在warren mcculloch and walter pitts早期神经系统工作的基础上，搞成了一个数学符号体系——regular sets，规则的集合。这个咚咚很快被计算机科学家用于编译器的扫描或词法分析（ lexical analysis）中。因此，正则表达式起始于自动机理论和形式语言理论（我们会在形式语言与自动机理论课程中接触正则表达式，属于理论计算机科学），我们在编译原理课程中，也可能会接触到正则表达式。【ref：《编译原理及实践》】
正则表达式强大的文本处理能力，很快被kenneth thompson应用到unix的工具软件grep中；此后，正则表达式被广泛应用于unix系操作系统，perl、php，delphi、javascript、c#（.net），java、python、ruby等语言和开发环境，以及很多的应用软件特别是文本编辑器中。值得一提的是，perl regular expressions形成了一种大致的标准，人们常常使用pcre (perl compatible regular expressions)，如同ibm兼容机。【http://en.wikipedia.org/wiki】yqj2065
为什么java直到jdk1.4才提供对regex的支持呢？这让很多人不满。在jdk1.4出现之前，有一些第三方库出现，现在可能不需要它了。例如：
l package com.stevesoft.pat【http://www.javaregex.com/patfull.html】，这里有一些有趣的东西还可以看看。比如regame, the regular expression game。
l 源代码开放的正则表达式库：jakarta-oro正则表达式库，它是最全面的正则表达式api之一，而且它与perl 5正则表达式完全兼容。
直到现在，很多人还在学习和使用stringtokenizer，一方面是教材落后（滞后），一方面是很多人认为正则表达式麻烦，如果我们把它视为洪水猛兽，我们永远搞不懂它。其实，学习正则表达式的唯一困难，仅仅是它不直观。
§2正则表达式是定义语言的语言
自从xml为人们熟悉以来，定义语言的语言就不神秘了。直观地说，regex是生成字符串的字符串。这些由一个regex生成的字符串组成了一种语言。
正则表达式r完全由它所匹配的字符串集合（串集）来定义。这个集合称为由正则表达式生成的语言（language generated by the regular expression），可以写作l（r）——以r为模式的l。此处的语言只表示“串的集合”。如：
l(a)＝{a}
l(a+)={a,aa,aaa,aaaa,……}
该语言首先依赖于适用的字符集，一般是ascii字符的集合或它的某个子集，java则使用unicode字符集，这个字符集是我们在正则表达式中能使用的字母表——∑。
正则表达式r的组成：
l 字母表中的字符。要注意，此时l(a+)中的a不是简单的a，它是一个模式（模板）。
l 有特殊含义的字符——元字符(meta-character)。它们可能也是字母表中正规字符，如* +等等，也可能不是字母表中字符，如\n,\x09等等。这时，我们通过转义字符（escape character）来处理。源代码中，对于前者，加一个\；对于后者，去掉\。
【下面的符号指集合的运算】
最小正则表达式有三种形式：
l l (a) = {a}。单一字符a。此时a可能是任何一个合法的字母表中的字符。如l (x) = {x}。
l l(ε) = {ε}。ε（epsilon）表示空串（empty string）——空串就是不包含任何字符的串。类似string str=””.
l l(ф)= { }.ф表示空集（empty set）,该语言与任何串都不匹配。
注意{ε}和{ }的区别：{ }集不包括任何串，而{ }则包含一个串——没有任何字符的串。
正则表达式的三种基本运算：
l 并集——用元字符|（竖线）表示。
如果r 和s 是正则表达式，那么正则表达式r | s 可匹配被r 或s 匹配的任意串。r | s 语言是r 语言和s 语言的联合（union）。
例如：l (a)＝{a}, l (c)＝{ c }则
l (a|c)= l (a)∪l (c)= {a}∪{ c }={a,c}.
又如：l (a|b|c|d) = { a, b, c, d}。
【并集在java的正则表达式中，书写方式有：a|c、[ac] 、a-z 、等等】
l 连结——不用元字符，顺着写就行了。
正则表达式r 和正则表达式s 的连结可写作rs。
这里说明一下括号()元字符的作用。正则表达式l (a b)＝{a b}，l (c)＝{c},那么正则表达式l((a|b)c)= l (a|b)⊙ l(c)={ac,bc}
【连结书写方式有：a{2,4}等等】
l 重复或“闭包”——用元字符*表示。
r 是一个正则表达式。正则表达式r * 将匹配r串的任意有穷连结。虽然我们说l(a*)＝{ }∪{ a}∪{aa}∪{aaa}∪……＝{ε,a,aa,aaa,aaaa,……}是一个无穷集。
【闭包在java的正则表达式中派生了一些书写方式：
l(a+)＝l(a*)－ε即a+匹配a,aa,aaa,aaaa,……
l(a?) = l (ε|a). 即a? 匹配ε、a。】
运算的优先和括号的使用
三种基本运算的优先级为闭包>连结>并集，除非使用()改变。
l(a|b*)={ a,ε,b, bb, bbb…… }
l((a|b)*) = {ε, a, b, aa, ab, ba, bb, …… }，
定义正则表达式（regular expression）是以下的一种：
1. 基本（b a s i c）正则表达式由一个单字符a（其中a 在正规字符的字母表å中），以及元字符或元字符组成。在第1种情况下，l (a) = {a}；在第2种情况下，l (ε) ={ε}；在第3种情况下，l (ф) = {}。
r和s 均是正则表达式时：
2. r | s 格式的表达式： l (r | s) = l (r) ∪ l (s)。
3. rs 格式的表达式： l (r s) = l (r) l (s)。
4. r* 格式的表达式： l (r*) = l (r) *。
5. (r）格式的表达式： l ( (r)) = l (r)，括号并不改变语言，它们只调整运算的优先权。
【这些东西，都是应该知道的基本知识哦。ref：《编译原理及实践》】
练习
2.1-1 在简单字母表∑ = {a, b, c}上构造一种语言，它是仅包括一个b 的所有串的集合：如aaba、abcca等等。
答案： (a|c)*b(a|c)*
例如：string str＝“abaaabcccbabaaaaabc”，匹配时替换为java。则输出为：javajavajavajavajava。为什么上面的匹配方式不是abaaabcccbabaaaaabc，因为存在所谓的最大匹配——贪婪匹配。
2.1-2 在字母表∑ ={a, b}上构造一种语言，串s的集合是由一个b及在其前后有相同数目的a 组成：s = { b, aba, aabaa, aaabaaa, . . . }
答案：搞不定。正则表达式并不能描述这个集合。重复运算只有闭包运算*一种，但a*ba*能保证b 前后的a 的数量是否相等。它通常表示为“不能计算的正则表达式”——在自动机理论中的数学论证是著名的pumping lemma定理。
（待续……）
这个黑胡子是unix的爸爸，c语言的爷爷。
