正規表現
有限オートマトンにコンパイルして、その実行をエミュレートしてるわけではない
これでもできるが、先読み/後読みが実装しづらい
言語を有限の記述で指定する
ここで言う言語とは文字列(記号の有限な並び)の集合のこと
これらの文字列には意味は割り当てられていない、ただの分類のことを指している
言語の分類
記号 Symbol
一文字の記号
例: a
選択 Alternation
|で又はを表現
例: a|b
連接 Concatenation
連接演算子.を用いて複数の集合の組み合わせを表現する
$ M.N=\{mn|m\in M,n\in N\}
$ 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+と表現
曖昧さ排除規則の例
最長一致
優先規則
正規表現のC++実装
パターンをオートマトンにコンパイルすてる
Rubyの正規表現アルゴリズムの解説
正規表現からオートマトンの図を作成する
オートマトンの図の意味がわかる人ならわかりやすいmrsekut.icon
正規表現はクソ
参考
オライリーの正規表現本読むと良いかもなmrsekut.icon