String rewriting (SRS) in Prolog using DCGs

string_rewriting.pl

rewrite(L, R), [Skip] --> [Skip], rewrite(L, R).        % Skip the current head.
rewrite(L, R), R --> L.                                 % Match the current prefix and return.
rewrite(Rules) --> {member(L-R, Rules)}, rewrite(L, R). % Try a single rule.

normalize(P) --> P, normalize(P). % If at first you succeed, try, try again.
normalize(P) --> \+P.             % P failed so list remains the same.

% Single-step rewrite with {"ab"->"x", "ca"->"y"}:
% ?- phrase(rewrite([[a,b]-[x], [c,a]-[y]]), [a,b,c,a,b,c], Out).
% Out = [a, b, c, x, c] ;
% Out = [x, c, a, b, c] ;
% Out = [a, b, y, b, c] ;
% false.

% Keep rewriting until no more steps are possible with {"ab"->"x", "ca"->"y"} (use setof/3 to dedup, or equivalently once/1 if the SRS is confluent):
% ?- normalize(rewrite([[a,b]-[x], [c,a]-[y]]), [a,b,c,a,b,c], Out).
% Out = [x, c, x, c] ;
% Out = [x, c, x, c] ;
% Out = [x, y, b, c] ;
% Out = [x, y, b, c] ;
% false.