test_re2.erl

-module(test_re2).

-compile(export_all).

-type word() :: list().
-type phi() :: 'phi'.
-type empty() :: 'empty'.
-record(letter, {l :: char()}).
-record(choice, {left, right}).
-record(seq, {left, right}).
-record(star, {exp}).

-type regexp() :: phi() | empty() | #letter{} | #choice{} | #seq{} | #star{}.

-record(pvar, {v :: integer(),
               word :: word(),
               re :: regexp()}).
-record(ppair, {left :: tuple(),
                right :: tuple()}).
-record(pchoice, {left :: tuple(),
                  right :: tuple()}).

-type env() :: [{integer(), word()}].

-type pat() :: #pvar{} | #ppair{} | #pchoice{}.

-spec match(regexp(), word()) -> bool().
match(E, []) ->
    accepts_empty(E);
match(E, [C|W1]) ->
    match(part_deriv(E, C), W1).

-spec accepts_empty(regexp()) -> bool().
accepts_empty(phi) ->
    false;
accepts_empty(empty) ->
    true;
accepts_empty(#choice{left=L, right=R}) ->
    case accepts_empty(L) of
        true ->
            true;
        false ->
            accepts_empty(R)
    end;
accepts_empty(#seq{left=L, right=R}) ->
    case accepts_empty(L) of
        false ->
            false;
        true ->
            accepts_empty(R)
    end;
accepts_empty(#star{exp=_}) ->
    true;
accepts_empty(#letter{l=_}) ->
    false.

-spec part_deriv(regexp(), char()) -> regexp().
part_deriv(phi, _) ->
    phi;
part_deriv(empty, _) ->
    phi;
part_deriv(#letter{l=C1}, C1) ->
    empty;
part_deriv(#letter{l=_}, _) ->
    phi;
part_deriv(#choice{left=R1, right=R2}, C) ->
    #choice{left=part_deriv(R1, C), right=part_deriv(R2, C)};
part_deriv(#seq{left=R1, right=R2}, C) ->
    R = #seq{left=part_deriv(R1, C), right=R2},
    case accepts_empty(R1) of
        true ->
            #choice{left=R, right=part_deriv(R2, C)};
        false ->
            R
    end;
part_deriv(#star{exp=R}=Rs, C) ->
    #seq{left=part_deriv(R, C), right=Rs}.

-spec test() -> true.
test() ->
    true = match(#choice{left=#letter{l=$a}, right=#star{exp=#letter{l=$b}}}, "bbb").

-spec pat_match(pat(), word()) -> [env()].
pat_match(P, [C|W]) ->
    pat_match(pd_pat(P, C), W);
pat_match(#pvar{v=X, word=W, re=R}, []) ->
    case accepts_empty(R) of
        true -> [[{X, W}]];
        false -> []
    end;
pat_match(#pchoice{left=P1, right=P2}, []) ->
    pat_match(P1, []) ++ pat_match(P2, []);
pat_match(#ppair{left=P1, right=P2}, []) ->
    [Xs ++ Ys || Xs <- pat_match(P1, []),
                 Ys <- pat_match(P2, [])].

-spec long_pat_match(pat(), word()) -> env() | 'none'.
long_pat_match(Pat, Word) ->
    case pat_match(Pat, Word) of
        [H|_] -> H;
        _ -> none
    end.

-spec short_pat_match(pat(), word()) -> env() | 'none'.
short_pat_match(Pat, Word) ->
    case pat_match(Pat, Word) of
        [] -> none;
        L when is_list(L) -> lists:last(L)
    end.

-spec pd_pat(pat(), char()) -> pat().
pd_pat(#pvar{v=X, word=W, re=R}, C) ->
    #pvar{v=X, word=W ++ [C], re=part_deriv(R, C)};
pd_pat(#ppair{left=P1, right=P2}, C) ->
    Pn = #ppair{left=pd_pat(P1, C), right=P2},
    case accepts_empty(strip(P1)) of
        true ->
            #pchoice{left=Pn, right=#ppair{left=mk_emp_pat(P1), right=pd_pat(P2, C)}};
        false ->
            Pn
    end;
pd_pat(#pchoice{left=P1, right=P2}, C) ->
    #pchoice{left=pd_pat(P1, C), right=pd_pat(P2, C)}.

-spec strip(pat()) -> regexp().
strip(#pvar{re=R}) ->
    R;
strip(#ppair{left=P1, right=P2}) ->
    #seq{left=strip(P1), right=strip(P2)};
strip(#pchoice{left=P1, right=P2}) ->
    #choice{left=strip(P1), right=strip(P2)}.

-spec mk_emp_pat(pat()) -> pat().
mk_emp_pat(#pvar{v=X, word=W, re=R}) ->
    case accepts_empty(R) of
        true ->
            #pvar{v=X, word=W, re=empty};
        false ->
            #pvar{v=X, word=W, re=phi}
    end;
mk_emp_pat(#ppair{left=P1, right=P2}) ->
    #ppair{left=mk_emp_pat(P1), right=mk_emp_pat(P2)};
mk_emp_pat(#pchoice{left=P1, right=P2}) ->
    #pchoice{left=mk_emp_pat(P1), right=mk_emp_pat(P2)}.

ex() ->
    Choice = #choice{left=empty, right=#letter{l=$B}},
    #ppair{left=#pvar{v=1, word=[],
                      re=#star{exp=#letter{l=$A}}},
           right=#pvar{v=2, word=[],
                       re=Choice}}.

-spec ptest() -> 'true'.
ptest() ->
    Ex = ex(),
    [{1, "A"}, {2, []}] = long_pat_match(Ex, "A"),
    [{1, "A"}, {2, "B"}] = long_pat_match(Ex, "AB"),
    true.