5

我不明白我的导师提供的例子之一。

例子

S ::= aBA | BB | Bc
A ::= Ad | d
B ::= ε

我们有

FIRST(B) = FIRST(ε)
         = {ε}

FIRST(A) = FIRST(Ad) ∪ FIRST(d)
         = FIRST(A) ∪ {d}
         = {d}

FIRST(S) = FIRST(aBA) ∪ FIRST(BB) ∪ FIRST(Bc)
         = FIRST(a) ∪ (FIRST(B)\{ε}) ∪ FIRST(B) ∪ (FIRST(B)\{ε) ∪ FIRST(c)
         = {a, ε, c}

为什么在 FIRST(S) 计算中有 FIRST(B)？难道不应该

(FIRST(B)\{ε)?

为什么 FIRST(S) 计算中缺少 A？

4

1 回答 1

11

本页给出了派生 FIRST（和 FOLLOW）集的机械规则。我将尝试解释这些规则背后的逻辑以及它们如何应用于您的示例。

第一套

FIRST(u)是可以在 的完全推导中首先出现的终端集合u，其中u是终端和非终端的序列。换句话说，在计算FIRST(u)集合时，我们只寻找可能是可以从 派生的字符串的第一个终端的终端u。

第一（aBA）

给定定义，我们可以看到FIRST(aBA)减少到FIRST(a)，然后到a。这是因为无论AandB产生式是什么，终结a符总是首先出现在任何派生自的东西中，aBA因为a是终结符，并且不能从该序列的前面删除。

第一（公元前）

我现在要跳过FIRST(BB)并继续FIRST(Bc)。这里的情况有所不同，因为B是非终端。起初，我们说任何 inFIRST(B)也是 in FIRST(S)。不幸的是，FIRST(B)包含ε导致问题的原因，因为我们可能会遇到这种情况

   FIRST(Bc)
-> FIRST(εc)
=  FIRST(c)
=  c

其中箭头是可能的推导/归约。一般而言，我们因此说FIRST(Xu), where εis in FIRST(X), 等于(FIRST(X)\{ε}) ∪ FIRST(u)。这解释了计算中的最后两项。

第一（BB）

使用上述规则，我们现在可以导出FIRST(BB)为(FIRST(B)\{ε}) ∪ FIRST(B)。同样，如果我们在计算，FIRST(BBB)我们会将其减少为

  FIRST(BBB)
= (FIRST(B)\{ε}) ∪ FIRST(BB)
= (FIRST(B)\{ε}) ∪ (FIRST(B)\{ε}) ∪ FIRST(B)

值得注意的是，在计算 FIRST 集合时，符号序列中的最后一个符号永远不会从中删除空字符串，因为此时，空字符串是合理的可能性。这可以在您的示例中的可能推导中看到：

   S
-> BB
-> εε
-> ε

希望您可以从以上所有内容中看到为什么FIRST(B)出现在您的计算中而FIRST(A)没有出现。

于 2013-10-28T15:13:23.270 回答