句法分析 - 序言

Question

我有一个明确的语句语法：S→a S b | ɛ。

这也写成如下规则：s --> [a], s, [b].和s --> [].

这被翻译成序言如下：

s --> [a], s, [b]. became s([a|S2],R) :- s(S2,[b|R]). 
s --> [].   became s(S,S). 

有人可以告诉我什么S2的价值就在这里？ S2从哪里来？

Answer 1

它看起来像是一个程序，以确定一个列表的形式是一个ⁿ。 X 。 b ^Ñ，其中^Ñ装置n迭代a，并且类似地，B ^Ñ装置的bn迭代。

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 。 b ⁿ。
该规则仅查看第一项a，并注意到相符。所以它派生出s([x,y,z],[b|R])。然后它会尝试继续验证输入。只有在稍后的派生步骤中，它才会注意到[x,y,z]不以a开头。

让我们一步步地经历这一过程。

• 首先，我们必须：
  s([a,x,y,z],R) :- s([x,y,z],[b|R]). 这工作和前导结合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已经决定该字符串的格式不是ⁿ .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]使其成功。
然后，它进一步展开递归，为规则的右侧填充值并将这些值应用于左侧。最终它返回到它开始的位置，并具有值s([a,a,b,b],[a,a,b,b])。