以交互方式生成正則表達(dá)式的算法及演示

林果豐，鄭大鵬

（北京理工大學(xué)珠海學(xué)院計(jì)算機(jī)學(xué)院，珠海519000）

0 引言

正則表達(dá)式，又稱規(guī)則表達(dá)式。它由一些特定字符及這些特定字符的組合，組成一個(gè)“規(guī)則字符串”，這個(gè)“規(guī)則字符串”用來(lái)表達(dá)對(duì)其他字符串的一種過濾邏輯。正則表達(dá)式是對(duì)字符串（包括普通字符例如，a到z之間的字母，以及特殊字符即“元字符”）操作的一種邏輯公式，是一種文本模式，該模式描述在搜索文本時(shí)要匹配的一個(gè)或多個(gè)字符串[1]。正則表達(dá)式通常被用來(lái)檢索、替換那些符合某個(gè)模式（規(guī)則）的文本。

很多專業(yè)領(lǐng)域都能使用正則表達(dá)式，如網(wǎng)絡(luò)犯罪案件取證[1]和頁(yè)面數(shù)據(jù)獲取[2]等。但是在非計(jì)算機(jī)專業(yè)領(lǐng)域卻鮮有運(yùn)用。隨著許多傳統(tǒng)項(xiàng)目開始電子化，如無(wú)紙化考試系統(tǒng)[3]，越來(lái)越多問題開始使用計(jì)算機(jī)處理，正則表達(dá)式將被運(yùn)用到越來(lái)越多的各種不同的系統(tǒng)上，但由于其過于專業(yè)、晦澀難懂，對(duì)于非專業(yè)人士很難使用，甚至不知道正則表達(dá)式的存在。因此，需要有一個(gè)算法，可以在用戶不掌握正則表達(dá)式的情況下引導(dǎo)用戶生成正則表達(dá)式，甚至不需要學(xué)習(xí)正則表達(dá)式。

本文提出的算法可通過引導(dǎo)用戶從而生成正則表達(dá)式，從而使用模式匹配、連字符、元字符、分支條件、重復(fù)匹配這些功能[4]。

1 概述

要引導(dǎo)用戶使用正則表達(dá)式進(jìn)行匹配會(huì)遇到的引導(dǎo)場(chǎng)景有2種情況：用戶要匹配的字符串的個(gè)數(shù)是有限個(gè)的和用戶要匹配的字符串有無(wú)限個(gè)。對(duì)于第一種情況，使用有限項(xiàng)生成算法，即簡(jiǎn)單引導(dǎo)用戶輸入所有待匹配項(xiàng)即可。對(duì)于第二種情況，使用無(wú)限可描述項(xiàng)生成算法，它需要引導(dǎo)用戶輸入字符集范圍和重復(fù)限定的范圍才能生成結(jié)果。所以要生成正則表達(dá)式，需要兩種算法。由于這兩種算法最終都是生成正則表達(dá)式，所以那些無(wú)法用正則表達(dá)式記錄下的匹配要求是無(wú)法通過此算法生成正則表達(dá)式的。這兩種算法都是引導(dǎo)用戶思考正則表達(dá)式要思考的問題，而不用去關(guān)心如何寫出正則表達(dá)式。真正的正則表達(dá)式由算法生成，所以用戶可以在不掌握正則表達(dá)式的情況下，按照構(gòu)造正則表達(dá)式的思路去思考問題即可。算法不僅要關(guān)心正則表達(dá)式生成方面的問題，還要重視對(duì)用戶的引導(dǎo)作用。

2 有限項(xiàng)生成算法

2.1 有限項(xiàng)生成算法流程

對(duì)于待匹配項(xiàng)是有限個(gè)的情況，可以將每個(gè)待匹配項(xiàng)視為一個(gè)子表達(dá)式[4]，引導(dǎo)用戶將所有待匹配項(xiàng)輸入，算法再他們組合在一起，形成正則表達(dá)式分支條件的語(yǔ)法。如圖1所示。

圖1 有限項(xiàng)生成算法流程流程圖

系統(tǒng)首先生成一個(gè)固定的串“^（”，除了第一次不作處理外，每次用戶輸入后，給用戶輸入加上前綴“|”，并將這個(gè)新串其加入到最終的結(jié)果字符串中。當(dāng)用戶結(jié)束，加入后綴“）$”生成最終的字符串。為了提高辨識(shí)力度，首尾固定添加的串中帶有元字符“^”和“$”，從而限制字符串的開頭和結(jié)束，可有效避免未知因素的干擾，當(dāng)然，“^”和“$”不是必須的。如果用戶希望在某個(gè)系統(tǒng)使用生成的正則表達(dá)式時(shí)，匹配過程中可以忽略空白字符、字母大小寫等因素的干擾，可以讓該系統(tǒng)在使用正則表達(dá)式之前過濾或替換掉目標(biāo)字符，讓系統(tǒng)決定，所以算法在生成正則表達(dá)式時(shí)不需要考慮空白字符和大小寫干擾的情況。

2.2 有限項(xiàng)生成算法效果演示

在網(wǎng)絡(luò)教育領(lǐng)域中的無(wú)紙化考試系統(tǒng)中，教師會(huì)設(shè)置填空題。在傳統(tǒng)的填空題設(shè)置、判閱中，都要求教師輸入正確答案，在系統(tǒng)判閱時(shí)，通常采取靜態(tài)字符串比較算法。在這種情況下，可以使用有限項(xiàng)生成算法，在教師輸入答案時(shí)引導(dǎo)生成正則表達(dá)式，在判閱時(shí)使用正則表達(dá)式判題。假設(shè)教師題目為“請(qǐng)輸入一個(gè)數(shù)據(jù)庫(kù)事務(wù)的特性”，教師希望答題者輸入“原子性、一致性、隔離性、持久性”中的一個(gè)才可得分。此時(shí)引導(dǎo)界面見圖2。

圖2 有限項(xiàng)生成算法效果演示過程

用戶輸入完題目后，選擇“設(shè)定答案”，然后將答案一個(gè)一個(gè)輸入。每輸一個(gè)答案，就點(diǎn)擊右邊的“+”號(hào)，最后點(diǎn)擊“確定”按鈕生成預(yù)覽。最終生成的正則表達(dá)式為“（持久性）|（隔離性）|（一致性）|（原子性）”，效果如圖3。

圖3 有限項(xiàng)生成算法效果演示結(jié)果

3 無(wú)限可描述項(xiàng)生成算法

3.1 無(wú)限可描述項(xiàng)生成算法流程

在無(wú)限可描述項(xiàng)生成算法中，創(chuàng)建正則表達(dá)式的過程可以簡(jiǎn)化為構(gòu)造多個(gè)字符重復(fù)集合的過程。所謂字符重復(fù)集合，由一個(gè)字符集合和一個(gè)設(shè)定重復(fù)次數(shù)的語(yǔ)句構(gòu)成。一個(gè)最終要生成的正則表達(dá)式，可以由一個(gè)或多個(gè)字符重復(fù)集合構(gòu)成。所以要生成目標(biāo)串，就要引導(dǎo)用戶輸入字符集合和設(shè)定重復(fù)次數(shù)。

每一個(gè)字符集合都在描述各自對(duì)某一類字符的匹配規(guī)則，如“[0-9]”就是一個(gè)字符集合，它匹配所有阿拉伯?dāng)?shù)字。所以，需要引導(dǎo)用戶考慮他們的匹配規(guī)則，讓用戶輸入類似“[0-9]”這樣的待匹配的字符或者待匹配的字符范圍，在沒有字符集合的概念下創(chuàng)建一個(gè)字符集合。因?yàn)橛脩舨恍枰莆者B字符，所以用戶只需要輸入字符集的左右邊界即可，引導(dǎo)界面如圖4。

圖4 字符集創(chuàng)建算法引導(dǎo)圖

第一行用戶可以輸入要被匹配的特殊符號(hào)，即除了數(shù)字、大小寫字母外的任何字符，包括全半角字符、中文等，如果其中字符如果是“”、“-”或“^”等字符，還要進(jìn)行轉(zhuǎn)義。接下來(lái)3行處理要使用連字符的情況，范圍都是從左邊下拉框的字符到右邊下拉框的字符。若在某行的“是否使用”后打鉤，則會(huì)將該行左邊下拉選擇框和右邊下拉選擇框內(nèi)的兩個(gè)字符用連字符連接起來(lái)，形成“字符-字符”的形式，并加入生成的結(jié)果中。為了生成最終的字符集，需使用上述的有限項(xiàng)生成算法。用戶思考的結(jié)果會(huì)填入這四行的某幾行中，每填入一行，都是一個(gè)有限項(xiàng)生成算法中的“待匹配項(xiàng)”。所以我們可以認(rèn)為這是個(gè)通過有限項(xiàng)生成算法用1到4個(gè)待匹配項(xiàng)生成的一個(gè)字符集合。最終算法使用“[”和“]”包圍它們。該部分實(shí)現(xiàn)函數(shù)GenerateCharacterSet（）的偽代碼如下：

上面的算法中，str長(zhǎng)度至少為5，即使用戶沒有輸入也會(huì)有“^（[]）”，這可以判斷用戶是否有輸入字符集的內(nèi)容。在用戶完成對(duì)字符集的設(shè)定后，再立即引導(dǎo)用戶輸入“重復(fù)匹配”的次數(shù)，設(shè)定次數(shù)的引導(dǎo)界面如圖5。

圖5 重復(fù)匹配次數(shù)算法輸入引導(dǎo)圖

用戶輸入了次數(shù)后，只需要給輸入加上“{”前綴和“}”后綴，然后將結(jié)果放到上一步生成的字符集后，便成功構(gòu)造了一個(gè)字符重復(fù)集合。

這已經(jīng)能正確生成字符重復(fù)集合了，但是這仍不足，我們應(yīng)該要讓多個(gè)字符重復(fù)集合成為一個(gè)子表達(dá)式，從而使用正則表達(dá)式強(qiáng)大的功能。所以還應(yīng)該在生成字符重復(fù)集合的算法上再進(jìn)一步操作，允許更多字符集合進(jìn)入某個(gè)子表達(dá)式中?？梢赃@樣設(shè)定，如果用戶僅僅指定字符集而沒有輸入重復(fù)字?jǐn)?shù)，則不加入重復(fù)次數(shù)，簡(jiǎn)單將字符集生成，下次生成字符集就跟在這個(gè)字符集后面，而不是原本的讓一個(gè)字符集為一個(gè)子表達(dá)式，它們變成同一個(gè)子表達(dá)式。如果用戶在沒有指定字符集時(shí)，僅僅輸入重復(fù)次數(shù)，則將上一個(gè)子表達(dá)式用括號(hào)括起來(lái)，并加上用戶輸入和“{”與“}”，讓上一個(gè)子表達(dá)式重復(fù)匹配指定次數(shù)。這樣就能讓用戶真正使用正則表達(dá)式的功能了。函數(shù)RegGeneration（）便完成了這個(gè)功能，偽代碼如下：

用戶通過該算法引導(dǎo)一次或多次便能得到最終想要的正則表達(dá)式。完整引導(dǎo)界面如圖6。

圖6 無(wú)限可描述項(xiàng)生成算法輸入引導(dǎo)圖

用戶將需求輸入，點(diǎn)擊“+”號(hào)生成一個(gè)字符重復(fù)集合。然后可以再進(jìn)行輸入，再點(diǎn)擊“+”號(hào)。多次點(diǎn)擊“+”號(hào)從而多次調(diào)用無(wú)限可描述項(xiàng)生成算法，直到用戶達(dá)到了需求目標(biāo)。點(diǎn)擊“確定”即可生成最終的正則表達(dá)式。

3.2 無(wú)限可描述項(xiàng)生成算法效果演示

如果用戶希望生成一個(gè)正則表達(dá)式去匹配郵箱，可以使用無(wú)限可描述項(xiàng)生成算法。郵箱有郵箱名稱、“@”和域名這三部分組成，所以，用戶應(yīng)該調(diào)用至少三次無(wú)限可描述項(xiàng)生成算法。郵箱名稱允許出現(xiàn)英文字母、數(shù)字、下劃線、英文句號(hào)，以及中劃線，不以英文句號(hào)開頭，并且至少出現(xiàn)一次，所以生成郵箱名稱部分需要調(diào)用兩次算法。在第一次調(diào)用算法時(shí)，可如圖7填寫。

圖7 無(wú)限可描述項(xiàng)生成算法輸入演示輸入圖

填寫完成后點(diǎn)擊“+”號(hào)，生成的結(jié)果為“[0-9a-zAZ]{1}”，第二次調(diào)用時(shí)同樣勾選三個(gè)選擇框，并在特殊符號(hào)欄加上“._-”且將次數(shù)改為“0,”，便能生成“[._-0-9a-zA-Z]{0,}”?！癅”部分只需要限制“@”字符出現(xiàn)一次即可，所以在特殊符號(hào)欄輸入“@”，不勾選任何“是否使用”框并將次數(shù)設(shè)為“1”，其他都留空便可生成“[@]{1}”。

域名部分可以分為兩部分：它們都由字母、數(shù)字、下劃線和中劃線組成的字符重復(fù)集合，它們都至少出現(xiàn)一次，但是第二個(gè)字符集合額外地以“.”開頭。填寫效果見圖8。

圖8 域名部分字符重復(fù)集合輸入圖

點(diǎn)擊“+”后生成“[/-_0-9a-zA-Z]{1,}”。接著，不設(shè)定出現(xiàn)次數(shù)，僅輸入特殊符號(hào)“.”，生成“[.]”。之后，再重復(fù)上圖所示步驟，再次生成“[/-_0-9a-zA-Z]{1,}”，因?yàn)樯洗紊傻淖址瘺]有重復(fù)匹配次數(shù)，所以本次生成會(huì)拼接上上次生成的結(jié)果，成為一個(gè)新的子表達(dá)式，即變成“[.][/-_0-9a-zA-Z]{1,}”。最后，僅輸入出現(xiàn)次數(shù)為“1，”，便可讓上一個(gè)子表達(dá)式出現(xiàn)至少一次。最終生成的結(jié)果為（[0-9a-zA-Z]{1}）（[._/-0-9a-zA-Z]{0,}）（[@]{1}）（[/-_0-9a-zA-Z]{1,}）（（[.][/-_0-9a-zA-Z]{1,}）{1,}）。

4 結(jié)語(yǔ)

本文給出的算法可以引導(dǎo)用戶將正則表達(dá)式生成出來(lái)，并利用HTML和CSS實(shí)現(xiàn)了引導(dǎo)界面、利用Ja-vaScript編程實(shí)現(xiàn)算法。該算法在越來(lái)越多傳統(tǒng)行業(yè)都向電子化系統(tǒng)靠攏的網(wǎng)絡(luò)背景下，可以被許多領(lǐng)域使用。在教育領(lǐng)域的電子考試系統(tǒng)中，教師出填空題和判題系統(tǒng)自動(dòng)判閱填空題都可以用到正則表達(dá)式，教師可出更多類型的填空題，出題更方便，判題系統(tǒng)正確率高也可以變得更靈活，也沒有傳統(tǒng)的死板。有限項(xiàng)生成算法和無(wú)限可描述項(xiàng)生成算法都可以被使用。即使在計(jì)算機(jī)領(lǐng)域，程序員在遇到需要編寫正則表達(dá)式的情況下也可以使用本系統(tǒng)減少出錯(cuò)概率，大大減少人力成本。該算法可用于任何需要寫出正則表達(dá)式的場(chǎng)景，具有一定的實(shí)際意義。用JavaScript語(yǔ)言實(shí)現(xiàn)的演示程序則有助于讀者更好地理解該算法的基本思想和實(shí)現(xiàn)過程。