构造FIRST集和FLLOW集,并构造预测分析表
时间: 2024-03-17 08:41:11 浏览: 59
first、follow集合以及预测分析表
对于给定的文法,我们可以按照如下步骤来构造 FIRST 集和 FOLLOW 集以及预测分析表:
文法如下:
```
S -> A
A -> aB | bA | ε
B -> cC | dB | ε
C -> eC | ε
```
1. 首先,我们可以先求出每个非终结符能够推导出的所有可能的 FIRST 集。具体来说,对于每个非终结符 X,我们可以按照如下步骤来求出 FIRST(X):
- 如果 X 可以直接推导出 ε,则 ε 属于 FIRST(X)。
- 如果 X 可以直接推导出一个终结符 a,则 a 属于 FIRST(X)。
- 如果 X 可以直接推导出一个非终结符 Y,并且 Y 不可以推导出 ε,则 FIRST(Y) 中的所有终结符都属于 FIRST(X)。
- 如果 X 可以直接推导出一个非终结符 Y,并且 Y 可以推导出 ε,则 FIRST(Y) 中除了 ε 以外的所有终结符都属于 FIRST(X)。如果还存在其他的非终结符 Z,使得 Y 可以直接推导出 Z 且 Z 不能推导出 ε,则 FIRST(Z) 中的所有终结符也属于 FIRST(X)。
根据上述规则,我们可以求出每个非终结符的 FIRST 集:
```
FIRST(S) = {a}
FIRST(A) = {a, b, ε}
FIRST(B) = {c, d, ε}
FIRST(C) = {e, ε}
```
2. 接下来,我们可以求出每个非终结符的 FOLLOW 集。具体来说,对于每个非终结符 X,我们可以按照如下步骤来求出 FOLLOW(X):
- 如果 X 是文法的开始符号,则 $ 符号属于 FOLLOW(X)。
- 如果存在一个产生式 A -> αXβ,则把 FOLLOW(A) 中除了 ε 以外的所有符号加入到 FOLLOW(X) 中。
- 如果存在一个产生式 A -> αXβ,并且 X 可以推导出 ε,则把 FOLLOW(A) 中的所有符号都加入到 FOLLOW(X) 中。
根据上述规则,我们可以求出每个非终结符的 FOLLOW 集:
```
FOLLOW(S) = {$}
FOLLOW(A) = {c, d, $}
FOLLOW(B) = {e, c, d, $}
FOLLOW(C) = {c, d, $}
```
3. 最后,我们可以根据求出的 FIRST 集和 FOLLOW 集来构造预测分析表。预测分析表的行对应于文法的非终结符,列对应于文法的终结符(加上一个特殊的“结束符号”$),每个格子中存储了一个产生式。具体来说,对于每个产生式 A -> α,我们可以把它添加到所有能够推导出 FIRST(α) 中的终结符对应的格子中。如果 FIRST(α) 中包含 ε,则把它添加到所有能够推导出 FOLLOW(A) 中的终结符对应的格子中。
根据上述规则,我们可以构造出如下的预测分析表:
```
a b c d e $
S A - - - - -
A aB bA - - - ε
B - - cC dB ε ε
C - - eC - ε ε
```
预测分析表中的“-”表示该格子为空。例如,预测分析表中的第一行表示:如果当前读入的符号是 a,则使用产生式 S -> A 进行推导;如果当前读入的符号是 b,则无法使用任何产生式进行推导。
阅读全文