编译原理冲刺 · 第 06 课 ⏱ 冲刺模式 · ≤1周

FIRST 集 与 FOLLOW 集

全课程最重要的计算技能。对应教材第 4 章 4.3。
🎯 本课唯一目标
给一个文法,能准确、机械地求出每个非终结符的 FIRST 集、FOLLOW 集(以及 SELECT 集)。
为什么学它? 这是 LL(1)、预测分析表的"发动机"。几乎每年必考,而且后面 L07 直接拿它来填分析表。把这一课练到不用想就能写,后面两课白送。

一、FIRST 集

FIRST(α) = α 能推出的所有串的第一个终结符的集合;若 α 能推出空串(α⇒*ε),就把 ε 也放进去[1]

⚑ 求 FIRST 的规则

① 终结符 a:FIRST(a)={a}

② 对 X→Y₁Y₂…Yk:把 FIRST(Y₁)\{ε} 加入;若 ε∈FIRST(Y₁) 再看 Y₂……;若所有 Yᵢ 都含 ε,则 ε∈FIRST(X)。

X→ε:ε∈FIRST(X)。

二、FOLLOW 集

FOLLOW(A)(只对非终结符)= 在各种句型中,紧跟在 A 后面的终结符集合;若 A 可能出现在句型的最右端,就把结束符 # 放进去。

⚑ 求 FOLLOW 的规则(反复迭代到不再变化)

#∈FOLLOW(S)(S 是开始符号)。

② 对 B→αAβ:把 FIRST(β)\{ε} 加入 FOLLOW(A)。

③ 若 β⇒*ε(或 β 为空,即 B→αA):把 FOLLOW(B) 加入 FOLLOW(A)。

⚠️ 注意:FOLLOW 集里永远不会有 ε,只有终结符和 #。

三、SELECT 集(连接到 LL(1))

SELECT(A→α) =  FIRST(α)           若 ε∉FIRST(α)
              (FIRST(α)\{ε})∪ FOLLOW(A)   若 ε∈FIRST(α)

四、老师示范一题(必考文法)

例题 求下面文法各非终结符的 FIRST 与 FOLLOW 集。(即 L05 消除左递归后的表达式文法)
E → T E′      E′ → + T E′ | ε      T → F T′      T′ → * F T′ | ε      F → (E) | i
求 FIRST(从只含终结符的 F 往上推):
FIRST(F) = { ( , i }            (F→(E) 给 ( ;F→i 给 i)
FIRST(T) = FIRST(F) = { ( , i } (T→FT′,F 不推空)
FIRST(E) = FIRST(T) = { ( , i }
FIRST(E′) = { + , ε }           (E′→+TE′ 给 + ;E′→ε 给 ε)
FIRST(T′) = { * , ε }
非终结符FIRSTFOLLOW
E( , i) , #
E′+ , ε) , #
T( , i+ , ) , #
T′* , ε+ , ) , #
F( , i* , + , ) , #
FOLLOW 怎么来的(挑几条关键的):
FOLLOW(E):E 是开始符 ⇒ # ;F→(E) 里 E 后面是 ) ⇒ )         ∴ { ) , # }
FOLLOW(T):E→TE′,T 后是 E′,FIRST(E′)\ε = {+} ⇒ + ;
           E′ 能推 ε,故再并入 FOLLOW(E)={ ),# }              ∴ { + , ) , # }
FOLLOW(F):T→FT′,F 后是 T′,FIRST(T′)\ε = {*} ⇒ * ;
           T′ 能推 ε,故再并入 FOLLOW(T)={ +,),# }            ∴ { * , + , ) , # }
💡 易错点:FOLLOW(F) 一定要算到 {*,+,),#} 四个——很多人漏掉 + 和 )(它们是 T′ 可推空后"穿透"上来的)。

五、你来做

1. FIRST(α) 中含有 ε,表示什么?
2. FOLLOW(S)(S 为开始符号)一定含有?
3. 对 B→αAβ 且 β 能推出 ε,要把什么加入 FOLLOW(A)?
4. 对示范文法,FOLLOW(F) = ?
5. 当 ε∈FIRST(α) 时,SELECT(A→α) 等于?
得分:0 / 5
FIRST 看"开头",FOLLOW 看"屁股后面"
FOLLOW 先给 S 放 #;右邻能推空就把左部的 FOLLOW 接上来
📺 主源推荐 哈工大《编译原理》语法分析讲(FIRST/FOLLOW 部分)— 中国大学MOOC[1]
🙋 这是最关键的一课。强烈建议:自己另找一个文法把 FIRST/FOLLOW 算一遍,发我核对。算错一个集合,L07 的分析表就全错了。
  1. [1] FIRST/FOLLOW/SELECT 定义与求法:陈火旺《程序设计语言编译原理》4.3;交叉印证 龙书讲义。该表达式文法的集合为经典标准结果。