Microsoft PowerPoint - 7-Semantic_IR09.ppt

Transcription

1 中间代码生成 第七章 : 语义分析和中间代码生成 中间代码生成位于词法分析和语法分析之后, 是代码生成中的一个阶段 ; 中间代码的形式很多, 如逆波兰记号 抽象语法树 三地址码 ( 三元式 四元式 ) P- 代码, 等等 属性文法是用于中间代码生成的常用的方法 赵银亮 本章内容 : 1. 中间表示形式 2. 说明语句的翻译 3. 简单算术表达式和赋值句到四元式的翻译 4. 布尔表达式到四元式的翻译 5. 控制语句的翻译 6. 数组元素的引用 7. 过程调用 7.1 中间表示的概念 抽象语法树 vs 类似目标代码 是否使用目标机和运行时环境的详细信 息 数据类型的尺寸 ; 寄存器变量的存储位置 前端 IR 后端 是否使用符号表中的全部信息 作用域嵌套层次变量的偏移量 其它用处 : 用于代码分析以产生高效目标代码用于多目标编译 (retrgetble) 后缀式 - 逆波兰表示 用于表示表达式时 : 变量或常量的后缀式是自身 ; e 1 op e 2 的后缀式是 e 1 e 2 op, 其中 e 1, e 2 分别是 e 1 和 e 2 的后缀式 ; (e) 的后缀式就是 e 的后缀式 ; 对后缀式求值 使用一个栈来求值 过程 : 从左到右依次扫描后缀式表示中的各个符号, 每遇到一个运算对象, 就压入栈中 ; 每遇到一个运算符时, 就弹出栈顶 k 个运算对象进行运算, 并将结果压入栈顶 结束时, 栈顶为整个表达式的值 +B B+ +B*C BC*+ x/y^z-d*e x/y^z-d*e xyz^/de*- xyz^/de*- (=0 b>3) (e x y) 0=b3> exy 运算对象出现的顺序相同 ; 运算符是按实际计算次序从左到右排列 Yinling Zho ( 赵银亮 ) 1

2 后缀式的推广 后缀式表示中注意的问题 op 为 k 目运算符, 则 op 作用于 e 1 e 2 e k 的结果用 e 1 e 2 e k op 来表示 后缀式 : exy? 含义 : e 不等于 0, 取 x, 否则取 y. 若用? 表示 if-then-else, If then if c-d then +c else *c else +b?c-d?+c:*c:+b 表示为 : cd- c+ c*? b+? 这种表示法要求在任何情况下都要把 x,y 都计算出来, 但只会用到其中一个值 语义上的差异 : 如果运算对象无定义或者有副作用, 则后缀表示法不仅无效, 而且可能是错误的 ; 还有代码效率问题 后缀式表示实现 后缀式存放在一个向量 POST[1..n] 中, 并有如下转移运算 : p BR 无条件转至 POST[p] e p BZ e 是某表达式 e 的后缀表示, 当 e 值为 0 转 POST[p] e1 e2 p BL 当 e1 <e2 时转向 POST[p] 类似地还可以定义 BN( 非 0 转 ) BP( 正号转 ) BM( 负号转 ) IF e THN s 1 LS s 2 e p 1 BZ s 1 p 2 BR s 2 其中 e, s 1, s 2 是 e, s 1, s 2 的后缀表示, p 1 和 p 2 分别表示 s 2 在 POST 中的开始位置以及后邻的位置 e p 1 BZ s 1 p 2 BR p 1 :s 2 p 2 : 在向量 POST 存放的后缀式 e x e' p 1 BZ s 1 ' p 2 BR y 符号表 p 1 p 2 下标 s 2 ' 数组 属性文法表示 步骤分析栈 0 # R 输入串 +b*c# 动作 push 后缀表示 属性 ddr: 纪录运算对象的起始位置向量 POST 和指针 p # #F #T b*c# b*c# b*c# 归约 F->id;Sub6 归约 T->F;Sub4 归约 ->T;Sub2 4 # + *c# push 1 2+T {1.ddr=2.ddr; POST[p]= + ; p++;} T {.ddr=t.ddr} #+ #+b #+F b * * c# c# c# push 归约 F->id;Sub6 归约 T->F;Sub4 b b T1 T2*F {T1.ddr=T2.ddr; POST[p]= * ; p++;} T F {T.ddr=F.ddr;} # +T # +T* # +T*c * c # c# # push push 归约 F->id;Sub6 b b bc F () F id {F.ddr=.ddr;} {F.ddr=p; POST[p]=lookup(id); p++;} # +T*F #+T # # # # 归约 T->T*F;Sub3 归约 ->+T;Sub1 bc* bc*+ bc*+ Yinling Zho ( 赵银亮 ) 2

3 7.1.3 三地址码 实现三地址码的数据结构 x = y op z 以操作符为核心一个操作符 op 两个操作数 y 和 z 一个结果 x x,y 和 z 通常是内存地址 y 和 z 还可以是常数和常量 文法规则 S id:= * 2-1 ( 1 ) id 语义规则 S.tree=mkNode(:=, mklef( id, id.plce),.tree).tree=mknode(+, 2.tree, 2.tree).tree=mkNode(*, 1.tree, 2.tree) T.tree=mkNode(uminus, 1.tree, nil).tree= 1.tree F.tree=mkLef(id, id.plce) 一个程序段的三地址代码表示 : 要产生临时变量 ; 临时变量跟抽象语法树的内结点对应 ; 语句之间可以有不同的次序 ; 操作符可有扩充 ; 比如单目运算 ; 例 : 2*+(b-3) + * - 2 b 3 t1 = 2 * t2 = b 3 t3 t2 = t1 b + 3 t2 t1 = 2 * t3 = t2 + t1 产生临时变量 ; 临时变量跟抽象语法树的内结点对应 ; 语句的次序 ; 操作符扩充 ; 一个程序段的三地址代码表示 : red x; if 0 < x then fct := 1; repet fct := fct * x; x := x 1 until x = 0; write fct end red x; t1 = x > 0 if_flse t1 goto L1 fct = 1 lbel L2 t2 = fct * x fct = t2 t3 = x 1 x = t3 t4 = x == 0 if_flse t4 goto L2 write fct lbel L1 hlt 实现三地址码的数据结构 四元组 (op, rg1, rg2, result) op 是一个二元 ( 也可一元或零元 ) 运算符 ; rg1, rg2 分别为两个运算对象, 可以是变量 常数 临时变量等等 ( 可以缺省 ); 运算结果在 result 中 ; 跟符号表有关系 2*+(b-3) (*, 2,, T1) t1 = 2 * t2 = b 3 t3 = t1 + t2 (, b, 3, T2) (+, T1, T2, T3) Yinling Zho ( 赵银亮 ) 3

4 四元组举例 : red x; t1 = x > 0 if_flse t1 goto L1 fct = 1 lbel L2 t2 = fct * x fct = t2 t3 = x 1 x = t3 t4 = x == 0 if_flse t4 goto L2 write fct lbel L1 hlt (rd,x,_,_) (gt,x,0,t1) (if_f,t1,l1,_) (sn,1,fct,_) (lb,l2,_,_) (mul,fct,x,t2) (sn,t2,fct,_) (sub,x,1,t3) (sn,t3,x,_) (eq,x,0,t4) (if_f,t4,l2,_) (wri,fct,_,_) (lb,l1,_,_) (hlt,_,_,_) 实现三地址码的数据结构 2 三元组 (op, rg1, rg2) op 是一个二元 ( 也可一元或零元 ) 运算符 ; rg1, rg2 分别为两个运算对象 : 可以是变量 常数 临时变量等等 ( 可以缺省 ) ; 也可以是某个三元式的序号 ; 跟符号表有关系 2*+(b-3) t1 = 2 * t2 = b 3 t3 = t1 + t2 (1) (*, 2, ) (2) (, b, 3) (3) (+, (1), (2)) 三元组举例 : (0) (rd,x,_) (1) (gt,x,0) (2) (if_f,(1),11) (3) (sn,1,fct) (4) (mul,fct,x) (5) (sn,(4),fct) (6) (sub,x,1) (7) (sn,(6),x) (8) (eq,x,0) (9) (if_f,(8),(4)) (10) (wri,fct,_) (11) (hlt,_,_) (rd,x,_,_) (gt,x,0,t1) (if_f,t1,l1,_) (sn,1,fct,_) (lb,l2,_,_) (mul,fct,x,t2) (sn,t2,fct,_) (sub,x,1,t3) (sn,t3,x,_) (eq,x,0,t4) (if_f,t4,l2,_) (wri,fct,_,_) (lb,l1,_,_) (hlt,_,_,_) 产生三地址码的属性文法 例 : id= +F F F () num id 属性 nme: 记录临时变量名 属性 code: 记录已生成的代码 方法 1: 用符号串表示代码 语法规则 语义规则 1 id= 2 1.nme=id.strvl 1.code= 2.code++id.strvl = 2.nme.nme=.nme;.code=.code 1 2 +F 1.nme=newtemp() 1.code= 2.code++F.code++ 1.nme = 2.nme + F.nme F.nme=F.nme;.code=F.code F () F.nme=.nme; F.code=.code F num F.nme=num.strvl; F.code= F id F.nme=id.strvl; F.code= ++ 串连接, 包括 1 个换行 ; 串连接, 包括 1 个空格 方法 2: 用符号串表示代码 语法规则 语义规则 S id:= S.code=.code gen(id.plce :=.plce) - 1.plce=newtemp().code= 1.code gen(.plce := minus 1.plce) plce=newtemp().code= 1.code 2.code gen(.plce := 1.plce + 2.plce) ( 1 ).plce= 1.plce ;.code= 1.code id.plce=id.plce;.code= ++ 串连接, 包括 1 个换行 ; 串连接, 包括 1 个空格 Yinling Zho ( 赵银亮 ) 4

5 7.2 说明语句的翻译 例 6.3 变量声明 ->TL T->int flot L->id, L id 文法规则语义规则 ->TL L.dtype=T.dtype T->int T.dtype=integer T->flot T.dtype=rel L 1 ->id, L 2 id.dtype=l 1.dtype L->id L 2.dtype=L 1.dtype id.dtype=l.dtype 题目 : 求一个 3*3 矩阵对角线元素之和 min() { flot [3,3],sum; int i,j; sum=0; printf("plese input rectngle elements:\n"); for(i=0;i<3;i++) for(j=0;j<3;j++) scnf("%f",&[i,j]); for(i=0;i<3;i++) sum=sum+[i,i]; printf( Sum of the digonl elements is %6.2f\n",sum); } 过程中的说明语句 P-> ->; TL T->int flot L->id, L id 文法规则语义规则 P-> offset=0 1 -> 2 ; 3 ->TL L.type=T.type; L.width=T.width T->int T.type=integer;T.width=4 T->flot T.type=rel;T.width=8 L 1 ->id, L 2 L->id 题目 : 求一个 3*3 矩阵对角线元素之和 min() { flot [3,3],sum; int i,j; sum=0; printf("plese input rectngle elements:\n"); for(i=0;i<3;i++) for(j=0;j<3;j++) scnf("%f",&[i,j]); for(i=0;i<3;i++) sum=sum+[i,i]; printf( Sum of the digonl elements is %6.2f\n",sum); } lookup(id.nme, L 1.type, offset); L 2.type=L 1.type; L 2.width=L 1.width; offset=offset+l 1.width lookup(id.nme, L.type, offset); offset=offset+l.width 作用域 P ; TL proc id;;s func id;;s T int flot L id, L id progrm sort(input,output) vr : rry[0..10] of int; x:int; proc redrry; vr i:int; begin.end; proc exchnge(i,j:int); begin x:=[i];[i]:=[j];[j]=x end; proc quicksort(m,n:int); vr k,v:int; func prtition (y,z:int):int; vr i,j:int; begin vexchnge(i,j);end; beginend; beginend. Sort i j heder nil x redrry exchnge quicksort heder i heder heder k v prtition heder progrm sort(input,output) vr : rry[0..10] of int; x:int; proc redrry; vr i:int; begin.end; proc exchnge(i,j:int); begin x:=[i];[i]:=[j];[j]=x end; proc quicksort(m,n:int); vr k,v:int; func prtition (y,z:int):int; vr i,j:int; begin vexchnge(i,j); d; beginend; beginend. 属性及过程的定义 mktble(tb) 创建一个符号表, 父表指针为 tb; nter(tb,nme,type,offset) 在 tb 所指符号表中为名字 nme 建立一个登记项, 类型 type 和相对地址 offset 填入该项中 ; ddwidth(tb,width) 在 tb 所指符号表表头中记录下该表中所有名字占用的总宽度 ; enterproc(tb, nme, newtb) 在 tb 所指符号表中为名字 nme 的过程建立一个登记项, 参数 newtb 指向 nme 的符号表 处理嵌套过程中的说明语句 ( 方法 1) P M M ε ; proc id;n 1 ;S id:t N ε ddwidth(pop(s_tb), pop(s_offset)) t:=mktb(nil); push(t, s_tb); push(0,s_offset) t:= pop(s_tb); ddwidth(t,pop(s_offset)) enterproc(top(s_tb), id.nme, t) nter(top(s_tb), id.nme, T.type, top(s_offset)) push(pop(s_offset)+t.width, s_offset) t:=mktb(top(s_tb)) push(t, s_tb); push(0,s_offset) pop(s_) 弹出 s_ 栈顶元素 ;top(s_) 返回 s_ 栈顶元素 ;push(e,s_) 压入 e 到栈 s_. Yinling Zho ( 赵银亮 ) 5

6 ( 方法 1) P M M ε ; N ε P M ddwidth(pop(s_tb), pop(s_offset)) proc t:= pop(s_tb); id;n 1 ; ddwidth(t,pop(s_offset)) S enterproc(top(s_tb), id.nme, t) id:t enter(top(s_tb), id.nme, T.type, top(s_offset)) push(pop(s_offset)+t.width, s_offset) t:=mktb(nil); push(t, s_tb); push(0,s_offset) t:=mktb(top(s_tb)); push(t, s_tb); push(0,s_offset) progrm sort(input, vr : rry[0..10] x:int; proc redrry; N vr i:int; begin.end; proc exchnge(i,j begin x:=[i];[i]:= end; N proc quicksort(m, vr k,v:int; func prtition N vr i,j:int; begin ve beginend; beginend. P ( 方法 2) L L L P L L.intb=mktb(nil); L.ioffs=0 P.symtb=L.outtb id:t L L 1 L 2 ; proc id;l;s.outtb=.intb L nter(.outtb, id.nme, T.type,.ioffs).ooffs=.ioffs+T.width ddwidth(.outtb,.ooffs)).intb=l.intb; L.outtb=.outtb.ioffs=L.ioffs;L.ooffs=.ooffs L 2.intb=L 1.intb;.intb=L 2.outtb L 1.outtb=.outtb; L 2.ioffs=L 1.ioffs L.ioffs=L 2.ooffs; L 1.ooffs=.ooffs L.intb=mktb(.intb); L.ioffs=0 ddwidth(l.intb,l.ooffs)).outtb=.intb;.ooffs=.ioffs enterproc(.intb,id.nme,.outtb) L L progrm sort(input, vr : rry[0..10] x:int; proc redrry; vr i:int; begin.end; proc exchnge(i,j begin x:=[i];[i]:= end; proc quicksort(m, vr k,v:int; func prtition vr i,j:int; L L begin ve beginend; beginend. P L id:t ( 方法 2) L L 1 L 2 ; proc id;l;s ot outtb io ioffs nil 4 it inttb oo ooffs x int 0 说明语句的翻译的小结 P st f L.it=mktb(nil); L.io=0 P.st=L.ot.ot=.it nter(.ot, id.nme, T.type,.io).oo=.io+T.width ddwidth(.ot,.oo)).it=l.it; L.ot=.ot.io=L.io;L.oo=.oo 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=mktb(.it); L.io=0.ot=.it;.oo=.io ddwidth(.ot,.oo)) enterproc(.ot,id.nme,l.ot) it io x it ot L io oo it ot io=0 L oo ot oo it ot io oo it ot proc f ; L ; S io=0 oo : int 简单变量的类型偏移量 ( 以过程为单位 ) 创建符号表符号表中添加登记项 结构型变量 ( 在后面介绍 ) 数组结构指针等 7.3 赋值语句的翻译 前面介绍过的一个例子 翻译赋值语句和算术表达式的属性文法 类型转换 数组处理 语法规则 1 ->id= 2 -> 1 -> 2 +F ->F F->() F->num F->id 语义规则 1.nme=id.strvl 1.code= 2.code++id.strvl = 2.nme.nme=.nme;.code=.code 1.nme=newtemp() 1.code= 2.code++F.code++ 1.nme = 2.nme + F.nme.nme=F.nme;.code=F.code F.nme=.nme; F.code=.code F.nme=num.strvl; F.code= F.nme=id.strvl; F.code= Yinling Zho ( 赵银亮 ) 6

7 7.3.1 属性及过程的定义 ( 产生四元组 ) NewTemp() 函数过程, 返回一个新临时变量名 ( 一般用整数表示 ); Lookup(nme) 以 nme 为名字查符号表 : 查到返回入口, 否则加入该名字到符号表中并返回入口 ;.plce 表示存放 值的变量名在符号表的入口或者整数 ( 临时变量 ); Gen(op, rg1, rg2, result) 语义过程, 建立四元式 (op, rg1, rg2, result) 并填入四元式表中 例 : 翻译简单赋值语句为四元组的属性文法 V:= * 2 ( 1 ) V num V id {if.plce=err or V.plce=err then.plce=err else {.plce =ok; Gen(:=,.plce,nil,V.plce)}} {if 1.plce=err or 2.plce=err then.plce=err else {.plce=newtemp(); Gen(+, 1.plce, 2.plce,.plce)}} {if 1.plce=err or 2.plce=err then.plce=err else {.plce=newtemp(); Gen(*, 1.plce, 2.plce,.plce)}} {.plce= 1.plce} {.plce=v.plce} {.plce=lexvl(num)} {V.plce=(p:=Lookup(id.nme))? p : err} 去掉错误处理部分 V:= {Gen(:=,.plce,nil,V.plce)} {.plce=newtemp(); Gen(+, 1.plce, 2.plce,.plce)} 1 * 2 {.plce=newtemp(); Gen(*, 1.plce, 2.plce,.plce)} ( 1 ) V num V id {.plce= 1.plce} {.plce=v.plce} {.plce=lexvl(num)} {V.plce=Lookup(id.nme} 类型转换 V:= {Gen(:=,.plce,nil,V.plce);} {.plce=newtemp(); if 1.type=int then if 2.type=int then Gen(ddi, 1.plce, 2.plce,.plce) else {tmp=newtemp(); Gen(itor, 1.plce, nil, tmp);gen(ddr,tmp, 2.plce,.plce);} else if 2.type=int then {tmp=newtemp(); Gen(itor, 2.plce, nil, tmp); Gen(ddr, 1.plce,tmp,.plce);} else Gen(ddr, 1.plce, 2.plce,.plce); 1.type=} 1 * 2 { 跟上面相似, 将 ddi 和 ddr 分别换成 muli 和 mulr} ( 1 ) {.plce=1.plce;.type=} V {.plce=v.plce;.type=} intnum relnum {.plce=lexvl(num);.type=} V id {V.plce=lookup(id.nme; V.type=} ddr 为实数加 数组元素引用 数组说明与下标变量的语义 数组说明与下标变量的语义地址计算公式四元式中数组元素表达形式赋值语句中数组元素的翻译 数组说明 flot [SIZ] ; int i,j; 数组元素引用 [i+1]=[j*2]+3; 数组说明 vr : rry[0..10] of int; 数组元素引用 [i]:=[j]+1; i,j:int; 数组说明 rel x(-13,13) integer i,j 数组元素引用 x[i]=x[j]+1 数组元素的存放区域如何安排? 如何确定数组元素的偏移量? Yinling Zho ( 赵银亮 ) 7

8 数组说明与下标变量的语义 [i+1] + (i+1) * sizeof(int) [t] bse_ddress() + (t-lower_bound())*element_size() (1) 地址计算公式 对于一维数组 [i]: 下标的变化范围 : l i u 连续存储区的首址 :bse, 每个数组元素占用 w 个单元则 [i] 地址为 :bse+(i-l)*w [i] 地址 : bse+(i-l)*w=(bse-l*w)+i*w 固定部分 :bse-l*w ( 在数组说明时即可确定 ) 变化部分 :i*w ( 在数组引用时确定, 即动态确定 ) (2) 数组说明 [l:u] 的表示 名字 符号表项 类型 数组 地址 内情向量表 1 Type/w l u bse C d 元素存储区域 [1] [2] 对于一维数组元素引用形式 [i], 该元素的存储位置为 : bse+(i-l)* w= bse - C + i*w 地址计算公式 ( 续 ) 对于二维数组 [i,j]: 下标的变化范围 : l 1 i u 1 ; l 2 j u 2 连续存储区的首址 :bse, 每个数组元素占用 w 个单元则 [i,j] 地址为 :bse+[(i-l 1 )*(u 2 -l 2 )+j-l 2 ]*w bse+[(i-l 1 )*(u 2 -l 2 )+j-l 2 ]*w =[bse+(-l 1 *(u 2 -l 2 )-l 2 )*w] + [(i*(u 2 -l 2 )+j)*w] 固定部分 : bse;(-l 1 *(u 2 -l 2 )-l 2 )*w 变化部分 : (i*(u 2 -l 2 )+j)*w 用维长表示 :(i*d 2 +j)*w 对于多维数组 [i 1,i 2,,i n ]: 下标的变化范围 : l 1 i 1 u 1 ;; l n i n u n 连续存储区的首址 :bse, 每个数组元素占用单元 w 个 则 [i 1,i 2,,i n ] 地址为 : bse+((((i 1 -l 1 )*d 2 +(i 2 -l 2 ))*d 3 +(i 3 -l 3 ) ))d n +(i n -l n ))*w =bse-((((l 1 *d 2 +l 2 )*d 3 +l 3 ))d n +l n )*w+ 注意 : 固定部分与数组各维的维长 d i 和数组的首址 bse 相关 ( 在数组说明时可确定 ); VRPRT 部分与下标变量的每个下标相关 ( 在运行时才能确定 ) 计算数组元素的地址时分别计算出 CONSTPRT 和 VRPRT, 对前者静态算出具体值, 而对后者则产生计算代码 i 1 *d 2 **d n +i 2 *d 3 **d n ++i n = bse- ConstPrt+ (((i 1 )*d 2 +i 2 )*d 3 +i 3 )*d 4 +i 4 ))*d n +i n Yinling Zho ( 赵银亮 ) 8

9 静态数组 [l 1 :u 1,, l n :u n ] 表示形式 计算可变部分 对于不变部分 Constprt, 产生代码 { T1 := bse-c }; 名字 符号表项 类型地址数组 内情向量表 n bse Type/w C l 1 u 1 d 1 l n u n d n 数组元素存储区域 [1,1,,1] [1,1,,2] 可变部分 Vrprt, 产生代码形如 {T:=Vrprt}; 所以数组引用 [i 1,i k ] 的地址为 T + T1, 使用变址指令 : 形式为 T1[T] (T1 为基址,T 为偏移量 ) 如此, 四元式的形式如下 : 变址取值 X:= T1[T] ( =[], T1[T], _, X) 变址存储 T1[T] := X ( []=, X, _, T1[T]) (3) 赋值语句中的数组元素翻译 V:= V i[l] i L L, + () V B 数组数组 文法允许数组元素嵌套定义,B[i]:=[v,B[j]+w] l 1 T B 2 T u u 2 bse C d bse 2 C 2 l 1 u 1 d 1 l 2 d 2 对下标表 L 在归约过程中需要知道数组名 i 的入口, 以获取登记在符号表中的数组信息 V i[l] i L L, L.plce V L] i L L, i[ VRPRT=(((i 1 )*d 2 +i 2 )*d 3 +i 3 )*d 4 +i 4 ))*d n +i n limit(i,k),k=3 属性定义 L.rr 该数组名在符号表中的入口位置 L.dim 数组维数计数器, 随着归约新的下标而增加 L.plce 存放已形成的 VRPRT 部分, 可能是变量或临时变量 Limit(,k) 函数过程, 数组 的第 k 维长度为 d k V.plce 对于简单变量记录该变量名在符号表中的位置对于下标变量记录保存 CONSTPRT 的那个临时变量 V.offset 简单变量 NULL( 用于区分简单变量和下标变量 ) 下标变量保存 VRPRT 的临时变量 L.rr (3) 赋值语句中的数组元素翻译 V:= V L] i L L, i[ + () V L.plce 数组 V.offset l 1 l n L.dim n T u 1 u n bse C d 1 d n V.plce Limit(,1) Limit(,n) Yinling Zho ( 赵银亮 ) 9

10 V:= {if V.offset=NULL then Gen(:=,.plce,_,V.plce) else Gen([]=,.plce,_,V.plce[V.offset])} { t:=newtemp(); Gen(+, 1.plce, 2.plce,t);.plce := t } ( 1 ) {.plce := 1.plce } V { if (V.offset=NULL) then.plce := V.plce; else { t:=newtemp(); Gen (=[],V.plce[V.offset],_,t);.plce:=t; } } V L] { t:=newtemp(); Gen(-,cc_bse(L.rr),cc_C(L.rr),t); V.plce:=t; t:=newtemp(); Gen(*, cc_w(l.rr), L.plce, t); V.offset :=t } V i { V.plce:= ntry(i); V.offset:= NULL; } L L 1, { t1:=newtemp(); k:= L 1.dim + 1; d k :=Limit(L 1.rr,k); Gen(*,L 1.plce,d k,t1); t2:= NewTemp(); Gen(+,.plce,t1,t2); L.rr := L 1.rr; L.plce := t2; L.dim := k; } L i[ { L.plce :=.plce; L.dim := 1; L.rr := ntry(i) } 例 : 是一个 10*20 的数组,[i+2,j+1]:= m+n 的翻译 V := L ] m+n L, 7.4 布尔表达式的翻译 布尔表达式的语义布尔表达式的求值布尔表达式作为条件的处理 i [ i+2 V:= V L] i L L, i[ + () V j+1 (+, I, 2, T1) (+, J, 1, T2) (*, T1, 20, T3) (+, T2, T3, T4) (-,, 21, T5) (+, M, N, T7) ([]=, T7, _,T5[T6]) (*, 4, T4, T6) 布尔表达式的语义 文法 : () i i rop i C 语言 : &&! < == > <= >=!= if(1 < i && i < 10)... Pscl: N OR NOT < = > <= >= if (x = 0) N ( = 2) then... 布尔表达式的语义 ( 续 ) 布尔算符的优先级 : 顺序 :,, ; 其中 和 服从左结合 另外所有关系符的优先级相同, 高于任何布尔算符, 低于任何算术算符 由于大部分体系结构没有内置的布尔类型, 所以用 0 和 1( 或非 0) 分别表示 Flse 和 True Fortrn 逻辑表达式 :.N..OR..NOT..LT..Q..GT..L..G..N. b =.N. 3.LT. 5/2 Yinling Zho ( 赵银亮 ) 10

11 布尔表达式在语言中的作用 求值 logicl, b =.TRU. b =.N. 3.LT. 5/ 布尔表达式的求值 基本算法 : 如同算术表达式求值一样, 一步步地计算各部分的值, 进而计算出整个表达式的值 作为控制语句中的条件 if(1 < i && i < 10)... 例 B C= (=, C,, T1) (, B, T1, T2) (,, T2, T3) 基本求值算法的实现 布尔表达式的求值 ( 续 ) ( 1 ) i {.plce=newtemp(); gen(, 1.plce, 2.plce,.plce} {.plce=newtemp(); gen(, 1.plce, 2.plce,.plce} {.plce=newtemp(); gen(,.plce, NIL,.plce} {.plce= 1.plce} {.plce=i.nme} i 1 rop i 2 {.plce=newtemp(); gen(rop, i 1.plce, i 2.plce,.plce)} 短路算法 : B if then true else B B if then B else flse if then flse else true 与基本算法的差别 : 运算量减少适用范围广 if((p!=null)&&(p->vl==0)) 短路算法的实现问题 求值 : 转换成条件语句求值 B if then true else B B if then B else flse if then flse else true 作为条件 : 等价地转换成嵌套 if 语句 if 1 2 then S1 else S2 if 1 then if 2 then S1 else S2 else S2 if 1 2 then S1 else S2 if 1 then S1 else if 2 then S1 else S2 if then S1 else S2 if then S2 else S 布尔表达式作为条件的处理 真出口, 假出口 if 1 then if 2 then S1 else S2 else S2 if 1 then if 2 then goto L-true else goto L-flse else goto L-flse; L-true: S1; goto L-next; L-flse: S2; L-next: if 1 then S1 else if 2 then S1 else S2 if 1 then goto L-true else if 2 then goto L-true else goto L-flse; L-true: S1; goto L-next; L-flse: S2; L-next: if then S2 else S1 if then goto L-flse else goto L-true; L-true: S1; goto L-next; L-flse: S2; L-next: Yinling Zho ( 赵银亮 ) 11

12 例 IF B< THN S1 LS S2 (1) (jnz,,_,5) {} (2) (j,_,_,3) (3) (j<,b,,5) (4) (j,_,_,p+1) (5) {S1} 转向 为假时的目标 转向 为真时的目标 (p) (j,_,_,q) (p+1) {S2} (q) { 下一语句 } G1: -> () i i rop i G2: -> ^ () i i rop i ^ -> 填 真链 -> 填 假链 p( ). q( )..ṙ( )... 解决办法 设 p q r 三条四元式均要转向 t 四元式 (1) 队列法 t( ) p q r Q.rer Q.front (2) 拉链 - 返填法 p(_,_,_,0). q(_,_,_,_) q(_,_,_,p). r(_,_,_,_) r(_,_,_,q). t(_,_,_,_) pq r (2) 拉链 - 返填法 b (jnz,,-,3) (j,-,-,?) (jnz,,-,3) (j,-,-,0) p(_,_,_,0) p(_,_,_,t). q(_,_,_,p) q(_,_,_,t). r(_,_,_,q) r(_,_,_,t). t(_,_,_,_) qp rqp x+y<0? c z==8?? G2: ^ () i i rop i ^ (jnz,,-,?) (j,-,-,?) (+,x,y,t1) (jlz,t1,-,4) (j,-,-,?) (jnz,c,-,?) (j,-,-,6) (==,z,8,t2) (jnz,t2,-,?) (j,-,-,?) (jnz,,-,0) (j,-,-,2) 4 3 (+,x,y,t1) (jlz,t1,-,4) (j,-,-,0) (jnz,c,-,0) (j,-,-,6) (==,z,8,t2) (jnz,t2,-,4) (j,-,-,3) 8 7 Yinling Zho ( 赵银亮 ) 12

13 nxq 下一个四元组的编号 bp 回填 tc 或 fc merge 合并两个 tc 或 fc i {.tc=nxq++; Gen(jnz,i,_,0);.fc=nxq++; Gen(j,-,-,0);} ^ 1 {bp ( 1.tc, nxq); ^.fc= 1.fc;} 1 {bp ( 1.fc, nxq);.tc= 1.tc;} ^ 1 {.tc= 1.tc;.fc=merg (^.fc, 1.fc); } 1 {.fc= 1.fc;.tc=merg (.tc, 1.tc); } i 1 rop i 2 {.tc=nxq++; Gen(jrop,i 1,i 2,0);.fc=nxq++; Gen(j,-,-,0);} ( 1 ) {.fc= 1.fc;.tc= 1.tc;} 1 {.tc= 1.fc;.fc= 1.tc;} ->i {.tc=nxq++;.fc=nxq++; 例 :(x <b c=d ) e>f Gen(jnz,i,_,0); Gen(j,-,-,0);} ^-> 1 {bp ( 1.tc, nxq); ^.fc= 1.fc;} ^ () i 7 -> 1 i rop i 8 {bp ( 1.fc, nxq);.tc= 1.tc;} ^ ^?6 7 -> ^ {.tc= 1.tc;.fc=merg (^.fc, 1.fc); } 5 -> 1 ( 6 ) {.fc= 1.fc;.tc=merg (.tc, 1.tc); } e > f 3 5? 6 x ^ 1 2? < 3 4 b c = d (jnz, x, -, 0) (j,-,-,0) (j<,, 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 语言中允许标号先定义后使用, 也允许先使用后定义 1 标号先定义后引用 L1 : S1 符号表 Goto L1 名字 类型 定义否 遇到 L1 : S1 L1 标号 定义 P 1 : (,,,) 遇到 Goto L1 (j, _, _, P 1 ) 设标号对应的四元组从编号 P 1 开始 地址 P 1 2 标号先引用后定义 名字 L2 q1 goto L2 q2 goto L2 q3 L2 : S2 类型 定义 地址 q1 (j, _, _, 0 ) q3 q2 (j, _, _, q1 ) q3 标号 未 q1 q2 q3 1 遇到 goto L2, 填符号表, 未定义, 把 NXQ 填入 L2 的地址部分, 作为链头 产生 ( j, _, _, 0) 2 遇到 goto L2, 查到未定义, 取符号表中 L2 的地址 q1 填入四元式 q2:(j, _, _,q1), 将 q2 填入符号表 3 遇到 L2:S2, 就可以回填 Yinling Zho ( 赵银亮 ) 13

14 一般而言, 带标号语句产生式 S Lbel S Lbel i: 条件语句 较为复杂的程序控制语句常常是嵌套的 Lbel i: 的语义动作 : 1. 若 i 所指的标识符 ( 假定为 L) 不在符号表中, 则把它填入, 置类型为 标号, 定义否 为 已, 地址为 NXQ 2. 若 L 已在符号表中, 但 类型 不为 标号 或者 定义否 为 已, 则报告出错 3. 若 L 已在符号表中, 则把标志 未 改为 已, 然后, 把地址栏中的链头 ( 记为 q) 取出, 同时把 NXQ 填在其中, 最后, 执行 bp(q,nxq) if 1 THN if 2 then S1 else S2 LS S3 S1 后有一条转移指令, 转到本 if 语句之后 与布尔表达式中不同的是, 在 S2 翻译之后, 也不能确定这个转移地址, 它要跨越 S2,S3 所以, 转移地址的确定与语句所处的上下文有关 我们采用一个属性 后续链 来记录, 实现当后续目标位置确定时返填 S1 S2 S3 F2 V1 V2 V3 if then S1 else S2; S3; if then begin if F1 then U1 else U2; U3 end else S2; F1 S3; U1 if then begin U2 if F1 then U1 else U2; U3 U3 end else begin if F2 then V1 else V2; V3 end S3; S1 S2 S3 F1 U1 U2 U3 规则 S if then S1 else S2.true:=newlbel();.flse:=newlbel(); S1.next:=S.next; S2.next:=S.next; S.code:=.code gen(.true : ) S1.code gen( goto S.next) gen(.flse : ) S2.code if then begin if F1 then U1 else U2; U3 end else S2;S3; F1 规则 S if then S1 else S2 F1 规则 S if then S1 S1 S2 S3 U1 U2.true:=newlbel();.flse:=newlbel(); S1.next:=S.next; S2.next:=S.next; S.code:=.code gen(.true : ) S1.code gen( goto S.next) gen(.flse : ) S2.code S1 S2 S3 U1.true:=newlbel();.flse:= S.next; S1.next:=S.next; S.code:=.code gen(.true : ) S1.code if then begin if F1 then U1 else U2 end else S2;S3; if then begin if F1 then U1 end else S2;S3; Yinling Zho ( 赵银亮 ) 14

15 S1 S2 规则 S while do S1 S.begin:=newlbel();.true:=newlbel();.flse:=S.next; S1.next:=S.begin; S.code:=gen(S.begin : ).code gen(.true : ) S1.code gen( goto S.begin) while do S1;S2; 产生三地址码的属性文法 S if then S1 S if then S1 else S2 S while do S1.true:=newlbel();.flse:=S.next; S1.next:=S.next; S.code:=.code gen(.true : ) S1.code.true:=newlbel();.flse:=newlbel(); S1.next:=S.next; S2.next:=S.next; S.code:=.code gen(.true : ) S1.code gen( goto S.next) gen(.flse : ) S2.code S.begin:=newlbel();.true:=newlbel ();.flse:=s.next;s1.next:=s.begin; S.code:=gen(S.begin : ).code gen(.true : ) S1.code gen( goto S.begin) 采用四元组实现时需要对其中的 goto 语句进行处理 嵌套条件语句的拉链返填处理 在四元组表示中 newlbel() 是目标位置的首地址 : if then S1 else S2 语句中 的真假出口的目标位置分别是 S1 和 S2 if then S1 语句中 的真假出口的目标位置分别是 S1 和下一条语句 if then S1 [else S2] 语句中 S1 和 S2 的后续目标位置是该 if 语句下一条语句 嵌套时下一条语句指外层该语法单位的后续目标位置 while do S1 语句中 的真假出口的目标位置分别是 S1 和下一条语句 后续目标的地址只有到那个目标被归约时才知道 文法修剪 S if then S if then S else S while do S begin L end 属性 L : L; S S tc, fc ( 真假出口 ) chin ( 后续目标 ) qud (While 条件 ) S C S C 和 S 后续目标相同 T p S T p 和 S 后续目标相同 W d S begin L end C if then 真出口已知 T p CS else C 后续目标已知 W d W do W while L L s S S L s L; C 和 S 后续目标相同 S C S {S.chin := merg( T p S T p 和 S 后续目标相同 C.chin, S (1). chin)} W d {S.chin := S merg(t p.chin, S (1). chin)} begin L end 真出口已知 C if then {bp (.tc, nxq); T p CS else C 后续目标已知 C.chin :=.fc} W d {q:=nxq; Gen(j, _, _, 0); W do bp(c.chin,nxq); W while T p.chin:=merge(s.chin,q)} L L s S S if 语句 L s L; 示例 C if then { bp (.tc, nxq); C.chin :=.fc; } T p C S (1) else { q := nxq; Gen(j, _, _, 0); bp(c.chin,nxq); T p.chin := merge(s (1).chin,q);} S T p S (1) { S.chin := merge(t p. chin, S (1). chin;} IF THN S (1) LS S (2) C T P S 的代码 S (1) 的代码 q: ( j, _, _, 0) S (2) 的代码 Yinling Zho ( 赵银亮 ) 15

16 S C S while 语句 T p S W d S begin L end C if then T p CS else W d W do W 条件已知 W while { W.qud := nxq } L L s S S L s L; S 后续目标已确定 { bp(s (1).chin,W d.qud); Gen(j, _, _, W d.qud); S.chin := W d.chin} W 循环体已知 {bp (.tc,nxq); W d.chin :=.fc; W d.qud := W.qud} C if then { bp (.tc, nxq); C.chin :=.fc; } S C S (1) { S.chin := merg(c.chin, S (1). chin);} T p C S (1) else { q := nxq; Gen(j, _, _, 0); bp(c.chin,nxq); T p.chin := merge(s (1).chin,q);} S T p S (1) { S.chin := merge(t p. chin, S (1). chin;} W while { W.qud := nxq; } W d W do { bp (.tc,nxq); W d.chin :=.fc; W d.qud := W.qud ;} S W d S (1) { bp(s (1).chin,W d.qud); Gen(j, _, _, W d.qud); S.chin := W d.chin;} L S { L.chin := S.chin;} L s L; { bp(l.chin,nxq); } L L s S (1) { L.chin := S (1).chin;} S begin L end { S.chin := L.chin;} S { S.chin := 0;} 空链 if then while (1) do S (1) else S (2) C W W d S1 T P 的代码 p C if then { bp (.tc, nxq); C.chin S :=.fc; } (1) 的代码 T p CS (1) else { q := nxq; Gen(j, _, _, 0); bp(c.chin,nxq); T p.chin := merge(s (1).chin,q);} S T p S (1) { S.chin := merge(t p. chin, S (1). chin;} W while { W.qud := nxq; } W d W do{ bp (.tc,nxq); W d.chin :=.fc; q W d.qud := W.qud ;} S (1) 的代码 (j, _, _, p) (j, _, _, 0) p S W d S (1) {bp(s (1).chin,W d.qud); Gen(j, _, _, W d.qud); S (2) 的代码 S.chin := W d.chin;} while <B do if C< then X:= Y+Z W (1) W d (2) C S 105 (:=,T,_, X) C if then { bp (.tc, nxq); C.chin :=.fc; } 106 (j,_,_,100) T p CS (1) else { q := nxq; Gen(j, _, _, 0); bp(c.chin,nxq); T p.chin := merge(s (1).chin,q);} S T p S (1) { S.chin := merge(t p. chin, S (1). chin;} W d W do{ bp (.tc,nxq); W d.chin :=.fc; W d.qud := W.qud ;} W while { W.qud := nxq; } S W d S (1) {bp(s (1).chin,W d.qud); Gen(j, _, _, W d.qud); S.chin := W d.chin;} S C S (1) { S.chin := merg(c.chin, S (1). chin;} S (2) S (1) 100 (j<,,b, 0) (j,_,_, 0 ) 102 (j<,c,, 0) (j,_,_, 0) (+,Y, Z, T) 7.6 过程调用 过程的定义代码首址记录到符号表中 ; 形参记录到符号表中 ; 调用者与被调用者转移目标返回地址参数传递 关于参数传递 - 传地址 约定 : 把实参地址逐一放在转子指令前 如 CLL S(+B,Z) 翻成 k-4: T := +B k-3: Pr T k-2: Pr Z k-1: Cll S 进入子程序 S 之后,S 就可根据返回地址 k 寻找到存放实 k: 参地址的单元 Yinling Zho ( 赵银亮 ) 16

17 分析 文法 G: (1) S CLL i(rglist) (2) rglist rglist, (3) rglist 困难 : 如何在处理实参表的过程中记住每个实参的地址, 以便最后将它们排列在转子指令的前面 解决 : 遇到第一个实参建立一个队列, 后面的依次记录, 要记住队列头 属性文法 S CLL i(rglist) {for (rglist.queue 中每个元素 rg) gen(pr,_,_,rg); gen(cll,_,_,entry(i))} rglist rglist (1), {.plce 进队列 rglist (1).queue; rglist.queue:=rglist (1).queue} rglist { 建立一个 rglist.queue, 它只包含一项.plce} 例 CLL S (+B,Z) 7.7 类型检查 S CLL i(rglist) {for (rglist.queue 中每个元素 rg) gen(pr,_,_,rg); gen(cll,_,_,entry(i))} rglist rglist (1), {.plce 进队列 rglist (1).queue; rglist.queue:=rglist (1).queue} rglist { 建立一个 rglist.queue, 它只包含一项.plce} r r S k-4: T := +B k-3: Pr T k-2: Pr Z k-1: Cll S k: P list;slist list list; id:t T int bool rry [num] of L Slist Slist;S S S if then S id:= 类型检查补充 ->id:t {insert(id.nme, T.type)} T->int {.type=integer} T->rry [num] of T (1) {T.type=mkTypeNode(rry,num.size,T (1).type )} S->if then S {if not typequl(.type,boolen) then type-error(s)} S->id:= {if not typequl(lookup(id.nme),.type)then typeerror(s)} -> (1) + (2) {if not (typequl( (1).type,integer) nd typequl( (2).type,integer))then type-error();.type=integer} -> (1) or (2) {if not (typequl( (1).type,boolen) nd typequl( (2).type,boolen))then type-error();.type=boolen} ->num {.type=integer} ->true {.type=boolen} ->id {.type=lookup(id.nme)} 参考书 Kenneth C.L. 编译原理与实践 ( 英文版 ), 机械工业 2002 蒋立源 康慕宁, 编译原理 ( 第二版 ), 西北工业大学出版社 2004 本章习题 p : Yinling Zho ( 赵银亮 ) 17