Regular Expression(正規表現) Part17

**デフォルトの名無しさん** · 2025/11/02(日) 20:01:30.27

正規表現の枠を超える後方参照（\1）とかで使ってそう
あれが絡むと事前にDFA作れない

**デフォルトの名無しさん** · 2025/11/02(日) 20:13:48.87

正則言語の枠か
用語がちょっと怪しい

**デフォルトの名無しさん** · 2025/11/03(月) 19:15:39.49

>>280
自己レス。AI に聞いたら

| GNU grepでは、DFA の生成に On-the-Fly（実行時逐次的）な手法を採用していますが、
| それは基本的に部分集合構成法を逐次的に行うことを意味します。
| ε遷移の除去も、このプロセスの中で実質的に On-the-Fly で行われます。

とのことでした。やっぱε-除去も On-the-Fly なのか、ムズいなー

>>281
GNU grep の On-the-Fly 法は、到達しない状態ノードを作らないようにすることで
省メモリ化と高速化が目的なので、DFA の構造自体が動的に変わるものではないと思ってました。

で、言われるように後方参照は正規言語のクラスを超えてるので、DFA 型エンジンでは
普通は実現出来ないのだけど、「正規表現技術入門」では

| GNU grep は基本的に DFA 型ですが、部分的（後方参照への対応のためなど）に一部
| VM 型のアプローチもとっています。

とかさらっと書いてあるだけで、具体的な記述はないんすよね (やっぱ入門書だな)。

でも言われてみれば、On-the-Fly 的に動的に DFA を構成して行けば、それで後方参照も
実現出来そうな気がしてきた。バックトラックとか面倒そうだけど一考の価値はあるかも

GNU grep もそうやって実装してる ? かどうかは分からないけど

**デフォルトの名無しさん** · 2025/11/05(水) 01:01:25.63

それわかったらなんか良いことあるの（クルクルパー

**デフォルトの名無しさん** · 2025/11/07(金) 00:31:17.29

NFA使わずに正規表現から直接DFAを構成する方法がDragon Bookに書いてあるけど
この書籍は今もDragon Bookで通じるのかな
もう古文書扱いされてそう

**デフォルトの名無しさん** · 2025/11/07(金) 17:38:51.77

>>285
情報ありがとうございます
やはりドラゴンブックは読まざるを得ない感じですかね
読んでみます (気は重いけどｗ)

**デフォルトの名無しさん** · 2025/11/07(金) 18:36:08.56

Dragon Bookでpdf検索すると大学のサイトとかで英語版が引っ掛かるけど旧版はセーフなのかな
DFAの構成法は第2版だと3.9節
少なくとも3章は最初から読んだ方がいいと思う
コンパイラに興味ないなら全部読む必要はない

**デフォルトの名無しさん** · 2025/11/07(金) 19:00:36.04

そういえば正規表現自体の解析で4章前半のTop-Down Parsingくらいまでは役に立つかも

**デフォルトの名無しさん** · 2025/11/07(金) 20:27:12.90

>>287
ありがとうございます。旧版 (日本語訳) はⅠ、Ⅱ共にさっき中古をポチりました
届くのは来週末だけど、図書館に第二版があるようなので明日行ってきます
コンパイラに興味ない、とまでは言わないけど、果たしてそこまで手を広げられるものなのか心許ないす

**デフォルトの名無しさん** · 2025/11/11(火) 08:03:53.83

こういう方に最新版をポンと出す制度にならんもんかな

**デフォルトの名無しさん** · 2025/11/11(火) 14:34:01.30

複数の正規表現を使い分けられる記法があるといい

**デフォルトの名無しさん** · 2025/11/20(木) 00:34:25.20

DragonBook (第2版) の第3章まで読んだら、>>280 に書いた ε-遷移についての最初の疑問も氷解してしまったので、
一応伏線回収しておきます

「正規表現技術入門」では、ε-遷移を除去した後で部分集合構成法を行う、という流れで記述されていたので、
部分集合構成法を行うには前もって ε-遷移を除去しなければならない、と思い込んでいたのだけど、
その必要は全くなかったのでした

部分集合構成法の処理の中で一つ部分集合が得られたら、その集合の ε-閉包を取って
(その集合にそこから ε-遷移する状態を全て加えて)、それを DFA の 1 状態とすればよいだけなのでした

>>283 に書いた AI の回答が何となく歯切れが悪かった理由もこれで納得出来たわけで、
何でこんな簡単なことを思い付かなかったのか、我ながらアホでしたね

「正規表現技術入門」は章ごとに執筆者が違っていて、VM 型エンジンの章は鬼雲の作者が直々に書いていて説得力があるのですが、
DFA 型エンジンの章、とくにこの ε-遷移あたりの記述は今一つな感じです (エラそうに言ってますが)

--
ところで DragonBook 3.9 節の「正規表現から直接 DFA を導くやり方」も読みました
シンプソン構成法を経由せず、構文木から DFA を導くのはスゲーと思ったのですが
followpos() の張るダイアグラムは一種の NFA 的なものなので、それを DFA に変換する時には
やはり部分集合構成法と同じ手法を使うわけですね
とは言え ε-遷移が存在しないので扱う状態数もずっと少なくて済むはずなので、
これを使って On-the-Fly 法を実装して行きたいと思ってます

何にせよ、DragonBook を読めと言ってくれた >>285 さんには感謝しかないです
ありがとうございました

**デフォルトの名無しさん** · 2025/11/20(木) 01:53:23.80

●Regular Expressionの使用環境
　Java1.5
●検索か置換か？
　検索
●説明
　http://とhttps://があるもしくはない場合のドメインとサブドメインを検索したい
　自分で考えた以下の正規表現だと、.から始まる不正なURLまで一致してしまいダメでした
^(https?://)?(.*\.)?doubleclick.net
●対象データ
#一致させたいものは以下
http://doubleclick.net/pagead/
https://doubleclick.net/pagead/
http://g.doubleclick.net/pagead/
https://g.doubleclick.net/pagead/
http://googleads.g.doubleclick.net/pagead/
https://googleads.g.doubleclick.net/pagead/
doubleclick.net/pagead/
g.doubleclick.net/pagead/
googleads.g.doubleclick.net/pagead/

#一致させたくないものは以下
http://.doubleclick.net/pagead/
https://.doubleclick.net/pagead/
http://.g.doubleclick.net/pagead/
https://.g.doubleclick.net/pagead/
http://.a.g.doubleclick.net/pagead/
https://.a.g.doubleclick.net/pagead/
.doubleclick.net/pagead/
.g.doubleclick.net/pagead/
0doubleclick.net/pagead/
http://0doubleclick.net/pagead/
https://0doubleclick.net/pagead/

**デフォルトの名無しさん** · 2025/11/20(木) 09:40:15.39

その処理系で文字クラスが使えるなら (.*\.)? を ([^.0].*\.)? とすればイケるハズ

**293** · 2025/11/20(木) 15:17:38.43

>>294
レスありがとうございます
以下の2行は一致しなくなりましたが、
.doubleclick.net/pagead/
.g.doubleclick.net/pagead/

以下の6行は一致してしまいました
http://.doubleclick.net/pagead/
https://.doubleclick.net/pagead/
http://.g.doubleclick.net/pagead/
https://.g.doubleclick.net/pagead/
http://.a.g.doubleclick.net/pagead/
https://.a.g.doubleclick.net/pagead/

**デフォルトの名無しさん** · 2025/11/20(木) 16:30:51.92

"doubleclick.net"は決め打ちでいいのかな

Pattern p = Pattern.compile("^(?:https?://)?((?:[^./?#]+\\.)*doubleclick\\.net)(?=[:/]|$)");

マッチした後の処理は分からんけど動作例
https://ideone.com/3WFyH6

**293** · 2025/11/20(木) 21:15:50.67

>>296
レスありがとうございます
せっかく教えていただいたのにすみません、JavaではなくてJavaScriptでしたので動作しませんでした

チェッカー
https://www-creators.com/tool/regex-checker

**デフォルトの名無しさん** · 2025/11/20(木) 21:32:25.61

今時分にJava1.5でおかしいと思ったけどスルーしてしまった
文字列でエスケープしてる\\を\に直せば使えるはず
ついでに?と#を先読みに追加した（多分いらない）

^(?:https?://)?((?:[^./?#]+\.)*doubleclick\.net)(?=[:/?#]|$)

**293** · 2025/11/20(木) 21:52:35.87

>>298
度々ありがとうございます
完璧に動作しました！
助かりました

未だに先読みと後読みが使いこなせず・・・詰んでました

**デフォルトの名無しさん** · 2025/11/20(木) 23:34:16.70

>>292
シンプソン構成法じゃなくてトンプソン構成法でした。すまそん
尊敬する Ken Thompson の名前を間違えるとはヤバ過ぎ

**デフォルトの名無しさん** · 2025/11/22(土) 12:38:05.41

黄色くなりそう

**デフォルトの名無しさん** · 2025/12/03(水) 23:55:16.13

よろしくお願いします

●Regular Expressionの使用環境
　サクラエディタ32bit Ver2.4.2.6048（bregoing.dll Ver.4.20 with Onigmo 6.2.0）

●検索か置換か？
　検索

●説明
　1行に複数ある□=■■■;の■■■;（セミコロンも含む）部分を抽出したいです
　※フォントに色付けしたいため

●対象データの1行に対して他の色付けの正規表現も使っています
　　１．txt部分の着色用正規表現　/^(a|mx|cname|srv|txt|@|www)/k
　　２．_dmarc.example.com部分の着色用正規表現　/(?<=^a |mx |cname |srv |txt )(\S)+\s/k
　
●対象データ
txt _dmarc.example.com v=DMARC1; p=reject; rua=mailto:dmarc_rua@example.com; ruf=mailto:dmarc_ruf@example.com; fo=1; adkim=s; aspf=s;

**302** · 2025/12/04(木) 00:04:57.89

/(?<==)(\S)+/kで出来ました
ありがとうございました

**デフォルトの名無しさん** · 2025/12/04(木) 06:08:13.61

どういたしまして！

**デフォルトの名無しさん** · 2025/12/06(土) 22:50:10.26

セミコロンはどこいった

**デフォルトの名無しさん** · 2025/12/07(日) 02:42:31.53

DMARCレコードの末尾はセミコロンなくてもいいからじゃね？
それより修飾子kがなにかきになる

**デフォルトの名無しさん** · 2025/12/07(日) 07:46:42.62

プログラムでなくて正規表現メモパッド環境での質問でも良いですか
任意の文字をHTMLエンコード(16進数数値文字参照)するコマンドってありますか

文章：正規表現
検索：規
置換：⸨REGEXコマンド⸩
結果：正規表現

的な

**デフォルトの名無しさん** · 2025/12/07(日) 11:24:43.85

イヤん置換

**デフォルトの名無しさん** · 2025/12/07(日) 14:08:32.54

>>306
>DMARCレコードの末尾はセミコロンなくてもいいからじゃね？
なるほどね

>それより修飾子kがなにかきになる
文字のハイライトをしたいときに使うオプションのようだけど
/kが必要になる理由は分からないな

**デフォルトの名無しさん** · 2025/12/07(日) 16:01:19.36

使ってるAPI関係の話みたいだよ
-------
Bregexp.dll for SAKURA 互換 API
BMatch(), BMatchEx(), BSplit()
　　/pattern1/options
　　m/pattern1/options
BSubst(), BSubstEx()
　　s/pattern1/pattern2/options
BTrans()
　　tr/pattern3/pattern4/options
　　y/pattern3/pattern4/options (Ver.3 以降)

options
　k - 文字を日本語（Shift_JIS）として扱うが、Unicode API 利用時は無視される(Bregexp.dll 独自拡張)
-------

hintヒント
正規表現を検索、置換、Grepで利用する場合、「/」をエスケープしたり、「/」で囲ったりする必要はありません。
正規表現キーワードで使う場合は、/text\/css/k のように「/」をエスケープするか m#text/css#k のように書く必要があります。

hint追加情報
検索、置換、Grepでは、正規表現ライブラリに渡す文字列を以下のようにしています。[DELIMITER]は、0xffのバイナリ表記とします。
Unicode版では U+FFFF です。
検索時のオプションは「m[DELIMITER]Pattern[DELIMITER]km」です。
置換時のオプションは「s[DELIMITER]PatternBefore[DELIMITER]PatternAfter[DELIMITER]km」です。
デリミタ相当の文字を検索・置換するにはエスケープが必要です。
また大文字小文字を区別しない場合は最後に「i」が付加されます。
すべて置換で「すべて置換は置換の繰返し」がOFFの場合は「g」が付加されます。
(mオプションが付いていますが、改行をまたいだ検索はできません。)

**デフォルトの名無しさん** · 2025/12/07(日) 16:06:20.28

サクラエディタにはUnicode版もあるらしいが、そこでも //k が使われるのかは不明
まあこれをそのままユーザーに指定させるってのもどうかなってのは思う

**デフォルトの名無しさん** · 2025/12/07(日) 19:50:15.24

bregoing

**デフォルトの名無しさん** · 2025/12/07(日) 20:01:45.27

>>312
上のAPIの説明はbregonig.dll(v4.20)に付属の説明書からの抜き出しだよ
4. API
4.1. Bregexp.dll 互換 API (ANSI/Shift_JIS)
以下の Bregexp.dll 互換の API が使用できます。
•BMatch()
•BSubst()
•BTrans()
•BSplit()
•BRegfree()
•BRegexpVersion()
また、以下の Bregexp.dll for SAKURA 互換の API も使用できます。
•BMatchEx()
•BSubstEx()
pattern2, options の部分は bregonig.dll が自前で処理を行っており、Onigmo や Bregexp.dll あるいは Perl とは多少仕様が異なっています。（詳細は後述）
Bregexp.dll に比べて、BMatch(), BSubst(), BSplit() で s, x, a, u, R が使えるように拡張されています。なお、x は pattern1 にのみ効果があり、pattern2 には効果はありません。
Unicode API 利用時は k オプションは無視されます。漢字は常に使用可能です。
5.4. Bregexp.dll との非互換点
•オプションで k (日本語モード) を指定すると、\w は [A-Za-z0-9_] だけでなく、２バイト文字（漢字等）にもマッチするようになります。一方、Bregexp.dll では、オプション k の有無に関わらず、\w は [A-Za-z0-9_] と同義です。なお、Perl 5.8 でも、検索対象が Unicode 文字列（utf8 フラグがオン）ならば、\w は多バイト文字にもマッチします。Bregexp.dll と同じ動作にするには、オプション a を指定してください。
•Onigmo 自体は各種文字エンコーディングに対応していますが、bregonig.dll は Bregexp.dll との互換性のため、従来 API では、ASCII と Shift_JIS 以外の文字エンコーディングは使用できません。（新 API を使うことで、Ver.2 以降では UTF-16LE、Ver.3 以降では UTF-8 も使えます。）

**デフォルトの名無しさん** · 2025/12/08(月) 12:26:55.03

Bregexp.dllの頃から使われてたオプションっぽいね、20年前にはあったオプションかも

**デフォルトの名無しさん** · 2025/12/08(月) 21:08:56.84

2007年08月13日の投稿に/kを確認
https://sakura-editor.github.io/bbslog/sf/ansi/4937.html#4960

>正規表現キーワード /\b([0-9A-F]{2})+(?=h)?/k

bregonig.dllを導入するときに/kが必要になった可能性もあるのか
しかしこれ以上調べる気にはなれなかった

**デフォルトの名無しさん** · 2025/12/08(月) 21:53:56.42

面白いわくわくする

**デフォルトの名無しさん** · 2025/12/12(金) 00:35:57.86

よろしくお願いします

●Regular Expressionの使用環境
　サクラエディタ32bit Ver2.4.2.6048（bregoing.dll Ver.4.20 with Onigmo 6.2.0）

●検索か置換か？
　検索

●説明
　いかのアドレス範囲に一致させたい

●対象データ
151.145.0.0～151.145.127.255

**317** · 2025/12/12(金) 00:48:13.98

これで合ってますか？
(?:25[0-5]|2[0-4]\d|1\d{2}|[1-9]?\d)(?:\.(?:25[0-5]|2[0-4]\d|1\d{2}|[1-9]?\d)){3}

**317** · 2025/12/12(金) 00:51:57.92

間違えました

これで合ってますか？
(?:25[0-5]|2[0-4]\d|1\d{2}|[1-9]?\d)(?:\.(?:25[0-5]|2[0-4]\d|1\d{2}|[1-9]?\d)){3}

**317** · 2025/12/12(金) 00:52:53.14

また間違えてました・・・すみません

これで合ってますか？
151.145.(0|[1-9][0-9]?|1(0|1)[0-9]|12[0-7]).(0|[1-9][0-9]?|1[0-9]{2}|2[0-4][0-9]|25[0-5])

**デフォルトの名無しさん** · 2025/12/12(金) 01:16:30.11

細かい部分は見てないけど
とりあえず区切りの.はエスケープしないといけない

**デフォルトの名無しさん** · 2025/12/12(金) 01:18:48.94

IPアドレスに正規表現を使うなとは言っちゃダメなんだよね

**デフォルトの名無しさん** · 2025/12/12(金) 01:28:18.32

その心は？

**デフォルトの名無しさん** · 2025/12/12(金) 01:54:49.45

これ前後切らないと"151.145.127.256"が"151.145.127.25"で引っ掛かるな
10進数以外の表記が混ざってたら知らん

(?<!\d)(151\.145\.(([1-9]|1[01])?[0-9]|12[0-7])\.(([1-9]|1[0-9]|2[0-4])?[0-9]|25[0-5]))(?!\d)

**デフォルトの名無しさん** · 2025/12/12(金) 02:17:39.16

JSマクロで正規表現は文字列マッチまでにして
数値の評価はコードでやるのが素直ちゃうかな

**デフォルトの名無しさん** · 2025/12/12(金) 03:07:41.77

bregoing