2

我正在学习 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 中逻辑或的符号，而只是生成序列中字符的分隔符。

这样对吗？

4

1 回答 1

5

您可以将,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 使用深度优先搜索来找到解决方案，所以它可能需要尝试无限多个候选者才能在重新排序后找到解决方案。（在更专业的术语中，解决方案不会改变，但如果您重新排序目标，您的搜索可能不会终止）。

于 2013-05-15T15:39:49.477 回答