什么是 FIRST 和 FOLLOW，它们是如何计算的？

FIRST 和 FOLLOW 是两个与语法相关的函数，可以帮助我们填充 M 表的条目。

FIRST () - 它是一个函数，它给出了从产生式规则派生的字符串开始的终端集。

符号 c 在 FIRST (α) 中当且仅当对于某个语法符号序列 β α ⇒ cβ。

终结符 a 在 FOLLOW (N) 中当且仅当存在从文法的起始符号 S 的派生使得 S ⇒ αNαβ，其中 α 和 β 是（可能为空的）文法符号序列。换句话说，如果 c 可以在推导中的某个点跟随 N，则终端 c 在 FOLLOW (N) 中。

FIRST ( ) 和 FOLLOW ( ) 的好处

• 可以用来证明文法的LL(K)特性。

• 可用于促进预测解析表的构建。

• 它为递归下降解析器提供选择信息。

FIRST 的计算

FIRST (α) 被定义为终端符号的集合，这些终端符号是从 α 派生的字符串的第一个字母。

FIRST (α) = {α |α →∗ αβ 对于某些字符串 β }

如果 X 是语法符号，那么 First (X) 将是 -

• 如果 X 是终结符，则FIRST(X)= {X}

• 如果 X → ε，则FIRST(X)= {ε}

• 如果 X 是非终结符 & X → a α，则 FIRST (X) = {a}

• 如果 X → Y ₁ , Y ₂ , Y ₃，则 FIRST (X) 将是

(a) 如果 Y 是终结点，则

      第一 (X) = 第一 (Y ₁ , Y ₂ , Y ₃ ) = {Y ₁ }

(b) 如果 Y ₁是非终结符且

      如果 Y ₁不导出为空字符串，即，如果 FIRST (Y ₁ ) 不包含 ε，则 FIRST (X) = FIRST (Y ₁ , Y ₂ , Y ₃ ) = FIRST(Y ₁ )

(c) 如果 FIRST (Y ₁ ) 包含 ε，则。

     FIRST (X) = FIRST (Y ₁ , Y ₂ , Y ₃ ) = FIRST(Y ₁ ) − {ε} ∪ FIRST(Y ₂ , Y ₃ )

类似地，FIRST (Y ₂ , Y ₃ ) = {Y ₂ }，如果 Y ₂是终结符，否则如果 Y ₂是非终结符，则

• FIRST (Y ₂ , Y ₃ ) = FIRST (Y ₂ )，如果FIRST (Y ₂ ) 不包含ε。

• 如果 FIRST (Y ₂ ) 包含 ε，则

• FIRST (Y ₂ , Y ₃ ) = FIRST (Y ₂ ) − {ε} ∪ FIRST (Y ₃ )

类似地，对于进一步的语法符号，即对于Y ₄、Y ₅、Y ₆ ... ，将重复该方法。ÿ _ķ。

FOLLOW的计算

Follow (A) 定义为直接出现在 A 右侧的终结符的集合。

FOLLOW(A) = {a|S ⇒* αAaβ 其中 α, β 可以是任何字符串}

查找规则 FOLLOW

• 如果S是起始符号，FOLLOW(S)={$}

• 如果生产形式为 A → α B β，则 β ≠ ε。

(a) 如果 FIRST (β) 不包含 ε，则 FOLLOW (B) = {FIRST (β)}

或者

(b) 如果 FIRST (β) 包含 ε（即 β ⇒* ε），则

        跟随 (B) = 第一 (β) − {ε} ∪ 跟随 (A)

∵ 当 β 导出 ε 时，则 A 之后的终结点将跟随 B。

• 如果生产形式为 A → αB，则 Follow (B) ={FOLLOW (A)}。