国防科技大学 编译原理 第11讲 语法分析——自下而上分析2

课程主页：

https://www.icourse163.org/course/NUDT-1003101005?tid=1460976445

这次回顾第11讲：语法分析——自下而上分析2。

第11讲 语法分析—自下而上分析2(LR分析法)

LR分析法概述

自下而上分析法(Bottom-up)

• 基本思想
  • 从输入串开始，逐步归约，直到文法的开始符号
  • 归约：根据文法的产生式规则，把串中出现的产生式的右部替换成左部符号
  • 从树叶节点开始，构造语法树
• 算符优先分析法
  • 按照算符的优先关系和结合性质进行语法分析
  • 适合分析表达式
• LR分析法
  • 规范归约：句柄作为可归约串

LR分析法

• 1965年由Knuth提出
• L：从左到右扫描输入串
• R：自下而上进行归约

工作框架如下：

句柄和规范归约

短语、直接短语和句柄

• 定义：令$G$是一个文法，$S$是文法的开始符号，假定$\alpha\beta\delta$是文法$G$的一个句型，如果有

  $$S\overset{\star}⇒αAδ 且 A\overset{+}⇒β$$

  则称$\beta$是句型$\alpha\beta\delta$相对于非终结符$A$的短语。

• 如果有${A} \Rightarrow \beta$，则称$\beta $是句型$\alpha\beta\delta$相对于规则$A\to b$的直接短语。

• 一个句型的最左直接短语称为该句型的句柄。
• 在一个句型对应的语法树中
  • 以某非终结符为根的两代以上的子树的所有末端结点从左到右排列就是相对于该非终结符的一个短语
  • 如果子树只有两代，则该短语就是直接短语
  • 最左两代子树末端就是句柄

用句柄归约

• 可用句柄来对句子进行归约

规范归约

• 定义：假定$α$是文法$G$的一个句子，我们称序列$α_n,α_{n-1},\ldots,α_0$是$α$的一个规范归约，如果此序列满足：
  • $α_n= α$
  • $α_0$为文法的开始符号，即$α_0=S$
  • 对任何$i$，$0 ≤ i ≤ n$，$α_{i-1}$是从$α_i$经把句柄替换成为相应产生式左部符号而得到的

算符优先分析vs. 规范归约

算符优先分析一般并不等价于规范归约

规范句型

• 规范归约是最左归约

• 规范归约的逆过程就是最右推导

  $$S \Rightarrow aAcBe\Rightarrow aAcde \Rightarrow aAbcde \Rightarrow abbcde$$

• 最右推导也称为规范推导

• 由规范推导推出的句型称为规范句型

LR分析法

规范归约vs. 句柄

• 规范归约的关键问题是寻找句柄。
  • 历史：已移入符号栈的内容
  • 展望：根据产生式推测未来可能遇到的输入符号
  • 现实：当前的输入符号

LR分析器的结构

• LR分析方法：把”历史”及”展望”综合抽象成状态；由栈顶的状态和现行的输入符号唯一确定每一步工作

LR分析表

• LR分析器的核心是一张分析表
  • $\text{ACTION}[s, a]$：当状态$s$面临输入符号$a$时，应采取什么动作
  • $\text{GOTO}[s, X]$：状态$s$面对文法符号$X$时，下一状态是什么

分析表中的符号解释：

• 移进(shift, s)：把$(s,a)$的下一状态$s’$和输入符号$a$推进栈，下一输入符号变成现行输入符号
• 归约(reduce, r)：用某产生式$A→β$进行归约。假若$β$的长度为$r$，去除栈顶$r$个项，使状态$s_{m-r}$变成栈顶状态，然后把下一状态$s’=\text{GOTO}[s_{m-r}, A]$和文法符号$A$推进栈
• 接受(acc)：宣布分析成功，停止分析器工作
• 空格：报错

LR分析过程

• 分析开始时:

  $$\begin{aligned} &状态栈 &符号栈 &&输入串\\ &(s_0, &\sharp, &&a_1a_2\ldots a_n \sharp) \end{aligned}$$

• 以后每步的结果可以表示为:

  $$(s_0 s_1\ldots s_m, \sharp X_1 \ldots X_m, a_ia_{i+1}\ldots a_n \sharp)$$

• 具体来说：

  

  此处, $s=\text{GOTO}(s_{m-r}, A)$，$r$为$β$的长度, $β= X_{m-r+1}\ldots X_m$

• 若$\text{ACTION}(s_m , a_i)$为“接受”，则格局变化过程终止，宣布分析成功。

• 若$\text{ACTION}(s_m ,a_i)$为“报错”，则格局变化过程终止，报告错误。

LR分析示例

根据文法$G(E)$：

$$\begin{aligned} (1)& \mathrm{E} \rightarrow \mathrm{E}+\mathrm{T}\\ (2)& \mathrm{E} \rightarrow \mathrm{T}\\ (3)& \mathrm{T} \rightarrow \mathrm{T}^{*} \mathrm{F}\\ (4)& \mathrm{T} \rightarrow \mathrm{F}\\ (5)& \mathrm{F} \rightarrow(\mathrm{E})\\ (6)& \mathrm{F} \rightarrow \mathrm i \end{aligned}$$

分析输入串$i\star i+i$。

LR分析表为：

分析过程：

LR文法

LR文法

• 定义：对于一个文法，如果能够构造一张分析表，使得它的每个入口均是唯一确定的，则这个文法就称为$\mathrm {LR}$文法。
• 定义：一个文法，如果能用一个每步顶多向前检查$k$个输入符号的$\mathrm {LR}$分析器进行分析，则这个文法就称为$\text{LR}(k)$文法。

LR文法与二义文法

• LR文法不是二义的，二义文法肯定不会是LR的
• LR文法$\subset $无二义文法

小结

• LR分析器的工作原理
• LR分析器的性质
  • 栈内的符号串和扫描剩下的输入符号串构成了一个规范句型
  • 一旦栈的顶部出现可归约串(句柄)，则进行归约