- 1 名前：デフォルトの名無しさん [2017/03/15(水) 02:04:35.47 ID:e01p03UP.net]
- Regular Expressionスレです。
質問する場合は必ず実装言語や処理系ソフトウェア名を示してください。
前スレ
Regular Expression(正規表現) Part13
echo.2ch.net/test/read.cgi/tech/1415149975/
次スレは>>980宜しく
天ぷら等2以降
- 917 名前：デフォルトの名無しさん mailto:sage [2019/07/17(水) 08:28:41.50 ID:2/Bgill9.net]
- >>875訂正
俺は俺のケースだけ考えていたが、これだと871内URLの筆者のケースと合致しない。
そこで一応、両方とも合致する実装を考えてみた。
(といってもバグってる実装について推測すること自体はあまり意味がないが)
Perlはおそらく、^のフラグではなくて、空文字マッチ後のそのマッチ区間の*を+にしてる。
（というより筆者もそう言っているのだが俺が早とちりしてしまった）
871のケースだと、正規表現 (?:^|>)(.*?)(?:$|<) に対して、
1回目：(?:^|>)(.*?)(?:$|<)
2回目：(?:^|>)(.+?)(?:$|<)
というわけだ。結果、2回目は「先頭、<含んだ1文字、次の<まで、となり、
その筆者の説明通り先頭タグを含んで次タグ或いは文末まで伸びることになる。
俺のケースでは、正規表現 (^|[@;])[^@;]* に対して、
1回目：(^|[@;])[^@;]*
2回目：(^|[@;])[^@;]+
だから '@time;prop1:style1;prop2:style2' に対して @time のマッチも正しく取れることになる。
こういった場合、実装者は安全側に倒したくなる物だが、
現実は安全側に倒しすぎて余分なケースを含んでしまい、結果、バグっているというわけだ。
JavaScriptは最高に安全な実装、「空文字マッチは1文字進める」とした。（おそらくRubyその他もそう）
これだと絶対に無限ループはしないが、俺のケースでバグる。
Perlの実装だと俺のケースは通るが、871内URLの筆者のケースでバグる。
その他バグケースも出してくれれば俺の推測で合っているかどうかは答える。
- 918 名前：デフォルトの名無しさん mailto:sage [2019/07/17(水) 08:28:59.00 ID:2/Bgill9.net]
- 正しい実装は、「経路全体」（つまりツリーのリーフ）に対してフラグを持たないといけない。
Perlは「区間」(＝経路の一部)に対してフラグをつけてしまったところが間違いだ。
871のケース、単純化する為に (A0|A1)B(C0|C1)として、
1回目：A0BC1 で空文字マッチ
そして空文字マッチの場合はこれを記録し、これと同一の場合は次回以降はスキップする。
結果、2回目：最初に A0BC1 がマッチするがこれは捨てられ、次に A1BC0またはA1BC1となる。
そして非空文字マッチとなったので、この記録を全破棄して、同様にループを繰り返せばいい。
実装の修正は、探索関数そのものにだいぶ手を入れないといけないのでそれなりに大変だ。
まずは全部の最終段に「最終チェック」を入れて上記リストと照合、記載有ればマッチ失敗として探索継続、としなければならないが、
おそらくこれが1ヶ所では済まない。
ただしこれはリターンパスを辿ればいいので何らかのツールが有ればほぼ自動でいけるかもしれない。
次に上記リストを作成する為に全経路を出力させなければならない。
デバッグ用にこれが既にあればラッキーだが、なければ自前で作らなければいけない。
といっても内容はツリーのノードを辿るだけなので、ツリーのフォーマットが分かればすぐだが、
ゴリゴリに高速化とかしていると割と意味不明なコードになっていることが多いので、
その状態で確認するのは結構辛いとは思う。
リストの管理は、空文字マッチなら追記、非空文字マッチならクリア、なので、これはやるだけだ。
リストの管理も探索関数にやらせて、探索関数は
今：マッチ場所とマッチ長さを返す
修正後：マッチ場所とマッチ長さを含んだ『配列』を返す、とし、
「空文字マッチの場合は自動で継続、非空文字マッチまたは終了まで探索、まとめて配列で結果を返す」とするのがいいだろう。
|
 |
