檢查是否字符串包含在語言（序言）

這是CFG：檢查是否字符串包含在語言（序言）

S -> T | V 
T -> UU 
U -> aUb | ab 
V -> aVb | aWb 
W -> bWa | ba

所以這會接受某種形式的：

{a^n b^n a^m b^m | n,m >= 1} U {a^n b^m a^m b^n | n,m >= 1}

這裏是我的代碼有工作：

in_lang([]). 
in_lang(L) :- 
    mapS(L), !. 

mapS(L) :- 
    mapT(L) ; mapV(L),!. 

mapT(L) :- 
    append(L1, mapU(L), L), mapU(L1), !. 

mapU([a|T]) :- 
    ((append(L1,[b],T), mapU(L1)) ; (T = b)),!. 

mapV([a|T]) :- 
    ((append(L1,[b],T), mapV(L1)) ; 
    (append(L1,[b],T), mapW(L1))), 
    !. 

mapW([b|T]) :- 
    ((append(L1,[a],T), mapW(L1)) ; 
    (T = a)), 
    !.

截至目前，這是出於以下三個字符串返回false：

[a,a,b,b,a,b] // this should be true 
[a,a,a,b,b,a,a,b,b,b] // this should be true as well 
[a,a,a,b,b,a,b,b,b] // this one IS false

任何幫助或洞察力將不勝感激，我對Prolog不太舒服，因此自己調試一直是一個挑戰。

來源

2016-04-25 csh1579

所有這些切割（'！'），它們是幹什麼用的？謂詞定義的最後一個切點是非常強烈的代碼味道。 – 2016-04-25 15:39:29

首先，請注意這個代碼是沒有意義的：

... append(L1, mapU(L), L) ...

在Prolog有謂詞，而不是函數...

一個CFG產生式規則（非終端）應該「吃」一些令牌，而在Prolog中，這意味着您至少需要2個參數：輸入令牌列表，以及生產成功匹配相關輸入部分後剩下的參數。

即，附加/ 3不是必需的：只是模式匹配，通過統一運算符（=）進行/ 2

mapS(L1, L) :- mapT(L1,L) ; mapV(L1,L). 
mapT(L1, L) :- mapU(L1,L2), mapU(L2,L). 
mapU(L1, L) :- L1=[a|L2], mapU(L2,L3), L3=[b|L] ; L1=[a,b|L]. 
... complete the translation

然後調用它：

?- mapS([a,a,b,b,a,b],R). 
R = [] ; 
false.

R = []意味着整個序列已匹配...

來源

2016-04-25 17:39:18 CapelliC

在mapT的定義中，您試圖使用mapU的「返回值」作爲append的參數。但mapU是一個謂詞，謂詞沒有返回值。相反，人們通常用一個未綁定的變量來寫謂詞，謂詞綁定到所需的「返回值」。在predciate被證明之後，現在綁定的變量可以用於後續的謂詞。

來源

2016-04-25 15:48:30

我最初嘗試做T1是mapU（L），mapU（T1）。然而，這一直拋出一個異常，指出「錯誤是/ 2：類型錯誤：'[]'預期，發現'[a，a，b，b，a，b]'（」x「必須包含一個字符）「，我不太清楚如何解決這個問題，同時仍然使用一個未綁定的變量。 – csh1579

從這個描述中你完全不清楚你試圖做什麼，更不用說它爲什麼不起作用。也許如果你展示了實際的代碼，而不僅僅是一個不明身份的描述。 –

只需使用dcg！和library(double_quotes)。

:- set_prolog_flag(double_quotes, chars). 

s --> t | v. 
t --> u, u. 
u --> "a",u,"b" | "ab". 
v --> "a",v,"b" | "a",w,"b". 
w --> "b",w,"a" | "ba". 

| ?- use_module(library(double_quotes)). 

| ?- length(L,N), phrase(s, L). 
L = "abab", N = 4 ? ; 
L = "abab", N = 4 ? ; 
L = "aabbab", N = 6 ? ; 
L = "abaabb", N = 6 ? ; 
L = "aababb", N = 6 ? ; 
L = "abbaab", N = 6 ? ; 
L = "aaabbbab", N = 8 ? ; 
L = "aabbaabb", N = 8 ? ; 
L = "abaaabbb", N = 8 ? ; 
L = "aaababbb", N = 8 ? ...

來源

2016-04-25 15:58:12 false

這不會成爲一個家庭作業的問題，不是嗎？ –

@ScottHunter至少從1965年到1972年，人們無意中涉足這個問題：如何恰當地編碼一種語法。他們都嘗試了一些類似append的野獸。我們不要讓這個黑暗時刻永存。自1972年夏天以來，沒有任何藉口！ – false

因此，OP對dcg的明顯無知並不意味着它可能不會被使用？將CFG翻譯成dcg是一項非常簡單的練習，這使得它成爲一個很好的*解決方案*，但糟糕的*作業*。這是我的觀點。 –

檢查是否字符串包含在語言（序言）

回答

相關問題