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

とりあえず問題をブレークダウンすると、こんな風に入れ子になっているパターンを正規表現でうまく補足できないかなあという話。

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." エラーが出ることだ。はてどうする？