正規表現の角括弧記法の DFA

正規表現の角括弧で囲んだ文字集合要素リスト中に \d 等が使えると便利です。 \d 等が使える文字集合要素リストは NFA で簡潔に記述可能ですが、 これを DFA に変換してみました。 ただし、 DFA の状態数が増えすぎるので、 8 進数や 16 進数でのコード・ポイント表記と POSIX 文字クラス表記を除いてあります。 開始状態は S1 です。

この DFAC++11 にハードコードし、 懐古趣味行エディタ edit の正規表現コンパイラに組み込んでみました。 字句解析を担当する next_token メンバ関数を新設し、 その DFA に埋め込んでいます。 これで以前の版では扱いが適当だった \d-z のような誤った記述を検出してエラーを出せるようになりました。 新しい正規表現コンパイラには試験的に (?:exp)//x 修飾子を使えるようにしてあります。 前者は edit からも利用できますが、 後者は利用できません。

tociyuki/edit-cxx11: traditional line-oriented text editor.

# [^] は [\^] とみなす
# []] は [\]] とみなす
# [-] は [\-] とみなす
# [-a-z] は [\-a-z] とみなす
# [-a-z-] は [\-a-z\-] とみなす
# [a-z-] は [a-z\-] とみなす
# [-\d] は [\-0-9] とみなす
# [-\d-] は [\-0-9\-] とみなす
# [\d-] は [0-9\-] とみなす
# [%--] は [\%-\-] とみなす
# [\d-z] はエラー
# [a-\d] はエラー
# [a--z] はエラー
# [a-f-z] はエラー

S1 : '[' S2

S2 : '^' S3
   | '\\' S5
   | [ ] S4 | [^\^\\[:^graph:]] S4

S3 : ']' MATCH
   | '\\' S5
   | [ ] S4 | [^\^\][:^graph:]] S4

S4 : ']' MATCH
   | '\\' S5
   | '-' S6
   | [ ] S4 | [^\]\\\-[:^graph:]] S4

S5 : [dswDSW] S8
   | [ ] S4 | [^dswDSW[:^graph:]] S4

S6 : ']' MATCH
   | '\\' S7
   | '-' S9       # 2016-05-01 追加
   | [ ] S8 | [^\]\\\-[:^graph:]] S8

S7 : [ ] S8 | [^dswDSW[:^graph:]] S8

S8 : ']' MATCH
   | '\\' S5
   | '-' S9
   | [ ] S4 | [^\]\\\-[:^graph:]] S4

S9 : ']' MATCH