《编译原理》构造 LL(1) 分析表的步骤 - 例题解析

我就是我 2022-01-12 08:51 237阅读 0赞

### 《编译原理》构造 LL(1) 分析表的步骤 - 例题解析 ###

#### 易错点及扩展： ####

1、求每个产生式的 SELECT 集

2、注意区分是对谁 FIRST 集 FOLLOW 集

3、开始符号的 FOLLOW 集包含 \#

4、**各集合对对应的对象以及含义**

<table> 
 <thead> 
  <tr> 
   <th>集</th> 
   <th>对象</th> 
   <th>含义</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td>FIRST 集</td> 
   <td>是对产生式右部</td> 
   <td>右部内部的所有终结符集，可能为 ε</td> 
  </tr> 
  <tr> 
   <td>FOLLOW 集</td> 
   <td>是对产生式左部（非终结符）</td> 
   <td>非终结符后面紧跟的终结符，可能为 #，和该非终结符推导出的右部无关（因为LL(1)文法不包含递归，所以右部不会再有该非终结符，所以不能通过该右部判断该非终结符后跟集合）</td> 
  </tr> 
  <tr> 
   <td>SELECT 集</td> 
   <td>是对产生式</td> 
   <td>需要考虑产生式右部的不同情况，进一步确定是根据 FIRST 集还是 FOLLOW 集</td> 
  </tr> 
 </tbody> 
</table>

5、**SELECT 集的定义**  
**注：** 注意区分 FIRST 集 FOLLOW 时是对 α 还是 A

> 给定文法 G，对于产生式 A→α，α ∈ V\*，则可选集 SELECT(A→α) 有：  
> （1）若 α ≠ ε，且 α ≠\+> ε，则 SELECT(A→α) = FIRST(α)  
> （2）若 α ≠ ε，但 α =\+> ε，则 SELECT(A→α) = FIRST(α) ∪ FOLLOW(A)  
> （3）若 α = ε，则 SELECT(A→α) = FOLLOW(A)

**描述：**

*  第 1 条是，当 α ≠ ε，且通过1次或多次推不出 ε，SELECT(A→α) = FIRST(α)
 *  第 2 条是，当 α ≠ ε，但 α 经有限步可推出 ε，SELECT(A→α) = FIRST(α) ∪ FOLLOW(A)  
    （注意是一个 α，一个 A）
 *  第 3 条是，当 α = ε，SELECT 集就等于左部 A 的 FOLLOW 集
    
    解题时，先判断是否为 ε，是则用第（3）条，否则再判断能否通过1次或多次推出 ε，是则用第（2）条，否则用第（1）条
    
    求 FIRST，FOLLOW，SELECT 集详细例题可参考：  
    [《编译原理》-用例题理解-自顶向下语法分析及 FIRST，FOLLOW，SELECT集，LL(1)文法][-_-_ FIRST_FOLLOW_SELECT_LL_1]

6、**LL(1) 分析表的结构**

分析表是一个二维数组 M\[A，a\]，其中 A 表示行，是非终结符，a 表式列是终结符或 \#。

*  M\[A，a\] 中若有产生式，表明 A 可用该产生式推导，以求与输入符号 a 匹配。
 *  M\[A，a\] 中若为空，表明 A 不可能推导出与 a 匹配的字符串

7、**LL(1) 分析表构造方法：**

*  若 a∈SELECT(A→α)，则把 A→α 加至 M\[A, a\] 中
 *  把所有无定义的 M\[A, a\] 标上“出错标志”。为了使表简化，表中空白处为出错

#### 例题： ####

**已给文法：**

> **G\[S\]: S→aH  
> H→aMd  
> H→d  
> M→Ab  
> M→ε  
> A→aM  
> A→e**

（1）求 SELECT 集  
（2）证明文法是 LL(1) 文法  
（3）构造 LL(1) 分析表

**解析：**

**求 SELECT 集：**

<table> 
 <thead> 
  <tr> 
   <th>产生式</th> 
   <th>FIRST 集</th> 
   <th>FOLLOW 集</th> 
   <th>SELECT 集</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td>S→aH <strong>分析：</strong> 对该产生式，可知 FIRST(aH) = {a}；也可知应将 FOLLOW(S) = {#} 加到 FOLLOW(H) 中</td> 
   <td>{a}</td> 
   <td>FOLLOW(S) = {#}</td> 
   <td>SELECT(S→aH) = FIRST(aH) = {a}</td> 
  </tr> 
  <tr> 
   <td>H→aMd <strong>分析：</strong> 对该产生式，可知 FIRST(aMd) = {a}；也可知应将 d 加到 FOLLOW(M) 中</td> 
   <td>{a}</td> 
   <td>FOLLOW(H) = {#}</td> 
   <td>SELECT(H→aMd) = FIRST(aMd) = {a}</td> 
  </tr> 
  <tr> 
   <td>H→d <strong>分析：</strong> 对该产生式，可知 FIRST(d) = {d}</td> 
   <td>{d}</td> 
   <td></td> 
   <td>SELECT(H→d) = FIRST(d) = {d}</td> 
  </tr> 
  <tr> 
   <td>M→Ab <strong>分析：</strong> 对该产生式，可知 FIRST(Ab) = {a, e}；也可知应将 b 加到 FOLLOW(A) 中</td> 
   <td>{a, e}</td> 
   <td>FOLLOW(M) = {b, d}</td> 
   <td>SELECT(M→Ab) = FIRST(Ad) = {a, e}</td> 
  </tr> 
  <tr> 
   <td>M→ε</td> 
   <td>{ε}</td> 
   <td></td> 
   <td>SELECT(M→ε) = FOLLOW(M) ={d, b} <strong>求法：</strong> 由产生式 H→aMd，所以将 d 放入 FOLLOW(M)；由产生式 A→aM 所以把 FOLLOW(A) 加至 FOLLOW(M) 中。<strong>同理</strong> 求 FOLLOW(A)，由产生式 M→Ab，FOLLOW(A) = {b}。故 FOLLOW(M) = {d ,b}</td> 
  </tr> 
  <tr> 
   <td>A→aM <strong>分析：</strong> 对该产生式，可知 FIRST(aM) = {a}；也可知应将 FOLLOW(A) 加到 FOLLOW(M) 中</td> 
   <td>{a}</td> 
   <td>FOLLOW(A) = {b}</td> 
   <td>SELECT(A→aM) = FIRST(aM) = {a}</td> 
  </tr> 
  <tr> 
   <td>A→e <strong>分析：</strong> 对该产生式，可知 FIRST(e) = {e}</td> 
   <td>{e}</td> 
   <td></td> 
   <td>SELECT(A→e) = FIRST(e) = {e}</td> 
  </tr> 
 </tbody> 
</table>

**证明文法是 LL(1) 文法（2 分）**

定理：同一非终结符的 SELECT 交集为空集，则该文法是 LL(1) 文法：

*  SELECT(H→aMd) ∩ SELECT(H→d) = ∅
 *  SELECT(M→Ab) ∩ SELECT(M→ε) = ∅
 *  SELECT(A→aM) ∩ SELECT(A→e) = ∅

所以该文法是 LL(1) 文法

**构造 LL(1) 分析表（1 分）**

分析表是一个二维数组 M\[A，a\]，其中 A 表示行是非终结符，a 表式列是终结符或 \#。根据 SELECT 集构造分析表：

[-_-_ FIRST_FOLLOW_SELECT_LL_1]: https://icode.blog.csdn.net/article/details/90984375