6.1 概况
6.2 说明部分的翻译
6.3 目标代码的生成
6.4 源程序的内部中间表示
第六章 语义分析与目标代码生成
6.1 概况
6.1.1 语义分析的概念
1,程序的含义
2,语义分析的功能
第六章 语义分析与目标代码生成
6.1 概况
6.1.1 语义分析的概念
1,程序的含义
2,语义分析的功能
第六章 语义分析与目标代码生成
程序的含义涉及两方面，即数据结构的
含义与控制结构的含义。
数据结构的含义,主要指与标识符相关联
的数据对象，也即量的含义。量涉及类
型与值，值在运行时刻确定，而类型则
由程序中的说明部分来规定。
控制结构的含义,是由语言定义的。
if(〈 表达式 〉 ) 〈 语句 〉 else 〈 语句 〉
6.1 概况
6.1.1 语义分析的概念
1,语义分析的含义
2,语义分析的功能
1)确定类型, 确定标识符所关联数据对象的数据类型 。
2)类型检查, 按照语言的类型规则, 检查运算的合法性与运算分量类
型的一致性 (相容性 )。
3)识别含义, 根据程序设计语言的语义定义 (形式或非形式的 ),确认
程序中各构造成分组合到一起的含义, 并作相应的语义处理 。 对可执行
语句生成中间代码或目标代码 。
4)其他一些静态语义检查, 语义分析时可进行一些静态语义检查,
例如控制流检查 。
6.1 概况
6.1.1 语义分析的概念
6.1.2 属性文法
一,属性文法的引进
二、语法制导定义
三、翻译方案
第六章 语义分析与目标代码生成
6.1 概况
6.1.1 语义分析的概念
6.1.2 属性文法
一,属性文法的引进
1.属性
2.属性文法
3.语法制导定义
4.翻译方案
5.语法制导的翻译
第六章 语义分析与目标代码生成
6.1 概况
6.1.1 语义分析的概念
6.1.2 属性文法
一,属性文法的引进
1.属性,想表达或想涉及的任何内容。 如类型、数值、字符串,
2.属性文法 存储地址与代码等。
3.语法制导定义
4.翻译方案
5.语法制导的翻译
第六章 语义分析与目标代码生成
6.1 概况
6.1.1 语义分析的概念
6.1.2 属性文法
一,属性文法的引进
1.属性
2.属性文法
3.语法制导定义
4.翻译方案
5.语法制导的翻译
第六章 语义分析与目标代码生成
对于某个压缩了的上下文无关文法, 把每
个文法符号联系于一组属性, 且让该文法的重
写规则附加以语义规则时, 则称该上下文无关
文法为属性文法 。
6.1 概况
6.1.1 语义分析的概念
6.1.2 属性文法
一,属性文法的引进
1.属性
2.属性文法
3.语法制导定义
4.翻译方案
5.语法制导的翻译
第六章 语义分析与目标代码生成
是较抽象的翻译说明, 它隐蔽了一些实现
细节, 因此在书写语法制导定义时, 无需指明
翻译时语义规则的计算次序 。
6.1 概况
6.1.1 语义分析的概念
6.1.2 属性文法
一,属性文法的引进
1.属性
2.属性文法
3.语法制导定义
4.翻译方案
5.语法制导的翻译
第六章 语义分析与目标代码生成
如果语法制导定义中指明了语义规则的计
算次序, 陈述了一些实现细节, 将称其为翻译
方案 。
6.1 概况
6.1.1 语义分析的概念
6.1.2 属性文法
一,属性文法的引进
1.属性
2.属性文法
3.语法制导定义
4.翻译方案
5.语法制导的翻译
第六章 语义分析与目标代码生成
是在语法规则制导下, 通过对语义规则的
计算, 完成对输入符号串的翻译 。 在使用语法
规则进行推导或归约的同时又使用这些语义规
则来指导翻译与最终产生目标代码 。
6.1 概况
6.1.1 语义分析的概念
6.1.2 属性文法
一,属性文法的引进
1.属性
2.属性文法
3.语法制导定义
4.翻译方案
5.语法制导的翻译
第六章 语义分析与目标代码生成
例 6, 2 某程序设计语言说明部分的语法制导定义。
重写规则 语义规则
D::=TL
T::=int
T::=float
L::=L 1,id
L::=id
L.in:=T.ty pe
T.type:=in teger
T.type:=re al
L 1,in:=L.i n
addtype(id,e ntry,L,in)
addtype(id,e ntry,L,in)
6.1 概况
6.1.1 语义分析的概念
6.1.2 属性文法
一,属性文法的引进
1.属性
2.属性文法
3.语法制导定义
4.翻译方案
5.语法制导的翻译
第六章 语义分析与目标代码生成
综合属性,一个结点相应文法符号的属性之值
通过语法分析树中它的子结点的属性之值来计算；
继承属性,一个结点相应文法符号的属性之值
通过语法分析树中它的兄弟结点与父结点的相应
文法符号的属性之值来计算 。
6.1 概况
6.1.1 语义分析的概念
6.1.2 属性文法
一,属性文法的引进
1.属性
2.属性文法
3.语法制导定义
4.翻译方案
5.语法制导的翻译
第六章 语义分析与目标代码生成
翻译过程,
1)分析输入符号串, 建立语法分析树；
2)从语法分析树得到描述结点属性间
依赖关系的依赖图, 由此依赖图得到
语义规则的计算次序；
3)进行语义规则计算, 得到翻译结果 。
6.1 概况
6.1.1 语义分析的概念
6.1.2 属性文法
一,属性文法的引进
二、语法制导定义
1.属性文法的形式描述
2.属性的分类
3.依赖图
4.计算次序
第六章 语义分析与目标代码生成
定义 6.1 一个属性文法 AG是一个四元组
(G,A,R,C),其中,
G是压缩了的上下文无关文法 (VN,VT,P,Z)；
A是有穷属性集；
R是有穷属性规则集； C是有穷条件集 。
AG=(G,A,R,C)
6.1 概况
6.1.1 语义分析的概念
6.1.2 属性文法
一,属性文法的引进
二、语法制导定义
1.属性文法的形式描述
2.属性的分类：综合属性、继承属性
3.依赖图
4.计算次序
第六章 语义分析与目标代码生成
6.1 概况
6.1.1 语义分析的概念
6.1.2 属性文法
一,属性文法的引进
二、语法制导定义
1.属性文法的形式描述
2.属性的分类
3.依赖图
4.计算次序
第六章 语义分析与目标代码生成
依赖图：用来表达属性间相互依赖关系的
有向图称为依赖图 。
基本点：若属性 b依赖属性 c,则相应于 c的
结点到相应于 b的结点有一弧 。
6.1 概况
6.1.1 语义分析的概念
6.1.2 属性文法
一,属性文法的引进
二、语法制导定义
1.属性文法的形式描述
2.属性的分类
3.依赖图
4.计算次序
第六章 语义分析与目标代码生成
依赖图：用来表达属性间相互依赖关系的
有向图称为依赖图 。
基本点：若属性 b依赖属性 c,则相应于 c的
结点到相应于 b的结点有一弧 。
6.1 概况
6.1.1 语义分析的概念
6.1.2 属性文法
一,属性文法的引进
二、语法制导定义
1.属性文法的形式描述
2.属性的分类
3.依赖图
4.计算次序
第六章 语义分析与目标代码生成
依赖图的任何拓扑排序是语法分析树中结
点语义规则计算的一个正确排序 。
6.1 概况
6.1.1 语义分析的概念
6.1.2 属性文法
一,属性文法的引进
二、语法制导定义
三、翻译方案
第六章 语义分析与目标代码生成
翻译方案,在语法制导定义时指明语义规
则的计算次序 。
翻译方案与语法制导定义的区别,
在翻译方案中指明了语义规则的计算
次序, 也即允许描述一些实现细节 。
D∷=T { L.in:=T.type }
L
T∷=int { T.type:=integer }
T∷=float { T.type:=real }
L∷= { L1.in:=L.in }
L1,id { addtype(id.entry,L.in) }
L∷=id { addtype(id.entry,L.in) }
6.2 说明部分的翻译
一、常量定义的翻译
二、变量说明的翻译
const float pi=3.1416,one=1.0；
翻译方案如下,
CONSTDEF∷=const CDT；
CDT∷=CDT,CD
CDT∷=CD
CD∷=id=num { num.ord:=lookCT(num.lexval);
id.ord:=num.ord;id.type:=integer;
id.kind:=CONSTANT;
add(id.entry,id.kind,id.type,id.ord)}
CD∷=id=id 1 { id.kind:=CONSTANT; id.type:=id1.type;
id.ord:=id1.ord;
add(id.entry,id.kind,id.type,id.ord)}
6.2 说明部分的翻译
一、常量定义的翻译
二、变量说明的翻译
int i ； int j； int k； float a； float b；
重写规则 语 义 动 作
P ∷ =
D;S
D ∷ =D;D
D ∷ =T id
D ∷ =T id ［ num ］
T ∷ =int
T ∷ =float
T ∷ =T
1
*
{offset:=0 }
{enter(id,name,T.ty pe,offse t);
offset:= offset+T,width}
{enter(id,name,arr ay(num.l exval,T.t ype), off set);
offset:= offset+ n um.lexval *T.width}
{T.type:=i nteger; T,width:= 2}
{T.type:=r eal; T.wi dth:=4}
{T.type:=p ointer(T
1
.type); T.width:= 4}
6.1 概况
6.2 说明部分的翻译
6.3 目标代码的生成
一、概况
二、虚拟机
三、控制语句的翻译
第六章 语义分析与目标代码生成
6.1 概况
6.2 说明部分的翻译
6.3 目标代码的生成
一、概况
1,代码生成程序
2,目标代码生成中的有关问题
第六章 语义分析与目标代码生成
6.1 概况
6.2 说明部分的翻译
6.3 目标代码的生成
一、概况
1,代码生成程序
2,目标代码生成中的有关问题
第六章 语义分析与目标代码生成
代码生成程序,其功能是为源程序
生成与之等价的目标机器代码 。 其
输入是源程序的中间表示 （ 可以是
语法分析树或其他内部中间表示 ）,
输出是目标代码 。
6.1 概况
6.2 说明部分的翻译
6.3 目标代码的生成
一、概况
1,代码生成程序
2,目标代码生成中的有关问题
第六章 语义分析与目标代码生成
1,目标机目标语言的确定
2,语言结构目标代码的确定
3,运行时刻存储管理
4,寄存器分配
5,求值顺序的选择
6,代码生成程序的设计
6.1 概况
6.2 说明部分的翻译
6.3 目标代码的生成
一、概况
二、虚拟机
1.对虚拟机的约定
2.寻址方式
3.指令系统
第六章 语义分析与目标代码生成
6.1 概况
6.2 说明部分的翻译
6.3 目标代码的生成
一、概况
二、虚拟机
1.对虚拟机的约定
2.寻址方式
3.指令系统
第六章 语义分析与目标代码生成
对虚拟机的约定,
1.按字节编址, 4个字节组成一个字, 有 n
个通用寄存器 R0,R1,…,Rn-1。
2.指令的形式为,OP 源, 目标
3.一个字存放一条指令, 指令中的源和目
标必须由寄存器和存储字地址及寻址方式
组合起来指明 。
6.1 概况
6.2 说明部分的翻译
6.3 目标代码的生成
一、概况
二、虚拟机
1.对虚拟机的约定
2.寻址方式
3.指令系统
第六章 语义分析与目标代码生成
MOV R0,M 绝对地址寻址方式
把寄存器 R0的内容送入地址 M
MOV 4(R0),R1 变址寻址方式
把值 contents(4+contents(R0))送入 R1
MOV *4(R0),R1 间接变址寻址方式
把值 contents(contents(4+contents(R0)))送入 R1
MOV #1,R0 立即数寻址方式
把值 1送入 R0
6.1 概况
6.2 说明部分的翻译
6.3 目标代码的生成
一、概况
二、虚拟机
1.对虚拟机的约定
2.寻址方式
3.指令系统
第六章 语义分析与目标代码生成
MOV S,T
NEG T -contents(T)=>T
ADD S,T contents(T)+contents(S)=>T
SUB S,T contents(T)-contents(S)=>T
MPY S,T contents(T)*contents(S)=>T
DIV S,T contents(T)/contents(S)=>T
CMP S,T 比较 contents(S)和 contents(T)
CJrelop T 按 relop为 true转向 T(其中 relop
可以是＜, ＞, ≠, ＝, ≤, ≥ )
ITOF S,T 把整型的 contents(S)转成实
型, 然后将转换后的值传送给 T
GOTO T 无条件转移控制到 T
RETURN 返回
CALL P,N 以 N个参数调用子程序 P
6.1 概况
6.2 说明部分的翻译
6.3 目标代码的生成
一、概况
二、虚拟机
三、控制语句的翻译
1.赋值语句
2.选择语句
3.循环语句
4.过程语句
第六章 语义分析与目标代码生成
6.1 概况
6.2 说明部分的翻译
6.3 目标代码的生成
一、概况
二、虚拟机
三、控制语句的翻译
1.赋值语句
2.选择语句
3.循环语句
4.过程语句
第六章 语义分析与目标代码生成 1.语法定义 V=e； 2,语义,把右部表达式 e的值赋给左部变量 V。
3,赋值语句的执行
(1)计算右部表达式 e的值；
(2)必要时对 e的值进行类型转换, 强制到 V
的类型；
(3) 计算左部变量 V的地址；
(4) 把 e的值赋给左部变量 V。
4,目标代码设计
例 赋值语句 z=a*b－ c/d的目标代码
设 a,b,c与 d都是简单变量, 都用它们的
名字表示相应的存储地址 。
MOV a,R0
MPY b,R0
MOV c,R1
DIV d,R1
SUB R1,R0
MOV R0,z
6.1 概况
6.2 说明部分的翻译
6.3 目标代码的生成
一、概况
二、虚拟机
三、控制语句的翻译
1.赋值语句
2.选择语句
3.循环语句
4.过程语句
第六章 语义分析与目标代码生成
1.语法定义 if(E) S else S 或者 if(E) S
2,语义
3,条件语句的执行
(1)计算表达式 E的值；
(2)判别：若 E之值为 true,执行紧随 E之后的语句 S，
然后无条件转去执行条件语句的后继语句；
(3)否则, E之值为 false,跳过紧随 E之后的语句 S而
执行 else之后的语句 S,然后执行条件语句的后继语句 。
4,目标代码设计
例 if(a＜ b) max=b； else max=a；
其中, a,b与 max都是整型变量 。
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
6.1 概况
6.2 说明部分的翻译
6.3 目标代码的生成
一、概况
二、虚拟机
三、控制语句的翻译
1.赋值语句
2.选择语句
3.循环语句
4.过程语句
第六章 语义分析与目标代码生成 1.语法定义 while (E) S 2,语义
3,条件语句的执行
(1)计算逻辑表达式 E之值；
(2) E为 true,执行语句 S,然后返回到步骤 1；
(3)E为 false时, 执行 while语句的后继语句 。
4,目标代码设计
例 while(n<10) 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,
6.1 概况
6.2 说明部分的翻译
6.3 目标代码的生成
一、概况
二、虚拟机
三、控制语句的翻译
1.赋值语句
2.选择语句
3.循环语句
4.过程语句
第六章 语义分析与目标代码生成 几个概念,活动,过程体的每次执行；
过程活动的生存期,是过程体的执行步骤序列；
活动记录,为管理过程的一次执行所需信息而设置的连续存储区域。
返回值 域, 有值函数的函数值，常用特定的寄存器返回。
实在参数 域,
控制链 域, 指向调用程序的活动记录。
访问链 域, 用以引用存于其它活动记录的非局部数据。
机器状态 域, 用来保存临调用过程时的机器状态信息,局部数据 域, 用来
存放过程一次执行时的局部数据。
临时数据 域, 存放过程执行时产生的中间结果等。
6.1 概况
6.2 说明部分的翻译
6.3 目标代码的生成
一、概况
二、虚拟机
三、控制语句的翻译
1.赋值语句
2.选择语句
3.循环语句
4.过程语句
第六章 语义分析与目标代码生成
1.语法定义 CALL id(Elist)
2,过程语句的执行
(1)为被调用过程的活动记录分配存储区域；
(2)计算过程语句参数表中各个实参的值, 并存放在活动记录中相应存 储位置；
(3)设置环境指针 (访问链等 ),使得被调用过程可访问外围过程的数据；
(4)保护调用过程的机器状态, 包括寄存器值与返回地址等 ；
(5)把被调用过程局部数据域初始化 ；
(6)把控制转移到被调用过程的入口代码处 。
6.1 概况
6.2 说明部分的翻译
6.3 目标代码的生成
6.4 源程序的内部中间表示
使用中间语言的优点,
1)中间表示与具体机器特性无关, 一种中间表示可以为生成多种不
同型号的目标机之目标代码服务；
2)可对中间表示做与机器无关的优化, 有利于提高目标代码的质量；
3)把源程序映射成中间表示, 再映射成目标代码的工作分在几个阶
段进行 。 有利于编译程序本身的开发, 有利于人员的分工, 等等 。
几种中间表示的方法, 抽象语法树, 逆波兰表示, 三元式序列与四
元式序列等 。
6.1 概况
6.2 说明部分的翻译
6.3 目标代码的生成
6.4 源程序的内部中间表示
一、抽象语法树
二、逆波兰表示
三、四元式序列
四、三元式序列
6.4 源程序的内部中间表示
一、抽象语法树
S∷=IF E THEN S ELSE S 条件语句 表达式 语句 语句
S∷=V,=E 赋值语句 左部 表达式
例 设有赋值语句 x=a+b*c
6.4 源程序的内部中间表示
一、抽象语法树
S∷=IF E THEN S ELSE S 条件语句 表达式 语句 语句
S∷=V,=E 赋值语句 左部 表达式
二、逆波兰表示 逆波兰表示是从抽象语法树按后根遍历法产生的
线性化表示 。
表达式 a+b*c/(d+e)的逆波兰表示
是 abc*de+/+
6.4 源程序的内部中间表示
一、抽象语法树
二、逆波兰表示
三、四元式序列
1.表示法约定
2.四元式序列之例
3.从四元式序列生成目标代码
6.4 源程序的内部中间表示
一、抽象语法树
二、逆波兰表示
三、四元式序列
1.表示法约定
2.四元式序列之例
3.从四元式序列生成目标代码
双目运算的一般形式：运算符 运算分量 运算分量 结果
其中，运算分量和结果可以是变量、常量或由编译程序
引进的临时变量。
6.4 源程序的内部中间表示
一、抽象语法树
二、逆波兰表示
三、四元式序列
1.表示法约定
2.四元式序列之例
3.从四元式序列生成目标代码
例 for i:=1 to 100 do s:=s+i；
展开为,
i:=1；
10:if i <= 100 then
begin s:=s+i；
i:=i+1；
goto 10
end；
四元式序列,
(1)(:=,1,/,i)
(2)(>,i,100,(6))
(3)(+,s,i,s)
(4)(+,i,1,i)
(5)(GO,(2),/,/)
(6)
6.4 源程序的内部中间表示
一、抽象语法树
二、逆波兰表示
三、四元式序列
1.表示法约定
2.四元式序列之例
3.从四元式序列生成目标代码
如果对于四元式的一切运算符都有对应的目标机器操作码,
从四元式序列生成目标代码的工作是容易实现的 。 主要问题是
运算分量与计算结果的存取问题, 在生成目标指令时, 要考虑
四元式中运算分量是在寄存器中还是在内存中, 当在寄存器中
时, 以后还会被使用否, 等等 。
6.4 源程序的内部中间表示
一、抽象语法树
二、逆波兰表示
三、四元式序列
四、三元式序列
1.表示法约定 运算符 运算分量 运算分量
2.三元式序列之例
6.4 源程序的内部中间表示
一、抽象语法树
二、逆波兰表示
三、四元式序列
四、三元式序列
1.表示法约定
2.三元式序列之例
例 for i:=1 to 100 do s:=s+i；
展开为,i:=1；
10:if i <= 100 then
begin s:=s+i；
i:=i+1；
goto 10
end；
四元式序列,(1)(:=,1,/,i)
(2)(>,i,100,(6))
(3)(+,s,i,s)
(4)(+,i,1,i)
(5)(GO,(2),/,/)
(6)
三元式序列,(1)(:=,1,i)
(2)(>,i,100)
(3)(GOT,(9),(2))
(4)(+,s,i)
(5)(:=,(4),s)
(6)(+,i,1)
(7)(:=,(6),i)
(8)(GO,(2),/)
(9)
习题 15
1,试画出表达式 (a+b)*(c－ d)－ (a*b+c)的抽象语
法树 。
2,试把表达式 (a+b)*(c－ d)－ (a*b+c)翻译成
(1)逆波兰表示
(2)四元式序列
(3)三元式序列
6.2 说明部分的翻译
6.3 目标代码的生成
6.4 源程序的内部中间表示
第六章 语义分析与目标代码生成
6.1 概况
6.1.1 语义分析的概念
1,程序的含义
2,语义分析的功能
第六章 语义分析与目标代码生成
6.1 概况
6.1.1 语义分析的概念
1,程序的含义
2,语义分析的功能
第六章 语义分析与目标代码生成
程序的含义涉及两方面，即数据结构的
含义与控制结构的含义。
数据结构的含义,主要指与标识符相关联
的数据对象，也即量的含义。量涉及类
型与值，值在运行时刻确定，而类型则
由程序中的说明部分来规定。
控制结构的含义,是由语言定义的。
if(〈 表达式 〉 ) 〈 语句 〉 else 〈 语句 〉
6.1 概况
6.1.1 语义分析的概念
1,语义分析的含义
2,语义分析的功能
1)确定类型, 确定标识符所关联数据对象的数据类型 。
2)类型检查, 按照语言的类型规则, 检查运算的合法性与运算分量类
型的一致性 (相容性 )。
3)识别含义, 根据程序设计语言的语义定义 (形式或非形式的 ),确认
程序中各构造成分组合到一起的含义, 并作相应的语义处理 。 对可执行
语句生成中间代码或目标代码 。
4)其他一些静态语义检查, 语义分析时可进行一些静态语义检查,
例如控制流检查 。
6.1 概况
6.1.1 语义分析的概念
6.1.2 属性文法
一,属性文法的引进
二、语法制导定义
三、翻译方案
第六章 语义分析与目标代码生成
6.1 概况
6.1.1 语义分析的概念
6.1.2 属性文法
一,属性文法的引进
1.属性
2.属性文法
3.语法制导定义
4.翻译方案
5.语法制导的翻译
第六章 语义分析与目标代码生成
6.1 概况
6.1.1 语义分析的概念
6.1.2 属性文法
一,属性文法的引进
1.属性,想表达或想涉及的任何内容。 如类型、数值、字符串,
2.属性文法 存储地址与代码等。
3.语法制导定义
4.翻译方案
5.语法制导的翻译
第六章 语义分析与目标代码生成
6.1 概况
6.1.1 语义分析的概念
6.1.2 属性文法
一,属性文法的引进
1.属性
2.属性文法
3.语法制导定义
4.翻译方案
5.语法制导的翻译
第六章 语义分析与目标代码生成
对于某个压缩了的上下文无关文法, 把每
个文法符号联系于一组属性, 且让该文法的重
写规则附加以语义规则时, 则称该上下文无关
文法为属性文法 。
6.1 概况
6.1.1 语义分析的概念
6.1.2 属性文法
一,属性文法的引进
1.属性
2.属性文法
3.语法制导定义
4.翻译方案
5.语法制导的翻译
第六章 语义分析与目标代码生成
是较抽象的翻译说明, 它隐蔽了一些实现
细节, 因此在书写语法制导定义时, 无需指明
翻译时语义规则的计算次序 。
6.1 概况
6.1.1 语义分析的概念
6.1.2 属性文法
一,属性文法的引进
1.属性
2.属性文法
3.语法制导定义
4.翻译方案
5.语法制导的翻译
第六章 语义分析与目标代码生成
如果语法制导定义中指明了语义规则的计
算次序, 陈述了一些实现细节, 将称其为翻译
方案 。
6.1 概况
6.1.1 语义分析的概念
6.1.2 属性文法
一,属性文法的引进
1.属性
2.属性文法
3.语法制导定义
4.翻译方案
5.语法制导的翻译
第六章 语义分析与目标代码生成
是在语法规则制导下, 通过对语义规则的
计算, 完成对输入符号串的翻译 。 在使用语法
规则进行推导或归约的同时又使用这些语义规
则来指导翻译与最终产生目标代码 。
6.1 概况
6.1.1 语义分析的概念
6.1.2 属性文法
一,属性文法的引进
1.属性
2.属性文法
3.语法制导定义
4.翻译方案
5.语法制导的翻译
第六章 语义分析与目标代码生成
例 6, 2 某程序设计语言说明部分的语法制导定义。
重写规则 语义规则
D::=TL
T::=int
T::=float
L::=L 1,id
L::=id
L.in:=T.ty pe
T.type:=in teger
T.type:=re al
L 1,in:=L.i n
addtype(id,e ntry,L,in)
addtype(id,e ntry,L,in)
6.1 概况
6.1.1 语义分析的概念
6.1.2 属性文法
一,属性文法的引进
1.属性
2.属性文法
3.语法制导定义
4.翻译方案
5.语法制导的翻译
第六章 语义分析与目标代码生成
综合属性,一个结点相应文法符号的属性之值
通过语法分析树中它的子结点的属性之值来计算；
继承属性,一个结点相应文法符号的属性之值
通过语法分析树中它的兄弟结点与父结点的相应
文法符号的属性之值来计算 。
6.1 概况
6.1.1 语义分析的概念
6.1.2 属性文法
一,属性文法的引进
1.属性
2.属性文法
3.语法制导定义
4.翻译方案
5.语法制导的翻译
第六章 语义分析与目标代码生成
翻译过程,
1)分析输入符号串, 建立语法分析树；
2)从语法分析树得到描述结点属性间
依赖关系的依赖图, 由此依赖图得到
语义规则的计算次序；
3)进行语义规则计算, 得到翻译结果 。
6.1 概况
6.1.1 语义分析的概念
6.1.2 属性文法
一,属性文法的引进
二、语法制导定义
1.属性文法的形式描述
2.属性的分类
3.依赖图
4.计算次序
第六章 语义分析与目标代码生成
定义 6.1 一个属性文法 AG是一个四元组
(G,A,R,C),其中,
G是压缩了的上下文无关文法 (VN,VT,P,Z)；
A是有穷属性集；
R是有穷属性规则集； C是有穷条件集 。
AG=(G,A,R,C)
6.1 概况
6.1.1 语义分析的概念
6.1.2 属性文法
一,属性文法的引进
二、语法制导定义
1.属性文法的形式描述
2.属性的分类：综合属性、继承属性
3.依赖图
4.计算次序
第六章 语义分析与目标代码生成
6.1 概况
6.1.1 语义分析的概念
6.1.2 属性文法
一,属性文法的引进
二、语法制导定义
1.属性文法的形式描述
2.属性的分类
3.依赖图
4.计算次序
第六章 语义分析与目标代码生成
依赖图：用来表达属性间相互依赖关系的
有向图称为依赖图 。
基本点：若属性 b依赖属性 c,则相应于 c的
结点到相应于 b的结点有一弧 。
6.1 概况
6.1.1 语义分析的概念
6.1.2 属性文法
一,属性文法的引进
二、语法制导定义
1.属性文法的形式描述
2.属性的分类
3.依赖图
4.计算次序
第六章 语义分析与目标代码生成
依赖图：用来表达属性间相互依赖关系的
有向图称为依赖图 。
基本点：若属性 b依赖属性 c,则相应于 c的
结点到相应于 b的结点有一弧 。
6.1 概况
6.1.1 语义分析的概念
6.1.2 属性文法
一,属性文法的引进
二、语法制导定义
1.属性文法的形式描述
2.属性的分类
3.依赖图
4.计算次序
第六章 语义分析与目标代码生成
依赖图的任何拓扑排序是语法分析树中结
点语义规则计算的一个正确排序 。
6.1 概况
6.1.1 语义分析的概念
6.1.2 属性文法
一,属性文法的引进
二、语法制导定义
三、翻译方案
第六章 语义分析与目标代码生成
翻译方案,在语法制导定义时指明语义规
则的计算次序 。
翻译方案与语法制导定义的区别,
在翻译方案中指明了语义规则的计算
次序, 也即允许描述一些实现细节 。
D∷=T { L.in:=T.type }
L
T∷=int { T.type:=integer }
T∷=float { T.type:=real }
L∷= { L1.in:=L.in }
L1,id { addtype(id.entry,L.in) }
L∷=id { addtype(id.entry,L.in) }
6.2 说明部分的翻译
一、常量定义的翻译
二、变量说明的翻译
const float pi=3.1416,one=1.0；
翻译方案如下,
CONSTDEF∷=const CDT；
CDT∷=CDT,CD
CDT∷=CD
CD∷=id=num { num.ord:=lookCT(num.lexval);
id.ord:=num.ord;id.type:=integer;
id.kind:=CONSTANT;
add(id.entry,id.kind,id.type,id.ord)}
CD∷=id=id 1 { id.kind:=CONSTANT; id.type:=id1.type;
id.ord:=id1.ord;
add(id.entry,id.kind,id.type,id.ord)}
6.2 说明部分的翻译
一、常量定义的翻译
二、变量说明的翻译
int i ； int j； int k； float a； float b；
重写规则 语 义 动 作
P ∷ =
D;S
D ∷ =D;D
D ∷ =T id
D ∷ =T id ［ num ］
T ∷ =int
T ∷ =float
T ∷ =T
1
*
{offset:=0 }
{enter(id,name,T.ty pe,offse t);
offset:= offset+T,width}
{enter(id,name,arr ay(num.l exval,T.t ype), off set);
offset:= offset+ n um.lexval *T.width}
{T.type:=i nteger; T,width:= 2}
{T.type:=r eal; T.wi dth:=4}
{T.type:=p ointer(T
1
.type); T.width:= 4}
6.1 概况
6.2 说明部分的翻译
6.3 目标代码的生成
一、概况
二、虚拟机
三、控制语句的翻译
第六章 语义分析与目标代码生成
6.1 概况
6.2 说明部分的翻译
6.3 目标代码的生成
一、概况
1,代码生成程序
2,目标代码生成中的有关问题
第六章 语义分析与目标代码生成
6.1 概况
6.2 说明部分的翻译
6.3 目标代码的生成
一、概况
1,代码生成程序
2,目标代码生成中的有关问题
第六章 语义分析与目标代码生成
代码生成程序,其功能是为源程序
生成与之等价的目标机器代码 。 其
输入是源程序的中间表示 （ 可以是
语法分析树或其他内部中间表示 ）,
输出是目标代码 。
6.1 概况
6.2 说明部分的翻译
6.3 目标代码的生成
一、概况
1,代码生成程序
2,目标代码生成中的有关问题
第六章 语义分析与目标代码生成
1,目标机目标语言的确定
2,语言结构目标代码的确定
3,运行时刻存储管理
4,寄存器分配
5,求值顺序的选择
6,代码生成程序的设计
6.1 概况
6.2 说明部分的翻译
6.3 目标代码的生成
一、概况
二、虚拟机
1.对虚拟机的约定
2.寻址方式
3.指令系统
第六章 语义分析与目标代码生成
6.1 概况
6.2 说明部分的翻译
6.3 目标代码的生成
一、概况
二、虚拟机
1.对虚拟机的约定
2.寻址方式
3.指令系统
第六章 语义分析与目标代码生成
对虚拟机的约定,
1.按字节编址, 4个字节组成一个字, 有 n
个通用寄存器 R0,R1,…,Rn-1。
2.指令的形式为,OP 源, 目标
3.一个字存放一条指令, 指令中的源和目
标必须由寄存器和存储字地址及寻址方式
组合起来指明 。
6.1 概况
6.2 说明部分的翻译
6.3 目标代码的生成
一、概况
二、虚拟机
1.对虚拟机的约定
2.寻址方式
3.指令系统
第六章 语义分析与目标代码生成
MOV R0,M 绝对地址寻址方式
把寄存器 R0的内容送入地址 M
MOV 4(R0),R1 变址寻址方式
把值 contents(4+contents(R0))送入 R1
MOV *4(R0),R1 间接变址寻址方式
把值 contents(contents(4+contents(R0)))送入 R1
MOV #1,R0 立即数寻址方式
把值 1送入 R0
6.1 概况
6.2 说明部分的翻译
6.3 目标代码的生成
一、概况
二、虚拟机
1.对虚拟机的约定
2.寻址方式
3.指令系统
第六章 语义分析与目标代码生成
MOV S,T
NEG T -contents(T)=>T
ADD S,T contents(T)+contents(S)=>T
SUB S,T contents(T)-contents(S)=>T
MPY S,T contents(T)*contents(S)=>T
DIV S,T contents(T)/contents(S)=>T
CMP S,T 比较 contents(S)和 contents(T)
CJrelop T 按 relop为 true转向 T(其中 relop
可以是＜, ＞, ≠, ＝, ≤, ≥ )
ITOF S,T 把整型的 contents(S)转成实
型, 然后将转换后的值传送给 T
GOTO T 无条件转移控制到 T
RETURN 返回
CALL P,N 以 N个参数调用子程序 P
6.1 概况
6.2 说明部分的翻译
6.3 目标代码的生成
一、概况
二、虚拟机
三、控制语句的翻译
1.赋值语句
2.选择语句
3.循环语句
4.过程语句
第六章 语义分析与目标代码生成
6.1 概况
6.2 说明部分的翻译
6.3 目标代码的生成
一、概况
二、虚拟机
三、控制语句的翻译
1.赋值语句
2.选择语句
3.循环语句
4.过程语句
第六章 语义分析与目标代码生成 1.语法定义 V=e； 2,语义,把右部表达式 e的值赋给左部变量 V。
3,赋值语句的执行
(1)计算右部表达式 e的值；
(2)必要时对 e的值进行类型转换, 强制到 V
的类型；
(3) 计算左部变量 V的地址；
(4) 把 e的值赋给左部变量 V。
4,目标代码设计
例 赋值语句 z=a*b－ c/d的目标代码
设 a,b,c与 d都是简单变量, 都用它们的
名字表示相应的存储地址 。
MOV a,R0
MPY b,R0
MOV c,R1
DIV d,R1
SUB R1,R0
MOV R0,z
6.1 概况
6.2 说明部分的翻译
6.3 目标代码的生成
一、概况
二、虚拟机
三、控制语句的翻译
1.赋值语句
2.选择语句
3.循环语句
4.过程语句
第六章 语义分析与目标代码生成
1.语法定义 if(E) S else S 或者 if(E) S
2,语义
3,条件语句的执行
(1)计算表达式 E的值；
(2)判别：若 E之值为 true,执行紧随 E之后的语句 S，
然后无条件转去执行条件语句的后继语句；
(3)否则, E之值为 false,跳过紧随 E之后的语句 S而
执行 else之后的语句 S,然后执行条件语句的后继语句 。
4,目标代码设计
例 if(a＜ b) max=b； else max=a；
其中, a,b与 max都是整型变量 。
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
6.1 概况
6.2 说明部分的翻译
6.3 目标代码的生成
一、概况
二、虚拟机
三、控制语句的翻译
1.赋值语句
2.选择语句
3.循环语句
4.过程语句
第六章 语义分析与目标代码生成 1.语法定义 while (E) S 2,语义
3,条件语句的执行
(1)计算逻辑表达式 E之值；
(2) E为 true,执行语句 S,然后返回到步骤 1；
(3)E为 false时, 执行 while语句的后继语句 。
4,目标代码设计
例 while(n<10) 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,
6.1 概况
6.2 说明部分的翻译
6.3 目标代码的生成
一、概况
二、虚拟机
三、控制语句的翻译
1.赋值语句
2.选择语句
3.循环语句
4.过程语句
第六章 语义分析与目标代码生成 几个概念,活动,过程体的每次执行；
过程活动的生存期,是过程体的执行步骤序列；
活动记录,为管理过程的一次执行所需信息而设置的连续存储区域。
返回值 域, 有值函数的函数值，常用特定的寄存器返回。
实在参数 域,
控制链 域, 指向调用程序的活动记录。
访问链 域, 用以引用存于其它活动记录的非局部数据。
机器状态 域, 用来保存临调用过程时的机器状态信息,局部数据 域, 用来
存放过程一次执行时的局部数据。
临时数据 域, 存放过程执行时产生的中间结果等。
6.1 概况
6.2 说明部分的翻译
6.3 目标代码的生成
一、概况
二、虚拟机
三、控制语句的翻译
1.赋值语句
2.选择语句
3.循环语句
4.过程语句
第六章 语义分析与目标代码生成
1.语法定义 CALL id(Elist)
2,过程语句的执行
(1)为被调用过程的活动记录分配存储区域；
(2)计算过程语句参数表中各个实参的值, 并存放在活动记录中相应存 储位置；
(3)设置环境指针 (访问链等 ),使得被调用过程可访问外围过程的数据；
(4)保护调用过程的机器状态, 包括寄存器值与返回地址等 ；
(5)把被调用过程局部数据域初始化 ；
(6)把控制转移到被调用过程的入口代码处 。
6.1 概况
6.2 说明部分的翻译
6.3 目标代码的生成
6.4 源程序的内部中间表示
使用中间语言的优点,
1)中间表示与具体机器特性无关, 一种中间表示可以为生成多种不
同型号的目标机之目标代码服务；
2)可对中间表示做与机器无关的优化, 有利于提高目标代码的质量；
3)把源程序映射成中间表示, 再映射成目标代码的工作分在几个阶
段进行 。 有利于编译程序本身的开发, 有利于人员的分工, 等等 。
几种中间表示的方法, 抽象语法树, 逆波兰表示, 三元式序列与四
元式序列等 。
6.1 概况
6.2 说明部分的翻译
6.3 目标代码的生成
6.4 源程序的内部中间表示
一、抽象语法树
二、逆波兰表示
三、四元式序列
四、三元式序列
6.4 源程序的内部中间表示
一、抽象语法树
S∷=IF E THEN S ELSE S 条件语句 表达式 语句 语句
S∷=V,=E 赋值语句 左部 表达式
例 设有赋值语句 x=a+b*c
6.4 源程序的内部中间表示
一、抽象语法树
S∷=IF E THEN S ELSE S 条件语句 表达式 语句 语句
S∷=V,=E 赋值语句 左部 表达式
二、逆波兰表示 逆波兰表示是从抽象语法树按后根遍历法产生的
线性化表示 。
表达式 a+b*c/(d+e)的逆波兰表示
是 abc*de+/+
6.4 源程序的内部中间表示
一、抽象语法树
二、逆波兰表示
三、四元式序列
1.表示法约定
2.四元式序列之例
3.从四元式序列生成目标代码
6.4 源程序的内部中间表示
一、抽象语法树
二、逆波兰表示
三、四元式序列
1.表示法约定
2.四元式序列之例
3.从四元式序列生成目标代码
双目运算的一般形式：运算符 运算分量 运算分量 结果
其中，运算分量和结果可以是变量、常量或由编译程序
引进的临时变量。
6.4 源程序的内部中间表示
一、抽象语法树
二、逆波兰表示
三、四元式序列
1.表示法约定
2.四元式序列之例
3.从四元式序列生成目标代码
例 for i:=1 to 100 do s:=s+i；
展开为,
i:=1；
10:if i <= 100 then
begin s:=s+i；
i:=i+1；
goto 10
end；
四元式序列,
(1)(:=,1,/,i)
(2)(>,i,100,(6))
(3)(+,s,i,s)
(4)(+,i,1,i)
(5)(GO,(2),/,/)
(6)
6.4 源程序的内部中间表示
一、抽象语法树
二、逆波兰表示
三、四元式序列
1.表示法约定
2.四元式序列之例
3.从四元式序列生成目标代码
如果对于四元式的一切运算符都有对应的目标机器操作码,
从四元式序列生成目标代码的工作是容易实现的 。 主要问题是
运算分量与计算结果的存取问题, 在生成目标指令时, 要考虑
四元式中运算分量是在寄存器中还是在内存中, 当在寄存器中
时, 以后还会被使用否, 等等 。
6.4 源程序的内部中间表示
一、抽象语法树
二、逆波兰表示
三、四元式序列
四、三元式序列
1.表示法约定 运算符 运算分量 运算分量
2.三元式序列之例
6.4 源程序的内部中间表示
一、抽象语法树
二、逆波兰表示
三、四元式序列
四、三元式序列
1.表示法约定
2.三元式序列之例
例 for i:=1 to 100 do s:=s+i；
展开为,i:=1；
10:if i <= 100 then
begin s:=s+i；
i:=i+1；
goto 10
end；
四元式序列,(1)(:=,1,/,i)
(2)(>,i,100,(6))
(3)(+,s,i,s)
(4)(+,i,1,i)
(5)(GO,(2),/,/)
(6)
三元式序列,(1)(:=,1,i)
(2)(>,i,100)
(3)(GOT,(9),(2))
(4)(+,s,i)
(5)(:=,(4),s)
(6)(+,i,1)
(7)(:=,(6),i)
(8)(GO,(2),/)
(9)
习题 15
1,试画出表达式 (a+b)*(c－ d)－ (a*b+c)的抽象语
法树 。
2,试把表达式 (a+b)*(c－ d)－ (a*b+c)翻译成
(1)逆波兰表示
(2)四元式序列
(3)三元式序列
