[發明專利]正則表達式NFA的構造方法及裝置

在審

• 申請號: 201911415195.5
• 申請日: 2019-12-31
• 公開（公告）號: CN111159496A
• 公開（公告）日: 2020-05-15
• 發明（設計）人: 王彬;覃永靖;程詩堯;馬江波
• 申請（專利權）人: 奇安信科技集團股份有限公司;網神信息技術（北京）股份有限公司
• 主分類號: G06F16/903
• 分類號: G06F16/903;G06F16/9032
• 代理公司: 北京路浩知識產權代理有限公司 11002
• 代理人: 苗曉靜

1.一種正則表達式NFA的構造方法，其特征在于，包括：

對正則表達式進行格式化處理；

對格式化處理后的正則表達式進行遍歷處理，根據每個字符所屬的字符類型同步構造非確定有窮自動機NFA。

2.根據權利要求1所述的正則表達式NFA的構造方法，其特征在于，所述對正則表達式進行格式化處理，具體包括：

對正則表達式進行頭部預處理；以及，對正則表達式進行大小寫適配。

3.根據權利要求2所述的正則表達式NFA的構造方法，其特征在于，所述對正則表達式進行頭部預處理，具體包括：

若正則匹配為搜索模式且正則表達式第一個字符不是^，則為所述正則表達式增加前綴.*。

4.根據權利要求2所述的正則表達式NFA的構造方法，其特征在于，所述對正則表達式進行大小寫適配，具體包括：

若正則匹配忽略大小寫，則將正則表達式和待匹配字符串都轉換為小寫；若正則匹配不能忽略大小寫，則將正則表達式保持不變。

5.根據權利要求1所述的正則表達式NFA的構造方法，其特征在于，所述對格式化處理后的正則表達式進行遍歷處理，根據每個字符所屬的字符類型同步構造非確定有窮自動機NFA，具體包括：

創建當前自動機，對格式化處理后的正則表達式進行遍歷處理，若當前字符所屬的字符類型為字符轉換，則執行與字符轉換對應的第一NFA構造操作；若當前字符所屬的字符類型為量詞，則執行與量詞對應的第二NFA構造操作；若當前字符所屬的字符類型為或，則執行與或對應的第三NFA構造操作；若當前字符所屬的字符類型為小括號，則執行與小括號對應的第四NFA構造操作。

6.根據權利要求5所述的正則表達式NFA的構造方法，其特征在于，所述若當前字符所屬的字符類型為字符轉換，則執行與字符轉換對應的第一NFA構造操作，具體包括：

若當前字符為轉義字符，則解析轉義字符、16進制、8進制得到結果字符集；

若當前字符為非元字符，則解析為只包含非元字符的結果字符集；

若當前字符為任意字符.，則解析為包含所有字符的結果字符集；

若當前字符為區間值[]，則解析為包含所有區間值的結果字符集；

若當前字符為默認情況，則解析為只包含單個字符的結果字符集；

若下一個字符為量詞，則將當前結果轉化為下一個自動機；否則，為當前自動機根據結果字符集添加跳轉操作。

7.根據權利要求5所述的正則表達式NFA的構造方法，其特征在于，所述若當前字符所屬的字符類型為量詞，則執行與量詞對應的第二NFA構造操作，具體包括：

若當前字符為*，則解析值為{0，+∞}的量詞區間；

若當前字符為？，則解析值為{0，1}的量詞區間；

若當前字符為+，則解析值為{1，+∞}的量詞區間；

若當前字符為{，則解析值為{m，n}的量詞區間；

針對下一個自動機執行量詞操作repeat，并針對當前自動機和下一個自動機執行連接操作。

8.根據權利要求5所述的正則表達式NFA的構造方法，其特征在于，所述若當前字符所屬的字符類型為或，則執行與或對應的第三NFA構造操作，具體包括：

若當前字符為|，則針對后續的正則表達式子串構造單獨的自動機；

針對當前自動機和單獨的自動機執行或操作。

9.根據權利要求5所述的正則表達式NFA的構造方法，其特征在于，所述若當前字符所屬的字符類型為小括號，則執行與小括號對應的第四NFA構造操作，具體包括：

若當前字符為(，則針對處于小括號內正則表達式子串構造單獨的自動機；

針對當前自動機和單獨的自動機執行連接操作。