正規表現のはなし / regex theory

※ Docswell に移行しました
https://www.docswell.com/s/usami-k/Z389Q2-regex-theory

Transcript

1. 正規表現のはなし 宇佐見公輔 第25回日曜数学会（2022年10月15日）
2. 自己紹介 宇佐見公輔（うさみこうすけ） 職業：プログラマ 趣味：数学 近況 第3回すうがく徒のつどい：講演（4月） iOSDC Japan 2022：登壇、技術記事執筆（6〜9月） 技術書典13：技術同人誌執筆（8〜9月） 正規表現のはなし / 宇佐見公輔 / 第25回日曜数学会 2
3. 正規表現とは プログラミング言語で、文字列の検索（パターンマッチ）に使われる汎用的な文法。 テキストエディターなど各種ツールでの文字列検索機能でもよく使われる。 正規表現のはなし / 宇佐見公輔 / 第25回日曜数学会 3
4. 正規表現の記法 「 a 」は a にマッチ、「 b 」は b にマッチ 「 (a|b) 」は a または b にマッチ 「 [a-z] 」は a 〜 z のどれでもマッチ 「 . 」は任意の1文字にマッチ 「 a* 」は任意個の a からなる文字列にマッチ（空文字列、 a 、 aa 、、） 「 a+ 」は1個以上の a からなる文字列にマッチ（ a 、 aa 、 aaa 、、） 「 (a|b)* 」は aaa 、 abab 、 baab 、 bbbbb 、などにマッチ 「 .* 」は任意個の文字からなる文字列にマッチ 正規表現のはなし / 宇佐見公輔 / 第25回日曜数学会 4
5. 正規表現の基本三演算 正規表現は次の3つの演算で生成される。 連接：正規表現 と に対して、それを並べた 選択：正規表現 と に対して、そのどちらかにマッチする 繰り返し：正規表現 に対して、その任意個の繰り返し 例： 「 a+ 」は「 aa* 」と書ける 「 [a-z] 」は「 (a|b|c|...|z) 」と書ける 「 . 」はすべての文字の選択で書ける（※文字集合は有限集合） 正規表現のはなし / 宇佐見公輔 / 第25回日曜数学会 5
6. 余談：正規表現という言葉 正規表現は「regular expression」の訳だが・・・。 「regular」 一般に「regular」は「正則」と訳されることが多そう そもそも「regular」という言葉が妥当かどうか？ 「expression」 一般に「expression」は「式」と訳されることが多そう 「表現」と言われると「representation」を連想するかも？ 正規表現のはなし / 宇佐見公輔 / 第25回日曜数学会 6
7. 正規表現と集合 正規表現そのものを直接考える代わりに、集合で考える。 正規表現 にマッチする文字列の集合を の受理文字列集合と呼び、 と書く。 例： ある文字列が正規表現 にマッチするかという問題が、集合 の元かという問題 になる。 正規表現のはなし / 宇佐見公輔 / 第25回日曜数学会 7
8. 正規言語 文字列集合を定式化しておく（形式言語理論）。 ：文字集合（有限集合とする） ：文字列（＝ の元を有限個並べたもの）全体の集合 長さ の文字列を と書くことにする（空文字列） とする たとえば、 のとき の部分集合 を言語と呼ぶ 言語 がある正規表現 の受理文字列集合 と一致するとき、 を正規言語 と呼ぶ 正規表現のはなし / 宇佐見公輔 / 第25回日曜数学会 8
9. 正規言語の定式化 正規表現を使わずに正規言語を定義することができる。 空集合 は正規言語、空文字列のみの集合 は正規言語 について は正規言語 と が正規言語ならば、選択 は正規言語 と が正規言語ならば、連接 は正規言語 が正規言語ならば、Kleene閉包 は正規言語 これらの条件にあらわれない言語は正規言語ではない ※Kleene閉包 は、 の元を重複を許して有限個取り出して連接した文字列の全体 からなる集合。 正規表現のはなし / 宇佐見公輔 / 第25回日曜数学会 9
10. 正規言語の代数構造 選択の結合法則 選択の交換法則 選択の単位元 連接の結合法則 連接の単位元 零元 分配法則 、 正規表現のはなし / 宇佐見公輔 / 第25回日曜数学会 10
11. 正規性の判定 上の言語 があるとき、 上の同値関係 を次で定義する。 Myhill-Nerodeの定理 上の言語 が正規言語であることと、商集合 が有限集合であることは 同値。 これを言語の正規性の判定に使うことができる。また、より条件が緩いポンピング補 題を正規性の判定に使うことができる。 正規表現のはなし / 宇佐見公輔 / 第25回日曜数学会 11
12. より進んだ話題 有限オートマトン 正規表現マッチングの計算モデルとして、有限オートマトンがある 正規表現と決定性有限オートマトンは等価 正規性の利点 最適化問題が決定問題であり、そのアルゴリズムの方法論も確立されている 非正規な正規表現 プログラミングで使われている正規表現のうち後方参照や再帰の記法は、実 は正規ではない 形式言語理論 形式言語の理論は、正規表現以外にもさまざまな応用がある 正規表現のはなし / 宇佐見公輔 / 第25回日曜数学会 12
13. 参考文献 ※右端はiOSDC Japan 2022のセッション 正規表現のはなし / 宇佐見公輔 / 第25回日曜数学会 13