对BNF文法和Prolog的DCG文法的几点质疑

Question

我正在学习Prolog中的文法，我对从经典的BNF文法到Prolog DCG文法形式的转换有一点怀疑。

例如，我有以下BNF语法：

::= a b
 ::= a  b

通过重写，生成以下类型的所有字符串：

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

在Ivan Bratko的书《人工智能的编程》中，他以这种方式将BNF语法转换为DCG语法：

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

乍一看，这似乎与经典的BNF语法形式非常相似，但我只对

DCG中使用的符号

这不是逻辑上的符号

或者

在Prolog中，但它只是生成序列中字符的分隔符。

对吗？

Answer 1

您可以阅读

在DCGs中作为

然后

或者

与连接

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

和

t -->
  [a,b].

是相同的：

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

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

这是不同的

在表示逻辑合取(AND)的非DCG/常规Prolog规则中：

a.
b.

u :-
 a,
 b.

?- u.
true.

即

在以下情况下为真

和

都是真的(这里就是这种情况)。

另一个不同之处还在于，谓词

不存在：

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

这样做的原因是语法规则

转换为Prolog谓词，但这需要额外的参数。评估语法规则的预期方法是使用

如上(

)。如果你愿意，我可以添加关于从DCG到普通规则的转换的解释，但如果你是Prolog的初学者，我不知道这是否太令人困惑。

附录:一个更好的例子应该是定义

作为：

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

其中，带有短语的求值结果出现在列表中

(这绝对不同于

)：

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

但是如果我们对规则中的目标进行重新排序，则谓词为真的情况永远不会改变(

*

)，所以在我们的例子中，定义

v :-
  b,
  a.

等同于

..。

(

*

)因为prolog使用深度优先搜索来找到解决方案，所以它可能需要尝试无限多个候选，然后才能在重新排序后找到解决方案。(在更专业的术语中，解决方案不会改变，但如果您重新排序目标，您的搜索可能不会终止)。