正则表达式匹配Prolog

Question

我正在尝试进行正则表达式匹配.我已经写出了所有的功能,但是他们没有按照他们的意愿工作.据我所知,当我尝试比较列表时,它有一个问题.
例如,"re_contains(a,a)." 给出真实(显然),"re_contains(union(a,b),a)".

但是,只要我将其列为清单,它就会失败."re_contains(seq(a,b),[a,b])." 返回false.附加应该通过所有可能的组合来查找匹配,但这些功能都不能正常工作.这让我觉得我可能错过了一个基本案例.但我认为"re_contains(X,L): - X == L." 应该照顾它.我必须在这里寻找重要的东西.

这是我的代码:

re_contains(empty, []).

re_contains(X, L) :-
    X == L.

re_contains(seq(X, Y), L) :-
    append(L1, L2, L),
    re_contains(X, L1),
    re_contains(Y, L2). 

re_contains(union(X, _), L) :-
    re_contains(X, L).

re_contains(union(_, Y), L) :- 
    re_contains(Y, L).  

re_contains(kleene(X), L) :- 
    append([Car|L1], L2, L),
    re_contains(X, [Car|L1]),
    re_contains(kleene(X), L2).

re_contains(kleene(_),[]).

Answer 1

有几个问题.以下是最明显的:

打字. 你的谓词re_contains/2需要一个列表作为第二个参数.这re_contains(a,a).成功是相当巧合不是意图.

单调性.另一个问题是re_contains([a],[a])成功,但re_contains([X],[a])失败了.或者,从另一个角度看待它:re_contains([X],[a])失败,但X = a, re_contains([X],[a])成功.通过添加目标,X = a我们专门用于查询,因此最初失败的查询应该再次失败.

对identity(==/2)的测试应该用equality(=/2)替换,并确保我们有一些列表.所以:

re_contains(X, L) :-
    % X == L.
    X = L,
    append(X,_,_).

注意,append/3这里仅用于确保X是一个列表 - 不使用实际的附加功能.

效率.第三个问题涉及表示串联的实际方式.我们来看看以下规则:

re_contains(seq(X, Y), L) :-
    append(L1, L2, L),
    re_contains(X, L1),
    re_contains(Y, L2).

现在,假设我们这里有一个长度列表N.目标可能有多少答案append(L1, L2, L)？实际上N + 1.而这,无论涉及的实际价值如何.现在考虑:

?- length(L,1000000), time(re_contains(seq([a],[]),[b|L])).
% 2,000,005 inferences, 0.886 CPU in 0.890 seconds (100% CPU, 2258604 Lips)
false.

re_contains/2这里需要的时间与列表的长度成正比.但是,只要看看第一个元素就可以认识到这是不可能的.

所以背后的问题是使用append/3.Prolog有一个简单的经验法则:如果你使用过多append/3考虑使用dcg s - Definite Clause Grammars.请查看标签以获取更多详细信息 - 并参阅Prolog的介绍性文本.为了给你一个开始,这里是你定义的一个子集:

re_contains(RE, L) :-
    phrase(re(RE), L).

re([]) --> [].
re([E]) --> [E].
re(seq(X,Y)) -->
    re(X),
    re(Y).

哪个不再调查整个列表:

?- length(L,1000000), time(phrase(re(seq([a],[])),[b|L])).
% 6 inferences, 0.000 CPU in 0.000 seconds (88% CPU, 127313 Lips)
false.

顺便说一句,这是一个完整的定义.

终止/未结束.与效率相关的是终止的属性.理想情况下,如果可以有限地表示解集,则查询终止.也就是说,通过有限数量的答案.好的,这是我们正在努力的理想.当有限数量的答案可能时,Prolog的简单但非常有效的执行算法有时会循环.了解非终止的原因有时非常棘手.通常的调试策略 - 比如跟踪或逐步调试 - 都不起作用,因为它们向您显示了太多细节.幸运的是,有一种更好的技术:

我不会再看你的整个程序,而是只会看到它的一小部分.此片段是故障片(有关详细信息,请参阅链接).它要小得多,但对原始程序说了很多 - 只要这是一个纯粹的,单调的程序:

如果故障片未终止,则原始程序不会终止.

因此,如果我们找到这样的失败切片,我们可以立即得出关于整个程序的结论.甚至没有阅读其余的!

这是一个有趣的失败片:

...
re_contains(X, L) :- false,
    X = L
re_contains(seq(X, Y), L) :-
    append(L1, L2, L), false,
    re_contains(X, L1),
    re_contains(Y, L2).
re_contains(union(X, _), L) :- false,
    re_contains(X, L).
...

现在考虑目标re_contains(seq([],[]),L).理想情况下,应该只有一个答案L = [],目标应该终止.但是,它循环,因为append(L1, L2, L)不会终止.将其与上述终止的DCG解决方案进行对比phrase(re(seq([],[])),L).

Answer 2

append/3会分裂L,都L1和L2会名单.

我会尝试,以取代re_contains(X, L) :- X == L.与re_contains(X, [X]).

改变后,re_contains(a,a).将失败.

您以不同的方式表示序列,而您的匹配器不提供两者.实际上,唯一的"工作"案例不是序列.