有限自動機を用いた正規表現の解析
5037 ワード
任意に転載することができますが、転載する時は元の作者charlee、元のリンクhttp://tech.idv2.com/2006/05/08/parse-regex-with-DFA/及び本声明を明記しなければなりません.
プログラムコンパイルの第一段階は語法分析であり、バイトストリームを記号ストリームとして認識し、次のステップの構文解析プロセスに提供する.記号を識別する方法は正規表現の分析です.この論文では,有限な自動動機を用いて式を解析する方法を紹介した. 概念 正規表現をNFAに変換する（Thompson構造法） アルゴリズム 性質 例 NFFAをDFAに変換する アルゴリズム 例 NFAとDFAの効率 概念
記号
アルファベットの記号で構成される有限長のシーケンスがあります.記号sの
長さは
124 s 124.長さが0の記号を「0」といいます.
空マーク
ε.
有限自動機(Finite State Automaton)
ある計算過程を研究するために抽象的に出た計算モデル.有限の状態を持ち、異なる入力の各状態に応じて他の状態に移動することができます.
非確定有限自動機(Nondetterministic Finite Automaton)
略称
NFAは、以下の要素から構成されています.
1.有限状態集合
S;
2.限られた入力記号のアルファベット
Σ;
3.状態遷移関数
move;
4.開始状態
sSUB｛0｝
5.終了状態集合
F
F∈S
自動機の初期状態は
sSUB｛0｝は、入力文字列の各文字を一つ一つ読み込んで、現在の状態、読み込んでいる文字に基づいて、状態遷移関数により
move制御は次の状態に入ります.文字列読み込みが終了したら自動機の状態が終了状態セットになります.
Fは、この自動機が文字列を受け入れていることを示しています.そうでないと受け入れられません.
有限自動機(Deterministic Finite Automaton)を確定する.
略称
DFAは、NFAの特例であり、以下の2つの制限がある.
1.空入力について
ε,状態が遷移しない.
2.ある状態は各入力に対して最大1つの状態だけ遷移します.
正規表現をNFAに変換する(Thompson構造法)
アルゴリズム
アルゴリズム1は正則表現をNFAに変換します.
アルファベットを入力Σ上の正規表現r
出力はL(r)のNFA Nを受け入れることができます.
方法は、まず、rを構成する各要素を分解し、各要素について、以下の規則1と規則2に従ってNFAを生成する.注意:r中マークaが何度も出現すると、aに対しては毎回単独のNFAを生成する必要がある.
その後、正規表現rの文法規則に従い、生成されたNFAを下記規則3に従って組み合わせます.
ルール1対空記号ε,次のNFAを生成します.
ルール2についてΣのアルファベットの要素aは、次のNFAを生成する.
規則3は、正規表現sとtのNFAをそれぞれN(s)とN(t)とする.
a)s 124 tについては、以下のようにNFA N(s 124 t)が生成される.
b)stについては、以下のようにNFA N(st)が生成される.
c)s＊に対して、以下のようにNFA N(s*)を生成する.
d)(s)に対しては、s自体のNFA N(s)を使用する.
性質
アルゴリズム1によって生成されたNFAは、正規表現を正しく識別し、次のような性質を有する. N(r)の状態数は、rに現れる記号と演算子の個数の最大2倍である. N(r)の開始状態と終了状態はあり、一つしかない. N(r)の各状態は、Σの中の一つの記号、または一つの状態を持って移動するか、最大二つの記号を持っています.ε移る 例
アルゴリズム1を用いて、正規表現r=(a 124 b)*abbに基づいて、以下のNFAを生成することができる.
NFFAをDFAに変換する
アルゴリズム
以下のアルゴリズムを用いてNFAを等価DFAに変換することができる.
アルゴリズム2はNFAをDFAに変換する.
入力NFA N
出力はNと同じ言語のDFA Dを受け入れることができます.
方法本アルゴリズムはDに対応する状態遷移表Dtranを生成する.DFAの各状態はNFAの状態セットであり、各入力記号に対してDシミュレーションNにおいて可能な状態遷移がある.
以下の操作を定義します.
操作
説明
ε-クロージング(s)
NFAの状態sからは、通過のみε到達可能なNFAの状態セットを移動します.
ε-クロージング(T)
Tに含まれるあるNFAの状態sから出発して、ε到達可能なNFAの状態セットを移動します.
move(T,a)
Tに含まれるあるNFAの状態sから、記号aを入力することで到達可能なNFAの状態セットを遷移する.
上で生成したNFAをDFAに変換する.
最初はDstates内しかありませんでした.ε-クロージング(0)=A={0,1,2,4,7}そして、状態Aに対して、記号aを入力し、計算する.ε-クロージング(move(A,a)＝ε-closure(move({0,1,2,4,7},a)=ε-closure({3,8}={1,2,3,4,6,7,8}、つまりB={1,2,3,4,6,7,8}、Dtran[A,a]=Bです.状態Aについては、入力記号bで到達できるのは4->>5だけであるため、C=ε-closure({5}={1,2,4,5,6,7}、つまりDtran[A,b]=Cです.
これを類推すると、以下の状態とDtranが得られます.
記号を入力
a.
b
A
B
C
B
B
D
C
B
C
D
B
E
E
B
C
これにより、DFAは下図のようになる.
NFAとDFAの効率
正規表現rと入力記号シーケンスxを指定し、rがxを受け入れるかどうかを判断する.
NFAを使用した場合、正規表現からNFAを生成する時間複雑度はOであり、またNFAの状態数はrの2倍が最も多いため、空間複雑度はOである.NFAがxを受け入れるかどうかを判断すると、時間複雑度はO(124 r 124)である.×|x|したがって、全体的に処理時間はr,xの長さの積に比例する.この処理方法はxがあまり長くない時に非常に効果的である.
DFAを使用すると、xが受け入れられているかどうかは状態数に関係ないとDFAで判断されるので、時間複雑度はOである.しかしDFAの状態数は正規表現の長さと指数関数的な関係を示している.例えば、正規表現(a 124 b)＊a(a 124 b)…(a 124 b)、末尾にn−1個(a−b)があると、DFA最小状態数も2 SUP｛n｝を超える.
プログラムコンパイルの第一段階は語法分析であり、バイトストリームを記号ストリームとして認識し、次のステップの構文解析プロセスに提供する.記号を識別する方法は正規表現の分析です.この論文では,有限な自動動機を用いて式を解析する方法を紹介した.
記号
アルファベットの記号で構成される有限長のシーケンスがあります.記号sの
長さは
124 s 124.長さが0の記号を「0」といいます.
空マーク
ε.
有限自動機(Finite State Automaton)
ある計算過程を研究するために抽象的に出た計算モデル.有限の状態を持ち、異なる入力の各状態に応じて他の状態に移動することができます.
非確定有限自動機(Nondetterministic Finite Automaton)
略称
NFAは、以下の要素から構成されています.
1.有限状態集合
S;
2.限られた入力記号のアルファベット
Σ;
3.状態遷移関数
move;
4.開始状態
sSUB｛0｝
5.終了状態集合
F
F∈S
自動機の初期状態は
sSUB｛0｝は、入力文字列の各文字を一つ一つ読み込んで、現在の状態、読み込んでいる文字に基づいて、状態遷移関数により
move制御は次の状態に入ります.文字列読み込みが終了したら自動機の状態が終了状態セットになります.
Fは、この自動機が文字列を受け入れていることを示しています.そうでないと受け入れられません.
有限自動機(Deterministic Finite Automaton)を確定する.
略称
DFAは、NFAの特例であり、以下の2つの制限がある.
1.空入力について
ε,状態が遷移しない.
2.ある状態は各入力に対して最大1つの状態だけ遷移します.
正規表現をNFAに変換する(Thompson構造法)
アルゴリズム
アルゴリズム1は正則表現をNFAに変換します.
アルファベットを入力Σ上の正規表現r
出力はL(r)のNFA Nを受け入れることができます.
方法は、まず、rを構成する各要素を分解し、各要素について、以下の規則1と規則2に従ってNFAを生成する.注意:r中マークaが何度も出現すると、aに対しては毎回単独のNFAを生成する必要がある.
その後、正規表現rの文法規則に従い、生成されたNFAを下記規則3に従って組み合わせます.
ルール1対空記号ε,次のNFAを生成します.
ルール2についてΣのアルファベットの要素aは、次のNFAを生成する.
規則3は、正規表現sとtのNFAをそれぞれN(s)とN(t)とする.
a)s 124 tについては、以下のようにNFA N(s 124 t)が生成される.
b)stについては、以下のようにNFA N(st)が生成される.
c)s＊に対して、以下のようにNFA N(s*)を生成する.
d)(s)に対しては、s自体のNFA N(s)を使用する.
性質
アルゴリズム1によって生成されたNFAは、正規表現を正しく識別し、次のような性質を有する.
アルゴリズム1を用いて、正規表現r=(a 124 b)*abbに基づいて、以下のNFAを生成することができる.
NFFAをDFAに変換する
アルゴリズム
以下のアルゴリズムを用いてNFAを等価DFAに変換することができる.
アルゴリズム2はNFAをDFAに変換する.
入力NFA N
出力はNと同じ言語のDFA Dを受け入れることができます.
方法本アルゴリズムはDに対応する状態遷移表Dtranを生成する.DFAの各状態はNFAの状態セットであり、各入力記号に対してDシミュレーションNにおいて可能な状態遷移がある.
以下の操作を定義します.
操作
説明
ε-クロージング(s)
NFAの状態sからは、通過のみε到達可能なNFAの状態セットを移動します.
ε-クロージング(T)
Tに含まれるあるNFAの状態sから出発して、ε到達可能なNFAの状態セットを移動します.
move(T,a)
Tに含まれるあるNFAの状態sから、記号aを入力することで到達可能なNFAの状態セットを遷移する.
Dstates ε-closure(s), ;
while Dstates T do
begin
T;
for a do
begin
U := ε-closure(move(T, a));
if U Dstates then
U Dstates ， ;
Dtrans[T, a] := U;
end
end T ;
ε-closure(T) T;
while do
begin
t;
for t ε u do
if u ε-closure(T) then
begin
u ε-closure(T) ;
u ;
end
end上で生成したNFAをDFAに変換する.
最初はDstates内しかありませんでした.ε-クロージング(0)=A={0,1,2,4,7}そして、状態Aに対して、記号aを入力し、計算する.ε-クロージング(move(A,a)＝ε-closure(move({0,1,2,4,7},a)=ε-closure({3,8}={1,2,3,4,6,7,8}、つまりB={1,2,3,4,6,7,8}、Dtran[A,a]=Bです.状態Aについては、入力記号bで到達できるのは4->>5だけであるため、C=ε-closure({5}={1,2,4,5,6,7}、つまりDtran[A,b]=Cです.
これを類推すると、以下の状態とDtranが得られます.
A = {0, 1, 2, 4, 7} D = {1, 2, 4, 5, 6, 7, 9}
B = {1, 2, 3, 4, 6, 7, 8} E = {1, 2, 4, 5, 6, 7, 10}
C = {1, 2, 4, 5, 6, 7}記号を入力
a.
b
A
B
C
B
B
D
C
B
C
D
B
E
E
B
C
これにより、DFAは下図のようになる.
NFAとDFAの効率
正規表現rと入力記号シーケンスxを指定し、rがxを受け入れるかどうかを判断する.
NFAを使用した場合、正規表現からNFAを生成する時間複雑度はOであり、またNFAの状態数はrの2倍が最も多いため、空間複雑度はOである.NFAがxを受け入れるかどうかを判断すると、時間複雑度はO(124 r 124)である.×|x|したがって、全体的に処理時間はr,xの長さの積に比例する.この処理方法はxがあまり長くない時に非常に効果的である.
DFAを使用すると、xが受け入れられているかどうかは状態数に関係ないとDFAで判断されるので、時間複雑度はOである.しかしDFAの状態数は正規表現の長さと指数関数的な関係を示している.例えば、正規表現(a 124 b)＊a(a 124 b)…(a 124 b)、末尾にn−1個(a−b)があると、DFA最小状態数も2 SUP｛n｝を超える.