Role of FIRST & FOLLOW Sets

• FIRST and FOLLOW sets have a role to play in both the parsing strategies covered in this module, as you will see
• Given a rule, what are the set of terminals that could appear as the first terminal of strings derived by that rule? This is the FIRST set
  • FIRST 集：某个符号串最终能推导出来的串中，最左边第一个可能出现的终结符有哪些
• Given a rule, what are the set of terminals that could appear immediately after a string derived by that rule? This is the FOLLOW set
  • FOLLOW 集：某个非终结符推导出来之后，它后面紧接着可能出现哪些终结符

Construct FIRST(α)

1. If X₁ is a terminal → add X₁ to FIRST(α)
2. If X₁ is a non-terminal → add FIRST(X₁) to FIRST(α)
3. If X₁ ⇒ ε (null production) → continue to consider X₂, and so on...

注意：如果某个非终结符能推出 ε，那么 FIRST 的计算就不能只看第一个符号

简化版理解：算一个串的 FIRST，按顺序从左往右看：

• 先看第一个符号
• 如果它可能为空，再看第二个
• 一直看到某个“不能空”的符号为止。

Construct FOLLOW(X)

1. Put EOF ($) in FOLLOW (distinguished symbol / start symbol)
   1. 把 EOF 放进开始符号的 FOLLOW 集
2. If production: Y → α X β → add FIRST(β) \ {ε} to FOLLOW(X)
   1. 若有产生式 $Y→αXβ$，把 FIRST($β$) 加入 FOLLOW(X)
3. If production: Y → α X OR Y → α X β with β ⇒ ε → add FOLLOW(Y) to FOLLOW(X)
   1. 若有产生式 $Y→αX$，或者 $Y→αXβ$ 且 $β⇒ε$，那么把 FOLLOW($Y$) 加入 FOLLOW($X$)

FOLLOW 只看 X 后面有什么：

• 如果 X 已经在句尾，或者后面的东西能空，就把左边产生式头部的 FOLLOW 传给它
• 后面若跟非终结符，就加那个非终结符的 FIRST
• 后面若直接跟终结符，就加那个终结符