立即學習Prolog！ DCG練習示例

Question

我一直在通過Learn Prolog Now!進行自學，現在我正在學習有關定義語句的文法。我在實際會議的任務中遇到了一些困難。 The task讀取：

正式語言^Ñ b ^2米Ç^2米 d ^Ñ由下列形式的所有字符串的：依次不間斷的塊的一個秒的完整塊 b的隨後的ç秒的完整塊，隨後的 d秒的完整塊， S，從而使所述一個和 d塊是完全相同的長度，並且Ç和 d塊也完全一樣的長度和分別小號還包括一個偶數的Ç S和 d的。例如，＆epsilon;， abbccd，和 aaabbbbccccddd都屬於一個^Ñ b ^2米Ç^2米 d ^Ñ。寫一個生成這種語言的DCG。

我能夠編寫生成^ň d ^ñ規則，B ^2米Ç^2米，甚至^ň b ^2米和c ^2米 d ^ñ ...但我似乎無法將所有這些規則加入到ⁿ b ^2m c ^2m d ⁿ。以下是我的規則，可以生成ⁿ d ⁿ和b ^2m c ^2m。

s1 --> []. 
s1 --> a,s1,d. 
a --> [a]. 
d --> [d]. 

s2 --> []. 
s2 --> c,c,s2,d,d. 
c --> [c]. 
d --> [d]. 

是一個^ň b ^2米Ç^2米 d ^ň真的CFG，並有可能只使用了什麼的教訓教（沒有額外的參數或代碼寫DCG等）？如果是這樣，任何人都可以提供一些指導我如何加入這些，以便我可以解決給定的任務？

Answer 1

@Timothy，你的答案的工作，但它會產生重複：

?- length(S,_), s(S,[]). 
S = [] ; 
S = [a, d] ; 
S = [a, d] ;   % XXX 
S = [b, b, c, c] ; 
S = [a, a, d, d] ; 
S = [a, a, d, d] ;  % XXX 

這樣就可以消除一個條款是固定的，留下DCG：

s --> x. 
s --> a,s,d. 

x --> []. 
x --> b,b,x,c,c. 

% a, b, c, d the same 

這產生：

?- length(S,_), s(S,[]). 
S = [] ; 
S = [a, d] ; 
S = [b, b, c, c] ; 
S = [a, a, d, d] ; 
S = [a, b, b, c, c, d] ; 
S = [a, a, a, d, d, d] ; 
S = [b, b, b, b, c, c, c, c] ; 
S = [a, a, b, b, c, c, d, d] ; 
S = [a, a, a, a, d, d, d, d] ; 

Answer 2

如何像：

n(L,N) --> n(L,N,0). 

n(_,N,N) --> [], !. 
n(L,N,K) --> L, {K1 is K + 1}, n(L, N, K1). 

abbccd(N,M) --> 
    {M1 is 2*M}, 
    n("a",N), 
    n("b",M1), 
    n("c",M1), 
    n("d",N). 

gen :- 
    forall((
      between(1,4,N), 
     between(1,4,M), 
     phrase(abbccd(N,M),S), 
     string_to_atom(S,A) 
      ), 
      writeln(A)). 

執行：

?- gen. 
abbccd 
abbbbccccd 
abbbbbbccccccd 
abbbbbbbbccccccccd 
aabbccdd 
aabbbbccccdd 
aabbbbbbccccccdd 
aabbbbbbbbccccccccdd 
aaabbccddd 
aaabbbbccccddd 
aaabbbbbbccccccddd 
aaabbbbbbbbccccccccddd 
aaaabbccdddd 
aaaabbbbccccdddd 
aaaabbbbbbccccccdddd 
aaaabbbbbbbbccccccccdddd 
true. 

Answer 3

我相信我想通了...

s --> x. 
s --> a,d. 
s --> a,s,d. 

x --> []. 
x --> b,b,x,c,c. 

a --> [a]. 
b --> [b]. 
c --> [c]. 
d --> [d]. 

?- s([],[]). 
Yes 

?- s([a,b,c,c,d],[]). 
No 

?- s([a,a,a,b,b,c,c,d,d,d],[]). 
Yes 

這是一件有趣的事情看的解決方案，並認爲，「我絞盡腦汁想了是？」但我想這是學習新東西的樂趣的一半，特別是當它像邏輯程序來自命令式編程背景時。