句法分析 - 序言

Question

我有一个定从句语法：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从哪里来？

Answer 1

看起来这是一个确定列表是否为 aⁿ 形式的程序。 X 。 bⁿ，其中 aⁿ 表示 a 的 n 次迭代，类似地，bⁿ 表示 b.

的 n 次迭代

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] 实际上匹配谓词，尽管它不是 aⁿ 的形式。 X 。 bⁿ.
该规则仅查看第一项 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 已经决定字符串不是 aⁿ.bⁿ 的形式。

要了解如何使用 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].
使其成功然后它进一步展开递归，填充规则右侧的值并将这些值应用于左侧。最终它 returns 到它开始的地方，并具有值 s([a,a,b,b],[a,a,b,b])。

句法分析 - 序言

Syntactic analysis - prolog

prolog

dcg