分析實(shí)現(xiàn)一個簡易的正則表達(dá)式引擎)
首先給出博主自己編寫的正則表達(dá)式文法(在編譯器構(gòu)造中自底向上的LALR(1)語法分析的語法分析表生成的實(shí)現(xiàn)這篇文章里已經(jīng)出現(xiàn)過)#1b S’ S preSurvey E T M F G outSquare B V C B’ inSquare inSquareRange #1e#2b \ SPECTRANMETA POSITIVE-SURE-PRE POSITIVE-NEGA-PRE NEGATIVE-SURE-PRE NEGATIVE-NEGA-PRE ) | CLOSURE ? GIVEN LBOUND ULBOUND CLOSURE-NONGREEDY LBOUND-NONGREEDY ULBOUND-NONGREEDY CAP NONPRECAP SPECTRAN TRANMETA UPPERALPHA LOWERALPHA DIGIT SPECMETA REVERSEREF ^ [ ] - OTHERMETA $ #2e#3b S’ S #3e#4b#b S’ $1 S #e#b S $1 E #e#b S $1 preSurvey #e#b preSurvey $1 E $2 POSITIVE-SURE-PRE $1 E $2 ) #e#b preSurvey $1 E $2 POSITIVE-NEGA-PRE $1 E $2 ) #e#b preSurvey $2 NEGATIVE-SURE-PRE $1 E $2 ) $1 E #e#b preSurvey $2 NEGATIVE-NEGA-PRE $1 E $2 ) $1 E #e#b E $1 E $2 | $1 T #e#b E $1 T #e#b T $1 T $1 M #e#b T $1 M #e#b M $1 M $2 CLOSURE #e#b M $1 M $2 ? #e#b M $1 M $2 GIVEN #e#b M $1 M $2 LBOUND #e#b M $1 M $2 ULBOUND #e#b M $1 M $2 CLOSURE-NONGREEDY #e#b M $1 M $2 LBOUND-NONGREEDY #e#b M $1 M $2 ULBOUND-NONGREEDY #e#b M $1 F #e#b F $2 CAP $1 E $2 ) #e#b F $1 G #e#b F $2 NONPRECAP $1 E $2 ) #e#b F $1 outSquare #e#b outSquare $2 SPECTRAN #e#b outSquare $2 TRANMETA #e#b outSquare $2 \ #e#b outSquare $2 SPECTRANMETA #e#b outSquare $2 UPPERALPHA #e#b outSquare $2 LOWERALPHA #e#b outSquare $2 DIGIT #e#b outSquare $2 SPECMETA #e#b outSquare $2 REVERSEREF #e#b outSquare $2 ^ #e#b G $2 [ $1 B $1 V $1 C $2 ] #e#b V $2 ^ #e#b V #e#b B $1 B $1 B’ #e#b B $1 B’ #e#b B’ $1 V $1 inSquareRange $2 - $1 inSquareRange #e#b inSquareRange $2 SPECTRAN #e#b inSquareRange $2 SPECMETA #e#b inSquareRange $2 OTHERMETA #e#b inSquareRange $2 UPPERALPHA #e#b inSquareRange $2 LOWERALPHA #e#b inSquareRange $2 DIGIT #e#b inSquareRange $2 CLOSURE #e#b inSquareRange $2 \ #e#b inSquareRange $2 SPECTRANMETA #e#b inSquareRange $2 ? #e#b inSquareRange $2 CAP #e#b inSquareRange $2 | #e#b inSquareRange $2 ) #e#b C $1 C $1 inSquare #e#b C $1 inSquare #e#b inSquare $1 inSquareRange #e#b inSquare $2 NONPRECAP #e#b inSquare $2 POSITIVE-SURE-PRE #e#b inSquare $2 POSITIVE-NEGA-PRE #e#b inSquare $2 NEGATIVE-SURE-PRE #e#b inSquare $2 NEGATIVE-NEGA-PRE #e#b inSquare $2 ULBOUND #e#b inSquare $2 LBOUND #e#b inSquare $2 ULBOUND-NONGREEDY #e#b inSquare $2 LBOUND-NONGREEDY #e#b inSquare $2 CLOSURE-NONGREEDY #e#b inSquare $2 GIVEN #e#b G $2 [ $1 B $2 ] #e#b G $2 [ $1 V $1 C $2 ] #e#4e部分終結(jié)符和非終結(jié)符的含義是S’:增廣文法開始符號S:原文法開始符號preSurvey:預(yù)查表達(dá)式outSquare方括號外的直接量inSquareRange:方括號內(nèi)中 - 表示的范圍的一端inSquare方括號內(nèi)的直接量SPECTRANMETA特殊轉(zhuǎn)義元字符 - ^POSITIVE-SURE-PRE正向肯定預(yù)查運(yùn)算符(?POSITIVE-NEGA-PRE正向否定預(yù)查運(yùn)算符(?!NEGATIVE-SURE-PRE反向肯定預(yù)查運(yùn)算符(?NEGATIVE-NEGA-PRE反向否定預(yù)查運(yùn)算符(?!CLOSURE閉包*和GIVEN指定重復(fù)次數(shù){n}LBOUND:指定最小重復(fù)次數(shù){n, }ULBOUND:對重復(fù)次數(shù)指定上下界{n, m}**CLOSURE-NONGREEDY:非貪婪閉包? *?**LBOUND-NONGREEDY指定最小重復(fù)次數(shù)的非貪婪版本{n, }?ULBOUND-NONGREEDY指定最大最小重復(fù)次數(shù)的非貪婪版本{n, m}?CAP子表達(dá)式左括號(NONPRECAP非捕獲匹配(?:SPECTRAN特殊轉(zhuǎn)義字符\b單詞邊界 \B非單詞邊界 \d數(shù)字 \D非數(shù)字 \f 換頁 \n 換行 \r 回車 \s 空白 \S 非空白\t 制表\v 垂直制表 \w 單詞字符 \W 非單詞字符TRANMETA轉(zhuǎn)義元字符 * ? $ . ( ) : ! lt; | [ ] { }UPPERALPHA:大寫字母LOWERALPHA小寫字母DIGIT數(shù)字SPECMETA特殊元字符 . $REVERSEREF反向引用OTHERMETA其他元字符 : ! { }了解終結(jié)符非終結(jié)符的含義后產(chǎn)生式也就不難理解了本正則表達(dá)式引擎要求方括號外的直接量只能為SPECTRAN、TRANMETA、\、SPECTRANMETA、UPPERALPHA、LOWERALPHA、DIGIT、SPECMETA、REVERSEREF、^之一不相符的書寫形式都會報(bào)告語法錯誤。因此任何出現(xiàn)在方括號代表本身的元字符必須使用轉(zhuǎn)義書寫(即加).文法對預(yù)查的處理還是存在一些問題因?yàn)樗恢С诸A(yù)查表達(dá)式(不可自嵌套)和其他預(yù)查表達(dá)式以及E的任意組合如果要支持這一點(diǎn)必須大改文法且要做不少重復(fù)工作比較麻煩所以本引擎對預(yù)查只支持單一的沒有自嵌套的預(yù)查表達(dá)式。此外對非貪婪匹配的處理還是存在一些問題的回溯引擎處理非貪婪匹配會由少到多逐一嘗試但是本引擎并發(fā)地模擬所有可能的轉(zhuǎn)移路徑回溯引擎的做法在本引擎中行不通所以博主采用了比較笨有待斟酌的做法-閉包和指定重復(fù)次數(shù)的運(yùn)算符為非貪婪時讓其匹配最少的幾種可能如?轉(zhuǎn)換為NFA時將匹配1次這種做法是有一些問題的在回溯引擎中若匹配aaab則a?b和aaab匹配但本引擎只能匹配子串a(chǎn)b,雖然邏輯上也講得通但和非貪婪匹配的預(yù)期行為不一致。暫時不知道有什么更好的解決方法暫時就這樣吧引擎的總體執(zhí)行邏輯并不復(fù)雜語法分析器讀入詞法分析器傳入的Token進(jìn)行移入歸約在此過程中使用S屬性的語法制導(dǎo)翻譯方案將正則表達(dá)式翻譯為等價NFA每當(dāng)進(jìn)行一次對句柄的歸約時將用與句柄匹配的產(chǎn)生式體中非終結(jié)符的綜合屬性構(gòu)造產(chǎn)生頭非終結(jié)符的綜合屬性(可能為NFA也可能不為)實(shí)際上就是執(zhí)行與產(chǎn)生式關(guān)聯(lián)的語義動作。當(dāng)對句柄S在向前看符號$下歸約即接受時,S對應(yīng)的NFA即為翻譯結(jié)果。隨后采用模擬NFA(并發(fā)地考察所有可能的轉(zhuǎn)移狀態(tài))的方法進(jìn)行無回溯的匹配得到匹配結(jié)果。每一個子表達(dá)式的接受態(tài)都有一個指向相應(yīng)開始態(tài)的指針匹配過程中抵達(dá)子表達(dá)式接受態(tài)時使用該指針確定子匹配結(jié)果模擬過程中可能先后多次抵達(dá)同一個子表達(dá)式的開始態(tài)我采用開始態(tài)編號加抵達(dá)開始態(tài)時棧頂下標(biāo)來唯一標(biāo)識每一個到達(dá)對于每一個到達(dá)都會生成與到達(dá)相關(guān)的傳播項(xiàng)該傳播項(xiàng)沿匹配路徑不斷向前傳播當(dāng)傳播到對應(yīng)子表達(dá)式接受態(tài)時就可以利用與接受態(tài)對應(yīng)的傳播項(xiàng)確定與特定子表達(dá)式開始的到達(dá)對應(yīng)的子匹配結(jié)果當(dāng)該傳播項(xiàng)流動至生成該傳播項(xiàng)的子表達(dá)式開始態(tài)時就發(fā)生了回環(huán)此時傳播項(xiàng)會被殺死以阻止其進(jìn)一步傳播避免其對子匹配結(jié)果的截取造成影響。另外在算法中計(jì)算出從當(dāng)前字符轉(zhuǎn)移至的新狀態(tài)的閉包時會檢查是否有傳播項(xiàng)從閉包中消失如果有會在相關(guān)的數(shù)據(jù)結(jié)構(gòu)中刪去和消失的傳播項(xiàng)關(guān)聯(lián)的項(xiàng)以節(jié)省內(nèi)存空間。對反向引用的處理是保存文件指針當(dāng)前位置然后不斷向前讀入字符匹配反向引用若匹配成功則把此時文件指針的位置反向引用轉(zhuǎn)移至的狀態(tài)和和反向引用關(guān)聯(lián)的傳播項(xiàng)加入表如果匹配過程中文件指針到達(dá)了相同位置則把反向引用轉(zhuǎn)移至的新狀態(tài)加入會成為棧頂?shù)膎ewstacknode的狀態(tài)集然后將傳播項(xiàng)并入當(dāng)前傳播項(xiàng)集合并更新相關(guān)數(shù)據(jù)結(jié)構(gòu)。最后說明一下如果匹配成功每一個匹配結(jié)果都是整個正則表達(dá)式所能匹配的最長子串。另外這個引擎寫得真的很爛博主自己就很不滿意它對預(yù)查的支持不完善對非貪婪的處理存在問題也未能支持一些本可以支持的特性和google的RE2引擎實(shí)在沒法比(代碼量上已經(jīng)輸給它)僅能滿足常見的匹配需求后續(xù)可能會繼續(xù)改正本項(xiàng)目的github地址:GitHub - naturerun/RTNWSK-RE-ENGINE: 用C實(shí)現(xiàn)的正則表達(dá)式引擎支持子表達(dá)式反向引用簡單的預(yù)查語法一些字符類非貪婪匹配和邊界匹配自己編寫的正則表達(dá)式引擎可能有未知的缺陷、錯誤和漏洞博主自己沒有那么多精力進(jìn)行詳盡的測試和維護(hù)如果發(fā)現(xiàn)錯誤愿意提就提出謝謝大家2019.4.25更新新增對非貪婪匹配的支持 LALR(1)分析實(shí)現(xiàn)一個簡易的正則表達(dá)式引擎
首先給出博主自己編寫的正則表達(dá)式文法(在編譯器構(gòu)造中自底向上的LALR(1)語法分析的語法分析表生成的實(shí)現(xiàn)這篇文章里已經(jīng)出現(xiàn)過)#1b S’ S preSurvey E T M F G outSquare B V C B’ inSquare inSquareRange #1e#2b \ SPECTRANMETA POSITIVE-SURE-PRE POSITIVE-NEGA-PRE NEGATIVE-SURE-PRE NEGATIVE-NEGA-PRE ) | CLOSURE ? GIVEN LBOUND ULBOUND CLOSURE-NONGREEDY LBOUND-NONGREEDY ULBOUND-NONGREEDY CAP NONPRECAP SPECTRAN TRANMETA UPPERALPHA LOWERALPHA DIGIT SPECMETA REVERSEREF ^ [ ] - OTHERMETA $ #2e#3b S’ S #3e#4b#b S’ $1 S #e#b S $1 E #e#b S $1 preSurvey #e#b preSurvey $1 E $2 POSITIVE-SURE-PRE $1 E $2 ) #e#b preSurvey $1 E $2 POSITIVE-NEGA-PRE $1 E $2 ) #e#b preSurvey $2 NEGATIVE-SURE-PRE $1 E $2 ) $1 E #e#b preSurvey $2 NEGATIVE-NEGA-PRE $1 E $2 ) $1 E #e#b E $1 E $2 | $1 T #e#b E $1 T #e#b T $1 T $1 M #e#b T $1 M #e#b M $1 M $2 CLOSURE #e#b M $1 M $2 ? #e#b M $1 M $2 GIVEN #e#b M $1 M $2 LBOUND #e#b M $1 M $2 ULBOUND #e#b M $1 M $2 CLOSURE-NONGREEDY #e#b M $1 M $2 LBOUND-NONGREEDY #e#b M $1 M $2 ULBOUND-NONGREEDY #e#b M $1 F #e#b F $2 CAP $1 E $2 ) #e#b F $1 G #e#b F $2 NONPRECAP $1 E $2 ) #e#b F $1 outSquare #e#b outSquare $2 SPECTRAN #e#b outSquare $2 TRANMETA #e#b outSquare $2 \ #e#b outSquare $2 SPECTRANMETA #e#b outSquare $2 UPPERALPHA #e#b outSquare $2 LOWERALPHA #e#b outSquare $2 DIGIT #e#b outSquare $2 SPECMETA #e#b outSquare $2 REVERSEREF #e#b outSquare $2 ^ #e#b G $2 [ $1 B $1 V $1 C $2 ] #e#b V $2 ^ #e#b V #e#b B $1 B $1 B’ #e#b B $1 B’ #e#b B’ $1 V $1 inSquareRange $2 - $1 inSquareRange #e#b inSquareRange $2 SPECTRAN #e#b inSquareRange $2 SPECMETA #e#b inSquareRange $2 OTHERMETA #e#b inSquareRange $2 UPPERALPHA #e#b inSquareRange $2 LOWERALPHA #e#b inSquareRange $2 DIGIT #e#b inSquareRange $2 CLOSURE #e#b inSquareRange $2 \ #e#b inSquareRange $2 SPECTRANMETA #e#b inSquareRange $2 ? #e#b inSquareRange $2 CAP #e#b inSquareRange $2 | #e#b inSquareRange $2 ) #e#b C $1 C $1 inSquare #e#b C $1 inSquare #e#b inSquare $1 inSquareRange #e#b inSquare $2 NONPRECAP #e#b inSquare $2 POSITIVE-SURE-PRE #e#b inSquare $2 POSITIVE-NEGA-PRE #e#b inSquare $2 NEGATIVE-SURE-PRE #e#b inSquare $2 NEGATIVE-NEGA-PRE #e#b inSquare $2 ULBOUND #e#b inSquare $2 LBOUND #e#b inSquare $2 ULBOUND-NONGREEDY #e#b inSquare $2 LBOUND-NONGREEDY #e#b inSquare $2 CLOSURE-NONGREEDY #e#b inSquare $2 GIVEN #e#b G $2 [ $1 B $2 ] #e#b G $2 [ $1 V $1 C $2 ] #e#4e部分終結(jié)符和非終結(jié)符的含義是S’:增廣文法開始符號S:原文法開始符號preSurvey:預(yù)查表達(dá)式outSquare方括號外的直接量inSquareRange:方括號內(nèi)中 - 表示的范圍的一端inSquare方括號內(nèi)的直接量SPECTRANMETA特殊轉(zhuǎn)義元字符 - ^POSITIVE-SURE-PRE正向肯定預(yù)查運(yùn)算符(?POSITIVE-NEGA-PRE正向否定預(yù)查運(yùn)算符(?!NEGATIVE-SURE-PRE反向肯定預(yù)查運(yùn)算符(?NEGATIVE-NEGA-PRE反向否定預(yù)查運(yùn)算符(?!CLOSURE閉包*和GIVEN指定重復(fù)次數(shù){n}LBOUND:指定最小重復(fù)次數(shù){n, }ULBOUND:對重復(fù)次數(shù)指定上下界{n, m}**CLOSURE-NONGREEDY:非貪婪閉包? *?**LBOUND-NONGREEDY指定最小重復(fù)次數(shù)的非貪婪版本{n, }?ULBOUND-NONGREEDY指定最大最小重復(fù)次數(shù)的非貪婪版本{n, m}?CAP子表達(dá)式左括號(NONPRECAP非捕獲匹配(?:SPECTRAN特殊轉(zhuǎn)義字符\b單詞邊界 \B非單詞邊界 \d數(shù)字 \D非數(shù)字 \f 換頁 \n 換行 \r 回車 \s 空白 \S 非空白\t 制表\v 垂直制表 \w 單詞字符 \W 非單詞字符TRANMETA轉(zhuǎn)義元字符 * ? $ . ( ) : ! lt; | [ ] { }UPPERALPHA:大寫字母LOWERALPHA小寫字母DIGIT數(shù)字SPECMETA特殊元字符 . $REVERSEREF反向引用OTHERMETA其他元字符 : ! { }了解終結(jié)符非終結(jié)符的含義后產(chǎn)生式也就不難理解了本正則表達(dá)式引擎要求方括號外的直接量只能為SPECTRAN、TRANMETA、\、SPECTRANMETA、UPPERALPHA、LOWERALPHA、DIGIT、SPECMETA、REVERSEREF、^之一不相符的書寫形式都會報(bào)告語法錯誤。因此任何出現(xiàn)在方括號代表本身的元字符必須使用轉(zhuǎn)義書寫(即加).文法對預(yù)查的處理還是存在一些問題因?yàn)樗恢С诸A(yù)查表達(dá)式(不可自嵌套)和其他預(yù)查表達(dá)式以及E的任意組合如果要支持這一點(diǎn)必須大改文法且要做不少重復(fù)工作比較麻煩所以本引擎對預(yù)查只支持單一的沒有自嵌套的預(yù)查表達(dá)式。此外對非貪婪匹配的處理還是存在一些問題的回溯引擎處理非貪婪匹配會由少到多逐一嘗試但是本引擎并發(fā)地模擬所有可能的轉(zhuǎn)移路徑回溯引擎的做法在本引擎中行不通所以博主采用了比較笨有待斟酌的做法-閉包和指定重復(fù)次數(shù)的運(yùn)算符為非貪婪時讓其匹配最少的幾種可能如?轉(zhuǎn)換為NFA時將匹配1次這種做法是有一些問題的在回溯引擎中若匹配aaab則a?b和aaab匹配但本引擎只能匹配子串a(chǎn)b,雖然邏輯上也講得通但和非貪婪匹配的預(yù)期行為不一致。暫時不知道有什么更好的解決方法暫時就這樣吧引擎的總體執(zhí)行邏輯并不復(fù)雜語法分析器讀入詞法分析器傳入的Token進(jìn)行移入歸約在此過程中使用S屬性的語法制導(dǎo)翻譯方案將正則表達(dá)式翻譯為等價NFA每當(dāng)進(jìn)行一次對句柄的歸約時將用與句柄匹配的產(chǎn)生式體中非終結(jié)符的綜合屬性構(gòu)造產(chǎn)生頭非終結(jié)符的綜合屬性(可能為NFA也可能不為)實(shí)際上就是執(zhí)行與產(chǎn)生式關(guān)聯(lián)的語義動作。當(dāng)對句柄S在向前看符號$下歸約即接受時,S對應(yīng)的NFA即為翻譯結(jié)果。隨后采用模擬NFA(并發(fā)地考察所有可能的轉(zhuǎn)移狀態(tài))的方法進(jìn)行無回溯的匹配得到匹配結(jié)果。每一個子表達(dá)式的接受態(tài)都有一個指向相應(yīng)開始態(tài)的指針匹配過程中抵達(dá)子表達(dá)式接受態(tài)時使用該指針確定子匹配結(jié)果模擬過程中可能先后多次抵達(dá)同一個子表達(dá)式的開始態(tài)我采用開始態(tài)編號加抵達(dá)開始態(tài)時棧頂下標(biāo)來唯一標(biāo)識每一個到達(dá)對于每一個到達(dá)都會生成與到達(dá)相關(guān)的傳播項(xiàng)該傳播項(xiàng)沿匹配路徑不斷向前傳播當(dāng)傳播到對應(yīng)子表達(dá)式接受態(tài)時就可以利用與接受態(tài)對應(yīng)的傳播項(xiàng)確定與特定子表達(dá)式開始的到達(dá)對應(yīng)的子匹配結(jié)果當(dāng)該傳播項(xiàng)流動至生成該傳播項(xiàng)的子表達(dá)式開始態(tài)時就發(fā)生了回環(huán)此時傳播項(xiàng)會被殺死以阻止其進(jìn)一步傳播避免其對子匹配結(jié)果的截取造成影響。另外在算法中計(jì)算出從當(dāng)前字符轉(zhuǎn)移至的新狀態(tài)的閉包時會檢查是否有傳播項(xiàng)從閉包中消失如果有會在相關(guān)的數(shù)據(jù)結(jié)構(gòu)中刪去和消失的傳播項(xiàng)關(guān)聯(lián)的項(xiàng)以節(jié)省內(nèi)存空間。對反向引用的處理是保存文件指針當(dāng)前位置然后不斷向前讀入字符匹配反向引用若匹配成功則把此時文件指針的位置反向引用轉(zhuǎn)移至的狀態(tài)和和反向引用關(guān)聯(lián)的傳播項(xiàng)加入表如果匹配過程中文件指針到達(dá)了相同位置則把反向引用轉(zhuǎn)移至的新狀態(tài)加入會成為棧頂?shù)膎ewstacknode的狀態(tài)集然后將傳播項(xiàng)并入當(dāng)前傳播項(xiàng)集合并更新相關(guān)數(shù)據(jù)結(jié)構(gòu)。最后說明一下如果匹配成功每一個匹配結(jié)果都是整個正則表達(dá)式所能匹配的最長子串。另外這個引擎寫得真的很爛博主自己就很不滿意它對預(yù)查的支持不完善對非貪婪的處理存在問題也未能支持一些本可以支持的特性和google的RE2引擎實(shí)在沒法比(代碼量上已經(jīng)輸給它)僅能滿足常見的匹配需求后續(xù)可能會繼續(xù)改正本項(xiàng)目的github地址:GitHub - naturerun/RTNWSK-RE-ENGINE: 用C實(shí)現(xiàn)的正則表達(dá)式引擎支持子表達(dá)式反向引用簡單的預(yù)查語法一些字符類非貪婪匹配和邊界匹配自己編寫的正則表達(dá)式引擎可能有未知的缺陷、錯誤和漏洞博主自己沒有那么多精力進(jìn)行詳盡的測試和維護(hù)如果發(fā)現(xiàn)錯誤愿意提就提出謝謝大家2019.4.25更新新增對非貪婪匹配的支持