Hexo
0%

编译原理

Posted on Edited on

存疑

z=x+1;的中间代码生成

移植问题(已解决)

image-20220419121711994

虚属性？

中间代码生成，修改

image-20220514151221654

习题8.4 是否存在和这些规则一致的求值过程

9.1

9 10

12.2

13.3

14.6

15.4 15.5

重点

消除左递归

递归下降语法分析器

非递归下降语法分析器

句柄

判断是否为LL文法

LR文法的四种判断

1
关系：LR(0)<SLR(1)<LALR(1)<LR(1)

1.判断LR(0)文法：
看项目中是否有归约-归约和移进-归约冲突。
如果无冲突则是LR(0)文法（如果是LR(0)文法则四种都是）；如果有冲突则不是LR(0)文法。（就要向下判断）

2.判断SLR(1)文法：
a:DFA中存在冲突项目（归约-归约，归约-移进）
b:{a1,a2,…,an},FOLLOW(B1),FOLLOW(B2)两两互不相交，（交集=空集）时是SLR(1)项目。
【也就是说，同时满足两个条件才是SLR（1）文法】

若不是再向下判断。

3.判断LR(1)文法：
构造带向前搜索符的DFA，无归约-归约冲突则是LR(1)文法。

【此处意思是如果有向前搜索符还有冲突的话就不是LR（1）文法，就要再向下判断】

4.判断LALR(1)文法：
合并同心集后无（归约-归约）冲突（在之前的基础上）
（核相同，向前搜索符不同）

（B->a,a
B->a,a|b
同心集）
LR(0)项目集规范族的构造和分析的构造

1
https://blog.csdn.net/m0_37154839/article/details/80316089

设计SDD

改写SDT

四元式序列

1
https://blog.csdn.net/abc123lzf/article/details/103753507

中间代码生成

image-20220518170348404

image-20220518170539086

image-20220518170614471

赋值语句的翻译

1
2
3
newtemp( )：生成一个新的临时变量t，返回t的地址
gen(code)：生成三地址指令code
lookup(name)：查询符号表返回name 对应的记录

数组引用的翻译

1
2
3
4
L的综合属性
L.type：L生成的数组元素的类型
L.offset：指示一个临时变量，该临时变量用于累加公式中的ij × wj项，从而计算数组元素的偏移量
L.array：数组名在符号表的入口地址

控制语句的翻译

1
2
3
4
继承属性
B.true：是一个地址，该地址用来存放当B为真时控制流转向的指令的标号
B.false：是一个地址，该地址用来存放当B为假时控制流转向的指令的标号
S.next：是一个地址，该地址用来存放紧跟在S代码之后执行的指令(S的后继指令)的标号

回填

非终结符B的综合属性

1
2
B.truelist：指向一个包含跳转指令的列表，这些指令最终获得的目标标号就是当B为真时控制流应该转向的指令的标号
B.falselist：指向一个包含跳转指令的列表，这些指令最终获得的目标标号就是当B为假时控制流应该转向的指令的标号

函数

1
2
3
4
5
6
makelist( i )
创建一个只包含i的列表，i是跳转指令的标号，函数返回指向新创建的列表的指针
merge( p1, p2 )
将 p1 和 p2 指向的列表进行合并，返回指向合并后的列表的指针
backpatch( p, i )
将 i 作为目标标号插入到 p所指列表中的各指令中
1
nextquad：即将生成的下一条指令的标号

image-20220517011523873

什么是编译

编译：将高级语言翻译成汇编语言或机器语言的过程。

image-20220104110715843

预处理器：把存储在不同文件中的源程序聚合在一起；把被称为宏的缩写语句转换为原始语句。

可重定位：在内存中存放的起始位置L不是固定的

加载器：修改可重定位地址；将修改后的指令和数据放到内存中适当的位置。

链接器：将多个可重定位的机器代码文件连接到一起；解决外部内存地址问题

编译系统的结构

image-20220104113047587

词法分析概述

词法分析的主要任务：

1
2
从左向右逐行扫描源程序的字符，识别出各个单词，确定单词的类型。将识别出的单词转换成统一的机内表示——词法单元(token)形式。
token:<种别码，属性值>

image-20220105104115216

语法分析概述

语法分析器从词法分析器输出的token序列中识别出各类短语，并构造语法分析树。

语义分析概述

主要任务：

任务一：收集标识符的属性信息

1
2
3
4
5
6
7
：
种属:简单变量、复合变量(数组，记录)、过程
类型:整型、实型、字符型、布尔型、指针型
存储类型，长度
值
作用域
参数和返回值信息

符号表：用来存放标识符的属性信息的数据结构

image-20220106095418057

任务二：语义检查

1
2
3
4
变量或过程未经声明就使用；
变量或过程名重复声明；
运算分量类型不匹配；
操作符与操作数之间的类型不匹配

中间代码生成及编译器后端

常用的中间表示形式：

三地址码；语法结构树/语法树

三地址码

三地址码由类似于汇编语言的指令序列组成，每个指令最多有三个操作数。

image-20220106095933969

三地址指令的表示

1
2
3
四元式(op,arg1,arg2,result)
三元式(op,arg1,arg2)
间接三元式

目标代码生成以源程序的中间表示形式作为输入，并把它映射到目标语言；目标代码生成的一个重要任务是为程序中使用的变量合理分配寄存器。

代码优化：为改进代码，所进行的等价程序变换，使其运行得更快一些，占用空间更小一些。

编译程序的生成

编译器的T形图

image-20220419112048151

自展

image-20220419112803975

移植

image-20220419112828085

语言及其文法

基本概念

字母表

1
一个有穷符号集合。

字母表运算

1
2
3
4
乘积
n次幂
正闭包（正数次幂的并集）
克林闭包(正闭包的基础上加个空串)

串：字母表中符号的一个有穷序列

串的运算

1
2
连接，空串是连接运算的单位元
串的幂运算

文法的定义

文法

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

$V_T$:终结符集合

1
终结符是文法所定义的语言的基本符号，有事也称为token

$V_N$：非终结符集合

1
非终结符是用来表示语法成分的符号，有时也称为"语法变量"

$V_T$与$V_N$不相交，二者相并统称为文法符号集。

P：产生式集合

1
描述了将终结符和非终结符组合成串的方法

S:开始符号

1
开始符号表示的是该文法中最大的语法成分

image-20220107105320903

符号约定

终结符

image-20220107110153976

非终结符

image-20220107110227112

注

image-20220107110401057

语言的定义

符号串$a0$经过n步推导出$a_n$,可简记为$a_0\Longrightarrow {}^{n}a_n $

image-20220108100026833

句子是不包含非终结符的句型。

文法的分类

Chomsky文法分类体系

0型文法

$\alpha \longrightarrow \beta $

无限制文法，其中$\alpha$中至少包含一个非终结符。

由0型文法G生成的语言称为 0型语言

1型文法

$\alpha \longrightarrow \beta $

上下文有关文法，CSG

产生式的一般形式:

2型文法

$\alpha \longrightarrow \beta $

上下文无关文法，CFG

其中$\alpha\in V_N$

产生式的一般形式：

3型文法

$\alpha \longrightarrow \beta $

正则文法，RG

右线性文法：$A\longrightarrow wB或A\longrightarrow w$

左线性文法：$A\longrightarrow Bw或A\longrightarrow w$

image-20220429171644864

CFG的分析树

给定一个句型，其分析树中的每一棵子树的边缘称为该句型的一个短语。

直接短语：高度为2的子树的边缘。

1
2
直接短语一定是某产生式的右部
但产生式的右部不一定是给定句型的直接短语

二义性文法

1
如果一个文法可以为某个句子生成多颗分析树，则称这个文法是二义性的。

image-20220109105001704

词法分析

正则表达式

image-20220109105354813

正则定义

image-20220111100400281

有穷自动机

image-20220111101353306

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

有穷自动机的分类

DFA确定的有穷自动机

image-20220112104246612

NFA非确定的有穷自动机

image-20220112104402251

正则文法与正则表达式与有穷自动机等价

image-20220112104637911

带有空边的NFA与不带空边的NFA有等价性

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

先构造NFA,再从NFA到DFA。

根据RE构造NFA

image-20220501150009650

假设正则表达式r1和r2对应的NFA分别为N(r1)和N(r2)

image-20220501150031625

从NFA到DFA的转换

image-20220114100302890

image-20220114100719876

识别单词的DFA

词法分析阶段可检测错误的类型：

1
2
单词拼写错误
非法字符

错误恢复策略

1
2
最简单的错误恢复策略：恐慌模式
从剩余的输入中不断删除字符，直到词法分析器能够在剩余的开头发现一个正确的字符为止。

语法分析

自顶向下分析概述

从分析树的顶部向底部方向构造分析树。

1
最左推导：总是选择每个句型的最左非终结符进行替换。
1
最右推导：总是选择每个句型的最右非终结符进行替换。

在自底向上的分析中，总是采用最左规约的方式，因此把最左规约称为规范规约，而最右推导相应的称为规范推导。

自顶向下选择最左推导。

自顶向下分析存在的问题

同一非终结符的多个候选式存在共同前缀，将导致回溯现象

image-20220512192055179

左递归文法会使递归下降分析器陷入无限循环

image-20220512192124252

消除直接左递归

image-20220512192544030

消除直接左递归的一般形式

image-20220512192836269

消除间接左递归

image-20220512192935922

提取左公因子

image-20220512193513607

image-20220512193523610

预测分析

需要回溯的分析器叫不确定分析器。

1
2
预测分析：递归下降分析技术的一个特例，通过在输入中向前看固定个数符号来选择正确的A-产生式。
预测分析不需要回溯，是一种确定的自顶向下分析方法。

可以对某些文法构造出向前看k个输入符号的预测分析器，该类文法有时也称为LL(k) 文法类

预测分析法

LL(1)文法

S_文法

1
2
3
每个产生式的右部都以终结符开始
同一非终结符的各个候选式的首终结符都不同
S_文法不含ε产生式

什么时候使用ε产生式

1
如果当前某非终结符A与当前输入符a不匹配时，若存在A→ε，可以通过检查a是否可以出现在 A的后面，来决定是否使用产生式 A→ε（若文法中无 A→ε ，则应报错）

后继符号集

1
2
3
可能在某个句型中紧跟在A后边的终结符a的集合，记为FOLLOW(A)
	FOLLOW(A)={a| S ->* αAaβ, a∈VT，α,β∈(VT∪VN)*}
如果 A是某个句型的的最右符号，则将结束符“$”添加到FOLLOW(A)中

产生式的可选集

1
2
3
产生式A→β的可选集是指可以选用该产生式进行推导时对应的输入符号的集合，记为SELECT( A→β )
SELECT( A→aβ ) = { a }
SELECT( A→ε )=FOLLOW( A )

image-20220512212721662

q_文法

1
2
3
每个产生式的右部或为ε ，或以终结符开始
具有相同左部的产生式有不相交的可选集
q_文法不含右部以非终结符打头的产生式

串首终结符集

1
给定一个文法符号串α， α的串首终结符集FIRST(α)被定义为可以从α推导出的所有串首终结符构成的集合。如果α * ε，那么ε也在FIRST(α)中

LL(1)文法

1
2
3
4
5
当且仅当G的任意两个具有相同左部的产生式A → α | β 满足下面的条件：
不存在终结符a使得α 和β都能够推导出以a开头的串
α 和β至多有一个能推导出ε 
如果 β ->* ε，则FIRST (α)∩FOLLOW(A) =Φ；
如果 α ->* ε，则FIRST (β)∩FOLLOW(A) =Φ；

即同一非终结符的各个产生式的可选集互不相交

第一个L表示从左向右扫描输入，第二个L表示最左推导

follow(A)计算方法

image-20220512220412044

预测分析表

image-20220512220850395

预测分析

1
2
递归的方式：基于预测分析表对递归下降分析法进行扩展
非递归的方式：显式地维护一个栈结构来模拟最左推导过程

递归的预测分析法

非递归的预测分析法

非递归的预测分析显式地维护一个栈结构，而不是通过递归调用的方式隐式地维护栈。这样的语法分析器可以模拟最左推导过程

image-20220512221720701

image-20220512221741289

预测分析步骤

1
2
3
4
5
6
1.构造文法
2.改造文法：消除二义性、消除左递归、消除回溯
3.求每个变量的FIRST集和FOLLOW集，从而求得每个候选式的SELECT集
4.检查是不是 LL(1) 文法。若是，构造预测分析表
5.对于递归的预测分析，根据预测分析表为每一个非终结符编写一个过程；对于非递归的预测分析，实现表驱动
  的预测分析算法

二义性判定

1
对于任一个上下文无关文法，不存在一个算法判断其是否为二义性，但能给出一个充分条件，满足则无二义性，不满足也未必有二义性

预测分析中的错误检测

两种情况下可以检测到错误

1
2
栈顶的终结符和当前输入符号不匹配
栈顶非终结符与当前输入符号在预测分析表对应项中的信息为空

错误恢复

1
恐慌模式：忽略输入中的一些符号，直到输入中出现由设计者选定的同步词法单元(synchronizing token)集合中的某个词法单元；如果终结符在栈顶而不能匹配，一个简单的办法就是弹出此终结符

自底向上的分析

自底向上的语法分析采用最左归约方式（反向构造句子的最右推导）

移入-归约分析

工作过程

image-20220513095056700

四种动作

1
2
3
4
移入：将下一个输入符号移到栈的顶端
归约：被归约的符号串的右端必然处于栈顶。语法分析器在栈中确定这个串的左端，并决定用哪个非终结符来替换这个串
接收：宣布语法分析过程成功完成
报错：发现一个语法错误，并调用错误恢复子例程

存在问题

1
2
归约-归约冲突
移入-归约冲突

归约-归约冲突

造成错误的原因：错误地识别了句柄

句柄：句型的最左直接短语

image-20220513100212940

移入-归约冲突

image-20220513100150507

LR分析法

是最大的、可以构造出相应移入-归约语法分析器的文法类
L: 对输入进行从左到右的扫描
R: 反向构造出一个最右推导序列

LR(k)分析
需要向前查看k个输入符号的LR分析

image-20220513102223085

image-20220513102611274

看PPT例题分析

LR(0) 分析

右部某位置标有圆点的产生式称为相应文法的一个LR(0)项目（简称为项目）

image-20220513103304315

产生式A→ε 只生成一个项目A→ ·

增广文法

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

image-20220513103407672

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

image-20220513103852131

初始项目：S’→·S

接收项目：S’→S·

归约项目：·在末尾的项目

后继项目：同属于一个产生式的项目，但圆点的位置只相差一个符号， 则称后者是前者的后继项目

A→α· Xβ的后继项目是A→αX·β

可以把等价的项目组成一个项目集( I ) ，称为项目集闭包(Closure of Item Sets)，每个项目集闭包对应着自动机的一个状态

eg：

image-20220513104546195

image-20220513104843423

image-20220513104852180

LR(0)分析过程的冲突

移进归约冲突

image-20220513105245484

image-20220513105343336

在状态2时，当遇到*号时，不清楚应该移入还是归约。

归约归约冲突

image-20220513105500066

状态二有两个归约和一个移入，移进/归约冲突和归约/归约冲突混合。

如果LR(0)分析表中没有语法分析动作冲突，那么给定的文法就称为LR(0)文法

不是所有CFG(上下文无关文法)都能用LR(0)方法进行分析，也就是说，CFG不总是LR(0)文法。

SLR 分析

LR(0)解决不了冲突的原因

1
2
句柄都是相对一个句型而言的，因此应该将句柄的识别放在句型这样一个上下文环境中考虑
LR(0)考虑了A的上文（规范句型的前缀），但未考虑A的下文，因此消解冲突能力有限

image-20220513135613449

SLR冲突

image-20220513135724655

当状态2遇到=时，会有移入归约冲突。

存在问题

1
SLR只是简单地考察下一个输入符号b是否属于与归约项目A→α相关联的FOLLOW(A)，但b∈FOLLOW(A)只是归约α的一个必要条件，而非充分条件

LR(1)分析

在特定位置，A的后继符集合是FOLLOW(A)的子集，而SLR分析法则将其全部考虑了进去。

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

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

image-20220513143948062

image-20220513144511943

如果除展望符外，两个LR(1)项目集是相同的，则称这两个LR(1)项目集是同心的

LR(1)分析实际上是根据后继符集合的不同，将原始的LR(0)状态分裂成不同的LR(1)状态

LALR分析

1
2
3
寻找具有相同核心的LR  (1) 项集，并将这些项集合并为一个项集。 所谓项集的核心就是其第一分量的集合
然后根据合并后得到的项集族构造语法分析表
如果分析表中没有语法分析动作冲突，给定的文法就称为LALR  (1) 文法，就可以根据该分析表进行语法分析

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

image-20220513145829960

合并同心项集不会产生移进-归约冲突

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

LALR分析法可能会作多余的归约动作，但绝不会作错误的移进操作

LALR(1)的特点

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

二义性文法的LR分析

每个二义性文法都不是LR的
某些类型的二义性文法在语言的描述和实现中很有用

用优先级和结合性解决冲突

应该保守地使用二义性文法，并且必须在严格控制之下使用，因为稍有不慎就会导致语法分析器所识别的语言出现偏差

LR分析中的错误处理

语法错误的检测

1
当LR分析器在查询语法分析动作表并发现一个报错条目时，就检测到了一个语法错误

错误恢复策略

1
2
恐慌模式错误恢复
短语层次错误恢复

恐慌错误恢复

1
2
3
4
从栈顶向下扫描，直到发现某个状态si，它有一个对应于某个非终结符A的GOTO目标，可以认为从这个A推导出的串中包含错误
然后丢弃0个或多个输入符号，直到发现一个可能合法地紧跟在A之后的符号a为止
之后将si+1 = GOTO(si , A)压入栈中，继续进行正常的语法分析
实践中可能会选择多个这样的非终结符A。通常这些非终结符代表了主要的程序段，比如表达式、语句或块

短语层次错误恢复

1
2
检查LR分析表中的每一个报错条目，并根据语言的使用方法来决定程序员所犯的何种错误最有可能引起这个语法错误
然后构造出适当的恢复过程

image-20220513151319857

语法制导翻译

语法制导翻译使用CFG来引导对语言的翻译，是一种面向文法的翻译技术

基本思想

1
2
3
如何表示语义信息：为CFG中的文法符号设置语义属性，用来表示语法成分对应的语义信息
如何计算语义属性：文法符号的语义属性值是用与文法符号所在产生式（语法规则）相关联的语义规则来计算的
对于给定的输入串x ，构建x的语法分析树，并利用与产生式（语法规则）相关联的语义规则来计算分析树中各结点对应的语义属性值

语法制导定义(Syntax-Directed Definitions, SDD)

1
2
3
4
SDD是对CFG的推广
将每个文法符号和一个语义属性集合相关联
将每个产生式和一组语义规则相关联，这些规则用于计算该产生式中各文法符号的属性值
如果X是一个文法符号，a是X的一个属性，则用X.a表示属性a在某个标号为X的分析树结点上的值

语法制导翻译方案 (Syntax-Directed Translation Scheme , SDT )

1
SDT是在产生式右部嵌入了程序片段的CFG，这些程序片段称为语义动作。一个语义动作在产生式中的位置决定了这个动作的执行时间

语法制导定义SDD

概述

语法制导定义SDD是对CFG的推广

1
2
将每个文法符号和一个语义属性集合相关联
将每个产生式和一组语义规则相关联，用来计算该产生式中各文法符号的属性值

文法符号的属性

1
2
综合属性 (synthesized attribute)
继承属性 (inherited attribute)

综合属性

1
2
在分析树结点 N上的非终结符A的综合属性只能通过 N的子结点或 N本身的属性值来定义
终结符可以具有综合属性。终结符的综合属性值是由词法分析器提供的词法值，因此在SDD中没有计算终结符属性值的语义规则

继承属性

1
2
在分析树结点 N上的非终结符A的继承属性只能通过 N的父结点、N的兄弟结点或 N本身的属性值来定义
终结符没有继承属性。终结符从词法分析器处获得的属性值被归为综合属性值

属性文法

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

SDD的求值顺序

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

依赖图

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

eg：image-20220513155754626

属性值计算顺序

1
这样的排序将一个有向图变成了一个线性排序，这个排序称为这个图的拓扑排序
1
2
3
对于只具有综合属性的SDD ，可以按照任何自底向上的顺序计算它们的值
对于同时具有继承属性和综合属性的SDD，不能保证存在一个顺序来对各个节点上的属性进行求值
如果图中没有环，那么至少存在一个拓扑排序

S-属性定义与L-属性定义

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

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

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

正式定义

1
2
3
4
一个SDD是L-属性定义，当且仅当它的每个属性要么是一个综合属性，要么是满足如下条件的继承属性：假设存在一个产生式A→X1X2…Xn，其右部符号Xi (1<= i <= n)的继承属性仅依赖于下列属性：
A的继承属性
产生式中Xi左边的符号 X1, X2, … , Xi-1 的属性
Xi本身的属性，但Xi 的全部属性不能在依赖图中形成环路

虚属性：就是一个动作，不干其他事情。

语法制导翻译方案SDT

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

SDD定义了各属性的计算方法（计算规则），SDT进一步明确了各属性的计算时机（计算顺序）

这两种情况下，SDT可在语法分析过程中实现

1
2
基本文法可以使用LR分析技术，且SDD是S属性的
基本文法可以使用LL分析技术，且SDD是L属性的

S-SDD转换为SDT

将每个语义动作都放在产生式的最后

S-属性定义的SDT 实现

1
2
如果一个S-SDD的基本文法可以使用LR分析技术，那么它的SDT可以在LR语法分析过程中实现
当归约发生时执行相应的语义动作

语法分析器的扩展

1
2
为每个栈记录增加属性值字段，存放文法符号的综合属性值
在每次归约时调用计算综合属性值的语义子程序

image-20220513164603555

image-20220513164616906

image-20220513164754145

将L-SDD转换为SDT

1
2
将计算某个非终结符号A的继承属性的动作插入到产生式右部中紧靠在A的本次出现之前的位置上
将计算一个产生式左部符号的综合属性的动作放置在这个产生式右部的最右端

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

1
2
3
在非递归的预测分析过程中进行语义翻译
在递归的预测分析过程中进行语义翻译
在LR分析过程中进行语义翻译

L-属性定义的自顶向下翻译

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

扩展语法分析栈

image-20220513205659076

看例题

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

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

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

为每个非终结符A构造一个函数，A的每个继承属性对应该函数的一个形参，函数的返回值是A的综合属性值

对出现在A产生式右部中的每个文法符号的每个属性都设置一个局部变量

例题

算法

1
2
为每个非终结符A构造一个函数，A的每个继承属性对应该函数的一个形参，函数的返回值是A的综合属性值。对出现在A产生式中的每个文法符号的每个属性都设置一个局部变量
非终结符A的代码根据当前的输入决定使用哪个产生式

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

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

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

中间代码生成

声明语句的翻译

主要任务

1
收集标识符的类型等属性信息，并为每一个名字分配一个相对地址

名字的类型和相对地址信息保存在相应的符号表记录中

类型表达式

基本类型是类型表达式

1
2
3
4
5
6
integer
real
char
boolean
type_error (出错类型)
void (无类型)

可以为类型表达式命名，类型名也是类型表达式

将类型构造符(type constructor)作用于类型表达式可以构成新的类型表达式

数组构造符array

若T是类型表达式，则array ( I, T )是类型表达式( I是一个整数)

image-20220514094900862

指针构造符pointer

若T 是类型表达式，则 pointer ( T ) 是类型表达式，它表示一个指针类型

笛卡尔乘积构造符X

若T1 和T2是类型表达式，则笛卡尔乘积T1 X T2 是类型表达式

函数构造符→

若T1、T2、…、Tn 和R是类型表达式，则T1T2 …Tn→ R是类型表达式

记录构造符record

若有标识符N1 、N2 、…、Nn 与类型表达式T1 、T2 、…、Tn ， 则 record ( ( N1 X T1 ) X ( N2 X T2 )X …X ( Nn X Tn )) 是一个类型表达式

eg：image-20220514095400390

局部变量的存储分配

对于声明语句，语义分析的主要任务就是收集标识符的类型等属性信息，并为每一个名字分配一个相对地址

1
2
从类型表达式可以知道该类型在运行时刻所需的存储单元数量称为类型的宽度(width)
在编译时刻，可以使用类型的宽度为每一个名字分配一个相对地址

名字的类型和相对地址信息保存在相应的符号表记录中

赋值语句的翻译

简单赋值语句的翻译

newtemp( )：生成一个新的临时变量t，返回t的地址

gen(code)：生成三地址指令code

lookup(name)：查询符号表返回name 对应的记录

增量翻译

1
在增量方法中，gen( )不仅要构造出一个新的三地址指令，还要将它添加到至今为止已生成的指令序列之后

ppt例子

数组引用的翻译

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

image-20220514114112824

image-20220514142140992

image-20220514142202241

符号表的组织——数组

image-20220514142237490

控制语句的翻译

控制流语句

继承属性

1
2
3
B.true：是一个地址，该地址用来存放当B为真时控制流转向的指令的标号
B.false：是一个地址，该地址用来存放当B为假时控制流转向的指令的标号
S.next：是一个地址，该地址用来存放紧跟在S代码之后执行的指令(S的后继指令)的标号

image-20220514143929654

if-then-else

image-20220514144057301

if-then

image-20220514144152954

while-do

image-20220514144250284

控制流语句SDT编写要点

1
2
3
4
5
分析每一个非终结符之前
先计算继承属性
再观察代码结构图中该非终结符对应的方框顶部是否有导入箭头。如果有，调用label( )函数
上一个代码框执行完不顺序执行下一个代码框时，生成一条显式跳转指令
有自下而上的箭头时，设置begin属性。且定义后直接调用label( )函数绑定地址

布尔表达式的翻译

在跳转代码中，逻辑运算符&&、|| 和 ! 被翻译成跳转指令。运算符本身不出现在代码中，布尔表达式的值是通过代码序列中的位置来表示的

image-20220514144701666

布尔表达式的SDT

image-20220514144801933

image-20220514145311289

image-20220514145338517

SDT的通用实现方法

任何SDT都可以通过下面的方法实现

1
2
首先建立一棵语法分析树
然后按照从左到右的深度优先顺序来执行这些动作

例题

存疑，修改

回填

布尔表达式回填

基本思想

1
生成一个跳转指令时，暂时不指定该跳转指令的目标标号。这样的指令都被放入由跳转指令组成的列表中。同一个列表中的所有跳转指令具有相同的目标标号。等到 能够确定正确的目标标号时，才去填充这些指令的目标标号

非终结符B的综合属性

1
2
B.truelist：指向一个包含跳转指令的列表，这些指令最终获得的目标标号就是当B为真时控制流应该转向的指令的标号
B.falselist：指向一个包含跳转指令的列表，这些指令最终获得的目标标号就是当B为假时控制流应该转向的指令的标号

函数

1
2
3
4
5
6
makelist( i )
创建一个只包含i的列表，i是跳转指令的标号，函数返回指向新创建的列表的指针
merge( p1, p2 )
将 p1 和 p2 指向的列表进行合并，返回指向合并后的列表的指针
backpatch( p, i )
将 i 作为目标标号插入到 p所指列表中的各指令中

例题

控制流语句回填

综合属性

1
S.next1ist：指向一个包含跳转指令的列表，这些指令最终获得的目标标号就是按照运行顺序紧跟在S代码之后的指令的标号

例题

回填技术SDT编写要点

1
2
3
4
5
文法改造
在list箭头指向的位置设置标记非终结符M
在产生式末尾的语义动作中
计算综合属性
调用backpatch ( )函数回填各个list

switch语句的翻译

image-20220514162527513

image-20220514162534065

image-20220514162733153

过程调用语句的翻译

需要一个队列q存放E1.addr 、E2.addr、…、 En.addr，以生成

image-20220514163207424

例子

运行存储分配

存储组织

一个目标程序运行所需的存储空间主要包括

image-20220514163839643

存储分配策略

1
2
3
4
5
对于那些在编译时刻就可以确定大小的数据对象，可以在编译时刻就为它们分配存储空间，这样的分配策略称为静态存储分配
反之，如果不能在编译时完全确定数据对象的大小，就要采用动态存储分配的策略。即在编译时仅产生各种必要的信息，而在运行时刻，再动态地分配数据对象的存储空间
栈式存储分配
堆式存储分配
静态和动态分别对应编译时刻和运行时刻

image-20220514194257711

活动记录

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

活动记录的一般形式

image-20220514194518053

静态存储分配

1
2
3
4
在静态存储分配中，编译器为每个过程确定其活动记录在目标程序中的位置
这样，过程中每个名字的存储位置就确定了
因此，这些名字的存储地址可以被编译到目标代码中
过程每次执行时，它的名字都绑定到同样的存储单元

适合静态存储分配的语言必须满足以下条件

1
2
3
数组上下界必须是常数
不允许过程的递归调用
不允许用户动态建立数据实体

满足这些条件的语言有BASIC和FORTRAN等

常用的静态存储分配方法：顺序分配法、层次分配法

顺序分配法

按照过程出现的先后顺序逐段分配存储空间
各过程的活动记录占用互不相交的存储空间

image-20220514195326335

1
2
优点：处理上简单
缺点：对内存空间的使用不够经济合理

层次分配法

通过对过程间的调用关系进行分析，凡属无相互调用关系的并列过程，尽量使其局部数据共享存储空间

image-20220514195613542

层次分配算法

image-20220514195658467

栈式存储分配

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

活动树

1
2
3
用来描述程序运行期间控制进入和离开各个活动的情况的树称为活动树
树中的每个结点对应于一个活动。根结点是启动程序执行的main过程的活动
在表示过程p的某个活动的结点上，其子结点对应于被p的这次活动调用的各个过程的活动。按照这些活动被调用的顺序，自左向右地显示它们。一个子结点必须在其右兄弟结点的活动开始之前结束
1
2
3
4
每个活跃的活动都有一个位于控制栈中的活动记录
活动树的根的活动记录位于栈底
程序控制所在的活动的记录位于栈顶
栈中全部活动记录的序列对应于在活动树中到达当前控制所在的活动结点的路径

设计活动记录的一些原则

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

调用序列和返回序列

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

image-20220514203627726

image-20220514203641791

调用者和被调用者之间的任务划分

image-20220514203739336

变长数据的存储分配

1
2
在现代程序设计语言中，在编译时刻不能确定大小的对象将被分配在堆区。但是，如果它们是过程的局部对象，也可以将它们分配在运行时刻栈中。尽量将对象放置在栈区的原因：可以避免对它们的空间进行垃圾回收，也就减少了相应的开销
只有一个数据对象局部于某个过程，且当此过程结束时它变得不可访问，才可以使用栈为这个对象分配空间

非局部数据的访问

一个过程除了可以使用过程自身声明的局部数据以外，还可以使用过程外声明的非局部数据

1
2
全局数据
外围过程定义的数据

如何访问非局部数据

1
2
访问链（静态链）
display表（嵌套层次显示表）

访问链

1
2
3
静态作用域规则：只要过程b的声明嵌套在过程a的声明中，过程b就可以访问过程a中声明的对象
可以在相互嵌套的过程的活动记录之间建立一种称为访问链(Access link)的指针，使得内嵌的过程可以访问外层过程中声明的对象
如果过程b在源代码中直接嵌套在过程a中(b的嵌套深度比a的嵌套深度多1)，那么b的任何活动中的访问链都指向最近的a的活动

嵌套深度

image-20220514205925465

例子

访问链的建立

假设嵌套深度为nx的过程x调用嵌套深度为ny的过程y (x→y)

nx < ny的情况(外层调用内层)

1
2
y一定是直接在x中定义的 (例如：s→q,  q→p) ，因此，ny=nx +1
在调用代码序列中增加一个步骤：在y的访问链中放置一个指向x的活动记录的指针

nx = ny的情况(本层调用本层 )

1
2
例如：递归调用 (q→q )
被调用者的活动记录的访问链与调用者的活动记录的访问链是相同的，可以直接复制

nx > ny的情况(内层调用外层，如： p→e )

1
2
调用者x必定嵌套在某个过程z中，而z中直接定义了被调用者y
从x的活动记录开始，沿着访问链经过nx - ny + 1步就可以找到离栈顶最近的z的活动记录。 y的访问链必须指向z的这个活动记录

嵌套深度是在编译阶段通过静态分析就能确定的

display表

慕课没有

看例题，注意嵌套深度与树无关，在编译阶段就决定。

参数传递

形式参数（formal parameter）：在过程定义中使用的参数
实际参数（actual parameter）：在调用过程时使用的参数

形参和实参相关联的几种方法

1
2
3
4
传值（Call- by-Value）
传地址（Call- by-Reference）
传值结果（Call- by-Value-Result）
传名（Call- by-Name）

传值

1
2
3
4
把实参的值传递给相应的形参
实现方法
调用过程把实参的值计算出来，并传递到被调用过程相应的形式单元中
被调用过程中，像引用局部数据一样引用形式参数，直接访问对应的形式单元

传地址

1
2
3
4
把实参的地址传递给相应的形参
实现方法
调用过程把实参的地址传递到被调用过程相应的形式单元中
被调用过程中，对形参的引用或赋值被处理成对形式单元的间接访问

传值结果

1
2
3
4
5
传地址的一种变形
实现方法
每个形参对应两个形式单元。第一个形式单元存放实参的地址，第二个形式单元存放实参的值
在过程体中，对形参的引用或赋值看作对它的第二个形式单元的直接访问
过程完成返回前，把第二个单元的内容存放到第一个单元所指的实参单元中

传名

1
2
3
4
相当于把被调用过程的过程体抄到调用出现的地方，但把其中出现的形参都替换成相应的实参
实现方法
在进入被调用过程之前不对实参预先进行计值，而是让过程体中每当使用到相应的实参时才逐次对它实行计值（或计算地址）
通常把实参处理成一个子程序（称为参数子程序），每当过程体中使用到相应的实参时就调用这个子程序

符号表

符号表是用于存放标识符的属性信息的数据结构

1
2
3
4
5
种属 (Kind)
类型 (Type)
存储位置、长度
作用域 
参数和返回值信息

符号表的作用

1
2
辅助代码生成
一致性检查

例子

image-20220514213155111

标识符的基本处理方法

1
2
3
4
5
6
当在某一层的声明语句中识别出一个标识符(id的定义性出现)时，以此标识符查相应于本层的符号表
如果查到，则报错并发出诊断信息“id重复声明”
否则，在符号表中加入新登记项，将标识符及有关信息填入
当在可执行语句部分扫视到标识符时( id的应用性出现)
首先在该层符号表中查找该id，如果找不到，则到直接外层符号表中去查，如此等等，一旦找到，则在表中取出有关信息并作相应处理
如果查遍所有外层符号表均未找到该id，则报错并发出诊断信息“id未声明”

符号表的建立？

代码优化

流图

基本块(Basic Block)是满足下列条件的最大的连续三地址指令序列

1
2
控制流只能从基本块的第一条指令进入该块。也就是说，没有跳转到基本块中间或末尾指令的转移指令
除了基本块的最后一条指令，控制流在离开基本块之前不会跳转或者停机

每个基本块由一组总是一起执行的指令组成

image-20220515003940960

流图的每个结点是一个基本块
从基本块B到基本块C之间有一条边当且仅当基本块C的第一条指令可能紧跟在B的最后一条指令之后执行，此时称B是C的前驱(predecessor) ， C是B的后继(successor)

优化的分类

机器无关优化：针对中间代码
机器相关优化：针对目标代码
局部代码优化：单个基本块范围内的优化
全局代码优化：面向多个基本块的优化

常用的优化方法

1
2
3
4
5
删除公共子表达式
删除无用代码
代码移动
强度削弱
删除归纳变量

删除公共子表达式

如果表达式x op y先前已被计算过，并且从先前的计算到现在，x op y中变量的值没有改变，那么x op y的这次出现就称为公共子表达式

局部公共子表达式；全局公共子表达式

例子

删除无用代码

复制传播

1
2
常用的公共子表达式消除算法和其它一些优化算法会引入一些复制语句(形如x = y的赋值语句)
 复制传播：在复制语句x = y之后尽可能地用y代替x

复制传播给删除无用代码带来机会

无用代码(死代码Dead-Code ) ：其计算结果永远不会被使用的语句

例子

常量合并

如果在编译时刻推导出一个表达式的值是常量，就可以使用该常量来替代这个表达式。该技术被称为常量合并

代码移动

这个转换处理的是那些不管循环执行多少次都得到相同结果的表达式(即循环不变计算，loop-invariant computation) ，在进入循环之前就对它们求值

对于多重嵌套的循环，循环不变计算是相对于某个循环而言的。可能对于更加外层的循环，它就不是循环不变计算

强度削弱

用较快的操作代替较慢的操作，如用加代替乘

归纳变量

1
对于一个变量x ，如果存在一个正的或负的常数c使得每次x被赋值时它的值总增加c ，那么x就称为归纳变量(Induction Variable)

删除归纳变量

1
在沿着循环运行时，如果有一组归纳变量的值的变化保持步调一致，常常可以将这组变量删除为只剩一个

基本块的优化

很多重要的局部优化技术首先把一个基本块转换成为一个无环有向图

image-20220515144138737

基于基本块的 DAG 删除无用代码

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

image-20220515144511396

数组元素赋值指令的表示

image-20220515144602509

1
在a[j]=y时，有可能改变a[i]的值

image-20220515144738742

根据基本块的DAG可以获得一些非常有用的信息

1
2
3
4
确定哪些变量的值在该基本块中赋值前被引用过
在DAG中创建了叶结点的那些变量
确定哪些语句计算的值可以在基本块外被引用
在DAG构造过程中为语句s（该语句为变量x定值）创建的节点N，在DAG构造结束时x仍然是N的定值变量

image-20220515144412561

例子

数据流分析

一组用来获取有关数据如何沿着程序执行路径流动的相关信息的技术

在每一种数据流分析应用中，都会把每个程序点和一个数据流值关联起来

数据流分析的主要应用

1
2
3
到达-定值分析 (Reaching-Definition Analysis)
活跃变量分析 (Live-Variable Analysis)
可用表达式分析 (Available-Expression Analysis)

数据流分析模式

1
2
3
4
5
6
7
8
语句的数据流模式
 IN[s]:	语句s之前的数据流值
	 OUT[s]:	语句s之后的数据流值
 fs：语句s的传递函数(transfer function)
     一个赋值语句s之前和之后的数据流值的关系
     传递函数的两种风格
        信息沿执行路径前向传播 (前向数据流问题)：OUT[s] = fs (IN[s])
        信息沿执行路径逆向传播 (逆向数据流问题)：IN[s] = fs (OUT[s])

到达定值分析

定值

1
变量x的定值是(可能)将一个值赋给x的语句

到达定值(Reaching Definition)

1
2
如果存在一条从紧跟在x的定值d后面的点到达某一程序点p的路径，而且在此路径上d没有被“杀死” (如果在此路径上有对变量x的其它定值d′，则称定值d被定值d′“杀死”了) ，则称定值d到达程序点p
直观地讲，如果某个变量x的一个定值d到达点p，在点p处使用的x的值可能就是由d最后赋予的

image-20220515155110137

到达定值分析的主要用途

循环不变计算的检测

1
如果循环中含有赋值x=y+z ，而y和z所有可能的定值都在循环外面(包括y或z是常数的特殊情况) ，那么y+z就是循环不变计算

常量合并

1
如果对变量x的某次使用只有一个定值可以到达，并且该定值把一个常量赋给x ，那么可以简单地把x替换为该常量

判定变量x在p点上是否未经定值就被引用

image-20220515155325874

image-20220515155539821

image-20220515155645902

例子

image-20220515155911362

到达定值的计算

例题

引用-定值链

image-20220515160301603

活跃变量分析

活跃变量

1
对于变量x和程序点p，如果在流图中沿着从p开始的某条路径会引用变量x在p点的值，则称变量x在点p是活跃(live)的，否则称变量x在点p不活跃(dead)

例子

活跃变量信息的主要用途

删除无用赋值

1
无用赋值：如果x在点p的定值在基本块内所有后继点都不被引用，且x在基本块出口之后又是不活跃的，那么x在点p的定值就是无用的

为基本块分配寄存器

1
2
如果所有寄存器都被占用，并且还需要申请一个寄存器，则应该考虑使用已经存放了死亡值的寄存器，因为这个值不需要保存到内存
 如果一个值在基本块结尾处是死的就不必在结尾处保存这个值

image-20220515165840678

image-20220515170431350

image-20220515170613886

image-20220515172411560

image-20220515173505087

可用表达式分析

可用表达式

1
如果从流图的首节点到达程序点 p的每条路径都对表达式x op y进行计算，并且从最后一个这样的计算到点p之间没有再次对x或y定值，那么表达式x op y在点 p是可用的(available)

表达式可用的直观意义

1
在点 p上，x op y已经在之前被计算过，不需要重新计算

主要通途

消除全局公共子表达式

进行复制传播

image-20220515193957942

可用表达式传递函数

image-20220515194252677

可用表达式的数据流方程

image-20220515194545925

image-20220515194801190

注意此处初始化

流图中的循环

支配结点

1
如果从流图的入口结点到结点n的每条路径都经过结点d，则称结点d支配(dominate)结点n，记为d dom n

寻找支配节点

image-20220515195118328

image-20220515195158344

回边

1
如果存在从结点n到d的有向边n→d，且d dom n，那么这条边称为回边

自然循环

image-20220515195547361

image-20220515195949826

image-20220515200001241

自然循环的一个重要性质

1
如果两个自然循环的首结点不相同，则这两个循环要么互不相交，要么一个完全包含(嵌入)在另外一个里面

最内循环 (Innermost Loops): 不包含其它循环的循环

如果两个循环具有相同的首结点，那么很难说哪个是最内循环。此时把两个循环合并

全局优化

1
2
3
4
5
删除全局公共子表达式
删除复制语句
代码移动
作用于递归变量的强度削弱
删除递归变量

删除全局公共子表达式

image-20220515200350777

删除复制语句

对于复制语句s: x=y，如果在x的所有引用点都可以用对y的引用代替对x的引用(复制传播)，那么可以删除复制语句 x=y

image-20220515200456345

代码移动

循环不变计算检测算法

image-20220515200548207

代码外提

image-20220515200759125

循环不变计算语句 s : x = y + z 移动的条件

1
2
3
(1) s所在的基本块是循环所有出口结点(有后继结点在循环外的结点)的支配结点
(2) 循环中没有其它语句对x赋值
(3) 循环中对x的引用仅由s到达

image-20220515201036529

例子

作用于归纳变量的强度削弱

1
2
3
4
对于一个变量x ，如果存在一个正的或负的常量c ，使得每次x被赋值时，它的值总是增加c ，则称x为归纳变量
如果循环L中的变量i 只有形如i =i+c的定值(c是常量)，则称i为循环L的基本归纳变量
如果j = c×i+d，其中i是基本归纳变量，c和d是常量，则j也是一个归纳变量，称j属于i族
每个归纳变量都关联一个三元组。如果j = c×i+d，其中i是基本归纳变量，c和d是常量，则与j相关联的三元组是( i, c, d )

image-20220515201237286

image-20220515201248830

image-20220515201356302

归纳变量的删除

1
2
3
对于在强度削弱算法中引入的复制语句j=t，如果在归纳变量j的所有引用点都可以用对t的引用代替对j的引用，并且j在循环的出口处不活跃，则可以删除复制语句j=t

强度削弱后，有些归纳变量的作用只是用于测试。如果可以用对其它归纳变量的测试代替对这种归纳变量的测试，那么可以删除这种归纳变量

删除仅用于测试的归纳变量

image-20220515211020194

代码生成

代码生成器的主要任务

指令选择

1
选择适当的目标机指令来实现中间表示(IR)语句

寄存器分配（allocation）和指派（assignment）

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

指令排序

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

一个简单的目标机模型

三地址机器模型

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

指令选择

image-20220515215146285

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

1
2
使用静态内存分配的方式
使用栈式内存分配的方式

callee的活动记录在静态区中的起始位置

callee的目标代码在代码区中的起始位置

image-20220515215844342

寄存器的选择

image-20220515220019625

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

寄存器描述符

1
记录每个寄存器当前存放的是哪些变量的值

地址描述符

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

基本块的收尾处理

1
2
3
在基本块结束之前，基本块中使用的变量可能仅存放在某个寄存器中
如果这个变量是一个只在基本块内部使用的临时变量，当基本块结束时，可以忘记这些临时变量的值并假设这些寄存器是空的
对于一个在基本块的出口处可能活跃的变量x ,  如果它的地址描述符表明它的值没有存放在x的内存位置上,  则生成指令“ST x, R” ( R是在基本块结尾处存放 x值的寄存器 )

管理寄存器和地址描述符

1
当代码生成算法生成加载、保存和其他指令时，它必须同时更新寄存器和地址描述符

image-20220515220152288

image-20220515220242413

image-20220515220310043

image-20220515220624081

寄存器选择函getReg

image-20220515221133482

image-20220515221317333

image-20220515221332913

窥孔优化

窥孔(peephole)是程序上的一个小的滑动窗口

窥孔优化是指在优化的时候，检查目标指令的一个滑动窗口(即窥孔) ，并且只要有可能就在窥孔内用更快或更短的指令来替换窗口中的指令序列

也可以在中间代码生成之后直接应用窥孔优化来提高中间表示形式的质量

具有窥孔优化特点的程序变换的例子

1
2
3
4
冗余指令删除
控制流优化
代数优化
机器特有指令的使用

习题总结

重点

已掌握

1
2
3
4
3.1 4.1 4.2  5.1(5.1.2重点) 6.1 6.2 7.1 7.2 7.3 7.4 7.5 (规范LR项集族) 7.6 7.7 7.8  7.9
8.1 8.3 9.2(设计SDD) 9.3(设计SDD) 9.4(改写SDT) 12.2(四元式) 12.3(翻译赋值语句) 13.1(控制流处理方案) 13.2 13.3(控制流四元式) 14.1(求truelist) 14.2 14.3 14.4(构造SDT) 14.6(设计sdt) 15.1 15.2(快排) 15.3(Fibonacci) 15.4(栈问题，考前再看一下) 15.5 15.6(符号表) 16.3 16.4(DAG) 16.5 16.6(带跳转和[]=的DAG) 16.7 16.8(基本块) 
17.1(到达定值分析) 18.1(可用表达式分析) 18.2(活跃变量分析,逆分析) 18.3(到达定值分析应用) 19.1(重点，各种值的找取)
19.2(重点，代码优化) 19.6

未掌握

1
2
3
4
5
6
4.1.3的消除左递归方法 
9.1 扩展SDD
10.1(构造递归下降SDD)
13.4 13.5 *13.6(翻译方案) 
14.5(超级复杂的SDT构造)
19.5

非重点

已掌握

1
1.2 2.1 8.2 8.4(是否存在一致的求值过程)

未掌握

1
1.1 6.3 18.4 18.5

各种链