编译原理教程_5 自底向上分析

落日映苍穹つ 2023-01-21 11:17 310阅读 0赞

> 文章原稿  
> https://gitee.com/fakerlove/fundamentals-of-compiling

### 文章目录 ###

*  5. 自底向上分析
 *   *  5.1 移进—规约分析
     *  5.2 简单优先分析法
     *   *  5.2.1 基本概念
         *  5.2.2 优先关系定义
         *  5.2.3 简单优先文法定义
         *  5.2.4 简单优先分析法的操作步骤
         *  5.2.5 实例
         *  5.2.3 缺点
     *  5.3 算符优先分析
     *  5.4 算符优先分析法的进一步讨论
     *   *  5.4.1 算符优先文法（OPG）
         *  5.4.2 构造优先关系矩阵
         *   *  优先关系矩阵构造的自然语言描述
         *  5.4.3 算符优先分析算法的实现
         *   *   *  素短语

# 5. 自底向上分析 #

**基本算法思想**:  
若采用自左向右地扫描和分析输入串，那么自底向上的基本算法是：  
从输入符号串开始，通过反复查找当前句型的句柄（最左简单短语），并利用有关规则进行规约。若能规约为文法的识别符号，则表示分析成功，输入符号串是文法的合法句子；否则有语法错误。  
分析过程是 **重复以下步骤** ：  
1、找出当前句型的句柄 x （或句柄的变形）；  
2、找出以 x 为右部的规则 X::= x ；  
3、把 x 规约为X，产生语法树的一枝。  
**关键**：找出当前句型的句柄 x (或其变形）

## 5.1 移进—规约分析 ##

要点：设置符号栈，用来纪录分析的历史和现状 ，并根据所面临的状态，确定下一步动作是移进还是规约。  
分析器：  
![在这里插入图片描述][0ca0d58adf28a18a750809992aff3337.png]  
分析过程：  
![在这里插入图片描述][80699c019bf40889bdedb947ce65b580.png]  
**注意**：  
这种方法我们是默认：  
① 栈内符号串 + 未处理输入符号串 = 当前句型  
② **句柄都在栈顶**（未真正解决句柄的识别问题）  
也就是说，**移进-规约分析实际上是不靠谱** 的，因为：  
我们不能认为：对句型 xuy 而言，若有U∷= u，即U => u 就断定u是简单短语，u 就是句柄。而是要同时满足Z =\*> xUy。

## 5.2 简单优先分析法 ##

### 5.2.1 基本概念 ###

通过语法树来理解这三个概念更加简单：

> 文法G1\[S\]：  
> S→AB  
> A→bB  
> A→Aa  
> B→a  
> B→Sb

![2869373-9da4aa12dcd3c1c7.png][]

语法树

1.  **短语**：若S=\*=>αAδ且A=+=>β，则称β是相对于非终结符A的句型αβδ的短语。
    
    即：语法树中以非终结符的作为根的子树的叶子所组成的字符串。
    
    如：ba是相对于非终结符A的句型AB的短语。句型baSb的短语有ba，a，Sb，baSb。
2.  **直接短语**：若S=\*=>αAδ且A=>β，则称β是相对于非终结符A的句型αβδ的直接短语。
    
    即：语法树中以非终结符的作为根的子树，它的孩子都是叶子，没有其他子树。
    
    如：Sb是相对于非终结符B的句型AB的短语。句型baSb的短语有a，Sb。
3.  **句柄**：位于句型最左边的直接短语称为该句型的句柄。
    
    即：位于语法树中最左边的直接短语。
    
    如：句型baSb的句柄是a。

### 5.2.2 优先关系定义 ###

1.  X和Y优先级相等，表示为 `X=·Y`，当且仅当G中存在产生式规则A=>···XY···。
    
    *解读：X、Y的优先级相同，当XY存在一个句柄之中，它们将同时被归约。表现在语法树中S=·b。*

![2869373-6556e60491a33db0.png][]

优先级相等在语法树中

1.  X优先级小于Y，表示为 `X<·Y` ，当且仅当G中存在产生式规则A=>···XB···，B=+=>Y···。
    
    *解读：X优先级小于Y，当XY存在一个句型中时，它们将不可能出现在同一个句柄中，Y一定比X先被规约。表现在语法树中b<·a。*

![2869373-b21753552a961cd3.png][]

优先级小于语法树中

1.  X优先级大于Y，表示为 `X>·Y` ，当且仅当G中存在产生式规则A=>··BD···，B=+=>···X，D=\*=>Y···。
    
    *解读：X优先级大于Y，当XY存在一个句型中时，它们将不可能出现在同一个句柄中，X一定比Y先被规约。表现在语法树中a>·S。*

![2869373-05b519d51cb0d7c0.png][]

优先级大于在语法树中

1.  X和Y的优先级为空，表示在文法的任何句型中都不会出现该符号对相邻出现的情况。

**注意**：以上优先关系之间不具有对成性。

### 5.2.3 简单优先文法定义 ###

一个文法是简单优先文法，需要满足以下两个条件：

1.  在文法符号集中V，任意两个符号之间必须之后一种优先关系存在。（显然满足）
2.  在文法中，两个产生式不能有相同的右部。

### 5.2.4 简单优先分析法的操作步骤 ###

> 1.  将输入输入串a1a2···an\#依次压栈，不断比较栈顶符号ai和下一个待输入符号aj的优先级，若ai>·aj则进行下一步，否则重复此步骤。
>     
>     *解读：停止条件是ai>·aj表示前面输入串一定比后面先归约，所以只需要在前面找句柄就行了。*
> 2.  栈顶符号ai即为句柄尾，从此处向左寻找句柄头ak，满足ak-1<·ak。
>     
>     *解读：从后向前找ak-1<·ak表示ak之前的输入串一定比ai···ak后归约，由此确定现在就是要归约ai···ak。*
> 3.  由句柄ai···ak在文法中寻找右部为ai···ak的产生式；找到则将句柄替换为相应左部，找不到则说明该输入串不是该文法的句子。
> 4.  重复以上步骤直到归约完成。

### 5.2.5 实例 ###

由于还是以上面的例子不满足简单优先文法定义（b和b的优先关系不唯一），这里我们用另一个文法来举例。

> 文法G2\[S\]：  
> S→bAb ①  
> A→(B ②  
> A→a ③  
> B→Aa) ④
> 
> 输入串为b(aa)b\#

1.  首先我们做出文法符号的优先关系矩阵：

这里\#比其相邻所有符号的优先性都要小。

1.  然后按照简单优先分析法进行归约：

<table> 
 <thead> 
  <tr> 
   <th>步骤</th> 
   <th>栈S</th> 
   <th>当前输入符</th> 
   <th>输入串剩余部分</th> 
   <th>动作</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td>1</td> 
   <td>#</td> 
   <td>b</td> 
   <td>(aa)b#</td> 
   <td>移进</td> 
  </tr> 
  <tr> 
   <td>2</td> 
   <td>#b</td> 
   <td>(</td> 
   <td>aa)b#</td> 
   <td>移进</td> 
  </tr> 
  <tr> 
   <td>3</td> 
   <td>#b(</td> 
   <td>a</td> 
   <td>a)b#</td> 
   <td>移进</td> 
  </tr> 
  <tr> 
   <td>4</td> 
   <td>#b(a</td> 
   <td>a</td> 
   <td>)b#</td> 
   <td>归约③</td> 
  </tr> 
  <tr> 
   <td>5</td> 
   <td>#b(A</td> 
   <td>a</td> 
   <td>)b#</td> 
   <td>移进</td> 
  </tr> 
  <tr> 
   <td>6</td> 
   <td>#b(Aa</td> 
   <td>)</td> 
   <td>b#</td> 
   <td>移进</td> 
  </tr> 
  <tr> 
   <td>7</td> 
   <td>#b(Aa)</td> 
   <td>b</td> 
   <td>#</td> 
   <td>归约④</td> 
  </tr> 
  <tr> 
   <td>8</td> 
   <td>#b(B</td> 
   <td>b</td> 
   <td>#</td> 
   <td>归约②</td> 
  </tr> 
  <tr> 
   <td>9</td> 
   <td>#bA</td> 
   <td>b</td> 
   <td>#</td> 
   <td>移进</td> 
  </tr> 
  <tr> 
   <td>10</td> 
   <td>#bAb</td> 
   <td>#</td> 
   <td></td> 
   <td>归约①</td> 
  </tr> 
  <tr> 
   <td>11</td> 
   <td>#S</td> 
   <td>#</td> 
   <td></td> 
   <td>接受</td> 
  </tr> 
 </tbody> 
</table>

其语法树如下：

![2869373-66185eacc00a4423.png][]

语法树

### 5.2.3 缺点 ###

缺点：适用范围小，分析表尺寸太大。

## 5.3 算符优先分析 ##

算符优先分析法是一种经典的自底向上分析法，简单直观，并被广泛使用。开始主要是对表达式的分析，现在已不限于此，可以用于一大类上下文无关文法（称为OPG）。  
**特点**：仿效四则运算过程，预先规定相邻终结符之间的优先  
关系，然后利用这种优先关系来确定句型的句柄（或句柄的变式），并进行规约。  
**分析器**：  
![在这里插入图片描述][9d790a65a00caae19dae66d15b7aaa78.png]  
优先关系矩阵示例：  
![在这里插入图片描述][a36ffb3a558359ee25047ba99dafc0a2.png]  
**分析步骤**：  
(1) 确定终结符之间的优先关系，构造优先关系矩阵。  
优先关系：  
![在这里插入图片描述][725b758ddd6c30b442ba57b11d18e566.png]  
（2）根据优先关系矩阵，利用算法：  
当栈顶项（或次栈顶项）终结符的优先级大于栈外的终结符的优先级则进行规约，否则移进。  
（3）出错情况

1.  相邻终结符之间无优先关系。
2.  对双目运算符进行规约时，符号栈中无足够项。
3.  非正常结束状态。

**重要说明**：  
（1）上述分析过程不一定是严格的最左规约（即不一定是规范规约）。也就是每次规约不一定是规约当前句型的句柄，而是句柄的变形，但也是短语。  
（2）实际应用中，文法终结符间优先关系一般不用矩阵表示，而是采用两个优先函数来表示：  
f — 栈内优先函数  
g — 栈外优先函数  
若 a < b 则令 f ( a ) < g ( b )  
若a = b 则令 f ( a ) = g ( b )  
若a > b 则令 f ( a ) > g ( b )  
特点：  
① 优先函数值不唯一。  
② 优点：  
• 节省内存空间。  
若文法有n个终结符，则关系矩阵为n^2，而优先函数为2n。  
• 易于比较：算法上容易实现。数与数比，不必查矩阵。  
③ 缺点：可能掩盖某些错误。

## 5.4 算符优先分析法的进一步讨论 ##

### 5.4.1 算符优先文法（OPG） ###

条件：  
①若文法中无形如U∷= …VW…的规则，这里V, W∈Vn，则称G为OG文法，也就是算符文法。  
即：**算符文法不允许两个非终结符相邻！**  
②在任意两个终结符之间，优先关系唯一，则称该文法为算符优先文法(OPG)。  
三种可能的优先关系的条件：  
![在这里插入图片描述][35046665bba06d5fba1df0547ea3c256.png]

### 5.4.2 构造优先关系矩阵 ###

![在这里插入图片描述][a47d09a83679ab729c9115edfab2595b.png]  
\[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-EDp6WYTe-1621077811435)(picture/20190107145710981.png)\]  
![在这里插入图片描述][fa9a1ebebf3c4c8b86af23842354c3aa.png]  
**构造FIRSTVT(U)的算法**：  
1)若有规则U∷= b…或U∷= V b… 则b∈FIRSTVT(U)（FIRSTVT的定义中一步推导）  
2)若有规则U∷= V…且 b∈FIRSTVT(V), 则b∈FIRSTVT(U)（FIRSTVT的定义中多步推导）  
有这两个集合后，按照以下规则确定这两种优先关系：  
![在这里插入图片描述][3ee5ec1a767881d864b4348c3433e1c5.png]  
**构造LASTVT(U)的算法**：  
1）若有规则U::=…a 或 U::=…aV，则a∈LASTVT(U)  
2）若有规则U::=…V，且a∈LASTVT(V) 则a∈LASTVT(U)  
**构造优先关系矩阵的算法**  
![在这里插入图片描述][656f27fda32dba9b8c657d2659ad6055.png]

#### 优先关系矩阵构造的自然语言描述 ####

（1）构造出FirstVt、LastVt集合。  
（2）找出规则右部所有VtVn、VnVt的组合。  
（3）对每个（2）中组合找出Vt和FirstVt集或LastVt集的关系。  
（4）整理关系，填表。

### 5.4.3 算符优先分析算法的实现 ###

先定义优先级，在分析过程中通过比较相邻运算符之间的优先级来确定句型的“句柄”并进行归约。  
这里的“句柄”实际上叫做：**最左素短语**。

##### 素短语 #####

定义：文法G的句型的素短语是一个短语。它至少包含有一个终结符号，并且除它自身以外不再包含其它素短语。  
*个人理解*：含有Vt的短语单元：不能从它里面截出更小的含Vt短语。  
**注意**：素短语可以不是简单短语！  
**最左素短语**  
设有OPG文法句型为:  
\#N1 a1 N2 a2 …Nn an Nn+1\#  
其中Ni 为非终结符(可以为空)，ai 为终结符。  
![在这里插入图片描述][69597719a482d5bffc5b4b1869b4bae8.png]  
**注意**：出现在 aj 左端和 ai 右端的非终结符号一定属于这个素短语，因为我们的运算是中缀形式给出的（OPG文法的特点）。  
*个人理解*：如果不把这两个Vn纳入素短语，经多步规约到某一步后，必然会出现两个Vn相邻情况，且其他情况的短语都已经规约完成了，而OPG不允许有这种规则右部，无法继续规约。  
**分析过程**：  
基本部分是找句型的最左子串（最左素短语）并进行规约：  
①当栈内终结符的优先级＜或＝栈外终结符的优先级时，移进；  
②当栈内终结符的优先级＞栈外终结符的优先级时，表明找到了素短语的尾，再往前找其头，并进行规约。  
③接受条件为符号栈只剩\#和开始符合，输入串只剩\#。

[0ca0d58adf28a18a750809992aff3337.png]: /images/20221020/fd1b862f77cf4f8f9a68d95e785e7b60.png
[80699c019bf40889bdedb947ce65b580.png]: /images/20221020/5685d1ee445a42bf9087d7c14c371ef7.png
[2869373-9da4aa12dcd3c1c7.png]: /images/20221020/3490970ca3844746884ce9a6e5bee76f.png
[2869373-6556e60491a33db0.png]: /images/20221020/f20e4381d0284601a88f41bf812e6fc4.png
[2869373-b21753552a961cd3.png]: /images/20221020/4f1cb766b6ef432aa4b2a44a4974442d.png
[2869373-05b519d51cb0d7c0.png]: /images/20221020/caf4f8f644654920929179325a30eb55.png
[2869373-66185eacc00a4423.png]: /images/20221020/050d214f35404f99bf6e37555bf782bb.png
[9d790a65a00caae19dae66d15b7aaa78.png]: /images/20221020/2691e5d0edb144be86bdcd04ea703fff.png
[a36ffb3a558359ee25047ba99dafc0a2.png]: /images/20221020/8d7d6980281a47319669eecd329bddfc.png
[725b758ddd6c30b442ba57b11d18e566.png]: /images/20221020/568309f84d774686927b43db2757de9c.png
[35046665bba06d5fba1df0547ea3c256.png]: /images/20221020/7b1495f9bea843ccaa16e452593a7de6.png
[a47d09a83679ab729c9115edfab2595b.png]: /images/20221020/6fa307a1ecce4b77b21e1e924e17c844.png
[fa9a1ebebf3c4c8b86af23842354c3aa.png]: /images/20221020/1ff47c6bee3047f793051ceaf201bab1.png
[3ee5ec1a767881d864b4348c3433e1c5.png]: /images/20221020/3cdecd6592df47e1a1d77fe71ed120a7.png
[656f27fda32dba9b8c657d2659ad6055.png]: /images/20221020/dcc076bcf31c496888e695f61966b43a.png
[69597719a482d5bffc5b4b1869b4bae8.png]: /images/20221020/624e512c88414dfa8edc091f0bf47135.png