我不明白老师提供的示例之一。
例
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？
此页面提供了推导FIRST（和FOLLOW）集的机械规则。我将尝试解释这些规则背后的逻辑以及它们如何应用于您的示例。
FIRST(u)是的集合，可以在的全导数中首先出现u，其中u是终端和非终端的序列。换句话说，在计算FIRST(u)集合时，我们仅在寻找可能是的字符串的第一个终端的终端u。
给定定义，我们可以看到FIRST(aBA)减少到FIRST(a)，然后减少到a。这是因为无论A和B生产是什么，终端a都将始终首先出现，aBA因为a它是终端，并且不能从该序列的开头删除。
我现在暂时跳过FIRST(BB)并继续进行FIRST(Bc)。这里的情况有所不同，因为B它是非终结符。首先，我们说in中的任何FIRST(B)内容也都在中FIRST(S)。不幸的是，FIRST(B)包含ε可能导致问题的内容，因为我们可能遇到这种情况
FIRST(Bc)
-> FIRST(εc)
= FIRST(c)
= c
其中箭头是可能的推导/归约。一般来说，因此，我们说FIRST(Xu)，这里ε是FIRST(X)，等于(FIRST(X)\{ε}) ∪ FIRST(u)。这说明了计算中的最后两项。
使用上面的规则，我们现在可以得到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)没有出现。
本文收集自互联网，转载请注明来源。
如有侵权，请联系[email protected] 删除。
我来说两句