正規表現はPerlや多くの言語で重要な機能です。
しかし、正規表現は独特の文法から、自分の手で書くのは煩わしいです。
生成AIに書かせることもできますが、本当に期待しているものになっているのかという保証がありませんし、ReDoSなどの脆弱性を生んでしまう可能性もあります。

「正規表現をつくる」プログラム

そこで、「マッチしてほしい文字列」と「マッチしてほしくない文字列」を与えたら自動で、*や+を使ったいい感じの正規表現を作ってくれるプログラムがあったら便利だと思いませんか？
今回は、そういった「正規表現をつくる」プログラムについて話します。

オートマトンと正規表現のはざまで

「正規表現をつくる」プログラムといえば、PerlにはRegexp::Assembleがあります。
ですが、Regexp::Assembleでは単にマッチしてほしい文字列を|でつないだ正規表現のようなものが出てくるだけで、*や+を使った期待する正規表現にはなりません。

期待する正規表現についてはオートマトンを使うことで定義できます。
一方、オートマトンから人間の読みやすい正規表現を得ることは簡単ではありません。
この問題の解決ために、SATソルバなどを使って解決を試みます。

むすびに

この発表では、次のような内容を話します。

• 「正規表現をつくる」問題について
  • いい感じの正規表現とは何か？
• オートマトンの場合の解決方法
  • 受動的オートマトン学習
  • RPNIアルゴリズム
• 正規表現として求めるには？
  • 正規表現への変換の困難さ
  • SATソルバを使った探索

「正規表現をつくる」問題を、理論的な方法を用いながらも現実的に対処していくトークにご期待ください。