语法制导翻译技术及中间代码生成

本章主要介绍：语法制导翻译法的基本思想常见的几种中间代码的形式各种不同语法结构的语法制导翻译技术第五章语法制导翻译技术和

中间代码生成静态语义审查

审查每个语法结构的静态语义,即验证语法结构合法的程序,是否真正有意义。5.1概述如果静态语义正确,语义处理则要执行真正的翻译,即生成程序的某种中间代码的形式或直接生成目标代码。执行真正的翻译(1)属性对文法的每一个符号,引进一些属性,这些属性代表与文法符号相关的信息,如类型、值、存储位置等。与属性相关的信息,即属性值,可以在语法分析过程中计算和传递。1.属性文法5.2属性文法属性分为两类:综合属性其计算规则按“自下而上”方式进行,即规则左部符号的某些属性根据其右部符号的属性和(或)自己的其他属性计算而得。属性加工的过程即是语义的处理过程。综合属性和继承属性。E→E(1)+E(2){E.val=E(1).val+E(2).val}5.2属性文法继承属性其计算规则按“自上而下”方式进行,即规则右部符号的某些属性根据其左部符号的属性和(或)右部其他符号的某些属性计算而得。D→TL

{L.in=T.type}T→int{T.type=integer}T→real{T.type=real}L→L(1),id{L(1).in=L.in;Fill(id.entry,L.in)}L→id{Fill(id.entry,L.in)}5.2属性文法(2)属性文法为文法的每一个规则配备的计算属性的计算规则,称为语义规则(描述语义处理的加工动作)。属性文法包含一个上下文无关文法和一系列语义规则。语义规则:属性加工的过程即是语义的处理过程5.2属性文法语法制导翻译法的基本思想

为文法的每个产生式都配备一个语义动作或语义子程序。在语法分析的过程中，每当使用一条产生式进行推导或归约时，就执行相应产生式的语义动作,从而实现语义处理。E→E(1)+E(2){E.val=E(1).val+E(2).val}5.3语法制导翻译概述(语义子程序)

描述了一个产生式所对应的翻译工作。语义动作语义动作不仅指明了该产生式所产生符号串的意义，而且还根据这种意义规定了对应的加工动作（如查填各类表格、改变编译程序的某些变量的值、打印各种错误信息及生成中间代码等），从而完成预定的翻译工作。5.3语法制导翻译概述语法制导翻译法在语法分析过程中，依随分析的过程，根据每个产生式所对应的语义子程序(语义规则描述的语义处理的加工动作)进行翻译的方法。5.3语法制导翻译概述为文法每一产生式设计相应的求值的语义描述(语义动作)：例如，设有简单算术表达式的文法：E→E＋E|E*E|(E)|digit1.E→E(1)＋E(2)

{E.val＝E(1).val＋E(2).val}2.E→E(1)*E(2)

{E.val＝E(1).val*E(2).val}3.E→(E(1)){E.val＝E(1).val}4.E→digit{E.val＝Lex.digit}{7+8*5,3+8,6*5,…}5.3语法制导翻译概述E.val=47E.val=8E.val=40E.val=7E.val=5+5*871.E→E(1)＋E(2)

{E.val＝E(1).val＋E(2).val}2.E→E(1)*E(2)

{E.val＝E(1).val*E(2).val}3.E→(E(1)){E.val＝E(1).val}4.E→digit{E.val＝Lex.digit}句子7+8*5EEEEE5.3语法制导翻译概述语法制导翻译技术分为：自底向上语法制导翻译自顶向下语法制导翻译5.3语法制导翻译概述LR分析制导的具体实现方法:为文法的每一个产生式设计相应的语义动作为文法构造LR分析表5.3语法制导翻译概述扩充LR分析栈，以便存放文法符号对应的语义值语义值栈状态栈文法符号栈

S0$—

S1X1X1.val

SkXkXk.val.........修改总控程序:查分析表,当用某产生式归约时,调用相应的语义动作5.3语法制导翻译概述例如，设有简单算术表达式的文法：E→E＋E|E*E|(E)|digit1.E→E(1)＋E(2)

{E.val＝E(1).val＋E(2).val}2.E→E(1)*E(2)

{E.val＝E(1).val*E(2).val}3.E→(E(1)){E.val＝E(1).val}4.E→digit{E.val＝Lex.digit}为文法每一产生式设计相应的语义动作

(求值的语义描述)：5.3语法制导翻译概述2.为上述文法构造LR分析表如下图：90状态ACTIONGOTO+digit*()$ES3S9S5S4S2S3S2S3S5S4S2S5S2S3r4r4r4r4r1r1r1r2r3r2r3r3r2r2r3123456781678acc5.3语法制导翻译概述自下而上语法制导翻译法的特点:语义分析栈与语法分析栈同步操作当栈顶形成句柄执行归约时，调用相应的语义动作若将其翻译成某种中间代码,如何给出相应的语义描述?5.3语法制导翻译概述编译中常见的中间语言:逆波兰式（后缀式）三元式树形表示四元式5.4中间语言逆波兰式

逆波兰式除去了原表达式中的括号，并将运算对象写在前面，运算符写在后面，因而又称为后缀式。例如：逆波兰式a*bab*(a+b)*(c+d)ab+cd+*中缀表达式5.4.1逆波兰式逆波兰式表示法同中缀表示法相比其优点是:不再有括号,且运算符出现的顺序体现了中缀表达式的运算顺序2.易于计算机处理5.4.1逆波兰式逆波兰式ab+c*的处理过程如下图：baT1cT1T25.4.1逆波兰式逆波兰形式可以推广到其他语法结构：赋值语句V=E逆波兰式VE=条件语句逆波兰式ifES1;elseS2ES1S2￥5.4.1逆波兰式LR分析制导生成逆波兰式：

给出算术表达式翻译到逆波兰式的语义描述中间代码采取何种形式或计值根据各种语法成份的语义,给出翻译得到的代码结构的形式5.4.1逆波兰式LR分析制导生成逆波兰式例如:赋值语句V=E计算E值的代码将E值存放到V中的代码其代码结构:(3)给出从源结构到目标结构的变换方法例如，简单算术表达的文法：E→E＋E|E*E|(E)|i源结构a+b*c目标结构abc*+LR分析制导生成逆波兰式E→E＋E|E*E|(E)|i1.E→E(1)＋E(2)

{print+}2.E→E(1)*E(2)

{print*}3.E→(E(1)){空}4.E→i{printi}0.E'→E{空}E(1).code||E(2).code||+E(1).code||E(2).code||*LR分析制导生成逆波兰式2.为上述文法构造LR分析表如下图：LR分析制导生成逆波兰式90状态ACTIONGOTO+i*()$ES3S9S5S4S2S3S2S3S5S4S2S5S2S3r4r4r4r4r1r1r1r2r3r2r3r3r2r2r3123456781678acc三元式主要由三部分组成：（OP，arg1,arg2）其中OP是运算符，arg1,arg2分别是第一和第二两个运算对象。当OP是一目运算时，常常将运算对象定义为arg1。5.4.2三元式和树形表示例如a+b*c的三元式序列：(1)(*bc)(2)(+a(1))运算对象是指向符号表的某一项或指向三元式表的某一项。5.4.2三元式和树形表示1.三元式出现的顺序和语法成份的计值顺序相一致。三元式的特点：2.三元式之间的联系是通过指示器实现的。5.4.2三元式和树形表示间接三元式(1)间接三元式表:用来存放各三元式本身。(2)间接码表:按执行各三元式的顺序,依次列出各三元式在三元式表中的位置。注意:间接三元式表中不存放重复的三元式。5.4.2三元式和树形表示例如语句X=(A+B)*CY=D↑(A+B)三元式序列(1)(+,A,B)(2)(*,(1),C)(3)(=,X,(2))(5)(↑,D,(4))(4)(+,A,B)(6)(=,Y,(5))间接三元式间接码表三元式表(1)(2)(3)(1)(4)(5)(1)(+,A,B)(2)(*,(1),C)(3)(=,X,(2))(4)(↑,D,(1))(5)(=,Y,(4))5.4.2三元式和树形表示树形表示A*B+C*D+C*A*BD末端结点表示一个运算对象,每一个内结点表示一个一元或二元运算符。树形表示是三元式的翻版(3)+(1)*(2)*CABD5.4.2三元式和树形表示四元式主要由四部分组成：（OP，arg1,arg2,result）其中OP是运算符，arg1,arg2分别是第一和第二两个运算对象。当OP是一目运算时，常常将运算对象定义为arg1。5.4.3四元式例如X＝a*b＋c/d的四元式序列：(1)(*,a,b,T1)(2)(/,c,d,T2)(3)(+,T1,T2,T3)(4)(=,T3,-,X

)5.4.3四元式2.四元式之间的联系是通过临时变量实现的，这样易于调整和变动四元式。1.四元式出现的顺序和语法成份的计值顺序相一致。四元式的特点：3.便于优化处理。5.4.3四元式result:＝arg1OParg2

三地址语句:语句中是三个量的赋值语句,每个量占一个地址。三地址代码形式定义为：5.4.3四元式例如X＝a*b＋c/d的四元式序列：(1)(*,a,b,T1)(2)(/,c,d,T2)(3)(+,T1,T2,T3)(4)(=,T3,-,X

)相应的三地址语句序列为：（1）T1＝a*b（2）T2＝c/d（3）T3＝T1＋T2

（4）X＝T3

5.4.4四元式的翻译简单算术表达式和赋值语句

到四元式的翻译LR分析制导生成四元式例如A→i＝EE→E＋E∣E*E∣(E)|i1.给出算术表达式和赋值语句翻译到四元式的语义描述A→i＝EE→E＋E∣E*E∣(E)|i源结构目标结构（1）T1＝a*b（2）T2＝c/d（3）T3＝T1＋T2

（4）X＝T3

X＝a*b＋c/d简单算术表达式和赋值语句

到四元式的翻译语义函数emit（T＝arg1OParg2）

功能是生成一个三地址语句，并送到输出文件中。语义函数newtemp()

功能是产生一个新的临时变量名字，并回送新的临时变量名的整数码。如T1，T2等。简单算术表达式和赋值语句

到四元式的翻译(2)不进符号表，临时变量单词值部分用整数码表示。(1)送到符号表。对临时变量有两种不同的处理方法:简单算术表达式和赋值语句

到四元式的翻译语义过程Lookup（）

功能是审查是否出现在符号表中，在则返回其指针，否则返回NULL。语义变量E.place

表示存放非终结符E值的变量名在符号表中的入口地址或临时变量名的整数码。简单算术表达式和赋值语句

到四元式的翻译利用以上定义的语义变量和函数等，写出每一个规则式的语义动作如下：1.A→i＝E

{p=Lookup();if(P!=NULL)emit(p’＝’E.place);elseerror()}简单算术表达式和赋值语句

到四元式的翻译2.E→E(1)＋E(2)3.E→E(1)*E(2){E.place＝newtemp();emit(E.place’＝’E(1).place’＋’E(2).place)}{E.place＝newtemp();emit(E.place’＝’E(1).place’*’E(2).place)}简单算术表达式和赋值语句

到四元式的翻译4.E→（E(1)）{E.place＝E(1).place；}5.E→i{p＝Lookup();if(p!=NULL)E.place＝p;elseerror();}简单算术表达式和赋值语句

到四元式的翻译简单算术表达式和赋值语句

到四元式的翻译90状态ACTIONGOTO+i*()$ES2S12S8S7S6S5S3S8S6S5r5r5r5r5r2r2r2r3r4r3r4r4r3r41234567814910acc2.为文法构造LR分析表如下图

101112AS6S5S6S5:=r1S8S711 1.简单算术表达式的逆波兰式和四元式的表示例如–a+b*(–c+d)的逆波兰式a@bc@d+*+本章小结t1=@a

t2=@c

t3=t2+dt5=t1+t4例–a+b*(–c+d)的四元式

t4=b*t3本章小结i↑(i/(i–i))的逆波兰式

i↑(i/(i–i))的四元式

t1=i–i

t2=i/t1t3=i↑t2iiii–/↑例如：本章小结 2.编译中常用的中间代码:逆波兰式四元式三元式树形表示 3.什么是语法制导翻译法在语法分析过程中，依随分析的过程，根据每个产生式所对应的语义子程序(语义规则描述的语义处理的加工动作)进行翻译的方法。本章小结 4.采用自下而上的语法制导翻译法语义动作的设计（1）搞清楚源结构和目标结构（2）自下而上的语法制导翻译特点：栈顶形成句柄，归约时执行相应语义动作（3）给出从源结构到目标结构的变换方法本章小结例1.设文法及其相应的语义动作如下:S→bTc{print“1”}S→a{print“2”}T→R{print“3”}R→R/S{print“4”}R→S{print“5”}采用自下而上语法制导翻译,给出输入串bR/bTc/bSc/ac的翻译结果本章小结分析:首先对输入串

bR/bTc/bSc/ac画出语法树:ScTbRS/R/RS/RcTbaScTbRS再考虑归约时执行相应语义动作本章小结S→bTc{print“1”}S→a{print“2”}T→R{print“3”}R→R/S{print“4”}R→S{print“5”}14翻译结果为:53142431本章小结ScTbRS/R/RS/RcTbaScTbRSR→R/SS→bTcS→aT→R