Regular Expression(正規表現) Part17 (300ﾚｽ)
上下前次1-新
ﾘﾛｰﾄﾞ規制です｡10分ほどで解除するので､他のﾌﾞﾗｳｻﾞへ避難してください｡
1(2): 2023/12/16(土)08:59 ID:uVHZ7e2j(1/4) AAS
Regular Expressionスレです。
質問する場合は必ず実装言語や処理系ソフトウェア名を示してください。
前スレ
Regular Expression(正規表現) Part16
2chｽﾚ:tech
次スレは>>980宜しく
テンプレ>>2以降
271: 08/09(土)13:09 ID:AY2Xi2Yg(1) AAS
SNSやWeb検索もたいてい正規表現対応してるからプログラミング以外で活用できる場面が増えてなんか嬉しい
272: 08/14(木)17:46 ID:ll+c+ksk(1) AAS
そんなに対応してるのある？
273(2): [age] 09/29(月)18:28 ID:omFFHDum(1) AAS
^[^:]+://+([^:/]+\.)?
これの//+部分って//だけで問題ありますか？
274: 09/29(月)19:15 ID:QGaGSVZY(1) AAS
>>273
その正規表現の目的は理解できてるの？
275: 09/29(月)21:45 ID:SNsW5d6C(1) AAS
>>273
スラッシュをエスケープしなきゃいけない環境で使う正規表現かどうかによる
エスケープしなきゃいけない環境なら問題があるしそうじゃない環境なら問題ない
276: 09/29(月)22:25 ID:RjmgsX7I(1) AAS
file://で次が/になる場合はある
外部ﾘﾝｸ:en.wikipedia.org
277: 09/29(月)22:54 ID:FkLCZ8/e(1) AAS
何にマッチさせたいかによるわな
278: 10/25(土)12:46 ID:BjPJz/dc(1) AAS
【悲報】4/24に鬼車がgithubで開発終了したのに続いて
鬼雲（bregonig.dll）の公式サイトが9/30で閉鎖
外部ﾘﾝｸ:k-takata.o.oo7.jp
外部ﾘﾝｸ:x.com
279: 10/28(火)01:47 ID:WdB2Psfo(1) AAS
鬼車はJavaScriptの仕様に寄せろと細かいことまで言われて
嫌気がさしたのかなという印象だけど真相は作者のみぞ知るか
ただ最近はDFAキャッシュを使うエンジンの台頭で
これとかboost.regexが速いとされた時代はとうに終わってるんで
マルチバイト対応を必要とする人以外はあまり影響ない気もする
280(2): 11/02(日)19:07 ID:vGsY1NrW(1) AAS
「正規表現技術入門」を読むと、GNU grep ではマッチング途中で必要になった部分だけ
オンデマンドで DFA を構成していく On-the-Fly 構成法を使っている、と書かれてるけど
どのレベルから On-the-Fly してるんでしょ ?
部分集合構成法で NFA を DFA に変換する所からなのか、もっと前のε-遷移除去からなのか
あるいはさらに前の正規表現をパースして NFA を作る所も On-the-Fly なんですかね ?
GNU grep のソース見ろと言われそうだけど
281(1): 11/02(日)20:01 ID:JoUIYtII(1/2) AAS
正規表現の枠を超える後方参照（\1）とかで使ってそう
あれが絡むと事前にDFA作れない
282: 11/02(日)20:13 ID:JoUIYtII(2/2) AAS
正則言語の枠か
用語がちょっと怪しい
283(1): 11/03(月)19:15 ID:6hs01YZr(1) AAS
>>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: 11/05(水)01:01 ID:hq1L/1I1(1) AAS
それわかったらなんか良いことあるの（クルクルパー
285(2): 11/07(金)00:31 ID:Ua2fzQVD(1/3) AAS
NFA使わずに正規表現から直接DFAを構成する方法がDragon Bookに書いてあるけど
この書籍は今もDragon Bookで通じるのかな
もう古文書扱いされてそう
286: 11/07(金)17:38 ID:2v77MqUc(1/2) AAS
>>285
情報ありがとうございます
やはりドラゴンブックは読まざるを得ない感じですかね
読んでみます (気は重いけどｗ)
287(1): 11/07(金)18:36 ID:Ua2fzQVD(2/3) AAS
Dragon Bookでpdf検索すると大学のサイトとかで英語版が引っ掛かるけど旧版はセーフなのかな
DFAの構成法は第2版だと3.9節
少なくとも3章は最初から読んだ方がいいと思う
コンパイラに興味ないなら全部読む必要はない
288: 11/07(金)19:00 ID:Ua2fzQVD(3/3) AAS
そういえば正規表現自体の解析で4章前半のTop-Down Parsingくらいまでは役に立つかも
289: 11/07(金)20:27 ID:2v77MqUc(2/2) AAS
>>287
ありがとうございます。旧版 (日本語訳) は?、?共にさっき中古をポチりました
届くのは来週末だけど、図書館に第二版があるようなので明日行ってきます
コンパイラに興味ない、とまでは言わないけど、果たしてそこまで手を広げられるものなのか心許ないす
290: 11/11(火)08:03 ID:TgiPYl91(1) AAS
こういう方に最新版をポンと出す制度にならんもんかな
291: 11/11(火)14:34 ID:XyI6oP+4(1) AAS
複数の正規表現を使い分けられる記法があるといい
292(1): 11/20(木)00:34 ID:mbRrNt6G(1/2) AAS
DragonBook (第2版) の第3章まで読んだら、>>280 に書いた ε-遷移についての最初の疑問も氷解してしまったので、
一応伏線回収しておきます
「正規表現技術入門」では、ε-遷移を除去した後で部分集合構成法を行う、という流れで記述されていたので、
部分集合構成法を行うには前もって ε-遷移を除去しなければならない、と思い込んでいたのだけど、
その必要は全くなかったのでした
部分集合構成法の処理の中で一つ部分集合が得られたら、その集合の ε-閉包を取って
(その集合に そこから ε-遷移する状態を全て加えて)、それを DFA の 1 状態とすればよいだけなのでした
>>283 に書いた AI の回答が何となく歯切れが悪かった理由もこれで納得出来たわけで、
何でこんな簡単なことを思い付かなかったのか、我ながらアホでしたね
「正規表現技術入門」は章ごとに執筆者が違っていて、VM 型エンジンの章は鬼雲の作者が直々に書いていて説得力があるのですが、
DFA 型エンジンの章、とくにこの ε-遷移あたりの記述は今一つな感じです (エラそうに言ってますが)
--
ところで DragonBook 3.9 節の「正規表現から直接 DFA を導くやり方」も読みました
シンプソン構成法を経由せず、構文木から DFA を導くのはスゲーと思ったのですが
followpos() の張るダイアグラムは一種の NFA 的なものなので、それを DFA に変換する時には
やはり部分集合構成法と同じ手法を使うわけですね
とは言え ε-遷移が存在しないので扱う状態数もずっと少なくて済むはずなので、
これを使って On-the-Fly 法を実装して行きたいと思ってます
何にせよ、DragonBook を読めと言ってくれた >>285 さんには感謝しかないです
ありがとうございました
293(3): [age] 11/20(木)01:53 ID:MRBYucy1(1/4) AAS
●Regular Expressionの使用環境
Java1.5
●検索か置換か？
検索
●説明
http://とhttps://があるもしくはない場合のドメインとサブドメインを検索したい
自分で考えた以下の正規表現だと、.から始まる不正なURLまで一致してしまいダメでした
^(https?://)?(.*\.)?doubleclick.net
●対象データ
#一致させたいものは以下
外部ﾘﾝｸ:doubleclick.net
外部ﾘﾝｸ:doubleclick.net
外部ﾘﾝｸ:g.doubleclick.net
外部ﾘﾝｸ:g.doubleclick.net
外部ﾘﾝｸ:googleads.g.doubleclick.net
外部ﾘﾝｸ:googleads.g.doubleclick.net
doubleclick.net/pagead/
g.doubleclick.net/pagead/
googleads.g.doubleclick.net/pagead/
#一致させたくないものは以下
外部ﾘﾝｸ:.doubleclick.net
外部ﾘﾝｸ:.doubleclick.net
外部ﾘﾝｸ:.g.doubleclick.net
外部ﾘﾝｸ:.g.doubleclick.net
外部ﾘﾝｸ:.a.g.doubleclick.net
外部ﾘﾝｸ:.a.g.doubleclick.net
.doubleclick.net/pagead/
.g.doubleclick.net/pagead/
0doubleclick.net/pagead/
外部ﾘﾝｸ:0doubleclick.net
外部ﾘﾝｸ:0doubleclick.net
294(1): 11/20(木)09:40 ID:Mz3QCXK6(1) AAS
その処理系で文字クラスが使えるなら (.*\.)? を ([^.0].*\.)? とすればイケるハズ
295: 293 [age] 11/20(木)15:17 ID:MRBYucy1(2/4) AAS
>>294
レスありがとうございます
以下の2行は一致しなくなりましたが、
.doubleclick.net/pagead/
.g.doubleclick.net/pagead/
以下の6行は一致してしまいました
外部ﾘﾝｸ:.doubleclick.net
外部ﾘﾝｸ:.doubleclick.net
外部ﾘﾝｸ:.g.doubleclick.net
外部ﾘﾝｸ:.g.doubleclick.net
外部ﾘﾝｸ:.a.g.doubleclick.net
外部ﾘﾝｸ:.a.g.doubleclick.net
296(1): 11/20(木)16:30 ID:0pUMlwmF(1/2) AAS
"doubleclick.net"は決め打ちでいいのかな
Pattern p = Pattern.compile("^(?:https?://)?((?:[^./?#]+\\.)*doubleclick\\.net)(?=[:/]|$)");
マッチした後の処理は分からんけど動作例
外部ﾘﾝｸ:ideone.com
297: 293 [age] 11/20(木)21:15 ID:MRBYucy1(3/4) AAS
>>296
レスありがとうございます
せっかく教えていただいたのにすみません、JavaではなくてJavaScriptでしたので動作しませんでした
チェッカー
外部ﾘﾝｸ:www-creators.com
298(1): 11/20(木)21:32 ID:0pUMlwmF(2/2) AAS
今時分にJava1.5でおかしいと思ったけどスルーしてしまった
文字列でエスケープしてる\\を\に直せば使えるはず
ついでに?と#を先読みに追加した（多分いらない）
^(?:https?://)?((?:[^./?#]+\.)*doubleclick\.net)(?=[:/?#]|$)
299: 293 [age] 11/20(木)21:52 ID:MRBYucy1(4/4) AAS
>>298
度々ありがとうございます
完璧に動作しました！
助かりました
未だに先読みと後読みが使いこなせず・・・詰んでました
300: 11/20(木)23:34 ID:mbRrNt6G(2/2) AAS
>>292
シンプソン構成法じゃなくてトンプソン構成法でした。すまそん
尊敬する Ken Thompson の名前を間違えるとはヤバ過ぎ
上下前次1-新書関写板覧索設栞歴
ｽﾚ情報 赤ﾚｽ抽出 画像ﾚｽ抽出 歴の未読ｽﾚ
ぬこの手 ぬこTOP 0.025s