2007/03/16

開始タグと終了タグで構造化されているテキストがあって、しかも同じ種類のタグが入れ子になっていたら、どうやって一番外側のグループを取り出すのが定石なんだろう。『詳解 正規表現』には何かカッコいい方法が書いてあるんだろうか。

とりあえず問題をブレークダウンすると、こんな風に入れ子になっているパターンを正規表現でうまく補足できないかなあという話。
gosh> str
"<p>This is a paragraph.
<footnote><p>Here is a paragraph in the footnote</p></footnote>
Here is a main paragraph again.</p>"

gosh> ((rxmatch #/うまいパターン/ str))
"<p>This is a paragraph.
<footnote><p>Here is a paragraph in the footnote</p></footnote>
Here is a main paragraph again.</p>"
もちろん、これじゃ困るわけ。
gosh> ((rxmatch #/<p>.*?<\/p>/ str))
"<p>This is a paragraph.
<footnote><p>Here is a paragraph in the footnote</p>"

結論。一晩寝ても「うまいパターン」は見出せなかった。というわけで、正規表現ではなくGaucheでなんとかする方向へ逃げる。

戦略としては、こんなでどうか。
  1. 開始タグをみつける。
  2. 開始タグから最初にみつけた終了タグまでを match 候補にする。(その途中で開始タグを見つけるかもしれないけど気にしない)
  3. match 候補のなかの開始タグと終了タグの数を調べる。同じなら match 候補を match にして終了。違ったら4.へ。
  4. match 候補を開始タグとみなして2.へ。
実装。
; matche to the broadest range sandwiched between two patterns
(define (rxmatch-between-pattern pattern1 pattern2 string)
(define (make-pattern pattern-string1 pattern-string2)
(string->regexp
(string-append pattern-string1 ".*?" pattern-string2)))
(define init-pattern
(make-pattern (regexp->string pattern1) (regexp->string pattern2)))
(define (num-of-matched-inner pattern string)
(let R ((head-matched (pattern string)) (n 0))
(if (not head-matched)
n
(R (pattern (rxmatch-after head-matched)) (+ n 1)))))
(let R ((matched (init-pattern string)))
(if (not matched)
#f ;; There's no match -- REGEXP-BETWEEN-PATTERN"
(if (= (num-of-matched-inner pattern1 (matched))
(num-of-matched-inner pattern2 (matched)))
matched
(R ((make-pattern (regexp-quote (matched)) (regexp->string pattern2)) string))))))
これの問題点は、異常に長いグループがあった場合に Gauche の "regexp too large." エラーが出ることだ。はてどうする?

2 comments :

Anonymous said...

対応するカッコ、コッカだけからなるような言語は正規文法では表現できません。正規表現がいかに拡張されて強力になっているからといって、「正規表現でXMLをパースするなんてのがそもそも筋が悪いというか筋違い」(by Anonymous)ということなんじゃないでしょうか。。。

k16 said...

そういうことでいいんですね。ちょっと安心しました。こんな「いかにも」なパターンすら書けないのは自分が頭悪いからではないかという劣等感にさいなまれるところでした。

> 「正規表現でXMLをパースするなんてのがそもそも筋が悪いというか筋違い」

たいていは ssax:xml->sxml でS式になれば勝ったも同然なんですが、べたのテキストとして扱いたいことも少なくなくて、じゃあそのときにパーザを書くのかというと厳しいし、やっぱり正規表現が使えるというのは「何かと便利」ですね。