关于BNF文法和Prolog的DCG文法的一些疑惑

Question

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

例如，我有以下 BNF 语法：

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

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

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

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

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

乍一看，这在我看来与经典的 BNF 语法形式非常相似，但我只怀疑DCG 中使用的,符号

这不是Prolog 中逻辑OR的符号，而只是生成序列中字符的分隔符。

这样对吗？

Answer 1

您可以读取,DCG 中的，然后或与 连接：

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

和

t -->
  [a,b].

是一样的：

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

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

它与,非 DCG/常规 Prolog 规则不同，这意味着逻辑与（AND）：

a.
b.

u :-
 a,
 b.

?- u.
true.

ieu为真，如果a且b为真（这里就是这种情况）。

另一个区别还在于谓词s/0不存在：

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

这样做的原因是语法规则s被转换为 Prolog 谓词，但这需要额外的参数。评估语法规则的预期方法是使用phrase/2如上 ( phrase(startrule,List))。如果您愿意，我可以添加有关从 DCG 到普通规则的翻译的解释，但如果您是 Prolog 的初学者，我不知道这是否太混乱。

附录：一个更好的例子是定义t为：

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

带有短语的评估结果在列表中的位置[b,a]（绝对不同于[a,b]）：

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

但是如果我们对规则中的目标重新排序，谓词为真的情况永远不会改变 (*)，因此在我们的情况下，定义

v :-
  b,
  a.

相当于u。

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