如何手动计算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

该页面给出了导出FIRST(和FOLLOW)集的机械规则.我将尝试解释这些规则背后的逻辑以及它们如何应用于您的示例.

第一集

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

FIRST(ABA)

鉴于定义,我们可以看到FIRST(aBA)减少到FIRST(a),然后到a.这是因为,无论什么A和B生产是,终端a总是首先出现在源自什么aBA,因为a是一个终端,并且不能从该序列的前去除.

FIRST(BC)

我现在要跳过去继续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).这解释了计算中的最后两个术语.

FIRST(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)不会出现.