文本編碼類協議通用解析器的製作方法
2023-05-18 17:18:51
專利名稱：文本編碼類協議通用解析器的製作方法
技術領域：
本發明涉及網絡通信技術領域，尤其涉及一種文本編碼類協議通用解析器。
背景技術：
Internet工程任務組(IETF，Internet Engineering Task Force)組織使用ABNF定義了多個協議中的報文格式，例如會話起始協議(SIP，SessionInitiation Protocol)等。在實現這些協議時，需要按照擴展巴克斯範式(ABNF，Augmented BNF)規則對報文進行分析和模式。
ABNF是IETF組織在RFC2234中定義的一個字符串模式匹配的文法定義。ABNF是在巴克斯範式(BNF)基礎上的擴展，其與標準巴克斯範式的區別包括命名規則，循環，選擇，次序獨立以及值域。
目前，常見的ABNF解析器的實現方案為在通用微處理器上，使用軟體來實現編譯原理領域內的詞法和語法解析算法。例如，常見的LL(1)文法解析算法，該算法是一種自上而下的非遞歸預測分析器，它通過計算文法的首終結符集合(First集合)和後繼終結符集合(Follow集合)從而構造出該文法的預測分析表，進而利用分析表進行推導。LL(1)文法是無二義的文法，且不含左遞歸。LL(1)中的第一個「L」表示從左到右地掃描輸入串；第二個「L」表示產生最左推導；1代表在決定分析器的每步動作時向前看一個輸入符號。
由於ABNF是基於文本定義的語法，所以在對變長的字符串解析時，其複雜度高於基於二進位的定長數據解析。上述方案的優點在於解析器開發代價小，開發效率高。但是，由於通用處理器並不是專門針對ABNF解析進行設計的，因而其處理速度、吞吐量等性能參數往往受限。當需要高速處理能力時，例如，SIP軟交換系統需要處理百萬量級的連接，則為了達到性能要求需要採用更高級別的微處理器，這樣，必然提高解析器產品的成本。
目前，採用的另一種ABNF解析方案是也是在通用微處理器上，針對特定領域內ABNF語法規則的特點設計特定的軟體來進行處理。以SIP協議棧為例，常見的實現方式是根據SIP文法規則的特點，通過分割符將SIP報文分割為若干欄位，再進行相應的語法規則檢查。
在這一方案中針對特定語法規則進行設計，在效率上優於前面描述的技術方案。但是由於其針對特定規則進行處理，導致其通用性較差，針對新的語法規則必須重新進行設計，從而提高了解析器開發成本，導致開發效率較低。另一方面，由於其仍然是基於通用微處理器進行的，在需要高速處理能力的情況下仍然會存在前面描述的第一種方案所存在的問題。
發明內容
鑑於上述現有技術所存在的問題，本發明的目的是提供一種文本編碼類協議通用解析器，提高解析器的解析效率，並使解析器具有良好的通用性。
本發明的目的是通過以下技術方案實現的本發明提供了一種文本編碼類協議通用解析器，該解析器包括規則存儲模塊、待解析消息存儲模塊和消息解析模塊，消息解析模塊根據規則存儲模塊中保存的規則信息對待解析消息存儲模塊中的消息文本進行解析處理，所述的消息解析模塊為採用邏輯晶片實現。
所述的邏輯晶片包括現場可編程邏輯門列陣FPGA或複雜可編程邏輯器件CPLD。
所述的規則存儲模塊為規則樹存儲模塊，規則樹存儲模塊中保存有基於擴展巴克斯範式ABNF方法定義的規則生成的規則樹。
所述的規則樹為不包含增式選擇、序列組及可選序列結構的規則樹，且所述的規則樹為以各規則中的一個規則為頂點，採用遞歸的方式生成的規則樹。
所述的消息解析模塊進一步包括主進程處理部分用於根據棧頂節點的類型控制分別進入解析終結符部分、匹配首終結符部分或匹配後繼終結符部分的處理過程；解析終結符部分用於當棧頂結點為終結節點時，由主進程處理部分控制啟動，並進行終結節點的終結符的解析處理，解析完成後通知主進程處理部分；匹配首終結符部分用於對當棧頂結點為非終結點時，且為首終結符集合時，由主進程處理部分控制啟動，並進行首終結符的匹配處理，判斷當前字符是否在節點首終結符集合內，匹配完成後通知主進程處理部分；匹配後繼終結符部分用於對當棧頂結點為非終結點時，且為後繼終結符集合時，由主進程處理部分控制啟動，並進行後繼終結符的匹配處理，判斷當前字符是否在節點後繼終結符集合內，匹配完成後通知主進程處理部分。
所述的消息解析模塊採用狀態機實現。
所述的主進程處理部分對應的狀態機包括循環解析PARSE_LOOP狀態，在該狀態下進行消息報文的解析；到達最大重複次數REPEAT_MAX狀態，在該狀態下判斷保存首規則樹節點的節點棧的棧頂節點的類型是否為終結節點；匹配終結符TERM_MATCH狀態，在該狀態下進行終結符的匹配處理張，並啟動解析終結符部分；
進入首終結符集合判斷IN_FIRST狀態，在該狀態下進行首終結符集合的判斷處理，並在確定存在首終結符集合時，啟動匹配首終結符部分；所有的子節點已經處理ALLSUB狀態，當IN_FIRST狀態下所有的子節點處理完成時進入該狀態，且在該狀態下返回PARSE_LOOP狀態；後繼終結符集判斷JUDGE_FOLLOW狀態，在該狀態下進行後繼終結符集合的判斷處理，並在確定存在後繼終結符集合時，進入FOLLOW集合判斷IN_FOLLOW狀態，啟動匹配後繼終結符部分，如果不存在後繼終結符集合時進入下一規則NEXTRULE狀態，並返回PARSE_LOOP狀態的。
所述的解析終結符部分的狀態機包括字符串類型終結符TERM_STRING狀態，在該狀態下對單個字符串循環進行單個字符的匹配處理；字符編碼連接類型終結符TERM_CODE_LIST狀態，在該狀態下對字符編碼連接循環進行單個字符的匹配處理；終結符匹配成功TERM_SUCCESS狀態和終結符匹配失敗TERM_FAIL狀態，在該狀態下通知主進程處理部分匹配處理結果。
所述的匹配首終結符部分的狀態機包括列表循環處理UST_LOOP狀態，在該狀態下判斷編碼類型為字符串字符編碼連接；字符串類型FIRST_STRING狀態，在該狀態下對單個字符串循環進行單個字符的匹配處理；字符編碼連接類型終結符FIRST_CODE_UST狀態，在該狀態下對字符編碼連接循環進行單個字符的匹配處理；首終結符集合匹配成功FIRST_SUCCESS狀態和首終結符集合匹配失敗FIRST_FAIL狀態，在該狀態下通知主進程處理部分匹配處理結果。
所述的匹配後繼終結符部分包括
列表循環處理LIST_LOOP狀態，在該狀態下判斷編碼類型為字符串 字符編碼連接；字符串類型FOLLOW_STRING狀態，在該狀態下對單個字符串循環進行單個字符的匹配處理；字符編碼連接類型FOLLOW_CODE_LIST狀態，在該狀態下對字符編碼連接循環進行單個字符的匹配處理；後繼終結符匹配成功FOLLOW_SUCCESS狀態和後繼終結符匹配失敗FOLLOW_FAIL狀態，在該狀態下通知主進程處理部分匹配處理結果。
由上述本發明提供的技術方案可以看出，本發明提供的基於FPGA硬體實現的通用ABNF文法解析與軟體實現方式相比，解析效率大為提高，有利於提高產品效率，降低成本。同時，本發明為基於ABNF規則進行解析，使得本發明具有良好的通用性，可以適用於各種基於ABNF進行規則定義的場合，例如，對SIP協議棧、XML(可擴展標記語言)的處理等等；因此，本發明極大地降低了相應的解析器的開發成本，提高了開發效率。
圖1為本發明所述的解析器的結構示意圖；圖2為本發明所述的消息解析模塊的實現原理圖；圖3為圖2中的主進程的狀態機模型；圖4為圖2中的解析終結符進程的狀態機模型；圖5為圖2中的匹配首終結符進程的狀態機模型；圖6為圖2中的匹配後繼終結符進程的狀態機模型。
具體實施例方式
本發明的核心是基於FPGA(可編程邏輯晶片)實現的硬體ABNF解析器，所述硬體ABNF解析器可以在保證通用性的前提下，通過硬體優化提高解析器的解碼效率。
本發明是在LL(1)算法的基礎上，提出一種FPGA實現的通用ABNF硬體解析器，可以對輸入字符串依據ABNF規則進行解析。
本發明所述的基於FPGA實現的通用ABNF硬體解析器，其功能結構如圖1所示，根據代表ABNF規則的規則樹信息(即未賦值的規則樹)，對需要處理的字符串消息進行解析，結果為已經賦值的規則樹。
本發明所述的文本編碼類協議通用解析器主要包括規則樹存儲模塊、待解析消息存儲模塊和消息解析模塊組成，其中所述的規則樹存儲模塊用於存儲規則樹數據，規則樹節點通常需要按順序存儲，一次可以讀入整個規則節點；所述的待解析消息存儲模塊用於存放待解析的消息文本，通常可以以字節形式順序存放；所述的消息解析模塊用於根據規則樹信息對待解析的消息文件進行解碼處理，以獲得消息文件的解析處理結果。
本發明中主要涉及規則樹的生成過程和消息解析模塊的硬體實現方式，下面將分別對兩個主要方面進行說明。
本發明中，所述的規則樹信息可以按如下方式從ABNF規則文本生成(1)對ABNF規則進行展平處理，即將各規則進行簡化描述，使得其不包含增式選擇、序列組和可選序列等複雜結構，具體可以將簡化描述後的規則保存於規則表中，每個表項對應一個簡化處理後的新的規則，相應的處理步驟如下所述對於每個規則，在規則表(如哈希表)中添加一條規則表項；對於包含增式選擇的規則，將規則添加的選擇內容加入到原規則中，更新原規則表的表項；
對於包含序列組的規則，將序列組內容定義為新規則，並用新規則替換原規則的序列組內容，重複此過程，直到新規則不包含序列組為止；對於包含可選序列的規則，將可選序列內容定義為新規則，並用新規則替換原規則的可選序列內容，重複此過程，直到新規則不包含序列組為止；(2)基於所述的規則表生成相應的規則樹，具體為指定規則表中的某一規則為頂點，並以此為根節點遞歸生成對應的規則樹；(3)使用LL(1)解析算法中First集合和Follow集合的生成方法，對每個規則樹節點計算其相應的First集合和Follow集合。
本發明中，所述的消息解析模塊為核心處理部分，下面將對所述的消息解析模塊的具體實現方式進行詳細說明。
所述的消息解析模塊主要包括四個進程，分別由四個狀態機實現。其中主進程main控制其它三個子進程，其它三個子進程包括parse_term(解析終結符)進程、match_first_proc(匹配first過程)和match_follow_proc(匹配follow過程)，各進程關係如圖2所示，由主進程在處理過程中控制其他三個進程的啟動，並實現相應的功能；主進程判斷符合啟動相應的子進程的條件時，則遷移到相應的狀態，向相應的子進程發送信號啟動對應的子進程進行相應的處理，各子進程處理完成後需要將結果返回主進程，並由主進程輸出成功或失敗的解析結果信號。
下面將分別對各個進程的狀態機包括的狀態及具體處理過程進行說明。
(1)主進程main，即主進程處理部分主進程main作為主控進程，由時鐘上升沿驅動，包含以下狀態IDLE(空閒)，INIT(初始化)，PARSE_LOOP(循環解析)，REPEAT_MAX(到達最大重複次數)，TERM_MATCH(匹配終結符)，IN_FIRST(進行FIRST集合判斷)，FIRSTSUB(第一個子節點)，ALLSUB(所有的子節點已經處理)，CHOOSESUB(選擇子節點)，NEXTSUB0(下一個子節點0)，NEXTSUB1(下一個子節點1)，GETSUB(取子節點)，JUDGE_FOLLOW(FOLLOW集判斷)，IN_FOLLOW(進入FOLLOW集合判斷)，NEXTRULE(下一規則)，END_PARSE(解析結束)；其進程狀態機模型如附圖3所示，相應的狀態遷移處理過程為當檢測到上升沿信號時，狀態機由IDLE狀態進入PARSE_LOOP狀態，開始消息報文的解析；狀態機在REPEAT_MAX狀態判斷節點棧的棧頂節點的類型，所述的節點棧是在主進程實現時的一個節點棧，保存的內容是規則樹的節點，用於跟蹤當前基於相應的規則樹的解析進度情況，並根據棧頂節點的類型確定進入相應的子進程進行處理，參照圖2所示，具體如下如果是終結節點，則將終結符匹配信號match_term代入高電平，啟動parse_term進程，等待終結符匹配結果match_term_result信號出現高電平後進入狀態TERM_MATCH，並將信號match_term代入低電平以中止parse_term進程，狀態機返回PARSE_LOOP狀態；如果棧頂節點是非終結節點，則將信號match_first代入高電平，啟動match_first_proc進程，具體的處理過程為若match_first_success信號出現高電平，表示當前待解析字符在節點的first集合中，狀態機進入狀態FIRST_SUB，並把信號match_first代入低電平以中止match_first_proc進程，此時狀態機選取正確的子節點壓入棧中並返回PARSE_LOOP狀態；若match_first_fail信號出現高電平，表示當前待解析字符不在節點的first集合中，狀態機進入狀態JUDGE_FOLLOW狀態，在此狀態下，信號match_follow被代入高電平，啟動match_follow_proc進程，等待matcn_follow_success信號或者match_follow_fail信號以判斷能否進行下一節點的匹配，並返回PARSE_LOOP狀態。
(2)子進程parse_term，即解析終結符進程子進程parse_term為時鐘上升沿驅動，用於完成終結節點的匹配，其對應的狀態包括IDLE，START(啟動)，TERM_STRING(字符串類型終結符)，TERM_CODE_LIST(字符編碼連接類型終結符)，TERM_SUCCESS(終結符匹配成功)，TERM_FAIL(終結符匹配失敗)；其進程狀態機模型如附圖4所示，當match_term信號被主進程代入高電平，狀態機由IDLE狀態進入START狀態，在此狀態下狀態機判斷編碼類型，以根據不同的編碼類型進入不同的狀態進行處理如果是字符串，則進入TERM_STRING狀態，循環匹配單個字符，那當然，如果字符串僅包含單個字符編碼或者單個字符的range編碼，則直接判斷是否匹配即可；如果是字符編碼連接，則進入TERM_CODE_LIST狀態，循環進行單個字符的匹配；最後，便可以根據匹配結果選擇進入狀態TERM_SUCCESS或者TERM_FAIL，將term_match_result代入高電平通知主狀態機；當主狀態機將math_term置為低電平，則parse_term狀態機回到IDLE狀態，清除term_match_result信號等待下一次匹配。
(3)子進程match_first_proc，即匹配首終結符進程進程match_first_proc為時鐘上升沿驅動，用於比較當前字符是否存在於節點first集合中，相應的狀態包括IDLE，LIST_LOOP(列表循環處理)，FIRST_STRING(字符串類型)，FIRST_CODE_LIST(字符編碼連接類型)，FIRST_SUCCESS(FIRST集合匹配成功)，FIRST_FAIL(FIRST集合匹配失敗)；其進程狀態機模型如附圖5所示，相應的狀態遷移處理過程為
當match_first信號被主進程代入高電平，狀態機由IDLE狀態進入LIST_LOOP狀態，在此狀態下狀態機判斷編碼類型，並根據編碼類型採用相應的處理如果是字符串，則進入FIRST_STRING狀態，循環匹配單個字符；如果是單個字符編碼或者單個字符的range(有效範圍)編碼，則直接判斷是否匹配；如果是字符編碼連接，則進入FIRST_CODE_LIST狀態，循環匹配單個字符；最後，根據匹配結果選擇進入狀態FIRST_SUCCESS或者回到LIST_LOOP匹配下一個列表內容，直到發現匹配的first集合元素或者到達列表尾部；如果沒有發現匹配的first元素，則狀態機進入FIRST_FAIL狀態；狀態機在FIRST_SUCCESS和FIRST_FAIL分別把first_match_success和first_match_fail代入高電平通知主狀態機；當主狀態機將match_first置為低電平，則match_first_proc狀態機回到IDLE狀態，清除match_first_success或match_first_fail信號，並等待下一次匹配。
(4)子進程match_follow_proc，即匹配後繼終結符處理進程進程match_follow_proc時鐘上升沿驅動，用於比較當前字符是否存在於節點follow集合中，相應的狀態包括IDLE，LIST_LOOP(列表循環處理)，FOLLOW_STRING(字符串類型)，FOLLOW_CODE_LIST(字符編碼連接類型)，FOLLOW_SUCCESS(FOLLOW匹配成功)，FOLLOW_FAIL(FOLLOW匹配失敗)；其進程狀態機模型如附圖6所示，相應的狀態遷移處理過程為
當match_follow信號被主進程代入高電平，狀態機由IDLE狀態進入LIST_LOOP狀態，在此狀態下狀態機判斷編碼類型，同樣需要根據編碼類型進行不同的處理如果是字符串，則進入FOLLOW_STRING狀態，循環匹配單個字符；如果是單個字符編碼或者單個字符的range編碼，則直接判斷是否匹配；如果是字符編碼連接，則進入FOLLOW_CODE_LIST狀態，循環匹配單個字符；最後，根據匹配結果選擇進入狀態FOLLOW_SUCCESS或者回到LIST_LOOP匹配下一個列表內容，直到發現匹配的FOLLOW集合元素或者到達列表尾部；如果沒有發現匹配的FOLLOW元素，則狀態機進入FOLLOW_FAIL狀態；狀態機在FOLLOW_SUCCESS和FOLLOW_FAIL分別將follow_match_success和follow_match_fail代入高電平通知主狀態機；當主狀態機將match_follow置為低電平，則match_follow_proc狀態機回到IDLE狀態，清除match_follow_success或match_follow_fail信號，等待下一次匹配。
基於上述各狀態機，則可以利用可編程邏輯器件實現通用的ABNF文法解析器。
以上所述，僅為本發明較佳的具體實施方式
，但本發明的保護範圍並不局限於此，任何熟悉本技術領域的技術人員在本發明揭露的技術範圍內，可輕易想到的變化或替換，都應涵蓋在本發明的保護範圍之內。因此，本發明的保護範圍應該以權利要求的保護範圍為準。
權利要求
1.一種文本編碼類協議通用解析器，其特徵在於，包括規則存儲模塊、待解析消息存儲模塊和消息解析模塊，消息解析模塊根據規則存儲模塊中保存的規則信息對待解析消息存儲模塊中的消息文本進行解析處理，所述的消息解析模塊為採用邏輯晶片實現。
2.根據權利要求1所述的文本編碼類協議通用解析器，其特徵在於，所述的邏輯晶片包括現場可編程邏輯門列陣FPGA或複雜可編程邏輯器件CPLD。
3.根據權利要求1所述的文本編碼類協議通用解析器，其特徵在於，所述的規則存儲模塊為規則樹存儲模塊，規則樹存儲模塊中保存有基於擴展巴克斯範式ABNF方法定義的規則生成的規則樹。
4.根據權利要求3所述的文本編碼類協議通用解析器，其特徵在於，所述的規則樹為不包含增式選擇、序列組及可選序列結構的規則樹，且所述的規則樹為以各規則中的一個規則為頂點，採用遞歸的方式生成的規則樹。
5.根據權利要求1、2、3或4所述的文本編碼類協議通用解析器，其特徵在於，所述的消息解析模塊進一步包括主進程處理部分用於根據棧頂節點的類型控制分別進入解析終結符部分、匹配首終結符部分或匹配後繼終結符部分的處理過程；解析終結符部分用於當棧頂結點為終結節點時，由主進程處理部分控制啟動，並進行終結節點的終結符的解析處理，解析完成後通知主進程處理部分；匹配首終結符部分用於對當棧頂結點為非終結點時，且為首終結符集合時，由主進程處理部分控制啟動，並進行首終結符的匹配處理，判斷當前字符是否在節點首終結符集合內，匹配完成後通知主進程處理部分；匹配後繼終結符部分用於對當棧頂結點為非終結點時，且為後繼終結符集合時，由主進程處理部分控制啟動，並進行後繼終結符的匹配處理，判斷當前字符是否在節點後繼終結符集合內，匹配完成後通知主進程處理部分。
6.根據權利要求5所述的文本編碼類協議通用解析器，其特徵在於，所述的消息解析模塊採用狀態機實現。
7.根據權利要求6所述的文本編碼類協議通用解析器，其特徵在於，所述的主進程處理部分對應的狀態機包括循環解析PARSE_LOOP狀態，在該狀態下進行消息報文的解析；到達最大重複次數REPEAT_MAX狀態，在該狀態下判斷保存首規則樹節點的節點棧的棧頂節點的類型是否為終結節點；匹配終結符TERM_MATCH狀態，在該狀態下進行終結符的匹配處理張，並啟動解析終結符部分；進入首終結符集合判斷IN_FIRST狀態，在該狀態下進行首終結符集合的判斷處理，並在確定存在首終結符集合時，啟動匹配首終結符部分；所有的子節點已經處理ALLSUB狀態，當IN_FIRST狀態下所有的子節點處理完成時進入該狀態，且在該狀態下返回PARSE_LOOP狀態；後繼終結符集判斷JUDGE_FOLLOW狀態，在該狀態下進行後繼終結符集合的判斷處理，並在確定存在後繼終結符集合時，進入FOLLOW集合判斷IN_FOLLOW狀態，啟動匹配後繼終結符部分，如果不存在後繼終結符集合時進入下一規則NEXTRULE狀態，並返回PARSE_LOOP狀態的。
8.根據權利要求6所述的文本編碼類協議通用解析器，其特徵在於，所述的解析終結符部分的狀態機包括字符串類型終結符TERM_STRING狀態，在該狀態下對單個字符串循環進行單個字符的匹配處理；字符編碼連接類型終結符TERM_CODE_LIST狀態，在該狀態下對字符編碼連接循環進行單個字符的匹配處理；終結符匹配成功TERM_SUCCESS狀態和終結符匹配失敗TERM_FAIL狀態，在該狀態下通知主進程處理部分匹配處理結果。
9.根據權利要求6所述的文本編碼類協議通用解析器，其特徵在於，所述的匹配首終結符部分的狀態機包括列表循環處理LIST_LOOP狀態，在該狀態下判斷編碼類型為字符串字符編碼連接；字符串類型FIRST_STRING狀態，在該狀態下對單個字符串循環進行單個字符的匹配處理；字符編碼連接類型終結符FIRST_CODE_LIST狀態，在該狀態下對字符編碼連接循環進行單個字符的匹配處理；首終結符集合匹配成功FIRST_SUCCESS狀態和首終結符集合匹配失敗FIRST_FAIL狀態，在該狀態下通知主進程處理部分匹配處理結果。
10.根據權利要求6所述的文本編碼類協議通用解析器，其特徵在於，所述的匹配後繼終結符部分包括列表循環處理LIST_LOOP狀態，在該狀態下判斷編碼類型為字符串字符編碼連接；字符串類型FOLLOW_STRING狀態，在該狀態下對單個字符串循環進行單個字符的匹配處理；字符編碼連接類型FOLLOW_CODE_LIST狀態，在該狀態下對字符編碼連接循環進行單個字符的匹配處理；後繼終結符匹配成功FOLLOW_SUCCESS狀態和後繼終結符匹配失敗FOLLOW_FAIL狀態，在該狀態下通知主進程處理部分匹配處理結果。
全文摘要
本發明涉及一種文本編碼類協議通用解析器。本發明包括規則存儲模塊、待解析消息存儲模塊和消息解析模塊，消息解析模塊根據規則存儲模塊中保存的ABNF規則樹信息對待解析消息存儲模塊中的消息文本進行解析處理，所述消息解析模塊為基於FPGA(可編程邏輯晶片)實現。因此，本發明與軟體實現方式相比，解析效率大為提高，有利於提高產品效率，降低成本。同時，本發明為基於ABNF規則進行解析，使得本發明具有良好的通用性，可以適用於各種基於ABNF進行規則定義的場合，從而極大地降低了相應的解析器的開發成本，提高了開發效率。
文檔編號H04L29/06GK1809053SQ20051000178
公開日2006年7月26日 申請日期2005年1月21日 優先權日2005年1月21日
發明者趙寶華, 屈玉貴, 周顥, 田野, 王爍, 李奇越, 呂超, 靳志偉 申請人:華為技術有限公司, 中國科學技術大學