# 第四章 语法分析

> 语法分析的前提：
>
> * 采用正规式和有限自动机扫描和识别语言的单词符号
> * 使用上下文无关文法来描述语法规则

## 1. 前情回顾

### 上下文无关文法

$$G = (V_T，V_N，P，S)$$&#x20;

* $$V_T$$ ：终结符集合（非空）
* $$V_N$$ ：非终结符集合（非空），$$V_T \bigcap V_N = \Phi$$&#x20;
* $$P$$ ：产生式集合（有限）
  * 产生式的一般形式： $$\alpha \rightarrow\beta$$  读作： $$\alpha$$ 定义为 $$\beta$$
    * $$\alpha \in V_N$$
    * $$\beta \in (V_T \bigcup V_N) ^ *$$&#x20;
* $$S$$ ：开始符号，$$S \in V_N$$&#x20;
* 开始符 $$S$$ 至少必须在某个产生式的左部出现一次

### 句型

如果 $$S \stackrel{*}\Longrightarrow \alpha$$ ，则称 $$\alpha$$ 是一个句型

### 句子

仅含终结符的句型是一个句子

### 语言

文法 $$G$$ 所产生的句子的全体是一个语言，记为 $$L(G)$$&#x20;

$$L(G) = \{ \alpha \mid S \stackrel{+}\Longrightarrow  \alpha, \alpha \in V_T^* \}$$&#x20;

### Hint

$$\alpha _1 \stackrel{*}\Longrightarrow \alpha_n$$ ： $$\alpha _1$$ 经过 0 步或若干步到达 $$\alpha_n$$&#x20;

$$\alpha _1 \stackrel{+}\Longrightarrow \alpha_n$$ ： $$\alpha _1$$ 经过 1 步或若干步到达 $$\alpha_n$$&#x20;

## 2. 语法分析器的功能

**语法分析的任务：**&#x5206;析一个文法句子的结构

**语法分析器的功能：**&#x6839;据文法产生式（语言的语法规则），判断输入符号串（单词串）是否为一个句子

![](https://123904567-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-M9-HnMHifkICpaw8S2c%2F-M9EYPT5X0jGhsJNtlvj%2F-M9EZRtAV-9FTiMWTeXT%2Fimage.png?alt=media\&token=fb0aaa96-f506-406f-930d-630261be254f)

## 3. 语法分析方法

### 3.1 自上而下分析法（Top-down）

**基本思想：**&#x4ECE;文法开始符号开始，反复使用各种产生式，寻找“匹配”的**推导**

**递归下降分析法**

* 对每一语法变量（非终结符）构造一个相应的子程序，每个子程序识别一定的语法单位
* 通过子程序间的相互调用实现对输入串的识别

**预测分析程序**

* 非递归实现
* 直观、简单

### 3.1 自下而上分析法（Bottom-up）

**基本思想**

* 从输入串开始，逐步开始归约，直到文法的开始符号
* **归约**：根据文法的产生式规则，把产生式的右部替换成左部符号
* 从树末端开始，构造语法树

**算法优先分析法**

* 按照终结符的优先级关系和结合性质进行语法分析
* 适合分析表达式

**LR 分析法**

* 规范归约

