Microsoft PowerPoint - 7-Semantic&IR.ppt

Transcription

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

2 后缀式的推广 op 为 k 目运算符, 则 op 作用于 e 1 e 2 e k 的结果用 e 1 e 2 e k op 来表示 在向量 POST 存放的后缀式 e p 1 p 2 下标 若用? 表示 if-then-else, 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+? x y 符号表 e' p 1 BZ s 1 ' p 2 BR s 2 ' 数组 后缀式表示中注意的问题 属性文法表示 后缀式 : exy? 含义 : e 不等于 0, 取 x, 否则取 y. 这种表示法要求在任何情况下都要把 x,y 都计算出来, 但只会用到其中一个值 语义上的差异 : 如果运算对象无定义或者有副作用, 则后缀表示法不仅无效, 而且可能是错误的 ; 还有代码效率问题 属性 addr: 纪录运算对象的起始位置向量 POST 和指针 p 1 2+T {1.addr=2.addr; POST[p]= + ; p++;} T {.addr=t.addr} T1 T2*F {T1.addr=T2.addr; POST[p]= * ; p++;} T F F () {T.addr=F.addr;} {F.addr=.addr;} F id {F.addr=p; POST[p]=lookup(id); p++;} 后缀式表示实现 步骤分析栈 0 # R a 输入串 +b*c# 动作 push 后缀表示 后缀式存放在一个向量 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( 负号转 ) #a #F #T # #+ #+b b * b*c# b*c# b*c# *c# c# c# 归约 F->id;Sub6 归约 T->F;Sub4 归约 ->T;Sub2 push push 归约 F->id;Sub6 a a a a a ab 7 #+F * c# 归约 T->F;Sub4 ab 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 中的开始位置以及后邻的位置 # +T # +T* # +T*c # +T*F #+T * c # # # c# # push push 归约 F->id;Sub6 归约 T->T*F;Sub3 归约 ->+T;Sub1 ab ab abc abc* abc*+ e p 1 BZ s 1 p 2 BR p 1 :s 2 p 2 : 13 # # abc*+ Yinliang Zhao 2

3 实现三地址码的数据结构 文法规则 S->id:= -> > 1 * 2 ->- 1 ->( 1 ) ->id 语义规则 S.tree=mkNode(:=, mkleaf( id, id.place),.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=mkLeaf(id, id.place) 例 : 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 产生临时变量 ; 临时变量跟抽象语法树的内结点对应 ; 语句的次序 ; 操作符扩充 ; 三地址码 x = y op z 以操作符为核心 一个操作符 op 两个操作数 y 和 z 一个结果 x x,y 和 z 通常是内存地址 y 和 z 还可以是常数和常量 一个程序段的三地址代码表示 : 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) t1 = 2 * a t2 = b 3 t3 = t1 + t2 (*, 2, a, T1) (, b, 3, T2) (+, T1, T2, T3) Yinliang Zhao 3

4 四元组举例 : 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,_,_,_) 产生三地址码的属性文法 例 : ->id= A A->A+F F F->() num id 属性 name: 记录临时变量名属性 code: 记录已生成的代码 实现三地址码的数据结构 2 三元组 (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)) 语法规则 1 ->id= 2 ->A A 1 ->A 2 +F A->F F->() F->num F->id 语义规则用符号串表示代码 1 1.name=id.strval 1.code= 2.code++id.strval = 2.nam e.name=a.name.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=.name F.code=.code F.name=num.strval F.code= F.name=id.strval F.code= ++ 串连接, 包括 1 个换行 ; 串连接, 包括 1 个空格 三元组举例 : (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,_,_,_) 语法规则 S->id:= ->- 1 -> >( 1 ) ->id 语义规则 S.code=.code gen(id.place :=.place).place=newtemp().code= 1.code gen(.place := minus 1.place).place=newtemp().code= 1.code 2.code gen(.place := 1.place + 2.place).place= 1.place.code= 1.code.place=id.place.code= 用符号串表示代码 2 ++ 串连接, 包括 1 个换行 ; 串连接, 包括 1 个空格 Yinliang Zhao 4

5 7.2 说明语句的翻译 例 6.3 变量声明 D->TL T->int float L->id, L id 文法规则 D->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() { float a[3,3],sum; int i,j; 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); } Sort a x i j header nil readarray exchange quicksort header i header k v header partitio n header program sort(input,output) var a: array[0..10] of int; x:int; proc readarray; var i:int; begina.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 avexchange(i,j); d; beginend; beginend. 过程中的说明语句 P->D D->D;D TL T->int float L->id, L id 文法规则 P->D D 1 ->D 2 ;D 3 D->TL T->int T->float L 1 ->id, L 2 L->id 语义规则 offset=0 题目 : 求一个 3*3 矩阵对角线元素之和 main() { float a[3,3],sum; int i,j; 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); L.type=T.type; L.width=T.width T.type=integer;T.width=4 T.type=real;T.width=8 } 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 属性及过程的定义 mktable(tab) 创建一个符号表, 父表指针为 tab; nter(tab,name,type,offset) 在 tab 所指符号表中为名字 name 建立一个登记项, 类型 type 和相对地址 offset 填入该项中 ; addwidth(tab,width) 在 tab 所指符号表表头中记录下该表中所有名字占用的总宽度 ; enterproc(tab, name, newtab) 在 tab 所指符号表中为名字 name 的过程建立一个登记项, 参数 newtab 指向 name 的符号表 作用域 P D D D;D TL proc id;d;s func id;d;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; begina.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 avexchange(i,j);end; beginend; beginend. 处理嵌套过程中的说明语句 ( 方法 1) P MD M ε D D;D D proc id;nd 1 ;S D id:t N ε 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) nter(top(s_tab), id.name, T.type, top(s_offset)) t:=mktab(top(s_tab)) push(pop(s_offset)+t.width, s_offset) pop(s_) 弹出 s_ 栈顶元素 ; push(t, s_tab) top(s_) 返回 s_ 栈顶元素 ; push(0,s_offset) push(e,s_) 压入 e 到栈 s_. Yinliang Zhao 5

6 P ( 方法 2) L L L L L program sort(input D P L L.intab=mktab(nil); L.ioffs=0 var a: array[0..10 P.symtab=L.outtab D D x:int; proc readarray; D D.outtab=D.intab L D var i:int; id:t nter(d.outtab, id.name, T.type, begina.end; D.ioffs) proc exchange(i,j D.ooffs=D.ioffs+T.width D begin L D D.intab=L.intab; addwidth(d.outtab,d.ooffs)) L.outtab=D.outtab D x:=a[i];a[i]:= D.ioffs=L.ioffs;L.ooffs=D.ooffs end; L 1 L 2.intab=L 1.intab; D.intab=L 2.outtab L proc quicksort(m, L L 2 ;D L 1.outtab=D.outtab; L 2.ioffs=L 1.ioffs D var k,v:int; D.ioffs=L 2.ooffs; L 1.ooffs=D.ooffs D func partition D L.intab=mktab(D.intab); L.ioffs=0 var i,j:int; proc addwidth(l.intab,l.ooffs)) L D begin ave id;l;s D.outtab=D.intab; D.ooffs=D.ioffs enterproc(d.intab,id.name,d.outtab) beginend; beginend. 7.3 赋值语句的翻译 翻译赋值语句和算术表达式的属性文法类型转换数组处理 ( 方法 2) P L D id:t L D L 1 L 2 ;D ot outtab it inttab L.it=mktab(nil); L.io=0 P.st=L.ot D.ot=D.it nter(d.ot, id.name, T.type, D.io) D.oo=D.io+T.width addwidth(d.ot,d.oo)) D.it=L.it; L.ot=D.ot D.io=L.io;L.oo=D.oo L 2.it=L 1.it; D.it=L 2.ot L 1.ot=D.ot; L 2.io=L 1.io D.io=L 2.oo; L 1.oo=D.oo io ioffs oo ooffs it ot L io oo P st it ot io=0 L oo it ot D io oo nil 4 x int 0 f it ot io D oo D L.it=mktab(D.it); L.io=0 proc D.ot=D.it; D.oo=D.io it ot proc f ; L ; S id;l;s addwidth(d.ot,d.oo)) io=0 oo enterproc(d.ot,id.name,l.ot) x : int 语法规则 1 ->id= 2 ->A A 1 ->A 2 +F A->F F->() F->num F->id 语义规则 1.name=id.strval 1.code= 2.code++id.strval = 2.nam e.name=a.name.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=.name F.code=.code F.name=num.strval F.code= F.name=id.strval F.code= 前面介绍过的一个例子 说明语句的翻译的小结 简单变量的 类型 偏移量 ( 以过程为单位 ) 创建符号表 符号表中添加登记项结构型变量 ( 在后面介绍 ) 数组 结构 指针等 属性及过程的定义 ( 产生四元组 ) NewTemp() 函数过程 每次调用时, 它都回送一个代表新临时变量名的整数码作为函数值 ( 跟符号表有关 ); Lookup(name) 以 name 为名字查符号表 : 查到返回入口指针, 否则填入并返回入口指针 ;.place 表示存放 值的变量名在符号表的入口或者整数码 ( 若为临时变量 ); Gen(op, arg1, arg2, result) 语义过程, 建立四元式 (op, arg1,arg2, result) 并填入四元式表中 Yinliang Zhao 6

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

8 (1) 地址计算公式对于一维数组 A[i]: 下标的变化范围 : l i u 连续存储区的首址 :base, 每个数组元素占用 w 个单元 则 A[i] 地址为 :base+(i-l)*w base+(i-l)*w=(base-l*w)+i*w 固定部分 :base-l*w ( 在数组说明时即可确定 ) 变化部分 :i*w ( 在数组引用时确定, 即动态确定 ) 对于多维数组 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+ 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 (2) 数组说明 A[l:u] 的表示 注意 : 名字 A 符号表项 类型地址数组 内情向量表 1 base Type/w C l u d 元素存储区域 A[1] A[2] 固定部分与数组各维的维长 d i 和数组的首址 base 相关 ( 在数组说明时可确定 ); VARPART 部分与下标变量的每个下标相关 ( 在运行时才能确定 ) 计算数组元素的地址时分别计算出 CONSTPART 和 VARPART, 对前者静态算出具体值, 而对后者则产生计算代码 对于一维数组元素引用形式 A[i], 该元素的存储位置为 : base+(i-l)* w= base - C + i*w 地址计算公式 ( 续 ) 静态数组 A[l 1 :u 1,, l n :u n ] 表示形式 对于二维数组 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 名字 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] Yinliang Zhao 8

9 计算可变部分对于不变部分 Constpart, 产生代码 { T1 := base-c }; 可变部分 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]) 属性定义 L.arr 数组名的符号表入口 L.dim 数组维数计数器, 随着归约新的下标而增加 L.place 记存业已形成的 VARPART 的中间结果名字在符号表中的位置, 或者是一个临时变量的整数码 Limit(ARRAY,k) 函数过程, 数组 ARRAY 的第 k 维长度 d k V.place 简单变量 变量名的符号表入口 下标变量 保存 CONSTPART 的临时变量的整数码 V.offset 简单变量 NULL( 用于区分简单变量和下标变量 ) 下标变量 保存 VARPART 的临时变量的整数码 (3) 赋值语句中的数组元素翻译 A V:= V i[l] i L L, + () V A V:= {if V.offset=NULL then Gen(:=,.place,_,V.place) else Gen([]=,.place,_,V.place[V.offset])} { t:=newtemp(); Gen(+, 1.place, 2.place,t);.place := t } ( 1 ) {.place := 1.place } 文法允许数组元素嵌套定义,A[B,C[2]+1] V { if (V.offset=NULL) then.place := V.place; else { t:=newtemp(); Gen (=[],V.place[V.offset],_,t);.place:=t; } } 对下标表 L 在归约过程中需要知道数组名 i 的入口, 以获取登记在符号表中的数组信息 V i[l] i L L, 回顾一下 VARPART 的计算公式, 它是一个乘加式 ((i 1 * d 2 +i 2 ) d 3 + i 3 )+i n-1 )d n +i n L.place limit(i,k),k=3 V L] i L L, i[ 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 } V i { V.place:= ntry(i); V.offset:= NULL; } L L 1, { t1:=newtemp(); k:= L 1.dim + 1; d k :=Limit(L 1.arr,k); Gen(*,L 1.place,d k,t1); t2:= NewTemp(); Gen(+,.place,t1,t2); L.arr := L 1.arr; L.place := t2; L.dim := k; } L i[ { L.place :=.place; L.dim := 1; L.arr := ntry(i) } Yinliang Zhao 9

10 例 : A 是一个 10*20 的数组,A[i+2,j+1]:= m+n 的翻译 A V := L ] m+n L, 布尔表达式的语义 ( 续 ) 布尔算符的优先级 : 顺序 :,, ; 其中 和 服从左结合 另外所有关系符的优先级相同, 高于任何布尔算符, 低于任何算术算符 i [ i+2 A V:= V L] i L L, i[ + () V j+1 (+, I, 2, T1) (+, J, 1, T2) (*, T1, 20, T3) (+, T2, T3, T4) (-, A, 21, T5) (+, M, N, T7) ([]=, T7, _,T5[T6]) (*, 4, T3, T6) 由于大部分体系结构没有内置的布尔类型, 所以用 0 和 1( 或非 0) 分别表示 False 和 True 7.4 布尔表达式的翻译 布尔表达式的语义布尔表达式的求值布尔表达式作为条件的处理 布尔表达式在语言中的作用 求值 logical a, b a =.TRU. b = a.and. 3.LT. 5/2 作为控制语句中的条件 if(1 < i && i < 10) 布尔表达式的语义 文法 : () i i rop i C 语言 : &&! < == > <= >=!= if(1 < i && i < 10)... Pascal: AND OR NOT < = > <= >= if (x = 0) AND (a = 2) then... Fortran 逻辑表达式 :.AND..OR..NOT..LT..Q..GT..L..G..N. b = a.and. 3.LT. 5/ 布尔表达式的求值 基本算法 : 如同算术表达式求值一样, 一步步地计算各部分的值, 进而计算出整个表达式的值 例 A B C=D (=, C, D, T1) (, B, T1, T2) (, A, T2, T3) Yinliang Zhao 10

11 基本求值算法的实现 1 2 {.place=newtemp(); gen(, 1.place, 2.place,.place} 1 2 {.place=newtemp(); gen(, 1.place, 2.place,.place} {.place=newtemp(); gen(,.place, NIL,.place} ( 1 ) {.place= 1.place} i {.place=i.name} i 1 rop i 2 {.place=newtemp(); gen(rop, i 1.place, i 2.place,.place)} 布尔表达式作为条件的处理 真出口, 假出口 if 1 then if 2 then S1 else S2 else S2 if 1 then if 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 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-false; L-true: S1; goto L-next; L-false: S2; L-next: if then S2 else S1 if then goto L-false else goto L-true; L-true: S1; goto L-next; L-false: S2; L-next: 布尔表达式的求值 ( 续 ) 例 IF A B<D THN S1 LS S2 短路算法 : 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)) {} 转向 为假时的目标 转向 为真时的目标 (1) (jnz,a,_,5) (2) (j,_,_,3) (3) (j<,b,d,5) (4) (j,_,_,p+1) (5) {S1} (p) (j,_,_,q) (p+1) {S2} (q) { 下一语句 } 短路算法的实现问题 求值 : 转换成条件语句求值 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 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 S1 G1: -> () i i rop i G2: -> ^ () i i rop i ^ -> 填 真链 -> 填 假链 Yinliang Zhao 11

12 a b (jnz,a,-,3) (j,-,-,?) (jnz,a,-,3) (j,-,-,0) 解决办法 (jnz,a,-,?) (j,-,-,?) (jnz,a,-,0) (j,-,-,2) 设 p q r 三条四元式均要转向 t 四元式 (1) 队列法 p( ). q( )..ṙ( )... t( ) p q r Q.rear Q.front x+y<0? c z==8?? G2: ^ () i i rop i ^ (+,x,y,t1) (jlz,t1,-,4) (j,-,-,?) (jnz,c,-,?) (j,-,-,6) (==,z,8,t2) (jnz,t2,-,?) (j,-,-,?) 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 (2) 拉链 - 返填法 nxq 下一个四元组的编号 bp 回填 tc 或 fc merge 合并两个 tc 或 fc p(_,_,_,0). q(_,_,_,_) q(_,_,_,p). r(_,_,_,_) r(_,_,_,q). t(_,_,_,_) pq r 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;} (2) 拉链 - 返填法 p(_,_,_,0) p(_,_,_,t). q(_,_,_,p) q(_,_,_,t). r(_,_,_,q) r(_,_,_,t). t(_,_,_,_) qp rqp ->i {.tc=nxq++;.fc=nxq++; 例 :(x a<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? a < 3 4 b c = d (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) Yinliang Zhao 12

13 7.5 控制语句 标号和转移语句条件语句分支语句 标号先引用后定义 q1 goto L2 q2 goto L2 q3 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, 就可以回填 标号和转移语句 标号的两种使用方法 L: S Goto L 语言中允许标号先定义后使用, 也允许先使用后定义 一般而言, 带标号语句产生式 S Label S Label i: Label i: 的语义动作 : 1. 若 i 所指的标识符 ( 假定为 L) 不在符号表中, 则把它填入, 置类型为 标号, 定义否 为 已, 地址为 NXQ 2. 若 L 已在符号表中, 但 类型 不为 标号 或者 定义否 为 已, 则报告出错 3. 若 L 已在符号表中, 则把标志 未 改为 已, 然后, 把地址栏中的链头 ( 记为 q) 取出, 同时把 NXQ 填在其中, 最后, 执行 bp(q,nxq) 标号先定义后引用 L1 : S1 符号表 Goto L1 名字 类型 定义否 遇到 L1 : S1 L1 标号 定义 P 1 : (,,,) 遇到 Goto L1 (j, _, _, P 1 ) 设标号对应的四元组从编号 P 1 开始 地址 P 条件语句 较为复杂的程序控制语句常常是嵌套的 if 1 THN if 2 then S1 else S2 LS S3 S1 后有一条转移指令, 转到本 if 语句之后 与布尔表达式中不同的是, 在 S2 翻译之后, 也不能确定这个转移地址, 它要跨越 S2,S3 所以, 转移地址的确定与语句所处的上下文有关 我们采用一个属性 后续链 来记录, 实现当后续目标位置确定时返填 Yinliang Zhao 13

14 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 规则 S if then S1.true:=newlabel();.false:= S.next; S1.next:=S.next; S.code:=.code gen(.true : ) S1.code if then begin if F1 then U1 end else S2;S3; S1 S2 S3 F1 U1 U2 U3 规则 S if then S1 else S2.true:=newlabel();.false:=newlabel(); S1.next:=S.next; S2.next:=S.next; S.code:=.code gen(.true : ) S1.code gen( goto S.next) gen(.false : ) S2.code S1 S2 规则 S while do S1 S.begin:=newlabel();.true:=newlabel();.false:=S.next; S1.next:=S.begin; S.code:=gen(S.begin : ).code gen(.true : ) S1.code gen( goto S.begin) if then begin if F1 then U1 else U2; U3 end else S2;S3; while do S1;S2; S1 S2 S3 F1 U1 U2 规则 S if then S1 else S2.true:=newlabel();.false:=newlabel(); S1.next:=S.next; S2.next:=S.next; S.code:=.code gen(.true : ) S1.code gen( goto S.next) gen(.false : ) S2.code if then begin if F1 then U1 else U2 end else S2;S3; 产生三地址码的属性文法 S if then S1 S if then S1 else S2 S while do S1.true:=newlabel();.false:=S.next; S1.next:=S.next; S.code:=.code gen(.true : ) S1.code.true:=newlabel();.false:=newlabel(); S1.next:=S.next; S2.next:=S.next; S.code:=.code gen(.true : ) S1.code gen( goto S.next) gen(.false : ) S2.code S.begin:=newlabel();.true:=newlabel();.false:=S.next;S1.next:=S.begin; S.code:=gen(S.begin : ).code gen(.true : ) S1.code gen( goto S.begin) 采用四元组实现时需要对其中的 goto 语句进行处理 Yinliang Zhao 14

15 嵌套条件语句的拉链返填处理 在四元组表示中 newlabel() 是目标位置的首地址 : if then S1 else S2 语句中 的真假出口的目标位置分别是 S1 和 S2 if then S1 语句中 的真假出口的目标位置分别是 S1 和下一条语句 if then S1 [else S2] 语句中 S1 和 S2 的后续目标位置是该 if 语句下一条语句 嵌套时下一条语句指外层该语法单位的后续目标位置 while do S1 语句中 的真假出口的目标位置分别是 S1 和下一条语句 后续目标的地址只有到那个目标被归约时才知道 示例 C if then { bp (.tc, nxq); C.chain :=.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 THN S (1) LS S (2) C T P S 的代码 S (1) 的代码 q: ( j, _, _, 0) S (2) 的代码 文法修剪 S if then S if then S else S while do S begin L end A L L; S S 属性 : tc, fc ( 真假出口 ) chain ( 后续目标 ) quad (While 条件 ) S C S C 和 S 后续目标相同 T p S T p 和 S 后续目标相同 W d S begin L end A C if then 真出口已知 T p CS else C 后续目标已知 W d W do W while L L s S S L s L; while 语句 W 条件已知 { W.quad := nxq } S C S T p S W d S begin L end A C if then T p CS else W d W do W while 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 (.tc,nxq); W d.chain :=.fc; W d.quad := W.quad} C 和 S 后续目标相同 S C S {S.chain := merg( C.chain, S (1). chain)} T p S W d S T p 和 S 后续目标相同 {S.chain := merg(t p.chain, S (1). chain)} 真出口已知 {bp (.tc, nxq); begin L end A C if then T p CS else C 后续目标已知 C.chain :=.fc} W d W do {q:=nxq; Gen(j, _, _, 0); bp(c.chain,nxq); W while T p.chain:=merge(s.chain,q)} L L s S if 语句 S L s L; C if then { bp (.tc, nxq); C.chain :=.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 do { bp (.tc,nxq); W d.chain :=.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;} 空链 Yinliang Zhao 15

16 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.chain S :=.fc; } (1) 的代码 T p CS (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 do{ bp (.tc,nxq); W d.chain :=.fc; q W d.quad := W.quad ;} S (1) 的代码 (j, _, _, p) (j, _, _, 0) p S W d S (1) {bp(s (1).chain,W d.quad); Gen(j, _, _, W d.quad); S (2) 的代码 S.chain := W d.chain;} 关于参数传递 - 传地址 约定 : 把实参地址逐一放在转子指令前 如 CALL S(A+B,Z) 翻成 k-4: T := A+B k-3: Par T k-2: Par Z k-1: Call S 进入子程序 S 之后,S 就可根据返回地址 k 寻找到存放实 k: 参地址的单元 while A<B do if C<D then X:= Y+Z W (1) W d (2) C S 105 (:=,T,_, X) C if then { bp (.tc, nxq); C.chain :=.fc; } 106 (j,_,_,100) T p CS (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 do{ bp (.tc,nxq); W d.chain :=.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,d, 0) (j,_,_, 0) (+,Y, Z, T) 分析 文法 G: (1) S CALL i(arglist) (2) Arglist Arglist, (3) Arglist 困难 : 如何在处理实参表的过程之中记住每个实参的地址, 以便最后将它们排列在转子指令的前面 解决 : 遇到第一个实参建立一个队列, 后面的依次记录, 要记住队列头 7.6 过程调用 过程的定义 代码首址记录到符号表中 ; 形参记录到符号表中 ; 调用者与被调用者 转移目标 返回地址 参数传递 属性文法 S CALL i(arglist) {for (Arglist.queue 中每个元素 arg) gen(par,_,_,arg); gen(call,_,_,entry(i))} Arglist Arglist (1), {.place 进队列 Arglist (1).queue; Arglist.queue:=Arglist (1).queue} Arglist { 建立一个 Arglist.queue, 它只包含一项.place} Yinliang Zhao 16

17 例 CALL S (A+B,Z) 参考书 S CALL i(arglist) {for (arglist.queue 中每个元素 arg) gen(par,_,_,arg); gen(call,_,_,entry(i))} arglist arglist (1), {.place 进队列 arglist (1).queue; arglist.queue:=arglist (1).queue} arglist { 建立一个 arglist.queue, 它只包含一项.place} Ar Ar S k-4: T := A+B k-3: Par T k-2: Par Z k-1: Call S k: Kenneth C.L. 编译原理与实践 ( 英文版 ), 机械工业 2002 蒋立源 康慕宁, 编译原理 ( 第二版 ), 西北工业大学出版社 2004 本章习题 p : 类型检查 P Dlist;Slist Dlist Dlist;D D D id:t T int bool array [num] of L Slist Slist;S S S if then S id:= 类型检查补充 D->id:T {insert(id.name, T.type)} T->int {.type=integer} T->array [num] of T (1) {T.type=mkTypeNode(array,num.size,T (1).type )} S->if then S {if not typequal(.type,boolean) then type-error(s)} S->id:= {if not typequal(lookup(id.name),.type)then typeerror(s)} -> (1) + (2) {if not (typequal( (1).type,integer) and typequal( (2).type,integer))then type-error();.type=integer} -> (1) or (2) {if not (typequal( (1).type,boolean) and typequal( (2).type,boolean))then type-error();.type=boolean} ->num {.type=integer} ->true {.type=boolean} ->id {.type=lookup(id.name)} Yinliang Zhao 17