2 词法分析

词法单元，正则表达式书写，有穷自动机构造

标记Token

标记是一对 <标记名，属性值>

A = B * 2：
<id, pointer to symbol-table entry for A>

<id, pointer to symbol-table entry for B> <number, integer value 2>

• 词法分析器无法继续的情况：没有一个词块模式与剩余输入的任何前缀相匹配，Example: int 3a = a * 3

字符串相关术语

• 字母表（Alphabet）：任何有限的符号集合
■ 符号示例：字母、数字和标点符号
■ 字母示例：{1，0}，ASCII，Unicode
• 字母表上的字符串（串）是从字母表中抽取的符号的有限序列字符串 s 的长度（用 |s| 表示）是指有多少个
• 符号在 s 中的出现次数（即基数）
■ 空串（Empty string）：长度为 0 的字符串，ε

▪ 字符串 s 的前缀（前缀）：从 s 的末尾去掉 0 个或多个符号后得到的任何字符串
▪ 适当的前缀（真前缀）：不是空且不为整个字符串
▪ 后缀（Suffix）：从 s 开头去掉 0 个或更多符号后得到的字符串
▪ 正后缀（真后缀）：不是空且不为字符串本身

子串：从 s 中去掉任何前缀和后缀后得到的任何字符串
真子串：不为空且不等于字符串
子序列：从 s 中删除 0 个或多个不一定连续的符号后形成的字符串

正则表达式

定义

• ε是一个RE，L(ε) = {ε}

• 如果 a∈∑，则a是一个RE，L(a) = {a}

• 假设 r和 s都是 RE，表示的语言分别是 L(r)和L(s)，则

  • r|s 是一个RE，L( r|s ) = L(r)∪L(s)
  • rs是一个RE，L( rs ) = L(r) L(s)
  • r*是一个RE，L( r* )= (L(r))*
  • (r) 是一个RE，L( (r) ) = L(r)

运算的优先级：*、连接、|

根据规则，regexps 通常包含不必要的括号对。如果我们采用约定俗成的规则，就可以省去一些括号：
优先级：闭合* > 连接 > 联合 | |
关联性：所有三个运算符都是左关联运算，即从左侧开始分组运算，例如，
a | b | c 将被解释为 (a | b) | c
• 例如：(a) | ((b)*(c)) = a | b*c

举例说明：假设 Σ = {a, b}
a|b 表示语言 {a, b}
(a|b)(a|b) 表示 {aa, ab, ba, bb}
▪ a* 表示{空，, a, aa, aaa, …}。
▪ (a|b)* 表示由 0 个或多个 a 或 b 组成的所有字符串的集合：{空，a, b, aa, ab, ba, bb, aaa, …}。
▪ a|a* b 表示字符串 a 和所有由 0 个或多个 a 组成并以 b 结尾的字
符串：{a, b, ab, aab, aaab, …}。

RE的代数定律

正则定义

正则定义是具有如下形式的定义序列：
d1→r1
d2→r2
…
dn→rn

​ 其中：

• 每个di都是一个新符号，它们都不在字母表 Σ中，而且各不相同
• 每个ri是字母表 Σ∪{d1 ,d2 , … ,di-1}上的正则表达式

有穷自动机

FA的表示

• 转换图 (Transition Graph)
  • 结点：FA的状态
    • 初始状态（开始状态）：只有一个，由start箭头指向
    • 终止状态（接收状态）：可以有多个，用双圈表示
  • 带标记的有向边：如果对于输入a，存在一个从状态p到状 态q的转换，就在p、q之间画一条有向边，并标记上a

给定输入串x，如果存在一个对应于串x的从初始状态到某个终止状态的转换序列，则称串x被该FA接收

由一个有穷自动机M接收的所有串构成的集合称为是该FA定义（或接收）的语言，记为L(M)

上图的自动机：L(M) =所有以abb结尾的字母表{a, b}上的串的集合

最长子串匹配原则(Longest String Matching Principle)

当输入串的多个前缀与一个或多个模式匹配时，总是选择最长的前缀进行匹配

有穷自动机的分类

确定的FA (Deterministic finite automata, DFA)
非确定的FA (Nondeterministic finite automata, NFA)

DFA：确定的有穷自动机

M = ( S，Σ ，δ，s0，F )

S：有穷状态集
Σ：输入字母表，即输入符号集合。假设ε不是 Σ中的元素
δ：将S×Σ映射到S的转换函数。 ∀s∈S, a∈Σ, δ(s,a)表示从状态s出发，沿着标记为a的边所能到达的状态。
s0：开始状态 (或初始状态)，s0∈ S
F：接收状态（或终止状态）集合，F⊆ S

NFA：非确定的有穷自动机

M = ( S，Σ ，δ，s0，F )
S：有穷状态集
Σ：输入符号集合，即输入字母表。假设ε 不是Σ中的元素
δ：将S×Σ映射到2^S^的转换函数。∀s∈S, a∈Σ, δ(s,a)表示从状态s出发，沿着标记为a的边所能到达的状态集合
s0：开始状态 (或初始状态)，s0∈ S
F：接收状态（或终止状态）集合，F⊆ S

正则文法 ⇔ 正则表达式 ⇔ FA

带有“ε-边”的 NFA

M = ( S，Σ ，δ，s0，F )
S：有穷状态集
Σ：输入符号集合，即输入字母表。假设ε不是Σ中的元素
δ：将S×(Σ∪{ε})映射到2^S^的转换函数。∀s∈S, a∈Σ∪{ε}, δ(s,a)表示从状态s出发，沿着标记为a的边所能到达的状态集合
s0：开始状态 (或初始状态)，s0∈ S
F：接收状态（或终止状态）集合，F⊆ S

带有和不带有“ε-边”的 NFA 是等价的

从正则表达式到有穷自动机

根据RE构造NFA

汤普森构造法

从NFA到DFA——子集构造法

省流：合并相同状态，然后构建一个新的自动机

▪ 见解：构建的 DFA 的每个状态都对应一组 NFA 状态
• 在读取输入 a a12 …an 之后，DFA 所处的状态与 NFA 从起始状态按照标有 a a12 …a 的路径可以到达的状态集相对应。
▪ 算法 “并行 “模拟 NFA 在给定输入字符串上可能做出的所有动作

• DFA 状态 # 有可能是 NFA 状态 # 的指数级（最坏情况）每个 DFA 状态对应一个 NFA 状态子集
• 然而，对于真实语言来说，NFA 和 DFA 的状态数大致相同，不会出现指数行为。

• 算法中使用的运算：
▪ 𝜖-closure(s)：仅在𝜖-transitions 上可从 NFA 状态 s 到达的 NFA 状态集合
▪ 𝜖-closure(T)：仅在𝜖-transitions 上可从集合 T 中的某个 NFA 状态 s 到达的 NFA 状态的集合
move（T，a）：输入符号 a 可以从 T 中的某个状态 s 过渡到的 NFA 状态集合

Example：

A: 𝜖-closure(0) = {0, 1, 2, 4, 7}
B: Dtran[A, a] = 𝜖-closure({3, 8}) = {1, 2, 3, 4, 6, 7, 8}
C: Dtran[A, b] = 𝜖-closure({5}) = {1, 2, 4, 5, 6, 7}
D: Dtran[B, b] = 𝜖-closure({5, 9}) = {1, 2, 4, 5, 6, 7, 9}
…

有穷自动机的构造步骤

assignment2.pdf 2021211999_assignment2.pdf

**(a|b)a(a|b)(a|b)*

NFA

DFA

3 语法分析

自顶向下语法分析：构造语法分析树，构造FIRST和FOLLOW集合，进行LL(1)递归下降分析，设计预测分析程序

自底向上语法分析：LR(0)，SLR，LR(1)，LALR

推导和语法分析树

从开始符号开始，使用产生式重写非终结符，直到只剩下终结符为止

⇒ 意思是“一步到位”
⇒ ∗ 意思是“以零个或多个步骤推导” 𝛼 ⇒∗ 𝛼 适用于任何字符串𝛼
⇒ ‘’/ ⇒ + 意思是“以一个或多个步骤推导”

最左推导

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

最右推导就是从右边开始

术语
• 如果S⇒ ∗ α, 其中S是语法G的开始符号，我们说α是G文法的句型
· 文法的句型可以同时包含终结符号和非终结符号，并且可以为空
· 示例𝐸 ⇒ −𝐸 ⇒ −(𝐸)⇒ −(𝐸+𝐸) ⇒ −(𝐢𝐝+𝐸) ⇒ −(𝐢𝐝 + 𝐢𝐝) 这里所有的语法符号串都是文法的句型
• 一个G的句子是一个没有非终结符的文法句型
· 在上面的例子中，只有最后一个字符串−(𝐢𝐝 + 𝐢𝐝)是一个句子
•语法产生的语言是它的一组句子

语法分析树

语法分析树是一种推导的图形表示，它过滤掉了产生式应用的顺序
· 根结点是文法的开始符号
· 每个叶子结点由终结符或𝜖标记
· 每个内部结点由非终结符标记
· 每个内部结点代表产生式的应用
· 内部节点用产生式的头部中的非终结符进行标记；
· 子节点由产生式主体中的符号从左到右进行标记

构造示例：

如果一个语法为某个句子生成了多个语法分析树，则它具有二义性

语法设计

CFG与正则表达式比较

CFG比正则表达式更具表达能力
· 可以用正则表达式描述的每个构造都可以用语法描述，但反之不成立
· 每个正则语言都是上下文无关的语言，但反之不成立
示例：𝐿 ={𝑎𝑛𝑏𝑛 | 𝑛> 0}
语言L可以用CFG：𝑆 → 𝑎𝑆𝑏 | 𝑎𝑏 来描述
L不能用正则表达式来描述。换句话说，我们不能构造一个DFA来接受L

消除二义性

接近原则：用最接近的未匹配的then匹配else

消除左递归

如果语法中存在一个非终结符A，使得某个字符𝛼有相关的产生式𝐴 ⇒+ 𝐴𝛼 ，则该语法为左递归语法

消除左递归就是把他变成右递归

简单语法：𝐴 → 𝐴𝛼 | 𝛽 它生成以符号𝛽开头的句子，后面跟零个或更多的𝛼’s

将语法替换为：

𝐴 → 𝛽A’
A’ → 𝛼A’ | 𝜖

消除立即左递归

𝐴 → 𝐴𝛼1|…|𝐴𝛼𝑚|𝛽1|… | 𝛽𝑛

将语法替换为：

𝐴 →𝛽1A’ | … |𝛽nA’

A’ → 𝛼1A’ | … | 𝛼mA’ |𝜖1

提取左公因子

自顶向下语法分析树构建

FIRST集合和FOLLOW集合

FIRST集合

FIRST集合，能够在开头出现的终结符构成的集合，如S->aA|bA FIRST(S)={a,b}

令G是一个不含左递归的文法，对G的所有非终结符的每个候选α定义它的终结首符集FIRST($\alpha$)为：
𝐹𝐼𝑅𝑆𝑇(𝛼)={𝑎│𝛼⇒∗ 𝑎…, 𝑎∈$𝑉_𝑇$ }
特别是，若𝛼⇒∗ 𝜀，则规定𝜀∈𝐹𝐼𝑅𝑆𝑇(𝛼)。

FOLLOW集合

FOLLOW集合，能够跟在非终结符后面的终结符构成的集合，即把终结符换成𝜀后后面还能出现终结符，如S->…Aa|…Ab|𝜀 FOLLOW(A)={a,b}

假定S是文法G的开始符号，对于G的任何非终结符A，我们定义A的FOLLOW集合
𝐹𝑂𝐿𝐿𝑂𝑊(𝐴)={𝑎│𝑆⇒∗…𝐴𝑎…, 𝑎∈$𝑉_𝑇$ }
特别是，若𝑆⇒∗…𝐴，则规定#∈𝐹𝑂𝐿𝐿𝑂𝑊(𝐴)

LL(1)文法

1. 文法不含左递归
2. 对于文法中每一个非终结符A的各个产生式的候选首符集两两不相交。即，若

$$
\begin{align}\mathbf{A}{\stackrel{}{\to}}\alpha_{1}|\alpha_{2}|\ldots|\alpha_{n}\end{align}
$$

则 $FIRST(α_i)∩FIRST(α_j)=φ (i≠j)$

3. 对文法中的每个非终结符A，若它存在某个候选首符集包含𝜀，则$FIRST(A)∩FOLLOW(A)=φ$，i=1,2,…,n

如果一个文法G满足以上条件，则称该文法G为LL(1)文法。

PPT上的定义：

​ 语法𝑮 是LL(1)当且仅当对于任意两个不同的产生式𝐴 → 𝛼 | 𝛽, 以下条件成立：

​ 1.不存在终结符𝑎 使得𝛼 和𝛽 都可以推导以𝑎开头的字符串

​ 2.𝛼 和𝛽 中最多只有一个可以推导空字符串

​ 3.如果𝛽 ⇒* 𝜖, 那么𝛼 不能推导出任何以FOLLOW(𝐴)中某个终结符开头的字符串，反之亦然

FIRST集合的构造

构造每个文法符号的FIRST集合

对每一X∈$V_T$∪$V_N$，连续使用下面的规则，直至每个集合FIRST不再增大为止：

1. （终结符）若X∈$V_T$，则FIRST(X)＝{X}。
2. （终结符开头）若X∈$V_N$，且有产生式X→a…，则把a加入到FIRST(X)中；若X→𝜀也是一条产生式，则把𝜀也加到FIRST(X)中。
3. （非终结符开头）

• 若X→Y…是一个产生式且Y∈$V_N$，则把FIRST(Y)中的所有非𝜀-元素都加到FIRST(X)中；

• 若X→$Y_1Y_2…Y_{i-1}Y_i…Y_k$是一个产生式，$Y_1，…，Y_{i-1}$都是非终结符，

  • 对于任何j，1≤j≤i-1，FIRST($Y_j$)都含有𝜀(即$Y_1…Y_{i-1}$⇒∗𝜀)， 则把FIRST($Y_i$)中的所有非𝜀-元素都加到FIRST(X)中（也就是说，如果有一个非终结符前面的非终结符的FIRST集合不含𝜀，那么后面的非终结符不需要再验证加入FIRST集合了，如T->FT’，F不含𝜀，则T’不需要看了）
  • 若所有的FIRST($Y_j$)均含有𝜀（或者𝜀本身就是一个产生式），j＝1，2，…，k，则把𝜀加到FIRST(X)中。

示例：FIRST集合的构造示例 2:05

FOLLOW集合的构造

构造每个非终结符的的FOLLOW集合

对于文法G的每个非终结符A构造FOLLOW(A)的办法是，连续使用下面的规则，直至每个FOLLOW不再增大为止（注意一个产生式可以对应多种模式）：

1. 对于文法的开始符号S，置$于FOLLOW(S)中；
2. (FIRST($\beta$)的可以FOLLOW(B))若A→$\alpha B\beta$是一个产生式，则把FIRST($\beta$)\{𝜀}加至FOLLOW(B)中；
3. (FOLLOW(A)的可以FOLLOW(B))若A→$\alpha$B是一个产生式，或A→$\alpha B\beta$是一个产生式而($\beta$⇒∗𝜀 (即𝜀∈FIRST($\beta$)，最右边的FIRST有𝜀的还FOLLOW(A)可以FOLLOW(中间))，则把FOLLOW(A)加至FOLLOW(B)中

示例：FOLLOW集合的构造示例 10:14

LL(1)分析法

假设要用非终结符A进行匹配，面临的输入符号为a，A的所有产生式为$\begin{align}\mathbf{A}{\stackrel{}{\to}}\alpha_{1}|\alpha_{2}|\ldots|\alpha_{n}\end{align}$

1. 若a∈FIRST($α_i$)，则指派$α_i$执行匹配任务；
2. 若a不属于任何一个候选首符集，则：
   (1) 若𝜀属于某个FIRST($α_i$)且 a∈FOLLOW(A)， 则让A与𝜀自动匹配。
   (2) 否则，a的出现是一种语法错误。

递归下降分析器

分析程序由一组子程序组成， 对每一语法单位(非终结符)构造一个相应的子程序，识别对应的语法单位
通过子程序间的相互调用实现对输入串的识别，例如，A → B c D
文法的定义通常是递归的，通常具有递归结构

定义全局过程和变量

• ADVANCE，把输入串指示器IP指向下一个输入符号，即读入一个单词符号
• SYM，IP当前所指的输入符号
• ERROR，出错处理子程序

A→TE’ | BC | 𝜀 对应的递归下降子程序为

1
2
3
4
5
6
7
8
9

PROCEDURE  A；
BEGIN
	IF  SYM ∈ FIRST(TE’) THEN
           BEGIN  T；E' END
	ELSE IF  SYM ∈ FIRST(BC) THEN
		     BEGIN  B; C  END
    ELSE IF  SYM ∉ FOLLOW(A) THEN
        ERROR
END；

E’→+TE’ | 𝜀 简化的形式

1
2
3
4
5
6

PROCEDURE  E'；
IF SYM=‘+’ THEN
BEGIN	
	ADVANCE；
          T；E'	
END

扩充的巴克斯范式

在元符号“→”或“::=”和“|”的基础上，扩充几个元语言符号：
用花括号{α}表示闭包运算α*。
用表示$\begin{align}{\alpha}{0}^{n}\end{align}$可任意重复0次至n次。
用方括号[α]表示$\begin{align}{\alpha}{0}^{1}\end{align}$，即表示α的出现可有可无(等价于α|𝜀)。

预测分析

预测分析程序构成

总控程序，根据现行栈顶符号和当前输入符号，执行动作
分析表 M[A，a]矩阵，A ∈ VN ，a ∈ VT 是终结符或‘$’
分析栈 STACK 用于存放文法符号

预测分析过程

总控程序根据当前栈顶符号X和输入符号a，执行下列三动作之一：

1. 若X＝a＝‘$’，则宣布分析成功，停止分析。
2. 若X＝a ≠‘$’，则把X从STACK栈顶逐出，让a指向下一个输入符号。
3. 若X是一个非终结符，则查看分析表M。
   若M[X，a]中存放着关于X的一个产生式，把X逐出STACK栈顶，把产生式的右部符号串按反序一一推进STACK栈(若右部符号为𝜀，则意味不推什么东西进栈)。
   若M[X，a]中存放着“出错标志”，则调用出错诊察程序ERROR。

总控程序实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

  BEGIN
   首先把‘＃’然后把文法开始符号推进STACK栈；
   把第一个输入符号读进a；
   FLAG:=TRUE;
   WHILE  FLAG  DO
	BEGIN
       把STACK栈顶符号上托出去并放在X中；
       IF X∈VT THEN
	        IF X= a  THEN 把下一输入符号读进a
	                       ELSE   ERROR
       ELSE IF X=‘#’ THEN
	         IF X=a THEN FLAG:=FALSE 
                         ELSE ERROR
       ELSE IF M[X,a]={X→X1X2…Xk}THEN
         	把Xk,Xk-1,…,X1一一推进STACK栈
	        /* 若X1X2…Xk=𝜀，不推什么进栈 */
       ELSE ERROR
    END OF WHILE;
STOP /*分析成功，过程完毕*/
END

分析示例：[[9.1.3]–预测分析示例](https://www.bilibili.com/video/BV1dJ411D7w6?p=82&vd_source=c75b11f1c6d9b809759edcc17586cf0d )

分析表构造算法

构造G的分析表M[A，a]， 确定每个产生式A→$\alpha$在表中的位置

1. 对文法G的每个产生式A→$\alpha$执行第2步和第3步；
2. 对每个终结符a ∈FIRST($\alpha$)，把A→$\alpha$加至M[A，a]中；
3. 若𝜀∈FIRST($\alpha$)，则对任何b∈FOLLOW(A)把A→$\alpha$加至M[A，b]中。（如T->TE’如果T的FIRST集合中没有𝜀，则不需要继续考虑E’）
4. 把所有无定义的M[A，a]标上“出错标志”。

构造示例：[9.2.2]–构造预测分析表示例

自下而上（自底向上）分析的基本思想

采用“移进－归约”思想进行自下而上分析

基本思想

用一个寄存符号的先进后出栈，把输入符号一个一个地移进到栈里，当栈顶形成某个产生式的候选式时，即把栈顶的这一部分替换成(归约为)该产生式的左部符号。

短语

定义：令G是一个文法，S是文法的开始符号，假定$\alpha\beta\delta$是文法G的一个句型，如果有
S⇒∗αAδ 且 “A” ⇒+β
则β称是句型$\alpha\beta\delta$相对于非终结符A的短语。
如果有A⇒β,则称β是句型$\alpha\beta\delta$相对于规则A→β的直接短语。

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

算符文法

一个文法，如果它的任一产生式的右部都不含两个相继(并列)的非终结符，即不含…QR…形式的产生式右部，则我们称该文法为算符文法。

约定：
a、b代表任意终结符
P、Q、R代表任意非终结符
‘…’代表由终结符和非终结符组成的任意序列，包括空字

句柄

一个句型的最左直接短语称为该句型的句柄

最左两代子树末端就是句柄

规范规约

定义：假定$\alpha$是文法G的一个句子，我们称序列 $\alpha_n$， $\alpha_{n-1}$，… ，$\alpha_0$ 是$\alpha$的一个规范归约，如果此序列满足：
1. $\alpha_n$= $\alpha$
2. $\alpha_0$为文法的开始符号，即$\alpha_0$=S
3. 对任何i，0 ≤ i ≤ n， $\alpha_{i-1}$是从$\alpha_i$经把句柄替换成为相应产生式左部符号而得到的

LR分析器

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

LR分析表

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

LR分析过程

​ ($s_0 s_1 … s_m $, #$X_1 … X_m$ ，$a_ia_{i+1} … a_n$#)

分析器根据ACTION$(s_m , a_i)$确定下一步动作

1. 若ACTION(sm , ai)为移进，且s为下一状态，则格局变为:
   ($s_0 s_1 … s_ms $, #$X_1 … X_ma_i$ ，$a_ia_{i+1} … a_n$#)
2. 若ACTION$(s_m , a_i)$为按A->$\beta$归约，格局变为:
   ($s_0 s_1 … s_ms $, #$X_1 … X_mA$ ，$a_ia_{i+1} … a_n$#)
   此处, s=GOTO($s_{m-r}$, A), r为$\beta$的长度, $\beta$= $X_{m-r+1}… X_m$
3. 若ACTION$(s_m , a_i)$为“接受”，则格局变化过程终止，宣布分析成功。
4. 若ACTION$(s_m , a_i)$为“报错”，则格局变化过程终止，报告错误。

分析示例：[11.2.3]–LR文法

LR文法

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

LR文法不是二义的，二义文法肯定不会是LR的
LR文法⊂无二义文法

增广文法

如果G 是一个以S为开始符号的文法，则G的增广文法 G’ 就 是在G中加上新开始符号S’ 和产生式S’ → S而得到的文法

引入这个新的开始产生式的目的是使得文法开始符号仅出现 在一个产生式的左边，从而使得分析器只有一个接受状态

LR语法分析器的优势

LR语法分析器的优势
· 表驱动（类似于非递归LL语法分析器）、强大
· 尽管手工构建LR语法分析器工作量太大，但也有一些语法分析器生成器可以自动构建语法分析表
· 相比之下，LL语法分析器往往更容易手工编写，但功能较弱（处理的语法较少）
· LR语法分析技术是已知的最通用的非回溯移入-归约语法分析方法
· LR语法分析器可以被构造为识别几乎所有可以为其编写CFG的编程语言结构
· LR语法比LL语法可以描述更多的语言

LR(0)分析表构造算法

这里不需要看那么多形式化定义，只要会构造就行

CLOSURE( )函数

项集闭包

如果𝐼 是文法𝐺的一组项集, 那么CLOSURE(𝐼)就是按照下面两条规则构造的项集：

  1. 一开始，将𝐼中的各个项加入到CLOSURE(𝐼)
  2. 如果𝐴 → 𝛼 · 𝐵𝛽在CLOSURE(𝐼)中，𝐵 → 𝛾是一个产生式，并且𝐵 → ·𝛾不在CLOSURE(𝐼)中，那么将𝐵 → ·𝛾加入CLOSURE(𝐼)中。不断应用这条规则，直到没有新项可以加入到
     直观地讲：𝐴 → 𝛼 · 𝐵𝛽 表示我们希望看到从一个能够从𝐵𝛽推导得到的子串。这个子串的某个前缀可以从B推导得到。因此，我们将所有𝐵-产生式加入到项集。

计算给定项目集I的闭包

$$
\begin{align}\mathrm{CLOSURE}(I)=I\cup{B\to\cdot,\gamma\mid A\to\alpha\cdot B\beta\in\mathrm{CLOSURE}(I),,B\to\gamma\in P}\end{align}
$$

1
2
3
4
5
6
7
8
9
10

SetOfltems CLOSURE ( I ) {
		J = I；
		repeat
			for ( J中的每个项A → α·Bβ ) 
				for ( G的每个产生式B → γ ) 
					if ( 项B → · γ不在J中 ) 
						将B → · γ加入J中；
		until 在某一轮中没有新的项被加入到J中；
		return J；
}

GOTO ( )函数

𝐆𝐎𝐓𝐎(𝑰, 𝑿) 其中𝑰是一个项集而𝑿是一个文法符号，被定义为𝑰中所有形如的项所对应的项的集合的闭包。

返回项目集I对应于文法符号X的后继项目集闭包
$$
\begin{align}\mathrm(I,X){=C L O S U R E({A\to\alpha X·\beta{\mid}{A\to\alpha\cdot X\beta{\in}I}}})\end{align}
$$

1
2
3
4
5
6

SetOfltems GOTO ( I，X ) {
	将J 初始化为空集；
	for ( I 中的每个项A → α·Xβ ) 
		将项 A → αX·β 加入到集合J 中；
	return CLOSURE ( J )；
}

构造LR(0)自动机的状态集

规范LR(0) 项集族(Canonical LR(0) Collection)
$$
\begin{align}C={I_{0}}\cup{I|\exists J\in C,X\in V_{N}\cup V_{T},I=G O T O(J,X);}\end{align}
$$

1
2
3
4
5
6
7
8
9

void items( G' ) {
	C＝{ CLOSURE ({[ S'→ ·S ] } ) }；
	repeat
	for (C中的每个项集 I )
		for(每个文法符号X )
			if ( GOTO ( I，X )非空且不在C中)
				将GOTO ( I，X )加入C中；
	until在某一轮中没有新的项集被加入到C中；
}

LR(0)分析表构造算法

移进-规约冲突

归约-归约冲突

SLR分析

如果集合${a_1, a_2, …, a_m}$和FOLLOW(B1)， FOLLOW(B2)，…，FOLLOW(Bn)两两不相交，则项目集I中的冲突可以按以下原则解决：

​ 设a是下一个输入符号：

• 若a∈${a_1, a_2, …, a_m}$，则移进a
• 若a∈FOLLOW($B_i$)，则用产生式$B_i→γ_i$ 归约
• 此外，报错

SLR分析表构造算法

LR(1)分析

将一般形式为 [A→α·β, a]的项称为 LR(1) 项，其中A→αβ 是 一个产生式，a 是一个终结符(这里将$视为一个特殊的终结符) 它表示在当前状态下，A后面必须紧跟的终结符，称为该项的展望符(lookahead)

• LR(1) 中的1指的是项的第二个分量的长度
• 在形如[A→α·β, a]且β ≠ ε的项中，展望符a没有任何作用
• 但是一个形如[A→α·, a]的项在只有在下一个输入符号等于a时才可以按照A→α 进行归约
  • 这样的a的集合总是FOLLOW(A)的子集，而且它通常是一个真子集

LR(1)分析表构造算法

LALR分析法

• 寻找具有相同核心的LR (1) 项集，并将这些项集合并为一个项集。 所谓项集的核心就是其第一分量的集合

• 然后根据合并后得到的项集族构造语法分析表

• 如果分析表中没有语法分析动作冲突，给定的文法就称为LALR (1) 文法，就可以根据该分析表进行语法分析

合并同心项集时产生归约-归约冲突

合并同心项集后，虽然不产生冲突，但可能会推迟错误的发现

LALR(1)的特点

• 形式上与LR(1)相同
• 大小上与LR(0)/SLR相当
• 分析能力介于SLR和LR(1)二者之间 SLR<LALR(1)<LR(1)
• 合并后的展望符集合仍为FOLLOW集的子集

LR语法分析器对比

•The languages (grammars) that can be handled

CLR > LALR > SLR

•# states in the parsing table

CLR > LALR = SLR

•Driver programs

SLR = CLR = LALR

错误恢复？

4 语法制导翻译

语法制导定义SDD

语法制导定义SDD是对CFG的推广
将每个文法符号和一个语义属性集合相关联
将每个产生式和一组语义规则相关联，用来计算该产生式中各文法符号的属性值
文法符号的属性
综合属性 (synthesized attribute)
继承属性 (inherited attribute)

注释解析树

语法树与解析树
在语法树中，内部节点代表编程结构，而在解析树中，内部节点代表非终结符。
解析树也称为具体语法树，其底层语法称为语言的具体语法

9-5+2的注释解析树

综合属性

在分析树结点 N上的非终结符A的综合属性只能通过 N的子结点或 N本身的属性值来定义

例：val是E的综合属性

终结符可以具有综合属性。终结符的综合属性值是由词法分析器提供的词法值，因此在SDD中没有计算终结符属性值的语义规则

继承属性

在分析树结点N上的非终结符A的继承属性只能通过N的父结点、N的兄弟结点或N本身的属性值来定义

例：in是L的继承属性

终结符没有继承属性。终结符从词法分析器处获得的属性值被归为综合属性值

属性文法

一个没有副作用的SDD有时也称为属性文法
属性文法的规则仅仅通过其它属性值和常量来定义一个属性值
例

SDD的求值顺序

SDD为CFG中的文法符号设置语义属性。对于给定的输入串x，应用语义规则计算分析树中各结点对应的属性值

语义规则建立了属性之间的依赖关系，在对语法分析树节点的一个属性求值之前，必须首先求出这个属性值所依赖的所有属性值

依赖图

依赖图是一个描述了分析树中结点属性间依赖关系的有向图
分析树中每个标号为X的结点的每个属性a都对应着依赖图中的一个结点
如果属性X.a的值依赖于属性Y.b的值，则依赖图中有一条从Y.b的结点指向X.a的结点的有向边

属性值的计算顺序

5-3 SSD的求值顺序_哔哩哔哩_bilibili

可行的求值顺序是满足下列条件的结点序列N1, N2, … , Nk ：如果依赖图中有一条从结点Ni到 Nj 的边(Ni→Nj), 那么i < j（即：在节点序列中，Ni 排在Nj 前面）
这样的排序将一个有向图变成了一个线性排序，这个排序称为这个图的拓扑排序(topological sort)

对于只具有综合属性的SDD ，可以按照任何自底向上的顺序计算它们的值
对于同时具有继承属性和综合属性的SDD，不能保证存在一个顺序来对各个节点上的属性进行求值

S-属性定义

仅仅使用综合属性的SDD称为S属性的SDD，或S-属性定义、S-SDD

如果一个SDD是S属性的，可以按照语法分析树节点的任何自底向上顺序来计算它的各个属性值
S-属性定义可以在自底向上的语法分析过程中实现

L-属性定义

L-属性定义(也称为L属性的SDD或L-SDD)的直观含义：在一个产生式所关联的各属性之间，依赖图的边可以从左到右，但不能从右到左(因此称为L属性的，L是Left的首字母)

L-SDD的正式定义

一个SDD是L-属性定义，当且仅当它的每个属性要么是一个综合属性，要么是满足如下条件的继承属性：假设存在一个产生式$A→X_1X_2…X_n$，其右部符号$X_i$ (1≤ i ≤ n)的继承属性仅依赖于下列属性：

• A的继承属性
• 产生式中$X_i$左边的符号 $X_1, X_2, … , X_{i-1}$ 的属性
• $X_i$本身的属性，但$X_i$的全部属性不能在依赖图中形成环路

每个S-属性定义都是L-属性定义

语法制导翻译方案SDT

语法制导翻译方案(SDT)是在产生式右部中嵌入了程序片段(称为语义动作)的CFG

SDT可以看作是SDD的具体实施方案
本节主要关注如何使用SDT来实现两类重要的SDD，因为在这两种情况下，SDT可在语法分析过程中实现
基本文法可以使用LR分析技术，且SDD是S属性的
基本文法可以使用LL分析技术，且SDD是L属性的

底层语法是LR，而SDD是S属性的：
LR语法：这是一种可以用自底向上的方式进行解析的语法。LR解析器从左到右读取输入，但决策是基于右侧的上下文进行的。它使用一个堆栈来存储已经读取的符号，并在适当的时候进行规约。
S属性的SDD：这意味着所有属性都是合成属性，它们只从子节点传递给父节点，没有从父节点传递给子节点的继承属性。这对于自底向上的LR解析是非常合适的，因为我们从叶子节点开始构建并向上移动，因此只需要合成属性即可。

底层语法是LL，而SDD是L属性的：
LL语法：这是一种可以用自顶向下的方式进行解析的语法。LL解析器从左到右读取输入，并基于左侧的上下文来进行决策。它通常使用递归下降的方法，直接从起始符号开始，并尝试应用各种产生式。
L属性的SDD：这种SDD除了合成属性外，还包括继承属性，但这些继承属性只能依赖于它左边的兄弟节点或其父节点的属性。由于LL解析是自顶向下的，所以可以在解析过程中计算这些继承属性。

SDD和SDT

SDD（Syntax Directed Definition）：

1. SDD定义了与语法产生式关联的属性和规则。它为每个语法产生式指定一个或多个属性计算或语义动作。
2. SDD关注于如何为语法树中的节点计算属性值，但不一定涉及产生中间代码或目标代码的具体操作。
3. 它可以有合成属性和继承属性，因此可以描述为S属性的（只有合成属性）或L属性的（允许继承属性但有限制）。

SDT（Syntax Directed Translation）：

1. SDT是SDD的一个特例，它专门用于生成中间代码或目标代码。换句话说，SDT的目的是翻译，它定义了与语法产生式关联的动作，这些动作通常在解析时执行。
2. 当解析器在处理产生式时，与该产生式关联的SDT动作被执行，从而生成代码或进行其他翻译工作。
3. 动作可以嵌入到产生式中，例如，在YACC或Bison这样的工具中，可以直接在语法规则中插入C代码作为动作。

总结差异：
SDD更为通用，关注于为语法树的节点计算属性。这些属性可以用于多种目的，如类型检查、变量绑定等。
SDT特化于翻译任务，即将源代码转换为中间代码或目标代码。它通常涉及在解析过程中执行特定的动作。
尽管有这些区别，但在实际应用中，SDD和SDT的界限可能会模糊，因为编译器的语义分析和翻译阶段通常是交织在一起的

将S-SDD转换为SDT

将一个S-SDD转换为SDT的方法：将每个语义动作都放在产生式的最后

S-属性定义的SDT实现——归约发生时执行语义动作

如果一个S-SDD的基本文法可以使用LR分析技术，那么它的SDT可以在LR语法分析过程中实现

当归约发生时执行相应的语义动作

扩展的LR语法分析栈

在分析栈中使用一个附加的域来存放综合属性值

若支持多个属性：
使栈记录变得足够大
在栈记录中存放指针

将语义动作中的抽象定义式改写成具体可执行的栈操作

示例：5-5语法制导翻译方案_哔哩哔哩_bilibili

在非递归的预测分析过程中进行翻译

扩展语法分析栈

例：5-6在非递归的预测分析过程中进行翻译_哔哩哔哩_bilibili

分析栈中的每一个记录都对应着一段执行代码

综合记录出栈时，要将综合属性值复制给后面特定的语义动作
变量展开时（即变量本身的记录出栈时），如果其含有继承属性，则要将继承属性值复制给后面特定的语义动作

在递归的预测分析过程中进行翻译

• 为每个非终结符A构造一个函数，A的每个继承属性对应该函数的一个形参，函数的返回值是A的综合属性值。对出现在A产生式中的每个文法符号的每个属性都设置一个局部变量

• 非终结符A的代码根据当前的输入决定使用哪个产生式

• 与每个产生式有关的代码执行如下动作：从左到右考虑产生式右部的词法单元、非终结符及语义动作

  • 对于带有综合属性x的词法单元 X，把x的值保存在局部变量X.x中；然后产生一个匹配 X的调用，并继续输入
  • 对于非终结符B，产生一个右部带有函数调用的赋值语句c := B(b1 , b2 , …, bk)，其中， b1 , b2 , …, bk是代表B的继承属性的变量，c是代表B的综合属性的变量
  • 对于每个动作，将其代码复制到语法分析器，并把对属性的引用改为对相应变量的引用

L-属性定义的自底向上翻译

给定一个以LL文法为基础的L-SDD，可以修改这个文法，并在LR语法分析过程中计算这个新文法之上的SDD

例：5-8L属性定义的自底向上翻译_哔哩哔哩_bilibili

将语义动作改写为可执行的栈操作

1. T→F M T′ {stack[top-2]. val = stack[top].syn; top = top-2;}
   M→ ε {stack[top+1]. T′inh = stack[top].val; top = top+1;}
2. T′→*F N T1′ {stack[top-3]. syn = stack[top].syn; top = top-3;}
   N → ε {stack[top+1]. T′inh = stack[top-2]. T΄inh × stack[top].val; top = top+1;}
3. T′→ε{stack[top+1].syn = stack[top]. T′inh; top = top+1;}
4. F →digit {stack[top].val = stack[top]. lexval;}

给定一个以LL文法为基础的L-属性定义，可以修改这个文法，并在LR语法分析过程中计算这个新文法之上的SDD

• 首先构造SDT，在各个非终结符之前放置语义动作来计算它的继承属性， 并在产生式后端放置语义动作计算综合属性
• 对每个内嵌的语义动作，向文法中引入一个标记非终结符来替换它。每个这样的位置都有一个不同的标记，并且对于任意一个标记M都有一个产生式M→ε
• 如果标记非终结符M在某个产生式A→α{a}β中替换了语义动作a，对a进行修改得到a’ ，并且将a’关联到M→ε 上。动作a’
  • (a) 将动作a需要的A或α中符号的任何属性作为M的继承属性进行复制
  • (b) 按照a中的方法计算各个属性，但是将计算得到的这些属性作为M的综合属性

5 中间代码生成

生成各种语句的中间代码（三地址代码）

中间代码表示

抽象语法树和有向无环图

a:=b*(-c)+b*(-c)的图表示法

DAG 可以用构造语法树的 SDD 来构造
区别：在构建 DAG 时，只有当且仅当没有现存的相同节点时，才会创建新节点

三地址代码

在三地址代码中，指令右侧最多只有一个运算符
指令的形式通常是 𝑥 = 𝑦 𝑜𝑝 𝑧

运算符（或地址）可以是：
源程序中的名称
常量：编译器必须处理多种类型的常量
编译器生成的临时名称

赋值指令：
𝑥 = 𝑦 op 𝑧，其中 op 是二进制算术/逻辑运算
𝑥 = op 𝑦，其中 op 是一元运算
复制(赋值)指令： 𝑥 = 𝑦
无条件跳转指令：goto 𝐿，其中 𝐿 是跳转目标的标记
有条件跳转指令：
if 𝑥 goto 𝐿
if Flase 𝑥 goto 𝐿
if 𝑥 relop 𝑦 goto 𝐿
程序调用和返回：
param 𝑥1
…
param 𝑥𝑛
call 𝑝, 𝑛 (procedure call)
y = call p, n (function call)
return y
索引赋值指令： 𝑥 = 𝑦[𝑖] 𝑥[𝑖] = 𝑦 这里，𝑦[𝑖] 表示位置 𝑖 存储单元中超出位置 𝑦 的值。这里，𝑦[𝑖] 表示位置 𝑖存储元中超出位置 𝑦 的值。
地址和指针赋值指令：𝑥 = &𝑦 ，𝑥 =∗ 𝑦， ∗ 𝑥 = 𝑦

例：
Source code: do i = i + 1; while (a[i] < v);

四元式

一个四元式（或 “四元组”）有四个字段
一般形式： op arg1 arg2 result
op 包含运算符的内部代码
arg1、arg2、result 是地址（操作数）

一元运算符（如 x = 减 y 或 x = y）不使用 arg2
参数运算符既不使用 arg2 也不使用 result
条件/非条件跳转将目标标签放在 result 中

例：
Assignment statement: 𝑎 = 𝑏 ∗ −𝑐 + 𝑏 ∗ −𝑐

三元组

三元组只有三个字段：op, arg1, arg2。
我们用操作 x op y 的位置来表示操作结果，而无需生成临时名称（这是对四元组的优化）

在优化编译器中，指令经常被移动
四地址表达式的优势：使用 t1 和 t3 的指令不受影响

间接三元式

间接三元组由一个指向三元组的指针列表（下面的指令数组）

优化可以通过重新排序指令列表来移动指令（无需修改三元组）
交换后，列表中的第一条和第二条指令仍然指向正确的指令

类型表达式

基本类型是类型表达式
可以为类型表达式命名，类型名也是类型表达式
将类型构造符(type constructor)作用于类型表达式可以构成新的类型表达式

• 数组构造符array
• 指针构造符pointer
• 笛卡尔乘积构造符×
• 函数构造符→
• 记录构造符record

如果 𝑠和 𝑡是类型表达式，那么它们的笛卡尔乘积 𝑠 × 𝑡 就是一个类型表达式（例如，表示函数参数等类型的元组）。

声明语句的翻译

变量声明语句的SDT

非终端 𝐷生成声明序列
𝑇 生成基本类型、数组类型或记录类型，记录类型是记录字段的声明序列，由大括号包围
𝐵 生成基本类型之一：int 和 float
𝐶 生成一个或多个整数的序列，每个整数都由大括号包围

对于声明语句，语义分析的主要任务就是收集标识符的类型等属性信息，并为每一个名字分配一个相对地址
从类型表达式可以知道该类型在运行时刻所需的存储单元数量称为类型的宽度(width)
在编译时刻，可以使用类型的宽度为每一个名字分配一个相对地址
名字的类型和相对地址信息保存在相应的符号表记录中

① P →{ offset = 0 } D
② D → T id;{ enter( id.lexeme, T.type, offset );
offset = offset + T.width; }D
③ D → ε
④ T → B { t =B.type; w=B.width;}
C { T.type = C.type; T.width = C.width; }
⑤ T → ↑T1{ T.type = pointer( T1.type); T.width = 4; }
⑥ B → int { B.type = int; B.width = 4; }
⑦ B → real{ B.type = real; B.width = 8; }
⑧ C → ε { C.type=t; C.width=w; }
⑨ C → [num]C1 { C.type = array( num.val, C1.type);
C.width = num.val * C1.width; }

例：6-2声明语句的翻译_哔哩哔哩_bilibili

在LL语法分析过程中，将语法动作当作节点{a}，分析到{a}时执行相应的语义动作

简单赋值语句的翻译

赋值语句翻译的任务

赋值语句的基本文法

① S → id = E；
② E → E1 + E2
③ E → E1 * E2
④ E → —E1
⑤ E → (E1)
⑥ E → id

赋值语句生成三地址代码的S-属性文法

赋值语句翻译的主要任务
生成对表达式求值的三地址码

例
源程序片段：
x = ( a + b ) * c ;
三地址码：
t1 = a + b
t2 = t1 * c
x = t2

增量翻译 (Incremental Translation)

例：6-3简单赋值语句的翻译_哔哩哔哩_bilibili

语义动作都在产生式末尾的，在LR分析过程中进行语义动作翻译

数组引用的翻译

数组元素寻址 (Addressing Array Elements )

赋值语句的基本文法
S → id = E; | L = E;
E → E1 + E2 | —E1 | (E1) | id | L
L → id [E] | L1 [E]

将数组引用翻译成三地址码时要解决的主要问题是确定数组元素的存放地址，也就是数组元素的寻址

例：6-4数组引用的翻译_哔哩哔哩_bilibili

布尔表达式SDT

[18.3.3]–根据属性文法翻译布尔表达式_哔哩哔哩_bilibili

文法

E → E or E | E and E | not E | (E) | i rop i | i

产生布尔表达式三地址代码的属性文法

示例：[18.3.6]–布尔表达式的翻译示例_哔哩哔哩_bilibili

控制流语句

[19.2.1]–if语句的属性文法_哔哩哔哩_bilibili

[19.2.2]–while语句的属性文法_哔哩哔哩_bilibili

[19.3.1]–控制语句的属性计算示例_哔哩哔哩_bilibili

常用的控制语句

S → if E then S1

S → if E then S1 else S2

S → while E do S1

其中E为布尔表达式

S → if E then S1

S→if E then S1 else S2

S→while E do S1

6 运行时刻环境

运行存储分配概述

运行存储分配策略

编译器在工作过程中，必须为源程序中出现的一些数据对象分配运行时的存储空间
对于那些在编译时刻就可以确定大小的数据对象，可以在编译时刻就为它们分配存储空间，这样的分配策略称为静态存储分配
反之，如果不能在编译时完全确定数据对象的大小，就要采用动态存储分配的策略。即在编译时仅产生各种必要的信息，而在运行时刻，再动态地分配数据对象的存储空间

栈式存储分配
堆式存储分配

静态和动态分别对应编译时刻和运行时刻

活动记录

使用过程(或函数、方法)作为用户自定义动作的单元的语言，其编译器通常以过程为单位分配存储空间
过程体的每次执行称为该过程的一个活动(activation)
过程每执行一次，就为它分配一块连续存储区，用来管理过程一次执行所需的信息，这块连续存储区称为活动记录( activation record )

活动记录的一般形式

栈式存储分配

有些语言使用过程、函数或方法作为用户自定义动作的单元，几乎所有针对这些语言的编译器都把它们的(至少一部分的)运行时刻存储以栈的形式进行管理，称为栈式存储分配
当一个过程被调用时，该过程的活动记录被压入栈；当过程结束时，该活动记录被弹出栈
这种安排不仅允许活跃时段不交叠的多个过程调用之间共享空间，而且允许以如下方式为一个过程编译代码：它的非局部变量的相对地址总是固定的，和过程调用序列无关

活动树

用来描述程序运行期间控制进入和离开各个活动的情况的树称为活动树
树中的每个结点对应于一个活动。根结点是启动程序执行的main过程的活动
在表示过程p的某个活动的结点上，其子结点对应于被p的这次活动调用的各个过程的活动。按照这些活动被调用的顺序，自左向右地显示它们。一个子结点必须在其右兄弟结点的活动开始之前结束

设计活动记录的一些原则

在调用者和被调用者之间传递的值一般被放在被调用者的活动记录的开始位置，这样它们可以尽可能地靠近调用者的活动记录
固定长度的项被放置在中间位置
控制连、访问链、机器状态字
在早期不知道大小的项被放置在活动记录的尾部
栈顶指针寄存器top_sp指向活动记录中局部数据开始的位置，以该位置作为基地址

调用序列和返回序列

过程调用和过程返回都需要执行一些代码来管理活动记录栈，保存或恢复机器状态等
调用序列
实现过程调用的代码段。为一个活动记录在栈中分配空间，并在此记录的字段中填写信息
返回序列
恢复机器状态，使得调用过程能够在调用结束之后继续执行
一个调用代码序列中的代码通常被分割到调用过程（调用者）和被调用过程（被调用者）中。返回序列也是如此

调用者计算实际参数的值
调用者将返回地址（程序计数器的值）放到被调用者的机器状态字段中。将原来的top-sp值放到被调用者的控制链中。然后，增加top-sp的值，使其指向被调用者局部数据开始的位置
被调用者保存寄存器值和其它状态信息
被调用者初始化其局部数据并开始执行
被调用者将返回值放到与参数相邻的位置
使用机器状态字段中的信息，被调用者恢复top-sp和其它寄存器，然后跳转到由调用者放在机器状态字段中的返回地址
尽管top-sp已经被减小，但调用者仍然知道返回值相对于当前top-sp值的位置。因此，调用者可以使用那个返回值

堆式存储分配

堆式存储分配是把连续存储区域分成块，当活动记录或其它对象需要时就分配
块的释放可以按任意次序进行，所以经过一段时间后，对可能包含交错的正在使用和已经释放的区域

这章接下来看课本（

7 代码生成

代码生成器的主要任务

指令选择

选择适当的目标机指令来实现中间表示(IR)语句
例：
三地址语句：x = y + z
目标代码
LD R0，y /* 把y的值加载到寄存器R0中 */
ADD R0，R0 ，z /* z加到R0上 */
ST x ，R0 /* 把R0的值保存到x中 */

寄存器分配和指派

把哪个值放在哪个寄存器中

指令排序

按照什么顺序来安排指令的执行

一个简单的目标机模型

三地址机器模型

​ 加载、保存、运算、跳转等操作
​ 内存按字节寻址
​ n个通用寄存器R0, R1, …, Rn-1
​ 假设所有的运算分量都是整数
​ 指令之间可能有一个标号

目标机器主要指令

加载指令 LD dst, addr
LD r, x
LD r1, r2
保存指令 ST x, r
运算指令 OP dst, src1, src2
无条件跳转指令 BR L
条件跳转指令 Bcond r, L
例: BLTZ r, L

寻址模式

变量名a
a的内存地址
例：LD R1 , a
R1 = contents ( a )

a(r)
取 a 的 地址 值并将寄存器 R 中的值添加到该值中
a是一个变量，r是一个寄存器
例：LD R1 , a(R2)
R1 = contents ( a + contents(R2) )

c(r)
c是一个整数
例：LD R1 , 100 (R2)
R1 = contents (contents(R2) + 100 )

*r
在寄存器r的内容所表示的位置上存放的内存位置
例：LD R1 , * R2
R1 = conents (contents (contents (R2) ) )

*c(r)
在寄存器r中内容加上c后所表示的位置上存放的内存位置
例：LD R1 , *100(R2)
R1 = conents (contents (contents(R2) + 100 ) )

#c
立即寻址模式
例：LD R1 , #100
R1 = 100

x = y - z

𝑏 = 𝑎[𝑖]

𝑎[𝑗] = 𝑐

𝑥 =∗ 𝑝

∗ 𝑝 = 𝑦

if 𝑥 < 𝑦 goto L

M是标号为L的三地址指令所产生的目标代码中的第一个指令的标号

过程调用和返回的目标代码

静态存储分配

三地址语句
call callee
目标代码
ST callee.staticArea, #here + 20 （callee的活动记录在静态区中的起始位置）
BR callee.codeArea （callee的目标代码在代码区中的起始位置）

三地址语句
return
目标代码
BR *callee.staticArea

栈式存储分配

三地址语句
call callee
目标代码
ADD SP, SP, #caller.recordsize
ST 0(SP), #here + 16
BR callee.codeArea

三地址语句
return
目标代码
被调用过程
BR *0(SP)
调用过程
SUB SP, SP, #caller.recordsize

基本块和流图

基本块

基本块是满足下列条件的最大的连续三地址指令序列
控制流只能从基本块的第一个指令进入该块。也就是说，没有跳转到基本块中间或末尾指令的转移指令
除了基本块的最后一个指令，控制流在离开基本块之前不会跳转或者停机

基本块划分算法

输入： 三地址指令序列
输出： 输入序列对应的基本块列表，其中每个指令恰好被分配给一个基本块

方法：
首先，确定指令序列中哪些指令是首指令(leaders)，即某个基本块的第一个指令

1. 指令序列的第一个三地址指令是一个首指令
2. 任意一个条件或无条件转移指令的目标指令是一个首指令
3. 紧跟在一个条件或无条件转移指令之后的指令是一个首指令

然后，每个首指令对应的基本块包括了从它自己开始，直到下一个首指令(不含)或者指令序列结尾之间的所有指令

流图(Flow Graphs)

流图的结点是一些基本块
从基本块B到基本块C之间有一条边当且仅当基本块C的第一个指令可能紧跟在B的最后一条指令之后执行
此时称B是C的前驱(predecessor) ，C是B的后继(successor)
有两种方式可以确认这样的边：
有一个从B的结尾跳转到C的开头的条件或无条件跳转语句
按照原来的三地址语句序列中的顺序，C紧跟在之B后，且B的结尾不存在无条件跳转语句

基本块的DAG（有向无环图）表示

例
a = b + c
b = a - d
c = b + c
d = a - d
基本块中的每个语句s都对应一个内部结点N

• 结点N的标号是s中的运算符；同时还有一个定值变量表被关联到N ，表示s是在此基本块内最晚对表中变量进行定值的语句
• N的子结点是基本块中在s之前、最后一个对s所使用的运算分量进行定值的语句对应的结点。如果s的某个运算分量在基本块内没有在s之前被定值，则这个运算分量对应的子结点就是代表该运算分量初始值的叶结点(为区别起见，叶节点的定值变量表中的变量加上下脚标0)
• 在为语句x=y+z构造结点N的时候，如果x已经在某结点M的定值变量表中，则从M的定值变量表中删除变量x

DAG的构造

从一个DAG上删除所有没有附加活跃变量（活跃变量是指其值可能会在以后被使用的变量）的根结点(即没有父结点的结点) 。重复应用这样的处理过程就可以从DAG中消除所有对应于无用代码的结点
例
a = b + c
b = b - d
c = c + d
e = b + c

寄存器的选择

三地址语句的目标代码生成

对每个形如x = y op z的三地址指令I，执行如下动作
调用函数getreg( I )来为x、y、z选择寄存器，把这些寄存器称为Rx、Ry、Rz
如果 Ry中存放的不是 y ，则生成指令LD Ry, y′。y′是存放y的内存位置之一
类似的，如果 Rz中存放的不是z，生成指令LD Rz, z
生成目标指令OP Rx, Ry, Rz

寄存器描述符和地址描述符

寄存器描述符 ( register descriptor )
记录每个寄存器当前存放的是哪些变量的值
地址描述符 ( address descriptor )
记录运行时每个名字的当前值存放在哪个或哪些位置
该位置可能是寄存器、栈单元、内存地址或者是它们的某个集合
这些信息可以存放在该变量名对应的符号表条目中

基本块的收尾处理

对于一个在基本块的出口处可能活跃的变量x , 如果它的地址描述符表明它的值没有存放在x的内存位置上, 则生成指令ST x, R ( R是在基本块结尾处存放 x值的寄存器 )

管理寄存器和地址描述符

当代码生成算法生成加载、保存和其他指令时，它必须同时更新寄存器和地址描述符
对于指令LD R, x
修改 R的寄存器描述符，使之只包含x
修改x的地址描述符，把 R 作为新增位置加入到x的位置集合中
从任何不同于x的地址描述符中删除 R

当代码生成算法生成加载、保存和其他指令时，它必须同时更新寄存器和地址描述符
对于指令LD R, x
对于指令OP Rx, Ry, Rz
修改 Rx的寄存器描述符，使之只包含 x
从任何不同于Rx的寄存器描述符中删除 x
修改x的地址描述符，使之只包含位置 Rx
从任何不同于x的地址描述符中删除 Rx

当代码生成算法生成加载、保存和其他指令时，它必须同时更新寄存器和地址描述符
对于指令LD R, x
对于指令OP Rx, Ry, Rz
对于指令ST x, R
修改x的地址描述符，使之包含自己的内存位置

当代码生成算法生成加载、保存和其他指令时，它必须同时更新寄存器和地址描述符
对于指令LD R, x
对于指令OP Rx, Ry, Rz
对于指令ST x, R
对于复制语句x=y，如果需要生成加载指令LD Ry, y′ 则
修改 Ry的寄存器描述符，使之只包含 y
修改 y的地址描述符，把Ry作为新增位置加入到 y的位置集合中
从任何不同于y的变量的地址描述符中删除Ry
修改 Ry的寄存器描述符，使之也包含x
修改 x的地址描述符，使之只包含 Ry

示例：9-4寄存器的选择_哔哩哔哩_bilibili

1
2
3
4
5

t = a - b
u = a - c
v = t + u
a = d
d = v + u

寄存器选择函数getReg的设计

寄存器选择函数getReg

计算R的“费用”

寄存器Rx的选择

选择方法与Ry类似，区别之处在于：

• 因为x的一个新值正在被计算，因此只存放了x的值的寄存器对Rx来说总是可接受的，即使 x就是 y或 z之一(因为我们的机器指令允许一个指令中的两个寄存器相同)
• 如果 y在指令I之后不再使用，且(在必要时加载 y之后) Ry仅仅保存了y的值，那么， Ry同时也可以用作Rx 。对z和Rz也有类似选择

当I是复制指令x=y时，选择好Ry后，令Rx =Ry

窥孔优化

窥孔(peephole)是程序上的一个小的滑动窗口
窥孔优化是指在优化的时候，检查目标指令的一个滑动窗口(即窥孔) ，并且只要有可能就在窥孔内用更快或更短的指令来替换窗口中的指令序列
也可以在中间代码生成之后直接应用窥孔优化来提高中间表示形式的质量

冗余指令删除

消除冗余的加载和保存指令

消除不可达代码

一个紧跟在无条件跳转之后的不带标号的指令可以被删除

控制流优化

在代码中出现跳转到跳转指令的指令时，某些条件下可以使用一个跳转指令来代替

代数优化

代数恒等式
消除窥孔中类似于x=x+0或x=x*1的运算指令

强度削弱
对于乘数(除数)是2的幂的定点数乘法(除法) ，用移位运算实现代价比较低
除数为常量的浮点数除法可以通过乘数为该常量倒数的乘法来求近似值

特殊指令的使用

充分利用目标系统的某些高效的特殊指令来提高代码效率
例如：INC指令可以用来替代加1的操作

Chapter 8

看课本吧整不完了