《编译原理》求 FIRSTVT 集和 LASTVT 集的步骤 - 例题解析

深碍√TFBOYSˉ_ 2022-01-12 10:09 352阅读 0赞

### 《编译原理》求 FIRSTVT 集和 LASTVT 集的步骤 - 例题解析 ###

算符优先关系表的构造中涉及到求 FIRSTVT 集和 LASTVT 集。

**表示及含义：**

<table> 
 <thead> 
  <tr> 
   <th>FIRSTVT(T)</th> 
   <th>非终结符T的最左终结符集合</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td><strong>LASTVT(T)</strong></td> 
   <td><strong>非终结符T的最右终结符集合</strong></td> 
  </tr> 
 </tbody> 
</table>

**定义：**

![在这里插入图片描述][2019062116361495.png]

**定义解释：**

<table> 
 <thead> 
  <tr> 
   <th>FIRSTVT(T)</th> 
   <th>非终结符T经过1步或多步推导，得到的最左端终结符，以及左端第二个终结符的集合</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td><strong>LASTVT(T)</strong></td> 
   <td><strong>非终结符T经过1步或多步推导，得到的最右端终结符，以及倒数第二个终结符的集合</strong></td> 
  </tr> 
 </tbody> 
</table>

**求 FIRSTVT 集的步骤：**

（1）若有产生式 T→a 或者 T→Ra…，则 a ∈ FIRSTVT(T)

（2）若 a ∈ FIRSTVT®，且有产生式 T→R…，则 a ∈ FIRSTVT(T)

就是说如果 a 是非终结符 R 的 FIRSTVT 集，且 T 可以推出以非终结 R 带头的右部，则 a 也是非终结符 T 的 FIRSTVT 集。

**注：** 省略号 … 可以为空，就是没有

**求 LASTVT 集的步骤：**

（1）若有产生式 T→…a 或者 T→…aR，则 a ∈ LASTVT(T)

（2）若 a ∈ LASTVT®，且有产生式 T→…R，则 a ∈ LASTVT(T)

**例题：**

> **已给文法：  
> G\[S\]:  
> S→a|b|(B)  
> A→S, A|S  
> B→A**

求所有非终结符的 FIRSTVT，LASTVT 集

##### 解析： #####

（1）只要是让求 FIRSTVT，LASTVT 集，则该文法就隐含条件为算符优先文法。

（2）算符优先文法的特点是：不会出现两个相邻的非终结符，即两个非终结符中间夹着一个终结符。如果第一个是终结符则第二个是非终结符。

**结果：**

<table> 
 <thead> 
  <tr> 
   <th></th> 
   <th>FIRSTVT 集</th> 
   <th>LASTVT 集</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td>S</td> 
   <td>{a, b, ( }</td> 
   <td>{a, b, ) }</td> 
  </tr> 
  <tr> 
   <td>A</td> 
   <td>{a, b, (, 逗号 }</td> 
   <td>{a, b, ), 逗号}</td> 
  </tr> 
  <tr> 
   <td>B</td> 
   <td>{a, b, (, 逗号 }</td> 
   <td>{a, b, ), 逗号}</td> 
  </tr> 
 </tbody> 
</table>

[2019062116361495.png]: /images/20220109/a544a5be68c54408bb0059bbe2b35eb8.png