DEV Community

Exercise: Making a Simple Regex Engine

Amin Arria on August 05, 2018

I've started working for Lambdaclass and getting to know Erlang. As preparation for interviews with potential clients I got an assignment based on ...
Read full post
Collapse
 
stealthmusic profile image
Jan Wedel • • Edited

<3 for using Erlang. Although it may look strange people using C-Style syntax or other scripting languages, Erlang and the Erlang VM (BEAM) has a ton of great features and concepts that gets slowly added to other more popular languages.

I also love RegExs so that was a great read for me :)

You might mention, that most actual productive implementation do compile a regular expression on runtime to executable code for performance reasons.

Collapse
 
elfan7asma profile image
ElFantasma •

Hey, nice job.

Actually, you can fit it in less than 40 lines just reordering some of the clauses and using the fact that:

  case matching(Something) of
    true ->
      true;
    false ->
      matching(SomethingElse) 
  end

is equivalent to:

   matching(Something) orelse matching(SomethingElse)

since matching/2 returns a boolean.

Here's my (I believe equivalent) version:
(I used search and match names since they are similar to how python re module works, where search looks anywhere in the string and match has to match from the beginning of the string)

-module(regex).

-export([search/2, match/2]).

search(String, [$^ | Regex]) ->
  match(String, Regex);
search([Char | String], Regex = [_ | _]) ->
  search(String, Regex) orelse match([Char | String], Regex);
search(_String, _Regex) ->
  false.

match(_String, []) ->
  true;

match([], [$$]) ->
  true;

match(String, [Char | [$? | Regex]]) ->
  match(String, Regex) orelse match(String, [Char | Regex]);

match([_Char | String], [$. | [$* | Regex]]) ->
  match(String, Regex) orelse match(String, [$. | [$* | Regex]]);
match([Char | String], [Char | [$* | Regex]]) ->
  match(String, Regex) orelse match(String, [Char | [$* | Regex]]);
match(String, [_Char | [$* | Regex]]) ->
  match(String, Regex);

match([_Char | String], [$. | Regex]) ->
  match(String, Regex);

match([Char | String], [Char | Regex]) ->
  match(String, Regex);

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

match(_String, _Regex) ->
  false.

Haven't tested a lot of cases, but seems to be working. :)

Collapse
 
aminarria profile image
Amin Arria •

Nice catch!