Let's start Scheme

2011-12-15

正規表現実装中

ぶっちゃけ行き詰ったのでちょっと問題点の洗い出し。

出来てそうなこと
  • greedyマッチ
  • non-greedyマッチ
  • スタートとエンドアンカー
  • 単語境界
  • グループ(キャプチャリングとそうじゃないの含む)
  • 文字クラス
出来がやばそうなの
  • 肯定、否定先読み及び後読み
  • possessiveマッチ
やばそうなのもある程度は動いてるんだけど、パターンによっては簡単に無限ループに入る。
例えばこんなパターン
\D(?!123)
っで、"ABC123"を与えた場合、文字「C」にマッチしなければいけないが、マッチしない。また、パターンが
\D*(?!123)
になると無限ループする。(ほとんど出来て無いじゃん!)
原因は幅0を実装しているところにあって、2つ目のパターンだと、文字「A」は「\D」と否定先読みの両方を見る。っで、否定先読み(肯定でも)の条件にマッチすると、次の文字に行かずその場にとどまる(幅0の実装)。そうすると、結局文字列"ABCD123"の先頭から同じパターンを繰り返すので無限ループ突入となる。
っと、ここまで書いてちょっと解決案っぽいのが思いついた。要するに先にマッチしたものがあった場合にアサーションに突入しなければいいのではないだろうか?ちょっと試してみよう。

No comments:

Post a Comment