任意の正規表現はそれと等価の非決定性有限オートマトンに変換できる

ただし、大抵の正規表現ライブラリはある種のバックトラッキングアルゴリズムを使っている

有限オートマトンにコンパイルして、その実行をエミュレートしてるわけではない

これでもできるが、先読み/後読みが実装しづらい

言語を有限の記述で指定する

ここで言う言語とは文字列(記号の有限な並び)の集合のこと

これらの文字列には意味は割り当てられていない、ただの分類のことを指している

言語の分類

記号 Symbol

一文字の記号

例: a

選択 Alternation

| で又はを表現

例: a|b

連接 Concatenation

連接演算子 . を用いて複数の集合の組み合わせを表現する

M,Nは言語

m,nは文字列

例: M=\{xy,pq\}, N=\{a,b,c\}とすると、M.N=\{xya,xyb,xyc,pqa,pqb,pqc\}

イプシロン Epsilon

空文字だけを含む言語

例: (a.b)|ε は、言語\{\epsilon,"ab"\}のこと

反復 Repetition

正規表現Mが与えられたとき、M^*のことをクリーネ閉包という

M^*にはM中の0個以上の文字列の連接からなる文字列が含まれる

例

((a|b).a)* は無限集合で、\{\epsilon,"aa","ba","aaaa","baaa","aaba","baba",...\}

省略記法

連接記号やεの省略

(a|b|c|d) を [abcd] と表現

- を用いて [a-z] などと表現

(M|ε) を M? と表現

(M.M*) を M+ と表現

曖昧さ排除規則の例

最長一致

優先規則

Russ Cox作

正規表現のC++実装

パターンをオートマトンにコンパイルすてる

Pat Shaughnessy著

Rubyの正規表現アルゴリズムの解説

正規表現からオートマトンの図を作成する

オートマトンの図の意味がわかる人ならわかりやすい

正規表現はクソ

参考

オライリーの正規表現本読むと良いかもな

正規表現と半群