エクササイズ:シンプルなRegexエンジンの作り方

仕事を始めたLambdaclass そして、Erlangを知っていること.潜在的な顧客とのインタビューの準備として、私はこの記事に基づいて割り当てを得ました:Build a Regex Engine in Less than 40 Lines of Code . だから今私は試してみてErlangでそれを行うには、どのように行くか見てみましょう.

仕事
関数を作成するmatch/2 ) これは文字列と正規表現(文字列)を受け取り、true 、false を返します.Regexのすべてを使用することはできません.以下の小さなサブセットです.
構文
意味
例
マッチa指定した文字にマッチするkケイ.任意の文字にマッチします(改行を除く).A,B,C,D?前の文字の0または1にマッチしますaq?エー、AQ*前の文字の0以上b*「B、BB、BBB^文字列の先頭にマッチする^caCA$文字列の終端にマッチするeb$EB

考慮
ダイビングをする前にソリューションを設計する際に考慮した特定の考慮事項を確立するために必要なソリューションを作る.

与えられたregexは無効である( EG :"^*", "*?" )

単純な文字列を入力として期待しているので、改行文字の存在を無視することができます.このように. 何かにマッチ

空のregexは何もマッチmatch(SomeString, EmptyRegex) はfalse

match/2 私はどこか何か気にしないので、すぐにそれが何かに一致するように真を返すことができます.

問題を解決する
解決策の第一歩はベースケースを作成することでした.空文字列または空の正規表現は何も一致できません.

-module(regex).

-export([match/2]).

match([], _Regex) ->
  false;
match(_String, []) ->
  false;

次のステップでは、同じ文字にマッチするようにしました.

match([Char | String], [Char | Regex]) ->
  matching(String, Regex);
match([_Char | _String], [_OtherChar | _Regex]) ->
  false.

これをして、私は私がすでに誤りをしたとわかりましたmatch/2 関数は、match("hi", "hi") , しかし、失敗するmatch("oh hi", "hi") . 文字列内のすべての文字を出発点として、正規表現を使用して文字列と一致させる方法が必要でした.このためにmatch/2 私用するmatching/2 関数.成功すればmatch/2 を返しますが、失敗した場合はもう一度試してみますが、文字列の最初の文字を削除します.

match(String, Regex) ->
  case matching(String, Regex) of
    true ->
      true;
    false ->
      match(tl(String), Regex)
  end.

matching/2 は正規表現と文字列を消費して動作します.マッチがないときはいつでも、マッチは見つけられます.この節を追加し、既存の文字の一致を変更します.

matching(_String, []) ->
  true;
matching([], _Regex) ->
  false;

matching([Char | String], [Char | Regex]) ->
  matching(String, Regex);
matching([_Char | _String], [_OtherChar | _Regex]) ->
  false.

のために. 私はちょうどそれに対して文字列の任意の文字と一致して一致するように節を持っていた.

matching([_Char | String], [%. | Regex]) ->
  matching(String, Regex);

次のステップは、残りの特殊文字に取り組むことでした.私は^ and $ 簡単になるので、最初に.のために^ 私は、句を加えるだけでmatch/2 それをチェックして何でも返すmatching/2 戻り続けることはできません.のために$ 文字列が空であるかどうかをチェックする必要がありますtrue または空の返り値false .

match(String, [$^ | Regex]) ->
  matching(String, Regex);

...

matching([], [$$]) ->
  true;
matching(_String, [$$]) ->
  false;

今すぐハード部品、起動を開始? and * . いつものように、私は単純からdificultに行くことがベストであるので、始めましょう? . マッチしたときに文字列と正規表現の文字を消費する必要がありますが、正規表現の文字を消費しない場合だけです.

matching([Char | String], [Char | [$? | Regex]]) ->
  matching(String, Regex);
matching(String, [_OtherChar | [$? | Regex]]) ->
  matching(String, Regex);

最も美しいパターンのマッチングではなく、それは動作します.問題は、私たちに問題を残します.今、私たちは文字列がなくて、まだ正常にマッチすることができません.match("hi", "hio?") . この問題を解決するためには、? の場合は、次の文字と一致し続ける.

matching([], [_Char | [$? | Regex]]) ->
  matching([], Regex);
matching([], _Regex) ->
  false;

For * それは私たちが先に行くしない一致する場合を除き、そのほとんど同じですが、代わりに我々はそれが一致しないまで、それを呼び出し続ける.前のように、私はさらにストリングを持たないという問題にも走らせます、それで、私も同様に条項を加えなければなりません.
つの最後の問題.* . この組み合わせはすべての文字にマッチし、マッチを防ぐmatch("hello", ".*o") . これは本当に対処する良い方法を把握するのは難しい.最終的には.* 何も私と同じように行うことができますmatch/2 を使って、文字列を試したり消費したりするのと同じプロセスを使います.

matching(String, [$. | [$* | RemRegex]] = Regex) ->
  case matching(String, RemRegex) of
    true ->
      true;
    false ->
      matching(tl(String), Regex)
  end;

終わり
最後にかなり苦労して(そして40行以上のコード)私は単純な正規表現エンジンを完成させた.エッジケース、ベストパターンマッチの方法、および関数節の順序付けについて本当に興味深いことでした.以下の全モジュールのスニペットを残します.
あなたはいくつかの演習でerlangの学習に興味がある場合Erlings

-module(regex).

-export([match/2]).

match([], _Regex) ->
  false;
match(_String, []) ->
  false;
match(String, [$^ | Regex]) ->
  matching(String, Regex);
match(String, Regex) ->
  case matching(String, Regex) of
    true ->
      true;
    false ->
      match(tl(String), Regex)
  end.

matching(_String, []) ->
  true;

matching([], [$$]) ->
  true;
matching([], [_Char | [$? | Regex]]) ->
  matching([], Regex);
matching([], [_Char | [$* | Regex]]) ->
  matching([], Regex);
matching([], _Regex) ->
  false;

matching(_String, [$$]) ->
  false;

matching(String, [$. | [$* | RemRegex]] = Regex) ->
  case matching(String, RemRegex) of
    true ->
      true;
    false ->
      matching(tl(String), Regex)
  end;

matching([Char | String], [Char | [$? | Regex]]) ->
  matching(String, Regex);
matching(String, [_OtherChar | [$? | Regex]]) ->
  matching(String, Regex);

matching([Char | String], [Char | [$* | _RemRegex]] = Regex) ->
  matching(String, Regex);
matching(String, [_OtherChar | [$* | Regex]]) ->
  matching(String, Regex);

matching([_Char | String], [$. | Regex]) ->
  matching(String, Regex);
matching([Char | String], [Char | Regex]) ->
  matching(String, Regex);
matching([_Char | _String], [_OtherChar | _Regex]) ->
  false.