簡單的正規表示式原理

奇怪,學正規表示式幹啥要扯到原理?會寫就好了唄!那怎麼行,學東西最重要的就是原理,原理懂了,再怎麼樣都可以隨心所欲的應用它,如果只知道表面而不知道原由,那就像是學數學只知道公式卻不知道公式怎麼來的一樣糟糕,要,就給它透徹的學會,尤其是像正規表示式這種有點難纏的東西。

寫正規表示式的時候,你一定常常會遇到這種狀況,那就是「我的寫法應該沒錯,為什麼它就是比對不出來?」,沒錯,在下我就常常出現這種低能的狀況,害我只能把我原本長長一串的正規表示式拼命化簡妥協,簡單到如果再化簡下去實在比對不出個什麼屁了,才能夠勉強比對出差強人意的結果,為什麼我的正規表示式只要寫得長一點就會出問題咧?

嗯,這個問題我一直很想知道答案。

了解正規表示式的原理當然不能保證你都不再出錯,但是可以讓你在需要寫一大串比對語法時不用老是在那邊猜是不是要多加一個+號或是少掉一個\,再不然就是是拼命抓頭或是拔鬍子,這應該足夠作為你暸解正規表示式運作原理的動機了吧?

基本上,有兩種不同的正規表示式引擎:text-directed engines 和 regex-directed engines, Jeffrey Friedl 稱之為 DFA 和 NFA 引擎,我們文章當中所有的內容大多都是建立在 regex-directed engines 上面,那是因為有很多好用的功能例如 lazy quantifiers 和 backreferences (後面會介紹),就只能應用在 regex-directed engines 上面,也難怪它現在會是最普遍的正規表示式引擎。

不過 text-directed engines 也沒那麼悲慘啦!起碼他也有一些相當值得注意的工具,例如 awk、egrep、 flex、 lex、 MySQL 以及 Procmail ,awk 和 egrep 目前有相當少的版本可以支援 regex-directed engines。

你可以很容易的找到你現在用的到底是哪種正規表示式引擎,只要你發現你可以在其中使用 lazy quantifiers 和 backreferences 的功能,你就可以確定你是在使用 regex-directed engines,怎麼測呢?你可以用”regex|regex not”去比對”regex not”這個字,如果回傳的結果是”regex”,代表你現在用的是regex-directed engines,如果回傳的結果是”regex not”,代表你用的則是text-directed engines,可以現在測測看,你大概會發現PHP、Perl、Python應該都是前者。會出現這樣不同的結果,其實主要的原因是因為 regex-directed engines 本身是個比較熱心的傢伙,到底是怎麼熱心法,下面就會簡單說明。

regex-directed engines 非常重要的一點就是,它會回傳最左邊的結果,即便這個比對字串稍晚還會出現,因為 regex 比對字串的方式,是從左邊算起來第一個字元開始比對,它會一個個去比對所有pattern當中的字元,直到所有的可能性都試過並且找不到為止,它才會繼續比對第二個字元,就這樣一直重複比下去,這也是為什麼regex比對時總是會回傳最左邊的結果。

有點複雜嗎?沒關係,我們來看個例子就明白了。

假設我們今天的pattern是”cat”,而我們要比對的字串是”He captured a catfish for his cat”,regex在比對的時候會先拿出pattern當中的c去跟字串當中左邊數起來第一個字元H比對,嗯…失敗,接著就跟第二個字元去比對,嗯…也失敗,直到比到第三個字元,喔耶~比到了喔!因為比到了,就會拿出pattern當中第二個字元a來跟第四個字元比,喔耶!又比到了~接著又拿出pattern當中第三個字元c來跟第五個字元比,哎呀….槓龜了,糗,不過regex這會子知道不可能再笨到回頭從第四個字元來比,於是它就直接從第五個字元開始從頭比對起。

冗長而且無聊的比對作業繼續下去,一直到第十五個字元,c又跟c對到了,於是regex又燃起了希望,重複先前的動作往下比對,賓果!這下子cat都比到了,好了搞定,收工。

哇咧,後面的東西咧?

不比了,因為regex已經找到了第一個符合的比對結果,熱心的regex可是迫不及待的想要把這個結果回報給在螢幕前面痴痴等待的我們呢!後面還有沒有不重要,重要的是已經找到一個了啊~樂~

這就是regex。

了解比對的原理,就比較能夠了解其中的邏輯,就算日後碰到更加複雜的正規表示式,也可以用這樣的邏輯去判斷是否能夠正確比對出你想要的結果。

One thought on “簡單的正規表示式原理

  1. Pingback: 網站製作學習誌 » [Web] 連結分享

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s