[發(fā)明專利]正則表達(dá)式NFA的構(gòu)造方法及裝置

在審

• 申請(qǐng)?zhí)枺?/td>: 201911415195.5
• 申請(qǐng)日: 2019-12-31
• 公開（公告）號(hào): CN111159496A
• 公開（公告）日: 2020-05-15
• 發(fā)明（設(shè)計(jì)）人: 王彬;覃永靖;程詩(shī)堯;馬江波
• 申請(qǐng)（專利權(quán)）人: 奇安信科技集團(tuán)股份有限公司;網(wǎng)神信息技術(shù)（北京）股份有限公司
• 主分類號(hào): G06F16/903
• 分類號(hào): G06F16/903;G06F16/9032
• 代理公司: 北京路浩知識(shí)產(chǎn)權(quán)代理有限公司 11002
• 代理人: 苗曉靜

本發(fā)明實(shí)施例提供一種正則表達(dá)式NFA的構(gòu)造方法及裝置，所述方法包括：對(duì)正則表達(dá)式進(jìn)行格式化處理；對(duì)格式化處理后的正則表達(dá)式進(jìn)行遍歷處理，根據(jù)每個(gè)字符所屬的字符類型同步構(gòu)造非確定有窮自動(dòng)機(jī)NFA。也即本發(fā)明實(shí)施例采用遍歷正則表達(dá)式的方式直接構(gòu)造NFA，跨過了構(gòu)造“語(yǔ)法樹”的環(huán)節(jié)，實(shí)現(xiàn)了一種無(wú)需申請(qǐng)額外的“堆棧”空間的正則表達(dá)式NFA高效構(gòu)造方法。本發(fā)明實(shí)施例在遍歷正則表達(dá)式的同時(shí)，直接構(gòu)造了NFA，無(wú)需中間結(jié)果“語(yǔ)法樹”，因此，構(gòu)造效率較高，程序執(zhí)行時(shí)間短。此外，由于程序執(zhí)行過程中無(wú)需額外申請(qǐng)與“正則串長(zhǎng)度成正比”的“堆?！眱?nèi)存空間，因此可以避免內(nèi)存溢出風(fēng)險(xiǎn)，保障程序正常運(yùn)行。

技術(shù)領(lǐng)域

本發(fā)明涉及計(jì)算機(jī)技術(shù)領(lǐng)域，尤其涉及一種正則表達(dá)式NFA的構(gòu)造方法及裝置。

背景技術(shù)

現(xiàn)有的正則表達(dá)式NFA(非確定有窮自動(dòng)機(jī)，Non-deterministic finiteautomaton)構(gòu)造方法，通常分為兩個(gè)步驟：第一步，借助“堆棧(Stack)”構(gòu)造“語(yǔ)法樹(SyntaxTree)”，第二步，將語(yǔ)法樹轉(zhuǎn)換為NFA。

現(xiàn)有的正則表達(dá)式NFA構(gòu)造方法存在如下問題：

由于堆棧的大小不受控制，因此可能會(huì)出現(xiàn)內(nèi)存溢出問題，進(jìn)而導(dǎo)致程序掛掉。同時(shí)，構(gòu)造語(yǔ)法樹也需要消耗一定的CPU。

發(fā)明內(nèi)容

針對(duì)現(xiàn)有技術(shù)中的問題，本發(fā)明實(shí)施例提供一種正則表達(dá)式NFA的構(gòu)造方法及裝置。

具體地，本發(fā)明實(shí)施例提供了以下技術(shù)方案：

第一方面，本發(fā)明實(shí)施例提供了一種正則表達(dá)式NFA的構(gòu)造方法，包括：

對(duì)正則表達(dá)式進(jìn)行格式化處理；

對(duì)格式化處理后的正則表達(dá)式進(jìn)行遍歷處理，根據(jù)每個(gè)字符所屬的字符類型同步構(gòu)造非確定有窮自動(dòng)機(jī)NFA。

進(jìn)一步地，所述對(duì)正則表達(dá)式進(jìn)行格式化處理，具體包括：

對(duì)正則表達(dá)式進(jìn)行頭部預(yù)處理；以及，對(duì)正則表達(dá)式進(jìn)行大小寫適配。

進(jìn)一步地，所述對(duì)正則表達(dá)式進(jìn)行頭部預(yù)處理，具體包括：

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

進(jìn)一步地，所述對(duì)正則表達(dá)式進(jìn)行大小寫適配，具體包括：

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

進(jìn)一步地，所述對(duì)格式化處理后的正則表達(dá)式進(jìn)行遍歷處理，根據(jù)每個(gè)字符所屬的字符類型同步構(gòu)造非確定有窮自動(dòng)機(jī)NFA，具體包括：

創(chuàng)建當(dāng)前自動(dòng)機(jī)，對(duì)格式化處理后的正則表達(dá)式進(jìn)行遍歷處理，若當(dāng)前字符所屬的字符類型為字符轉(zhuǎn)換，則執(zhí)行與字符轉(zhuǎn)換對(duì)應(yīng)的第一NFA構(gòu)造操作；若當(dāng)前字符所屬的字符類型為量詞，則執(zhí)行與量詞對(duì)應(yīng)的第二NFA構(gòu)造操作；若當(dāng)前字符所屬的字符類型為或，則執(zhí)行與或?qū)?yīng)的第三NFA構(gòu)造操作；若當(dāng)前字符所屬的字符類型為小括號(hào)，則執(zhí)行與小括號(hào)對(duì)應(yīng)的第四NFA構(gòu)造操作。

進(jìn)一步地，所述若當(dāng)前字符所屬的字符類型為字符轉(zhuǎn)換，則執(zhí)行與字符轉(zhuǎn)換對(duì)應(yīng)的第一NFA構(gòu)造操作，具體包括：

若當(dāng)前字符為轉(zhuǎn)義字符，則解析轉(zhuǎn)義字符、16進(jìn)制、8進(jìn)制得到結(jié)果字符集；

若當(dāng)前字符為非元字符，則解析為只包含非元字符的結(jié)果字符集；

若當(dāng)前字符為任意字符.，則解析為包含所有字符的結(jié)果字符集；

若當(dāng)前字符為區(qū)間值[]，則解析為包含所有區(qū)間值的結(jié)果字符集；

若當(dāng)前字符為默認(rèn)情況，則解析為只包含單個(gè)字符的結(jié)果字符集；