《编译原理》求短语，直接短语，句柄，素短语，最左素短语 - 例题解析

港控/mmm° 2022-10-02 14:52 180阅读 0赞

### 《编译原理》求短语，直接短语，句柄，素短语，最左素短语 - 例题解析 ###

笔记

#### （一）明确概念： ####

<table> 
 <thead> 
  <tr> 
   <th>名称</th> 
   <th>概念</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td>短语</td> 
   <td><strong>定义：</strong> 若 S 为文法 G 的开始符号，αβδ 是该文法的一个句型，即 S ⇒* αβδ，且有 A ⇒<sup>+</sup> β，则称 β 是句型 αβδ 相对于非终结符 A 的短语。<strong>语法树：</strong> 在语法树中表示所有分支结点对应子树，短语即子树叶子对应的符号。<strong>注：</strong> 子树包括语法树本身，及句型本身也可以称为短语。</td> 
  </tr> 
  <tr> 
   <td>直接短语</td> 
   <td><strong>定义：</strong> 若 S ⇒* αβδ，且文法中包含产生式 A → β，则称 β 是句型 αβδ 相对于非终结符 A 的直接短语。<strong>语法树：</strong> 在语法树中表示为该短语只有上下相邻父子两代</td> 
  </tr> 
  <tr> 
   <td>句柄</td> 
   <td>“可规约串”，句柄对应某个产生式的右部，是某个，但不是任意一个。作为一种规约对象，<strong>句柄表示最左直接短语</strong>。<strong>语法树：</strong> 在语法树上，则表示为最左边的只包含相邻父子节点的短语（最左直接短语）</td> 
  </tr> 
  <tr> 
   <td>素短语</td> 
   <td><strong>定义：</strong> 是指一个短语至少包含一个终结符，并且除它自身之外不再包含其他素短语</td> 
  </tr> 
  <tr> 
   <td>最左素短语</td> 
   <td><strong>定义：</strong> 最左素短语就是句型最左边的素短语，是算符优先分析法的规约对象。<strong>语法树：</strong> 通过语法树分析时，要注意先判断是否为素短语，再找相对最左端的素短语。</td> 
  </tr> 
 </tbody> 
</table>

#### 例题1：求短语，直接短语，句柄 ####

**给定句型：**

T\*P↑(T\*F)

**给定文法：**

> **G\[T\]:  
> T → T\*F|F  
> F → F↑P|P  
> P → (T)|i**

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

**推导步骤为：**

T ⇒ T\*F  
⇒ T\*F↑P  
⇒ T\*P↑P  
⇒ T\*P↑(T)  
⇒ T\*P↑(T\*F)

**画出语法树为：**

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9pY29kZS5ibG9nLmNzZG4ubmV0_size_16_color_FFFFFF_t_70]

**该语法树的 5 个子树及 5 个短语为：**

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9pY29kZS5ibG9nLmNzZG4ubmV0_size_16_color_FFFFFF_t_70 1]

**求直接短语方法：** 该句型的语法树有两颗直接子树（最左边的两颗子树），由这两颗直接子树的叶子结点组成的符号串（或者说只包含两层的子树叶子结点对应的），就是句型的两个直接短语，直接短语 P 和 T\*F。

**求句柄：** 因为 P 相对 T\*F，在语法树上的左侧，所以句柄是 P

**最终结果：**

#### 例题二：求素短语，最左素短语 ####

**给定句型：**

FF↑\*a\*

**给定文法：**

> **G\[T\]:  
> T → T\*F|F  
> F → F↑P|P  
> P → (T)|i**

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

**推导步骤为：**

T ⇒ TF\*  
⇒ TF\*F\*  
⇒ TF↑\*\\F\*  
⇒ TF↑\*a\*

**画出语法树：**

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9pY29kZS5ibG9nLmNzZG4ubmV0_size_16_color_FFFFFF_t_70 2]

**最终结果：**

根据定义可以找出素短语有：

<table> 
 <thead> 
  <tr> 
   <th>类型</th> 
   <th>内容</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td>素短语 2 个</td> 
   <td>F↑，a</td> 
  </tr> 
  <tr> 
   <td>最左素短语</td> 
   <td>F↑</td> 
  </tr> 
 </tbody> 
</table>

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9pY29kZS5ibG9nLmNzZG4ubmV0_size_16_color_FFFFFF_t_70]: /images/20220109/e65d22b5a7a347559939d76a53b219d8.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9pY29kZS5ibG9nLmNzZG4ubmV0_size_16_color_FFFFFF_t_70 1]: /images/20220109/0a0bc8584fc4466aa4a92e0824fd872e.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9pY29kZS5ibG9nLmNzZG4ubmV0_size_16_color_FFFFFF_t_70 2]: /images/20220109/57b3b0067af3472194a087b5f8e0fc5d.png