Microsoft PowerPoint - 7-Semantic_IR12.ppt [兼容模式]

Transcription

1 中间代码生成 第七章 : 语义分析和中间代码生成 赵银亮 词法分析 语法分析 中间代码生成 中间代码的表示形式有多种 : 逆波兰表示三地址码 ( 三元式 四元式 ) 抽象语法树 P- 代码 属性文法是实现中间代码生成的常用手段 2012 本章内容 : 几种中间表示说明语句的翻译简单算术表达式和赋值句到四元式的翻译布尔表达式到四元式的翻译控制语句的翻译数组元素的引用过程调用 7.1 中间表示的概念 抽象语法树 vs 类目标代码 是否涉及目标机及运行时环境的信息 : 数据类型的尺寸 ; 寄存器前端 IR 后端变量的存储位置 是否使用符号表中的全部信息 : 作用域 嵌套层次变量的偏移量 其它用途 : 用于代码分析以产生高效目标代码用于多目标编译 1

2 7.1.1 后缀式 - 逆波兰表示 一个表达式 E 的后缀形式可以如下定义 : 如果 E 是一个变量或常量, 则 E 的后缀式是 E 自身 ; 如果 E 是 E 1 op E 2 形式的表达式, 其中 op 是任何二元操作符, 则 E 的后缀式为 E 1 E 2 op, 其中 E 1 和 E 2 分别为 E 1 和 E 2 的后缀式 ; 如果 E 是 (E 1 ) 形式的表达式, 则 E 1 的后缀式就是 E 的后缀式 运算对象出现的顺序相同 运算符按实际计算次序从左到右排列 对后缀式求值 后缀式的特点 : 逆波兰表示法不用括号 只要知道每个算符的目数, 对于后缀式, 不论从哪一端进行扫描, 都能对它进行唯一分解 适合于采用栈来求值 : 从左到右依次扫描后缀式中的各个符号, 每遇到运算对象, 就进栈 ; 每碰到 k 目运算符, 就弹出栈顶 k 个运算对象进行运算, 并将结果进栈 结束时, 栈顶为整个表达式的值 x/y^z-d*e A+B AB+ A+B*C ABC*+ x/y^z-d*e xyz^/de*- (a=0 b>3) (e x y) a0=b3> exy xyz^/de*- 把表达式翻译成后缀式的语义规则描述 补充 : 属性文法 产生式 E E (1) op E (2) E (E (1) ) E id 语义动作 E.code:= E (1).code E (2).code op E.code:= E (1).code E.code:=id 语义分析涉及到计算额外信息 ( 语法分析之外的信息 ); 这些信息与程序的语义有关 ; 编译阶段进行的语义分析叫静态语义分析 ; 构造符号表 ; 类型检查 ; 类型推理 ; E.code 表示 E 后缀形式 op 表示任意二元操作符 表示后缀形式的连接 2

3 进行语义分析的手段 语义表示上的困难性缺乏标准的方法描述语言的语义 ; 语义分析中的量和种类在不同语言间变化很大 ; 属性文法标识语言实体的属性 ; 写出属性方程 ( 或语义规则 ) 表达属性计算与语法规则之间的关系 ; 属性与属性方程的集合叫属性文法 ; 适用于语法制导的语言 ( 语义密切关联于语法 ) 属性 + 属性方程 = 属性文法 标识语言实体 (language entity) 的属性 An entity is something that has a distinct, separate existence, though it need not be a material existence. 写出属性方程 ( 语义规则 ): 表明如何把这些属性的计算跟文法规则相关联 ; 属性文法如何使用? 计算属性值运用属性文法进行语义分析 属性文法, 另一种定义 An attribute grammar is a context-free grammar that has been extended to provide context-sensitive information by appending attributes to some of its nonterminals. Each distinct symbol in the grammar has associated with it a finite, possibly empty, set of attributes. Each attribute has a domain of possible values. An attribute may be assigned values from its domain during parsing. Attributes can be evaluated in assignments or conditions. 属性 属性 : 是任意一个跟语言构造相关的特性 A language construct is a syntactically allowable part of a program that may be formed from one or more lexical tokens in accordance with the rules of a programming language. 属性举例 : 变量的类型 ; 表达式的值 ; 变量在存储器中的位置 ; 过程 (procedure) 的目标代码 ; 数中有效位数 3

4 属性的特点 属性所包含的信息 复杂程度 能够确定其值的时间区间等都有较大的范围 编译之前确定 数中有效位数 ; 编译过程中确定 执行之前确定 为语言构造指定属性 给定上下文无关文法, 为它的每个文法符号关联相关的 值 ( 称为属性 ), 以表示与这些文法符号相关的信息 使用的场合语法词法代码优化与生成 表达式的值 ; 动态分配的数据结构的地址 ; 属性的 binding 计算属性的值及将其跟语言构造建立联系的过程, 属性绑定发生的时刻称为绑定时间静态 : 在编译过程中 ( 执行之前 ) 动态 : 在执行时 变量的类型 ;(C/Pascal/Lisp Type Checker) 表达式的值 ;(Code/Constant Folding) 变量在存储器中的位置 ;(Static/ynamic Allocation) 过程 (procedure) 的目标代码 ;(Static) 数中有意义数字的个数 (Runtime Env.) 属性方程的表示 将属性值 a 与文法符号 X 联系起来, 记为 X.a 对于产生式规则 X 0 X 1 X 2 X n, 有 X i.a j = f ij (X 0.a 1,,X 0.a k,x 1.a 1,,X 1.a k,,x n.a 1,,X n.a k ) 其中,f ij 为数学函数, 则称为属性方程或语义规则一般采用表格方式表示 4

5 属性文法的表示形式 补充完 文法规则 语义规则 产生式规则 1 关联的属性方程 ( 多个 ) 产生式规则 n 关联的属性方程 ( 多个 ) 产生式 E E (1) op E (2) E (E (1) ) E id 语义动作 {E.code:= E (1).code E (2).code op} {E.code:= E (1).code} {E.code:=id} E E (1) op E (2) E (E (1) ) E id E.code:= E (1).code E (2).code op E.code:= E (1).code E.code:=id 数组 POST 存放后缀式 :k 为下标, 初值为 1 上述语义动作另一种形式 : 产生式 语义动作 E E (1) op E (2) {POST[k]:=op; k:=k+1} E (E (1) ) {} E i {POST[k]:=i; k:=k+1} 例 : 输入串 a+b+c 的分析和翻译 POST: a b + c + 后缀式的一般情况 op 为 k 目运算符, 则 op 作用于 e 1 e 2 e k 的结果用 e 1 e 2 e k op 来表示 例 : if a then if c-d then a+c else a*c else a+b a?c-d?a+c:a*c:a+b a cd- ac+ ac*? ab+? 5

6 后缀式表示中注意的问题 exy? 的语义期望 : e 不等于 0, 返回 x 值, 否则返回 y 值. 实际 : x 和 y 都要计算, 但只返回其中一个的值 问题 语义差异 : 运算对象无定义或者有副作用, 则后缀表示法不仅无效, 而且可能是错误的 ; 代码效率 后缀式表示实现 将后缀式表示存放在一维向量 POST[1..n] 中 引入转移操作 : p BR 无条件转至 POST[p] e p BZ 当 e 值为 0 转 POST[p], 其中 e 是某表达式 e 的后缀式表示 e1 e2 p BL 当 e1 <e2 时转向 POST[p] 类似地还可以定义 BN( 非 0 转 ) BP( 正号转 ) BM( 负号转 ) 后缀式表示实现 ( 例 ) IF e THEN s1 e p2 BZ s1 p2 BR e p2 BZ s1 p2: IF e THEN s1 ELSE s2 e p1 BZ s1 p2 BR p1:s2 p2 BR e p1 BZ s1 p2 BR p1:s2 p2: POST e p 1 BZ s 1 p 2 BR s 2 p 1 p 2 其中 e, s1, s2 是 e, s1, s2 的后缀式表示, p1 表示 s2 在 POST 中的开始位置,p2 表示该 IF 语句的后继 6

7 利用属性文法产生后缀式表示 属性 addr: 纪录运算对象的起始位置向量 POST 和指针 p E1 E2+T {E1.addr=E2.addr; POST[p]= + ; p++;} E T {E.addr=T.addr} T1 T2*F {T1.addr=T2.addr; POST[p]= * ; p++;} T F {T.addr=F.addr;} F (E) {F.addr=E.addr;} F id {F.addr=p; POST[p]=lookup(id); p++;} 步骤 符号栈 R 输入串 动作 后缀表示 0 # a +b*c# shift 1 #a + b*c# 归约 F->id;Sub6 a 2 #F + b*c# 归约 T->F;Sub4 a 3 #T + b*c# 归约 E->T;Sub2 a 4 #E + b*c# shift a 5 #E+ b *c# shift a 6 #E+b * c# 归约 F->id;Sub6 ab 7 #E+F * c# 归约 T->F;Sub4 ab 8 # E+T * c# shift ab 9 # E+T* c # shift ab 10 # E+T*c # 归约 F->id;Sub6 abc 11 # E+T*F # 归约 T->T*F;Sub3 abc* 12 #E+T # 归约 E->E+T;Sub1 abc*+ 13 #E # abc* 图表示法 a:=b*(-c)+b*(-c) 的图表示法 图表示法 AG 抽象语法树 assign assign 无循环有向图 (irected Acyclic Graph, 简称 AG) 对表达式中的每个子表达式,AG 中都有一个结点一个内部结点代表一个操作符, 它的孩子代表操作数在一个 AG 中代表公共子表达式的结点具有多个父结点 a + * b uminus b c 抽象语法树 * uminus c a + * b AG uminus c 7

8 抽象语法树与中间代码对应示例 对应的代码 : assign a + T 1 :=-c T 2 :=b*t 1 * * T 3 :=-c b uminus b c uminus c T 4 :=b*t 3 T 5 :=T 2 +T 4 a:=t 5 抽象语法树 例 :AG 与中间代码 assign a + * b uminus c AG 抽象语法树对应的代码 : T 1 :=-c T 2 :=b*t 1 T 3 :=-c T 4 :=b*t 3 T 5 :=T 2 +T 4 a:=t 5 AG 对应的代码 : T 1 :=-c T 2 :=b*t 1 T 5 :=T 2 +T 2 a:=t 5 产生赋值语句抽象语法树的属性文法 三地址代码 文法规则 S id:=e E E 1 +E 2 E E 1 *E 2 E -E 1 E (E 1 ) E id 语义规则 S.tree=mkNode(:=, mkleaf( id, id.place), E.tree) E.tree=mkNode(+, E 2.tree, E 2.tree) E.tree=mkNode(*, E 1.tree, E 2.tree) E.tree=mkNode(uminus, E 1.tree, nil) E.tree=E 1.tree F.tree=mkLeaf(id, id.place) 三地址代码 x:=y op z 三地址代码可以看成是抽象语法树或 AG 的一种线性表示 8

9 三地址语句示例 x:=y op z x:=op y x:=y goto L if x relop y goto L 或 if a goto L par x 和 call p,n, 以及返回语句 return y x:=y[i] 及 x[i]:=y 的索引赋值 x:=&y, x:=*y 和 *x:=y 的地址和指针赋值 例 : 2*a+(b-3) + * - 2 a b 3 t1 = 2 * a t2 = b 3 t3 = t1 + t2 t2 = b 3 t1 = 2 * a t3 = t2 + t1 产生临时变量 ; 临时变量跟抽象语法树的内结点对应 ; 语句的次序 ; 操作符扩充 ; 一个程序段的三地址代码表示 : read x; if 0 < x then fact := 1; repeat fact := fact * x; x := x 1 until x = 0; write fact end read x; t1 = x > 0 if_false t1 goto L1 fact = 1 label L2 t2 = fact * x fact = t2 t3 = x 1 x = t3 t4 = x == 0 if_false t4 goto L2 write fact label L1 halt 三地址码的实现 : 四元组 四元组 (op, arg1, arg2, result) op 是一个二元 ( 也可一元或零元 ) 运算符 arg1, arg2 分别为两个运算对象, 可以是变量 常数 临时变量等等 ( 可以缺省 ) 运算结果在 result 中跟符号表有关系 2*a+(b-3) (*, 2, a, T1) (, b, 3, T2) t1 = 2 * a t2 = b 3 (+, T1, T2, T3) t3 = t1 + t2 9

10 四元组举例 : read x; t1 = x > 0 if_false t1 goto L1 fact = 1 label L2 t2 = fact * x fact = t2 t3 = x 1 x = t3 t4 = x == 0 if_false t4 goto L2 write fact label L1 halt (rd,x,_,_) (gt,x,0,t1) (if_f,t1,l1,_) (asn,1,fact,_) (lab,l2,_,_) (mul,fact,x,t2) (asn,t2,fact,_) (sub,x,1,t3) (asn,t3,x,_) (eq,x,0,t4) (if_f,t4,l2,_) (wri,fact,_,_) (lab,l1,_,_) (halt,_,_,_) 三地址码的实现 : 三元组 (op, arg1, arg2) op 是一个二元 ( 也可一元或零元 ) 运算符 ; arg1, arg2 分别为两个运算对象 : 可以是变量 常数 临时变量等等 ( 可以缺省 ) ; 也可以是某个三元式的序号 ; 跟符号表有关系 2*a+(b-3) t1 = 2 * a t2 = b 3 t3 = t1 + t2 (1) (*, 2, a) (2) (, b, 3) (3) (+, (1), (2)) 三元组举例 : (0) (rd,x,_) (1) (gt,x,0) (2) (if_f,(1),11) (3) (asn,1,fact) (4) (mul,fact,x) (5) (asn,(4),fact) (6) (sub,x,1) (7) (asn,(6),x) (8) (eq,x,0) (9) (if_f,(8),(4)) (10) (wri,fact,_) (11) (halt,_,_) (rd,x,_,_) (gt,x,0,t1) (if_f,t1,l1,_) (asn,1,fact,_) (lab,l2,_,_) (mul,fact,x,t2) (asn,t2,fact,_) (sub,x,1,t3) (asn,t3,x,_) (eq,x,0,t4) (if_f,t4,l2,_) (wri,fact,_,_) (lab,l1,_,_) (halt,_,_,_) 产生三地址码的属性文法 例 : E id=e A A A+F F F (E) num id 属性 name: 记录临时变量名 属性 code: 记录已生成的代码 10

11 方法 1: 用符号串表示代码 方法 2: 用符号串表示代码 E 1 id=e 2 E A A 1 A 2 +F A F F (E) F num F id E 1.name=id.strval E 1.code=E 2.code++id.strval = E 2.name E.name=A.name; E.code=A.code A 1.name=newtemp() A 1.code=A 2.code++F.code++ A 1.name = A 2.name + F.name A.name=F.name; A.code=F.code F.name=E.name; F.code=E.code F.name=num.strval; F.code= F.name=id.strval; F.code= 语法规则 S id:=e E -E 1 E E 1 +E 2 E (E 1 ) E id 语义规则 S.code=E.code gen(id.place := E.place) E.place=newtemp() E.code=E 1.code gen(e.place := minus E 1.place) E.place=newtemp() E.code=E 1.code E 2.code gen(e.place := E 1.place + E 2.place) E.place=E 1.place ; E.code=E 1.code E.place=id.place; E.code= ++ 串连接, 包括 1 个换行 ; 串连接, 包括 1 个空格 ++ 串连接, 包括 1 个换行 ; 串连接, 包括 1 个空格 7.2 说明语句的翻译 例 6.3 变量声明 TL T int float L id, L id 文法规则 TL T int T float L 1 id, L 2 L id 语义规则 L.dtype=T.dtype T.dtype=integer T.dtype=real id.dtype=l 1.dtype L 2.dtype=L 1.dtype id.dtype=l.dtype 题目 : 求一个 3*3 矩阵对角线元素之和 main() { int i,j; float a[3,3],sum; sum=0; printf("please input rectangle elements:\n"); for(i=0;i<3;i++) for(j=0;j<3;j++) scanf("%f",&a[i,j]); for(i=0;i<3;i++) sum=sum+a[i,i]; printf( Sum of the diagonal elements is %6.2f\n",sum); } 过程中的说明语句 P ; TL T int float L id, L id 文法规则语义规则 P offset=0 1 2 ; 3 TL T int T float L 1 id, L 2 L id L.type=T.type; L.width=T.width T.type=integer;T.width=4 T.type=real;T.width=8 题目 : 求一个 3*3 矩阵对角线元素之和 main() { int i,j; float a[3,3],sum; sum=0; printf("please input rectangle elements:\n"); for(i=0;i<3;i++) for(j=0;j<3;j++) scanf("%f",&a[i,j]); for(i=0;i<3;i++) sum=sum+a[i,i]; printf( Sum of the diagonal elements is %6.2f\n",sum); } lookup(id.name, L 1.type, offset); L 2.type=L 1.type; L 2.width=L 1.width; offset=offset+l 1.width lookup(id.name, L.type, offset); offset=offset+l.width 11

12 补充 : 综合属性与继承属性 一个属性是综合属性是指在语法树中, 该属性的值由其孩子结点的属性值计算而得 a 是综合属性, 若给定 A X 1 X 2 X n, 唯一与其关联的属性方程中 a 在等号左边 A.a = f(x 1.a 1,,X 1.a k,,x n.a 1,,X n.a k ) 继承属性 不是综合属性的属性是继承属性 语法树中, 一个结点的继承属性由此结点的父结点和或兄弟结点的某些属性确定 a A A S- 属性文法所有属性都是综合属性的属性文法 a B a (a) Inheritance from parent to siblings C a B a (b) Inheritance from sibling to sibling C 补充 : 依赖图 TL dtype L L.dtype T int float L id, L id T dtype dtype L dtype id, dtype L id.dtype L.dtype 文法规则 语义规则 TL L.dtype=T.dtype T int T.dtype=integer T float T.dtype=real L 1 id, L 2 id.dtype=l 1.dtyp e L 2.dtype=L 1.dtyp e L id id.dtype=l.dtype T.dtype L.dtype id.dtype L.dtype L.dtype L.dtype id.dtype T dtype dtype float dtype id, float x,y L dtype dtype L id 12

13 作用域 P ; TL proc id;;s func id;;s T int float L id, L id program sort(input,output) var a: array[0..10] of int; x:int; proc readarray; var i:int; begin a.end; proc exchange(i,j:int); begin x:=a[i];a[i]:=a[j];a[j]=x end; proc quicksort(m,n:int); var k,v:int; func partition (y,z:int):int; var i,j:int; begin a v exchange(i,j); end; begin end; begin end. header nil header Sort a x readarray exchange quicksort header i j i header header k v partition program sort(input,output) var a: array[0..10] of int; x:int; proc readarray; var i:int; begin a.end; proc exchange(i,j:int); begin x:=a[i];a[i]:=a[j];a[j]=x end; proc quicksort(m,n:int); var k,v:int; func partition (y,z:int):int; var i,j:int; begin a v exchange(i,j); begin end; begin end. 属性及过程的定义 mktable(tab) 创建一个符号表, 父表指针为 tab; Enter(tab,name,type,offset) 在 tab 所指符号表中为名字 name 建立一个登记项, 类型 type 和相对地址 offset 填入该项中 ; addwidth(tab,width) 在 tab 所指符号表表头中记录下该表中所有名字占用的总宽度 ; enterproc(tab, name, newtab) 在 tab 所指符号表中为名字 name 的过程建立一个登记项, 参数 newtab 指向 name 的符号表 处理嵌套过程中的说明语句 ( 方法 1) P M M ε addwidth(pop(s_tab), pop(s_offset)) t:=mktab(nil); push(t, s_tab); push(0,s_offset) ; t:= pop(s_tab); addwidth(t,pop(s_offset)) proc enterproc(top(s_tab), id.name, t) id;n 1 ;S id:t Enter(top(s_tab), id.name, T.type, top(s_offset)) push(pop(s_offset)+t.width, s_offset) N ε t:=mktab(top(s_tab)) pop(s_) 弹出 s_ 栈顶元素 ;top(s_) 返回 s_ 栈顶元素 ;push(e,s_) 压入 e 到栈 s_. push(t, s tab); push(0,s offset) 13

14 ( 方法 1) P M M ε ; proc id;n 1 ; S id:t N ε P M addwidth(pop(s_tab), pop(s_offset)) t:=mktab(nil); push(t, s_tab); push(0,s_offset) t:= pop(s_tab); addwidth(t,pop(s_offset)) enterproc(top(s_tab), id.name, t) enter(top(s_tab), id.name, T.type, top(s_offset)) push(pop(s_offset)+t.width, s_offset) t:=mktab(top(s_tab)); push(t, s_tab); push(0,s_offset) program sort(input, var a: array[0..10] x:int; proc readarray; N var i:int; begin a.end; proc exchange(i,j begin x:=a[i];a[i]:=a end; N proc quicksort(m, var k,v:int; func partition N var i,j:int; begin a v e begin end; begin end. P L id:t ( 方法 2) L L 1 L 2 ; proc id;l;s P L L L L.intab=mktab(nil); L.ioffs=0 P.symtab=L.outtab.outtab=.intab L Enter(.outtab, id.name, T.type,.ioffs).ooffs=.ioffs+T.width addwidth(.outtab,.ooffs)).intab=l.intab; L.outtab=.outtab.ioffs=L.ioffs;L.ooffs=.ooffs L 2.intab=L 1.intab;.intab=L 2.outtab L 1.outtab=.outtab; L 2.ioffs=L 1.ioffs L.ioffs=L 2.ooffs; L 1.ooffs=.ooffs L.intab=mktab(.intab); L.ioffs=0 addwidth(l.intab,l.ooffs)).outtab=.intab;.ooffs=.ioffs enterproc(.intab,id.name,.outtab) L L program sort(input, var a: array[0..10] x:int; proc readarray; var i:int; begin a.end; proc exchange(i,j begin x:=a[i];a[i]:=a end; proc quicksort(m, var k,v:int; func partition var i,j:int; L L begin a v e begin end; begin end. P L id:t ( 方法 2) L L 1 L 2 ; proc id;l;s L.it=mktab(nil); L.io=0 P.st=L.ot.ot=.it Enter(.ot, id.name, T.type,.io).oo=.io+T.width addwidth(.ot,.oo)).it=l.it; L.ot=.ot.io=L.io;L.oo=.oo ot outtab io ioffs nil 4 it inttab oo ooffs 说明语句的翻译的小结 P st L 2.it=L 1.it;.it=L 2.ot L 1.ot=.ot; L 2.io=L 1.io.io=L 2.oo; L 1.oo=.oo L.it=mktab(.it); L.io=0.ot=.it;.oo=.io addwidth(.ot,.oo)) enterproc(.ot,id.name,l.ot) it io x it ot L io oo it ot io=0l oo ot oo it ot io oo x int 0 f it ot proc f ; L ; S io=0 oo : int 简单变量的类型偏移量 ( 以过程为单位 ) 创建符号表符号表中添加登记项 结构型变量 ( 在后面介绍 ) 数组结构指针等 14

15 7.3 赋值语句的翻译 翻译赋值语句和算术表达式的属性文法类型转换数组处理 前面介绍过的一个例子 语法规则语义规则 S id:=e S.code=E.code gen(id.place := E.place) E -E 1 E.place=newtemp() E.code=E 1.code gen(e.place := minus E 1.place) E E 1 +E 2 E.place=newtemp() E.code=E 1.code E 2.code gen(e.place := E 1.place + E 2.place) E (E 1 ) E.place=E 1.place ; E.code=E 1.code E id E.place=id.place; E.code= ++ 串连接, 包括 1 个换行 ; 串连接, 包括 1 个空格 属性及过程定义 ( 产生四元组 ) 例 : 翻译简单赋值语句为四元组的属性文法 NewTemp() 函数过程, 返回一个新临时变量名 ( 一般用整数表示 ); Lookup(name) 以 name 为名字查符号表 : 查到返回入口, 否则加入该名字到符号表中并返回入口 ; E.place 表示存放 E 值的变量名在符号表的入口或者整数 ( 临时变量 ); Gen(op, arg1, arg2, result) 语义过程, 建立四元式 (op, arg1, arg2, result) 并填入四元式表中 A V:=E {if E.place=err or V.place=err then A.place=err else {A.place =ok; Gen(:=,E.place,nil,V.place)}} E E 1 +E 2 {if E 1.place=err or E 2.place=err then E.place=err else {E.place=NewTemp(); Gen(+,E 1.place,E 2.place,E.place)}} E E 1 *E 2 {if E 1.place=err or E 2.place=err then E.place=err else {E.place=NewTemp(); Gen(*,E 1.place,E 2.place,E.place)}} E (E 1 ) {E.place=E 1.place} E V {E.place=V.place} E num {E.place=lexval(num)} V id {V.place=(p:=Lookup(id.name))? p : err} 15

16 去掉错误处理部分 A V:=E E E 1 +E 2 {Gen(:=,E.place,nil,V.place)} {E.place=NewTemp(); Gen(+,E 1.place,E 2.place,E.place)} E E 1 *E 2 {E.place=NewTemp(); Gen(*,E 1.place,E 2.place,E.place)} E (E 1 ) E V E num V id {E.place=E 1.place} {E.place=V.place} {E.place=lexval(num)} {V.place=Lookup(id.name)} 类型转换 A V:=E {Gen(:=,E.place,nil,V.place);} E E 1 +E 2 {E.place=NewTemp(); Addr 为实数加 if E 1.type=int then if E 2.type=int then Gen(addi,E 1.place,E 2.place,E.place) else {tmp=newtemp(); Gen(itor, E 1.place, nil, tmp);gen(addr,tmp,e 2.place,E.place);} else if E 2.type=int then {tmp=newtemp(); Gen(itor, E 2.place, nil, tmp); Gen(addr,E 1.place,tmp,E.place);} else Gen(addr, E 1.place,E 2.place,E.place); E.type= } E E 1 *E 2 { 跟上面相似, 将 addi 和 addr 分别换成 muli 和 mulr} E (E 1 ) {E.place=E1.place; E.type= } E V {E.place=V.place; E.type= } E intnum realnum {E.place=lexval(num); E.type= } V id {V.place=lookup(id.name; V.type= } 数组元素引用 数组说明与下标变量的语义 数组说明与下标变量的语义地址计算公式四元式中数组元素表达形式赋值语句中数组元素的翻译 数组说明 float a[size] ; int i,j; 数组元素引用 a[i+1]=a[j*2]+3; 数组说明 var a: array[0..10] of int; 数组元素引用 a[i]:=a[j]+1; i,j:int; 数组说明 real x(-13,13) integer i,j 数组元素引用 x[i]=x[j]+1 数组元素的存放区域如何安排? 如何确定数组元素的偏移量? 16

17 数组说明与下标变量的语义 a[i+1] a + (i+1) * sizeof(int) a[t] base_address(a) + (t-lower_bound(a))*element_size(a) (1) 地址计算公式 对于一维数组 A[i]: 下标的变化范围 : l i u 连续存储区的首址 :base, 每个数组元素占用 w 个单元则 A[i] 地址为 :base+(i-l)*w A[i] 地址 : base+(i-l)*w=(base-l*w)+i*w 固定部分 :base-l*w ( 在数组说明时即可确定 ) 变化部分 :i*w ( 在数组引用时确定, 即动态确定 ) (2) 数组说明 A[l:u] 的表示 符号表项 名字类型地址 A 数组 内情向量表 1 base Type/w C l u d 元素存储区域 A[1] A[2] 对于一维数组元素引用形式 A[i], 该元素的存储位置为 : base+(i-l)* w= base - C + i*w 地址计算公式 ( 续 ) 对于二维数组 A[i,j]: 下标的变化范围 : l 1 i u 1 ; l 2 j u 2 连续存储区的首址 :base, 每个数组元素占用 w 个单元则 A[i,j] 地址为 :base+[(i-l 1 )*(u 2 -l 2 )+j-l 2 ]*w base+[(i-l 1 )*(u 2 -l 2 )+j-l 2 ]*w =[base+(-l 1 *(u 2 -l 2 )-l 2 )*w] + [(i*(u 2 -l 2 )+j)*w] 固定部分 : base;(-l 1 *(u 2 -l 2 )-l 2 )*w 变化部分 : (i*(u 2 -l 2 )+j)*w 用维长表示 :(i*d 2 +j)*w 17

18 对于多维数组 A[i 1,i 2,,i n ]: 下标的变化范围 : l 1 i 1 u 1 ; ; l n i n u n 连续存储区的首址 :base, 每个数组元素占用单元 w 个 则 A[i 1,i 2,,i n ] 地址为 : base+(( ((i 1 -l 1 )*d 2 +(i 2 -l 2 ))*d 3 +(i 3 -l 3 ) ) )d n +(i n -l n ))*w =base-(( ((l 1 *d 2 +l 2 )*d 3 +l 3 ) )d n +l n )*w+ 注意 : CONSTPART 与数组各维的维长 d i 和数组的首址 base 相关 ( 在数组说明时可确定 ); VARPART 部分与下标变量的每个下标相关 ( 在运行时才能确定 ) 计算数组元素的地址时分别计算出 CONSTPART 和 VARPART, 对前者静态算出具体值, 而对后者则产生计算代码 i 1 *d 2 * *d n +i 2 *d 3 * *d n + +i n = base- ConstPart+ ( ((i 1 )*d 2 +i 2 )*d 3 +i 3 )*d 4 +i 4 ) )*d n +i n 静态数组 A[l 1 :u 1,, l n :u n ] 表示形式 计算可变部分 对于不变部分 Constpart, 产生代码 { T1 := base-c }; 符号表项名字类型地址 A 数组 内情向量表 n base Type/w C l 1 u 1 d 1 l n u n d n 数组元素存储区域 A[1,1,,1] A[1,1,,2] 可变部分 Varpart, 产生代码形如 {T:=Varpart}; 所以数组引用 A[i 1, i k ] 的地址为 T + T1, 使用变址指令 : 形式为 T1[T] (T1 为基址,T 为偏移量 ) 如此, 四元式的形式如下 : 变址取值 X:= T1[T] ( =[], T1[T], _, X) 变址存储 T1[T] := X ( []=, X, _, T1[T]) 18

19 (3) 赋值语句中的数组元素翻译 A V:= E V i[l] i L L,E E E E+E (E) V B A 数组 数组 1 base T B C l u d 2 base 2 T A C 2 l 1 u 1 d 1 l 2 u 2 d 2 文法允许数组元素嵌套定义,B[i]:=A[v,B[j]+w] 可变部分的计算 V i[l] i L L,E E e 1 =t 1 e m =e m-1 *d m +t m VARPART=( ((i 1 )*d 2 +i 2 )*d 3 +i 3 )*d 4 +i 4 ) )*d n +i n L.place V L] i L L,E i[e limit(i,k),k=3 对下标变量的处理 V L] i L L,E i[e e 1 =t 1 e m =e m-1 *d m +t m e2 L e3 L e4 L base-c w*e4v e1 L t1 t2 a [ E, E, E t3, E t4 ] 属性定义 L.arr 该数组名在符号表中的入口位置 L.dim 数组维数计数器, 随着归约新的下标而增加 L.place 存放已形成的 VARPART 部分, 可能是变量或临时变量 Limit(A,k) 函数过程, 数组 A 的第 k 维长度为 d k V.place 对于简单变量记录该变量名在符号表中的位置对于下标变量记录保存 CONSTPART 的那个临时变量 V.offset 简单变量 NULL( 用于区分简单变量和下标变量 ) 下标变量保存 VARPART 的临时变量 19

20 L.arr (3) 赋值语句中的数组元素翻译 A V:= E V L] i L L,E i[e E E+E (E) V A 数组 L.dim n T base C V.place A V:=E {if V.offset=NULL then Gen(:=,E.place,_,V.place) else Gen([]=,E.place,_,V.place[V.offset])} E E 1 +E 2 { t:=newtemp(); Gen(+,E 1.place,E 2.place,t); E.place := t } E (E 1 ) { E.place := E 1.place } L.place V.offset l 1 u 1 d 1 l n u n d n Limit(A,1) Limit(A,n) E V { if (V.offset=NULL) then E.place := V.place; else { t:=newtemp(); Gen (=[],V.place[V.offset],_,t); E.place:=t; } } V L] { t:=newtemp(); Gen(-,acc_base(L.arr),acc_C(L.arr),t); V.place:=t; t:=newtemp(); Gen(*, acc_w(l.arr), L.place, t); V.offset :=t } 例 : a 是一个 10*20 的数组,a[i+2,j+1]:= m+n 的翻译 A V := E V i { V.place:= Entry(i); V.offset:= NULL; } L ] m+n L L 1,E { t1:=newtemp(); k:= L 1.dim + 1; d k :=Limit(L 1.arr,k); Gen(*,L 1.place,d k,t1); t2:= NewTemp(); Gen(+,E.place,t1,t2); L.arr := L 1.arr; L.place := t2; L.dim := k; } L i[e { L.place := E.place; L.dim := 1; L.arr := Entry(i) } a L, [ E i+2 A V:= E V L] i L L,E i[e E E+E (E) V E j+1 (+, i, 2, T1) (+, j, 1, T2) (*, T1, 20, T3) (+, T2, T3, T4) (-, a, 21, T5) (*, 4, T4, T6) (+, m, n, T7) ([]=, T7, _,T5[T6]) 20

21 7.4 布尔表达式的翻译 布尔表达式的语义布尔表达式的求值布尔表达式作为条件的处理 布尔表达式的语义 文法 :E E E E E E (E) i i rop i C 语言 : &&! < == > <= >=!= if(1 < i && i < 10)... Pascal: AN OR NOT < = > <= >= if (x = 0) AN (a = 2) then... Fortran 逻辑表达式 :.AN..OR..NOT..LT..EQ..GT..LE..GE..NE. b = a.an. 3.LT. 5/2 布尔表达式的语义 ( 续 ) 布尔算符的优先级 : 顺序 :,, ; 其中 和 服从左结合 另外所有关系符的优先级相同, 高于任何布尔算符, 低于任何算术算符 由于大部分体系结构没有内置的布尔类型, 所以用 0 和 1( 或非 0) 分别表示 False 和 True 布尔表达式在语言中的作用 求值 logical a, b a =.TRUE. b = a.an. 3.LT. 5/2 作为控制语句中的条件 if(1 < i && i < 10)... 21

22 7.4.2 布尔表达式的求值 基本求值算法的实现 基本算法 : 如同算术表达式求值一样, 一步步地计算各部分的值, 进而计算出整个表达式的值 E E 1 E 2 E E 1 E 2 {E.place=newtemp(); gen(, E 1.place, E 2.place, E.place} {E.place=newtemp(); gen(, E 1.place, E 2.place, E.place} 例 A B C= (=, C,, T1) (, B, T1, T2) (, A, T2, T3) E E E (E 1 ) E i {E.place=newtemp(); gen(, E.place, NIL, E.place} {E.place=E 1.place} {E.place=i.name} E i 1 rop i 2 {E.place=newtemp(); gen(rop, i 1.place, i 2.place, E.place)} 布尔表达式的求值 ( 续 ) 短路算法 : A B if A then true else B A B if A then B else false A if A then false else true if((p!=null)&&(p->val==0)) 与基本算法的差别 : 运算量减少适用范围广 短路算法的实现问题 求值 : 转换成条件语句求值 A B if A then true else B A B if A then B else false A if A then false else true 作为条件 : 等价地转换成嵌套 if 语句 if E 1 E 2 then S1 else S2 if E 1 then if E 2 then S1 else S2 else S2 if E 1 E 2 then S1 else S2 if E 1 then S1 else if E 2 then S1 else S2 if E then S1 else S2 if E then S2 else S1 22

23 7.4.3 布尔表达式作为条件的处理 例 if A B< then S1 else S2 真出口, 假出口 if E 1 then if E 2 then S1 else S2 else S2 if E 1 then if E 2 then goto L-true else goto L-false else goto L-false; L-true: S1; goto L-next; L-false: S2; L-next: if E 1 then S1 else if E 2 then S1 else S2 if E 1 then goto L-true else if E 2 then goto L-true else goto L-false; L-true: S1; goto L-next; L-false: S2; L-next: if E then S1 else S2 if E then goto L-false else goto L-true; L-true: S1; goto L-next; L-false: S2; L-next: {E} 转向 E 为假时的目标 转向 E 为真时的目标 (1) (jnz,a,_,5) (2) (j,_,_,3) (3) (j<,b,,5) (4) (j,_,_,p+1) (5) {S1} (p) (j,_,_,q) (p+1) {S2} (q) { 下一语句 } 文法修剪 回填真假链的方法 E E 队列法 设 p q r 三条四元式均要转向 t 四元式 E G1: E-> E E E E E (E) i i rop i E G2: E -> E^ E E E E (E) i i rop i 填 E 真链 E^ -> E E 填 E 假链 -> E p( ). q( ). r( ). t( ) p q r Q.rear Q.front 23

24 回填真假链的方法 - 拉链返填 拉链返填法 ( 续 ) p(_,_,_,0). q(_,_,_,_) q(_,_,_,p) pq r p(_,_,_,0) p(_,_,_,t). q(_,_,_,p) q(_,_,_,t) rqp.ṙ(_,_,_,_).ṙ(_,_,_,q).ṫ(_,_,_,_).ṙ(_,_,_,q).ṙ(_,_,_,t).ṫ(_,_,_,_) qp 例 a x+y<0? G2: E E^E E E E (E) i i rop i E^ E E E b c z==8?? (jnz,a,-,3) (j,-,-,?) (jnz,a,-,?) (j,-,-,?) (+,x,y,t1) (jlz,t1,-,4) (j,-,-,?) (jnz,c,-,?) (j,-,-,6) (==,z,8,t2) (jnz,t2,-,?) (j,-,-,?)?? (jnz,a,-,3) (j,-,-,0) (jnz,a,-,0) (j,-,-,2) (+,x,y,t1) (jlz,t1,-,4) (j,-,-,0) (jnz,c,-,0) (j,-,-,6) (==,z,8,t2) (jnz,t2,-,4) (j,-,-,3) 属性及过程定义 nxq 下一个四元组的编号 merg(p, q) 把 p 链链接到 q 链尾, 返回 q bp(p, t) 把 p 链上所有四元组的第 4 区均回填为 t E.tc E 的代码中需回填真出口的那些四元组构成的链表 E.fc E 的代码中需回填假出口的那些四元组构成的链表 24

25 nxq 下一个四元组的编号 bp 回填 tc 或 fc merg 合并两个 tc 或 fc E i {E.tc=nxq; Gen(jnz,i,_,0); E.fc=nxq; Gen(j,-,-,0);} E^ E 1 {bp (E 1.tc, nxq); E^.fc=E 1.fc;} E E 1 {bp (E 1.fc, nxq); E.tc=E 1.tc;} E E^ E 1 {E.tc=E 1.tc; E.fc=merg (E^.fc,E 1.fc); } E E E 1 {E.fc=E 1.fc; E.tc=merg (E.tc,E 1.tc); } E i 1 rop i 2 {E.tc=nxq; Gen(jrop,i 1,i 2,0); E.fc=nxq; Gen(j,-,-,0);} E (E 1 ) {E.fc=E 1.fc; E.tc=E 1.tc;} E E 1 {E.tc=E 1.fc; E.fc=E 1.tc;} E 例 :(x a<b c=d ) e>f E E^E E E E (E) i i rop i E^ E E E E 5 6 x E^ 1 2? 2 E 3 4 ( E 5 6 ) E a 3? E < 3 4 b E^?6 c E E 7 8 = 5 6 E 7 8 e d > E->i {E.tc=nxq; Gen(jnz,i,_,0); E.fc=nxq; Gen(j,-,-,0);} E^->E 1 {bp (E 1.tc, nxq); E^.fc=E 1.fc;} E ->E 1 {bp (E 1.fc, nxq); E.tc=E 1.tc;} E-> E^ E 1 {E.tc=E 1.tc; E.fc=merg (E^.fc,E 1.fc); } E-> E E 1 {E.fc=E 1.fc; E.tc=merg (E.tc,E 1.tc); } f (jnz, x, -, 0) (j,-,-,0) (j<, a, b, 0) (j,-,-,0) (j=, c, d, 0) (j,-,-,0) (j>, e, f, 0) (j,-,-,0) (3) (2) (6) (5) (7) (5) (3) (7) 7.5 控制语句 标号和转移语句 分支与循环语句 标号和转移语句 标号的两种使用方法 L: S Goto L 语言中允许标号先定义后使用, 也允许先使用后定义 25

26 1 标号先定义后引用 L1 : S1 Goto L1 遇到 L1 : S1 符号表 名字 类型 定义否 地址 L1 标号 定义 P 1 P 1 : (,,,) 遇到 Goto L1 (j, _, _, P 1 ) 设标号对应的四元组从编号 P 1 开始 2 标号先引用后定义 q1 q2 q3 goto L2 goto L2 L2 : S2 名字类型 定义地址 q1 (j, _, _, 0 ) q3 q2 (j, _, _, q1 ) q3 L2 标号 未 q1 q2 q3 1 遇到 goto L2, 填符号表, 未定义, 把 NXQ 填入 L2 的地址部分, 作为链头 产生 ( j, _, _, 0) 2 遇到 goto L2, 查到未定义, 取符号表中 L2 的地址 q1 填入四元式 q2:(j, _, _,q1), 将 q2 填入符号表 3 遇到 L2:S2, 就可以回填 一般而言, 带标号语句产生式 S Label S Label i: Label i: 的语义动作 : 1. 若 i 所指的标识符 ( 假定为 L) 不在符号表中, 则把它填入, 置类型为 标号, 定义否 为 已, 地址为 NXQ 2. 若 L 已在符号表中, 但 类型 不为 标号 或者 定义否 为 已, 则报告出错 3. 若 L 已在符号表中, 则把标志 未 改为 已, 然后, 把地址栏中的链头 ( 记为 q) 取出, 同时把 NXQ 填在其中, 最后, 执行 bp(q,nxq) 分支与循环语句 if E then S1 else S2 if E then goto L-true else goto L-false; L-true: S1; goto L-next; L-false: S2; L-next: E S1 S2 S3 E.tc, E.fc; 回填 E.tc S1.next; 回填 E.fc S2.next; E,S1 和 S2 代码是相邻的, 共同构成 S 代码 S.next 26

27 E S1 S2 S3 F2 V1 V2 V3 if E then S1 else S2; S3; if E then begin if F1 then U1 else U2; U3 end else S2; F1 S3; U1 U2 U3 if E then begin if F1 then U1 else U2; U3 end else begin if F2 then V1 else V2; V3 end S3; E S1 S2 S3 F1 U1 U2 U3 规则 S if E then S1 else S2 E.true:=newlabel(); E.false:=newlabel(); S1.next:=S.next; S2.next:=S.next; S.code:=E.code gen(e.true : ) S1.code gen( goto S.next) gen(e.false : ) S2.code if E then begin if F1 then U1 else U2; U3 end else S2;S3; E E F1 规则 S if E then S1 else S2 F1 规则 S if E then S1 S1 S2 S3 U1 U2 E.true:=newlabel(); E.false:=newlabel(); S1.next:=S.next; S2.next:=S.next; S.code:=E.code gen(e.true : ) S1.code gen( goto S.next) gen(e.false : ) S2.code S1 S2 S3 U1 E.true:=newlabel(); E.false:= S.next; S1.next:=S.next; S.code:=E.code gen(e.true : ) S1.code if E then begin if F1 then U1 else U2 end else S2;S3; if E then begin if F1 then U1 end else S2;S3; 27

28 产生三地址码的属性文法 E S1 S2 规则 S while E do S1 S.begin:=newlabel(); E.true:=newlabel(); E.false:=S.next; S1.next:=S.begin; S.code:=gen(S.begin : ) E.code gen(e.true : ) S1.code gen( goto S.begin) S if E then S1 S if E then S1 else S2 S while E do S1 E.true:=newlabel(); E.false:=S.next; S1.next:=S.next; S.code:=E.code gen(e.true : ) S1.code E.true:=newlabel(); E.false:=newlabel(); S1.next:=S.next; S2.next:=S.next; S.code:=E.code gen(e.true : ) S1.code gen( goto S.next) gen(e.false : ) S2.code S.begin:=newlabel();E.true:=newlabel( ); E.false:=S.next;S1.next:=S.begin; S.code:=gen(S.begin : ) E.code gen(e.true : ) S1.code gen( goto S.begin) while E do S1;S2; 采用四元组实现时需要对其中的 goto 语句进行处理 嵌套条件语句的拉链返填处理 在四元组表示中 newlabel() 是目标位置的首地址 : if E then S1 else S2 语句中 E 的真假出口的目标位置分别是 S1 和 S2 if E then S1 语句中 E 的真假出口的目标位置分别是 S1 和下一条语句 if E then S1 [else S2] 语句中 S1 和 S2 的后续目标位置是该 if 语句下一条语句嵌套时下一条语句指外层该语法单位的后续目标位置 while E do S1 语句中 E 的真假出口的目标位置分别是 S1 和下一条语句 后续目标的地址只有到那个目标被归约时才知道 文法修剪 S if E then S if E then S else S while E do S begin L end A L L; S S 属性 : tc, fc ( 真假出口 ) chain ( 后续目标 )next quad (While 条件 ) S C S T p S W d S begin L end C 和 S 后续目标相同 T p 和 S 后续目标相同 S C A if E then S C if E then T p CS else W d W E do E 真出口已知 C 后续目标已知 S W while L L s S S T p C if E th S el S L s L; 28

29 C 和 S 后续目标相同 S C S T p S T p 和 S 后续目标相同 W d S begin L end A E 真出口已知 C if E then T p CS else C 后续目标已知 W d W E do W while L L s S S L s L; {S.chain := merg( C.chain, S (1). chain)} {S.chain := merg(t p.chain, S (1). chain)} {bp (E.tc, nxq); C.chain := E.fc} if 语句 {q:=nxq; Gen(j, _, _, 0); bp(c.chain,nxq); T p.chain:=merge(s.chain,q)} 示例 C if E then { bp (E.tc, nxq); C.chain := E.fc; } T p C S (1) else { q := nxq; Gen(j, _, _, 0); bp(c.chain,nxq); T p.chain := merge(s (1).chain,q);} S T p S (1) { S.chain := merge(t p. chain, S (1). chain;} IF E THEN S (1) ELSE S (2) C T P S E 的代码 S (1) 的代码 q: ( j, _, _, 0) S (2) 的代码 while 语句 S C S T p S W d S S begin L end W d A W C if E then T p CS else while E do S W d W E do W 条件已知 W while { W.quad := nxq } L L s S S L s L; S 后续目标已确定 { bp(s (1).chain,W d.quad); Gen(j, _, _, W d.quad); S.chain := W d.chain} W 循环体已知 {bp (E.tc,nxq); W d.chain := E.fc; W d.quad := W.quad} 复合语句 S C S T p S begin W d S S begin L end A L C if E then L s T p CS else L S ; S W d W E do end W while L L s S S L s L; L 后续就是 S 后续 A 后续为空 S 后续就是 L 后续 S 后续就是 L 后续 L 的后续已知 29

30 C if E then { bp (E.tc, nxq); C.chain := E.fc; } S C S (1) { S.chain := merg(c.chain, S (1). chain);} T p C S (1) else { q := nxq; Gen(j, _, _, 0); bp(c.chain,nxq); T p.chain := merge(s (1).chain,q);} S T p S (1) { S.chain := merge(t p. chain, S (1). chain;} W while { W.quad := nxq; } W d W E do { bp (E.tc,nxq); W d.chain := E.fc; W d.quad := W.quad ;} S W d S (1) { bp(s (1).chain,W d.quad); Gen(j, _, _, W d.quad); S.chain := W d.chain;} L S { L.chain := S.chain;} L s L; { bp(l.chain,nxq); } L L s S (1) { L.chain := S (1).chain;} S begin L end { S.chain := L.chain;} S A { S.chain := 0;} 空链 if E then while E (1) do S (1) else S (2) C W T P p C if E then { bp (E.tc, nxq); C.chain S := E.fc; } T p C S (1) else { q := nxq; Gen(j, _, _, 0); bp(c.chain,nxq); T p.chain := merge(s (1).chain,q);} S T p S (1) { S.chain := merge(t p. chain, S (1). chain;} W while { W.quad := nxq; } W d W E do { bp (E.tc,nxq); W d.chain := E.fc; q W d.quad := W.quad ;} W d S W d S (1) {bp(s (1).chain,W d.quad); Gen(j, _, _, W d.quad); S.chain := W d.chain;} S1 E 的代码 E (1) 的代码 S (1) 的代码 (j, _, _, p) (j, _, _, 0) p S (2) 的代码 while A<B do if C< then X:= Y+Z W E (1) W d E (2) C S 105 (:=,T,_, X) C if E then { bp (E.tc, nxq); C.chain := E.fc; } 106 (j,_,_,100) T p C S (1) else { q := nxq; Gen(j, _, _, 0); bp(c.chain,nxq); T p.chain := merge(s (1).chain,q);} S T p S (1) { S.chain := merge(t p. chain, S (1). chain;} W d W E do { bp (E.tc,nxq); W d.chain := E.fc; W d.quad := W.quad ;} W while { W.quad := nxq; } S W d S (1) {bp(s (1).chain,W d.quad); Gen(j, _, _, W d.quad); S.chain := W d.chain;} S C S (1) { S.chain := merg(c.chain, S (1). chain;} S (2) S (1) 100 (j<,a,b, 0) (j,_,_, 0 ) 102 (j<,c,, 0) (j,_,_, 0) (+,Y, Z, T) 7.6 过程调用 过程的定义代码首址记录到符号表中 ; 形参记录到符号表中 ; 调用者与被调用者转移目标返回地址参数传递 procedure S(var a, b:integer); 30

31 关于参数传递 - 传地址 约定 : 把实参地址逐一放在转子指令前 如 CALL S(A+B,Z) 翻成 k-4: T := A+B k-3: Par T k-2: Par Z k-1: Call S k: 进入子程序 S 之后,S 就可根据返回地址 k 寻找到存放实参地址的单元 分析 文法 G: (1) S CALL i(arglist) (2) Arglist Arglist, E (3) Arglist E 困难 : 如何在处理实参表的过程中记住每个实参的地址, 以便最后将它们排列在转子指令的前面 解决 : 遇到第一个实参建立一个队列, 后面的依次记录, 要记住队列头 属性文法 例 CALL S (A+B,Z) S CALL i(arglist) {for (Arglist.queue 中每个元素 arg) gen(par,_,_,arg); gen(call,_,_,entry(i))} Arglist Arglist (1), E {E.place 进队列 Arglist (1).queue; Arglist.queue:=Arglist (1).queue} Arglist E { 建立一个 Arglist.queue, 它只包含一项 E.place} S CALL i(arglist) {for (arglist.queue 中每个元素 arg) gen(par,_,_,arg); gen(call,_,_,entry(i))} arglist arglist (1), E {E.place 进队列 arglist (1).queue; arglist.queue:=arglist (1).queue} arglist E { 建立一个 arglist.queue, 它只包含一项 E.place} E E Ar Ar S k-4: T := A+B k-3: Par T k-2: Par Z k-1: Call S k: 31

32 7.7 类型检查类型表达式 P list;slist list list; id:t T int bool array [num] of L Slist Slist;S S S if E then S id:=e 基本类型是类型表达式 类型名是类型表达式 用于类型表达式得到类型表达式 基本类型 boolean, char, integer, real type-error void 类型构造符数组 array(i, T) 笛卡尔积 T 1 T 2 指针 pointer(t) 函数 R 确定标识符的类型 类型系统 A language s type system specifies which operations are valid for which types 类型检查 : 动态 ; 静态 The goal of type checking is to ensure that operations are used with the correct types 良类型系统 P ;E ; id:t {addtype(id.entry, T.type} T char {T.type=char} T integer {T.type=integer} T T 1 {T.type=pointer(T 1.type)} T array[num]of T {T.type=array(num.val, T 1.type)} 32

33 类型检查 E E 1 mod E 2 {if E 1.type=integer and E 2.type=integer then E.type=integer else E.type=type_error} E E 1 [E 2 ]{if E 2.type=integer and E 1.type=array(s,t) then E.type=t else E.type=type_error} E E 1 {if E 1.type=pointer(t) then E.type=t else E.type=type_error} E E 1 (E 2 ){if E 2.type=s and E 1.type=s t then E.type=t else E.type=type_error} 类型检查补充 ->id:t {insert(id.name, T.type)} T->int {E.type=integer} T->array [num] of T (1) {T.type=mkTypeNode(array,num.size,T (1).type )} S->if E then S {if not typeequal(e.type,boolean) then type-error(s)} S->id:=E {if not typeequal(lookup(id.name),e.type)then typeerror(s)} E->E (1) +E (2) {if not (typeequal(e (1).type,integer) and typeequal(e (2).type,integer))then type-error(e);e.type=integer} E->E (1) ore (2) {if not (typeequal(e (1).type,boolean) and typeequal(e (2).type,boolean))then type-error(e);e.type=boolean} E->num {E.type=integer} E->true {E.type=boolean} E->id {E.type=lookup(id.name)} 参考书 Kenneth C.L. 编译原理与实践 ( 英文版 ), 机械工业 2002 蒋立源 康慕宁, 编译原理 ( 第二版 ), 西北工业大学出版社 2004 本章习题 p :