first集和follow集的求法

在编译原理中，First集和Follow集是用于构造语法分析表的两个重要概念。其中，First集是指文法符号串中第一个终结符号的集合，而Follow集是指在文法符号串中某个非终结符号后面可能出现的结符号的集合。下面是它们的求法：

1. First集的求法：
- 如果X是一个终结符号，则First(X) = {X}。
- 如果X是一个非终结符号，则将X产生的所有符号串的First集合并，即First(X) = First(α)，其中X → α。
- 如果X可以推导出ε，则将ε加入First(X)中。

2. Follow集的求法：
- 对于文法的开始符号S，将#加入Follow(S)中。
- 对于文法中的每个产生式A → αBβ，将Follow(A)加入Follow(B)中。
- 对于文法中的每个产生式A → αB，或者产生式A → αBβ且ε∈First(β)，将Follow(A)加入Follow(B)中。

下面是一个综合例子，求解文法符号串E的First集和Follow集：

E → TE'
E' → +TE' | ε
T → FT'
T' → *FT' | ε
F → (E) | id

- 求解First(E)：
- First(T) = {(, id)}
- First(E') = {+, ε}
- First(E) = First(T) ∪ First(E') = {(, id, +, ε)}

- 求解Follow(E)：
- 将#加入Follow(E)中。
- 对于产生式T → FT'，将Follow(T)加入Follow(T')中，即{(, id, +, #)}
- 对于产生式E → TE'，将Follow(E)加入Follow(T)，即{(, id)}
- 对于产生式T' → *FT'，将Follow(T')加入Follow(F)，即{*, (, id)}
- 对于产生式E' → +TE'，将Follow(E')加入Follow(T')，即{+, *, (, id)}
- 对于产生式F → (E) ，将Follow(F)加入Follow(E')，即{+, *, ), #, (, id}
- 对于产生式F → id ，将Follow(F)加入Follow(E')，即{+, *, ), #, (, id}