构造LL(1)预测分析表

admin

2020 年 04 月 28 日

308次浏览

1 条评论

2899字数

编译原理

前提`只有当文法已经是LL(1)文法了，才可以为其构造分析表`，否则无法构造(二义等)

## 构造方法

**对于一个文法G的每个产生式 `A→α`进行如下处理：**

* 对于`FIRST(α)`中的每个终结符号`a`，将`A→α`加入到**`M[A,a]`**。
* 如果`ε`在`FIRST(α)`中，那么：
  * 对于`FOLLOW(A)`中的每个终结符号`b`，将`A→α`加入到**`M[A,b]`**。
  * 若`$`在`FOLLOW(A)`中，将`A→α`加入到**`M[A,$]`**。

## 例

#### 有如下LL(1)文法：

*E* → *T E'*

*E'* → **+** *T E'* | **ε**

*T*  → *F* *T'*

*T'* → **\*** *F T'* | **ε**

*F* → **(** *E* **)** | **id**

#### 先求FIRST与FOLLOW集

FIRST(*E* ) = FIRST(*T* ) = FIRST(*F* ) = { **(**, **id**, }

FIRST(*T'* ) = { **\***, **ε** }

FIRST(*E'* ) = { **+**, **ε** }

FOLLOW(*E'* ) = FOLLOW(*E* ) = { **$**, **\)** }

FOLLOW(*T'* ) = FOLLOW(*T* ) = { **+**, **$**, **\)** }

FOLLOW(*F* ) = { **\***, **+**, **$**, **\)** }

#### 再逐步构造分析表

1. 首先画出空表，横向表头是所有终结符，纵向表头是所有非终结符

|         | **id** | **+** | **\*** | **(** | **)** | **$** |
| :--------: | :------: | :-----: | :------: | :-----: | :-----: | :-----: |
| ***E*** |       |       |       |       |       |       |
| ***E'*** |       |       |       |       |       |       |
| ***T*** |       |       |       |       |       |       |
| ***T'*** |       |       |       |       |       |       |
| ***F*** |       |       |       |       |       |       |

2. 接着根据第一条规则，对每一个产生式，根据其右部第一个终结符，将产生式填入相应位置

|         |     **id**     |      **+**      |      **\***      |     **(**     | **)** | **$** |
| :--------: | :--------------: | :----------------: | :-----------------: | :--------------: | :-----: | :-----: |
| ***E*** | ***E*→*TE'*** |                 |                   | ***E*→*TE'*** |       |       |
| ***E'*** |               | ***E'*→+*TE'*** |                   |               |       |       |
| ***T*** | ***T*→*FT'*** |                 |                   | ***T*→*FT'*** |       |       |
| ***T'*** |               |                 | ***T'*→\**FT'*** |               |       |       |
| ***F*** |  ***F*→id**  |                 |                   | ***F*→(*E*)** |       |       |

3. 最后根据第二条规则，对于能推空的产生式，若输入的终结符或`$`在右部的FOLLOW集中，则将此产生式填入相应位置

|         |     **id**     |      **+**      |      **\***      |     **(**     |     **)**     |     **$**     |
| :--------: | :--------------: | :----------------: | :-----------------: | :--------------: | :--------------: | :--------------: |
| ***E*** | ***E*→*TE'*** |                 |                   | ***E*→*TE'*** |               |               |
| ***E'*** |               | ***E'*→+*TE'*** |                   |               | ***E'*→*ε*** | ***E'*→*ε*** |
| ***T*** | ***T*→*FT'*** |                 |                   | ***T*→*FT'*** |               |               |
| ***T'*** |               |  ***T'*→*ε***  | ***T'*→\**FT'*** |               | ***T'*→*ε*** | ***T'*→*ε*** |
| ***F*** |  ***F*→id**  |                 |                   | ***F*→(*E*)** |               |               |

最后修改：2021 年 09 月 09 日 03 : 10 PM

如果觉得我的文章对你有用，请随意赞赏

构造LL(1)预测分析表