Open5

読者コミュニティ|論理演算可能な正規表現エンジンを作ろう

j5c8k6m8j5c8k6m8

本の感想や質問をお気軽にコメントしてください。

j5c8k6m8j5c8k6m8

執筆背景を少し記載。
deadcoad cookbookを執筆中に、文字列操作に対する汎用的な手法の啓発がしたくて、「論理演算可能な正規表現を求めて」という本を作成しながら、方式を探しはじめたのが、年明けすぐ。
もともとは、グループの繰返しを制限(対象外)として、全く別の方式で構想して着手(執筆もコーディングも本書の2倍以上は行っていた)。
しかし、テストを重ねると、どうしても否定演算が実現できず、半年近く経過。

6月に入ってから、本書の方式を思いつき、その正しさを問いたい思いもあり、思い付いてから約2日で実装、約2日で執筆して公開。
そのため、テストは一部不十分。
ちょうど、Zennにmermaid記法が導入されたのも、確認効率が上がり幸いした。

構想、実装、執筆を完全に1人で行ってるため、意見をいただけると大変嬉しいです。

κeenκeen

正規表現の積と否定は先読みと否定先読みを使えば可能ではないでしょうか。
例えば使用例で挙げられている (a+|ab)&!a はPerl正規表現で(全体マッチを考慮して ^$ を補って)^(?!^a$)(a+|ab)$ と書けます。

$ echo aa | grep -P '^(?!^a$)(a+|ab)$'
aa
$ echo a | grep -P '^(?!^a$)(a+|ab)$'

先読みは有限状態オートマトンへ変換できるので正規表現といえます。
参考: 先読み付き正規表現の有限状態オートマトンへの変換

なので

何故、今まで論理演算可能な正規表現に関する議論が活発に行われなかったのでしょうか?

に関しては既に議論されているし実装が世間に流通までしているが、分かりやすい形で知られていないのかくらいが妥当ではないかと思います。

j5c8k6m8j5c8k6m8

正規表現の積と否定は先読みと否定先読みを使えば可能

ありがとうございます。ご指摘の通りですね!
参考の文献の提示もありがとうございます。「正規表現エンジンを作ろう」記事では、先読み付きの有限状態オートマトンへ変換までの内容はないので、大変参考になります。

既に議論されているし実装が世間に流通までしているが、分かりやすい形で知られていないのかくらいが妥当ではないかと思います。

こちらも、その通りですね。
本書は結局、 全体マッチの正規表現を考えた時に、論理演算が可能な実装の一例を示した (あとは、文字列の集合として正規表現がもっと活用されててもいいのではないか?という個人の考え)

本書の記載も頂いた意見を参考に修正させていただきます。