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

林果豐，鄭大鵬

（北京理工大學珠海學院計算機學院，珠海519000）

0 引言

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

很多專業領域都能使用正則表達式，如網絡犯罪案件取證[1]和頁面數據獲取[2]等。但是在非計算機專業領域卻鮮有運用。隨著許多傳統項目開始電子化，如無紙化考試系統[3]，越來越多問題開始使用計算機處理，正則表達式將被運用到越來越多的各種不同的系統上，但由于其過于專業、晦澀難懂，對于非專業人士很難使用，甚至不知道正則表達式的存在。因此，需要有一個算法，可以在用戶不掌握正則表達式的情況下引導用戶生成正則表達式，甚至不需要學習正則表達式。

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

1 概述

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

2 有限項生成算法

2.1 有限項生成算法流程

對于待匹配項是有限個的情況，可以將每個待匹配項視為一個子表達式[4]，引導用戶將所有待匹配項輸入，算法再他們組合在一起，形成正則表達式分支條件的語法。如圖1所示。

圖1 有限項生成算法流程流程圖

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

2.2 有限項生成算法效果演示

在網絡教育領域中的無紙化考試系統中，教師會設置填空題。在傳統的填空題設置、判閱中，都要求教師輸入正確答案，在系統判閱時，通常采取靜態字符串比較算法。在這種情況下，可以使用有限項生成算法，在教師輸入答案時引導生成正則表達式，在判閱時使用正則表達式判題。假設教師題目為“請輸入一個數據庫事務的特性”，教師希望答題者輸入“原子性、一致性、隔離性、持久性”中的一個才可得分。此時引導界面見圖2。

圖2 有限項生成算法效果演示過程

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

圖3 有限項生成算法效果演示結果

3 無限可描述項生成算法

3.1 無限可描述項生成算法流程

在無限可描述項生成算法中，創建正則表達式的過程可以簡化為構造多個字符重復集合的過程。所謂字符重復集合，由一個字符集合和一個設定重復次數的語句構成。一個最終要生成的正則表達式，可以由一個或多個字符重復集合構成。所以要生成目標串，就要引導用戶輸入字符集合和設定重復次數。

每一個字符集合都在描述各自對某一類字符的匹配規則，如“[0-9]”就是一個字符集合，它匹配所有阿拉伯數字。所以，需要引導用戶考慮他們的匹配規則，讓用戶輸入類似“[0-9]”這樣的待匹配的字符或者待匹配的字符范圍，在沒有字符集合的概念下創建一個字符集合。因為用戶不需要掌握連字符，所以用戶只需要輸入字符集的左右邊界即可，引導界面如圖4。

圖4 字符集創建算法引導圖

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

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

圖5 重復匹配次數算法輸入引導圖

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

這已經能正確生成字符重復集合了，但是這仍不足，我們應該要讓多個字符重復集合成為一個子表達式，從而使用正則表達式強大的功能。所以還應該在生成字符重復集合的算法上再進一步操作，允許更多字符集合進入某個子表達式中。可以這樣設定，如果用戶僅僅指定字符集而沒有輸入重復字數，則不加入重復次數，簡單將字符集生成，下次生成字符集就跟在這個字符集后面，而不是原本的讓一個字符集為一個子表達式，它們變成同一個子表達式。如果用戶在沒有指定字符集時，僅僅輸入重復次數，則將上一個子表達式用括號括起來，并加上用戶輸入和“{”與“}”，讓上一個子表達式重復匹配指定次數。這樣就能讓用戶真正使用正則表達式的功能了。函數RegGeneration（）便完成了這個功能，偽代碼如下：

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

圖6 無限可描述項生成算法輸入引導圖

用戶將需求輸入，點擊“+”號生成一個字符重復集合。然后可以再進行輸入，再點擊“+”號。多次點擊“+”號從而多次調用無限可描述項生成算法，直到用戶達到了需求目標。點擊“確定”即可生成最終的正則表達式。

3.2 無限可描述項生成算法效果演示

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

圖7 無限可描述項生成算法輸入演示輸入圖

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

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

圖8 域名部分字符重復集合輸入圖

點擊“+”后生成“[/-_0-9a-zA-Z]{1,}”。接著，不設定出現次數，僅輸入特殊符號“.”，生成“[.]”。之后，再重復上圖所示步驟，再次生成“[/-_0-9a-zA-Z]{1,}”，因為上次生成的字符集沒有重復匹配次數，所以本次生成會拼接上上次生成的結果，成為一個新的子表達式，即變成“[.][/-_0-9a-zA-Z]{1,}”。最后，僅輸入出現次數為“1，”，便可讓上一個子表達式出現至少一次。最終生成的結果為（[0-9a-zA-Z]{1}）（[._/-0-9a-zA-Z]{0,}）（[@]{1}）（[/-_0-9a-zA-Z]{1,}）（（[.][/-_0-9a-zA-Z]{1,}）{1,}）。

4 結語

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