parsing - 关于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 的书 Programming for Artificial Intelligence 他以这种方式将此 BNF 文法转换为 DCG 文法:

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

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

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

是吗？

Answer 1

您可以将 DCG 中的 , 读取为 and then 或 concatenated with:

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.

即如果 a 和 b 为真(这里就是这种情况)，则 u 为真。

另一个区别也是谓词 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 使用深度优先搜索来寻找解决方案，因此在重新排序后找到解决方案之前，它可能需要尝试无限多的候选者。 (用更专业的术语来说，解决方案不会改变，但如果您重新排序目标，您的搜索可能不会终止)。