将小正则表达式转换为DCG

Question

我明白，Prolog程序员通常使用DCG而不是正则表达式来匹配字符串中的模式。在Perl中，有人可能会写

if ('... accd' =~ /a+b*c{2,4}d$/) { 
    say "matched"; 
} 

如何匹配Prolog中的相同模式？

Answer 1

我已经扩展this答案

:- op(100, xf, *). 
:- op(100, xf, +). 

rexp(C) --> [C]. 

rexp([T|Ts]) --> rexp(T), rexp(Ts). 
rexp([])  --> []. 

rexp(eps)  --> []. 

rexp(_*)  --> []. 
rexp(R*)  --> rexp(R), rexp(R*). 

rexp(R+)  --> rexp(R), rexp(R*). 

rexp((R1|R2)) --> (rexp(R1) ; rexp(R2)). 

rexp(range(R,N,M)) --> 
    {between(N,M,L), 
    length(D,L), 
    maplist(copy_term(R),D) 
    }, rexp(D). 

那么你的正则表达式匹配可能是

?- phrase(rexp([a+, b*, range(c,2,4), d]), [a,c,c,d]), 
    writeln(matched). 

注意，在这种方式，我们相匹配的原子，而不是单个字符。

编辑后假”的评论，我认为，第一条应改为

rexp(C) --> {atomic(C)}, [C]. 

避免例如

?- phrase(rexp([a+]), [a+]). 
true ; 

事实上，修正后，我们有预期的结果：

?- phrase(rexp([a+]), [a+]). 
false. 

做编辑

相反的解释正则表达式的模式可能是“硬编码”（很容易）

% I prefer the equivalent clause below 
% p1 --> "a", p1 ; "a", p2. 
p1 --> "a", (p1 ; p2). 
p2 --> "b", p2 ; p3. 
p3 --> ("cc" ; "ccc" ; "cccc"), "d". 

然后

?- phrase(p1, "accd"). 
true 

在这里，我们匹配单个字符（在Prolog的字符串是字符代码列表）