正則表達式匹配序言

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

append/3會分裂L，都L1和L2會列出。

我會嘗試用re_contains(X, [X]).

變更後更換re_contains(X, L) :- X == L.，re_contains(a,a).將失敗。

您以不同的方式表示序列，而您的匹配器不提供這兩種方法。事實上，唯一的案件'工作'是而不是序列。

Answer 2

有幾個問題。這裏最明顯的是：

打字。 您的謂詞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我們已經專門化了查詢，因此最初失敗的查詢應該再次失敗。

身份（==/2）測試應通過平等更換（=/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 —定義語句語法。請查看代碼以獲取更多詳細信息—並查閱介紹性的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. 

BTW，here是一個完整的定義。

終止/不終止。與效率相關的是終止的財產。理想情況下，如果一組解決方案可以有限地表示，則查詢終止。也就是說，通過有限數量的答案。好的，那是我們追求的理想。當有限數量的答案成爲可能時，Prolog的簡單但非常高效的執行算法有時會循環。瞭解非終止的原因有時非常棘手。通常的調試策略–像調試器–跟蹤或逐步通過不起作用，因爲它們顯示你太多的細節。幸運的是，還有更好的技術：

而不是看你的整個程序，我只會再看看它的一小部分。這個片段是一個failure slice（更多細節見鏈接）。它是小得多，但告訴了很多關於原始程序—前提是這是一個純粹的，單調的程序：

如果失敗片沒有終止，那麼原始程序不會終止。

所以如果我們發現這樣一個失敗片段，我們可以立即對整個程序做出結論。甚至沒有閱讀其餘的！

這裏有這樣一個有趣的故障片：

 
... 
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)。