Rui:正規表現の拡張

Rui:正規表現の拡張

(?<=...)

Perlにある戻り読み(lookbehind)を実装しようとしている。PerlやRubyの戻り読みは、固定長のパターン((?<=re)のreが固定長)しか許容しないということになっているが、可変長のパターンも使えるようにしたい。

可変長のパターンをサポートするには2つの方法が考えられる。

  1. 戻り読みアサーションがある場所から1文字ずつ戻り、戻った場所からパターンがマッチするかを順方向に向かって試す
  2. 逆向きになった文字列にマッチするようパターンを変換し、戻り読みアサーションのある場所から文字列の先頭に向かってマッチを試す

(1)はマッチの失敗に指数時間かかることがあるので却下。(2)の方法で実装をしてみた。逆向きに進むVM命令を新たに定義して、それを使うようパターンをコンパイルすればよい。これで、簡単なパターン((?<=\s+)a)など)に対してはきちんと動作するものができた。

問題は「一度掴んだら離さない」マッチ((?>re))である。(?>a*)aは順方向に試すとどのような文字列にもマッチしないが、これを愚直にひっくり返してa(?>a*)を得ると、aを含む文字列にマッチしてしまう。戻り読みの中では(?>re)はサポートしないか、意味が違うということにすればいいかと思ったが、逆向きに進む貪欲なマッチを定義し、それが文字列の順方向にマッチする場合、即座にバックトラックすれば、うまく動く気もする。試してみよう。

なお、これをサポートしたい理由は、サポートすることによりre1 re2がマッチする限り常に(?<=re1) re2もマッチし、逆もまた真であることが保証できるからである。後読み((?=re))の場合にはこれが保証されているわけだし、そっちのほうがわかりやすいと思う。

(2006/02/06 06:10:55 PST)

「一度掴んだら離さない」パターンと戻り読みの関係についてその後少し考えてみて、上で書いている方針はやめることにした。上記のように、/re1 re2/と/(<?=re1) re2/とが同じようにマッチしてするならそれに越したことはないと思うが、実際にはそのようにうまくはマッチしてくれない。マッチの順番が重要な場合には、(?<=...)の中では右から左にマッチが進むという事実を無視できないのだ。

たとえば/(a*)(a*)/という正規表現を"aaa"にマッチさせると、$1は"aaa"、$2は""である。戻り読みを使ったパターン/(?<=(a*)(a*))/がそれと同じ結果になるためには、2番目の(a*)がnon-greedyに動作しなければならない。さもなければ、2番目の(a*)がすべてを飲み込んでしまって、$1が""、$2が"aaa"なってしまう。一般的には、(?<=...)の中ではデフォルトがnon-greedyでないといけないということになりそうだ。

ところが、デフォルトをnon-greedyにするとうまくいかない場合もある。たとえば、/(a*)b/を"aab"にマッチさせると$1は"aa"になるが、/(?<=(a*))b/のa*がnon-greedyだと、$1は""になってしまう。

もしかしたら、(?<=...)の中のパターンをうまくマッチさせる方法があるのかもしれないが、考えつかなかったので、とりあえず方針を決めないことにして、(?<=...)の中で(?>...)が現れた場合はエラーにすることにしてしまった。

次はconditional pattern ((?(condition)yes-pattern|no-pattern))と、named subpattern ((?P<name>))かなぁ。パフォーマンスのことも気になるけど、そちらに手をつけるにはかなりお勉強が必要になりそう。

(2006/02/07 05:26:54 PST)

Named subpatternを追加した。次はバックリファレンス("\1"など)をサポートし、最後にconditional patternをサポートすることにしようと思う。

最適化についてはちょっと調べただけでもいろんなテクニックがあるのがわかった。これを実装するなら、GaucheのSchemeコンパイラと同じように、Schemeでコンパイラを書くのがいいのかもしれない。なんにせよ勉強不足なので、すぐ取りかかるってわけにはいかなさそう。最適化テクニックをまとめてる論文か何かないですかね?

(2006/02/09 08:47:50 PST)

バックリファレンスのためにcapturing bracketに手を入れたら少し動作が変わってしまった。いままで複数回マッチする場合は最初の1つがキャプチャされていたのだが、最後のものがキャプチャされるようになった。具体的には/(.)*/を"abc"にマッチさせたとき、いままでは$1が"a"だったのだが、手元のコードでは最後の文字の"c"が返ってくる。もとの動作にするのも簡単なんだが、いまのキャプチャの振る舞いはPerlと同じなので、そっちのほうがいいんじゃないだろうかとも思える。Perlの正規表現とこの違いがあるのには気づいていて、そのときちょっと戸惑ったのだった。しかしなにがいいのか微妙。

ところで、前から考えていたのだけど、最初か最後の1つではなく、カッコにマッチした文字列をリストで返してくれるマッチャーがあったら便利ではないだろうか? たとえば((#/(.)*/ "abc") 1)が'("a" "b" "c")を返すような作りにするのである。この例は実用的ではないけど、CSVのようなリストになっている文字列をさっさとパーズしてしまうのに使えるんじゃないのかな。既存のコードとの互換性を保つために、`l'などといった修飾子で機能を有効にするのがいいかもしれない。

(2006/02/10 05:38:06 PST)

Perl 6のパターンマッチ関連の提案についてまとめた文書を見つけた。Apocalypse 5: Pattern Matching (日本語訳)。可変長のlookbehind (RFC 72)や、複数回マッチするグループがリストを返すようにする(RFC 360)といった提案がすでになされていて、Larry Wallのコメントがついている。Larry Wallのコメントはやっぱり参考になりますね。しかしこのリストにある提案、Perl 6ではなくPerl 5で、互換性を保ちつつ実現してくれたらいいのに。

で、複数回(正確には2回以上)マッチする可能性のあるカッコでキャプチャした文字列を、リストで返す機能を実装してみた。CSVのフィールドを分解する例。

(define re #/^?s*("(?:[^"]|"")*"|[^,]*?)(?:?s*,?s*("(?:[^"]|"")*"|[^,]*?))*?s*$/)
(rxmatch-let (re "foo, bar baz, ?"quoted, field?"")
    (#f col1 col2)
  (cons col1 col2))

;; => ("foo" "bar baz" "?"quoted, field?"")

フィールドの前後にあるダブルクオートは本来はフィールドではないので、取り除かなければいけないのだけど、ここではサボっている。図らずも正規表現でぜんぶやろうとすると大変だというひとつの例になってしまったりして。

(2006/03/07 22:23:21 PST)

木村さんからApocalypse 5の日本語訳を教えてもらいました。 ApocalypseExgegisSynopsis。拡張を行ったパッチを公開しました(メーリングリストのアーカイブ)。上にいろいろ書いてありますが、結局、可変長の戻り読みを除いて普通のPerl 5互換(+名前つきグループ)の正規表現としてまとめました。

(2006/05/31 09:17:49 PDT)

上記のパッチはGauche 0.8.7に取り込まれました。

More ...