關於BNF語法和Prolog的DCG語法的一些疑問

Question

我正在研究Prolog中的語法，我對從經典的BNF語法到Prolog DCG語法格式的轉換有疑問。

例如我有以下BNF語法：

<s> ::= a b 
<s> ::= a <s> b 

，通過改寫，生成類型的所有字符串：

ab 
aabb 
aaabbb 
aaaabbbb 
..... 
..... 
a^n b^n 

找上了伊萬·布拉科書編程人工智能他轉換這BNF語法以這種方式轉化爲DCG語法：

s --> [a],[b]. 
s --> [a],s,[b]. 

at af IRST看起來這似乎對我非常類似於經典的BNF語法形式，但我只有與在DCG

使用，符號懷疑這不是邏輯OR Prolog中，但它的象徵只是生成序列中字符的分隔符。

是不是？

Answer 1

可以作爲閱讀，在DCG中 「然後」/ 「級聯用」：

s --> 
    [a], 
    [b]. 

和

t --> 
    [a,b]. 

是一樣的：

?- phrase(s,X). 
X = [a, b]. 

?- phrase(t,X). 
X = [a, b]. 

這是不同於，在一個序言規則這意味着邏輯連詞：

a. 
b. 

u :- 
a, 
b. 

?- u. 
true. 

即，如果a和b爲真（這裏是這種情況），則u爲真。

另一個不同之處還在於，斷言S/0不存在：

?- s. 
ERROR: Undefined procedure: s/0 
ERROR:  However, there are definitions for: 
ERROR:   s/2 
false. 

這樣做的原因是，語法規則s的轉換爲一個序言謂詞，但這需要額外的參數。評估語法規則的預期方式是使用上面的短語/ 2（短語（startrule，List））。如果你願意，我可以添加關於從dcg到prolog的翻譯的解釋，但是我不知道如果你是prolog的初學者，這是不是太混亂。

附錄： 一個更好的實施例將是定義噸爲：

t --> 
    [b], 
    [a]. 

凡與短語結果列表中的[B，A]的評價（這是由[A，B絕對不同]）：

?- phrase(t,X). 
X = [b, a]. 

但是，如果我們重新排序規則中的目標，其中斷言是真的從來沒有在我們的例子中的變化（*），這樣的情況下，確定

v :- 
    b, 
    a. 

相當於你。（*）由於prolog使用深度優先搜索來尋找解決方案，可能會出現這樣的情況，它可能需要嘗試無限多個候選，然後才能在重新排序後找到解決方案。 （更具體地說，解決方案不會改變，但如果您重新排列目標，您的搜索可能不會終止）。