正規表現エンジンメモ

はじめに

正規表現とそのエンジンについてちょっとメモ。

正規表現とは

有限オートマトン
  • 以下の5つの組(Q,Σ,δ,q0,F)のことをいう
    • 有限状態機械ともいう
  • 有限個の状態Q
  • 有限個の文字集合Σ
  • 状態と文字集合の組から状態へ遷移する関数δ
  • 状態Qの一つとして、開始状態q0
  • 状態Qの一つとして、受理状態の集合F
  • 入力に対して、開始状態から状態を遷移させ、状態に応じて出力(受理or拒否)を返す
  • 状態遷移図とは、有限オートマトンを(抽象的に)記述した図
非決定性(Nondeterministic)と決定性(Deterministic)
  • DFAとNFAは「等価」なので、NFAからDFAへの変換ができる
    • NFAの状態の冪集合の各要素を状態としてもつDFAに変換する「冪集合構築」で変換可能

正規表現エンジンとは

正規表現エンジンの種類
DFAとNFAによる実装の違い
  • 理論的にはDFAとNFAは等価だが、拡張(非正規的に)するとNFAは多くの機能を実現できる(DFAではサポートできない)
    • 後方参照、マッチ後参照
    • ゼロ幅マッチ
    • 最小量指定子、早い者勝ち選択
    • 絶対最大量指定子、アトミックグループ
  • DFAエンジン
    • 決定論的なので状態遷移は文字に対して1つしかないため、順次処理される
    • 処理が高速
  • NFAエンジン
    • 状態からの複数の遷移があり得るので、バックトラックにより処理される
    • コンパイルした内部状態は一般にDFAに比べ、高速でメモリ消費も少ない
    • DFAではサポートできない上記のような機能をサポートできる
  • ハイブリットエンジン
    • 基本的にDFAで、ある機能のときだけNFAにする、など必要に応じてエンジンの切り替えを行うもの、など

正規表現エンジンライブラリ

いろんなライブラリが公開されているが、C++はよく使う気がするので、C++で使えるライブラリでちょっとメモ

参考文献