语法制导翻译和中间代码生成课件

1、第八章 语法制导翻译和中间代码生成教学目的理解语义处理的功能与作用掌握语法制导翻译的方法掌握中间代码的翻译教学重点理解属性、属性文法的概念理解语法制导翻译的基本原理掌握几种常见的中间代码了解常见语法结构的翻译1引言语义处理：在词法分析程序、语法分析程序完成源程序结构分析后，由语法分析程序直接调用相应的语义子程序进行语义处理。 语义处理的功能：静态语义检查，验证语法结构合法的程序是否真正有意义代码生成，如果静态语义正确，则将源代码翻译成目标代码或中间代码。28.1 属性文法目前语义处理尚不能完全形式化，常采用属性文法和语法制导翻译方法进行描述。属性文法:包含一个上下文无关文法和一系列的语义规则，

2、描述为A=（G，V，F）G是一个上下文无关文法V是G中各个符号的属性的有穷集合F是有关属性的断言或谓词的有穷集合，每个断言和文法的某产生式相关联。语法制导翻译:在语法分析的过程中，完成附加在产生式上的语义规则描述的动作。3例1: 文法：ET1 + T2 | T1 or T2 Tnum | true | false分析 3+4ET1+T243T1.t=intT2.t=intT1.t=int AND T2.t=intN.t表示非终结符N相联的属性t4 属性文法中，每个产生式A都有一套与之相关联的语义规则，形式为 b:= f(c1, c2, , ck)。 （1）若b是产生式左部A的一个属性，c1,

3、c2, , ck是产生式右部符号或A的属性，则b是A的综合属性。在分析树中，一个结点的综合属性值是从其子结点的属性值计算出来的。（2）若b是产生式右部符号X的一个属性，c1, c2, , ck是A或右部符号的属性，则b是X的继承属性。在分析树中，一个结点的继承属性值是由该结点兄弟结点和父结点的属性值计算出来的综合属性和继承属性5例2：简单算术表达式的语义描述 LE print (E.val) EE1+T E.val := E1.val +T.val ET E.val := T.val TT1*F T.val := T1.val *F.val TF T.val := F.val F(E) F.v

4、al := E.val Fdigit F.val := digit.lexval 其中E、T、F都有属性val，都是综合属性。 Lexval 由词法分析的结果提供EE1+TE.val := E1.val +T.val6例3：变量的类型说明 规则 语义规则 D TL L.in:=T.type /将L.in属性值设置为T.type T int T.type=integer Treal T.type:=real L L1,id L1.in:=L.in addtype(id.entry, L. in) /产生虚属性 L id addtype(id.entry, L. in) 其中， L.in是继承属性

5、，T有综合属性type。Addtype：把标识符的类型信息登录在符号表中相关项内DTLintLid2,id1属性信息传递情况7结论:（1）非终结符可以有综合属性和继承属性，但文法开始符没有继承属性（2）终结符只有综合属性,由词法分析程序提供88.2 语法制导翻译 1、基于属性文法的语法制导翻译：对单词符号串进行语法分析，构造语法分析树，再根据需要构造属性依赖图，遍历语法树，并在语法树的各结点处按语义规则进行计算。属性依赖图DTL4realtypeLLid1,id3,id2in5in7in9101entry82entry3entry6例4：real id1, id2, id3; D TL；Tre

6、alL L,id； L id 9例5：分析2+3*5 归约时完成语义处理LEE+TTF2T*FF53LEE+TTF(2)T*FF53LEE(2)+T(15)综合属性可自下而上进行计算。2、简单算术表达式求值：用一个产生式进行归约时就执行相应的语义动作，在分析一个句子时，句子的值同时产生。（自下而上分析）102+3*5的分析和计值过程（p142表7.8）118.3 中间代码形式源程序目标代码编译程序一、编译程序1、2、3、源程序词法语法语义中间代码目标代码生成源程序词法语法语义中间代码目标代码生成优化优化后的中间代码12二、几种常用的中间代码形式中间代码逆波兰表 示四元式三元式树约定：LJ表示转

7、向某标号处； TJ表示按真跳转；FJ表示按假跳转；RJ表示无条件跳转13*-表达式的树表示中缀：a*b-(c+d)/(e-f)ab/+cd-ef（后缀）逆波兰： ab*cd+ef-/-（一）树14（二）逆波兰表示1、赋值语句的逆波兰表示赋值语句 :=逆波兰表达式 :=例1： y:=(a+b)*c; yab+c*:=2、转向语句的逆波兰表示 转向语句：goto 逆波兰式： LJ 例2：100：write（晚上好）； . goto 100;逆波兰表示：100LJ 153、条件语句的逆波兰表示（a）无条件跳转： 逆波兰式： RJ 例3： 100RJ （b）有条件跳转： TJ表达式为真跳转到序号处 F

8、J 表达式为假跳转到序号处16 格式： ifthenelse; 逆波兰表达式： FJ 序号1指语句2的逆波兰式的第1个符号处 RJ 序号2是指紧跟语句2的逆波兰式的最后1个符号处 17例3：条件语句的逆波兰表示if ab then x:=a+b else x:=a-b1234567891011121314151617abi+j then begin k:=k-1; goto 10 end else k:=i*i-j*j i:=0; j:=0;end;(1)block(2)k100:=(5)kij+19FJ(12)kk1-:=5RJ(19)kii*jj*-:=(28)i0:=j0:=(34)bl

9、ockend(1) block(2) k100:=(5) 10:(7) kij+ 21FJ(14) kk1-:= 10LJ(21) kii*jj*-:=(30) i0:=(33) j0:=(36) blockend ( )( )( )( )21FJ10LJ194、循环语句的逆波兰表示循环语句：(1)i1:=(4)i100=21FJ(9)ssi+:=(14)ii1+:=4RJ(21)逆波兰表示for i:=1 to 100 do s:=s+ii:=1;10:if i=100 then begin s:=s+i; i:=i+1; goto 10 end等价代码练习1：P202 1（7）20（三）四

10、元式四元式：四元式定义为一个四元组： （,） 其中指运算结果。双目运算：a+b（ + ，a , b , T ）（,）临时变量，存放a+b的结果单目运算：a（ ，a , / , T ）单目运算无需分量2，写成/21例1:a*b+c/d表达式（*, a, b, T1）（/, c, d, T2）（+, T1, T2, T3）四元式1、表达式的四元式:例2：（含单目运算）-（a/b+c）表达式 （/,a, b, T1）（+, T1, c, T2）（ ,T2, /, T3）四元式2、赋值语句的四元式x:= -（a/b+c）赋值语句（/, a, b, T1）（+,T 1, c, T2）（ , T2, /,

11、 T3）四元式(:=, T3, / ,x)例3:223、转向语句和条件语句的四元式（RJ,A,/,/)（TJ,A,B,/)（FJ,C,B,/)无条件跳转到序号为A的四元式B为真跳转到序号为A的四元式B为假跳转到序号为C的四元式（1）跳转语句:23（2）条件语句: ifthenelse;四元式： （FJ,A,T,/) 序号A是指语句2的开始处。 （RJ,C,/,/) 序号C是指紧跟语句2的四元式的编号 : :24例4：条件语句的四元式:if ab then x:=a+b else x:=a-b（1） （,a,b,T1)（2） （FJ,6,T1,/)（3） （+,a,b,T2)（4） （:=,T2

12、,/,x)（5） （RJ,8,/,/)（6） （-,a,b,T3)（7） （:=,T3,/,x)（8） ( . )25例5：循环语句的四元式:循环语句：for i:=1 to 100 do s:=s+ii:=1;10:if i=100 then begin s:=s+i; i:=i+1; goto 10 end(1)（:=,1,/i)(2)(=,I,100,B)(3)(FJ,7,B,/)(4)(+,s,i,s)(5)(+,i,1,i)(6)(RJ,2,/,/)(7)四元式表示等价代码26（四）三元式三元式： ( ,）四元式： （,）三元式与四元式的区别：四元式运算结果存储在变量中；三元式运算结

13、果用三元式的位置或序号来代替；a*b+c/d表达式（*,a,b,T1）（/,c,d,T2）（+,T1,T2,T3）四元式a*b+c/d表达式(1) (*,a,b）(2) (/,c,d）(3) (+,(1),(2)）三元式27例1a*b+c/d表达式(1) (*a,b）(2) (/,c,d）(3) (+,(1),(2)）三元式1、表达式的三元式：2、赋值语句的三元式x:= -（a/b+c）赋值语句 (1)（/,a,b, ）(2)（+,(1),c）(3)（ ,(2),/）三元式(4)(:=,(3),x)例2283、转向语句和条件语句的三元式（RJ,A,/)（TJ,A,B)（FJ,A,B)无条件跳转

14、到序号为A的三元式B为真跳转到序号为A的三元式B为假跳转到序号为A的三元式（1）跳转语句:（2）条件语句:ifthenelse;三元式： （FJ,A,B) 序号A指语句2的第一个三元式的编号 （RJ,A,/) 序号A指紧跟语句2的三元式的编号29（1） （, a, b)（2） （FJ, 6, (1)（3） （+, a, b)（4） （:=, (3), x)（5） （RJ, 8, /)（6） （-, a, b)（7） （:=, (6), x)（8） ( . )三元式（1） （, a, b, T1)（2） （FJ, 6, T1 ,/)（3） （+, a, b, T2)（4） （:=, T2, /,

15、 x)（5） （RJ, 8, /, /)（6） （-, a, b, T3)（7） （:=, T3, /, x)（8） ( . )四元式例3：条件语句 if ab then x:=a+b else x:=a-b 四元式与三元式比较30例4：循环语句的三元式循环语句：(1)(:=,1,i)(2)(=,i,100)(3)(FJ,9,(2)(4)(+,s,i)(5)(:=,(4),s)(6)(+,i,1)(7)(:=,(6),i)(8)(RJ,2,/)(9)三元式表示for i:=1 to 100 do s:=s+ii:=1;10:if i=100 then begin s:=s+i; i:=i+1;

16、 goto 10 end等价代码练习2：P202 1（7）三元式，四元式318.4 简单赋值语句的翻译四元式: (op, arg1, arg2, result)几个函数与符号lookup():审查是否在符号表中,如存在, 则返回该表项的指针, 否则返回nil。emit(): 将四元式输出到中间代码文件中。newtemp: 生成一个新的临时变量/单元。E.place: 存放E值的变量名在符号表中的位置。32简单赋值语句的四元式翻译(1) S id := E P:=lookup () ; if Pnil then emit( P:=E.place) else error (2) EE1+E2 E.place:= newtemp; emit(E.place := E1.place+E2.place) (3) E - E1 E.place:=newtemp; emit(E.place := uminus E1.place)(4) E( E1) E.place:= E1.place(5) Eid E.place:=newtemp; P:=lookup(); if Pnil then E.place:=P else error若是乘法运算呢？33类型转换的语义处理：EE1*E2 E.pla