[發明專利]一種狀態機

有效

• 申請號: 201210248224.5
• 申請日: 2012-07-17
• 公開（公告）號: CN103544142A
• 公開（公告）日: 2014-01-29
• 發明（設計）人: 李小明;胡勝發
• 申請（專利權）人: 安凱（廣州）微電子技術有限公司
• 主分類號: G06F17/27
• 分類號: G06F17/27
• 代理公司: 北京集佳知識產權代理有限公司 11227
• 代理人: 王寶筠

技術領域

本發明涉及計算機技術領域，特別涉及一種狀態機。

背景技術

詞法分析（lexical?analysis）是計算機語言學的基本功能之一，用于定義單詞的組成方法。進行語法分析的程序或者函數稱為詞法分析器（Lexical?analyzer，簡稱Lexer），也叫掃描器（Scanner）。詞法分析器一般以函數的形式存在，供語法分析器調用。

詞法分析的第一階段為識別所處理的單詞中包含的字符集，該過程通常基于狀態機。狀態機為描述單詞組成方法的圖形，狀態機由狀態點和轉換箭頭組成，表示在一定的輸入條件下，狀態轉換的過程。一個狀態機和一個正則表達式相對應。

現有的狀態機主要有非確定性有限狀態機和確定性有限狀態機兩種；其中非確定性有限狀態機為在一定的輸入條件下，狀態轉換不唯一的狀態機；確定性有限狀態機為在一定的輸入條件下，狀態轉換唯一的狀態機。

現有的狀態機所包含的狀態與狀態轉換一般有上百個，由于數量大，所以使狀態機的復雜性非常高，而狀態機的高復雜性導致了編程語言在微系統上的實現有一定困難，并且導致處理字符的速度緩慢。

發明內容

有鑒于此，本發明的目的在于提供一種狀態機，通過對字符的預分類將多種具有相同特征的字符統一為一個特征值，實現狀態數量的減少，提高狀態機的運行速度。

為實現上述目的，本發明有以下技術方案：

一種狀態機，其特征在于，所述狀態機包括：

規則模塊，用于預先制定待識別字符集的劃分規則，所述劃分規則包括劃分字符集所依據的特征；

編輯模塊，用于按照所述劃分規則中劃分字符集所依據的特征為狀態機編輯正則表達式；

預分類模塊，用于利用所述劃分規則對待識別字符集中的字符進行預分類；

狀態識別模塊，用于利用所述正則表達式識別經過劃分的待識別字符集。

所述規則模塊包括：

第一規則單元，用于以大寫字母、小寫字母、數字和下劃線作為劃分字符集所依據的特征制定待識別字符集的劃分規則。

所述規則模塊包括：

第二規則單元，用于以名詞、動詞、代詞、數量詞和標點符號作為劃分字符集所依據的特征制定待識別字符集的劃分規則。

所述規則模塊還包括：

特征值單元，用于為每個特征定義一個特征值。

所述預分類單元包括：

特征值輸出單元，用于判斷待識別字符集中的字符是否符合劃分規則中的任意一個特征，如果符合則輸出該特征的特征值。

通過以上技術方案可知，本發明存在的有益效果是，通過劃分規則將待識別字符集中的字符預分類，從而將幾十種甚至上百種字符根據特征簡化為有限的若干個種類，并且根據所述特征編輯出簡化的正則表達式，則該正則表達式對應的狀態機僅對小數量特征進行識別，從而實現狀態機的簡化，提高了狀態機運行的速度。

附圖說明

為了更清楚地說明本發明實施例或現有技術中的技術方案，下面將對實施例或現有技術描述中所需要使用的附圖作簡單地介紹，顯而易見地，下面描述中的附圖是本發明的一些實施例，對于本領域普通技術人員來講，在不付出創造性勞動的前提下，還可以根據這些附圖獲得其他的附圖。

圖1為本發明實施例所述狀態機結構示意圖；

圖2為本發明另一實施例所述狀態機結構示意圖；

圖3為本發明所述字符預分類流程圖。

具體實施方式

為使本發明實施例的目的、技術方案和優點更加清楚，下面將結合本發明實施例中的附圖，對本發明實施例中的技術方案進行清楚、完整地描述，顯然，所描述的實施例是本發明一部分實施例，而不是全部的實施例。基于本發明中的實施例，本領域普通技術人員在沒有做出創造性勞動前提下所獲得的所有其他實施例，都屬于本發明保護的范圍。

本發明公開了一種狀態機，參照圖1所示，所述狀態機具體為：

規則模塊，用于預先制定待識別字符集的劃分規則，所述劃分規則包括劃分字符集所依據的特征；

編輯模塊，用于按照所述劃分規則中劃分字符集所依據的特征為狀態機編輯正則表達式；

預分類模塊，用于利用所述劃分規則對待識別字符集中的字符進行預分類；

狀態識別模塊，用于利用所述正則表達式識別經過劃分的待識別字符集。