■
NFA、DFAを勉強したので以下の定義を満たす最小構成(＋α）の正規表現をコーディングしてみようかと思う
アルファベットA上の正規表現とは以下の以下の規則によって作られる 表現の事である (1) ε(空記号列)は正規表現である (2) Aの要素a (a⊆A)は正規表現である (3) RとSが正規表現ならば R|S (union), RS (concat), R* (closure) も正規表現である。 (4) R+を簡易記法として以下のように定める R+ ::= RR*
コーディングは以下のような順に行う。
※まだ勉強中なので本も再度読みながら
文法考察フェーズ 1．正規表現の文法を考える 2. 1の文法が構文解析した時にあいまい（解析木が複数通りある）で無い事を確かめるため、LL(1)文法を満たしているかを考察する コーディングフェーズ 3. １の文法に従って解析木（構文木）を作成する 4. 3の構文木からNFAを作成する 5. 4のNFAからDFAを作成する 6. 5のDFAの状態数を最小化する 7. DFAのパターンマッチ処理を書く
