第四章 语法分析

语法分析的前提：

• 采用正规式和有限自动机扫描和识别语言的单词符号

• 使用上下文无关文法来描述语法规则

1. 前情回顾

上下文无关文法

$G = (V_T，V_N，P，S)$

• $V_T$ ：终结符集合（非空）

• $V_N$ ：非终结符集合（非空），$V_T \bigcap V_N = \Phi$

• $P$ ：产生式集合（有限）

  • 产生式的一般形式： $\alpha \rightarrow\beta$ 读作： $\alpha$ 定义为 $\beta$

    • $\alpha \in V_N$

    • $\beta \in (V_T \bigcup V_N) ^ *$

• $S$ ：开始符号，$S \in V_N$

• 开始符 $S$ 至少必须在某个产生式的左部出现一次

句型

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

句子

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

语言

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

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

Hint

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

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

2. 语法分析器的功能

语法分析的任务：分析一个文法句子的结构

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

3. 语法分析方法

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

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

递归下降分析法

• 对每一语法变量（非终结符）构造一个相应的子程序，每个子程序识别一定的语法单位

• 通过子程序间的相互调用实现对输入串的识别

预测分析程序

• 非递归实现

• 直观、简单

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

基本思想

• 从输入串开始，逐步开始归约，直到文法的开始符号

• 归约：根据文法的产生式规则，把产生式的右部替换成左部符号

• 从树末端开始，构造语法树

算法优先分析法

• 按照终结符的优先级关系和结合性质进行语法分析

• 适合分析表达式

LR 分析法

• 规范归约