课上不努力、课后徒伤悲。好好听网课，好好学习！

<!--more-->

### FIRST 集合

#### 定义

FIRST(X) 是 X 所有可能推导的开头终结符号或可能推导的`ε`所构成的集合。

#### 构造 FIRST 集合

对于每个非终结符或终结符 X 连续使用以下规则，直至每个 X 的 FIRST 集合不再增大为止

1. 若左边第一个符号是**终结符**或者是**ε**，将其放在 FIRST(X) 中;
2. 若左边第一个符号是**非终结符**，将其 FIRST 集合中**非ε**元素加入 FIRST(X) 中;
3. 若左边第一个符号是**非终结符**而且紧随其后有很多**非终结符**，要注意是否有**ε**;
  1. 若第 i 个非终结符的 FIRST 集中有ε，则把第 i+1 个非终结符的 FIRST 集合除ε的元素加入 FRIST(X);
  2. 若所有非终结符的 FIRST 集中都有ε，则把ε加入 FIRST(X);

重复使用以上规则，直至每个 X 的 FIRST 集合不再增大为止。

#### 例题

> 对于文法 G(E):
>
> > $$E-> TE^{\prime} $$
> >
> > $$E^{\prime}-> +TE^{\prime} |ε $$
> >
> > $$T->FT^{\prime}$$
> >
> > $$T^{\prime}->*FT^{\prime}|ε$$
> >
> > $$F->(E)|i$$
>
> 构造每个非终结符的 FIRST 集合

我们使用上述规则进行构造

##### 第一轮

###### E-> TE1

左边第一个是非终结符、紧随其后的也是终结符符合`2`,`3`规则，但是他们的 FISRT 集合都为空。

| $$FIRST\{E\}$$ | $$FIRST\{E^{\prime}\}$$ | $$FIRST\{T\}$$ | $$FIRST\{T^{\prime}\}$$ | $$FIRST\{F\}$$ |
| :------------: | :---------------------: | :------------: | :---------------------: | :------------: |
|                |                         |                |                         |                |

###### E1-> +TE1|ε

规则 `1`：左边第一个是终结符和**ε**，将他们放进 FIRST\{E1}集中

| $$FIRST\{E\}$$ | $$FIRST\{E^{\prime}\}$$ | $$FIRST\{T\}$$ | $$FIRST\{T^{\prime}\}$$ | $$FIRST\{F\}$$ |
| :------------: | :---------------------: | :------------: | :---------------------: | :------------: |
|                |          +，ε           |                |                         |                |

###### T->FT1

规则`2`: 将 FIRSR{F}中的**非ε**元素加入 FIRST(T)，FIRST{T}为空

规则`3`:FIRST{T}和 FIRST{F1}为空

| $$FIRST\{E\}$$ | $$FIRST\{E^{\prime}\}$$ | $$FIRST\{T\}$$ | $$FIRST\{T^{\prime}\}$$ | $$FIRST\{F\}$$ |
| :------------: | :---------------------: | :------------: | :---------------------: | :------------: |
|                |          +，ε           |                |                         |                |

###### T1->*FT1|ε

规则`1`:将 *，ε加入 FIRST{T1}

| $$FIRST\{E\}$$ | $$FIRST\{E^{\prime}\}$$ | $$FIRST\{T\}$$ | $$FIRST\{T^{\prime}\}$$ | $$FIRST\{F\}$$ |
| :------------: | :---------------------: | :------------: | :---------------------: | :------------: |
|                |          +，ε           |                |          *，ε           |                |

###### F->(E)|i

规则`1`:将（，i 加入 FIRST{F}

| $$FIRST\{E\}$$ | $$FIRST\{E^{\prime}\}$$ | $$FIRST\{T\}$$ | $$FIRST\{T^{\prime}\}$$ | $$FIRST\{F\}$$ |
| :------------: | :---------------------: | :------------: | :---------------------: | :------------: |
|                |          +，ε           |                |          *，ε           |     （，i      |

FIRST 集合还在增大所以继续下一轮

##### 第二轮

###### E-> TE1

规则`2`: FISRT{T}为空

规则`3`:   FISRT{T}为空

不变

| $$FIRST\{E\}$$ | $$FIRST\{E^{\prime}\}$$ | $$FIRST\{T\}$$ | $$FIRST\{T^{\prime}\}$$ | $$FIRST\{F\}$$ |
| :------------: | :---------------------: | :------------: | :---------------------: | :------------: |
|                |          +，ε           |                |          *，ε           |     （，i      |

###### E1-> +TE1|ε

规则 `1`：左边第一个是终结符和**ε**，将他们放进 FIRST\{E1}集中。不变

| $$FIRST\{E\}$$ | $$FIRST\{E^{\prime}\}$$ | $$FIRST\{T\}$$ | $$FIRST\{T^{\prime}\}$$ | $$FIRST\{F\}$$ |
| :------------: | :---------------------: | :------------: | :---------------------: | :------------: |
|                |          +，ε           |                |          *，ε           |     （，i      |

###### T->FT1

**规则`2`: 将 FIRSR{F}中的非ε元素加入 FIRST(T) 变化了。**

规则`3`:FIRST{F}没有ε，不用考虑了。不变

| $$FIRST\{E\}$$ | $$FIRST\{E^{\prime}\}$$ | $$FIRST\{T\}$$ | $$FIRST\{T^{\prime}\}$$ | $$FIRST\{F\}$$ |
| :------------: | :---------------------: | :------------: | :---------------------: | :------------: |
|                |          +，ε           |     （，i      |          *，ε           |     （，i      |

###### T1->*FT1|ε

规则`1`:将 *，ε加入 FIRST{T1}。不变

| $$FIRST\{E\}$$ | $$FIRST\{E^{\prime}\}$$ | $$FIRST\{T\}$$ | $$FIRST\{T^{\prime}\}$$ | $$FIRST\{F\}$$ |
| :------------: | :---------------------: | :------------: | :---------------------: | :------------: |
|                |          +，ε           |     （，i      |          *，ε           |     （，i      |

###### F->(E)|i

规则`1`:将（，i 加入 FIRST{F}不变

| $$FIRST\{E\}$$ | $$FIRST\{E^{\prime}\}$$ | $$FIRST\{T\}$$ | $$FIRST\{T^{\prime}\}$$ | $$FIRST\{F\}$$ |
| :------------: | :---------------------: | :------------: | :---------------------: | :------------: |
|                |          +，ε           |     （，i      |          *，ε           |     （，i      |

有变化，继续从头开始扫描

##### 第三轮

###### E-> TE1

**规则`2`: 把 FISRT{T}放入 FISRT{E}中** 有变化

规则`3`:   FISRT{T}中没有**ε**，不用管

| $$FIRST\{E\}$$ | $$FIRST\{E^{\prime}\}$$ | $$FIRST\{T\}$$ | $$FIRST\{T^{\prime}\}$$ | $$FIRST\{F\}$$ |
| :------------: | :---------------------: | :------------: | :---------------------: | :------------: |
|     （，i      |          +，ε           |     （，i      |          *，ε           |     （，i      |

###### E1-> +TE1|ε

规则 `1`：左边第一个是终结符和**ε**，将他们放进 FIRST\{E1}集中。不变

| $$FIRST\{E\}$$ | $$FIRST\{E^{\prime}\}$$ | $$FIRST\{T\}$$ | $$FIRST\{T^{\prime}\}$$ | $$FIRST\{F\}$$ |
| :------------: | :---------------------: | :------------: | :---------------------: | :------------: |
|     （，i      |          +，ε           |     （，i      |          *，ε           |     （，i      |

###### T->FT1

规则`2`: 将 FIRSR{F}中的非ε元素加入 FIRST(T)。已经放过了

规则`3`:FIRST{F}没有ε，不用考虑了。不变

| $$FIRST\{E\}$$ | $$FIRST\{E^{\prime}\}$$ | $$FIRST\{T\}$$ | $$FIRST\{T^{\prime}\}$$ | $$FIRST\{F\}$$ |
| :------------: | :---------------------: | :------------: | :---------------------: | :------------: |
|     （，i      |          +，ε           |     （，i      |          *，ε           |     （，i      |

###### T1->*FT1|ε

规则`1`:将 *，ε加入 FIRST{T1}。不变

| $$FIRST\{E\}$$ | $$FIRST\{E^{\prime}\}$$ | $$FIRST\{T\}$$ | $$FIRST\{T^{\prime}\}$$ | $$FIRST\{F\}$$ |
| :------------: | :---------------------: | :------------: | :---------------------: | :------------: |
|     （，i      |          +，ε           |     （，i      |          *，ε           |     （，i      |

###### F->(E)|i

规则`1`:将（，i 加入 FIRST{F}不变

| $$FIRST\{E\}$$ | $$FIRST\{E^{\prime}\}$$ | $$FIRST\{T\}$$ | $$FIRST\{T^{\prime}\}$$ | $$FIRST\{F\}$$ |
| :------------: | :---------------------: | :------------: | :---------------------: | :------------: |
|     （，i      |          +，ε           |     （，i      |          *，ε           |     （，i      |

有变化，继续从头开始扫描

##### 第四轮

###### E-> TE1

规则`2`: 把 FISRT{T}放入 FISRT{E}中。没有增大

规则`3`:   FISRT{T}中没有**ε**，不用管

| $$FIRST\{E\}$$ | $$FIRST\{E^{\prime}\}$$ | $$FIRST\{T\}$$ | $$FIRST\{T^{\prime}\}$$ | $$FIRST\{F\}$$ |
| :------------: | :---------------------: | :------------: | :---------------------: | :------------: |
|     （，i      |          +，ε           |     （，i      |          *，ε           |     （，i      |

###### E1-> +TE1|ε

规则 `1`：左边第一个是终结符和**ε**，将他们放进 FIRST\{E1}集中。没有增大

| $$FIRST\{E\}$$ | $$FIRST\{E^{\prime}\}$$ | $$FIRST\{T\}$$ | $$FIRST\{T^{\prime}\}$$ | $$FIRST\{F\}$$ |
| :------------: | :---------------------: | :------------: | :---------------------: | :------------: |
|     （，i      |          +，ε           |     （，i      |          *，ε           |     （，i      |

###### T->FT1

规则`2`: 将 FIRSR{F}中的非ε元素加入 FIRST(T)。没有增大

规则`3`:FIRST{F}没有ε，不用考虑了。不变

| $$FIRST\{E\}$$ | $$FIRST\{E^{\prime}\}$$ | $$FIRST\{T\}$$ | $$FIRST\{T^{\prime}\}$$ | $$FIRST\{F\}$$ |
| :------------: | :---------------------: | :------------: | :---------------------: | :------------: |
|     （，i      |          +，ε           |     （，i      |          *，ε           |     （，i      |

###### T1->*FT1|ε

规则`1`:将 *，ε加入 FIRST{T1}。没有增大

| $$FIRST\{E\}$$ | $$FIRST\{E^{\prime}\}$$ | $$FIRST\{T\}$$ | $$FIRST\{T^{\prime}\}$$ | $$FIRST\{F\}$$ |
| :------------: | :---------------------: | :------------: | :---------------------: | :------------: |
|     （，i      |          +，ε           |     （，i      |          *，ε           |     （，i      |

###### F->(E)|i

规则`1`:将（，i 加入 FIRST{F} 没有增大

| $$FIRST\{E\}$$ | $$FIRST\{E^{\prime}\}$$ | $$FIRST\{T\}$$ | $$FIRST\{T^{\prime}\}$$ | $$FIRST\{F\}$$ |
| :------------: | :---------------------: | :------------: | :---------------------: | :------------: |
|     （，i      |          +，ε           |     （，i      |          *，ε           |     （，i      |

没有增大 结束。

最终结果为：

| $$FIRST\{E\}$$ | $$FIRST\{E^{\prime}\}$$ | $$FIRST\{T\}$$ | $$FIRST\{T^{\prime}\}$$ | $$FIRST\{F\}$$ |
| :------------: | :---------------------: | :------------: | :---------------------: | :------------: |
|     （，i      |          +，ε           |     （，i      |          *，ε           |     （，i      |

### FOLLOW 集合

#### 定义

FOLLOW(A) 是所有矩形中出现在紧接 A 之后的终结符或#所构成的集合

#### 构造 FOLLOW 集合、

对于每个非终结符 A，连续使用以下规则，直至每个 FOLLOW 集合不再增大

1. 对于文法的开始符号 S，置#于 FOLLOW(S) 中
2. 若 A-> αBβ是一个产生式，则把 FISRT{β}中非**ε**元素放入 FOLLOW{B}中
3. 若 A-> αB 或 A-> αBβ【ε∈FISRT{B}】则把 FOLLOW{A}中的元素放入 FOLLOW{B}。

αβ是由终结符和非终结符构成的

#### 例题

> 对于文法 G(E):
>
> > $$E-> TE^{\prime} $$
> >
> > $$E^{\prime}-> +TE^{\prime} |ε $$
> >
> > $$T->FT^{\prime}$$
> >
> > $$T^{\prime}->*FT^{\prime}|ε$$
> >
> > $$F->(E)|i$$
>
> 构造每个非终结符的 FOLLOW 集合

根据规则`1`将# 放入 FOLLOW{E}中

| $$FOLLOW\{E\}$$ | $$FOLLOW\{E^{\prime}\}$$ | $$FOLLOW\{T\}$$ | $$FOLLOW\{T^{\prime}\}$$ | $$FOLLOW\{F\}$$ |
| :-------------: | :----------------------: | :-------------: | :----------------------: | :-------------: |
|       ＃        |                          |                 |                          |                 |

##### 第一轮

###### E-> TE1

规则 2：α为空，B 为 T，E1 为β。将 FISRT{E1}中非**ε**元素放入 FOLLOW{T}中

规则 3：α为 T，B 为 E1 FOLLOW{E}中的元素放入 FOLLOW{E1}。

规则 3：α为空，B 为 T，E1 为β，FISRT{E1}中有**ε**，将 FOLLOW{E}中的元素放入 FOLLOW{T}。

| $$FOLLOW\{E\}$$ | $$FOLLOW\{E^{\prime}\}$$ | $$FOLLOW\{T\}$$ | $$FOLLOW\{T^{\prime}\}$$ | $$FOLLOW\{F\}$$ |
| :-------------: | :----------------------: | :-------------: | :----------------------: | :-------------: |
|       ＃        |            ＃            |      +，＃      |                          |                 |

###### E1-> +TE1|ε

规则 2：α为＋，B 为 T，β为 E1，将 FISRT{E1}中非**ε**元素放入 FOLLOW{T}中 

规则 3：α为＋T，B 为 E1 FOLLOW{E}中的元素放入 FOLLOW{E1}。

规则 3：α为空，B 为 T，E1 为β，FISRT{E1}中有**ε**，将 FOLLOW{E}中的元素放入 FOLLOW{T}。

| $$FOLLOW\{E\}$$ | $$FOLLOW\{E^{\prime}\}$$ | $$FOLLOW\{T\}$$ | $$FOLLOW\{T^{\prime}\}$$ | $$FOLLOW\{F\}$$ |
| :-------------: | :----------------------: | :-------------: | :----------------------: | :-------------: |
|       ＃        |            ＃            |      +，＃      |                          |                 |

###### T->FT1

规则 2：α为空，B 为 F，T1 为β。将 FISRT{T1}中非**ε**元素放入 FOLLOW{F}中

规则 3：α为 F，B 为 T1 FOLLOW{T}中的元素放入 FOLLOW{T1}。

规则 3：α为空，B 为 F，T1 为β，FISRT{T1}中有**ε**，将 FOLLOW{T}中的元素放入 FOLLOW{F}。

| $$FOLLOW\{E\}$$ | $$FOLLOW\{E^{\prime}\}$$ | $$FOLLOW\{T\}$$ | $$FOLLOW\{T^{\prime}\}$$ | $$FOLLOW\{F\}$$ |
| :-------------: | :----------------------: | :-------------: | :----------------------: | :-------------: |
|       ＃        |            ＃            |      +，＃      |          +，＃           |    *，+，＃     |

###### T1->*FT1|ε

规则 2：α为＊，B 为 F，T1 为β。将 FISRT{T1}中非**ε**元素放入 FOLLOW{F}中

规则 3：α为＊F，B 为 T1 FOLLOW{T1}中的元素放入 FOLLOW{T1}。不变

规则 3：α为＊，B 为 F，T1 为β，FISRT{T1}中有**ε**，将 FOLLOW{T1}中的元素放入 FOLLOW{F}。不变

| $$FOLLOW\{E\}$$ | $$FOLLOW\{E^{\prime}\}$$ | $$FOLLOW\{T\}$$ | $$FOLLOW\{T^{\prime}\}$$ | $$FOLLOW\{F\}$$ |
| :-------------: | :----------------------: | :-------------: | :----------------------: | :-------------: |
|       ＃        |            ＃            |      +，＃      |          +，＃           |    *，+，＃     |

###### F->(E)|i

规则 2：α为（，B 为 E，）为β。将 FISRT{）}中非**ε**元素放入 FOLLOW{E}中

| $$FOLLOW\{E\}$$ | $$FOLLOW\{E^{\prime}\}$$ | $$FOLLOW\{T\}$$ | $$FOLLOW\{T^{\prime}\}$$ | $$FOLLOW\{F\}$$ |
| :-------------: | :----------------------: | :-------------: | :----------------------: | :-------------: |
|     ＃，）      |            ＃            |      +，＃      |          +，＃           |        *        |

##### 第二轮

###### E-> TE1

规则 2：α为空，B 为 T，E1 为β。将 FISRT{E1}中非**ε**元素放入 FOLLOW{T}中。已经放过

规则 3：α为 T，B 为 E1 FOLLOW{E}中的元素放入 FOLLOW{E1}。

规则 3：α为空，B 为 T，E1 为β，FISRT{E1}中有**ε**，将 FOLLOW{E}中的元素放入 FOLLOW{T}。已经放过

| $$FOLLOW\{E\}$$ | $$FOLLOW\{E^{\prime}\}$$ | $$FOLLOW\{T\}$$ | $$FOLLOW\{T^{\prime}\}$$ | $$FOLLOW\{F\}$$ |
| :-------------: | :----------------------: | :-------------: | :----------------------: | :-------------: |
|     ＃，）      |          ＃，）          |      +，＃      |          +，＃           |    *，+，＃     |

###### E1-> +TE1|ε

规则 2：α为＋，B 为 T，β为 E1，将 FISRT{E1}中非**ε**元素放入 FOLLOW{T}中

规则 3：α为＋T，B 为 E1 FOLLOW{E}中的元素放入 FOLLOW{E1}。没变

规则 3：α为空，B 为 T，E1 为β，FISRT{E1}中有**ε**，将 FOLLOW{E}中的元素放入 FOLLOW{T}。没变

| $$FOLLOW\{E\}$$ | $$FOLLOW\{E^{\prime}\}$$ | $$FOLLOW\{T\}$$ | $$FOLLOW\{T^{\prime}\}$$ | $$FOLLOW\{F\}$$ |
| :-------------: | :----------------------: | :-------------: | :----------------------: | :-------------: |
|     ＃，）      |          ＃，）          |    +，＃，）    |          +，＃           |    *，+，＃     |

###### T->FT1

规则 2：α为空，B 为 F，T1 为β。将 FISRT{T1}中非**ε**元素放入 FOLLOW{F}中。没变

规则 3：α为 F，B 为 T1 FOLLOW{T}中的元素放入 FOLLOW{T1}。变了

规则 3：α为空，B 为 F，T1 为β，FISRT{T1}中有**ε**，将 FOLLOW{T}中的元素放入 FOLLOW{F}。变了

| $$FOLLOW\{E\}$$ | $$FOLLOW\{E^{\prime}\}$$ | $$FOLLOW\{T\}$$ | $$FOLLOW\{T^{\prime}\}$$ | $$FOLLOW\{F\}$$ |
| :-------------: | :----------------------: | :-------------: | :----------------------: | :-------------: |
|     ＃，）      |          ＃，）          |    +，＃，）    |        +，＃，）         |  *，+，＃，）   |

###### T1->*FT1|ε

规则 2：α为＊，B 为 F，T1 为β。将 FISRT{T1}中非**ε**元素放入 FOLLOW{F}中。已经放过

规则 3：α为＊F，B 为 T1 FOLLOW{T1}中的元素放入 FOLLOW{T1}。不变

规则 3：α为＊，B 为 F，T1 为β，FISRT{T1}中有**ε**，将 FOLLOW{T1}中的元素放入 FOLLOW{F}。不变

| $$FOLLOW\{E\}$$ | $$FOLLOW\{E^{\prime}\}$$ | $$FOLLOW\{T\}$$ | $$FOLLOW\{T^{\prime}\}$$ | $$FOLLOW\{F\}$$ |
| :-------------: | :----------------------: | :-------------: | :----------------------: | :-------------: |
|     ＃，）      |          ＃，）          |    +，＃，）    |        +，＃，）         |  *，+，＃，）   |

###### F->(E)|i

规则 2：α为（，B 为 E，）为β。将 FISRT{）}中非**ε**元素放入 FOLLOW{E}中。不变

| $$FOLLOW\{E\}$$ | $$FOLLOW\{E^{\prime}\}$$ | $$FOLLOW\{T\}$$ | $$FOLLOW\{T^{\prime}\}$$ | $$FOLLOW\{F\}$$ |
| :-------------: | :----------------------: | :-------------: | :----------------------: | :-------------: |
|     ＃，）      |          ＃，）          |    +，＃，）    |        +，＃，）         |  *，+，＃，）   |

##### 第三轮

###### E-> TE1

规则 2：α为空，B 为 T，E1 为β。将 FISRT{E1}中非**ε**元素放入 FOLLOW{T}中。已经放过

规则 3：α为 T，B 为 E1 FOLLOW{E}中的元素放入 FOLLOW{E1}。没变

规则 3：α为空，B 为 T，E1 为β，FISRT{E1}中有**ε**，将 FOLLOW{E}中的元素放入 FOLLOW{T}。已经放过

| $$FOLLOW\{E\}$$ | $$FOLLOW\{E^{\prime}\}$$ | $$FOLLOW\{T\}$$ | $$FOLLOW\{T^{\prime}\}$$ | $$FOLLOW\{F\}$$ |
| :-------------: | :----------------------: | :-------------: | :----------------------: | :-------------: |
|     ＃，）      |          ＃，）          |      +，＃      |          +，＃           |    *，+，＃     |

###### E1-> +TE1|ε

规则 2：α为＋，B 为 T，β为 E1，将 FISRT{E1}中非**ε**元素放入 FOLLOW{T}中。已经放过

规则 3：α为＋T，B 为 E1 FOLLOW{E}中的元素放入 FOLLOW{E1}。没变

规则 3：α为空，B 为 T，E1 为β，FISRT{E1}中有**ε**，将 FOLLOW{E}中的元素放入 FOLLOW{T}。没变

| $$FOLLOW\{E\}$$ | $$FOLLOW\{E^{\prime}\}$$ | $$FOLLOW\{T\}$$ | $$FOLLOW\{T^{\prime}\}$$ | $$FOLLOW\{F\}$$ |
| :-------------: | :----------------------: | :-------------: | :----------------------: | :-------------: |
|     ＃，）      |          ＃，）          |    +，＃，）    |          +，＃           |    *，+，＃     |

###### T->FT1

规则 2：α为空，B 为 F，T1 为β。将 FISRT{T1}中非**ε**元素放入 FOLLOW{F}中。已经放过

规则 3：α为 F，B 为 T1 FOLLOW{T}中的元素放入 FOLLOW{T1}。没变

规则 3：α为空，B 为 F，T1 为β，FISRT{T1}中有**ε**，将 FOLLOW{T}中的元素放入 FOLLOW{F}。没变

| $$FOLLOW\{E\}$$ | $$FOLLOW\{E^{\prime}\}$$ | $$FOLLOW\{T\}$$ | $$FOLLOW\{T^{\prime}\}$$ | $$FOLLOW\{F\}$$ |
| :-------------: | :----------------------: | :-------------: | :----------------------: | :-------------: |
|     ＃，）      |          ＃，）          |    +，＃，）    |        +，＃，）         |  *，+，＃，）   |

###### T1->*FT1|ε

规则 2：α为＊，B 为 F，T1 为β。将 FISRT{T1}中非**ε**元素放入 FOLLOW{F}中。已经放过

规则 3：α为＊F，B 为 T1 FOLLOW{T1}中的元素放入 FOLLOW{T1}。不变

规则 3：α为＊，B 为 F，T1 为β，FISRT{T1}中有**ε**，将 FOLLOW{T1}中的元素放入 FOLLOW{F}。不变

| $$FOLLOW\{E\}$$ | $$FOLLOW\{E^{\prime}\}$$ | $$FOLLOW\{T\}$$ | $$FOLLOW\{T^{\prime}\}$$ | $$FOLLOW\{F\}$$ |
| :-------------: | :----------------------: | :-------------: | :----------------------: | :-------------: |
|     ＃，）      |          ＃，）          |    +，＃，）    |        +，＃，）         |  *，+，＃，）   |

###### F->(E)|i

规则 2：α为（，B 为 E，）为β。将 FISRT{）}中非**ε**元素放入 FOLLOW{E}中。不变

| $$FOLLOW\{E\}$$ | $$FOLLOW\{E^{\prime}\}$$ | $$FOLLOW\{T\}$$ | $$FOLLOW\{T^{\prime}\}$$ | $$FOLLOW\{F\}$$ |
| :-------------: | :----------------------: | :-------------: | :----------------------: | :-------------: |
|     ＃，）      |          ＃，）          |    +，＃，）    |        +，＃，）         |  *，+，＃，）   |

所有的 FOLLOW 已经没在变化了，这时候已经计算完了。

最后的结果为：

| $$FOLLOW\{E\}$$ | $$FOLLOW\{E^{\prime}\}$$ | $$FOLLOW\{T\}$$ | $$FOLLOW\{T^{\prime}\}$$ | $$FOLLOW\{F\}$$ |
| :-------------: | :----------------------: | :-------------: | :----------------------: | :-------------: |
|     ＃，）      |          ＃，）          |    +，＃，）    |        +，＃，）         |  *，+，＃，）   |

### 消除左递归

#### 法一

将左递归变为右递归

> P->Pα|β
>
> 变为
>
> P->βP1
>
> P1->αP1|ε

对于文法`P->Pα|β`我们可以推导出他能识别的串，它是以β开头后面接着 0-n 个α的串；βαααααα....

#### 法二

##### 条件

1. 不含以**ε**为右部的产生式
2. 不含回路（p->p）

##### 方法

1. 对非终结符进行排列 P1.....Pn
2. 从 P1 到 Pn 遍历，把 Pi 改为`α|Pi+1|Pi+2|...|Pn`
   1. 从 j=1 到 j=i-1 把形如 Pi->Pjγ的改写为`Pi->ζ1γ|ζ2γ|...|ζkγ ` 其中`Pj->ζ1|ζ2|...|ζk`。此时就可以得到形如 `Pi->α|Pi|Pi|...|Pi+k|...`
   2. 使用直接消除 Pi 使用`方法一`
3. 化简`2`，去除从开始符号出发永远无法到达的非终结符产生规则

#### 例题

> 考虑文法 G[S]
>
> > S->(T)|a+S|a
> >
> > T->T，S|S
>
> 消除左递归

##### 第一步

只有两个非终结符，按照一定顺序排序，按照 T，S 的顺序排列

##### 第二步

1. 先处理 T

   > T->T，S|S 

   由于 T 在前面，S 在后面，所以 S 不处理 (2.1)。由于本身有左递归，使用方法一直接消除左递归

   > T->ST1
   >
   > T1-> ,ST1|ε

2. 处理 S

   > S->(T)|a+S|a

   由于 T 在 S 的前面，所以要将 T 处理掉。T 又有（T->ST1）进行替换

   > S->(ST1)|a+S|a

   不含有左递归，处理结束

3. 化简

   > S->(ST1)|a+S|a
   >
   > T->ST1
   >
   > T1-> ,ST1|ε

   从开始符号都可以到达，所以不用去掉

##### 结果为

> S->(ST1)|a+S|a
>
> T->ST1
>
> T1-> ,ST1|ε

### 提取左公共因子

对于规则 S   

> S ->  aB1|aB2|aB3|aB4|...|aBn|y   

可以改写为

> S-> aS1|y
> S1 -> B1|B2|B3...|Bn   



### FISRTVT 集合

#### 方法

1. A->a.....  则将 a 加入 FIRSTVT(A) 中
2. A->B.... 将 FIRSTVT(B) 加入到 FIRSTVT(A) 中
3. A->Ba... 

#### 例题

已给文法：

> G[S]:
> S→a|b|(B)
> A→S, A|S
> B→A

求非终结符的 FISRTVT 集合

##### 求 FIRSTVT(S)

> S→a|b|(B)

根据规则`1`可得

FIRSTVT(S)= {a,b,(}

##### 求 FIRSTVT(A)

> A→S, A|S

根据规则`2`可得，应该 FISRTVT(S) 中的放入 FIRSTVT(A) 中

FIRSTVT(A) = {a,b,(}

根据规则`3`，应该把`,`放入 FIRSTVT(A) 中

FIRSTVT(A) = {a,b,(,逗号}

##### 求 FIRSTVT(B)

> B→A

根据规则`3`，应该 FISRTVT(A) 中的放入 FIRSTVT(B) 中

FIRSTVT(B) = {a,b,(,逗号}

|      |   FISRTVT    |
| :--: | :----------: |
|  S   |   {a,b,(}    |
|  A   | {a,b,(,逗号} |
|  B   | {a,b,(,逗号} |

### LASTVT 集合

#### 方法

1. A->.....a  把 a 加入 LASTVT(A) 中
2. A->.....B  把 LASTVT(B) 加入 LASTVT(A) 中
3. A->....aB 把 a 加入 LASTVT(A) 中

#### 例题

已给文法：

> G[S]:
> S→a|b|(B)
> A→S, A|S
> B→A

求非终结符的 LASTVT 集合

##### 求 LASTVT(S)

> S→a|b|(B)

根据规则`1`可得

LASTVT(S)= {a,b,)}

##### 求 LASTVT(A)

> A→S, A|S

根据规则`2`可得，应该 LASTVT(S) 中的放入 LASTVT(A) 中

LASTVT(A) = {a,b,)}

根据规则`3`，应该把`,`放入 LASTVT(A) 中

LASTVT(A) = {a,b,),逗号}

##### 求 LASTVT(B)

> B→A

根据规则`3`，应该 LASTVT(A) 中的放入 LASTVT(B) 中

FIRSTVT(B) = {a,b,),逗号}

|      |    LASTVT    |
| :--: | :----------: |
|  S   |   {a,b,)}    |
|  A   | {a,b,),逗号} |
|  B   | {a,b,),逗号} |

### 算符优先文法 OPG 的条件

1. OPG 文法条件
   1. 无 S->...AB...
   2. 无ε产生式
2. 两两终结符间至多一种优先关系

### 判断算符优先级

#### 方法一

1. 找出所有非终结符，画出一下表格

   |      | a    | b    | c    | ...  | n    |
   | ---- | ---- | ---- | ---- | ---- | ---- |
   | a    |      |      |      |      |      |
   | b    |      |      |      |      |      |
   | c    |      |      |      |      |      |
   | ...  |      |      |      |      |      |
   | n    |      |      |      |      |      |

2. ＝ 找 aQb 形式的，a=b，横排找 a，竖排找 b

3. <  找 aQ 形式的，a 与 FISRSTVT(Q) 的每个元素交叉处填`<`，a 为横排元素

4. \>  找 Qa 形式的，在竖排中找到 a，在横排中找到 LASTVT(Q) 中的元素，相交处填`>`

5. \# < FIRSTVT(A)

6. LASTVT(A)>#

#### 例题

已给文法：

> G[S]:
> S→a|b|(B)
> A→S, A|S
> B→A

判断算符优先级

根据上面我们已经求出非终结符的 FIRSTVT 和 LASTVT 集合。列表

|      | a    | b    | （   | ）   | ，   |
| ---- | ---- | ---- | ---- | ---- | ---- |
| a    |      |      |      |      |      |
| b    |      |      |      |      |      |
| （   |      |      |      |      |      |
| ）   |      |      |      |      |      |
| ，   |      |      |      |      |      |

1. =  我们可以找到`(B)`是符合要求的，则

|      | a    | b    | （   | ）   | ，   |
| ---- | ---- | ---- | ---- | ---- | ---- |
| a    |      |      |      |      |      |
| b    |      |      |      |      |      |
| （   |      |      |      | =    |      |
| ）   |      |      |      |      |      |
| ，   |      |      |      |      |      |

2.  < 我们找到 aQ 形式的，有`(B`,`,A` 则从横排找`(`,在竖排中找到 FIRSTVT(B)，在交叉处填上`<`。在横排中找到`，`在竖排中国找到 FIRSTVT(A) 中的元素，在交叉处填上`<`

|      | a    | b    | （   | ）   | ，   |
| ---- | ---- | ---- | ---- | ---- | ---- |
| a    |      |      |      |      |      |
| b    |      |      |      |      |      |
| （   | <    | <    | <    | =    | <    |
| ）   |      |      |      |      |      |
| ，   | <    | <    | <    |      | <    |

3. \> 我们找到 Qa 形式的，有`B)`,`S,` ，在竖排中找到`)`,在横排中找到 LASTVT(B) 中的元素，在交叉处填上`>`, 在竖排找到`,` 在横排找到 LASTVT(S)，在交叉处填上`>`


   |      | a    | b    | （   | ）   | ，   |
   | ---- | ---- | ---- | ---- | ---- | ---- |
   | a    |      |      |      | >    | >    |
   | b    |      |      |      | >    | >    |
   | （   | <    | <    | <    | =    | <    |
   | ）   |      |      |      | >    | >    |
   | ，   | <    | <    | <    | >    | <    |


4. \# < FIRSTVT(A)  横纵额外添加一列 (行)`#`


   |      | a    | b    | （   | ）   | ，   | #    |
   | ---- | ---- | ---- | ---- | ---- | ---- | ---- |
   | a    |      |      |      | >    | >    | >    |
   | b    |      |      |      | >    | >    | >    |
   | （   | <    | <    | <    | =    | <    |      |
   | ）   |      |      |      | >    | >    | >    |
   | ，   | <    | <    | <    | >    | <    |      |
   | #    | <    | <    | <    |      | <    | >    |

   \# < FIRSTVT(S) 

   \# < FIRSTVT(A) 

   \# < FIRSTVT(B) 

5. LASTVTVT(A)>#  

   LASTVTVT(S)>#

   LASTVTVT(A)>#

   LASTVTVT(B)>#

#### 结果如下

|      | a    | b    | （   | ）   | ，   | #    |
| ---- | ---- | ---- | ---- | ---- | ---- | ---- |
| a    |      |      |      | >    | >    | >    |
| b    |      |      |      | >    | >    | >    |
| （   | <    | <    | <    | =    | <    |      |
| ）   |      |      |      | >    | >    | >    |
| ，   | <    | <    | <    | >    | <    |      |
| #    | <    | <    | <    |      | <    | >    |

#### 方法二

1. 对于文法的开始符号 S，增加拓广文法 S1->#S#

2. 找出所有非终结符，画出一下表格

   |      | a    | b    | c    | ...  | n    | #    |
   | ---- | ---- | ---- | ---- | ---- | ---- | ---- |
   | a    |      |      |      |      |      |      |
   | b    |      |      |      |      |      |      |
   | c    |      |      |      |      |      |      |
   | ...  |      |      |      |      |      |      |
   | n    |      |      |      |      |      |      |
   | #    |      |      |      |      |      |      |

3. ＝ 找 aQb 形式的，a=b，横排找 a，竖排找 b

4. <  找 aQ 形式的，a 与 FISRSTVT(Q) 的每个元素交叉处填`<`，a 为横排元素

5. \>  找 Qa 形式的，在竖排中找到 a，在横排中找到 LASTVT(Q) 中的元素，相交处填`>`

此方法不用额外判断`#`的优先级，在与其他的处理过程中，会一同处理