编译原理讲义
(第六章,语义分析和目标代码生成 )
南京大学计算机系赵建华概念
编译程序的作用是：将源程序转换为具有 相同效果 的可运行程序。
所谓 相同效果 就是程序的语义。
并不是所有满足语法规则的程序都是有意义的 (well-
form)的。
所谓语义分析，就是确定程序是有意义的，分析程序的含义，并做出相应的处理。
程序的含义包括：
– 数据结构的含义：和标识符相关联的数据对象。
– 控制结构的含义：由语言定义。规定了每个语句的执行效果。
基本功能
确定类型：确定标识符所关联的数据对象的数据类型。
类型检查：按照语言的类型规则，对运算及分量进行类型检查，必要时做出相应类型转换。
识别含义：根据程序设计语言的语义定义，确定各个构造部分组合后的含义，做出相应处理
（生成中间代码或者目标代码）。
其它静态语义检查：比如控制流检查，嵌套层数检查。
语义分析的输入输出
输入为前面语法分析的结果。
输出为中间表示代码 (抽象语法树，三元式 …) 。
– 把生成中间代码和代码生成分开，可以使难点分解。
– 对中间代码的分析比较容易，便于进行优化。
– 可以把编译程序分成机器独立部分和机器相关部分。
– 便于任务的分解，和开发人员的分组开发。
属性文法
对于某个压缩了的文法，当把每个文法符号和一组属性相关联，并把重写规则附加以语义规则的时候，就得到属性文法。
语法制导的翻译过程：由于属性文法的规则和重写规则是一一对应的关系。所以，由属性文法的确定的语义分析可以在语法分析的过程中进行。这个过程成为语法指导的翻译。
语法指导的定义 /翻译方案：语法指导的定义比较抽象，隐藏了实现细节，无需指明语义规则的计算次序。翻译方案则指明的计算次序。
语法制导定义的例子
对于语法符号 E,T,F，都确定了属性 val，表示它们的值。
如果一个重写规则中有两个相同的符号，需加足标区别。
在归约过程中，每个归约得到的符号都对应于输入符号串中的某一段。
L::=En Print(E.val)
E::=E1+T E.val = E1.val+T.val
E::=T E.val = T.val
T::=T1*F T.val = T1.val*F.val
T::=F T.val = F.val
F::=(E) F.val = E.val
F::=digit F.val = digit.lexval
语法制导定义的例子（ 2）
L的属性包括,in； T的属性值为 type
addtype表示将 id对应的类型信息加入到标识符表中。
D::=TL L.in = T.type
T::=int T.type,= integer
T::=real T.type,= integer
L::=L1,id L1.in,= L.in; addtype(id.entry,
L.in)
L::= 空属性的计算和注释分析树
在语法制导分析过程中，我们不仅生成了一棵语法树，
还可以得到各个结点的属性值。把这些值加入到语法树上面之后，就得到了注释分析树。
结点的属性值的计算过程有两种类型：
– 结点的属性由其子结点确定，称为综合属性。
– 结点的属性由兄弟结点和父结点的属性确定，称为继承属性。
在概念上，翻译过程如下：
– 1：分析输入符号，建立语法树
– 2：从语法分析树得到描述结点属性之间的依赖关系，得到计算次序。
– 3：按照语义规则计算属性值。
分析过程和注释分析树例子 (1)
L
E n
TE
T F
F
3
T
*
+
Lexval=3
val=3 5
val=5val=3
val=15
val=15
F
4 lexval=4
val=4
Val=4
Val=19
分析过程和注释分析树例子 (2)
D
T L
real,i3L
L,i2
i1
type=real in=real
in=real
in=real
属性文法
一个属性文法 AG是一个四元组 (G,A,R,C)，其中
– G是已经压缩的文法。
– A是有穷属性集合，对于每个文法符号 X，都有其属性集合 A(X)对应。
– R是有穷属性规则集合。对于规则 p,X0=X1X2…Xk,有规则 Xi.a=f(Xj.b,…,Xpk.c)。定义了在使用这个规则进行归约的时候,Xi.a的求值。
– C是有穷条件集合。 C(Xi.a,…,Xj.a) 表示规则 p必须满足的条件。只有这些条件满足的时候，输入的符号串才是有意义的。
语法制导定义的分类
S_属性定义：所有的文法符号的属性都是综合属性。
– 实际上是说：一个语法结构的属性由它的组成部分的属性确定。
– 例如：对于表达式的结果类型；
– 基于 S_属性定义的语法分析树可以用自底向上的方法得到。
– 规则 E::=E1+T对应的语法结构,E.type的值可以如下确定：如果 E1的类型和 T的类型都是 int，
那么结果也是 int,如果有一个是 real，那么结果类型是 real。,..
继承属性
语法分析树中，一个结点的属性由其父结点和兄弟结点确定。
– 反映了文法结构的属性对上下文的依赖特性。
– 比如：对于 C语言中变量的申明可以是如下方式，
TYPE v1,v2; 那么变量 v1,v2的属性值‘类型’是由 TYPE确定的，如果 TYPE是 float，那么它们的类型就是实数。
– 在前面的例子 6.2中，结点 T的属性 type是综合属性，
但是 D::=TL中,L的属性 in就是继承属性，这个属性的值是由 T的属性 type确定的。
依赖图
在语义规则中，假设某个属性的定义是 b=f(c1,c2,…,cn),
那么要求得属性 b的值，首先要计算出属性 c1,c2,…cn
的值。显然它们的计算顺序有一种依赖关系。
通常，我们可以在语法分析树中添加有向的箭头表示这种依赖关系。（对于过程调用，可以添加虚拟的属性）
在 语法分析树 中，如果属性 b依赖于 c，那么从 c对应的结点到 b对应的结点画一个箭头。
依赖图构造算法
步骤 1：构造语法树，对于语法树中的每个结点的每个属性，构造一个结点。
步骤 2：对每个树的结点 n，对该结点所相关的每个语义规则 b:=f(c1,c2,…,cn) 都如下添加有向弧：
– 从 c1,c2,…cn 的结点向 b对应的结点画有向弧。
实际上是对所有在建立语法树中所使用的规则都建立依赖关系。
依赖图的例子
real id1,id2,,id3
D
T L
L
L
id3
id2
id1
real
type
in
entry
vir
in vir
in vir
entry
entry
计算次序
显然，依赖图中指定了各个属性的计算顺序。
各个属性的计算顺序可以有多种，但是必须满足依赖图规定的拓扑次序。以保证在计算某个属性的值的时候，这个属性所依赖的属性值已经被计算出来。
用语法制导定义说明的翻译步骤如下：
– 构造语法分析树。
– 构造依赖图。
– 对依赖图的各个结点进行拓扑排序，得到计算次序。
– 按照上述次序计算属性的值。
比如，上面的图的计算顺序如下：
– a4=real,a5=a4,addtype(id3.entry,a5),...
其它得到计算次序的方法
避免在分析的过程中显式地构造分析树。
忽略规则：按照语法分析的归约（或者）推导程序完成属性的计算。
– 比如，当定义中只有 S_属性定义的时候，可以按照自底向上归约过程进行。
基于规则的计算次序：通过对重写规则和语义规则进行分析，确定和每个重写规则相关联的语义规则的计算次序。
翻译方案
语法制导定义基于属性文法，其计算次序被隐藏。
如果在进行语义定义的时候，陈述了一些实现的细节，我们称为翻译方案。
在翻译方案中，语义定义部分是用 {}包含的语义动作。并且语义动作可以出现在规则右部的任何地方。
这些语义动作的执行顺序是这样的。当建立了一个语法分析树之后（把语义动作也当作规则右部的结点加入到语法树中），我们按照深度优先的方法变例这个分析树。每次遍历到一个语义动作对应的结点的时候，执行这个动作，
计算相应的属性值。
L_属性定义是可以使用翻译方案计算的一类语义定义方式。
L_属性定义
L_属性定义：如果每个重写规则 U::=X1X2…X n对应的语义规则中的每个属性：
– 或者是综合属性，
– 或者是这样的继承属性：
Xj.a或者仅仅依赖于 U。
Xj.a依赖于 Xj左边的符号的属性。
S_属性定义也是 L_属性定义。
显然，对于 L_属性定义，其属性的值可以按照深度优先的次序计算。也就是说，可以直接地使用翻译方案实现。
L_属性定义的例子可以看关于变量申明的定义。
L_属性定义的属性计算
L_dfvisit(n)
{
for m=从左到右的 n的每个子节点 do
{
计算 m的继承属性；
L_dfvisit(m);
}
计算 n的综合属性。
}
翻译方案的例子
E::=TR
R::=addop T{print(addop.lexeme)}R1 | 空
T::=num{print(num.lexval)}
同时，翻译方案设计需要满足 L_属性定义。
E
T R
- T R
+ T R
2 Print(2) 空
Print(+)
5 Print(5)
Print(-)Print(9)9
翻译方案的设计
对于综合属性，只需要把属性的定义修改称为赋值语句，放在规则的最末尾就可以了。
存在继承属性的时候，必须满足一下条件：
– 重写规则右部符号的属性必须先于这个符号的语义动作中计算。
– 一个语义动作不能引用右边符号的综合属性。
– 重写规则左部的符号的综合属性必须在它所引用的所有属性都计算完成之后才可以计算。
错误的例子,S::=A1A2 {A1.in=1,A2.in=2} A::=a
{print(A.in)}.应该把 {A1.in=1}移到最前面。
L_属性定义总存在相应的翻译方案。
翻译方案的实现 (自底向上 )
S_属性定义的翻译方案可以在分析输入符号串的时候完成。
通过在栈中的每个符号添加一个属性项来完成。
在移入的时候，把文法符号的属性同时压栈。终结符号的属性在词法分析的时候获得。
归约的时候，除了进行原来的工作之外，需要根据重写规则和语义规则，根据栈顶部的符号属性计算出被归约得到的符号的属性值。
比如，如果需要按照 U::=XYZ归约，而相应的语义动作为 {U.a=f(X.x,Y.y,Z.z)}，那么栈顶部的符号为 ZYX，从这些符号的属性部分得到 X.x,Y.y和 Z.z就可以计算得到
U.a。当把 U压入栈的时候，同时把 U.a的值压入属性栈。
实例步骤 栈 规则输入
1
2
3
5
6
7
8
(#,-)(F,3)
(#,-)(T,3)(*,-)
(#,-)(T,3)(*,-)(5,5)
(#,-)(T,3)(*,-)(F,5)
(#,-)(T,15)
(#,-)
(#,-)(3,3)
*5+4n
*5+4n
5+4n
+4n
+4n
3*5+4n
*5+4n
F::=digit
9 (#,-)(E,15) +4n E::=T
F::=digit
10 (#,-)(E,15)(+,-) 输入
4 (#,-)(T,3) *5+4n T::=F
T::=T*F
非 S_属性定义的例子
D::= T{L.in = T.type} L
T::=int{T.type = integer}
T::=real{T.type = real}
L::={L1.in=L.in}L1,id{addtype(id.entry,L.in)}
L::=id {addtype(id.entry,L.in)}
L_属性定义翻译方案不能直接用自底向上的方法实现。
自底向上的方法
在 YACC中通过添加空规则来实现。比如第一个规则修改为 D::=TAL,A::=空，但是问题是：
可能变成非 LR(K)文法，并且，不能直接使用上面的定义。
比如,D::=T{L.in:=T.type}L，实现的方式实际是,D::=TAL,A::=空 {}。
但是，值的传递不是那么方便。
自顶向下的实现方法
可以按照前面 L_属性定义的计算算法计算的方法完成。
但是，需要消除左递归。消除左递归的时候，牵涉到语义规则的修改。
自顶向下的实现方法（例子）
E::=E+T|E-T|T T::=(E)|num
翻译方案如下：
– E::=E+T {E.val=E1.val+T.val}
– E::=E-T {E.val=E1.val-T.val}
– E::=T {E.val=T.val}
– T::=(E) {T.val=E.val}
– T::=num {T.val=num.lexval}
这个翻译方案中，所有的属性都是综合属性。
自顶向下的实现方法（例子）
由于自顶向下的方法不能处理左递归的情况，
所以必须修改相应的重写规则。而语义规则也需要相应的修改。
E::=T{R.i=T.val}R{E.val=R.s}
R::=+T{R1.i=R.i+T.val}R1{R.s=R1.s}
R::=-T{R1.i:=R.i-T.val}R1{R.s=R1.s}
R::=空 {R.s=R.i}
T::=(E{T.val=E.val})
T::=num{T.val=num.lexval}
实现程序（ 1）
E::=T{R.i=T.val}R{E.val=R.s}
S_attribute E(L_attribute)
{attribute E_val;
attribute T_val = T();
attribute R_i = T_val;
attribute R_s = R(R_i);
E_val = R_s;
}
实现程序（ 2）
R::=+T{R1.i=R.i+T.val}R1{R.s=R1.s}
R(attribute in)
{
GetSym();
attribute T_val=T();
attribute R1_i = in+T_val;
attribute R_s = R(R1_i);
return R_s;
}
消除左递归时翻译方案的修改
U::= U1Y {U.a=g(U1.a,Y.y)}
U::=X {U.a=f(X.x)}
修改为：
– U::=X {R.i=f(X.x)} R{U.a = R.s}
– R::=Y {R1.i=g(R.i,Y.y)} R1{R.s=R1.s}
– R::=空 {R.s=R.i}
引入新的符号 R，对于 R有继承属性 i。
R.i纪录了前面扫描过的 U的 a属性值。
关于语义定义的解释
U
U2
U1
X
Y2
Y1
U
R1
R2
X
Y2
Y1
R3
修改后的翻译方案的计算过程
R.i=6 R.s=6
E.val=6
T.val=9
num.lexval=9
R.i=9 R.s=6
- T.val=5
Num.lexval=5 + T.val=2
Num.lexval=2
R.i=4 R.s=6
类型体系
指明了程序中，运算的合法型和运算分量类型的一致性（相容性）；类型转换的规则等。
本部分说明如何使用翻译方案来实现类型的检查。
类型的获得（变量说明）由变量申明部分确定。
类型表达式
使用类型表达式来表示程序中可能出现个各种类型。
定义：
– 基本类型就是类型表达式。
– 对类型表达式命名的类型名时类型表达式。
– 类型构造符作用于类型表达式的结果时类型表达式。
数组,array(I,T)
卡氏积,T1?T2
纪录,record((N1?T1)? (N2?T2)?..,?(Nn?Tn))
指针,pointer(T)
函数,D1?D2?..,?Dn?R
– 类型表达式可以包含变量（如果允许类型重载）
类型表达式例子
int a[200]; array(0..199,int)
struct {int a[10]; float f}st;
record((a?array(0..9,int) )? (f?real))
int *a; pointer(int)
int f(int a,float f)
(int? float)?int
表达式类型的等价性
类型等价的定义可以分为结构等价和名字等价。
结构等价：两个类型表达式结构等价 iff
它们是相同的基本类型，或者它们是从同样的类型构造符作用于结构等价的类型。
名字等价：（如果允许类型命名）当且仅当它们相同。
结构等价的确定
BOOL testeq(s,t)
{ if(s和 t是相同的基本类型） return true;
if(s ==array(s1,s2) && t==array(t1,t2))
return testeq(s1,t1) && testeq(s2,t2);
if(s==s1?s2 && t==t1?t2)
return testeq(s1,t1) && testeq(s2,t2);
… … … …
return false;
}
名字等价的例子
变量和类型申明 (pascal)：
– TYPE link = ^cell; np = ^cell; neq=^cell;
– VAR next:link,last:link,p:np,q:nqr; r:nqr;
所有的变量在结构等价的意义下面都相同。但是在名字等价的情况下：
– next和 last相同； q,r类型相同；
– p和 next类型相同。
类型强制
一般的程序设计语言中都规定了某些类型之间的转换关系：比如说整数量可以被当作实数量参与运算，并且不需要程序员显式说明。
不同类型的常数在计算机中有不同的表示。当一个值需要转换称为其它类型使用的时候，需要使用某些代码进行转换。
因此，编译程序需要识别需要进行类型转换的地方，并相应地生成代码。
程序设计语言的设计者需要考虑什么情况下需要和可以进行转换。
类型强制转换的语义规则
首先，要确定强制转换的地方，首先需要确定参加运算的分量的类型，而这个分量本身就可能是一个表达式。
重写规则 语义规则
E::=num
E::=num.num
E::=id
E.type:=integer
E.type=float
E.type=gettype(id.entry)
E::=E1 op E2 if (E1.type=int && E2.type=int)
E.type = integer;
if (E1.type=int&&E2.type=float)
E.type = float;(E1的结果需要强制转换 )
… …
变量类型的确定
类型确定就是确定标识符代表对象的数据类型。在标识符的定义性出现的时候，要把标识符和类型相关联；
在标识符的使用性出现时，需要获取得到标识符相关联的类型。
假设说明部分的文法如下：
– P::=D;E D::=D;D | id:T
– T::=char | integer | ARRAY[num] OF T | ^T
处理说明部分的时候，需要做的语义处理是：对于每个说明 id:T，把 id和 T的类型表达式相关联。就是说，
将 id的类型为 T的信息纪录到标识符表中。所以，每次识别到 D::=id:T的情况时，需要调用 addtype(id,T.type)
变量类型的确定
D有一个虚拟的综合属性。 T有属性 type，
以后的作业和考试中，对于标识符有属性 entry，常量有属性 lexval
D::=D;D
D::=id:T
T::=char
T::=integer
T::=^T1
T::=ARRAY[num] of T
{addtype(id.entry,T.type)}
{T.type,= char}
{T.type = integer}
{T.type=pointer(T1.type)}
{T.type=array(num.lexval,T.type)
类型检查
类型检查可以分为动态和静态两种。
– 动态检查在运行时刻完成。功效很低。但是如果语言允许动态确定类型，动态检查是必须的。
– 静态检查在编译时刻完成。静态检查是高效的。
如果一个语言能够保证所有经过静态检查之后，程序没有运行时刻的类型错误，则称为强类型的。
类型检查的内容包括：
– 表达式
– 语句
– 函数表达式的类型检查
对于表达式的类型检查，主要的工作是检查参与运算的操作数是否可以进行相应操作。
重写规则 重写规则
E::=literal
E::=num
E::=E1 mod E2
E::=E1 [E2]
{E.type = char}
{E.type = integer}
{E.type = if (E1.type = integer &&
E2.type==integer) then integer else
type_error}
E::=id {E.type = gettype(id.entry)}
语句的类型检查
语句的类型检查主要包括,赋值语句 类型的相容性，控制表达式的结果类型检查。
先面的例子中，赋值语句要求左右两边类型相同；在 C
语言中，赋值类型相容性在表达式部分处理。
重写规则 重写规则
S::=id = E
S::=while E do S1
{S.type = if id.type == E.type
then void else type_error}
{S.type = if E.type = boolean then
S1.type else type_error}
S::= if E then S1 {S.type=if E.type = boolean
then S1.type else type_error
函数的类型检查
简化了的函数调用语法为 E::=E(E)；
类型检查所需要做的工作是：检查参数是否符合条件，并且确定函数结果的类型。
E::= E1(E2)
{E.type = if E2.type=s and E1.type=s?t then t
else type_error}
当函数有多个参数的时候，需要检查多个参数的类型。
实际的翻译方案还需要考虑类型的相容性问题。
说明部分的翻译
对于说明部分的翻译，需要考虑的问题包括：
– 标识符的类型纪录。
– 标识符对应的数据对象的地址分配。
– 标识符的作用域问题。
常量定义的翻译
常量定义的翻译主要工作是将常量标识符的信息纪录下来。
重写规则 语义动作规则
CDT::=CDT;CD
CD::=id=num {num.ord=lookCT(num.lexval);id.ord
=num.ord; id.type=integer;
id.kind=CONST; add(id.entry,id.kind,
id.type,id.ord)}
CDT::=CD
变量说明的翻译
变量说明的翻译工作包括：确定变量类型，分配地址空间。
地址空间的分配方式如下：有一个全局变量 offset，纪录了当前可用的空间的开始地址。每次分配一个变量的空间，将
offset增加相应的值。
有 static类变量时，必须
规则如下：
– P::={offset = 0}D;S D::=D;D
– D::=id:T {enter(id.name,T.type,offset); offset+=T.width}
– T::=integer {T.type=integer,T.width=8}
– T::=real {T.type=real; T.width=8}
– T::=ARRAY[num] of T1 {T.type=array(num.lexval,
T1.type); T.width=num.lexval*T1.width}
变量说明的处理过程
P
D SOffset=0
D D
id1 T
integer
id2 T
float
Enter(id,T.type,offset)
Offset+=T.width
Enter(id,T.type,offset)
Offset+=T.width
T.type=integer
T.width=4
T.type=float
T.width=8
Offset:0
没有变量
Offset:4
id1:integer
Offset:4
id1:integer
id2:float
过程说明的翻译
过程说明的翻译工作主要包括：
– 为过程建立标识符表。
– 处理过程嵌套而引起的作用域问题。
主要方法：
– 每个过程有一个标识符表；
– 过程的嵌套用标识符表的栈 tblptr来表示。栈 tblptr中有统计表中的所有变量所占的内存长度，当推出过程的时候，需要将栈指针减小相应长度。
– 每个过程都有自己的地址空间，相对地址从 0开始。
用栈 offset存放当前过程可用的栈的初始地址。
过程说明的翻译方案重写规则 语义动作
P::=MD {addwidth(top(tblptr),top(offset));
pop(tblptr);pop(offset)}
M::=空 {t=mktable(NIL);
push(t,tabptr);push(0,offset)}
D::=D1;D2
D::=proc
id;ND1;S
{t:=top(tblptr);addwidth(t,top(offset));
pop(tblptr);pop(offset);
enterproc(top(tblptr),id.name,t)}
扫描结束；
退出栈。
扫描过程之前，建立新的标识符号表和 offset栈将当前表纪录到上个表（其父过程的表）中间去。
D::=id:T; {enter(top(tblptr),id.name,T.type,top(offset));
top(offset)+=T.width}
N::=空 {t:=mktable(top(tblptr)); push(t,tblptr);
put(0,offset)}
过程说明翻译方案的解释
在进行扫描之前，建立初始的 tblptr栈和
offset栈,M::=空 对应的语义动作。
进入每个过程说明的时候，建立一个新的表格,N::=空 对应的语义动作。
每个过程说明扫描结束的时候，消除空栈，并且将过程的符号加入到其父过程的符号表中去。
过程说明符号表的例子
Header(4)null
a array 0
x int 40
readarray
exchange
quicksort
Header(0)父
Header(4)
k int 0
v int 4
readarray
i int 0
Header(4)
纪录类型说明的翻译
在处理记录类型的说明的时候，首先需要知道各个域的名字，
类型，和该域的偏移量。
如果考虑到记录类型的嵌套，那么可以和过程的说明类似处理。都建立符号表。
T::= struct L D end {T.type,= record(top(tblptr));
T.width:=top(offset);
pop(tblptr);pop(offset)}
L::=空 {t:=mktable(null);
push(t,tblptr); push(0,offset)}
目标代码的生成
代码生成程序
– 输入时源程序的中间表示形式，输出为和源程序等价的目标代码。
目标代码可以有不同的形式：
– 目标机器代码形式；
– 汇编语言程序形式；
– 虚拟机目标代码形式；
目标代码生成的有关问题
目标机器语言的确定：确定目标代码的形式，目标机，和目标语言。也可以使用一些中间表示方式，比如三元式，四元式等。
语言结构目标代码的确定：确定语言中的各类语言结构和目标代码结构之间的对应关系。
运行时刻存储管理：程序运行的时刻，需要为变量分配存储空间。在编译时刻可以确定变量所需要的空间，和偏移地址。
而实际的地址要等到运行时刻才可以确定。
寄存器分配：合理利用寄存器可以使得程序运行效率比较高。
求值顺序的选择：
代码生成程序的设计：
虚拟机
虚拟机的设立包含了一般计算机的特征，但是比较简单。
方便学习编译程序的书写。
按照字节编址,4个字节为一个字。
有 n个通用寄存器。
指令形式为 OP 源，目标，表示将源和目标地址中的数据计算后存放到目标地址中。
绝对地址 M M 1
寄存器 R R 0
变址 D(R) D+contents(R) 2
间接寄存器 *R contents(R) 1
间接变址 *D(R) Con(D+con (R)) 2
立即数 #C 常数 C 1
虚拟机的指令集合
NEG T -con(T)=>T
SUB S T con(T)-con(S)=>T
MPY S T con(T)*con(S)=>T
DIV S T con(T)/con(S)=>T
CMP S T 比较 con(T)和 con(s)
Cjrelop T 按 relop为 true转向 T
ITOF S T 整型 con(S)转换为 float后存放到 T。
GOTO T 转向 T
RETURN 返回
CALL P,N 以 N个参数调用子程序 P
语句的翻译（赋值）
语法,V=e
语义：计算 e的值之后把值赋给变量 V。
执行的过程：
– 计算 V的变量地址；
– 计算右部表达式 e的值；
– 如果需要，对 e进行强制类型转换；
– 把转换过的 e值赋予 V的地址；
显然，一个赋值语句（赋值表达式）对应的代码由对应于上述 4个部分的代码组成。
对于每个表达式，它对应的属性应该包括：代码 code，
结果存放的地址 place。
赋值语句的翻译方案
S::=id:=E P:=lookup(id.name);//获取 id信息
if(p!=NIL) then
S.code = E.code | gencode(MOV,E.place,p->place)
else error
E::=E1+E2 E.place=newtemp;
E.code=E1.code||E2.code||gencode(MOV,E1.place,E.place)
||gencode(ADD,E2.place,E.place)
E::=E1*E2 E.place=newtemp;
E.code=E1.code||E2.code||gencode(MOV,E1.place,E.place)
||gencode(MPY,E2.place,E.place)
E::=id p:=lookup(id.name);
if(p!=null) {E.place=p->place; E.code=空 }
赋值语句中的类型强制
当赋值语句的左右两边类型不同却相容的时候，应该进行类型强制。
{p=lookup(id.name);
if(p!=null) then
{ S.code=E.code;
if(p->type ==int and E.type==int)
S.code=S.code||gencode(MOV,E.place,p->place)
else if (p->type=real and E.type=int)
{u=newtemp; S.code= S.code||gencode(ITOF,
E.place,u)||gencode(MOV,u,p->place)}
else if … …
变量的存取
当赋值语句的左部不是简单变量的时候，代码中，计算左部地址的部分比较复杂。
主要需要讨论的是：
– 下标变量的翻译方案
– 域变量的翻译方案下标变量的计算方法
对于一维数组 T a[num]，其第 i(从 0开始计算）个元素的地址是 base+i*sizeof(T)
对于二维数组 T a[num1][num2]，元素 a[i][j]的地址和数组的分配相关。假设，数组元素按行存放，那么
a[i][j]的地址是 base+(i*num2+j)*sizeof(T)。
对于多维数组 Ta[n1][n2]…[nm],其元素 A[i1,i2,…im]
的地址是,
– base+i1*n2*…*nm+i2*n3*…*nm+…+im 。
赋值左部的语法修改成,V::=Elist]|id，
Elist::=Elist,E|id[E。
下标变量的计算方法 (续 )
E::=V
{if (V.atag==0)/*不是数组 */ …...
else{ E.place = newtemp;
E.code = V.code ||gencode(’MOV 0(V.place),E.place)}
}
V::= Elist]{V.place=newtemp; V.tag = 1; V.code =
Elist.code || ‘MOV’,sizeof(T)存放处,V.place ||MPY
Elist.place,V.place) || ADD Elist.array的零地址 V.place
V::=id{p=lookup(id.name);V.place=p;V.atag=0}
注：类型 T和零地址存放处在 Elist.array中可以得到。
下标变量的计算方法 (续 )
Elist::=Elist1,E {t=newtmp; i:=Elist1.dim+1; Elist.code:=
Elist1.code || E.code || MOV,Elist1.array第 i维上界存放处,t
|| MPY Elist1.place,t || ADD E.place;
Elist.array = Elist1.array; Elist.place=i;
Elist.dim = i;}
Elist,:= id[E {p=lookup(id.name); Elist.place = E.place;
Elist.dim = 1; Elist.code = E.code; Elist.array = p;}
属性说明：
– Elist.array包含了这个数组的信息。
– Elist.dim表示当前已经扫描到了第几维。
– Elist.place最终存放了偏移量（以 sizeof(T)为单位 )，在其它时刻，
扫描到第 m维时生成的代码使 (((i1*num2 + i2)*num3+…)*numm) 存放在 Elist.place中。
下标变量计算的例子
B[j,m],V
E.list ]
id
E
[
E.list
E
Name=B place=j
place=j,dim=1,
array=A,code=‘’
place=m
place=t1,dim=2,
array=A,code=(1)
Place=t2,code=(1)(2)
MOV A的第 2维上界 t1
MPY j t1
ADD m t1
MOV sizeof(int) t2
MPY t1 t2
ADD B的零地址 t2
域变量的翻译方案
在说明记录（结构）类型的时候，已经记录了各个域的偏移量，因此，域变量的地址的计算只需要查找各个域的偏移量就可以完成。
V::=E.domainname{V.place = newtmp;
offset = LOOKUP_st(E.type,domainname)
V.code = E.code || MOV E.place,V.place ||ADD
const(offset) V.place
选择语句的翻译
语法,S::= if (E) S1 else S2; | if(E) S1;
语义：如果 E的值为 true，那么执行 S1；否则执行 S2（情况 1）
或者不执行（情况 2）
代码模式：（ E为真的时候跳转）
– E的目标代码
– 判别 E值的代码
– E值为 true时转向 E.true的代码
– 转向 E.false的代码
– E.true,S1的目标代码
– 转向 E.next的代码
– E.false,S2的代码
– S.next,后继语句的代码代码的例子
If (a<b) max = b else max = a;
MOV a,R0; CMP R0 b;
CJ< L1
GOTO L2;
L1:MOV b R1; MOV R1 max;
GOTO L3;
L2,MOV a R1; MOV R1 max;
L3:
语法制导的语义定义
S::= if (E) S1 then S2
{E.true=newlabel();
E.false=newlabel();S1.next=S.next;
S2.next=S.next;(方案中斜体部分应该在 if后面 )
S.code = E.code || CMP E.place #1 || CJ=,E.true ||
GOTO E.false || ‘E.true:’ || S1.code || GOTO
S1.next || ‘E.false:’ || S2.code || ‘S.next:’
}
布尔表达式的翻译（基本方式）
E::= E1 OR E2 {E.place = newtmp;
E.code=E1.code || E2.code || MOV E1.place,
E.place || OR E1.place E.place}
E::= id1 relop id2 {E.place = newtemp; t:=
newtemp; E.code = MOV id1.place,t || CMP t,
id2.place || Cjrelop t,*+8 || GOTO *+12 || MOV
#1 E.place || GOTO *+8 || MOV #0 E.place
这里假定每个指令长度为 4，所以 goto *+8表示跳转到指令下面 2条指令。
基本方式的代码例子
a<b OR c>d代码如下：
MOV a,t2; CMP t2,b;
CJ< *+8; GOTO *+12;
MOV #1 t1; GOTO *+8;
MOV #0 t1; MOV c t4
CMP t4,d; CJ> *+8
GOTO *+12; MOV #1,t3
GOTO *+8; MOV #0 t3;
MOV t1 t5; OR t3 t5;
布尔表达式的翻译（高效方式）
显然，对于一个布尔表达式来说，有时不需要计算全部表达式就可以得到值。比如 E1 OR E2，如果 E1
的值为真，那么整个表达式的值也是真。
可以仅仅使用一个 MOV #1（ #0） E.place语句，当表达式的值为真（假）的时候，转向这个语句。而对于用于控制的表达式，直接转向‘真’的分支。
注意：因为表达式可能有副作用，布尔表达式怎么翻译需要根据语言的语义来决定。比如
– if (E1 OR f()) S1，使用基本方式的时候,f()一定会被执行，
但是使用高效方式的时候,f()可能不执行。
– 一般语言的语义定义都使用高效方式。
布尔表达式的语义规则
E::= E1 OR E2
– E1.true = E.true; E1.false=newlabel;
– E2.true = E.true; E2.false = E.false;
– E.code = E1.code||gencode(E1.false,‘:’)||E2.code
E::=id1 relop id2
– t=newtemp;
– E.code = MOV id1.place,t || CMP t,id2.place || Cjrelop
E.true || GOTO E.false
E的属性 true和 false分别表示如果 E的值为真和假的时候，程序执行的下一步。
这是语义规则，所以 E1的继承属性 true在后面定义。
例子
a<b OR c>d的代码：
MOV a,t1; CMP t1,b;
CJ< E.true;
GOTO L1;
L1,MOV c,t2;
CMP> E.true; GOTO E.false
对于 if (a<b OR c>d) S1 else S2,E.true和 E.false分别是 S1和
S2的标号。
对于 id = a<b OR c>d,E.true和 E.false分别是 MOV #1 id和
MOV #0 id的标号。
回填技术
if (a<b) max=b; else max = a;
MOV a R0; CMP R0 b; CJ<?
如果使用一趟扫描方式，显然，当要生成 CJ<?
指令的时候，不知道该指令需要转向哪里。
可以使用回填技术解决：
– 先生成一个指令坯，不填入转移目标；把这个指令的相关信息保存好，当可以得到转移目标的时候，在把目标填入这个位置。
Backpatch函数,把第一个参数里面的所有地址对应的指令中的转移目标都设置为第二个参数。
条件语句的翻译方案（回填）
S::=if (E) M1 S1 N ELSE M2 S2
– {backpatch(E.truelist,M1.pos); backpatch(E.falselist,
M2.pos); S.nextlist = merge(S1.nextlist,S2.nextlist);
S.nextlist=merge(S.nextlist,N.nextlist);}
M::=空 {M.pos=nextpos}
N::=空 {N.nextlist=makelist(nextpos); emit(‘GOTO’,‘_’);}
E::=E1 OR M E2{backpatch(E1.falselist,M.POS),
E.truelist = merge(E1.truelist,E2.truelist);
E.falselist=E2.falselist;}
回填的例子
a<b OR c>d AND e=f
E
E OR M E
E AND M Ea<b 动作 1 动作 2
c>d 动作 3 动作 4
e=f 动作 5
动作 6
MOV a t1
CMP t1 b
CJ< _
GOTO _
MOV c t2
CMP t2 d
CJ> _
GOTO _
MOV e t3
CMP t3 f
CJ> _
GOTO _
情况语句 (switch?)
语法,
CASE E of
case C1,S1;
case C2,S2;
….
Default Sn
end
语义：根据 E的值，执行相应的分支；如果 E的值等于 Ci，那么执行 Si。
情况语句的执行步骤
步骤 1：计算表达式 E的值
步骤 2：在情况表中顺序寻找和 E的值相同的值。如果找不到，则和缺省值匹配。
步骤 3：执行和该值相关的语句，然后执行后继语句。
情况语句的目标代码设计
（方案一）
计算 E的值并存放在 t的代码
如 t!=C1则转向 L1的代码。
语句 S1的代码。
转向后继语句的代码。
L1：如 t!=C2则转向 L2的代码。
语句 S2的代码。
转向后继语句的代码。
L2,… … …
… … … …
Ln-1：语句 Sn的目标代码。
Next：后继语句的目标代码。
情况语句的目标代码设计
（方案二）
计算 E的值并存于 t的目标代码。
转向测试 (test)的目标代码。
L1：语句 S1的目标代码。
转向后继语句的目标代码。
L2：语句 S2的目标代码。
转向后继语句的目标代码。
L3,… … … …
… … … …
test,如 t=Ci则转向 Si的代码。
Next:后继语句的代码。
翻译方案的设计
S::= switch E CaseList DefaultS end
{APPENDCODE(CaseTestCode(CList.PosList,CList.ValueList,
DefaultS.Pos));
}
CList1,:=
C,{pos=nextPos(); Clist1.PosList+=pos;
Clist1.ValueList+=C.lexvalue;}
S{APPENDCODE(S.code) }Clist
上面的方案不一定准确，只是表示一个大概思路。
迭代语句的翻译
语法,while E do S
语义：当 E的值为真的时候，重复执行语句 S，
直到 E的值为假。
执行步骤：
– 步骤 1：计算 E的值。
– 步骤 2：判断 E的值，如果为 true，则执行 S，
然后返回步骤 1。
– 步骤 3：如果 E的值为 false，转向执行当语句的后续语句。
迭代语句的代码设计
L,计算表达式 E的目标代码。
判别 E的值，并且当其值为 false时，
转向后继语句 (NEXT)的目标代码。
语句 S的目标代码转向标号 L的目标代码。
NEXT：后继语句的目标代码。
代码例子
While n<10 do n=n+1;
L1,MOV n,r0
CMP r0,#10
CJ< L2
GOTO L3
L2,MOV n,r1
ADD #1,r1
MOV r1,n
GOTO L1
L3:
迭代语句的语义规则
S::= while E do S
规则如下：
– S.begin = newlabel();
– E.true = newlabel(); E.false = S.next;
– S1.next = S.begin;
– S.code = S.begin,||E.code || E.true,|| S1.code ||
goto S1.next;
请注意 E的代码是按照高效的方案实现的，
所以 E的代码后面不需要判断转向的代码。
迭代语句的翻译方案（回填）
S::= while M1 E do M2 S1
{backpatch(S1.nextlist,M1.pos);
backpatch(E.truelist,M2.pos);
S.nextlist = E.falselist;
emit(goto,M1.pos)}
M::=空 {M.pos = nextpos}
复合语句的回填方案
S::= begin L end{S.nextlist = L.nextlist}
L::=L1; M S {backpatch(L1.nextlist,
M.pos); L.nextlist:=S.nextlist;}
L::=S{L.nextlist = S.nextlist}
过程调用
过程调用时，程序转向执行另外一段代码，
执行完毕后，返回原来的执行点继续往下执行。正确的过程调用必须保证：
– 程序的控制能够正确地转移到被调用的过程。
– 被调用者能够正确地从调用者哪里获取数据。
– 被调用者能够把处理结果返回给调用者。
– 同时，控制能够返回到调用的地方继续执行。
上述 4条中,1,4是控制联系,2,3是数据联系。
数据联系
数据联系的内容包括：
– 寄存器的内容在调用前后不被破坏。
– 实在参数的正确传递。
– 被调用过程局部变量的分配。
– 非局部变量的正确引用。
活动记录
过程（函数）体的每次执行称为该过程
（函数）的活动。
活动记录是为了管理过程的一次执行
（活动）中所需要信息的连续存储区域。
所有的活动记录被放在一个栈里面。活动记录在过程被调用的开始建立并压栈，
在过程执行结束之后出栈。
活动记录的结构
返回值：用来存放被调用过程返回给调用者的值。
实在参数：存放调用者传递给被调用者的实在参数。
访问链：存放用于引用其它活动记录中的非局部数据。
机器状态：保存临调用时的机器状态。
局部数据：过程的局部变量存放地点。
临时数据：存放执行时产生的中间结果。
活动记录的大小根据各个被调用过程决定。一般来说，在编译时刻就可以确定活动记录的大小。
返回值实在参数控制链机器状态局部数据临时数据访问链调用者和被调用者的衔接
调用者：
– 计算实在参数；把返回地址和自己的活动记录指针存放到被调用过程的活动记录。
被调用过程：
– 保存寄存器和其它的机器状态。
– 初始化局部数据，开始执行过程。
– 把返回值存放在活动记录中。
– 使用活动记录中的相应信息，恢复 top_sp和其它寄存器，返回控制。
调用者：
– 把返回值复制到自己的活动记录中去。继续执行。
过程（函数）调用语句
语法：
– call id(Elist)
语义：
– 建立形式参数和实在参数的对应关系后，执行被调用过程的过程体。
过程语句的执行
为被调用者的活动记录分配存储区域
计算过程调用中各个实在参数的值，并把值存放在到相应的位置。
设置环境指针（访问链）等，使得被调用过程可以访问外围数据。
保护交用过程的机器状态，包括寄存器状态。
初始化被调用过程的局部数据。
控制转移到被调用过程的入口处。
目标代码设计
过程调用入口和出口部分的处理可以调用入口子程序和出口子程序来完成。
代码模式如下：
– 计算实在参数 p1的值的代码
– param p1
– … …
– 计算实在参数 pn的值的代码
– param pm
– call P m
翻译方案
S::=CALL id(Elist)
– {S.code = Elist.code || ‘CALL id.place,Elist.number}
Elist,:= Elist1,E
– {Elist.code = Elist1.code || E.code || PARAM E.place;
Elist.number = Elist1.number + 1;}
Elist::= E
– {Elist.code = E.code ||PARAM E.place; Elist.number = 1}
缺陷：
– call P(…,f(x),…)
– 由于 PARAM的功能时将数据拷贝到被调用者的活动区域。
在上述的例子中,f(x)对应的 PARAM指令会和 P对应的指令混淆。
改进后的翻译方案
申请临时空间存放实在参数，用队列数据结构记录各个参数的存放位置。在计算完成之后一次性复制到新的活动记录。
S::=CALL id(Elist)
{count = 0; while not emptyQ(Elist.q) do
{ t=headQ(Elist.q); S.code = S.code || PARAM,t Count:=count +1;}
S.code = S.code || CALL id.place,Count;
}
Elist::=Elist1,E{EnterQ(E.place,Elist.q)}
Elsit::=E { Elist.q = CreateQ(); Enter(E.place,q)}
参数的传递
值调用
– 值参数的形式参数被当作过程的局部变量看待，存储区域在被调用者的活动记录中。
– 调用者计算实在参数的值，并把该值送入相应位置。
引用调用
– 如果参数时变量，传送给形式参数的实际上时参数的地址。
– 如果参数时常量或者表达式，首先给这些值分配临时存储区域，然后把这个区域的地址传送给被调用者。
– 在被调用的过程中，对于参数的使用通过间接的方式实现。
比如 swap(x,y)中,x,y为引用调用时,x=1的操作为向 x中的值存放
过程内部的语句可以使用到非局部的变量。在 pascal语言中，这种情况比较复杂。
F()
{int x,y
f1()
{int i,j; j=x;}
f2()
{
call f1();
}
call f2();
}
非局部数据的存取
F的活动记录
F2的活动记录
F1的活动记录
F1中调用 x时，对应的是在 F的活动记录中的 x.需要根据访问链向上寻找。
显示表
显示表是活动记录的指针数组 d，第 i个元素表示嵌套层次为 i的过程对应的活动记录的位置。
显示表的维护：当为（正文静态）嵌套深度为 i的过程的活动记录的时候，把 d[i]保存在活动记录中，并把 d[i]设置为当前活动记录。退出某个活动记录的时候，恢复 d[i]
为原来保存的值。
显示表的使用：当要使用嵌套层次为 i的变量时，由 d[i]得到该活动记录。根据该变量的偏移量，就可以得到该变量的地址。
显示表的内容时根据正文嵌套关系定的，和具体的调用关系没有多大关系。
在 C语言中，由于不需要考虑函数的嵌套定义，所以非局部变量就是全局变量。不需要考虑显示表。
显示表的例子
F的活动记录
F2的活动记录D[0]
D[1]
D[0]
D[1]
F的活动记录
F2的活动记录
F1的活动记录源程序的中间表示
优点：
– 和具体的机器特性无关，有利于重定目标。
– 可以对中间表示进行优化，提高代码质量。
– 可以分解程序的复杂性。
抽象语法树
通常的语法规则中，有些符号起到了解释作用。比如 S::= if (E) S1 else S2中,if,
else等的作用就类似于标点符号。一般，
关键字就类似于标点符号。
如果我们抛弃掉这些标点符号，就得到了抽象的语法规则：
– 选择语句 表达式 语句 语句抽象语法树的例子
x = a+b*c
assign
x +
a *
b c
S
V = E
E E+
E E*
b c
a
x
产生抽象语法树的语法制导定义重写规则 语义规则
S::=id=E
E::=E1+T
E::=T
T::=T1*F
T::=F
F::=(E)
F::=id
F::=num
S.nptr:=mn(assign,ml(id,id.entry),E.nptr)
E.nptr=mn(‘+’,E1.nptr,T.nptr)
E.nptr=T.nptr
T.nptr=mn(‘*’,T1.nptr,F.nptr)
T.nptr=F.nptr
F.nptr = E.nptr
F.nptr = ml(id,id.entry)
F.nptr=ml(num,num.lexval)
逆波兰表示方法
逆波兰又称为后缀表示方法，是表达式的一种表示形式。
在逆波兰表达式中，运算符写在分量后面。
a+b*c/(d+e)的逆波兰表示为 abc*de+/+
定义：设 E是表达式，那么
– 如果 E是变量或者常量,E的逆波兰表示为 E
– E1 OP E2 ==> E1’ E2’ OP，其中 E1’,E2’ 为
E1,E2的逆波兰表示。
– (E) ==> E’
逆波兰表示的生成（翻译）
E::=E1+T {printf(+)}
E::=T
T::=T1*F {printf(*)}
T::=F
F::=(E)
F::=id {printf(id.name);}
逆波兰表示方法的扩充
逆波兰表示可以被扩充到表达式以外的地方。
赋值语句,V=e ==> V’e’ =
赋值语句的例子：
– t=(a+b)*c/(d-e)
– tab+c*de-/=
条件语句的逆波兰表示
if (e) St else Se
e’ N1 GOF St’ N2 GO Sf’
N1和 N2是逆波兰表示中符号的序号。
GOF表示按假转,GO表示无条件转。
例子,if (a<b) max=b else max=a
1
a
11
max
3
<
4
11
5
GOF
6
max
7
b
8
=
9
14
10
GO
2
b
12
a
13
=
扩充后的逆波兰表示
GOTO N ==> N GOL
GOL表示无条件转向标号
复合语句,S1;S2 ==> S1’S2’
例子：
– {i=1; next,f=f+1; if (i>f) i=2 else goto next;}
– i 1 = next,f f 1 + = i f > 20 GOF i 2 = 22 GO
next GOL
迭代语句的逆波兰表示
while (e) S; ==> e’ N1 GOF S’ 1 GO
例子,
– wile (i<100) {j = j+i}
– i 100 < 13 GOF j j i + = 1 GO
从逆波兰表示生成代码
算法框架,
– 设立运算分量栈。
– 从左到右扫描逆波兰表示。扫描到运算分量栈的时候，将该分量入栈。扫描到运算符的时候，根据该运算符号的个数，对运算分量栈中相应个数的栈顶元素生成相应的目标代码；从分量栈中退出相应个数的分量；把存放运算结果的临时变量压栈。
– 重复第二步，直到扫描完表达式中的所有符号。
从逆波兰表示生成代码（例子）
If (a<b) max = b else max = a
a b < 11 GOF max b = 14 GO max a,=
MOV a R0
CMP R 0 b
CJ< *+8
CJ>= ____
MOV b R1
MOV R1 max
GOTO ____
MOV a R2
MOV R2 max
四元式序列
表示方法：
– 元算符 运算分量 运算分量 结果
– 运算分量可以是变量，常量，或者由编译程序引进的临时变量。
例子：
– a+b*c
– * b c t1
– + a t1 t2
四元式
单目运算符 op x
– OP X _ T
赋值语句,x = y;
–,= y _ x
间接赋值,*x = y;
– &= y x x
转向指令,GOTO L(L为标号）
– GOL L _ _
四元式
按照关系 relop比较按真转：
– relop x y L
无条件转移到序号 L(L为四元式序号 )
– GO L _ _
过程调用,p(x1,x2,…,xn)
– PARAM x1 _ _
– PARAM x2 _ _
– …
– PARAM xn _ _
– CALL p n _
四元式
份程序复合语句的开始与结尾：
– BLOCK _ _ _
– BLOCKEND _ _ _
将数组 A的第 i个元素的地址存放到 t:
– []= A i t
将数组 A的第 i个元素存放到 t:
– =[] A i t
A[i] = B[j]
– []= A i t1
– =[] B j t2
– &= t2 t1 t1
四元式序列的例子
max=a[1]; i=2;
while(i<=n)
{ if(a[i]>max) max = a[i]; i=i+1; }
=[] a 1 t1
= t1 max
= 2 i
> i n (12)
=[] a i t2
<= t2 max (9)
=[] a i t3
= t3 max
+ i 1 i
= t4 i
GO (4)
生成四元式的翻译方案
生成四元式的方案和前面的直接生成代码的方案是类似的。
S::= id=E{p=loopup(id.name);
if(p!=NULL) genquad(‘=’,E.place,‘ ’,p->place)
else error();
E::=E1+E2
{E.place = newtmp;genquad(‘+’,E1.place,E2.place,E.place)}
E::=id{p=lookup(id.name);if (p!=null) E.place=p->place;
else error();}
从四元式到代码
一般来讲，四元式的运算符都有对应的机器指令，或者对应的子程序，因此从四元式生成指令代码是容易的。
主要考虑的问题是运算分量和计算结果的存取问题。主要考虑：运算分量在内存中还是四元式中，在寄存器中时以后是否可以被使用等。
例如,- x y z对应的代码：
– 如果 x,y的值分别在 Ri和 Rj中且以后不需要引用 x，那么指令为,sub Rj Ri，寄存器 Ri中包含 z的值。
– 如果 x在 Ri中，而 y在内存单元,SUB y Ri
– 如果 x的值以后还需要被使用，或者 x,y都在内存中，或者其中有常数，指令的生成还要作相应的变化。
基本块
定义：基本块时这样的一个四元式序列，其控制流从第一个四元式进入，而从最后一个四元式离开，期间没有停止，也没有分支。
例如：
– * a z t1
– * a t1 t2
– * b b t3
– * b t3 t4
– - t2 t4 t5
基本块划分算法
算法 6.1
步骤 1：确定入口四元式：
– 第一个四元式是入口四元式。
– 由条件转移或无条件转移四元式转移到的四元式是入口四元式；
– 紧跟在条件转移或者无条件转移四元式后面的四元式是入口四元式。
步骤 2：对于每个入口四元式，它所对应的基本块是从该四元式（含）开始，到下一个入口四元式（不含）
或者四元式结束的全部四元式组成。
基本块划分的例子
入口四元式,1,4,5,12
基本块,1-3,4,5-11,12
= 1 i
= 1 f
= 0 a
>= i (12)10
= f b
+ f t1a
= t1 f
= b a
+ i t21
= t2 i
GO (4)
= f fib
代码生成算法
假定：每个四元式运算符都由相应的指令代码，并要求计算结果尽可能保留在寄存器中（为提高效率）。
算法输入：四元式；输出：目标代码
数据结构：
– 寄存器描述符：记录寄存器当前存放了哪个变量的值。一个寄存器可以存放一个或者多个的值。
– 地址描述符：记录每个名字的当前值的存放处所，
可以是寄存器，内存地址，或者它们的集合（当值被赋值传输的时候）。
寄存器描述符和地址描述符的例子
四元式
– + a b t1
– = t1 x
代码：
– MOV a r0
– ADD b r0 r0包含 t1 t1在 r0中
– MOV r0 x r0包含 t1,x x在 r0和存储字中。
算法
对于每个四元式 op x y z完成下列动作：
– 调用 getreg()，确定 x op y的值的存放地址 L,L通常是寄存器。
– 查看地址描述符，确定 x的当前的一个位置 x’。如果
x的当前值既在内存，又在寄存器中，选择寄存器作为 x’。如果 x’不是 L，生成指令 MOV
x’ L。
– 生成指令,op y’ L，其中 y’是 y的当前值所在
（寄存器优先）。修改地址描述符，指明 z在 L中。
如果 L是寄存器，修改寄存器描述符号，指明 L中包含了 z的值。
算法（续）
如果 x和 /或 y的值此后不再使用，并且在寄存器中，则修改寄存器描述符，只是这些寄存器中不再包含 x和 /或
y的值。
处理单目运算的四元式时，和上面的方法类似。但是对于 = x _ y四元式，如果此时 x的值在某个寄存器中，那么不需要生成代码，只需要用寄存器描述符和地址描述符指明 y的值也在该寄存器中即可。
当基本块处理完毕之后，如果有些值可能在其他基本块被使用，并且地址描述字表示这些值仅仅存放在寄存器中。那么我们需要生成将这些值存放到内存中的指令。
算法 (getreg)
如果 x的值在寄存器中，此寄存器不包含其他名字的值，
并且 op x y z之后，没有对 x的引用，则将该寄存器作为
L。修改地址描述符。
如果 1失败，并且由空闲寄存器的话，回送一个空闲寄存器作为 L
如果 2失败，并且 z在基本块中有下次引用，或者 OP必须使用寄存器，那么寻找一个被占用的寄存器 R，用 MOV
R M指令将 R的值存入相应的内存单元，修改地址描述符。如果 R中存放了多个值，需要生成多个 MOV指令。
把 z的单元作为 L。
例子
X=(a-b)*(a-c)+(a-c)
1) - a b t1 2)- a c t2
3)* t1 t2 t3 4)+ t3 t2 t4
5)= t4 x
MOV a,R0; SUB b R0 (R0包含 t1,t1在 R0中 )
MOV a R1; SUB c R1 (R1包含 t2,t2在 R1中 )
MPY R1 R0 (R0包含 t3,R1包含 t2 t2在 R1中,t3
在 R0中）
ADD R1 R0 (R0包含 t4,t4在 R0中 )
MOV R0 x (R0包含 t4,x x在 R0和内存中,t4
在 R0中 )
不同的寻址方式
对于变址寻址和间接寻址，考虑四元式：
– =[] A i t
– = t _ a
i所在的位置确定了生成哪些指令。
– 当 i在寄存器 Ri中的时候，
MOV A(Ri),R
MOV R,a
– 当 i在内存中的时候，需要在前面添加指令
MOV Mi,Ri.
寻址方式（ 2）
考虑四元式：
– []= B i t
– &= b t t
假定有获取地址的指令 ADDR A,R
– ADDR B(Ri) R
– MOV b *R.
同样,i在内存的时候需要先生成指令
– MOV Mi Ri。
三元式
如果我们不明显给出四元式的结果部分，而是用四元式的编号来表示结果，那么我们可以得到三元式。形式如下：
运算符 运算分量 运算分量
和四元式的区别：
– 用序号表示结果,ADD (3) t
– 赋值运算是双目运算符,= x y
– 按假转中有两个运算参数,GOF (14) (4)
三元式例子
max=a[1]; i=2;
while(i<=n)
{ if(a[i]>max) max = a[i]; i=i+1; }
(1) =[] A 1
(2) = (1) max
(3) = 2 i
(4) <= i n
(5) GOF (14) (4)
(6) =[] A i
(7) > (6) max
(8) GOF (11) (7)
(9) =[] A i
(10) = (9) max
(11) + i 1
(12) = (11) i
(13) GO (4)
运行环境
在得到目标程序之后，程序的运行还需要一些运行时刻支持程序包的支持。
本章内容包括：
– 运行时刻存储分配以及支持。
– 符号表的管理。
– 运行时刻支持系统。
名字到存储字的结合
程序设计语言是基于冯,诺伊曼结构的。
变量仿效的是存储字，而赋值语句模拟的是计算机存取，运算操作。
在目标程序运行的时刻，必须要对源程序中的每一个量都分配相应的存储字。
分配是隐式进行的。在编译时刻就决定了这些变量应该如何分配，在运行时刻决定究竟分配到哪里。
环境和状态
环境是名字到存储字的映射，就是说：在程序的运行中的某个时刻，某个名字的变量究竟存放在什么内存的什么地方。
在不同的时刻，变量的存放位置不变。
一般在进入分程序和退出分程序的时刻，环境会改变。
状态是存储字到值的映射函数。
一般执行赋值语句的时候，状态会改变。但是环境不变。
例子
Main()
{ int x,y,t; t=x; x=y; y=t; }
当进入 main()函数的时候,x,y,t的存储字在活动记录中分配。
环境为,{(x,mx),(y,my),(t,mt)};
假设开始的时刻 x,y,t的值为 5,1,0，那么相应的状态为
{(mx,5),(my,1),(mt,0)}。
在执行了三个赋值语句之后，状态变成 {(mx,1),(my,5),
(mt,5)}
作用域和生存周期的问题
作用域是根据静态的源程序文本确定的。但是程序的运行是动态的。每个函数的调用的层次关系和正文的嵌套是不一致的。我们需要一个方法来确定在特定的运行时刻，某个名字对应的值存放在什么地方。
每个值都有生存周期。
– 全局变量的值在整个运行期间有效。
– 局部变量在函数退出之后就没有意义了。
– 由 new,或者 malloc确定的存储字中的值的意义直到相应的 delete和 free的语句执行过后才消失。
程序运行时刻的存储区域
分为代码段，和数据段。
数据段中分为静态数据，
栈和堆。
堆和栈的增长方向相反。
代码静态数据栈堆
存储分配策略
静态分配策略
动态分配策略
– 栈式分配策略
– 堆式分配策略静态存储分配
对于某些变量，在编译时刻就可以由编译程序为它们分配存储字。在运行时刻，这些变量和存储字的结合不变。
全局变量和静态变量。
不能处理的情况：
– 在编译时刻不能确定大小的变量。
– 要支持递归过程实现。
– 动态建立的数据结构。
栈式存储分配
在内存中开放一个栈区，当过程的一次活动开始的时候，把活动记录入栈。过程活动结束的时候，活动记录出栈。
过程的局部变量在活动记录入栈的时候和存储字结合，活动记录出栈的时候结合消失。
栈式存储的方式可以分成活动记录大小可以确定和活动记录大小不可确定两种。
栈式存储分配（记录大小确定）
引入两个指针（一般使用特定的寄存器存放）：
– top：指向运行栈的栈顶。
– top_sp：指向活动记录中机器状态域的末端。
在过程 p执行之前，把 top加上 l，在过程
p执行结束后，把 top减去 l。 Top_sp的值可以相应确定。
对于过程中的局部名字 x，假设它的偏移量为 dx，那么 x的地址可以表示为 -
dx(Rtop)。也可以写成 dx’(Rtop_sp)。
top
top_sp
机器状态
0
出 /入口子程序
使用一个寄存器 sp来存放栈顶指针。
入口子程序：
– ADD #caller.recordsize SP
– MOV #here+8,SP//保存控制返回地址
– GOTO callee.code_area
出口子程序：
– GOTO 0(sp);//callee执行。
– SUB #caller.recordsize SP//退栈，由 caller执行。
可变长度变量的存放
在安排活动记录的时候，首先安排的是在编译时刻就可以确定的域，比如：控制链，访问链，机器状态域等。这样可以使得安排可变长度的变量的时候可以不影响到这些域的位置。
可变长数组被安排在活动记录的顶部。并且在活动记录的局部数据区中另外存放可变长度数据的指针（长度可以预先确定）。
调用其他函数的时候,SP的增加值需要动态确定。
top
P
A的指针数组 a
其他局部变量堆式存储分配
有些数据对象是不适合安排在静态区或者栈区里面的。它们的生存期是难以确定的。比如：由 new生成的对象。这些对象生存期在 new语句执行后开始，
到 delete语句执行后结束。以下任何一种情况都必须使用堆式分配：
– 数据对象随机创建和消亡。
– 过程活动结束后，数据对象依旧需要保留。
– 被调用过程活动的生存期比调用过程更加长。
堆式分配中,只有当程序在运行中,正式要求撤销数据对象的时候,该对象才被释放,
堆式存储分配
堆管理的基本功能,
– 分配空间
– 释放空间
指针 (指引 )的管理：
– 当程序申请了一个空间之后，一般得到一个指针。该指针同时也是表示该空间的句柄。
– 如果已经释放了该空间，那么这个指针就没有意义了，称为悬空指针。
指针空间
对于每个申请的空间，都有长度限制。如果超出这个限制，会产生不可预测的错误。
C语言中的堆空间的分配一般如下：
管理信息 存储区域指针垃圾回收系统
有些程序设计语言（一般式面向对象的程序设计语言）没有显式的空间回收机制，而是使用垃圾回收系统。便于编写程序，但是效率较低下。
当没有指针指向某段空间的时候，系统就回收该空间。
数据对象的指针的拷贝时，需要记录指向该对象的指针数量。
4 运行时刻支持系统
运行时刻子程序是为了支持目标程序的运行而开发的一系列子程序。这些子程序的全体被称为运行时刻支持程序包。
面向用户的运行子程序
– 用户可以显式调用这些子程序。
对用户隐匿的运行子程序：
– 活动记录的存储分配，参数传递机制，机器状态的保护。
(第六章,语义分析和目标代码生成 )
南京大学计算机系赵建华概念
编译程序的作用是：将源程序转换为具有 相同效果 的可运行程序。
所谓 相同效果 就是程序的语义。
并不是所有满足语法规则的程序都是有意义的 (well-
form)的。
所谓语义分析，就是确定程序是有意义的，分析程序的含义，并做出相应的处理。
程序的含义包括：
– 数据结构的含义：和标识符相关联的数据对象。
– 控制结构的含义：由语言定义。规定了每个语句的执行效果。
基本功能
确定类型：确定标识符所关联的数据对象的数据类型。
类型检查：按照语言的类型规则，对运算及分量进行类型检查，必要时做出相应类型转换。
识别含义：根据程序设计语言的语义定义，确定各个构造部分组合后的含义，做出相应处理
（生成中间代码或者目标代码）。
其它静态语义检查：比如控制流检查，嵌套层数检查。
语义分析的输入输出
输入为前面语法分析的结果。
输出为中间表示代码 (抽象语法树，三元式 …) 。
– 把生成中间代码和代码生成分开，可以使难点分解。
– 对中间代码的分析比较容易，便于进行优化。
– 可以把编译程序分成机器独立部分和机器相关部分。
– 便于任务的分解，和开发人员的分组开发。
属性文法
对于某个压缩了的文法，当把每个文法符号和一组属性相关联，并把重写规则附加以语义规则的时候，就得到属性文法。
语法制导的翻译过程：由于属性文法的规则和重写规则是一一对应的关系。所以，由属性文法的确定的语义分析可以在语法分析的过程中进行。这个过程成为语法指导的翻译。
语法指导的定义 /翻译方案：语法指导的定义比较抽象，隐藏了实现细节，无需指明语义规则的计算次序。翻译方案则指明的计算次序。
语法制导定义的例子
对于语法符号 E,T,F，都确定了属性 val，表示它们的值。
如果一个重写规则中有两个相同的符号，需加足标区别。
在归约过程中，每个归约得到的符号都对应于输入符号串中的某一段。
L::=En Print(E.val)
E::=E1+T E.val = E1.val+T.val
E::=T E.val = T.val
T::=T1*F T.val = T1.val*F.val
T::=F T.val = F.val
F::=(E) F.val = E.val
F::=digit F.val = digit.lexval
语法制导定义的例子（ 2）
L的属性包括,in； T的属性值为 type
addtype表示将 id对应的类型信息加入到标识符表中。
D::=TL L.in = T.type
T::=int T.type,= integer
T::=real T.type,= integer
L::=L1,id L1.in,= L.in; addtype(id.entry,
L.in)
L::= 空属性的计算和注释分析树
在语法制导分析过程中，我们不仅生成了一棵语法树，
还可以得到各个结点的属性值。把这些值加入到语法树上面之后，就得到了注释分析树。
结点的属性值的计算过程有两种类型：
– 结点的属性由其子结点确定，称为综合属性。
– 结点的属性由兄弟结点和父结点的属性确定，称为继承属性。
在概念上，翻译过程如下：
– 1：分析输入符号，建立语法树
– 2：从语法分析树得到描述结点属性之间的依赖关系，得到计算次序。
– 3：按照语义规则计算属性值。
分析过程和注释分析树例子 (1)
L
E n
TE
T F
F
3
T
*
+
Lexval=3
val=3 5
val=5val=3
val=15
val=15
F
4 lexval=4
val=4
Val=4
Val=19
分析过程和注释分析树例子 (2)
D
T L
real,i3L
L,i2
i1
type=real in=real
in=real
in=real
属性文法
一个属性文法 AG是一个四元组 (G,A,R,C)，其中
– G是已经压缩的文法。
– A是有穷属性集合，对于每个文法符号 X，都有其属性集合 A(X)对应。
– R是有穷属性规则集合。对于规则 p,X0=X1X2…Xk,有规则 Xi.a=f(Xj.b,…,Xpk.c)。定义了在使用这个规则进行归约的时候,Xi.a的求值。
– C是有穷条件集合。 C(Xi.a,…,Xj.a) 表示规则 p必须满足的条件。只有这些条件满足的时候，输入的符号串才是有意义的。
语法制导定义的分类
S_属性定义：所有的文法符号的属性都是综合属性。
– 实际上是说：一个语法结构的属性由它的组成部分的属性确定。
– 例如：对于表达式的结果类型；
– 基于 S_属性定义的语法分析树可以用自底向上的方法得到。
– 规则 E::=E1+T对应的语法结构,E.type的值可以如下确定：如果 E1的类型和 T的类型都是 int，
那么结果也是 int,如果有一个是 real，那么结果类型是 real。,..
继承属性
语法分析树中，一个结点的属性由其父结点和兄弟结点确定。
– 反映了文法结构的属性对上下文的依赖特性。
– 比如：对于 C语言中变量的申明可以是如下方式，
TYPE v1,v2; 那么变量 v1,v2的属性值‘类型’是由 TYPE确定的，如果 TYPE是 float，那么它们的类型就是实数。
– 在前面的例子 6.2中，结点 T的属性 type是综合属性，
但是 D::=TL中,L的属性 in就是继承属性，这个属性的值是由 T的属性 type确定的。
依赖图
在语义规则中，假设某个属性的定义是 b=f(c1,c2,…,cn),
那么要求得属性 b的值，首先要计算出属性 c1,c2,…cn
的值。显然它们的计算顺序有一种依赖关系。
通常，我们可以在语法分析树中添加有向的箭头表示这种依赖关系。（对于过程调用，可以添加虚拟的属性）
在 语法分析树 中，如果属性 b依赖于 c，那么从 c对应的结点到 b对应的结点画一个箭头。
依赖图构造算法
步骤 1：构造语法树，对于语法树中的每个结点的每个属性，构造一个结点。
步骤 2：对每个树的结点 n，对该结点所相关的每个语义规则 b:=f(c1,c2,…,cn) 都如下添加有向弧：
– 从 c1,c2,…cn 的结点向 b对应的结点画有向弧。
实际上是对所有在建立语法树中所使用的规则都建立依赖关系。
依赖图的例子
real id1,id2,,id3
D
T L
L
L
id3
id2
id1
real
type
in
entry
vir
in vir
in vir
entry
entry
计算次序
显然，依赖图中指定了各个属性的计算顺序。
各个属性的计算顺序可以有多种，但是必须满足依赖图规定的拓扑次序。以保证在计算某个属性的值的时候，这个属性所依赖的属性值已经被计算出来。
用语法制导定义说明的翻译步骤如下：
– 构造语法分析树。
– 构造依赖图。
– 对依赖图的各个结点进行拓扑排序，得到计算次序。
– 按照上述次序计算属性的值。
比如，上面的图的计算顺序如下：
– a4=real,a5=a4,addtype(id3.entry,a5),...
其它得到计算次序的方法
避免在分析的过程中显式地构造分析树。
忽略规则：按照语法分析的归约（或者）推导程序完成属性的计算。
– 比如，当定义中只有 S_属性定义的时候，可以按照自底向上归约过程进行。
基于规则的计算次序：通过对重写规则和语义规则进行分析，确定和每个重写规则相关联的语义规则的计算次序。
翻译方案
语法制导定义基于属性文法，其计算次序被隐藏。
如果在进行语义定义的时候，陈述了一些实现的细节，我们称为翻译方案。
在翻译方案中，语义定义部分是用 {}包含的语义动作。并且语义动作可以出现在规则右部的任何地方。
这些语义动作的执行顺序是这样的。当建立了一个语法分析树之后（把语义动作也当作规则右部的结点加入到语法树中），我们按照深度优先的方法变例这个分析树。每次遍历到一个语义动作对应的结点的时候，执行这个动作，
计算相应的属性值。
L_属性定义是可以使用翻译方案计算的一类语义定义方式。
L_属性定义
L_属性定义：如果每个重写规则 U::=X1X2…X n对应的语义规则中的每个属性：
– 或者是综合属性，
– 或者是这样的继承属性：
Xj.a或者仅仅依赖于 U。
Xj.a依赖于 Xj左边的符号的属性。
S_属性定义也是 L_属性定义。
显然，对于 L_属性定义，其属性的值可以按照深度优先的次序计算。也就是说，可以直接地使用翻译方案实现。
L_属性定义的例子可以看关于变量申明的定义。
L_属性定义的属性计算
L_dfvisit(n)
{
for m=从左到右的 n的每个子节点 do
{
计算 m的继承属性；
L_dfvisit(m);
}
计算 n的综合属性。
}
翻译方案的例子
E::=TR
R::=addop T{print(addop.lexeme)}R1 | 空
T::=num{print(num.lexval)}
同时，翻译方案设计需要满足 L_属性定义。
E
T R
- T R
+ T R
2 Print(2) 空
Print(+)
5 Print(5)
Print(-)Print(9)9
翻译方案的设计
对于综合属性，只需要把属性的定义修改称为赋值语句，放在规则的最末尾就可以了。
存在继承属性的时候，必须满足一下条件：
– 重写规则右部符号的属性必须先于这个符号的语义动作中计算。
– 一个语义动作不能引用右边符号的综合属性。
– 重写规则左部的符号的综合属性必须在它所引用的所有属性都计算完成之后才可以计算。
错误的例子,S::=A1A2 {A1.in=1,A2.in=2} A::=a
{print(A.in)}.应该把 {A1.in=1}移到最前面。
L_属性定义总存在相应的翻译方案。
翻译方案的实现 (自底向上 )
S_属性定义的翻译方案可以在分析输入符号串的时候完成。
通过在栈中的每个符号添加一个属性项来完成。
在移入的时候，把文法符号的属性同时压栈。终结符号的属性在词法分析的时候获得。
归约的时候，除了进行原来的工作之外，需要根据重写规则和语义规则，根据栈顶部的符号属性计算出被归约得到的符号的属性值。
比如，如果需要按照 U::=XYZ归约，而相应的语义动作为 {U.a=f(X.x,Y.y,Z.z)}，那么栈顶部的符号为 ZYX，从这些符号的属性部分得到 X.x,Y.y和 Z.z就可以计算得到
U.a。当把 U压入栈的时候，同时把 U.a的值压入属性栈。
实例步骤 栈 规则输入
1
2
3
5
6
7
8
(#,-)(F,3)
(#,-)(T,3)(*,-)
(#,-)(T,3)(*,-)(5,5)
(#,-)(T,3)(*,-)(F,5)
(#,-)(T,15)
(#,-)
(#,-)(3,3)
*5+4n
*5+4n
5+4n
+4n
+4n
3*5+4n
*5+4n
F::=digit
9 (#,-)(E,15) +4n E::=T
F::=digit
10 (#,-)(E,15)(+,-) 输入
4 (#,-)(T,3) *5+4n T::=F
T::=T*F
非 S_属性定义的例子
D::= T{L.in = T.type} L
T::=int{T.type = integer}
T::=real{T.type = real}
L::={L1.in=L.in}L1,id{addtype(id.entry,L.in)}
L::=id {addtype(id.entry,L.in)}
L_属性定义翻译方案不能直接用自底向上的方法实现。
自底向上的方法
在 YACC中通过添加空规则来实现。比如第一个规则修改为 D::=TAL,A::=空，但是问题是：
可能变成非 LR(K)文法，并且，不能直接使用上面的定义。
比如,D::=T{L.in:=T.type}L，实现的方式实际是,D::=TAL,A::=空 {}。
但是，值的传递不是那么方便。
自顶向下的实现方法
可以按照前面 L_属性定义的计算算法计算的方法完成。
但是，需要消除左递归。消除左递归的时候，牵涉到语义规则的修改。
自顶向下的实现方法（例子）
E::=E+T|E-T|T T::=(E)|num
翻译方案如下：
– E::=E+T {E.val=E1.val+T.val}
– E::=E-T {E.val=E1.val-T.val}
– E::=T {E.val=T.val}
– T::=(E) {T.val=E.val}
– T::=num {T.val=num.lexval}
这个翻译方案中，所有的属性都是综合属性。
自顶向下的实现方法（例子）
由于自顶向下的方法不能处理左递归的情况，
所以必须修改相应的重写规则。而语义规则也需要相应的修改。
E::=T{R.i=T.val}R{E.val=R.s}
R::=+T{R1.i=R.i+T.val}R1{R.s=R1.s}
R::=-T{R1.i:=R.i-T.val}R1{R.s=R1.s}
R::=空 {R.s=R.i}
T::=(E{T.val=E.val})
T::=num{T.val=num.lexval}
实现程序（ 1）
E::=T{R.i=T.val}R{E.val=R.s}
S_attribute E(L_attribute)
{attribute E_val;
attribute T_val = T();
attribute R_i = T_val;
attribute R_s = R(R_i);
E_val = R_s;
}
实现程序（ 2）
R::=+T{R1.i=R.i+T.val}R1{R.s=R1.s}
R(attribute in)
{
GetSym();
attribute T_val=T();
attribute R1_i = in+T_val;
attribute R_s = R(R1_i);
return R_s;
}
消除左递归时翻译方案的修改
U::= U1Y {U.a=g(U1.a,Y.y)}
U::=X {U.a=f(X.x)}
修改为：
– U::=X {R.i=f(X.x)} R{U.a = R.s}
– R::=Y {R1.i=g(R.i,Y.y)} R1{R.s=R1.s}
– R::=空 {R.s=R.i}
引入新的符号 R，对于 R有继承属性 i。
R.i纪录了前面扫描过的 U的 a属性值。
关于语义定义的解释
U
U2
U1
X
Y2
Y1
U
R1
R2
X
Y2
Y1
R3
修改后的翻译方案的计算过程
R.i=6 R.s=6
E.val=6
T.val=9
num.lexval=9
R.i=9 R.s=6
- T.val=5
Num.lexval=5 + T.val=2
Num.lexval=2
R.i=4 R.s=6
类型体系
指明了程序中，运算的合法型和运算分量类型的一致性（相容性）；类型转换的规则等。
本部分说明如何使用翻译方案来实现类型的检查。
类型的获得（变量说明）由变量申明部分确定。
类型表达式
使用类型表达式来表示程序中可能出现个各种类型。
定义：
– 基本类型就是类型表达式。
– 对类型表达式命名的类型名时类型表达式。
– 类型构造符作用于类型表达式的结果时类型表达式。
数组,array(I,T)
卡氏积,T1?T2
纪录,record((N1?T1)? (N2?T2)?..,?(Nn?Tn))
指针,pointer(T)
函数,D1?D2?..,?Dn?R
– 类型表达式可以包含变量（如果允许类型重载）
类型表达式例子
int a[200]; array(0..199,int)
struct {int a[10]; float f}st;
record((a?array(0..9,int) )? (f?real))
int *a; pointer(int)
int f(int a,float f)
(int? float)?int
表达式类型的等价性
类型等价的定义可以分为结构等价和名字等价。
结构等价：两个类型表达式结构等价 iff
它们是相同的基本类型，或者它们是从同样的类型构造符作用于结构等价的类型。
名字等价：（如果允许类型命名）当且仅当它们相同。
结构等价的确定
BOOL testeq(s,t)
{ if(s和 t是相同的基本类型） return true;
if(s ==array(s1,s2) && t==array(t1,t2))
return testeq(s1,t1) && testeq(s2,t2);
if(s==s1?s2 && t==t1?t2)
return testeq(s1,t1) && testeq(s2,t2);
… … … …
return false;
}
名字等价的例子
变量和类型申明 (pascal)：
– TYPE link = ^cell; np = ^cell; neq=^cell;
– VAR next:link,last:link,p:np,q:nqr; r:nqr;
所有的变量在结构等价的意义下面都相同。但是在名字等价的情况下：
– next和 last相同； q,r类型相同；
– p和 next类型相同。
类型强制
一般的程序设计语言中都规定了某些类型之间的转换关系：比如说整数量可以被当作实数量参与运算，并且不需要程序员显式说明。
不同类型的常数在计算机中有不同的表示。当一个值需要转换称为其它类型使用的时候，需要使用某些代码进行转换。
因此，编译程序需要识别需要进行类型转换的地方，并相应地生成代码。
程序设计语言的设计者需要考虑什么情况下需要和可以进行转换。
类型强制转换的语义规则
首先，要确定强制转换的地方，首先需要确定参加运算的分量的类型，而这个分量本身就可能是一个表达式。
重写规则 语义规则
E::=num
E::=num.num
E::=id
E.type:=integer
E.type=float
E.type=gettype(id.entry)
E::=E1 op E2 if (E1.type=int && E2.type=int)
E.type = integer;
if (E1.type=int&&E2.type=float)
E.type = float;(E1的结果需要强制转换 )
… …
变量类型的确定
类型确定就是确定标识符代表对象的数据类型。在标识符的定义性出现的时候，要把标识符和类型相关联；
在标识符的使用性出现时，需要获取得到标识符相关联的类型。
假设说明部分的文法如下：
– P::=D;E D::=D;D | id:T
– T::=char | integer | ARRAY[num] OF T | ^T
处理说明部分的时候，需要做的语义处理是：对于每个说明 id:T，把 id和 T的类型表达式相关联。就是说，
将 id的类型为 T的信息纪录到标识符表中。所以，每次识别到 D::=id:T的情况时，需要调用 addtype(id,T.type)
变量类型的确定
D有一个虚拟的综合属性。 T有属性 type，
以后的作业和考试中，对于标识符有属性 entry，常量有属性 lexval
D::=D;D
D::=id:T
T::=char
T::=integer
T::=^T1
T::=ARRAY[num] of T
{addtype(id.entry,T.type)}
{T.type,= char}
{T.type = integer}
{T.type=pointer(T1.type)}
{T.type=array(num.lexval,T.type)
类型检查
类型检查可以分为动态和静态两种。
– 动态检查在运行时刻完成。功效很低。但是如果语言允许动态确定类型，动态检查是必须的。
– 静态检查在编译时刻完成。静态检查是高效的。
如果一个语言能够保证所有经过静态检查之后，程序没有运行时刻的类型错误，则称为强类型的。
类型检查的内容包括：
– 表达式
– 语句
– 函数表达式的类型检查
对于表达式的类型检查，主要的工作是检查参与运算的操作数是否可以进行相应操作。
重写规则 重写规则
E::=literal
E::=num
E::=E1 mod E2
E::=E1 [E2]
{E.type = char}
{E.type = integer}
{E.type = if (E1.type = integer &&
E2.type==integer) then integer else
type_error}
E::=id {E.type = gettype(id.entry)}
语句的类型检查
语句的类型检查主要包括,赋值语句 类型的相容性，控制表达式的结果类型检查。
先面的例子中，赋值语句要求左右两边类型相同；在 C
语言中，赋值类型相容性在表达式部分处理。
重写规则 重写规则
S::=id = E
S::=while E do S1
{S.type = if id.type == E.type
then void else type_error}
{S.type = if E.type = boolean then
S1.type else type_error}
S::= if E then S1 {S.type=if E.type = boolean
then S1.type else type_error
函数的类型检查
简化了的函数调用语法为 E::=E(E)；
类型检查所需要做的工作是：检查参数是否符合条件，并且确定函数结果的类型。
E::= E1(E2)
{E.type = if E2.type=s and E1.type=s?t then t
else type_error}
当函数有多个参数的时候，需要检查多个参数的类型。
实际的翻译方案还需要考虑类型的相容性问题。
说明部分的翻译
对于说明部分的翻译，需要考虑的问题包括：
– 标识符的类型纪录。
– 标识符对应的数据对象的地址分配。
– 标识符的作用域问题。
常量定义的翻译
常量定义的翻译主要工作是将常量标识符的信息纪录下来。
重写规则 语义动作规则
CDT::=CDT;CD
CD::=id=num {num.ord=lookCT(num.lexval);id.ord
=num.ord; id.type=integer;
id.kind=CONST; add(id.entry,id.kind,
id.type,id.ord)}
CDT::=CD
变量说明的翻译
变量说明的翻译工作包括：确定变量类型，分配地址空间。
地址空间的分配方式如下：有一个全局变量 offset，纪录了当前可用的空间的开始地址。每次分配一个变量的空间，将
offset增加相应的值。
有 static类变量时，必须
规则如下：
– P::={offset = 0}D;S D::=D;D
– D::=id:T {enter(id.name,T.type,offset); offset+=T.width}
– T::=integer {T.type=integer,T.width=8}
– T::=real {T.type=real; T.width=8}
– T::=ARRAY[num] of T1 {T.type=array(num.lexval,
T1.type); T.width=num.lexval*T1.width}
变量说明的处理过程
P
D SOffset=0
D D
id1 T
integer
id2 T
float
Enter(id,T.type,offset)
Offset+=T.width
Enter(id,T.type,offset)
Offset+=T.width
T.type=integer
T.width=4
T.type=float
T.width=8
Offset:0
没有变量
Offset:4
id1:integer
Offset:4
id1:integer
id2:float
过程说明的翻译
过程说明的翻译工作主要包括：
– 为过程建立标识符表。
– 处理过程嵌套而引起的作用域问题。
主要方法：
– 每个过程有一个标识符表；
– 过程的嵌套用标识符表的栈 tblptr来表示。栈 tblptr中有统计表中的所有变量所占的内存长度，当推出过程的时候，需要将栈指针减小相应长度。
– 每个过程都有自己的地址空间，相对地址从 0开始。
用栈 offset存放当前过程可用的栈的初始地址。
过程说明的翻译方案重写规则 语义动作
P::=MD {addwidth(top(tblptr),top(offset));
pop(tblptr);pop(offset)}
M::=空 {t=mktable(NIL);
push(t,tabptr);push(0,offset)}
D::=D1;D2
D::=proc
id;ND1;S
{t:=top(tblptr);addwidth(t,top(offset));
pop(tblptr);pop(offset);
enterproc(top(tblptr),id.name,t)}
扫描结束；
退出栈。
扫描过程之前，建立新的标识符号表和 offset栈将当前表纪录到上个表（其父过程的表）中间去。
D::=id:T; {enter(top(tblptr),id.name,T.type,top(offset));
top(offset)+=T.width}
N::=空 {t:=mktable(top(tblptr)); push(t,tblptr);
put(0,offset)}
过程说明翻译方案的解释
在进行扫描之前，建立初始的 tblptr栈和
offset栈,M::=空 对应的语义动作。
进入每个过程说明的时候，建立一个新的表格,N::=空 对应的语义动作。
每个过程说明扫描结束的时候，消除空栈，并且将过程的符号加入到其父过程的符号表中去。
过程说明符号表的例子
Header(4)null
a array 0
x int 40
readarray
exchange
quicksort
Header(0)父
Header(4)
k int 0
v int 4
readarray
i int 0
Header(4)
纪录类型说明的翻译
在处理记录类型的说明的时候，首先需要知道各个域的名字，
类型，和该域的偏移量。
如果考虑到记录类型的嵌套，那么可以和过程的说明类似处理。都建立符号表。
T::= struct L D end {T.type,= record(top(tblptr));
T.width:=top(offset);
pop(tblptr);pop(offset)}
L::=空 {t:=mktable(null);
push(t,tblptr); push(0,offset)}
目标代码的生成
代码生成程序
– 输入时源程序的中间表示形式，输出为和源程序等价的目标代码。
目标代码可以有不同的形式：
– 目标机器代码形式；
– 汇编语言程序形式；
– 虚拟机目标代码形式；
目标代码生成的有关问题
目标机器语言的确定：确定目标代码的形式，目标机，和目标语言。也可以使用一些中间表示方式，比如三元式，四元式等。
语言结构目标代码的确定：确定语言中的各类语言结构和目标代码结构之间的对应关系。
运行时刻存储管理：程序运行的时刻，需要为变量分配存储空间。在编译时刻可以确定变量所需要的空间，和偏移地址。
而实际的地址要等到运行时刻才可以确定。
寄存器分配：合理利用寄存器可以使得程序运行效率比较高。
求值顺序的选择：
代码生成程序的设计：
虚拟机
虚拟机的设立包含了一般计算机的特征，但是比较简单。
方便学习编译程序的书写。
按照字节编址,4个字节为一个字。
有 n个通用寄存器。
指令形式为 OP 源，目标，表示将源和目标地址中的数据计算后存放到目标地址中。
绝对地址 M M 1
寄存器 R R 0
变址 D(R) D+contents(R) 2
间接寄存器 *R contents(R) 1
间接变址 *D(R) Con(D+con (R)) 2
立即数 #C 常数 C 1
虚拟机的指令集合
NEG T -con(T)=>T
SUB S T con(T)-con(S)=>T
MPY S T con(T)*con(S)=>T
DIV S T con(T)/con(S)=>T
CMP S T 比较 con(T)和 con(s)
Cjrelop T 按 relop为 true转向 T
ITOF S T 整型 con(S)转换为 float后存放到 T。
GOTO T 转向 T
RETURN 返回
CALL P,N 以 N个参数调用子程序 P
语句的翻译（赋值）
语法,V=e
语义：计算 e的值之后把值赋给变量 V。
执行的过程：
– 计算 V的变量地址；
– 计算右部表达式 e的值；
– 如果需要，对 e进行强制类型转换；
– 把转换过的 e值赋予 V的地址；
显然，一个赋值语句（赋值表达式）对应的代码由对应于上述 4个部分的代码组成。
对于每个表达式，它对应的属性应该包括：代码 code，
结果存放的地址 place。
赋值语句的翻译方案
S::=id:=E P:=lookup(id.name);//获取 id信息
if(p!=NIL) then
S.code = E.code | gencode(MOV,E.place,p->place)
else error
E::=E1+E2 E.place=newtemp;
E.code=E1.code||E2.code||gencode(MOV,E1.place,E.place)
||gencode(ADD,E2.place,E.place)
E::=E1*E2 E.place=newtemp;
E.code=E1.code||E2.code||gencode(MOV,E1.place,E.place)
||gencode(MPY,E2.place,E.place)
E::=id p:=lookup(id.name);
if(p!=null) {E.place=p->place; E.code=空 }
赋值语句中的类型强制
当赋值语句的左右两边类型不同却相容的时候，应该进行类型强制。
{p=lookup(id.name);
if(p!=null) then
{ S.code=E.code;
if(p->type ==int and E.type==int)
S.code=S.code||gencode(MOV,E.place,p->place)
else if (p->type=real and E.type=int)
{u=newtemp; S.code= S.code||gencode(ITOF,
E.place,u)||gencode(MOV,u,p->place)}
else if … …
变量的存取
当赋值语句的左部不是简单变量的时候，代码中，计算左部地址的部分比较复杂。
主要需要讨论的是：
– 下标变量的翻译方案
– 域变量的翻译方案下标变量的计算方法
对于一维数组 T a[num]，其第 i(从 0开始计算）个元素的地址是 base+i*sizeof(T)
对于二维数组 T a[num1][num2]，元素 a[i][j]的地址和数组的分配相关。假设，数组元素按行存放，那么
a[i][j]的地址是 base+(i*num2+j)*sizeof(T)。
对于多维数组 Ta[n1][n2]…[nm],其元素 A[i1,i2,…im]
的地址是,
– base+i1*n2*…*nm+i2*n3*…*nm+…+im 。
赋值左部的语法修改成,V::=Elist]|id，
Elist::=Elist,E|id[E。
下标变量的计算方法 (续 )
E::=V
{if (V.atag==0)/*不是数组 */ …...
else{ E.place = newtemp;
E.code = V.code ||gencode(’MOV 0(V.place),E.place)}
}
V::= Elist]{V.place=newtemp; V.tag = 1; V.code =
Elist.code || ‘MOV’,sizeof(T)存放处,V.place ||MPY
Elist.place,V.place) || ADD Elist.array的零地址 V.place
V::=id{p=lookup(id.name);V.place=p;V.atag=0}
注：类型 T和零地址存放处在 Elist.array中可以得到。
下标变量的计算方法 (续 )
Elist::=Elist1,E {t=newtmp; i:=Elist1.dim+1; Elist.code:=
Elist1.code || E.code || MOV,Elist1.array第 i维上界存放处,t
|| MPY Elist1.place,t || ADD E.place;
Elist.array = Elist1.array; Elist.place=i;
Elist.dim = i;}
Elist,:= id[E {p=lookup(id.name); Elist.place = E.place;
Elist.dim = 1; Elist.code = E.code; Elist.array = p;}
属性说明：
– Elist.array包含了这个数组的信息。
– Elist.dim表示当前已经扫描到了第几维。
– Elist.place最终存放了偏移量（以 sizeof(T)为单位 )，在其它时刻，
扫描到第 m维时生成的代码使 (((i1*num2 + i2)*num3+…)*numm) 存放在 Elist.place中。
下标变量计算的例子
B[j,m],V
E.list ]
id
E
[
E.list
E
Name=B place=j
place=j,dim=1,
array=A,code=‘’
place=m
place=t1,dim=2,
array=A,code=(1)
Place=t2,code=(1)(2)
MOV A的第 2维上界 t1
MPY j t1
ADD m t1
MOV sizeof(int) t2
MPY t1 t2
ADD B的零地址 t2
域变量的翻译方案
在说明记录（结构）类型的时候，已经记录了各个域的偏移量，因此，域变量的地址的计算只需要查找各个域的偏移量就可以完成。
V::=E.domainname{V.place = newtmp;
offset = LOOKUP_st(E.type,domainname)
V.code = E.code || MOV E.place,V.place ||ADD
const(offset) V.place
选择语句的翻译
语法,S::= if (E) S1 else S2; | if(E) S1;
语义：如果 E的值为 true，那么执行 S1；否则执行 S2（情况 1）
或者不执行（情况 2）
代码模式：（ E为真的时候跳转）
– E的目标代码
– 判别 E值的代码
– E值为 true时转向 E.true的代码
– 转向 E.false的代码
– E.true,S1的目标代码
– 转向 E.next的代码
– E.false,S2的代码
– S.next,后继语句的代码代码的例子
If (a<b) max = b else max = a;
MOV a,R0; CMP R0 b;
CJ< L1
GOTO L2;
L1:MOV b R1; MOV R1 max;
GOTO L3;
L2,MOV a R1; MOV R1 max;
L3:
语法制导的语义定义
S::= if (E) S1 then S2
{E.true=newlabel();
E.false=newlabel();S1.next=S.next;
S2.next=S.next;(方案中斜体部分应该在 if后面 )
S.code = E.code || CMP E.place #1 || CJ=,E.true ||
GOTO E.false || ‘E.true:’ || S1.code || GOTO
S1.next || ‘E.false:’ || S2.code || ‘S.next:’
}
布尔表达式的翻译（基本方式）
E::= E1 OR E2 {E.place = newtmp;
E.code=E1.code || E2.code || MOV E1.place,
E.place || OR E1.place E.place}
E::= id1 relop id2 {E.place = newtemp; t:=
newtemp; E.code = MOV id1.place,t || CMP t,
id2.place || Cjrelop t,*+8 || GOTO *+12 || MOV
#1 E.place || GOTO *+8 || MOV #0 E.place
这里假定每个指令长度为 4，所以 goto *+8表示跳转到指令下面 2条指令。
基本方式的代码例子
a<b OR c>d代码如下：
MOV a,t2; CMP t2,b;
CJ< *+8; GOTO *+12;
MOV #1 t1; GOTO *+8;
MOV #0 t1; MOV c t4
CMP t4,d; CJ> *+8
GOTO *+12; MOV #1,t3
GOTO *+8; MOV #0 t3;
MOV t1 t5; OR t3 t5;
布尔表达式的翻译（高效方式）
显然，对于一个布尔表达式来说，有时不需要计算全部表达式就可以得到值。比如 E1 OR E2，如果 E1
的值为真，那么整个表达式的值也是真。
可以仅仅使用一个 MOV #1（ #0） E.place语句，当表达式的值为真（假）的时候，转向这个语句。而对于用于控制的表达式，直接转向‘真’的分支。
注意：因为表达式可能有副作用，布尔表达式怎么翻译需要根据语言的语义来决定。比如
– if (E1 OR f()) S1，使用基本方式的时候,f()一定会被执行，
但是使用高效方式的时候,f()可能不执行。
– 一般语言的语义定义都使用高效方式。
布尔表达式的语义规则
E::= E1 OR E2
– E1.true = E.true; E1.false=newlabel;
– E2.true = E.true; E2.false = E.false;
– E.code = E1.code||gencode(E1.false,‘:’)||E2.code
E::=id1 relop id2
– t=newtemp;
– E.code = MOV id1.place,t || CMP t,id2.place || Cjrelop
E.true || GOTO E.false
E的属性 true和 false分别表示如果 E的值为真和假的时候，程序执行的下一步。
这是语义规则，所以 E1的继承属性 true在后面定义。
例子
a<b OR c>d的代码：
MOV a,t1; CMP t1,b;
CJ< E.true;
GOTO L1;
L1,MOV c,t2;
CMP> E.true; GOTO E.false
对于 if (a<b OR c>d) S1 else S2,E.true和 E.false分别是 S1和
S2的标号。
对于 id = a<b OR c>d,E.true和 E.false分别是 MOV #1 id和
MOV #0 id的标号。
回填技术
if (a<b) max=b; else max = a;
MOV a R0; CMP R0 b; CJ<?
如果使用一趟扫描方式，显然，当要生成 CJ<?
指令的时候，不知道该指令需要转向哪里。
可以使用回填技术解决：
– 先生成一个指令坯，不填入转移目标；把这个指令的相关信息保存好，当可以得到转移目标的时候，在把目标填入这个位置。
Backpatch函数,把第一个参数里面的所有地址对应的指令中的转移目标都设置为第二个参数。
条件语句的翻译方案（回填）
S::=if (E) M1 S1 N ELSE M2 S2
– {backpatch(E.truelist,M1.pos); backpatch(E.falselist,
M2.pos); S.nextlist = merge(S1.nextlist,S2.nextlist);
S.nextlist=merge(S.nextlist,N.nextlist);}
M::=空 {M.pos=nextpos}
N::=空 {N.nextlist=makelist(nextpos); emit(‘GOTO’,‘_’);}
E::=E1 OR M E2{backpatch(E1.falselist,M.POS),
E.truelist = merge(E1.truelist,E2.truelist);
E.falselist=E2.falselist;}
回填的例子
a<b OR c>d AND e=f
E
E OR M E
E AND M Ea<b 动作 1 动作 2
c>d 动作 3 动作 4
e=f 动作 5
动作 6
MOV a t1
CMP t1 b
CJ< _
GOTO _
MOV c t2
CMP t2 d
CJ> _
GOTO _
MOV e t3
CMP t3 f
CJ> _
GOTO _
情况语句 (switch?)
语法,
CASE E of
case C1,S1;
case C2,S2;
….
Default Sn
end
语义：根据 E的值，执行相应的分支；如果 E的值等于 Ci，那么执行 Si。
情况语句的执行步骤
步骤 1：计算表达式 E的值
步骤 2：在情况表中顺序寻找和 E的值相同的值。如果找不到，则和缺省值匹配。
步骤 3：执行和该值相关的语句，然后执行后继语句。
情况语句的目标代码设计
（方案一）
计算 E的值并存放在 t的代码
如 t!=C1则转向 L1的代码。
语句 S1的代码。
转向后继语句的代码。
L1：如 t!=C2则转向 L2的代码。
语句 S2的代码。
转向后继语句的代码。
L2,… … …
… … … …
Ln-1：语句 Sn的目标代码。
Next：后继语句的目标代码。
情况语句的目标代码设计
（方案二）
计算 E的值并存于 t的目标代码。
转向测试 (test)的目标代码。
L1：语句 S1的目标代码。
转向后继语句的目标代码。
L2：语句 S2的目标代码。
转向后继语句的目标代码。
L3,… … … …
… … … …
test,如 t=Ci则转向 Si的代码。
Next:后继语句的代码。
翻译方案的设计
S::= switch E CaseList DefaultS end
{APPENDCODE(CaseTestCode(CList.PosList,CList.ValueList,
DefaultS.Pos));
}
CList1,:=
C,{pos=nextPos(); Clist1.PosList+=pos;
Clist1.ValueList+=C.lexvalue;}
S{APPENDCODE(S.code) }Clist
上面的方案不一定准确，只是表示一个大概思路。
迭代语句的翻译
语法,while E do S
语义：当 E的值为真的时候，重复执行语句 S，
直到 E的值为假。
执行步骤：
– 步骤 1：计算 E的值。
– 步骤 2：判断 E的值，如果为 true，则执行 S，
然后返回步骤 1。
– 步骤 3：如果 E的值为 false，转向执行当语句的后续语句。
迭代语句的代码设计
L,计算表达式 E的目标代码。
判别 E的值，并且当其值为 false时，
转向后继语句 (NEXT)的目标代码。
语句 S的目标代码转向标号 L的目标代码。
NEXT：后继语句的目标代码。
代码例子
While n<10 do n=n+1;
L1,MOV n,r0
CMP r0,#10
CJ< L2
GOTO L3
L2,MOV n,r1
ADD #1,r1
MOV r1,n
GOTO L1
L3:
迭代语句的语义规则
S::= while E do S
规则如下：
– S.begin = newlabel();
– E.true = newlabel(); E.false = S.next;
– S1.next = S.begin;
– S.code = S.begin,||E.code || E.true,|| S1.code ||
goto S1.next;
请注意 E的代码是按照高效的方案实现的，
所以 E的代码后面不需要判断转向的代码。
迭代语句的翻译方案（回填）
S::= while M1 E do M2 S1
{backpatch(S1.nextlist,M1.pos);
backpatch(E.truelist,M2.pos);
S.nextlist = E.falselist;
emit(goto,M1.pos)}
M::=空 {M.pos = nextpos}
复合语句的回填方案
S::= begin L end{S.nextlist = L.nextlist}
L::=L1; M S {backpatch(L1.nextlist,
M.pos); L.nextlist:=S.nextlist;}
L::=S{L.nextlist = S.nextlist}
过程调用
过程调用时，程序转向执行另外一段代码，
执行完毕后，返回原来的执行点继续往下执行。正确的过程调用必须保证：
– 程序的控制能够正确地转移到被调用的过程。
– 被调用者能够正确地从调用者哪里获取数据。
– 被调用者能够把处理结果返回给调用者。
– 同时，控制能够返回到调用的地方继续执行。
上述 4条中,1,4是控制联系,2,3是数据联系。
数据联系
数据联系的内容包括：
– 寄存器的内容在调用前后不被破坏。
– 实在参数的正确传递。
– 被调用过程局部变量的分配。
– 非局部变量的正确引用。
活动记录
过程（函数）体的每次执行称为该过程
（函数）的活动。
活动记录是为了管理过程的一次执行
（活动）中所需要信息的连续存储区域。
所有的活动记录被放在一个栈里面。活动记录在过程被调用的开始建立并压栈，
在过程执行结束之后出栈。
活动记录的结构
返回值：用来存放被调用过程返回给调用者的值。
实在参数：存放调用者传递给被调用者的实在参数。
访问链：存放用于引用其它活动记录中的非局部数据。
机器状态：保存临调用时的机器状态。
局部数据：过程的局部变量存放地点。
临时数据：存放执行时产生的中间结果。
活动记录的大小根据各个被调用过程决定。一般来说，在编译时刻就可以确定活动记录的大小。
返回值实在参数控制链机器状态局部数据临时数据访问链调用者和被调用者的衔接
调用者：
– 计算实在参数；把返回地址和自己的活动记录指针存放到被调用过程的活动记录。
被调用过程：
– 保存寄存器和其它的机器状态。
– 初始化局部数据，开始执行过程。
– 把返回值存放在活动记录中。
– 使用活动记录中的相应信息，恢复 top_sp和其它寄存器，返回控制。
调用者：
– 把返回值复制到自己的活动记录中去。继续执行。
过程（函数）调用语句
语法：
– call id(Elist)
语义：
– 建立形式参数和实在参数的对应关系后，执行被调用过程的过程体。
过程语句的执行
为被调用者的活动记录分配存储区域
计算过程调用中各个实在参数的值，并把值存放在到相应的位置。
设置环境指针（访问链）等，使得被调用过程可以访问外围数据。
保护交用过程的机器状态，包括寄存器状态。
初始化被调用过程的局部数据。
控制转移到被调用过程的入口处。
目标代码设计
过程调用入口和出口部分的处理可以调用入口子程序和出口子程序来完成。
代码模式如下：
– 计算实在参数 p1的值的代码
– param p1
– … …
– 计算实在参数 pn的值的代码
– param pm
– call P m
翻译方案
S::=CALL id(Elist)
– {S.code = Elist.code || ‘CALL id.place,Elist.number}
Elist,:= Elist1,E
– {Elist.code = Elist1.code || E.code || PARAM E.place;
Elist.number = Elist1.number + 1;}
Elist::= E
– {Elist.code = E.code ||PARAM E.place; Elist.number = 1}
缺陷：
– call P(…,f(x),…)
– 由于 PARAM的功能时将数据拷贝到被调用者的活动区域。
在上述的例子中,f(x)对应的 PARAM指令会和 P对应的指令混淆。
改进后的翻译方案
申请临时空间存放实在参数，用队列数据结构记录各个参数的存放位置。在计算完成之后一次性复制到新的活动记录。
S::=CALL id(Elist)
{count = 0; while not emptyQ(Elist.q) do
{ t=headQ(Elist.q); S.code = S.code || PARAM,t Count:=count +1;}
S.code = S.code || CALL id.place,Count;
}
Elist::=Elist1,E{EnterQ(E.place,Elist.q)}
Elsit::=E { Elist.q = CreateQ(); Enter(E.place,q)}
参数的传递
值调用
– 值参数的形式参数被当作过程的局部变量看待，存储区域在被调用者的活动记录中。
– 调用者计算实在参数的值，并把该值送入相应位置。
引用调用
– 如果参数时变量，传送给形式参数的实际上时参数的地址。
– 如果参数时常量或者表达式，首先给这些值分配临时存储区域，然后把这个区域的地址传送给被调用者。
– 在被调用的过程中，对于参数的使用通过间接的方式实现。
比如 swap(x,y)中,x,y为引用调用时,x=1的操作为向 x中的值存放
过程内部的语句可以使用到非局部的变量。在 pascal语言中，这种情况比较复杂。
F()
{int x,y
f1()
{int i,j; j=x;}
f2()
{
call f1();
}
call f2();
}
非局部数据的存取
F的活动记录
F2的活动记录
F1的活动记录
F1中调用 x时，对应的是在 F的活动记录中的 x.需要根据访问链向上寻找。
显示表
显示表是活动记录的指针数组 d，第 i个元素表示嵌套层次为 i的过程对应的活动记录的位置。
显示表的维护：当为（正文静态）嵌套深度为 i的过程的活动记录的时候，把 d[i]保存在活动记录中，并把 d[i]设置为当前活动记录。退出某个活动记录的时候，恢复 d[i]
为原来保存的值。
显示表的使用：当要使用嵌套层次为 i的变量时，由 d[i]得到该活动记录。根据该变量的偏移量，就可以得到该变量的地址。
显示表的内容时根据正文嵌套关系定的，和具体的调用关系没有多大关系。
在 C语言中，由于不需要考虑函数的嵌套定义，所以非局部变量就是全局变量。不需要考虑显示表。
显示表的例子
F的活动记录
F2的活动记录D[0]
D[1]
D[0]
D[1]
F的活动记录
F2的活动记录
F1的活动记录源程序的中间表示
优点：
– 和具体的机器特性无关，有利于重定目标。
– 可以对中间表示进行优化，提高代码质量。
– 可以分解程序的复杂性。
抽象语法树
通常的语法规则中，有些符号起到了解释作用。比如 S::= if (E) S1 else S2中,if,
else等的作用就类似于标点符号。一般，
关键字就类似于标点符号。
如果我们抛弃掉这些标点符号，就得到了抽象的语法规则：
– 选择语句 表达式 语句 语句抽象语法树的例子
x = a+b*c
assign
x +
a *
b c
S
V = E
E E+
E E*
b c
a
x
产生抽象语法树的语法制导定义重写规则 语义规则
S::=id=E
E::=E1+T
E::=T
T::=T1*F
T::=F
F::=(E)
F::=id
F::=num
S.nptr:=mn(assign,ml(id,id.entry),E.nptr)
E.nptr=mn(‘+’,E1.nptr,T.nptr)
E.nptr=T.nptr
T.nptr=mn(‘*’,T1.nptr,F.nptr)
T.nptr=F.nptr
F.nptr = E.nptr
F.nptr = ml(id,id.entry)
F.nptr=ml(num,num.lexval)
逆波兰表示方法
逆波兰又称为后缀表示方法，是表达式的一种表示形式。
在逆波兰表达式中，运算符写在分量后面。
a+b*c/(d+e)的逆波兰表示为 abc*de+/+
定义：设 E是表达式，那么
– 如果 E是变量或者常量,E的逆波兰表示为 E
– E1 OP E2 ==> E1’ E2’ OP，其中 E1’,E2’ 为
E1,E2的逆波兰表示。
– (E) ==> E’
逆波兰表示的生成（翻译）
E::=E1+T {printf(+)}
E::=T
T::=T1*F {printf(*)}
T::=F
F::=(E)
F::=id {printf(id.name);}
逆波兰表示方法的扩充
逆波兰表示可以被扩充到表达式以外的地方。
赋值语句,V=e ==> V’e’ =
赋值语句的例子：
– t=(a+b)*c/(d-e)
– tab+c*de-/=
条件语句的逆波兰表示
if (e) St else Se
e’ N1 GOF St’ N2 GO Sf’
N1和 N2是逆波兰表示中符号的序号。
GOF表示按假转,GO表示无条件转。
例子,if (a<b) max=b else max=a
1
a
11
max
3
<
4
11
5
GOF
6
max
7
b
8
=
9
14
10
GO
2
b
12
a
13
=
扩充后的逆波兰表示
GOTO N ==> N GOL
GOL表示无条件转向标号
复合语句,S1;S2 ==> S1’S2’
例子：
– {i=1; next,f=f+1; if (i>f) i=2 else goto next;}
– i 1 = next,f f 1 + = i f > 20 GOF i 2 = 22 GO
next GOL
迭代语句的逆波兰表示
while (e) S; ==> e’ N1 GOF S’ 1 GO
例子,
– wile (i<100) {j = j+i}
– i 100 < 13 GOF j j i + = 1 GO
从逆波兰表示生成代码
算法框架,
– 设立运算分量栈。
– 从左到右扫描逆波兰表示。扫描到运算分量栈的时候，将该分量入栈。扫描到运算符的时候，根据该运算符号的个数，对运算分量栈中相应个数的栈顶元素生成相应的目标代码；从分量栈中退出相应个数的分量；把存放运算结果的临时变量压栈。
– 重复第二步，直到扫描完表达式中的所有符号。
从逆波兰表示生成代码（例子）
If (a<b) max = b else max = a
a b < 11 GOF max b = 14 GO max a,=
MOV a R0
CMP R 0 b
CJ< *+8
CJ>= ____
MOV b R1
MOV R1 max
GOTO ____
MOV a R2
MOV R2 max
四元式序列
表示方法：
– 元算符 运算分量 运算分量 结果
– 运算分量可以是变量，常量，或者由编译程序引进的临时变量。
例子：
– a+b*c
– * b c t1
– + a t1 t2
四元式
单目运算符 op x
– OP X _ T
赋值语句,x = y;
–,= y _ x
间接赋值,*x = y;
– &= y x x
转向指令,GOTO L(L为标号）
– GOL L _ _
四元式
按照关系 relop比较按真转：
– relop x y L
无条件转移到序号 L(L为四元式序号 )
– GO L _ _
过程调用,p(x1,x2,…,xn)
– PARAM x1 _ _
– PARAM x2 _ _
– …
– PARAM xn _ _
– CALL p n _
四元式
份程序复合语句的开始与结尾：
– BLOCK _ _ _
– BLOCKEND _ _ _
将数组 A的第 i个元素的地址存放到 t:
– []= A i t
将数组 A的第 i个元素存放到 t:
– =[] A i t
A[i] = B[j]
– []= A i t1
– =[] B j t2
– &= t2 t1 t1
四元式序列的例子
max=a[1]; i=2;
while(i<=n)
{ if(a[i]>max) max = a[i]; i=i+1; }
=[] a 1 t1
= t1 max
= 2 i
> i n (12)
=[] a i t2
<= t2 max (9)
=[] a i t3
= t3 max
+ i 1 i
= t4 i
GO (4)
生成四元式的翻译方案
生成四元式的方案和前面的直接生成代码的方案是类似的。
S::= id=E{p=loopup(id.name);
if(p!=NULL) genquad(‘=’,E.place,‘ ’,p->place)
else error();
E::=E1+E2
{E.place = newtmp;genquad(‘+’,E1.place,E2.place,E.place)}
E::=id{p=lookup(id.name);if (p!=null) E.place=p->place;
else error();}
从四元式到代码
一般来讲，四元式的运算符都有对应的机器指令，或者对应的子程序，因此从四元式生成指令代码是容易的。
主要考虑的问题是运算分量和计算结果的存取问题。主要考虑：运算分量在内存中还是四元式中，在寄存器中时以后是否可以被使用等。
例如,- x y z对应的代码：
– 如果 x,y的值分别在 Ri和 Rj中且以后不需要引用 x，那么指令为,sub Rj Ri，寄存器 Ri中包含 z的值。
– 如果 x在 Ri中，而 y在内存单元,SUB y Ri
– 如果 x的值以后还需要被使用，或者 x,y都在内存中，或者其中有常数，指令的生成还要作相应的变化。
基本块
定义：基本块时这样的一个四元式序列，其控制流从第一个四元式进入，而从最后一个四元式离开，期间没有停止，也没有分支。
例如：
– * a z t1
– * a t1 t2
– * b b t3
– * b t3 t4
– - t2 t4 t5
基本块划分算法
算法 6.1
步骤 1：确定入口四元式：
– 第一个四元式是入口四元式。
– 由条件转移或无条件转移四元式转移到的四元式是入口四元式；
– 紧跟在条件转移或者无条件转移四元式后面的四元式是入口四元式。
步骤 2：对于每个入口四元式，它所对应的基本块是从该四元式（含）开始，到下一个入口四元式（不含）
或者四元式结束的全部四元式组成。
基本块划分的例子
入口四元式,1,4,5,12
基本块,1-3,4,5-11,12
= 1 i
= 1 f
= 0 a
>= i (12)10
= f b
+ f t1a
= t1 f
= b a
+ i t21
= t2 i
GO (4)
= f fib
代码生成算法
假定：每个四元式运算符都由相应的指令代码，并要求计算结果尽可能保留在寄存器中（为提高效率）。
算法输入：四元式；输出：目标代码
数据结构：
– 寄存器描述符：记录寄存器当前存放了哪个变量的值。一个寄存器可以存放一个或者多个的值。
– 地址描述符：记录每个名字的当前值的存放处所，
可以是寄存器，内存地址，或者它们的集合（当值被赋值传输的时候）。
寄存器描述符和地址描述符的例子
四元式
– + a b t1
– = t1 x
代码：
– MOV a r0
– ADD b r0 r0包含 t1 t1在 r0中
– MOV r0 x r0包含 t1,x x在 r0和存储字中。
算法
对于每个四元式 op x y z完成下列动作：
– 调用 getreg()，确定 x op y的值的存放地址 L,L通常是寄存器。
– 查看地址描述符，确定 x的当前的一个位置 x’。如果
x的当前值既在内存，又在寄存器中，选择寄存器作为 x’。如果 x’不是 L，生成指令 MOV
x’ L。
– 生成指令,op y’ L，其中 y’是 y的当前值所在
（寄存器优先）。修改地址描述符，指明 z在 L中。
如果 L是寄存器，修改寄存器描述符号，指明 L中包含了 z的值。
算法（续）
如果 x和 /或 y的值此后不再使用，并且在寄存器中，则修改寄存器描述符，只是这些寄存器中不再包含 x和 /或
y的值。
处理单目运算的四元式时，和上面的方法类似。但是对于 = x _ y四元式，如果此时 x的值在某个寄存器中，那么不需要生成代码，只需要用寄存器描述符和地址描述符指明 y的值也在该寄存器中即可。
当基本块处理完毕之后，如果有些值可能在其他基本块被使用，并且地址描述字表示这些值仅仅存放在寄存器中。那么我们需要生成将这些值存放到内存中的指令。
算法 (getreg)
如果 x的值在寄存器中，此寄存器不包含其他名字的值，
并且 op x y z之后，没有对 x的引用，则将该寄存器作为
L。修改地址描述符。
如果 1失败，并且由空闲寄存器的话，回送一个空闲寄存器作为 L
如果 2失败，并且 z在基本块中有下次引用，或者 OP必须使用寄存器，那么寻找一个被占用的寄存器 R，用 MOV
R M指令将 R的值存入相应的内存单元，修改地址描述符。如果 R中存放了多个值，需要生成多个 MOV指令。
把 z的单元作为 L。
例子
X=(a-b)*(a-c)+(a-c)
1) - a b t1 2)- a c t2
3)* t1 t2 t3 4)+ t3 t2 t4
5)= t4 x
MOV a,R0; SUB b R0 (R0包含 t1,t1在 R0中 )
MOV a R1; SUB c R1 (R1包含 t2,t2在 R1中 )
MPY R1 R0 (R0包含 t3,R1包含 t2 t2在 R1中,t3
在 R0中）
ADD R1 R0 (R0包含 t4,t4在 R0中 )
MOV R0 x (R0包含 t4,x x在 R0和内存中,t4
在 R0中 )
不同的寻址方式
对于变址寻址和间接寻址，考虑四元式：
– =[] A i t
– = t _ a
i所在的位置确定了生成哪些指令。
– 当 i在寄存器 Ri中的时候，
MOV A(Ri),R
MOV R,a
– 当 i在内存中的时候，需要在前面添加指令
MOV Mi,Ri.
寻址方式（ 2）
考虑四元式：
– []= B i t
– &= b t t
假定有获取地址的指令 ADDR A,R
– ADDR B(Ri) R
– MOV b *R.
同样,i在内存的时候需要先生成指令
– MOV Mi Ri。
三元式
如果我们不明显给出四元式的结果部分，而是用四元式的编号来表示结果，那么我们可以得到三元式。形式如下：
运算符 运算分量 运算分量
和四元式的区别：
– 用序号表示结果,ADD (3) t
– 赋值运算是双目运算符,= x y
– 按假转中有两个运算参数,GOF (14) (4)
三元式例子
max=a[1]; i=2;
while(i<=n)
{ if(a[i]>max) max = a[i]; i=i+1; }
(1) =[] A 1
(2) = (1) max
(3) = 2 i
(4) <= i n
(5) GOF (14) (4)
(6) =[] A i
(7) > (6) max
(8) GOF (11) (7)
(9) =[] A i
(10) = (9) max
(11) + i 1
(12) = (11) i
(13) GO (4)
运行环境
在得到目标程序之后，程序的运行还需要一些运行时刻支持程序包的支持。
本章内容包括：
– 运行时刻存储分配以及支持。
– 符号表的管理。
– 运行时刻支持系统。
名字到存储字的结合
程序设计语言是基于冯,诺伊曼结构的。
变量仿效的是存储字，而赋值语句模拟的是计算机存取，运算操作。
在目标程序运行的时刻，必须要对源程序中的每一个量都分配相应的存储字。
分配是隐式进行的。在编译时刻就决定了这些变量应该如何分配，在运行时刻决定究竟分配到哪里。
环境和状态
环境是名字到存储字的映射，就是说：在程序的运行中的某个时刻，某个名字的变量究竟存放在什么内存的什么地方。
在不同的时刻，变量的存放位置不变。
一般在进入分程序和退出分程序的时刻，环境会改变。
状态是存储字到值的映射函数。
一般执行赋值语句的时候，状态会改变。但是环境不变。
例子
Main()
{ int x,y,t; t=x; x=y; y=t; }
当进入 main()函数的时候,x,y,t的存储字在活动记录中分配。
环境为,{(x,mx),(y,my),(t,mt)};
假设开始的时刻 x,y,t的值为 5,1,0，那么相应的状态为
{(mx,5),(my,1),(mt,0)}。
在执行了三个赋值语句之后，状态变成 {(mx,1),(my,5),
(mt,5)}
作用域和生存周期的问题
作用域是根据静态的源程序文本确定的。但是程序的运行是动态的。每个函数的调用的层次关系和正文的嵌套是不一致的。我们需要一个方法来确定在特定的运行时刻，某个名字对应的值存放在什么地方。
每个值都有生存周期。
– 全局变量的值在整个运行期间有效。
– 局部变量在函数退出之后就没有意义了。
– 由 new,或者 malloc确定的存储字中的值的意义直到相应的 delete和 free的语句执行过后才消失。
程序运行时刻的存储区域
分为代码段，和数据段。
数据段中分为静态数据，
栈和堆。
堆和栈的增长方向相反。
代码静态数据栈堆
存储分配策略
静态分配策略
动态分配策略
– 栈式分配策略
– 堆式分配策略静态存储分配
对于某些变量，在编译时刻就可以由编译程序为它们分配存储字。在运行时刻，这些变量和存储字的结合不变。
全局变量和静态变量。
不能处理的情况：
– 在编译时刻不能确定大小的变量。
– 要支持递归过程实现。
– 动态建立的数据结构。
栈式存储分配
在内存中开放一个栈区，当过程的一次活动开始的时候，把活动记录入栈。过程活动结束的时候，活动记录出栈。
过程的局部变量在活动记录入栈的时候和存储字结合，活动记录出栈的时候结合消失。
栈式存储的方式可以分成活动记录大小可以确定和活动记录大小不可确定两种。
栈式存储分配（记录大小确定）
引入两个指针（一般使用特定的寄存器存放）：
– top：指向运行栈的栈顶。
– top_sp：指向活动记录中机器状态域的末端。
在过程 p执行之前，把 top加上 l，在过程
p执行结束后，把 top减去 l。 Top_sp的值可以相应确定。
对于过程中的局部名字 x，假设它的偏移量为 dx，那么 x的地址可以表示为 -
dx(Rtop)。也可以写成 dx’(Rtop_sp)。
top
top_sp
机器状态
0
出 /入口子程序
使用一个寄存器 sp来存放栈顶指针。
入口子程序：
– ADD #caller.recordsize SP
– MOV #here+8,SP//保存控制返回地址
– GOTO callee.code_area
出口子程序：
– GOTO 0(sp);//callee执行。
– SUB #caller.recordsize SP//退栈，由 caller执行。
可变长度变量的存放
在安排活动记录的时候，首先安排的是在编译时刻就可以确定的域，比如：控制链，访问链，机器状态域等。这样可以使得安排可变长度的变量的时候可以不影响到这些域的位置。
可变长数组被安排在活动记录的顶部。并且在活动记录的局部数据区中另外存放可变长度数据的指针（长度可以预先确定）。
调用其他函数的时候,SP的增加值需要动态确定。
top
P
A的指针数组 a
其他局部变量堆式存储分配
有些数据对象是不适合安排在静态区或者栈区里面的。它们的生存期是难以确定的。比如：由 new生成的对象。这些对象生存期在 new语句执行后开始，
到 delete语句执行后结束。以下任何一种情况都必须使用堆式分配：
– 数据对象随机创建和消亡。
– 过程活动结束后，数据对象依旧需要保留。
– 被调用过程活动的生存期比调用过程更加长。
堆式分配中,只有当程序在运行中,正式要求撤销数据对象的时候,该对象才被释放,
堆式存储分配
堆管理的基本功能,
– 分配空间
– 释放空间
指针 (指引 )的管理：
– 当程序申请了一个空间之后，一般得到一个指针。该指针同时也是表示该空间的句柄。
– 如果已经释放了该空间，那么这个指针就没有意义了，称为悬空指针。
指针空间
对于每个申请的空间，都有长度限制。如果超出这个限制，会产生不可预测的错误。
C语言中的堆空间的分配一般如下：
管理信息 存储区域指针垃圾回收系统
有些程序设计语言（一般式面向对象的程序设计语言）没有显式的空间回收机制，而是使用垃圾回收系统。便于编写程序，但是效率较低下。
当没有指针指向某段空间的时候，系统就回收该空间。
数据对象的指针的拷贝时，需要记录指向该对象的指针数量。
4 运行时刻支持系统
运行时刻子程序是为了支持目标程序的运行而开发的一系列子程序。这些子程序的全体被称为运行时刻支持程序包。
面向用户的运行子程序
– 用户可以显式调用这些子程序。
对用户隐匿的运行子程序：
– 活动记录的存储分配，参数传递机制，机器状态的保护。
