dre.erl

-module(dre).

-compile(export_all).

-type re() :: empty
            | eps
            | {char,Value::char()}
            | {cat,Left::re(),Right::re()}
            | {alt,This::re(),That::re()}
            | {rep,InnerRE::re()}.

re_to_sum(RE) ->
    (fix(fun re_to_sum/2, []))(RE).

re_to_sum(empty, _Self) ->
    [];
re_to_sum(eps, _Self) ->
    [eps];
re_to_sum({char,_}=RE, _Self) ->
    [{RE,eps}];
re_to_sum({cat,Left,Right}, Self) ->
    lists:flatmap(
        fun (eps) ->
                Self(Right, Self);
            ({LeftLeft,LeftRight}) ->
                [{LeftLeft,{cat,LeftRight,Right}}]
        end,
        Self(Left, Self));
re_to_sum({alt,This,That}, Self) ->
    Self(This, Self) ++ Self(That, Self);
re_to_sum({rep,InnerRE}=RE, Self) ->
    Self({alt,{cat,InnerRE,RE},eps}, Self).

fix(F, Bottom) ->
    fun (V) -> F(V, fix(F, Bottom, V)) end.

fix(F, Bottom, X) ->
    fun (V, _Self) when X =:= V -> Bottom;
        (V,  Self)              -> F(V, fix(Self, Bottom, V))
    end.