25/11/02 20:01:30.27 JoUIYtII.net
正規表現の枠を超える後方参照（\1）とかで使ってそう
あれが絡むと事前にDFA作れない
282:デフォルトの名無しさん
25/11/02 20:13:48.87 JoUIYtII.net
正則言語の枠か
用語がちょっと怪しい
283:デフォルトの名無しさん
25/11/03 19:15:39.49 6hs01YZr.net
>>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 もそうやって実装してる ? かどうかは分からないけど
284:デフォルトの名無しさん
25/11/05 01:01:25.63 hq1L/1I1.net
それわかったらなんか良いことあるの（クルクルパー
285:デフォルトの名無しさん
25/11/07 00:31:17.29 Ua2fzQVD.net
NFA使わずに正規表現から直接DFAを構成する方法がDragon Bookに書いてあるけど
この書籍は今もDragon Bookで通じるのかな
もう古文書扱いされてそう
286:デフォルトの名無しさん
25/11/07 17:38:51.77 2v77MqUc.net
>>285
情報ありがとうございます
やはりドラゴンブックは読まざるを得ない感じですかね
読んでみます (気は重いけどｗ)
287:デフォルトの名無しさん
25/11/07 18:36:08.56 Ua2fzQVD.net
Dragon Bookでpdf検索すると大学のサイトとかで英語版が引っ掛かるけど旧版はセーフなのかな
DFAの構成法は第2版だと3.9節
少なくとも3章は最初から読んだ方がいいと思う
コンパイラに興味ないなら全部読む必要はない
288:デフォルトの名無しさん
25/11/07 19:00:36.04 Ua2fzQVD.net
そういえば正規表現自体の解析で4章前半のTop-Down Parsingくらいまでは役に立つかも
289:デフォルトの名無しさん
25/11/07 20:27:12.90 2v77MqUc.net
>>287
ありがとうございます。旧版 (日本語訳) はⅠ、Ⅱ共にさっき中古をポチりました
届くのは来週末だけど、図書館に第二版があるようなので明日行ってきます
コンパイラに興味ない、とまでは言わないけど、果たしてそこまで手を広げられるものなのか心許ないす
290:デフォルトの名無しさん
25/11/11 08:03:53.83 TgiPYl91.net
こういう方に最新版をポンと出す制度にならんもんかな
291:デフォルトの名無しさん
25/11/11 14:34:01.30 XyI6oP+4.net
複数の正規表現を使い分けられる記法があるといい
292:デフォルトの名無しさん
25/11/20 00:34:25.20 mbRrNt6G.net
DragonBook (第2版) の第3章まで読んだら、>>280 に書いた ε-遷移についての最初の疑問も氷解してしまったので、
一応伏線回収しておきます
「正規表現技術入門」では、ε-遷移を除去した後で部分集合構成法を行う、という流れで記述されていたので、
部分集合構成法を行うには前もって ε-遷移を除去しなければならない、と思い込んでいたのだけど、
その必要は全くなかったのでした
部分集合構成法の処理の中で一つ部分集合が得られたら、その集合の ε-閉包を取って
(その集合に そこから ε-遷移する状態を全て加えて)、それを DFA の 1 状態とすればよいだけなのでした
>>283 に書いた AI の回答が何となく歯切れが悪かった理由もこれで納得出来たわけで、
何でこんな簡単なことを思い付かなかったのか、我ながらアホでしたね
「正規表現技術入門」は章ごとに執筆者が違っていて、VM 型エンジンの章は鬼雲の作者が直々に書いていて説得力があるのですが、
DFA 型エンジンの章、とくにこの ε-遷移あたりの記述は今一つな感じです (エラそうに言ってますが)
--
ところで DragonBook 3.9 節の「正規表現から直接 DFA を導くやり方」も読みました
シンプソン構成法を経由せず、構文木から DFA を導くのはスゲーと思ったのですが
followpos() の張るダイアグラムは一種の NFA 的なものなので、それを DFA に変換する時には
やはり部分集合構成法と同じ手法を使うわけですね
とは言え ε-遷移が存在しないので扱う状態数もずっと少なくて済むはずなので、
これを使って On-the-Fly 法を実装して行きたいと思ってます
何にせよ、DragonBook を読めと言ってくれた >>285 さんには感謝しかないです
ありがとうございました
293:デフォルトの名無しさん
25/11/20 01:53:23.80 MRBYucy1.net
●Regular Expressionの使用環境
Java1.5
●検索か置換か？
検索
●説明
http://とhttps://があるもしくはない場合のドメインとサブドメインを検索したい
自分で考えた以下の正規表現だと、.から始まる不正なURLまで一致してしまいダメでした
^(https?://)?(.*\.)?doubleclick.net
●対象データ
#一致させたいものは以下
URLﾘﾝｸ(doubleclick.net)
URLﾘﾝｸ(doubleclick.net)
URLﾘﾝｸ(g.doubleclick.net)
URLﾘﾝｸ(g.doubleclick.net)
URLﾘﾝｸ(googleads.g.doubleclick.net)
URLﾘﾝｸ(googleads.g.doubleclick.net)
doubleclick.net/pagead/
g.doubleclick.net/pagead/
googleads.g.doubleclick.net/pagead/
#一致させたくないものは以下
URLﾘﾝｸ(.doubleclick.net)
URLﾘﾝｸ(.doubleclick.net)
URLﾘﾝｸ(.g.doubleclick.net)
URLﾘﾝｸ(.g.doubleclick.net)
URLﾘﾝｸ(.a.g.doubleclick.net)
URLﾘﾝｸ(.a.g.doubleclick.net)
.doubleclick.net/pagead/
.g.doubleclick.net/pagead/
0doubleclick.net/pagead/
URLﾘﾝｸ(0doubleclick.net)
URLﾘﾝｸ(0doubleclick.net)
294:デフォルトの名無しさん
25/11/20 09:40:15.39 Mz3QCXK6.net
その処理系で文字クラスが使えるなら (.*\.)? を ([^.0].*\.)? とすればイケるハズ
295:293
25/11/20 15:17:38.43 MRBYucy1.net
>>294
レスありがとうございます
以下の2行は一致しなくなりましたが、
.doubleclick.net/pagead/
.g.doubleclick.net/pagead/
以下の6行は一致してしまいました
URLﾘﾝｸ(.doubleclick.net)
URLﾘﾝｸ(.doubleclick.net)
URLﾘﾝｸ(.g.doubleclick.net)
URLﾘﾝｸ(.g.doubleclick.net)
URLﾘﾝｸ(.a.g.doubleclick.net)
URLﾘﾝｸ(.a.g.doubleclick.net)
296:デフォルトの名無しさん
25/11/20 16:30:51.92 0pUMlwmF.net
"doubleclick.net"は決め打ちでいいのかな
Pattern p = Pattern.compile("^(?:https?://)?((?:[^./?#]+\\.)*doubleclick\\.net)(?=[:/]|$)");
マッチした後の処理は分からんけど動作例
URLﾘﾝｸ(ideone.com)
297:293
25/11/20 21:15:50.67 MRBYucy1.net
>>296
レスありがとうございます
せっかく教えていただいたのにすみません、JavaではなくてJavaScriptでしたので動作しませんでした
チェッカー
URLﾘﾝｸ(www-creators.com)
298:デフォルトの名無しさん
25/11/20 21:32:25.61 0pUMlwmF.net
今時分にJava1.5でおかしいと思ったけどスルーしてしまった
文字列でエスケープしてる\\を\に直せば使えるはず
ついでに?と#を先読みに追加した（多分いらない）
^(?:https?://)?((?:[^./?#]+\.)*doubleclick\.net)(?=[:/?#]|$)
299:293
25/11/20 21:52:35.87 MRBYucy1.net
>>298
度々ありがとうございます
完璧に動作しました！
助かりました
未だに先読みと後読みが使いこなせず・・・詰んでました
300:デフォルトの名無しさん
25/11/20 23:34:16.70 mbRrNt6G.net
>>292
シンプソン構成法じゃなくてトンプソン構成法でした。すまそん
尊敬する Ken Thompson の名前を間違えるとはヤバ過ぎ
301:デフォルトの名無しさん
25/11/22 12:38:05.41 Vr8VfdEk.net
黄色くなりそう