parsing - 如何手工计算FIRST集

Question

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

例子

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？

Answer 1

This page给出导出 FIRST(和 FOLLOW)集的机械规则。我将尝试解释这些规则背后的逻辑以及它们如何应用于您的示例。
第一套FIRST(u)是在 u 的完整推导中可以首先出现的终端集。 ，其中 u是终结符和非终结符的序列。换句话说，在计算 FIRST(u) 时设置，我们只寻找可能是可以从 u 派生的字符串的第一个终端的终端。 .
第一(aBA)
根据定义，我们可以看到 FIRST(aBA)减少到 FIRST(a) ，然后到 a .这是因为不管怎样A和 B制作是，终端a将始终首先出现在从 aBA 派生的任何事物中自 a是一个终端，不能从该序列的前面删除。
第一(公元前)
我要跳过FIRST(BB)现在转到 FIRST(Bc) .这里的情况有所不同，因为 B是一个非终端。起初，我们在 FIRST(B) 中说任何事情也在FIRST(S) .不幸的是，FIRST(B)包含 ε这会导致问题，因为我们可以有这样的场景

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

其中箭头是可能的推导/减少。一般来说，我们因此说 FIRST(Xu) ，其中 ε在 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)才不是。