2 ms·
I wrote a Jupyter notebook with an implementation of Derivatives of Regular Expressions in Python[1]. The Prolog version is pretty much just an encoding of the
by carapace 8y ago
I wrote a Jupyter notebook with an implementation of Derivatives of Regular Expressions in Python[1].
The Prolog version is pretty much just an encoding of the rules. This is an implementation of a two-symbol alphabet {01} (without "compaction" IIRC):
% Brzozowski's Derivatives of Regular Expressions
:- use_module(library(ordsets)).
:- use_module(library(tabling)).
dre(_, [], []).
dre(_, [""], []).
dre(0, ["1"], []).
dre(0, ["0"], [""]).
dre(1, ["0"], []).
dre(1, ["1"], [""]).
dre(C, kstar(R), cons(Rd, R)) :- dre(C, R, Rd).
dre(C, not_(R), not_(Rd) ) :- dre(C, R, Rd).
dre(C, and(R, S), and(Rd, Sd)) :- dre(C, R, Rd), dre(C, S, Sd).
dre(C, or(R, S), or(Rd, Sd)) :- dre(C, R, Rd), dre(C, S, Sd).
dre(C, cons(R, S), cons(Rd, S) ) :- nully(R, [] ), dre(C, R, Rd).
dre(C, cons(R, S), or(cons(Rd, S), Sd)) :- nully(R, [""]), dre(C, R, Rd), dre(C, S, Sd).
nully([], []).
nully([""], [""]).
nully([_], []).
nully(kstar(_), [""]).
nully(not_(R), [""]) :- nully(R, []).
nully(not_(R), []) :- nully(R, [""]).
nully( and(R, S), N) :- nully(R, Rn), nully(S, Sn), ord_intersect(Rn, Sn, N).
nully(cons(R, S), N) :- nully(R, Rn), nully(S, Sn), ord_intersect(Rn, Sn, N).
nully( or(R, S), N) :- nully(R, Rn), nully(S, Sn), ord_union(Rn, Sn, N).
[1] "∂RE: Brzozowski’s Derivatives of Regular Expressions" http://joypy.osdn.io/notebooks/Derivatives_of_Regular_Expressions.html http://joypy.osdn.io/notebooks/Derivatives_of_Regular_Expres...