正規表現

正規表現 前のドキュメント ＶｉＶｉの正規表現処理について説明する。 ■ 有限オートマトン チョムスキーの言語理論によれば、形式文法はクラス０～３に分類できる。正規表現は生成規則の制約が最も強いクラス３に属し、入力文字列が与えられた正規表現として受理されるかどうかを有限オートマトンにより決定することが出来る。 有限オートマトンとは下図の様に（有限の）状態と、入力文字によりどの状態に遷移するかの規則により構成されるものである。 'a' 'b' ○────→○────→◎ q0 q1 q2 上図では３つの状態、q0, q1, q2 があり、'a' が入力されると状態 q0 から q1 に遷移し、'b' が入力されると q1 から q2 に遷移することを表す。q2 は受理状態なので、"ab" が入力文字列であれば、めでたく受理されることになる。 正規表現を有限オートマトン

[sou3ilow]

NFAで直接マッチング

[cnomiya]

正規表現と有限オートマトン

[ihag]

Viviでの正規表現エンジンの実装の解説。バックトラックを用いないNFAエンジンの実装

[r-west]

文法理論

[yupo5656]

NFAをバックトラックなしで実行して、部分参照(capture)を実現する方法の説明。すばらしい。regex