句法分析 - 序言

Question

我有一个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来自哪里？

Answer 1

看起来这是一个程序来确定列表是否具有形式。 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])。