概述

编译的几个阶段

C/C++编译的几个阶段是：

• 预处理：汇合源程序，展开宏定义，生成.i文件
• 编译：处理后的源文件到汇编代码文件
• 汇编：汇编代码文件到目标文件/机器指令文件
• 连接：连接库代码从而生成可执行（executable）文件

编译过程

编译过程分为：

• 前端（分析）：对源程序，识别语法结构信息，理解语义信息，反馈出错信息
  • 词法分析
  • 语法分析
  • 语义分析

• 后端（综合）：综合分析结果，生成语义上等价于源程序的目标程序

  • 中间代码生成

  • 代码优化

  • 目标代码生成

词法分析

针对token

语法分析

针对语句

语义分析

针对整个程序

中间代码生成

也就是生成一个等价的、易于优化的中间表示

代码优化

删掉不必要的代码

目标代码生成

生成汇编

语言和文法基础

语言和文法的直观概念

程序设计语言包括：语法和语义

• 语法：是一组规则，用它可以形成和产生一个合适的程序
• 语义：定义程序的意义

文法：是语言语法的描述工具，实现用有穷的规则把语言的无穷句子集描述出来。比如<句子>=<主语><谓语＞，可以用右端的符号串代替=的左端

符号和符号串

字母表：字母表是元素的非空有穷集合。例如A={a,b,c}。

符号串：符号串是由字母表中的符号组成的任何有穷序列。a,ab,aaca是A={a,b,c}上的符号串。

• 在符号串中，符号是有顺序的，顺序不同，代表不同的符号串

• 不含任何符号的符号串称为空串，用$ε$表示。注意：$\{\epsilon\}$并不等于空集合$\{\}$即$\Phi$

• 符号串长度：是符号串中含有符号的个数。例：$|abc|=3$

• 符号串的头尾，固有头和固有尾：如果$z=xy$是一符号串，则$x$是$z$的头，$y$是$z$的尾。如果$x$是非空的，则$y$是固有尾；如果$y$非空，则$x$是固有头。

  例：$z=abc$，$z$的头：$\epsilon$，$a$，$ab$，$abc$，除$abc$外，其他都是固有头

符号串的运算

符号串的连接：设$x$、$y$是符号串，它们的连接是把$y$的符号写在$x$的符号之后得到的符号串$xy$

符号串的方幂：把符号串$a$自身连接$n$次得到的符号串

符号串集合

若集合$A$中所有元素都是某字母表$\Sigma$上的符号串，则称$A$为字母表$\Sigma$上的符号串集合。

符号串集合$A$和$B$的乘积定义为：$AB =\{xy|x\in A 且 y\in B\}$，即AB是由A中的串x和B中的串y连接而成的所有串xy 组成的集合。

符号串集合的方幂：设$A$是符号串的集合，则称$A$为符号串集$A$的方幂，其中$i$是非负整数。具体定义如下：

集合的闭包

集合 $\Sigma$ 的闭包 $\Sigma^*$ 定义如下：

$\Sigma^+=\Sigma^1\cup\Sigma^2\cup\Sigma^3\cup…$称为$\Sigma$的正闭包。

$\Sigma^*$上任意字符串的集合均是该字母表$Σ$上的语言

文法的定义

文法定义:

• 文法$G$定义为四元组$(V_N, V_T, P, S)$

  • $V_N$ : 非终结符集
  • $V_T$ : 终结符集
  • $P$ : 产生式(规则)集合
  • $S$ : 开始符号或识别符号

• 产生式(规则):

  • 产生式是一个有序对$(a,β)$，通常写作$a→β$(或$a ::= β$)(读作：$a$定义为$β$)

$V_N, V_T \text{和} P \text{是非空有穷集}$

$V = V_N \cup V_T, V \text{称为文法G的字母表}$

$V_N \cap V_T = \Phi$

$S \text{是一个非终结符，且至少要在一条产生式的左部出现}$

$P$中产生式形如:$\alpha\rightarrow\beta$,其中:$\alpha\in V^+$且至少含一个非终结符,$\beta\in V^*$

通常不用将文法的四元组表示出来，只写出产生式:

• 默认第一条产生式的左部的符号是开始符号，或用$G[S]$表示$S$是开始符号；
• 用大写字母（或用尖括号括起来）表示非终结符；
• 用小写字母表示终结符；
• 左部相同的产生式$A \rightarrow \alpha$，$A\rightarrow \beta$可以记为；$A\rightarrow \alpha |\beta$，其中“$|$”表示“或”

推导与规约

$\alpha \rightarrow \beta$ 是文法 $G$ 的产生式，若有 $v, w$ 满足： $v=\gamma \alpha \delta, w=\gamma \beta \delta$ ，其中 $\gamma, \delta \in V^{*}$ ，则称：

• $v$ 直接推导到 $w$
• 或称： $w$ 直接归约到 $v$
• 记作： $v \Rightarrow w$

若存在${v}={w}_0\Rightarrow{w}_1\Rightarrow\ldots\Rightarrow{w}_n={w}_i(n>0)$（即${v}$经过多步推到${w}$），则称：

• $v$推导出$w$
• 或称：$w$归约到$v$
• 记为：$v=*>w$

若$v=+>w$，或$v=w$，则记作$v=*>w$

句型、句子、语言的定义

句型：由文法开始符号$S$推导出的符号串$\alpha$，称为文法$G[S]$的句型

句子：仅由终结符组成的句型$\alpha$，称为文法$G[S]$的句子。

语言：文法$G[S]$的一切句子的集合称为语言

文法的等价

若两个文法所定义的语言是一样的，则称两个文法是等价的

文法的类型

通过对产生式施加不同的限制，Chomsky将文法分为四种类型：

• 0型：

  

• 1型（上下文有关文法）:

  

• 2型（上下文无关文法）:

  

• 3型（正规文法）

上下文无关文法及其语法树

如果在推导的任何一步$\alpha\rightarrow \beta$，其中$\alpha$、$\beta$是句型，都是对$\alpha$中的最左非终结符进行替换，则称这种推导为最左推导；同理，如果是总对最右的非终结符进行替换，则称为最右推导

最右推导被称为规范推导。

语法树

文法的二义性

定义：如果一个文法存在某个句子对应两棵不同的语法树，则说这个文法是二义的

二义性文法存在某个句子，它有两个不同的最左（右）推导

任何一个二义性的文法，都可以转换成一个等价的无二义性文法。

句型分析

任务：句型分析就是识别一个符号串是否为某文法的句型，是某个推导的构造过程。

自上而下的分析方法：从文法的开始符号出发，反复使用文法的产生式，寻找与输入符号串匹配的推导。主要问题是选择产生式

自下而上的分析方法：从输入符号串开始，逐步进行归约，直至归约到文法的开始符号。自下而上分析的主要问题：如何确定“可归约串”——“句柄”。

短语，直接短语和句柄

有关文法实用中的一些说明

有害规则：$U \rightarrow U$：无用且引起文法的二义性。

多余规则：所有句子推导都用不到的规则，表现在：

1. 不可到达：文法中某些非终结符不在任何规则的右部出现，所以任何句子的推导中都无法用到它。
2. 不可终止：不可推导出终结符号串的非终结符。

上下文无关文法中允许使用$A \to \varepsilon$产生式，$A \to \varepsilon$称为$\varepsilon$规则

词法分析

概述

词法分析：扫描源程序字符流，识别并分解出有词法意义的单词或符号

Token：词，最小意义单元

• 每个token类别对应一个字符串集合

词法分析器也称标记化Tokenization或扫描器Scanner，得到的token会被送入语法分析器

实现时需完成2件事情：

• 识别字符串的token分类
• 返回token的值或词素

一个token是一个二元组（class, lexeme）

词法规范

三种词法规范：

• 表达式：
  • 正则表达式：正则表达式可用于定义token class
  • 正则定义
• 语法：
  • 正规文法
• 有穷自动机：
  • 确定的有穷自动机
  • 不确定的有穷自动机

正则表达式

有穷自动机

转换图

结点：状态

初始状态：只有一个，一般由没有出发结点的箭头表示

最终状态：可以有多个，用双圈表示

边：从一个状态指向另一个状态

有穷自动机

正则表达是定义、自动机是实现。

自动机［Automata］：一个机器或一个程序

有穷自动机［Finite Automata， FA］：具有有穷个状态的程序

有穷自动机基于转换图：

• 有状态和标记的边
• 有一个唯一的开始状态和一个或多个最终状态

DFA和NFA

DFA：机器在任何给定时间只能以一种状态存在（确定）：

• 每个状态对于每个输入只对应一个转换
• 没有ε转移 [ε-moves]
• 只通过状态图的一条路径

DFA：机器可以同时以多种状态存在（非确定）：

• 在给定状态下，对一个输入可以有多个转换
• 可以有ε转移 [ε-moves]
• 多条路径：可以选择采取哪条路径

转换和等价

流程: RE→NFA→DFA→Table-drive Implementation

RE→NFA

NFA→DFA

ε闭包构造算法

子集构造算法

DFA化简

【编译原理正规表达式转NFA到DFA再化简】

语法分析

自顶向下语法分析

问题

改写文法

提取左公因子

规则：

• 提取左公因子，将产生式 $A \rightarrow \alpha\beta | \alpha r$ 等价变换为：$A \rightarrow \alpha (\beta | r)$
• 将括号内用一新引入的非终结符 $A’$ 表示，得：$A \rightarrow \alpha A’$，$A’ \rightarrow \beta | r$

一般形式：

• 若 $A \rightarrow \alpha\beta_1 | \alpha\beta_2 | \ldots | \alpha\beta_n$，提取左公共因子后变为：$A \rightarrow \alpha (\beta_1 | \beta_2 | \ldots | \beta_n)$

• 引进新的非终结符 $A’$，得：$A \rightarrow \alpha A’$，$A’ \rightarrow \beta_1 | \beta_2 | \ldots | \beta_n$

• 若在 $\beta_i$ 中仍含有左公共因子，可再次提取。

消除左递归

消除直接左递归

规则:

• 引入新的非终结符 $A’$，将产生式 $A \rightarrow A\alpha | \beta$ 改写成：$A \rightarrow \beta A’$，$A’ \rightarrow \alpha A’ | \varepsilon$

为什么能确保等价性？

• 原产生式 $A \rightarrow A\alpha | \beta$ 的语言：$\beta, \beta\alpha, \beta\alpha\alpha, …$，即 $\beta$ 后跟零个或多个 $\alpha$，隐式终止递归（不再调用 $A \rightarrow A\alpha$ 时）。

• 现产生式 $A \rightarrow \beta A’$，$A’ \rightarrow \alpha A’ | \varepsilon$ 能产生同样的语言，变换成右递归，且利用 $\varepsilon$ 产生式显式终止递归。

一般形式：

• 若 $A \rightarrow A\alpha_1 | A\alpha_2 | … | A\alpha_m | \beta_1 | \beta_2 | … | \beta_n$，则消除左递归后改写成：

  • $A \rightarrow \beta_1 A’ | \beta_2 A’ | … | \beta_n A’$

  • $A’ \rightarrow \alpha_1 A’ | \alpha_2 A’ | … | \alpha_m A’ | \varepsilon$

消除间接左递归

具体步骤：

1. 把文法的所有非终结符按任一顺序排列，如：$A_1$，$A_2$，…，$A_n$。
2. 从 $A_1$ 开始，按以下顺序处理 $A_i$：
   • 首先，消除左部为 $A_i$ 的产生式的直接左递归；
   • 然后，若左部为 $A_i$ 的产生式的右部为非终结符 $A_j$($j<i$)开头，即 $A_i→A_j…$，则用左部为 $A_j$的所有产生式的右部分别代替$A_i→Aj…$中的$A_j$；
   • 最后，得到的左部为 $A_i$ 的产生式若有直接左递归，则消除之。
3. 去掉无用产生式。

消除二义性

消除ε产生式

1. 将每个产生式右部的非终结符均替换成ε：如果该非终结符能推出ε的话。
2. 列出所有可能性：确保所有可能的替换都被考虑。
3. 对每个产生式应用规则：对于形式为 $A → X_1X_2…X_n$ 的产生式，其中 $X_i ∈ Σ ∪ N$, $1 ≤ i ≤ n$。
4. 增加新产生式：形成新的产生式 $A → a_1a_2…a_n$，其中：
   • 如果 $X_i =>* ε$，则 $a_i = X_i$ 或 $a_i = ε$；
   • 如果 $X_i ≠* ε$，则 $a_i = X_i$；
   • 条件是 $1 ≤ i ≤ n$，且 $a_i ≠ ε$。

确定的自顶向下语法分析

FIRST集

如果由同一非终结符的两个产生式的右部推导出来的开始符号集不相交，因此可根据当前输入符属于哪个产生式右部的开始符号集而决定唯一选哪个产生式进行推导，可以进行确定的自顶向下分析。

FOLLOW集

注意：$\varepsilon$不存在于任何FOLLOW集中

LL(1)文法

含义

• 第一个 L 表示从左到右扫描输入串。
• 第二个 L 表示分析过程用最左推导。
• 1 表明只需向前看一个符号便可以决定选哪个产生式进行推导。类似地，LL(k) 文法需要向前看 k 个符号才可以确定选用哪个产生式。

  定义

  一个上下文无关文法是 LL(1) 文法的充分必要条件是，若存在产生式 A → α | β，则需同时满足以下两个条件：

1. $ \text{FIRST}(α) ∩ \text{FIRST}(β) = ∅ $
2. 若 $ ε ∈ \text{FIRST}(β) $，则 $ \text{FIRST}(α) ∩ \text{FOLLOW}(A) = ∅ $

满足上述条件的 LL(1) 文法就能进行确定的自顶向下分析。

递归下降预测分析

概念：

• 基于手写代码实现，每个非终结符对应一个递归函数。

• 通过函数的递归调用模拟推导过程，显式地编码产生式的选择（通常通过if else或switch分支实现）。

• 可以是$LL(1)$文法，也可以是更强的$LL(k)$（通过向前看更多符号解决冲突）。

步骤

画转换图

对每个非终结符$A$：

• 创建初始状态和结束状态。
• 对于每个$A \to X_1X_2\cdots X_n$，创建一条从初始状态到最终状态的路径，边标记为$X_1$，$X_2$，$\cdots$，$X_n$。
• 如果$A \to \varepsilon$：表示路径为$\varepsilon$。

化简转换图

有点像DFA化简（如果两个状态是等价的，就可以合并。只不过那里都是终结符，而这里可以有非终结符）

编写解析器

为每个图编写递归过程，开始符号 S对应的转换图是程序的主要 main 入口。

设计程序的控制流，模仿图中的路径，考虑到前瞻：

• 如果路径中边的符号等于终结符，则执行 匹配 [match] 动作。
• 如果路径中边的符号是非终结符，则执行 派生 [derive] 操作，即调用非终结符的过程（递归）。

LL（1）分析

前提条件

LL（1）分析：

• 表驱动：依赖预先计算的预测分析表。
• 使用统一的算法（栈 + 表驱动）：通过查表决定下一步动作。
• 文法规则：必须严格满足LL(1)文法规则。

构造预测分析表

对于文法$G$的每个产生式$A \to \alpha$：

• 对于$\text{FIRST}(\alpha)$中的每个终结符$a$，将$A \to \alpha$填入表$M[A,a]$中；
• 如果$\varepsilon \in \text{FIRST}(\alpha)$，则对于$\text{FOLLOW}(A)$中的每个终结符$a$，将$A \to \alpha$填入表$M[A,a]$中，此时如果$$\in \text{FOLLOW}(A)$，也将$A \to \alpha$填入表$M[A,$]$中。

错误恢复

错误类型：

• 终结符不匹配：栈顶符号和下一个输入符号不匹配
• $M[A,a]$为空：无候选产生式
• 栈为空，输入符号仍有剩余

恐慌模式：

• 是一种错误恢复策略。
• 恐慌：遇到危险先跑再说，不尝试精确修复错误，直接跳过。
• 目标：让parser尽快回到可以继续分析的状态，而不是纠结于错误的细节。

规则：

• 将$FOLLOW(A)$的所有符号都放到$A$的同步集合中，即，对于$a\in FOLLOW(A)$，预测分析表中$M[A, a]$处均填写synch。
• 如果$M[top, lookahead]==empty$，则跳过$lookhead$字符，栈保持不变。
• 如果$M[top, lookahead]==synch$，则跳过栈顶$top$，将栈顶弹出，输入字符不变。
• 如果$top\neq lookahead$，则同样跳过栈顶$top$，将栈顶弹出，输入字符不变。

自底向上语法分析

规范归约：

• 自底向上分析的归约过程是自顶向下推导的逆过程。
• 最右推导为规范推导，所以自左向右的归约称为规范归约。

在自底向上的分析方法中，每一步都是从当前串中选择一个子串加以归约，该子串暂称“可归约串”。可选择：

• 句柄(最左直接短语)
• 最左素短语

移进-归约

Shift-Reduce分析：

• 引进一个先进后出的符号栈来存放符号。
• 对输入符号串自左向右进行扫描，并把当前输入符号下推入栈中（移进），边移进边分析，一旦栈顶符号串形成某个句型的句柄（为某产生式的右部）时，就用相应的非终结符（产生式的左部）替换它（归约）。
• 重复这一过程，直到输入符号串的末端，此时如果栈中只剩文法开始符号，则输入符号串是文法的句子，否则不是。

算符优先分析

基本思想：只定义文法中终结符之间的优先关系（不考虑非终结符），并由这种关系指导分析过程。

• 性质：不是规范归约。
• 优点：算符优先分析法分析速度快，特别适用于表达式的分析。
• 缺点：不规范，常常要采用适当措施克服其缺点。
• 前提：文法必须是算符文法。

算符文法：设有上下文无关文法$G$，如果$G$中产生式的右部没有两个非终结符相连，则称$G$为算符文法。

算符优先

优先关系只存在于句型中相邻出现的符号。

算符优先分析法只考虑终结符之间的优先关系，不考虑非终结符，所以两个终结符相邻指它们之间没有其他的终结符(但可以有非终结符)。

如：$E+T×i$，则$+$和$×$相邻，$×$和$i$相邻，但$+$和$i$不相邻。

算符有三种优先关系：

• $a < b$：表示$a$的优先级低于$b$。
• $a = b$：表示$a$的优先级等于$b$。
• $a > b$：表示$a$的优先级高于$b$。

注意:

• $\lt$，$=$，$\gt$是偏序关系：
  • 不具备自反性：$a$不一定$=a$。
  • 不具备对称性：$a\lt b$不意味着$b\gt a$，$a = b$不意味着$b = a$。
  • 不具备传递性：$a\lt b$，$b\lt c$不意味着$a\lt c$。
• 算法优先关系仅考虑相邻两个终结符之间的关系，若终结符$a$和$b$在任何句型中都不相邻，则无法比较它们的优先关系。

最左素短语

设有文法$G[S]$，其句型的素短语是一个短语，它至少包含一个终结符，并除自身外不包含其它素短语。最左边的素短语称为最左素短语。因此，找素短语，就要先找短语。

算法

将输入符号串 $a_1a_2\cdots a_t$ 依次逐个存入符号栈 $S$ 中，直至符号栈顶终结符 $a_j$ 与当前输入符 $a_{j + 1}$ 的关系为 $a_j \succ a_{j + 1}$ 为止；

$a_j$后有非终结符也没关系

最左素短语尾已在符号栈 $S$ 的栈顶，由栈顶向下找最左素短语的头符号，即找到第一个 $\prec$ 关系 $a_{i - 1} \prec a_i$；

已找到最左素短语 $N_ia_iN_{i + 1}a_{i + 1}\cdots N_ja_jN_{j + 1}$（其中 $N_k$（$i\leq k\leq j + 1$）为非终结符或空），用相应的产生式进行归约；

重复上述过程，当处理到输入符号串尾时，若栈中只剩：$\cdots$，若栈中只剩：$N$（$N$ 为任何一个非终结符），则分析成功，否则分析失败。

优先函数

LR分析

自底向上分析法的关键问题是在分析过程中如何确定句柄。

• LR分析法：根据当前分析栈中的符号串（通常以状态表示）和向前顺序查看输入串的$k$个符号$(k\geq0)$就可唯一地确定句柄。
• 目前最流行的自底向上语法分析器都是基于$LR(k)$语法分析，其中：
  • $L$表示从左到右扫描输入串。
  • $R$表示最左规约（即最右推导的逆过程）。
  • $k$表示向前查看输入串符号的个数。
    • 当($k = 1$)时，能满足当前绝大多数高级语言编译程序的需要，所以着重介绍$LR(0), SLR(1), LR(1), LALR(1)$方法。
    • 省略$k$时，一般指$k = 1$。

LR分析的特点:

• 是规范归约（最右推导/规范推导的逆过程）
• 适用范围广
• 分析速度快
• 在对输入进行自左到右扫描时能尽早准确定位错误
• 缺点：LR分析器构造的工作量

LR(0)分析

根据当前符号栈中的符号串和向前顺序查看输入串的0个符号就可唯一地确定句柄以进行归约，即，仅凭符号栈中的符号串即可确定句柄，做出归约决定，不需要向前查看输入符号。

对文法的限制较大，对绝大多数高级语言的语法分析器不适用。

项目[item]

LR语法分析器通过维护一些状态，用这些状态来表明我们在语法分析过程中所处的位置，从而做出shift或reduce决定

状态由项目[item]集表示，在文法G中每个产生式的右部适当位置添加一个圆点构成项目

例：产生式$A→XYZ$对应有4个项目

1. $A→ • XYZ$

2. $A→X • YZ$

3. $A→XY • Z$

4. $A→XYZ •$

产生式$A→\varepsilon$只有一个项目$A→•$

项目=在产生式上加圆点

含义

圆点在最左部（$A \to • XYZ$）表示希望用产生式的右部归约。

圆点的左部（$A \to X • YZ$）表示分析过程中已识别过的部分。

圆点的右部（$A \to X • YZ$）表示待识别部分。

圆点达到最右边（$A \to XYZ •$）表示句柄已形成，可以进行归约。

分类

LR（0）项目集

为了构造文法的LR（0）项目集，需定义拓广文法 [augmented grammar]和两个函数：CLOSURE函数和GOTO函数。

LR（0）分析算法

构造DFA：

构造分析表：

这里的GOTO(k,a)指的是DFA上箭头的标签。GOTO[k,B]指的是GOTO表。

分析：

$\text{ACTION[S,a]}$中的$\text{S}$是状态栈栈顶的值，$\text{a}$是符号栈栈顶的值

LR(0)DFA识别的语言

可行前缀：

规范句型是指通过最右推导生成的句型

有效项目：

SLR(1)分析

项目冲突

项目集中的冲突：一个项目集中存在下列情况称为项目冲突：

• 移进-归约冲突：移进项目$A→α•aβ$和归约项目$B→r•$同在一个项目集中，当面临输入符$a$时，不能确定移进$a$还是把$r$归约为$B$；

• 归约-归约冲突： 归约项目$A→β•$和归约项目$B→r•$同在一个项目集中，不管面临什么输入符，都不能确定把$β$归约为$A$还是把$r$归约为$B$。

构造ACTION和GOTO表的时候会有不确定性

一个文法的$LR(0)$项目集规范族中的项目集不存在移进-归约冲突，也不存在归约-归约冲突时，称该文法为$LR(0)$文法

SLR(1)分析方法可解决这种冲突：

• 基本思想：对于LR(0)有冲突的项目集，用向前查看输入符号串的 $1$ 个符号的办法加以解决。

• 解决方法：对归约项目 $A→r•$ ，只有当输入符号 $a$ ∈ $FOLLOW(A)$ 才进行归约，缩小归约范围，有可能解决冲突。

方法

一个LR(0)项目集$I$含有冲突项目$I = \{X→α•bβ，A→r• ，B→δ•\}$，其中$b∈V_T$。如果$FOLLOW(A)$和$FOLLOW(B)$互不相交，且不含$b$，则当状态$I$面临某输入符$a$时，可采用下列动作：

• 若$a = b$，则移进；

• 若$a∈FOLLOW(A)$，则用产生式$A→r$归约；

• 若$a∈FOLLOW(B)$，则用产生式$B→δ$归约；

• 此外，报错。

如果一个文法的LR(0)项目集中某些项目集所含有的动作冲突都能用$SLR(1)$方法解决，则称这个文法为$SLR(1)$文法。$SLR(1)$的$S$是simple的意思

构造时仅对表格中有冲突的行采用SLR(1)方法区分移进或归约对应的列。

LR(1)分析

如果 $\text{Follow}(R)=\{ $, =\}$ 与移进符号集 $\{=\}$ 交集不为空，SLR(1) 方法不能解决冲突，该文法不是 SLR(1) 文法。

LR(1)项目

• 在LR(0)项目基础上增加一个终结符，所增加的终结符称为向前搜索符（lookahead），表示产生式右端完整匹配后所允许在剩余符号串中的下一个终结符。
• LR(1)项目形如：$[A→\alpha•\beta, a]$，其中，$A→\alpha•\beta$同LR(0)项目，$a$为向前搜索符，或为终结符，或为输入结束标志符$$$。
• 对于形如：$[A→\alpha•, a]$的LR(1)项目，对应LR(0)的归约项目，但只有当下一个输入符是$a$时才能进行归约。
• 对于其它形式的LR(1)项目，$a$只起到信息传承的作用。

LR(1)分析

求CLUSURE函数的时候要思考，求GOTO函数的时候直接照抄就可以了。

LR(1)分析表在构建的时候，只有遇到归约项目的时候才要考虑向前搜索符，其他和LR(0)一样。也就是，若项目$[A\rightarrow\alpha• \in k,a]$，且产生式$A\rightarrow\alpha$的编号为$j$，则对任何前向搜索符$a$（终结符和’$”），置 $\text{ACTION[k,a]}=r_j$，归约；

缺点

LR(1)分析表的状态数目庞大，可能存在项目集的冗余——合并, LALR(1)；LR(1)分析方法也不能解决所有冲突——LR(k), $k$ > 2。

LALR(1)分析

合并完之后可能有一个项目集有冲突的归约项目，不会有移进-规约冲突，因为合并前两个集合都有相同的移进项目，如果有冲突，应该在原始集合就有冲突

小结

主要区别：归约的判定方法

• LR(0)：不看下一个字符即可判定归约；
• SLR(1)：看下一个字符，但把所有$B \to \gamma \cdot$的向前搜索字符集均定义为Follow($B$)，即把符号栈顶上的句柄$\gamma$归约为$B$的条件是：向前搜索字符为Follow($B$)中的元素；
• LR(1)：也是看下一个字符，但归约不同位置上的$B$时，采用不同的向前搜索字符集，每个项由心与向前搜索符组成，搜索符长度为$1$；由于LR(1)方法对于归约条件的判定比SLR(1)更精确，可大大减少移入/归约冲突；
• LALR(1)：对LR(1)项目集规范族合并同心集，减少状态个数。

分析能力的区别：

• LR（0）分析表局限性大，但其构造方法是其他构造方法的基础；

• SLR（1）分析表虽然不是对所有文法都存在，但这种分析表较易实现又极有使用价值；

• LR（1）分析表的分析能力最强，能适用于一大类文法，但是，实现代价过高 （表过大）；
• LALR（1）分析表的能力介于SLR（1）和LR（1）之间，实现效率较高。

LR分析中的句柄是隐式存在的：句柄的识别是通过状态栈和符号栈的动态组合完成的，

二义性文法的LR分析

有两种方法：

1. 消除二义性后分析

2. 直接分析，但须添加额外的文法限制（如优先级或结合性等）

错误恢复

若能构造出没有冲突的LR分析表，则输入的句子中的所有错误都能被发现。（LR分析表中的空白位置）

各种LR分析发现错误的位置可能不一样，在发现错误前需要执行的归约次数：$LR(0)\geq SLR(1)\geq LALR(1)\geq LR(1)$。

空白处填错误处理程序的指针：

1. 检查LR分析表中的每个报错条目。
2. 根据语言的使用方法来决定程序员所犯的何种错误最有可能引起这个语法错误。
3. 构造出适当的恢复过程：给出具体的错误处理例程。
4. 在分析表的ACTION表中每个空条目中填写一个指向错误处理例程的指针。

语法制导翻译

语义分析

主要是类型相容检查，有以下几种：

• 各种条件表达式的类型是不是 boolean 型？
• 运算符的分量类型是否相容？
• 赋值语句的左右部的类型是否相容？
• 形参和实参的类型是否相容?
• 下标表达式的类型是否为所允许的类型？
• 函数说明中的函数类型和返回值的类型是否一致？

语义分析方法：

• 语法制导翻译方法
• 使用属性文法为工具来说明程序设计语言的语义

语法制导定义[Syntax-Directed Definition,SDD]是一个上下文无关文法和属性及语义规则的结合

语法制导定义

语法制导定义也称属性文法。

1. 上下文无关文法

2. 属性：对文法的每一个符号，引进相关属性，来代表与文法符号相关的信息，如类型、值、存储位置等；$X.a$表示文法符号$X$的属性$a$。

3. 语义规则：为文法的每一个产生式配备的计算属性的规则，称为语义规则；它所描述的工作可以包括属性计算、静态语义检查、符号表的操作、代码生成等，有时写成函数或过程段。

属性分类

分类：

• 综合属性[synthesized attribute]：
  • 从语法树的角度来看，如果一个结点的某一属性值是由该结点的子结点的属性值计算来的，则称该属性为综合属性。
  • 用于“自下而上”传递信息。
• 继承属性[inherited attribute]：
  • 从语法树的角度来看，若一个结点的某一属性值是由该结点的兄弟结点和（或）父结点的属性值计算来的，则称该属性为继承属性。
  • 用于“自上而下”传递信息。

终结符只有综合属性，它们由词法分析器提供。非终结符既有综合属性也有继承属性，但文法开始符没有继承属性。

SDD的求值顺序

依赖图

如果依赖图中有一条从结点$M$到结点$N$的边，那么要先对$M$对应的属性求值，再对$N$对应的属性求值。

• 可行的求值顺序就是满足下列条件的结点顺序$N_1,N_2,\ldots N_k$，如果有一条从结点$N_i$到$N_j$的依赖图的边，则$i < j$，这个排序称为这个图的拓扑排序。
• 若图中有环，则不存在拓扑排序。
• 有向无环图则至少存在一个拓扑排序。

抽象语法树

S-属性和L-属性

S-属性

一个仅包含综合属性的SDD称为S-属性的SDD，或称S-属性文法。

• 每个属性都必须是综合属性。
• 每个节点的属性值仅由其子节点的属性值计算而来（自底向上传递信息），可以保证求值顺序与LR分析的输出顺序相同。

翻译方案

在LR分析的过程中加一个语义栈，进出和符号栈与状态栈相同。

L-属性

一个SDD的产生式右部所关联的各个属性之间，依赖图的边总是从左到右，则称该SDD为L-属性的SDD。

L-属性的SDD中，每个属性：

• 要么是一个综合属性。
• 要么是一个继承属性，但有以下约束：假设存在产生式$A \to X_1X_2 \cdots X_n$，其$X_i$的继承属性$X_i.a$的计算规则只能依赖：
  • 产生式左部$A$的继承属性。
  • $X_i$左边的文法符号$X_1$、$X_2$、…、$X_{i - 1}$的继承属性或综合属性（即已经计算过的兄弟节点）。
  • $X_i$本身的属性，且由$X_i$的属性组成的依赖图中不存在环。

L-属性定义的目的是确保属性计算可以按从左到右的顺序进行

适用于：

• 递归下降、LL(1)等自顶向下分析方法
• LR(1)等自底向上的分析方法

翻译方案

翻译方案中的显式求值顺序。按照从左到右深度优先的顺序执行语义操作

语法制导翻译方案[Syntax - Directed Translation Schemes, SDT]：

• 产生式内部带有语义动作的SDT：语义动作可以放置在产生式右部的任何位置上[Actions inside productions]。若有产生式$B \to X\{a\}Y$：

  • 如果$X$是终结符，则识别到$X$后，动作$a$就会执行

• 如果$X$是非终结符，则识别到所有从$X$推导出的终结符后，动作$a$就会执行

• 如果语法分析是自底向上的，则在$X$出现在分析栈的栈顶时，动作$a$就会执行

• 如果语法分析是自顶向下的，则在推导展开$Y$（$Y$为非终结符）或者在输入中检测到$Y$（$Y$为终结符）之前，动作$a$就会执行

在预测分析中实现L-属性定义

1）为语法规则编写一个LL(1)语法

2）通过附加语义规则定义L-属性定义

3）将L-属性定义转换为翻译方案

4）消除翻译方案中的左递归（因为带有左递归的文法无法进行确定的自顶向下语法分析）

5）编写一个递归下降预测解析器（翻译器）

L-属性的SDD转换为SDT

把计算某个非终结符A的继承属性的动作插入到产生式体中紧靠在A的本次出现之前的位置上；如果A的多个继承属性以无环的方式相互依赖，就需要对这些属性的求值动作进行排序，以便先计算需要的属性。将计算一个产生式头的综合属性的动作放置在这个产生式体的最右端。

消除翻译方案中的左递归

因为带有左递归的文法无法进行确定的自顶向下语法分析，所以要消除翻译方案中的左递归。

编写一个递归下降预测解析器

在LR分析中实现L-属性定义

中间代码生成

概述

从中间代码生成开始真正做翻译工作，输入：语法树，输出：IR（Intermediate Representation，中间表示）

高级中间表示：AST和DAG

低级中间表示：3-地址码

中间表示

构造DAG的值编码方法

三地址码

三地址码中，一条指令右侧最多有一个运算符，即不允许出现组合的算术表达式。例如，像 x + y * z 这样的表达式，需要翻译成如下的三地址指令序列：

1. t1 = y * z
2. t2 = x + t1

三元式

1. 三元式（Triple）具有三个字段：op、arg1、arg2。
2. 它使用运算 x op y 的位置来表示其结果，而不是使用一个显式的临时名字。
3. 带括号的数字表示指向相应三元式结构的指针。

间接三元式

1. 改进的三元式表示方法包含三个字段：op、arg1、arg2。
2. 它包含一个指向三元式的指针列表，而不是直接列出三元式序列。
3. 这种方法可以解决由于指令改变引起的问题。

四元式

1. 扩展的三元式表示方法包含四个字段：op、arg1、arg2、result。
2. 特例包括：
   • 形如 x = minus y 的单目运算符指令和赋值指令 x = y，不使用 arg2。
   • 像 param 这样的运算既不使用 arg2，也不使用 result。
   • 条件或非条件转移指令将目标标号放入 result 字段。

类型和声明

类型表达式包括：

• 基本类型，如 boolean、char、integer、float、void 等
• 类名
• 类型构造算子 array，如 array(3, integer)
• 类型构造算子 record，如 record{float x; float y;}
• 类型构造算子 →，如 s→t 表示从类型 s 到类型 t 的函数
• 笛卡尔积 ×：具有左结合性，优先级高于 →
• 取值为类型表达式的变量

表达式和语句

中间代码生成

代码拼接

使用记号 gen(...) 来表示三地址指令：

• 例如，gen(x'='y'+'z) 表示三地址指令 $x = y + z$。

|| 作为代码拼接符号。

增量生成

类型检查

强类型：类型规则严格，不允许隐式的类型转换。

弱类型：类型规则宽松，允许隐式的类型转换

布尔表达式

有两种，一种是数值表示的直接计算，另一种是逻辑表示的短路计算

直接计算的翻译

每个a<b都可以被翻译成四个四元式，它们的跳转就按代码逻辑跳到下个判断的位置。然后就可以翻译出来了。

短路计算

按直接计算的方式翻译完之后，第一个跳转到false或者true的填写false或true。直接翻译，末尾的跳转式子跳到false或true的时候跳转到之前填写false的那个式子，其他不变。

代码优化

所谓优化是对代码进行等价变换，使得变换后的代码的效率更高（节省运行时间、存储空间或两者兼而有之）。

根据优化涉及的程序范围，分为：

• 局部优化［Local Optimization］：在只有一个入口、一个出口的基本块［basic block］上进行优化
• 循环优化［Loop Optimization］：
  • 对循环中的代码进行优化
  • 基于控制流分析
• 全局优化［Global Optimization］：
  • 在整个程序范围内进行的优化
  • 基于数据流分析

通用技术

删除公共子表达式：

常量折叠及复写传播：

消除死代码：

局部优化

基本块是指程序中一个顺序执行的语句序列，其中只有一个入口语句和一个出口语句。执行时只能从入口语句进入，从其出口语句退出。

基本块的划分

求基本块的入口语句，它们是：

• 程序的第1个语句；

• 条件转移或无条件转移语句的转移目标语句；

• 紧跟在条件转移语句后面的语句。

(1)是第一条语句

(8)、(3)是被跳转到的语句

(5)是紧跟在条件语句后面的语句

对每一入口语句，构造其所属的基本块

构造DAG

基本块的DAG是一种结点带有标记或附加信息的DAG：

• 叶子结点：标识符或常数，代表变量或常数的值

• 内部结点：运算符，代表用该运算符对其前驱结点所代表的值进行运算的结果

• 各结点都可以附加上一个或多个标识符，表示这些变量具有该结点所代表的
  值

循环优化

循环优化对提高目标代码的效率作用显著。

基于流图［Flow Graphs］进行：

• 把控制流的信息加到基本块集合上构成的有向图称表示程序的流图，简称流图。
• 流图的构造方法：
  • V 点集：以基本块为结点，含程序第一条语句的结点为首结点。
  • 边集：从基本块$B_{i}$向基本块$B_{j}$引有向边，仅当：
    • $B_{i}$在程序中的位置紧跟在$B_{j}$之后，且$B_{i}$的出口语句不是无条件转移语句或停止语句。或者
    • $B_{i}$的出口是转移语句 （goto（s）或if..goto （s）），并且转移目标（s）是$B_{j}$的入口语句。

优化技术

代码外提

把循环不变量提到循环的前面，使之只在循环外执行一次。

循环不变运算：其结果独立于循环执行次数的表达式；运算对象为常量或在循环外定值，每次循环时其值不变的量。

强度削弱

把程序中强度大的运算替换成强度小的运算。例如把乘法运算换成加法运算等。

变换循环控制条件

将循环控制条件更换为等价的另一个循环控制条件

变换后可以删减代码或减少执行次数

在流图中确定循环

要求：

• 强连通子图
• 具有唯一的入口
• 循环可以表示为一个结点序列

方法

回边，顾名思义，就是从$a$回到了到达它必经之路上的一个点$b$。

确定循环的算法：

1. 确定回边$a\rightarrow b$
2. 初始化$\text{loop}=[a,b],\text{stack}=[a]$
3. 将$\text{stack}$栈顶元素弹出，获得其的直接前驱节点$[c,d,….]$。将不在$\text{loop}$中的前驱节点压入$\text{loop}$和$\text{stack}$栈中。重复3直到$\text{stack}$为空。
4. $\text{loop}$中的元素即为一个循环

自然循环的性质

自然循环并不涵盖常识中的所有循环

• 例如，在下面的流图中不存在回边，但按照常识它确实有一个循环：{2, 3}。
• 只有在可归约流图中，回边才找到所有循环。

可归约流图[Reducible flow graph]:

• 移除所有回边 ，子图是无环的。

• 在可归约流图中，循环的唯一入口是头节点。

全局优化

全局优化作用于整个过程（函数），可以进行跨基本块的优化。

常用技术：

• 全局公共子表达式删除
• 常数折叠和传播
• 死代码删除
• 复写传播

何时需要全局信息？

• 局部优化
  • 如果变量从未被使用，则可以删除对该变量的赋值
• 循环优化：代码外提
  • 根据变量的定义，确定循环不变运算
  • 代码外提要求该运算是循环中唯一的定义
  • 代码外提还要求所定义的变量在循环出口处不是活跃的（not live）
• 循环优化：归纳变量消除
  • 如果归纳变量在循环外未被使用，则可以将其消除
• 代码生成
  • 出口处的活跃性信息有助于提高寄存器利用率

数据流分析

到达-定值 数据流分析[Reaching Definition Analysis]

• 前流：信息流的方向与控制流是一致的

• 变量 $A$ 的定值[definition]是对 $A$ 的赋值或读值到 $A$ 的语句，该语句的位置称作 $A$ 的定值点

• 变量 $A$ 的定值点 $d$ 到达某点 $p$，是指流图中从 $d$ 有一条路径到达 $p$ 且该通路上没有 $A$ 的其它定值

  • 当我们在 $p$ 之前立即使用变量 $A$ 时，$A$ 的值可以由 $d$ 决定

UD链

UD链是在该引用点（Use）处，用到的值可能是哪里定义的（Define）

填表

1. 刚开始的时候先写GEN、KILL，OUT=GEN
2. 每轮循环用两个公式更新IN和OUT列直到收敛

活跃变量

填表

1. 初始化：填Def和LiveUse
2. 每次迭代用两个公式更新LiveIn、LiveOut直到收敛。

DU链

UD链是该定值点（Define），会在哪里被使用（Use）

目标代码生成

基础概念

代码生成的任务：把中间代码（经过优化或未经过优化）作为输入，将其转换成特定 机器 的机器语言或 汇编 语言作为输出，这样的转换程序称为代码生成器 ( Code Generator)。

代码生成器主要关注：

1. 指令选择［Instruction selection］
   • 选择合适的目标机器指令来实现中间表示（IR）语句 。
2. 寄存器分配与指派［Register allocation and assignment］
   • 充分利用寄存器（最快的计算单元）。
3. 指令排序［Instruction ordering］
   • 决定指令执行的顺序。
   • 也称为指令调度［Instruction scheduling］。

指令选择

生成的代码的速度和大小成本都需要考虑：

寄存器分配与指派

高效利用寄存器资源，减少内存访问开销：

包含两个子问题：

1. 寄存器分配：选择在程序的每个点上哪些变量将驻留在寄存器中
2. 寄存器指派：为变量分配具体的寄存器

指令调度

通过重新排列指令顺序，最大化利用CPU流水线，減少因依赖关系导致的停顿（Bubble），提升指令级并行性（ILP）

目标机器的抽象

指令集

RISC［Reduced Instruction Set Computer，精简指令集计算机］架构支持以下指令：

• LD dst, addr 加载（从内存addr读取数据到目标寄存器dst）
• ST X, Ri 存储（将寄存器数据写入内存）
• OP dst, src1， src2 // 二元运算（如加、减等）
• OP dst, src1 一元运算
• BR L 无条件跳转（跳转到标签L）
• Bcond r, L 条件跳转（根据寄存器r的值决定是否跳转到标签L）

寻址模式

$a(R_{i})$ 。直接变址寻址，开销 = 1

• $a$为变量或常量
• 示例： $LD\ R_{1}, a(R_{2})$

含义：$R_{1} = contents(a + contents(R_{2}))$。$contents(x)$表示$x$所代表的寄存器或内存位置中存放的内容

示例：$LD\ R_{1}，100(R_{2})$。含义：寄存器$R_{2}$中的值加上$100$得到的和所指向的位置中的内容加载到$R_{1}$中

程序和指令的代价

一条指令的代价 = 1+操作数寻址代价

一个程序的代价= 所有指令代价的总和

第一条指令不需要寻址操作数，第二条指令要寻址操作数$x$，第三条指令要寻址100(R2)和*100(R2)，但是两次内存访问只记作1代价。

目标代码中的地址

静态分配

call callee：

• call 表示过程调用
• callee是被调用的过程 / 函数
• ST callee.staticArea, #here + 20
  • 将返回地址保存到callee的活动记录的开始处 callee.staticArea；
  • #here：当前指令的地址;
  • +20：假设调用序列需占用 20 字节
  • 用于保存返回地址

BR callee.codeArea：

• 跳转到被调用过程 callee的目标代码上

BR *callee.staticArea：

• 跳转到保存callee 的活动记录开始位置的地址上
• 相当于return

栈分配

代码生成器

基本概念

一个基于基本块的代码生成器

• 它的输入是四元式中间代码，输出是M机器的汇编代码
• 着重讨论在基本块内如何充分利用寄存器

总原则：

• 在指令的执行代价中，寄存器的代价是最小的，因此总是希望将尽可能多的运算对象放在寄存器中；
• 由于任何一个计算机模型中的寄存器个数都是有限的，因而需要根据一些原则，对寄存器进行分配。

基于基本块的寄存器分配的一般原则：

• 当生成某变量的目标代码时，尽量让变量的值或中间结果保留在寄存器中， 直到寄存器不够分配止，这样引用变量值时可减少对内存的存取次数，提高运行速度

• 进入基本块时所有寄存器是空闲的，当到基本块出口时，应将变量的有用值存回内存，释放所有寄存器

• 在基本块内，后面不再被引用的变量占用的寄存器应尽早释放，以提高寄存器的利用效率

待用信息链表

为了把在基本块内还要被引用的变量值尽可能保存在寄存器中，不再被引用的变量所占的寄存器尽早释放，在翻译四元式 i:A := B op C 时，必须知道变量 A，B，C 在基本块内其后的引用情况，即所谓变量的待用信息。

基本定义（回顾）

• 定值、引用、活跃：在形如 i:A := B + C 的代码中，出现在:= 左边和右边的变量，分别被称为对变量的定值和引用（对变量A定值，对变量B和 C引用），i 被称为变量的定值点或引用点。若变量的值在 i 之后的代码序列中被引用，则称变量在 i 点是活跃的。
• 待用信息：在基本块中，变量 A 在四元式 i 中被定值，在 i 后面的四元式 j 中引用 A 值，且从i到j之间没有其他对A的定值点，称 j 是i中对变量 A 的待用信息（下次引用信息）。所有这样的待用信息$j_k(k=1,2,\cdots)$构成待用信息链。

基本块内求待用信息的算法

① 处理符号表初始状态

把基本块中各变量在符号表登记项中的待用信息栏置“非待用”，活跃信息栏按变量在基本块出口是否活跃置“活跃”或“非活跃”（假定用户变量均为活跃，临时变量均为非活跃）。

② 逆序处理四元式（从出口向前）

从基本块出口的四元式开始，由后向前依次处理每个四元式 $i: A := B \ \text{Op} \ C$，直至处理完毕：

1. 处理变量 A
   • 把符号表中变量 (A) 的待用信息和活跃信息附加到四元式 (i) 上。
   • 将符号表中变量 (A) 的待用信息栏和活跃信息栏分别置为“非待用”和“非活跃”。
     （原因：在四元式 (i) 中对 (A) 的定值仅在 (i) 之后可能被引用，对 (i) 之前的四元式而言，(A) 既非活跃也非待用。）
2. 处理变量 B 和 C
   • 把符号表中变量 (B) 和 (C) 的待用信息和活跃信息附加到四元式 (i) 上。
   • 将符号表中变量 (B) 和 (C) 的待用信息栏置为i，活跃信息栏置为“活跃”。

注意：步骤 i、ii 的次序不可颠倒，因为 (B) 和 (C) 也可能是 (A)。

符号表中的待用信息栏和活跃信息栏中，(4)中写的是针对第三个式子的时候变量的待用信息和活跃信息。

四元式的待用信息栏和活跃信息栏中，序号4针对的是序号4之后的式子变量的待用信息和活跃信息。

代码生成算法

变量及函数

1. 寄存器描述数组RVALUE：

   • 为了掌握各寄存器的使用情况，用数组RVALUE记录每个寄存器的当前情况：

     • $RVALUE[R_i] = \{A\}$：表示$R_i$里的值是变量A的值，或说A独占$R_i$。
     • $RVALUE[R_i] = \{\}$：表示$R_i$是空闲的。
     • $RVALUE[R_i] = \{B, C\}$：表示$R_i$里的值是变量B和C的值，或说B、C共占$R_i$。

   • 在复写（B := C）时存在多个变量共占一个寄存器。

2. 变量地址描述数组 AVALUE：

   • 生成目标代码要用到变量的地址，它可能是某寄存器 $R_i$，也可能是内存单元（仍用变量名表示）。若变量值同时在寄存器 $R_i$ 和内存，则取 $R_i$ 为其地址。

     • $V_AVALUE[A] = \{R_i\}$：表示变量 A 的值在 $R_i$ 中，不在内存。

     • $V_AVALUE[B] = \{R_i, B\}$：表示变量 B 的值在 $R_i$ 中，又在内存。

     • $V_AVALUE[C] = \{C\}$：表示变量 C 的值只在内存。

3. 寄存器分配函数GETREG：

   • 以形如$i：A：=B\ op\ C$的四元式为输入，返回一个寄存器R，用以存放A的结果值，其算法为：

     1. 如果B独占$R_i$，且B与A是同一标识符或B值不再引用，则选$R_i$为R并转④。

     2. 否则，如果有空闲$R_i$，则选$R_i$为R并转④。

     3. 否则，释放一个$R_i$作为R，最好占用$R_i$（要被释放的寄存器）的变量值同时在内存中，或在基本块中引用的位置最远。对$R_i$中不是A的变量M，且其值不在内存，则做如下处理：

        • 生成目标代码ST Ri，M，把Ri的值存回变量M在内存的地址。

        • 修改变量地址描述：如M不是B则AVALUE[M] = {M}，否则AVALUE[M] = {Ri, M}。

        • 修改寄存器描述：删除RVALUE{Ri}中的M。

     4. 给出R，返回

通过$GETREG(i：A：=B\ op\ C)$返回的寄存器R用于进行B op C的运算，并把结果（A值）保存在R中。

算法流程

开始时所有寄存器都空闲，顺序取出四元式 $i: A := B \ \text{op} \ C$，按下述算法生成目标代码。

1. 分配寄存器 $R = \text{GETREG}(i: A := B \ \text{op} \ C)$；
2. 利用地址描述数组 $\text{AVALUE}[B]$ 和 $\text{AVALUE}[C]$，确定出 $B$ 和 $C$ 现行值的存放位置 $B’$ 和 $C’$，如果其现行值在寄存器中，则把寄存器取作 $B’$ 和 $C’$；
3. 如果 $B’ \neq R$，则生成目标代码 $\text{LD} \ R, B’$；$\text{op} \ R, C’$；否则生成 $\text{op} \ R, C’$。如果 $B’$ 或 $C’$ 为 $R$，则删除 $\text{AVALUE}[B]$ 或 $\text{AVALUE}[C]$ 中的 $R$。
4. $$\text{AVALUE}[A] = \{R\}, \ \text{RVALUE}[R] = \{A\}$$
5. 如果 $B$ 和 $C$ 的现行值是“非引用”和“非活跃”，且其值在某个 $R_p$ 中，则删除 $\text{RVALUE}[R_p]$ 中的 $B$ 或 $C$，删除 $\text{AVALUE}[B]$ 和 $\text{AVALUE}[C]$ 中的 $R_k$。

到达基本块出口时，若有活跃变量占用寄存器且其值不在内存，则生成存数指令 $\text{ST}$，保存其值并释放寄存器。