Regular Expression(正規表現) Part17

**デフォルトの名無しさん** · 2023/12/16(土) 08:59:20.50

Regular Expressionスレです。

質問する場合は必ず実装言語や処理系ソフトウェア名を示してください。

前スレ
Regular Expression(正規表現) Part16
https://mevius.5ch.net/test/read.cgi/tech/1635936601/

次スレは>>980宜しく
テンプレ>>2以降

**デフォルトの名無しさん** · 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 の名前を間違えるとはヤバ過ぎ