[理学]第5章 语法制导翻译及中间代码.ppt

第5章 语法制导翻译及中间代码生成, 5.1 语法制导翻译 5.2 中间代码的形式 5.3 简单赋值语句的翻译 5.4 布尔表达式的翻译 5.5 控制语句的翻译,5.1 语法制导翻译,静态语义审查：审查每个语法结构的静态语义，即验证语法结构合法的程序，是否真正有意义。如类型检查。,语义处理是指两个功能：,动态语义处理：如果静态语义正确，语义处理则要执行真正的翻译，即，或者将源程序翻译成程序的一种中间表示形式（中间代码），或者将源程序翻译成目标代码。,翻译的任务：首先是语义分析和正确性检查，若正确，则翻译成中间代码或目标代码。 使用的方法：语法制导翻译。 基本思想：根据翻译的需要设置文法符号的属性，以描述语法结构的语义。即语法制导翻译法使用属性文法为工具来描述程序设计语言的语义。,1、属性文法(Syntax-directed definitions),(1) 属性,对文法的每一个符号， 引进一些属性，这些属性代表与文法符号相关的信息,，如类型、值、存储位置等。属性值，可以在语法分析过程中计算和传递。,属性分为两类:,属性加工的过程即是语义的处理过程。,综合属性和继承属性。,综合属性：其计算规则按“自下而上”方式进行， 即规则左部符号的某些属性根据其右部符号的属性和(或)自己的其他属性计算而得。在语法树中，一个结点的综合属性由该结点 的子结点的属性值确定。,继承属性：其计算规则按“自上而下”方式进行， 即规则右部符号的某些属性根据其左部符号的属性和(或)右部其他符号的某些属性计算而得。继承属性值是由此结点的父结点和（或）兄弟结点的某些属性值来决定的。,(2) 属性文法,属性文法包含一个上下文无关文法和一系列语义规则。,语义规则：为文法的每一个规则配备的计算属性的计算规则， (描述语义处理的加工动作) 。,这些语义规则附在文法的每个产生式上，在语法分析过程中，执行语义规则描述的动作，从而实现语义处理。 即： 附在文法的每个产生式上的语义规则描述了语义处理的加工动作。,A（G，V，F）， G: 是一个上下文无关文法 V: 有穷的属性集,每个属性与文法的一终结符或非终结符 相连。 F: 关于属性的属性断言或谓词集.每个断言与一个产生式 相联。一个断言即一个语义规则，描述各属性关系。,属性文法是一个三元组：,属性文法的主要思想有两点： 对于每个文法符号引进相关的属性符号； 对于每个产生式写出属性值计算的规则。,例如定义表达式的文法如下：,为文法符号E引进属性val表示E的值，记为E.val，语义规则以赋值语句的形式给出，附在每个产生式后。为了明确E的不同出现位置，用上角标区别。终结符n的值是词法分析程序提供的，这里用n.lex表示。下面给出属性文法： EE1+E2 E.val := E1.val +E2.val E(E1) E.val := E1.val En E.val := n.lex,EE+E E(E) En 给出定义表达式值的属性文法。,例1 表达式计算的语法制导定义,产生式 语义规则,LE print(Eval) E E1+T E val := E1 val+T val E T E val := T val T T1*F T val := T1 val+F val T F T val := F val F (E) F val := E val F digit F val := digitlexval,digitlexval:=3,Fval:=3,Tval:=3,digitlexval:=5,Fval:=5,Tval:=15,*,Eval:=2,+,digitlexval:=2,Fval:=2,Tval:=2,Eval:=17,L,例2：输入23*5,只有综合属性,例2：变量说明的类型定义 int a,b,c,将L.in的属性值置为该说明语句T指定的类型,把每个标识符的类型信息登录在符号表相关项中（虚属性）,非终结符T有一综合属性type，它的值由关键字决定（int或real）。,与产生式DTL相联的语义规则L.in:=T.type，将L.in的属性值置为该说明语句指定的类型。,属性L.in被沿着语法树下传到下边结点，与L产生式相联的规则里使用了它。,T,L,L,id3,L,id2,D,id1,int,1 entry,2 entry,3 entry,4 type,5 in,6 in,7 in,例如：int a,b,c, 具有继承属性的属性文法,2、语法制导翻译,只含有综合属性的称为S属性文法 综合属性可以在分析输入符号串的同时采用自下而上的分析器来计算。分析器可以保存与栈中文法符号有关的综合属性值，每当进行归约时，新的属性值就由栈中正在归约的产生式右边符号的属性值来计算。 S属性文法的翻译器很容易建立。通常可借助于LR分析器实现。,在语法分析过程中，依随分析的过程，根据每个产生式所对应的语义子程序(或语义规则描述的语义处理的加工动作)进行翻译的方法。,分析器模型,例如：*的分析和计值过程,步骤 动作 状态栈 语义栈(值栈) 符号栈 余留输入串 ） 0 3* ） 05 2 3* ） r6 03 * ） r4 02 * ） r2 01 * ） 016 * ） 0165 * ） r6 0163 * ） r4 0169 * ） 01697 * ） 016975 - * ） r6 01697510 * # ） （15） ） （） ）接受,5.2 中间代码形式,“中间代码生成”程序的任务是：把经过语法分析和语义分析而获得的源程序中间表示翻译为中间代码表示。 方法：语法制导翻译。 采用独立于机器的中间代码的好处： 便于编译系统的建立和编译系统的移植； 便于进行独立于机器的代码优化工作。 中间代码表示形式有： 语法树 后缀式 三地址代码表示（三元式、四元式）,1）后缀式,表示：将运算对象写在前面，运算符号写在后面。a+b写成ab+ 特点：运算符处于运算量之后； 运算符在表示式中出现的次序和计算的先后次序一致； 不用括号； 易于计算机处理表达式。利用栈自左至右扫描表达式后缀表示，碰到运算对象入栈；碰到运算符，则执行相应运算（出栈），结果入栈，最后结果留在栈顶。,语法制导生成后缀式举例：,”|”为捻接运算，在机器内实现是通过数组，利用post数组存放后缀式，k为下标，初值为1。 则：当用产生式EE1 + E2 归约句柄E1 + E2 时，分别与E1、E2相关的后缀式子串E1.nptr、E2.nptr均已在post 中，只需将运算符“+”放入post即可。,Postp:=“op”,p:=p+1,Postp:=“id”,p:=p+1,例：EE+T Postp:=“+”,p:=p+1 ET TT*F Postp:=“*”,p:=p+1 TF F(E) Fi Postp:=“i”,p:=p+1,a+b*c生成后缀式,分析栈 当前符号 余留输入串 操作 后缀表示 # a b*c 移进 #a + b*c# 归约 a #F + b*c# 归约 #T + b*c# 归约 #E + b*c# 移进 #E+ b *c# 移进 #E+b * c# 归约 ab #E+F * c# 归约 #E+T * c# 移进 #E+T* c # 移进 #E+T*c # 归约 abc #E+T*F # 归约 abc* #E+T # 归约 abc*+ #E,2）四元式,四元式：是一种更接近目标代码的中间代码形式，由于该形式的中间代码便于优化处理，因此得到广泛应用。 可用一种“三地址语句”等价表示，一般形式为： （op，arg1，arg2，result） Op为运算符； Arg1，arg2为两个运算对象：变量、常量、临时变量； Result中存放运算结果。,每个四元式只能有一个运算符，因此一个复杂表达式可由多个四元式构成的序列表示。 例：A+B*C写成： （*，B，C，T1） （+，A，T1，T2） 若op为一元、零元(无条件转移)时，arg1、arg2可省略。 会引入一些临时变量。,注 意！,3）三元式,一般形式为：（i）（op，arg1，arg2）,其中：(i)为三元式编码，也代表了该式的运算结果。,例：a:=-b*(c+d) 其三元式表示写成： （1）(-，b， ) （2）(+，c，d) （3）(*，(1)，(2) （4）(:=，a，（3）) 特点：三元式比四元式空间少；三元式间的相互引用频繁，因此不便于优化。为此引入间接三元式。,1、辅助函数：,1）LOOKUP（name）：以name（变量名）查符号表，若在符号中，则将其表项位置（入口位置）作为LOOKUP的值，否则，取值为null。,2）ENTER（name）：在符号表中以名字name新登记一项，并将此项的位置作为enter值。,5.3 简单赋值语句的翻译,3）ENTRY（name）：以name为名查、添符号表，描述为： function entry(name) entry:=lookup(name); if entry=null then entry:=enter(name),对于先说明后使用的语言，若在翻译表达式时，遇到的变量名不在表中，则程序出错。即 if entry=null then error,5）GEN（op，arg1，arg2，result）：产生一个四元式将它送入四元式表中，并以此四元式在四元式表中的位置作为返回值。,4) Newtemp函数，产生一个新的临时变量。返回值为标识此临时变量的整数码。,6) E.place属性：表示存放E值的变量名在符号表的入口或整数码（若E是临时变量）。,实例,2、赋值语句的属性文法,分析栈 当前符号 余留输入串 语义栈place 四元式 # A := B*(C+D) #A := B*(C+D) A #A:= B *(C+D) A_ #A:=B * (C+D) A_ B ，归约 #A:=E * (C+D) A_ B #A:=E* ( C+D) A_ B_ #A:=E*( C +D) A_ B_ _ #A:=E*(C + D) A_ B_ _C,归约 #A:=E*(E + D) A_ B_ _C #A:=E*(E+ D ) A_ B_ _C _ #A:=E*(E+D ) # A_ B_ _C _D,归约 #A:=E*(E+E ) # A_ B_ _C _D,归约 (+,C,D,T1) #A:=E*(E ) A_ B_ _T1 #A:=E*(E) # A_ B_ _T1_,归约 #A:=E*E # A_ B_ T1,归约 (*,T1,B,T2) #A:=E # A_T2, 归约 (:=,T2,-,A) #E # ACC,例如：A:=B*（C+D）,文法,实际上：在表达式运算中要考虑是否类型冲突，若有，需进行类型转换。,Sid:=E if id.type=int GEN(itr，E.place，-，T) GEN(:=，T，-，id.place) ,1、布尔表达式: 用布尔运算符号（，）作用到布尔变量或关系表达式上而组成的表达式。 布尔表达式的作用： 1. 计算逻辑值，注意计算时的优先级。 2. 控制流语句，如if-then，if-then-else和 while-do语句中的条件表达式 本节考虑由如下文法生成的布尔表达式： EE E| E E| E|(E)| id rop id|true|false,5.4 布尔表达式的翻译,方法一：用数值表示真假，对布尔表达式的求值可如同算术表达式求值一步步计算。 例如：ABC，其四元式为: (，B，C，T1) (，A，T1，T2） 方法二：采取某种优化措施。即将任何布尔表达式描述为等价的if-then-else结构。 例AB:if A then true else if B then true else false AB：if A then if B then true else false else false A：if A then false else true,方法一很容易写出相应的四元式，从而表示出每个产生式的语义动作。,2、布尔表达式的翻译方法,方法二涉及如何翻译if-then-else结构的问题。,3、作为条件控制的布尔式翻译,E.code,S1.code,E.true:,S2.code,E.false:,goto S.next,.,S.next:,to E.true,to E.false,(a) if-then-else,if-then？,1）条件语句 if E then S1 else S2 E的作用在于控制对 S1、S2的选择，因此结果无需最终保留。通过程序的控制流，即用程序中控制转移到达的位置来表示布尔表达式的值。,对作为转移条件的布尔式，其转移可用下述三种四元式表示： (jnz，A，-，P)：若A为真(1或非0)则转向第P四元式 (jrop，A1，A2，P)：若A1 rop A2为真，则转向第P四元式 (j，-，-，P)：无条件转向P四元式,例如：if ABD then S1 else S2 翻译成四元式为： （1） (jnz，A，-，？) A的真出口 （2） （j，-，-，？） A的假出口 （3） （j，B，D，?） BD的真出口 （4） （j，-， -， ？ ） BD的假出口 （5） 关于S1的四元式 （P） （j，-，-，？） 跳过S2的代码段 （P+1）关于S2的四元式 （q） s2后的语句,3,5,5,P+1,q,(2)可删除,可优化吗？,分 析,(1)(4)是布尔式 ABD 的代码，他们全是条件转移或无条件转移四元式，取代了原来的布尔运算。 A的真出口和BD的真出口相同(5)S1的第一个四元式(布尔式的真出口) A的假出口为BD的第一个四元式。 BD的假出口是整个布尔式的假出口S2的第一个四元式。 (2)四元式可删除，(3)、(4)也可合并代码优化。,翻译布尔式时要解决的问题 1、确定每个四元式的第四项，即转向的位置真假出口 2、拉链、回填,问题1：确定一个布尔表达式的真假出口,EE(1) E(2) 若E(1)为真，则E为真，因此 E(1)的真出口是E的真出口 若E(1)为假，则计算E(2), E(1)的假出口为E(2)的第一个四元式, E(2)的真假即为E的真假出口,EE(1) E(2): 若E(1)为假，则E为假，因此E(1) 的假出口是E的假出口 若E(1)为真，则计算E(2), E(2)的真假即为E的真假出口, E(1)的真出口为E(2)的第一个四元式,E E(1)： E(1)的真出口是E的假出口；E(1)的假出口是E的真出口。,问题2：拉链、回填,翻译过程中常出现若干转移四元式转向同一目标。但此目标的具体位置未确定。 将这些四元式用“拉链”的方法链接起来，用一指针指向链头，在确定了目标四元式后，再“回填”此链。 对一个布尔表达式E，应有两条链： 真出口链（T链） 假出口链（F链） 用属性 ETC，EFC记录。,（1）（jnz，A，-，0 ） （2）（j，-，-，0 ） （3）（j，B，D，0） （4）（j，-，-，0 ） （5）关于S1的四元式 （P）关于S2的四元式,1,3,拉链,回填,5,5,P,例：if ABD then S1 else S2,回填,为了方便对布尔式生成相应的四元式，可对上述文法进行改写，以利于编制相应的语义子程序。,EE E| E E| E|(E）| id rop id| id E E E E 1）语义变量和语义过程 为了实现“拉链”和“回填”及处理ETC，EFC，需定义如下变量和过程：,4、布尔式四元式翻译,NXQ指示器指示所要产生的下一个四元式序号(在四元式表中位置)，初值为1，每当执行一次GEN后，NXQ自动加1； GEN（op，arg1，arg2，Result ） 同前，产生一个四元式送入四元式表中，并以此四元式在四元式表中位置作为返回值； MERGE（P1，P2）拉链函数，把以P1、P2为链首的两条链合并为一，作为函数值，回送合并后的链首； BACKPATCH(P，t)回填过程，把P所链接的每个四元式resule字段均填上t。,2）每个产生式的语义子程序,(1) Eid,ETC:=NXQ，EFC:=NXQ+1 GEN（jnz，entry(id)，-，0） GEN（j，-，-，0） ,(2) E id1 rop id2, ETC:=NXQ，EFC:=NXQ+1 GEN（jrop，entry(id1)，entry(id2)，-，0） GEN（j，-，-，0）,(3) E (E1),ETC:=E1TC，EFC:=E1FC ,(4) E E1,ETC:=E1FC，EFC:=E1TC ,(5) E E1,BACKPATCH(E1TC，NXQ） E FC:=E1FC,(6) EE E2, ETC:=E2TC， EFC:=MERGE(EFC，E2 FC) , EFC:=E2FC， ETC:=MERGE(ETC ，E2 TC) ,(7) E E1, BACKPATCH(E1FC，NXQ） ETC:=E1TC,(8) E E E2,例: 重新考虑表达式ab or cd and ef 一棵作了注释的分析树如下图所示,E.T=100,104 E.F=103,105,E1.T=100 E1.F=101,E4.T=104 E4.F=103,105,OR,a,b,E2.T=102 E2.F=103,E3.T=104 E3.F=105,and,c,e,d,f,100 : ( j，a，b， 0 ) 101 : ( j，-，-， 0 ) 102 : ( j，c，d，0 ) 103 : ( j，-，-，0 ) 104 : ( j，e，f，0 ) 105 : ( j，-，-，0 ),104,103,102,100,ab or cd and ef 的四元式,对于翻译后最终归约所得的E，具有两个语义属性E.TC、E.FC，分别指向对应四元式序列的T链、F链，这两个链的回填，需根据E所处的程序环境进一步处理：,注 意,若E用于条件语句if-then-else时，则当扫视到then时，应以当前NXQ值回填E的T链，对F链，则在扫视到else之后进行。,注 意,若E仅用于计算值，可引入临时变量t表示E计算结果，拓广文法S E，该产生式语义动作为：,t：=NEWTEMP； BACKPATCH(ETC，NXQ）， BACKPATCH(EFC，NXQ+2）， GEN（:=，1，-，t）， GEN（j，-，-，0）， GEN（:=，0，-，t,常见控制语句文法GS： （1）Sif E then S （2） | if E then S else S （3） | while E do S （4） | begin L end （5） | SA （6）LL；S （7） |S,5.5 控制语句的翻译,S ：语句 L：语句串 SA：赋值语句 E：布尔表达式,例：if E then S1 else S2 E.TC只有在扫描到then之后才能确定； E.FC只有在处理了S1之后，到达else时才能明确。 因此，E.FC应传递下去，以便到达相应的else回填。,布尔式E的两项语义值E.TC，E.FC，分别指示尚待回填“真”、“假”出口的四元式。,另外，S1语句执行后产生(j,-,-,0)，使控制离开整个if语句。其转移目标应在S2后确定。若if语句有嵌套，则即使翻译完S2，目标位置可能仍无法确定。,1、说 明,由此可知，转移目标的去向和语句所处的环境紧密相关。 解决办法：为非终结符S（和L）加上语义属性chain，S.chain或L.chain指示一条链的链头，该链将所有控制转出内层语句S的各个四元式连接(拉链)，在适当时候进行回填。 对于while语句中的布尔式E，其假出口也将使控制离开整个while语句，同样采用S.chain指示跳出while的链头，待处理while语句的外层语句时回填。,E.code,E.true:,S1.code,.,to E.T,to E. F(S.chain),2、控制语句的翻译,(a) While-do语句结构,1） 结构分析,E.code,S1.code,E.true:,S2.code,E.false:,goto S.chain,.,S.chain:,to E.true,to E.false,(b) if-then-else语句结构,为了在翻译过程中及时进行拉链或回填处理，将文法GS改写为GS：,（1）Cif E then （2) TP CS else （3）S CS （4）S TPS （5）Ls L; （6）LLsS,（7）LS （8）W while （9）Wd WE do （10）SWdS （11）S begin L end （12）S SA,在s1和s2间插入一个跳转四元式,用W.quad记录当前四元组的NXQ,为了跳回循环,反填E的真出口，为下一个四元式。,从；断开，用S的第一个四元式反填。,2）文法改写,（1）Cif E then,（2）SCS1,3）产生式语义子程序描述,backpatch（E.TC，NXQ）； C.chain=E.FC ,/*IF-THEN语句的出口为E.FC*/,S.chain=MERGE(C.chain，S1.chain) ,/*C出口与S1的出口一致，均为S出口，因此合并*/,注意：语义值S.chain将暂时保留在语义栈中，后续归约过程的适当时候，它所指的链会被回填。,/* C为条件子句*/,（3）TP CS1 else,q=NXQ; GEN(J,-,-,0); BACKPATCH(C.chain，NXQ); /*else后第一个四元式*/ TP.chain=MERGE(q，s1.chain) ,/*S1代码执行后，同样出控制，与q的出口以及与TP出口一致*/,/* TP为真部子句*/,（4）S TPS2,（5）WWhile,（6）WdW E do,S.chain=MERGE(TP.chain，s2.chain),/*S2的出口和TP(整个if语句)出口是一致的*/,W.quad=NXQ,/*用W.quad属性记录while语句首位置*/, backpatch(E.TC，NXQ); Wd.chain=E.FC; Wd.quad=W.quad,/*对E.TC回填，E.FC为while出口，Wd.chain与Wd.quad需进一步传递*/,/* Wd为while子句*/,（7）SWd S1,（8）SA,backpatch(S1.chain， Wd.quad); /*S1执行完后出口为while语句*/ GEN(J，-，-，Wd.quad); S.chain=Wd.chain; , S.chain=0 /*赋值语句不发生控制转移，因此S的出口链为空链*/,（9）LS,L.chain=S.chain ,/*按此式归约时，S的四元式已产生，由S.chain指示的四元式链的链头传递给L.chain，以便适当时机回填。*/,（10）LsL；,（11）L Ls S,（12）Sbegin L end,backpatch(L.chain=NXQ),/*L的四元式已产生，并且已扫描到L的语句结束符；执行完L后应将控制转移到分号后的语句。*/,L.chain=S.chain,/*S后控制应转向的目标尚待回填，故将有S.chain所指示的四元式链头传递给L.chain。 */,S.chain=L.chain,例：将While (AB) do If (CD) then X:=Y+Z 翻译成四元式。,按照文法GS，该语句的生成树为：,while,W,E,do,Wd,if,E,then,Y + Z,A B,C,X,:=,E,S,S,S,C D,1、按WWhile归约 W.quad=NXQ,分析语义，产生四元式,2、E id1 rop id2 ETC:=NXQ，EFC:=NXQ+1 GEN（jrop，entry(id1)，entry(id2)，-，0） GEN（j，-，-，0）,3、 WdW E do backpatch(E.TC，NXQ); Wd.chain=E.FC; Wd.quad=W.quad ,分析语义，产生四元式,Wd.c