编译原理first集合和follow集合的求法例子

假设有以下文法：

S -> AaB | bCD
A -> ε | a
B -> b | ε
C -> c | ε
D -> d | ε

下面我们来求文法中各个符号的First集合和Follow集合。

1. 求各符号的First集合：

- 非终结符号A的First集合：{a, ε}
- 非终结符号B的First集合：{b, ε}
- 非终结符号C的First集合：{c, ε}
- 非终结符号D的First集合：{d, ε}
- 终结符号a的First集合：{a}
- 终结符号b的First集合：{b}
- 终结符号c的First集合：{c}
- 终结符号d的First集合：{d}

产生式的First集合如下：

- First(S -> AaB) = First(A) ∪ {a} = {a, ε}
- First(S -> bCD) = {b}
- First(A -> ε) = {ε}
- First(A -> a) = {a}
- First(B -> b) = {b}
- First(B -> ε) = {ε}
- First(C -> c) = {c}
- First(C -> ε) = {ε}
- First(D -> d) = {d}
- First(D -> ε) = {ε}

2. 求各符号的Follow集合：

- 非终结符号S的Follow集合：{#}
- 非终结符号A的Follow集合：{a, b, c, d, #}
- 非终结符号B的Follow集合：{c, d, #}
- 非终结符号C的Follow集合：{d, #}
- 非终结符号D的Follow集合：{#}

产生式的Follow集合如下：

- Follow(S) = {#}
- Follow(A -> ε) = Follow(A -> aB) = Follow(S) = {#}
- Follow(B -> ε) = Follow(S) ∪ Follow(A -> aB) = {#, a, b, c, d}
- Follow(C -> ε) = Follow(S) ∪ Follow(B -> bCD) = {#, a, b, c, d}
- Follow(D -> ε) = Follow(S) ∪ Follow(B -> bCD) ∪ Follow(C -> cD) = {#, a, b, c, d}

以上就是对于该文法中各符号的First集合和Follow集合的求法。