へびにっき

みんな大好き正規表現が13章で初登場。Erlangのregexpモジュールについて調べてみた。

（追記：コメント欄にて、PCREベースの新しい正規表現モジュール re の存在を教えてもらいました。こちらも後で調べてみます）

実装・性能

regexpモジュールはErlnagで実装されている。code:which(regexp) でソースファイルを探してコメントを読んでみると、NFAに変換せずに独自の内部表現とパターンマッチで実装されているらしい（その方がずっと速いから、とのこと）。内部表現は regexp:parse を使って確認することができる。

erlang> regexp:parse("xxx|yyy").
{ok,{'or',{concat,{concat,120,120},120},
          {concat,{concat,121,121},121}}}

この実装を読み解いてみるのも面白いかも知れない。

ただし独自実装の宿命として、機能は貧弱だし遅い。本家ドキュメントのEfficiency Guide 3.1にも Don’t use the regexp module in time-critical code. と書いてある。

マッチの性質

正規表現によるマッチを行う関数として、match と first_match という2種類の関数が用意されている。

• first_match は最も左でマッチした結果を返す（最左マッチ）
• match は文字列中の全ての位置でマッチを行い、最も長くマッチした結果を返す

erlang> regexp:first_match("xx xxxx xxxxxx", "x+").
{match,1,2}
erlang> regexp:match("xx xxxx xxxxxx", "x+").
{match,9,6}

first_match の方が速いので、単にマッチするかどうか調べるだけなら first_match を使った方が良い。

またどちらの関数も、その位置でマッチする最長のものを見つけようとする（最長マッチ）。

erlang> regexp:first_match("xxxxyyyy", "x+(yy)?(yyyy)?").
{match,1,8}

よって first_match は、いわゆるPOSIX NFAと同じ最長最左マッチを行うことになる。これは perl や ruby など従来型NFAとは異なる動作である。

irb> $& if /x+(yy)?(yyyy)?/ =~ "xxxxyyyy"
=> "xxxxyy"

lib_find:files/5 の改善

『13.8 findユーティリティ』に出てくる lib_find:files/5 がイマイチだと感じたので、自分なりに修正してみた。以下の点を変更している。

• regexp:match/2 の代わりに regexp:first_match/2 を使うようにした
• accumulator の処理を lists:foldl/3 に委託した
• マッチ対象を「ファイルの完全パス」から「ファイル名」に変更した

files(Dir, RegExp, Recursive, Fun, Acc0) ->
    foldl(fun(F, Acc) ->
		  FullPath = filename:join([Dir, F]),
		  case file_type(FullPath) of
		      regular ->
			  apply_if_match(Fun, FullPath, Acc, F, RegExp);
		      directory when Recursive =:= true ->
			  files(FullPath, RegExp, Recursive, Fun, Acc);
		      _ ->
			  Acc
		  end
	  end,
	  Acc0,
	  case file:list_dir(Dir) of
	     {ok, Files} -> Files;
	      _          -> []
	  end).
 
apply_if_match(Fun, Arg1, Acc, Str, RegExp) ->
    case regexp:first_match(Str, RegExp) of
	{match, _, _} -> Fun(Arg1, Acc);
	_             -> Acc
    end.