s/正規表現/を語ろう/e
■ このスレッドは過去ログ倉庫に格納されています
0001Cスレの方々、ご迷惑をおかけしました(恥)
NGNGs/騙(ら|り|る|れ|ろ)/語$1/;
別にperlじゃなくてもいいです。。
0003デフォルトの名無しさん
NGNG0004デフォルトの名無しさん
NGNG早く、ネタ振れ
0005デフォルトの名無しさん
NGNGｼﾞｻｸｼﾞｴﾝ（・∀・）ﾃﾞｼﾀ!!
0006デフォルトの名無しさん
NGNGaaaaaabbbbbb
みたいのに1回でマッチさせるにはどうすればいいの？
0007デフォルトの名無しさん
NGNG?は任意の一文字かな？
<=ってなんだろ？
()は検索の補助で検索対象にならないのかな？
これはperlの表現か？
最近の正規表現は難しくて、おじさんにはわからんのぉ。
いろいろ教えてくれ
0008デフォルトの名無しさん
NGNG0009デフォルトの名無しさん
NGNG直前の文字が0回か1回出現する。
0010デフォルトの名無しさん
NGNG別に Perl 限定じゃないし、CGI な話題でもないし、プログラム技術板で
良いと思うが。
0011デフォルトの名無しさん
NGNGあっちでやった方が住人が喜ぶから
0012デフォルトの名無しさん
NGNG0013デフォルトの名無しさん
NGNGアルゴリズムを読んだけど、結構面白かったな。
0015デフォルトの名無しさん
NGNG正規表現道場@2ch
http://pc.2ch.net/test/read.cgi/php/996105815/
過去スレ
正規表現
http://piza2.2ch.net/tech/kako/993/993143342.html
0017デフォルトの名無しさん
NGNGhttp://www.yamada-labs.com/software/spec/jre/index.htm
こういうライブラリ使うのがいいのかな。
C++なんかで正規表現をさくっとやるには他に手段あんの？
0019デフォルトの名無しさん
NGNGa と b が同じ数じゃなくてもマッチしちゃうじゃん。
0020デフォルトの名無しさん
NGNGおぉ、そんな条件があったか。
スマソ見落としてました。
おぉ、一気に難しい（笑）
0021これはネタだな
NGNG正規表現(3型文法)では無理。
それは文脈自由文法(2型文法)の言語族に属する。
0022デフォルトの名無しさん
NGNG友人に聞いたら「痴漢するため」と言われました。
彼とはもう口をききたくありません。
00236
NGNG正解！ネタです。案外早く答えが出たな。
まぁこの機会だから21は正則文法と文脈自由文法の解説でもしてあげてください。
で、複数回の正規表現を組み合わせて良いなら、一番シンプルに仕上げるには
どうすれば良いかな(これはネタではありません)。
0024デフォルトの名無しさん
NGNG実際がどうしても結びつかない。
直訳っすか？＞正規表現
00256
NGNGレギュラーエクプレッションの直訳だから。
「規則的な言い回し」とでも訳すべきなのだが。
0026FAQ
NGNG以降、同様の質問は不可とす
0027デフォルトの名無しさん
NGNGboost
0028デフォルトの名無しさん
NGNGs/(.)[ッ|っ](.)(.)/$1$2ー$3/
だろ？jperlｷﾗｲだが。
0029デフォルトの名無しさん
NGNG間違えた、s/(.)[ッっ](.)(.)/$1$2ー$3/だ。
0031デフォルトの名無しさん
NGNGs/マッチパターン/置換パターン/
パッチパターンでは \1 .. \9で参照
置換パターン以降、次の正規表現までは $1 .. $9で参照
0032デフォルトの名無しさん
NGNG0034デフォルトの名無しさん
NGNG形式を踏襲するんだろ。
バッファを持たずに、一文字ずつ
while (matcher←データ) { if (受理()) 位置の記録(); }
という押し込み型になればインタラクティブな入力処理や
プロトコルの処理に都合が良いのに。
こうすれば、文字コードの変換も、全データに対して行う必要がない。
0035デフォルトの名無しさん
NGNG0036デフォルトの名無しさん
NGNGそういうのもほしいね
ぜひ作って contribute して下さい(w
そういうライブラリってあったかな…
つっこんだものはなかなか無い…
0037デフォルトの名無しさん
NGNG自分が正規表現クラス作った経験から言うと、
正規表現のマッチングはバックトラックしなきゃならんので、それは無理です。
全体を受理するまで処理してみなければ、正しい経路がわからんのです。
003837
NGNG0039デフォルトの名無しさん
NGNG過去形と口語のためにちょっと拡張
s/騙(ら|り|る|れ|ろ|っ|ん)/語$1/;
0040デフォルトの名無しさん
NGNGDFA に変換できればね。
でも、/(.+).*(.+).*\2.*\1/ みたいなやつだと、バックトラックなしでは
無理でない?
0041デフォルトの名無しさん
NGNG0042デフォルトの名無しさん
NGNG0043デフォルトの名無しさん
NGNG>ぜひ作って contribute して下さい(w
去年しましたが。
>正規表現のマッチングはバックトラックしなきゃならんので、それは無理です。
>全体を受理するまで処理してみなければ、正しい経路がわからんのです。
バックトラックでやるような処理はしてるけどバックトラックではないです。
ただ、どこで停止させるかという判断はユーザーに任されてる。
>DFA に変換できればね。
する必要はないです。できないのはカーニハンやRMS(regex)のデザインで
やるから仕様縛りが出ます。演算子はQEDの形式しかやってません。
インクリメンタルサーチや置換処理の時にヘンな動作の可能性がありますから、
｜やグループ化は排除してます。
0044デフォルトの名無しさん
NGNGaaabb とかは aabb としてマッチさせんの、それともさせないの？
0045デフォルトの名無しさん
NGNGkmp法のように正規表現を解析して速度を上げたり出来ないんですか？
0046デフォルトの名無しさん
NGNGもしマッチしても良いなら、こういうのを考えてみた。
$_ = 'ccccaaaaabbbdd';
$ab = 'ab';
$ab = $1 while(/(a${ab}b)/);
s/$ab/ マッチしたよん /;
print;
シンプルだとは思うが、効率が良いかどうかは謎。
0047デフォルトの名無しさん
NGNGそう思ったら違う実装にすればよい。
オレのは、探索中に中断できたり文字コード変換を
やりながらのマッチングでもバッファを持ちたくないという要求が
第一にあった。
0048デフォルトの名無しさん
NGNGもともとの正規表現ってのは、決定性有限状態オートマトンで表現できて、
それを素直に実行させれば、高速に動作するよ。
perl なんかで拡張された正規表現だとバックトラックでやったほうが簡単。
つか、(?=…) をバックトラックせずに、かつメモリ効率もよくマッチング
させるやり方って思いつかん。
0049デフォルトの名無しさん
NGNG仮想マシン（といってもプログラムカウンタと停止フラグだけ）を
εの度に増殖させる。再帰してもスタックが伸びて行くからコストは
変わらないし、速くも遅くもならない。
0050デフォルトの名無しさん
NGNGDFAが高速に動作するのは分かるのですが、
それでも高々逐次検索と同程度のパフォーマンスですよね？
BM法やkmp法のように比較要素の刈り込みを導入する
一般的な手法ってないかなって思ったのです。
005150
NGNGテキストエディタの正規表現での強調表示処理を書いていて、
複数の正規表現と比較しないといけないから、高速化したいのですが。
こういう場合は正規表現を合成する方が良いんでしょうか
0052デフォルトの名無しさん
NGNGでも、それって結局、バックトラックしてることにならない?
仮想マシン間で同期をとりながら実行すればよいのかな?
かなり面倒そうだけど。
0053デフォルトの名無しさん
NGNG同期なんか取らない。
S'←S(c)
を繰り返し行うだけ。
プログラム的にはむしろ短く単純になる。
match(c)という一個の関数の中で状態を
複数持ち、個数分だけ遷移させて終了。
0054デフォルトの名無しさん
NGNGああ、そういう意味か。さすがに一般的な正規表現に対して検索位置の
スキップが可能なような実装はないんじゃないかな。
正規表現から固定文字列部分を抜き出して、最初にそこを BM なりなんなりで
検索するってのは、たいていのエンジンで実装されていると思うけど。
複数の固定文字列の検索だったら、古典的だけど、Aho-Corasick とか
Commentz-Walter とかの手法はあるよ。
0055デフォルトの名無しさん
NGNG漏れならその場合なら合成する。ただDFAでも
function +[0-9A-Za-z]
みたいな正規表現なら、"function"のような固定長の部分を
１つの状態にしてBM法で検索するなどは可能。
0056デフォルトの名無しさん
NGNGDFAつーのは最小化アルゴリズムがあるんですよ。
オートマトンや形式言語の教科書読んでね。
0057デフォルトの名無しさん
NGNG最小化と高速化は関係ないでしょう
0058デフォルトの名無しさん
NGNGその通り。
でもスレ伸びないから話題としてlexなんかでは実行時に
圧縮されたテーブルの展開（Jhonsonの二重配列の参照）
をするんで元データ-が小さいことはいいことだと振ってみる。
0059デフォルトの名無しさん
NGNG0060デフォルトの名無しさん
NGNG最長を探せるのはなんだっけ？
POSIX NFAだったかな
0061デフォルトの名無しさん
NGNGDFAというのは吉野家のねぎだくと同じ両刃の剣。
店員にマークされるよりも怖い空間量の爆発。
経路もわからないんで置換に向かない。
（性能落とせば分かるんだったっけ）
NFAの方がライブラリとしては適切。
0062デフォルトの名無しさん
NGNG常に探せる。停止させなければ。
0063デフォルトの名無しさん
NGNGんじゃ、技術力が及ばない場合を除いて、
DFA以外を選択する意味はないってこと？
0064デフォルトの名無しさん
NGNG経路がわからないので置換できない。
（できるのもあるみたいだが
部分式だけDFAにしてるんで
メリットを相殺してる）
メモリーの使用量がタマーに巨大化する。
（遅延評価というテクでも完全には克服できないみたい）
0065デフォルトの名無しさん
NGNG0066デフォルトの名無しさん
NGNG0067デフォルトの名無しさん
NGNG0068デフォルトの名無しさん
NGNG0069デフォルトの名無しさん
NGNG0070デフォルトの名無しさん
NGNGhttp://cheese.2ch.net/test/read.cgi/math/1017770466/
0071デフォルトの名無しさん
NGNGどんなふうにすばらしく行うことができますか。
・メソッドブロック開始の「{」の直後で改行し
「System.out.println("クラス名.メソッド名:in");」
を挿入し改行。
・メソッドブロック終了の「}」の直前に
「System.out.println("クラス名.メソッド名:out");」
を挿入し改行。
・コンストラクタ開始の「{」の直後（superがある場合はsuperの直後）で改行し
「System.out.println("クラス名.Constructer:in");」
を挿入し改行。
・コンストラクタブロック終了の「}」の直前に
「System.out.println("クラス名.Constructer:out");」
を挿入し改行。
0072デフォルトの名無しさん
NGNGttp://aglaia.c.u-tokyo.ac.jp/~yamamoto/Yamaguch_Seminar/20010725/node3.html
DFA
ttp://aglaia.c.u-tokyo.ac.jp/~yamamoto/Yamaguch_Seminar/20010725/node4.html
0073デフォルトの名無しさん
NGNGどんな図面書けば理解してもらえる？
片言ALGOLだとわかってもらえんし
UML検討したけどイマイチぴんと来ない。
0074デフォルトの名無しさん
NGNG0075デフォルトの名無しさん
NGNG0076デフォルトの名無しさん
NGNG正規表現の神
0077デフォルトの名無しさん
NGNGおもろすぎ
0078デフォルトの名無しさん
NGNGhttp://cs.fit.edu/~ryan/cse3002/nfa2dfa.pdf
0079オレの彼女は
NGNGなので彼女はこの言葉を言わない。
男同士でニヤニヤしながら話しているのが誤解の原因
かもしれない...。
一度、正しい説明したほうがいいのか教えて欲しい。
（脱線してすまない。）
0080デフォルトの名無しさん
NGNG教科書通りにRE→NFA展開、DFA変換とやったのですが
(*a)+
みたいなε遷移だけになってしまう可能性のあるグループに
繰り返し文字を摘要すると、NFA状態遷移図にループが生じて
しまいますよね。
こういう正規表現は禁止にするべきなのでしょうか？
それとも回避する一般的な手法があるのでしょうか．．．
0081デフォルトの名無しさん
NGNG自分がライブラリを作ったときは、禁止しちゃいましたね。
DFA への変換はせずに NFA を直接実行するタイプだったけど、
ε遷移を含むグループの繰り返しというのは、パターンが
バグってる可能性も高いし、と思って。
0082デフォルトの名無しさん
NGNGhttp://slashdot.jp/article.pl?sid=02/06/06/0720253&mode=nested
008380
NGNGどうもです。
やはり禁止が手っ取り早そうですね。
どっちにしてもこの状態を検出してREのコンパイルを中止する
ようにしないと、使い物にならないわけですね。
毎回、探索済みのε遷移を保存しておいて重複チェックをしてと．．．
0084デフォルトの名無しさん
NGNGバックリファレンスのバリエーション増えるから
一つの値返したら結果がランダムになっちまう。
そこで、結果集合を返すようにしたけどヘン。
置換用はQEDの演算子に絞り、
orとグループはシラブル分け(トークンリーダー)用
とするのが妥当(それでも一意にはならないが)。
＃Perl、Rubyの仕様は壊れている。
0085デフォルトの名無しさん
NGNGPerlの REは backslashまみれにならなくてすき (emacsenだけに) だけど
こうやって非互換性がふえていくんだな..
0086デフォルトの名無しさん
NGNGひたすらDLする漏れは逝ってよしですか?
多分これが終わったら逝ってくると思うけどモナー
0087デフォルトの名無しさん
NGNG安心してください。(?...)はPerl6ではなくなります。
非互換性はさらに増えますが(わら
何しろ[]が文字クラスじゃなくなるしねえ。
0088デフォルトの名無しさん
NGNG0089デフォルトの名無しさん
NGNG言ってる事がよく理解できてないけど、DFA でバックリファレンスを
扱うことが難しいということかな。
perl は NFA をバックトラックで実行するので、先読みだろうが
バックリファレンスだろうが、問題なくサポートできるというわけ。
009084
NGNG>>89
8進数か10進数というパターンに
(0([0-7]+))|([0-9]+)
入力が011だった場合、バックリファレンス\1は
カラ文字でも11でもどちらでも間違いではないってこと。
複数の解ができるのに結果を一つしか選ばないPerlはヘンってこと。
すくなくとも、sedの仕様ならば置換結果は一つ。
0091デフォルトの名無しさん
NGNG> 複数の解ができるのに結果を一つしか選ばないPerlはヘンってこと。
いや、「複数の解のうちどの一つを選ぶか」は明確に仕様になっているよ。
> カラ文字でも11でもどちらでも間違いではないってこと。
少なくともPerlでは「11」が正解で空文字列は間違い。
84のいいたいことがおいらにはよく理解できてない……。
0092名無しさん＠カラアゲうまうま
NGNG0093デフォルトの名無しさん
NGNGPerl6では:anyで結果*集合*を返すらしいよ。
0094デフォルトの名無しさん
NGNG事実、上級Vim使いは検索コマンドを移動コマンドと同一視して編集作業をするとか。
画面内を /int .\+; とか打ち込んで飛び回るんだそうで。
0096デフォルトの名無しさん
NGNG0097名無しさん＠Ｅｍａｃｓ
NGNGそういうエディタの使い方する奴はvi以外のエディタを使ってようと
いずれ自分で正規表現を覚えるよ.
俺はsedが好き.
■ このスレッドは過去ログ倉庫に格納されています