编译原理课件 第 7 讲 语法制导翻译和中间代码生成(1)

1、源语言程序源语言程序中间代码中间代码汇编代码汇编代码词法分析词法分析语义分析语义分析语法分析语法分析中间代码生成中间代码生成代码生成代码生成在编译中的逻辑阶段在编译中的逻辑阶段前端处理前端处理后端处理后端处理语义处理语义处理1、使逻辑结、使逻辑结构简单明确构简单明确2、与机器相、与机器相关的某些实现关的某些实现细节放在代码细节放在代码生成阶段生成阶段3、可进行代、可进行代码优化码优化源语言程序源语言程序汇编代码汇编代码词法分析词法分析语义分析语义分析语法分析语法分析代码生成代码生成前端处理前端处理后端处理后端处理 语义处理语义处理类型检查的属性文法：类型检查的属性文法： 语 义 规 则L EE

2、 E1+TE TT T1 * FT FF (E)F digitPrint(E.val) E.val:=E1.val+T.val E.val:=T.val T.val:=T1.val F.val T.val:=F.valF.val:=E.valF.val:=digit.lexval产 生 式综合属性综合属性val综合属性综合属性n左部符号的左部符号的综合属性综合属性是从该产生式右部文法符号的属性值计算出来的；是从该产生式右部文法符号的属性值计算出来的；n在分析树中，如果一个结点的某一个属性由其子结点的属性确定，则称在分析树中，如果一个结点的某一个属性由其子结点的属性确定，则称这种属性为该结点的这

3、种属性为该结点的综合属性综合属性。产生副作用产生副作用的语义规则的语义规则，如打印一个如打印一个值、向符号值、向符号表中插入信表中插入信息或更新一息或更新一个全程变量个全程变量等。等。语义规则函数都不具有副作用的语法语义规则函数都不具有副作用的语法制导定义称为制导定义称为属性文法。属性文法。LE.val=19E.val=15T.val=4T.val=15F.val=4T.val=3F.val=3F.val=5digit.lexval=4digit.lexval=5digit.lexval=3+*3*5+4的带注释的分析树的带注释的分析树如果一个语法制如果一个语法制导定义仅仅使用导定义仅仅使用综

4、合属性，则称综合属性，则称这种语法制导定这种语法制导定义为义为S属性定义属性定义。通常采用通常采用自底向自底向上的方法上的方法对其分对其分析树加注释，即析树加注释，即从树叶到树根，从树叶到树根，按照语义规则计按照语义规则计算每个节点的属算每个节点的属性值。性值。生 产 式语 义 规 则D TL T int T real L L1,idL idL.in:=T.typeT.type=integerT.type:=real L1.in:=L.in addtype(id.entry,L.in) addtype(id.entry,L.in)继承属性继承属性L.in过程调用：过程调用：将每个标识将每个标识

5、符的类型信符的类型信息登录到符息登录到符号表的相关号表的相关项中项中 产 生 式语 义 规 则D TL T int T real L L1,idL idL.in:=T.typeT.type=integerT.type:=real L1.in:=L.in addtype(id.entry,L.in) addtype(id.entry,L.in)DL.in= realL.in= realL.in= realT.type=realrealid2id1id3.，addtype(id3.entry,L.in)addtype(id2.entry,L.in)addtype(id1.entry,L.in)计算

6、方法计算方法：自左向右扫描逆波兰式，遇到运算对象则入栈，：自左向右扫描逆波兰式，遇到运算对象则入栈，遇到算符则将相应数目的运算对象出栈计算后结果入栈遇到算符则将相应数目的运算对象出栈计算后结果入栈。复杂性：复杂性：压栈的可能是地址（如变量赋值），不是值；压栈的可能是地址（如变量赋值），不是值；栈中不一定产生结果。栈中不一定产生结果。例例a:=b*c+b*c将表达式将表达式b*c+b*c的值送到变量的值送到变量a(地址地址)，栈中无结果值。栈中无结果值。 把下述产生式定义的算术表达式映射到后缀式把下述产生式定义的算术表达式映射到后缀式表示：表示： EE+T E T T T F T F F (E)

7、 F a E = ET+ E = T T = TF T = F F = E F = a 产生式 翻译成分 EE+T E T T T F T F F (E) F a E = ET+ E = T T = TF T = F F = E F = a 产生式 翻译成分将下列语句翻译成后缀式：后缀式： if xy then y=y+z else x=x+z错误的翻译：错误的翻译： （ 翻译成：翻译成：xyyzy+ =z+xx=正确的翻译：正确的翻译：x yy zy+=z +x x=L1JzJzL2JmpJmp L1 L2:=a+*bcbd三元式表示三元式表示树形表示树形表示返回指向返回指向id的指针的指针

8、输出四元式输出四元式生成临时变量生成临时变量E.place:值值E的位置的位置(2) (3) 返回返回(4) E - E1 E.place:=newtemp; emit(E.place“:=”“uminus” E1.place)(5) E( E1) E.place:= E1.place(6) Eid P:=lookup(); if P nil then E.place:=P else error返回返回# A:=-B*(C+D)#查看语意义子程序查看语意义子程序13查看语意义子程序查看语意义子程序46 栈栈 余留输入字符余留输入字符 语意义动作语意义动作 产生的四元式产生的四元式

9、#idA :=-B*(C+D)#idA := -B*(C+D)#idA :=- B*(C+D)#idA :=-idB *(C+D)#idA :=-EB *(C+D)# Sub6#idA :=ET1 *(C+D)# Sub4 (，B， ，T1）#idA := ET1 * (C+D)#idA := ET1 * ( C+D)#idA := ET1 * (idC +D)#idA := ET1 * (EC +D)# Sub6#idA := ET1 * (EC+ D)#查看语意义子程序查看语意义子程序13查看语意义子程序查看语意义子程序46 栈栈 余留输入字符余留输入字符 语意义动作语意义动作 产生的四元

10、式产生的四元式#idA := ET1 * (EC+ D)#idA := ET1 * (EC+idD )#idA := ET1 * (EC+ED )# Sub6#idA := ET1 * (ET2 )# Sub2 (+，C，D，T2）#idA := ET1 * (ET2) #idA := ET1 * ET2 # Sub5#idA := ET3 # Sub3 (*，T1，T2，T3）#S # Sub1 (:=，T3， ，A）(1) （ ， B ， ， T1 ）(2) （ +， C ， D， T2 ）(3) （ *， T1 ，T2， T3 ）(4) （ :=，T3 ， ， A ）E.false控制语

11、句控制语句 Sif E then S1 else S2 E 的代码的代码 E.true E.true: S1的代码的代码 goto outE.false: S2的代码的代码out:1 . 把条件转移的布尔表达式把条件转移的布尔表达式 E 翻译成仅含翻译成仅含 条件真条件真 转转 和和 无条件无条件 转转 的四元式的四元式 E：a rop b ?if a rop b goto E.true goto E.false如如 ：ab or cd and ef 可可 翻译成如下四元式：翻译成如下四元式：(1) if ab goto E.true(2) goto (3)(3) if cd goto (5)

12、(4) goto E.false(5) if ef goto E.true(6) goto E.false (翻译翻译 不是最优不是最优)2拉链返填拉链返填 （10） goto L （10）goto 0 链尾链尾 （10）（20） goto L （20）goto 10 （30） goto L (30) goto 20 链头链头（30）（40）L： （40）L: ?语句语句 if ab or cd and ef then S1 else S2的四元式的四元式(1) if ab goto (7) (E.true ) (1)和和(5）(2) goto (3) 拉链拉链（真）（真）(3) if cd

13、goto (5)(4) goto (p+1)(E.false)(4) 和和(6)(5) if ef goto (7)拉链拉链（假）（假）(6) goto (p+1)(7)( S1的四元式的四元式 (p-1) ）(p) goto (q)(p+1) (S2的四元式的四元式(q-1) ）(q)(1) if ab goto (E.true )(2) goto (3)(3) if cd goto (5)(4) goto (E.false)(5) if ef goto (E.true ) (6) goto (E.false) (E.true)( S1的四元式序列的四元式序列 ）(p) goto (q)(E

14、.false) (S2的四元式序列的四元式序列(q-1) ）(q)语义描述使用的变量和过程：语义描述使用的变量和过程： E.true ： “真真”链，链， E.false ： “假假”链链 。 E.codebegin ： E 的第一个四元式的第一个四元式 Nextstat： 下一四元式地址下一四元式地址 过程：过程： emit( ) 输出一条四元式输出一条四元式 merge(p1, p2) 把把 p1的链头填在的链头填在p2 的链尾的链尾例：例： merge(p1, p2)(p10) 0 p1 链链 (p100) p10(p1) p100(p20) 0p2 链链 (p200) p20(p2)

15、p200 backpatch(p,t) 把把 p 所链接的每个四元式所链接的每个四元式的第四区段都填为的第四区段都填为t语义描述使用的变量和过程：语义描述使用的变量和过程： E.true ： “真真”链，链， E.false ： “假假”链链 。 E.codebegin ： E 的第一个四元式的第一个四元式 Nextstat： 下一四元式地址下一四元式地址 过程：过程： emit( ) 输出一条四元式输出一条四元式 merge(p1, p2) 把把 p1的链头填在的链头填在p2 的链尾的链尾例：例： merge(p1, p2)(p10) 0 p1 链链 (p100) p10(p1) p100(

16、p20) p100p2 链链 (p200) p20(p2) p200 backpatch(p,t) 把把 p 所链接的每个四元式所链接的每个四元式的第四区段都填为的第四区段都填为t自下而上分析中的一种翻译方案：自下而上分析中的一种翻译方案：(1) EE1 or E2 backpatch(E1.false, E2.Codebegin); E.Codebegin:= E1.codebegin; E.true:=merge(E1.true, E2.true) E.false:= E2.false(2) EE1 and E2 backpatch(E1.true, E2.codebegin); E.Codebegin:= E1.codebegin; E.true:= E2.true; E.false:= merge(E1.false, E2false);(3) Enot E1 E.true:= E1.false; E.Codebegin:= E1.codebegin; E.false:= E1.true(4) E(E1) E.true:= E1.true; E.Codebegin:= E1.co