我有一个Definite Clause Grammar:S→a S b | ɛ。
这也写成以下规则:s --> [a], s, [b].
和s --> [].
这被翻译成Prolog如下:
s --> [a], s, [b]. became s([a|S2],R) :- s(S2,[b|R]).
s --> []. became s(S,S).
谁能告诉我S2的价值在哪里? S2来自哪里?
看起来这是一个程序来确定列表是否具有形式。 X 。 bn,其中n
的a
迭代,类似地,bn意味着n
的b
迭代。
s --> [a], s, [b]. becomes s([a|S2],R) :- s(S2,[b|R]).
s --> []. becomes s(S,S).
这里S2
是列表的中间位置,是列表的一部分可以绑定的自由变量。
命名为S2
完全是武断的。它也可以被称为S
。唯一不应该调用的是R
,因为它已经用于该语句中的另一个变量。
重要的是它所绑定的 - 列表的尾部。如果在以a
开头的任何列表上尝试此谓词,那么S2
将绑定到尾部。
举几个例子来说明一下:
如果输入是[a,a,b,b]
,S2
的值将是[a,b,b]
。
如果输入是[a]
,则S2的值将是空列表[]
。
如果输入是[a,x,y,z]
,S2
的值将是[x,y,z]
。
如果输入是[b,c,d,e]
,那么它将不匹配,并且S2
不会被绑定到任何东西;相反,谓词会失败。
请注意,[a,x,y,z]
实际上匹配谓词,尽管它不是形式的谓词。 X 。 BN。
该规则仅查看第一个项目a
,以及匹配的通知。所以它派生出s([x,y,z],[b|R])
。然后它会尝试继续验证输入。只有在后来的推导步骤中才会注意到[x,y,z]
不是以a
开头的。
让我们一步一步来看看。
s([a,x,y,z],R) :- s([x,y,z],[b|R]).
这是有效的,Prolog将S2绑定到[x,y,z]
。s([x,y,z],R)
,但它无法与s([a|S2])
匹配,因为它不是以a
开头,所以这次规则失败了。s(S,S)
。它填写:s([x,y,z],[x,y,z]).
有了这个,它回到它早先的调用,并试图匹配s([x,y,z],[x,y,z])
与其早期的规则s([x,y,z],[b|R])
。[x,y,z]
上的[b|R]
匹配,因为它不是以b
开头的。这就是规则失败的地方 - Prolog已经确定字符串不是an.bn形式。要了解如何使用R
,让我们看一下匹配的列表。
s([a,a,b,b],R):-s([a,b,b],[b|R]). /* We haven't got a value for R yet. */
s([a,b,b],R):-s([b,b],[b|R]). /* We haven't got a value for R yet. */
s([b,b],[b,b]). /* Stop condition for the recursion. */
此时,右侧将被实例化为[b,b]
。
Prolog在上一步中有s([a,b,b],[b|R])
,它现在可以通过设置R=[b]
来取得成功。
然后它进一步展开递归,填充规则右侧的值并将这些值应用于左侧。最终它返回到它开始的位置,并具有值s([a,a,b,b],[a,a,b,b])
。