什么是 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→Y1,Y2,Y3，则FIRST(X)将是

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

第一(X)=第一(Y1,Y2,Y3)={Y1}

(b)如果Y1是非终结符且

如果Y1不导出为空字符串，即，如果FIRST(Y1)不包含ε，则FIRST(X)=FIRST(Y1,Y2,Y3)=FIRST(Y1)

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

FIRST(X)=FIRST(Y1,Y2,Y3)=FIRST(Y1)−{ε}∪FIRST(Y2,Y3)

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

FIRST(Y2,Y3)=FIRST(Y2)，如果FIRST(Y2)不包含ε。

如果FIRST(Y2)包含ε，则

FIRST(Y2,Y3)=FIRST(Y2)−{ε}∪FIRST(Y3)

类似地，对于进一步的语法符号，即对于Y4、Y5、Y6...，将重复该方法。ÿķ。

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)}。