自顶向下分析概述

今天药忘吃喽~ 2022-03-16 00:52 431阅读 0赞

### 文章目录 ###

*  自顶向下的分析(Top-Down Parsing)
 *   *  最左推导(Left-most Derivation)
     *  最右推导
     *  最左推导和最右推导的唯一性
     *  最左推导例子
     *  自顶向下语法分析的通用形式
     *   *  递归下降分析(Recursive-Descent Parsing)
         *  预测分析(Predictive Parsing)

# 自顶向下的分析(Top-Down Parsing) #

*  从分析树的顶部（根节点）向底部（叶节点）方向构造分析树。
 *  可以看成是从文法开始符号 S S S推导出词串 w w w的过程。

文法：

1.   E → E + E E \\rightarrow\{E+E\} E→E\+E
2.   E → E ∗ E E \\rightarrow\{E\*E\} E→E∗E
3.   E → − E E \\rightarrow\{-E\} E→−E
4.   E → ( E ) E \\rightarrow\{(E)\} E→(E)
5.   E → i d E \\rightarrow\{id\} E→id

推导过程： E ⇒ − E ⇒ − ( E ) ⇒ − ( E + E ) ⇒ − ( i d + E ) ⇒ − ( i d + i d ) E \\Rightarrow\{-E \\Rightarrow\{-(E) \\Rightarrow\{-(E+E) \\Rightarrow\{-(id+E) \\Rightarrow\{-(id+id)\}\}\}\}\} E⇒−E⇒−(E)⇒−(E\+E)⇒−(id\+E)⇒−(id\+id)

**分析树：**

![未命名文件 (2)][_2]

*  每一步推导中，都需要做两个选择：
    
     *  替换当前句型中的**哪个非终结符**
     *  用该非终结符的**哪个候选式**进行替换

## 最左推导(Left-most Derivation) ##

在最左推导中，总是选择每个句型的**最左非终结符**进行替换

**例如：**

文法：

输入：  
 i d + ( i d + i d ) id+(id+id) id\+(id\+id)

推导过程：

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

注：1. 最左推导的逆过程称为最右规约。  
2. 如果 S ⇒ l m ∗ α S \\Rightarrow\{^\*\_\{lm\} \\alpha\} S⇒lm∗α，则称 α \\alpha α为当前文法的**最左句型**（left-sentential form）。（lm意为left most）

## 最右推导 ##

在最右推导中，总是选择每个句型的最右非终结符进行替换。

**例如：**

文法：

输入：  
 i d + ( i d + i d ) id+(id+id) id\+(id\+id)

推导过程：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2hqYzI1Ng_size_16_color_FFFFFF_t_70 1]

注： 1.最右推导的逆过程称为最左规约。  
2. 在自底向上的分析中，总是采用最左规约的方式因此把**最左规约称为规范规约**，而**最右推导相应地称为规范推导**。

## 最左推导和最右推导的唯一性 ##

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

给定一棵如上图所示分析树，其推导过程**不是唯一的**。因为可以选择句型中任意非终结符来进行替换。**但是，一个分析树的最左和最右推导都是唯一的。因为在推导的每一步，当前句型的最左或最右非终结符都是唯一的。**

**因为分析器是自左向右的扫描字符串，所以自顶向下的语法分析采用最左推导方式。**

## 最左推导例子 ##

文法：

1.   E → T E ′ E \\rightarrow\{TE&\#x27;\} E→TE′
2.   E ′ → T E ′ ∣ ϵ E&\#x27; \\rightarrow\{TE&\#x27;\} | \\epsilon E′→TE′∣ϵ
3.   T → F T ′ T \\rightarrow\{FT&\#x27;\} T→FT′
4.   T ′ → ∗ F T ′ ∣ ϵ T&\#x27; \\rightarrow\{^\*FT&\#x27;\} | \\epsilon T′→∗FT′∣ϵ
5.   F → ( E ) ∣ i d F \\rightarrow\{(E) | id\} F→(E)∣id

输入：

i d + i d ∗ i d id + id \* id id\+id∗id

**分析树：**

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

因为该分析树的叶节点从左到右排列与输入相同，所以输入是这个文法的一个句子。

## 自顶向下语法分析的通用形式 ##

### 递归下降分析(Recursive-Descent Parsing) ###

*  由一组过程组成，每个过程对应一个非终结符
 *  从文法开始符号 S S S对应的过程开始，其中递归调用文法中其他非终结符对应的过程。如果 S S S对应的过程体恰好扫描了整个输入串，则成功完成语法分析。

伪代码形式，**以下即为一个过程**：

C + + v o i d A ( ) / / 选 择 一 个 A 产 生 式 ， 根 据 当 前 输 入 的 终 结 符 来 选 f o r ( i = 1 t o k ) i f ( x i 是 一 个 非 终 结 符 号 ) 调 用 过 程 x i ( ) ; / / x i ( ) 就 是 这 一 候 选 式 对 应 的 方 法 类 似 于 A ( ) e l s e i f ( x i 等 于 当 前 的 输 入 符 号 ) 读 入 下 一 个 输 入 符 号 ; C++ void A()\{ //选择一个A产生式，根据当前输入的终结符来选 for(i=1 to k)\{ if(xi是一个非终结符号)\{ 调用过程xi(); //xi()就是这一候选式对应的方法 类似于A() \} else if(xi等于当前的输入符号)\{ 读入下一个输入符号; \} \} \} C\+\+voidA()//选择一个A产生式，根据当前输入的终结符来选for(i=1tok)if(xi是一个非终结符号)调用过程xi();//xi()就是这一候选式对应的方法类似于A()elseif(xi等于当前的输入符号)读入下一个输入符号;

在递归下降分析的过程中，可能会出现有多个以当前输入的终结符开头的产生式，所以就要一个一个试，这就可能要回溯的情况，效率较低。

需要回溯的分析器，称作**不确定**的分析器。

### 预测分析(Predictive Parsing) ###

**预测分析**是递归下降分析的一个特例，它不需要回溯（通过剪枝），是一种确定的自顶向下分析方法，通过在输入中向前看固定个数（通常为1）个符号来选择正确的A-产生式。

可以对某些文法构造出向前看k个输入符号的预测分析器，该类文法又是也称为 **LL(k)** 文法类。

[_2]: https://note.youdao.com/yws/res/5015/658AD2F0F7B24D4C813CA53F06B220C7
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2hqYzI1Ng_size_16_color_FFFFFF_t_70]: /images/20220316/65f55b881131467194cb2421e8e71d05.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2hqYzI1Ng_size_16_color_FFFFFF_t_70 1]: /images/20220316/7e4db49a699242c2a6be176b2faaa59b.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2hqYzI1Ng_size_16_color_FFFFFF_t_70 2]: /images/20220316/192bbe692d604d4283fdcf2329bbedd2.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2hqYzI1Ng_size_16_color_FFFFFF_t_70 3]: /images/20220316/a847d209df334d3bb892a795c9f5b470.png