句法分析 - 序言

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])。