第八章语法制导翻译和中间代码生成.ppt

第8章,语法制导翻译和中间代码生成,语义分析(semanticanalysis),编译程序的语义处理工作：静态语义分析静态语义是对程序约束的描述。可分为类型规则和作用域/可见性规则两大类。审查每个语法结构的静态语义，即验证语法结构合法的程序是否真正有意义。动态语义程序单位描述的计算，执行翻译、生成目标代码。,翻译模式(Translationschemes),两种翻译模式：生成中间代码形式、直接生成目标代码。中间代码(intermediatecode)中间语言：是介于源程序语言和机器语言之间的一种表示形式。Thesemanticrulesgovernwhattypesareallowableinthevariouslanguageconstructs.,语义分析,(1)类型检查。验证程序中执行的每个操作是否遵守语言的类型系统的过程.(2)控制流检查。控制流语句必须使控制转移到合法的地方(3)一致性检查。在很多场合要求对象只能被定义一次。(4)相关名字检查。(5)名字的作用域分析,semanticanalysis,Theparsedprogramisfurtheranalyzedtodeterminewhetheritconformstothesourcelanguagescontextualconstraints:scoperules,typerulese.g.Torelateeachappliedoccurrenceofanidentifierinthesourceprogramtothecorrespondingdeclaration.,语义学,语义形式化、语义建模文法模型属性文法命令式或操作式模型操作语义学公理式模型公理语义学应用式模型指称语义学目前在实际应用中比较流行的语义描述和语义处理的方法主要是属性文法和语法制导翻译,8.1属性文法(attributegrammar),一个属性文法包括一个上下文无关文法和一系列语义规则，这些语义规则附在文法的每个产生式上。语法制导翻译是指在语法分析过程中，完成附加在所使用的产生式上的语义规则描述的动作。,属性文法,一个属性文法是一个三元组A=(G,V,F)G上下文无关文法V属性的有穷集F关于属性的断言或谓词(语义规则)的有穷集。每个属性和非终结符或终结符相联每个断言与文法的某产生式相联，只引用该产生式相联的属性。,属性文法,这些属性代表与文法符号相关信息，如它的类型、值、代码序列、符号表内容等等。属性与变量一样，可以进行计算和传递。属性加工的过程即是语义处理的过程。属性的计算规则称为语义规则,属性文法,表达式文法：ET1+T2|T1orT2Tnum|true|falseET1+T2T1.t=intANDT2.t=intET1orT2T1.t=boolANDT2.t=boolTnumT.t:=intTtureT.t:=boolTfalseT.t:=bool,属性文法,使用N.t的形式表示与非终结符N相连的属性t。T.t的值为int或bool。与非终结符E的产生式相连的断言表明：两个T的属性必须相同。,继承的和综合的属性,属性通常分为两类：综合属性和继承属性综合属性用于“自下而上”传递信息，继承属性用于“自上而下”传递信息。非终结符既可有综合属性也可有继承属性，但文法开始符号没有继承属性。终结符只有综合属性。,继承的和综合的属性,属性文法中，对应每一个产生式A都有一套与之相关联的语义规则，每条规则的形式为：b:=f(c1,c2,ck)其中：f是一个函数，b和c1,c2,ck是该产生式文法符号的属性。如果b是A的一个属性，c1,c2,ck是产生式右部文法符号的属性或A的其它属性，则称b是A的综合属性。,继承的和综合的属性,(2)如果b是产生式右部某个文法符号X的一个属性，并且c1,c2,ck是A或产生式右部任何文法符号的属性，则称b是X的继承属性。在两种情况下，都称属性b依赖于属性c1,c2,ck,属性文法的例,产生式语义规则LEPrint(E.val)EE1+TE.val:=E1.val+T.valETE.val:=T.valTT1*FT.val:=T1.valF.valTFT.val:=F.valF(E)F.val:=E.valFdigitF.val:=digit.lexval,非终结符E、T及F都有一个综合属性val符号digit有一个综合属性，它的值由词法分析器提供。与产生式LE对应的语义规则仅仅是打印由E产生的算术表达式的值的一个过程，我们可认为这条规则定义了L的一个虚属性。某些非终结符加下标是为了区分一个产生式中同一非终结符多次出现,属性文法的例,属性文法的例,.,设表达式为35+4，则语义动作打印数值19,继承属性,例8.2描述说明语句中各种变量的类型信息的语义规则，L.in是继承属性。,一个结点的继承属性值是由此结点的父结点和/或兄弟结点的某些属性来决定的。,继承属性,8.2语法制导翻译概论,一个翻译是符号串对的一个集合。在一个编译程序定义的翻译中，符号串对是源程序和目标程序。各个编译阶段定义一个翻译词法分析：(字符串，单词串)语法分析：(单词串，语法树)代码生成：(语法树，汇编语言),翻译模式,翻译模式（Translationschemes）适合语法制导翻译的另一种描述形式。翻译模式给出了使用语义规则进行计算的次序，可把某些实现细节表示出来。在翻译模式中，和文法符号相关的属性和语义规则（这里我们也称语义动作），用花括号括起来，插入到产生式右部的合适位置上。,语法制导翻译,直观地说，一个语法制导翻译的基础是一个文法，其中翻译成分依附在每一产生式上。根据每个产生式所对应的语义子程序(或语义规则描述的语义动作)进行翻译,语法制导翻译实现,从概念上讲，语法制导翻译基于属性文法的处理过程，通常是这样的：输入符号串分析树属性依赖图语义规则的计算顺序,8.2.1计算语义规则,依赖图一个有向图，用于描述分析树中的属性和属性间的相互依赖关系。属性计算有树遍历和一遍扫描两种方法树遍历设已建立语法树，且树中带有开始符号的继承属性和终结符的综合属性，以某种次序遍历语法树，直到计算出所有属性。一遍扫描在语法分析的同时计算属性值,依赖图的构造算法,For分析树中的每一个结点ndoFor结点的文法符号的每一个属性ado为a在依赖图中建立一个结点；For分析树中的每一个结点ndoFor结点n所用产生式对应的每一个语义规则b:=f(c1,c2,ck)doFori:=1do从ci结点到b结点构造一条有向边,8.2.2S-属性文法和自下而上翻译,L-属性文法的一个特例：S-属性文法S-属性文法：只含有综合属性的属性文法综合属性可以在分析输入符号串的同时自下而上的计算语法制导方式计算表达式2+3*5,2+3*5的分析和计值过程,步骤动作状态栈语义栈(值栈)符号栈余留输入串1)0-#2+3*5#2)05-#2+3*5#3)r603-2#F+3*5#4)r402-2#T+3*5#5)r201-2#E+3*5#6)016-2-#E+3*5#7)0165-2-#E+3*5#,步骤动作状态栈语义栈(值栈)符号栈余留输入串8)r60163-2-3#E+F*5#9)r40169-2-3#E+T*5#10)01697-2-3-#E+T*5#11)016975-2-3-#E+T*5#12)r601697(10)-2-3-5#E+T*F#13)r30169-2-(15)#E+T#14)r101-(17)#E#15)接受,2+3*5的分析和计值过程,8.2.3L-属性文法在自上而下分析中的实现,一个属性文法称为L-属性文法，如果对于每个产生式AX1X2Xn，其每个语义规则中的每个属性或者是综合属性，或者是Xj(1jn)的一个继承属性且仅依赖于：(1)在Xj左边的符号X1,X2,Xj-1的属性；(2)A的继承属性L-属性文法允许一次遍历就计算出所有属性值,8.2.4L-属性文法在自下而上分析中的实现,实现方法：从翻译模式中去掉嵌入在产生式在中间的动作或者用综合属性代替继承属性,8.3中间代码的形式,中间代码(Intermediatecode)源程序的一种内部表示不依赖目标机的结构；易于机械生成目标代码；逻辑结构清楚；利于不同目标机上实现同一种语言；利于进行与机器无关的优化。中间代码的几种形式：逆波兰、四元式、三元式、间接三元式、树,中间代码生成(intermediatecodegeneration),-Thisiswheretheintermediaterepresentationofthesourceprogramiscreated.Wewantthisrepresentationtobeeasytogenerate,andeasytotranslateintothetargetprogram.Therepresentationcanhaveavarietyofforms,butacommononeiscalledthree-addresscodeor4-tuplecode.,8.3.1逆波兰记号,逆波兰表示对表达式的后缀表示,逆波兰记号,例如：-B+C*D的逆波兰式为BCD*+，采用堆栈方式，扫描表达式。计值过程为：B进栈对B进行单目运算，栈顶置换为-BC进栈D进栈栈顶两元素C、D相乘并退栈，结果进栈栈顶两元素相加，退栈，结果进栈,例8.5把下述产生式定义的算术表达式映射到后缀(逆波兰)表示：,逆波兰记号,逆波兰记号,例：A+B*(C-D)+E/(C-D)N逆波兰式：ABCD-*+ECDN/+例：ifEthenS1elseS2作为三目运算符处理，用￥表示：ES1S2￥,8.3.2三元式和树形表示,三元式：(op,ARG1,ARG2)其中：op运算符ARG1第一运算对象ARG2第二运算对象例:a:=b*c+b*d三元式：(1)(*，b，c)(2)(*，b，d)(3)(+，(1)，(2)(4)(:=，(3)，a),树形表示,例:a:=b*c+b*d二目运算对应二叉树，,三元式和树形表示,例:A+B*(C-D)+E/(C-D)N三元式:(1)(-CD)(2)(*B(1)(3)(+A(2)(4)(-CD)(5)(4)N)(6)(/E(5)(7)(+(3)(6),间接三元式间接码表(1)(-CD)(1)(2)(*B(1)(2)(3)(+A(2)(3)(4)(1)N)(1)(5)(/E(4)(4)(+(3)(5)(3)(5),三元式和树形表示,8.3.3四元式,四元式形式：(op,ARG1,ARG2,RESULT)其中：op运算符ARG1第一运算对象ARG2第二运算对象RESULT运算结果RESULT:=ARG1opARG2运算对象及运算结果是程序中定义的变量，必要时可使用编译程序引进的临时变量。,四元式,例:A+B*(C-D)+E/(C-D)N四元式:(1)(-CDT1)(2)(*BT1T2)(3)(+AT2T3)(4)(-CDT4)(5)(T4NT5)(6)(/ET5T6)(7)(+T3T6T7),四元式写成简单赋值形式,t1:=b*ct2:=b*dt3:=t1+t2a:=t3其它语句直接写成：(jump,-,-,L)gotoL(jrop,B,C,L)ifBropCgotoL,8.4简单赋值语句的翻译,在四元式中，用ti表示中间或最后结果，实际实现时，ti或者是指向符号表项的指针，或者是一个临时变量的整数码。属性,E.place，作为语义变量E.place表示存放E值的变量名在符号表中的登录项，或临时变量的整数码。,简单赋值语句的翻译,语义函数lookup()，审查是否出现在符号表中，返回指针值或nil。语义过程emit(t:=arg1oparg2)表示输出四元式到输出文件。语义过程newtemp表示每调用一次，生成一新的临时变量。对变量先定义后检查。,(1)Sid:=Ep:=lookup()ifpnilthenemit(p:=E.place)elseerror(2)EE1+E2E.place:=newtemp;emit(E.place:=E1.place+E2.place)(3)EE1*E2E.place:=newtemp;emit(E.place:=E1.place*E2.place),产生式和语义动作描述,(4)E-E1E.place:=newtemp;emit(E.place:=uminusE1.place)(5)E(E1)E.place:=E1.place(6)EidE.place:=newtemp;P:=lookup();ifPnilthenE.place:=Pelseerror,产生式和语义动作描述,类型转换的语义处理,在编译过程中应对表达式中的运算对象进行语义检查。对不同类型的运算对象进行混合运算，有两种处理方式：指出错误或类型转换。语义变量E.type表示E的类型信息，假定E.type的值为int或real整型+整型*实型+实型*+i*i+r*r一目运算符itr将整型转换成实型,产生式(3)的语义动作描述,EE1*E2E.place:=newtemp;ifE1.type=intANDE2.type=intthenbeginemit(E.place:=E1.place*E2.place);E.type:=intendelse,产生式(3)的语义动作描述,ifE1.type=realANDE2.type=realthenbeginemit(E.place,:=,E1.place*E2.place);E.type:=realendelse,产生式(3)的语义动作描述,ifE1.type=int/*andE2.type=real*/thenbegint:=newtemp;emit(t,:=,itr,E1.place);emit(E.place,:=,t,*r,E2.place);E.type:=realendelse/*E1.type=realandE2.type=int*/,产生式(3)的语义动作描述,begint:=newtemp;emit(t,:=,itr,E2.place);emit(E.place,:=,E1.place,*r,t);E.type:=realend,8.5布尔表达式的翻译,布尔表达式的作用：计算逻辑值、用做控制流语句中的条件表达式布尔表达式的形式：E1ropE2即：按如下文法生成的布尔表达式：EEandE|EorE|notE|idandid|true|false,8.5.1布尔表达式的翻译方法,控制语句的翻译结构的翻译方法1：用1表示true，用0表示false，计算整个表达式的值。方法2：优化方法C语言的方法，某些情况下不需要计算整个表达式的值。,布尔表达式翻译成四元式,布尔表达式：aorbandnotct1:=notct2:=bandt1t3:=aort2,关系式ab等价的条件语句：ifabthen1else0ifabgoto(4)t:=0goto(5)t:=1,用数值表示布尔值的翻译方案,EE1orE2E.place:=newtemp;emit(E.place,:=,E1.placeorE2.place);EE1andE2E.place:=newtemp;emit(E.place,:=,E1.placeandE2.place);EnotE1E.place:=newtemp;emit(E.place,:=notE1.place);E(E1)E.place:=E1.place);,用数值表示布尔值的翻译方案,Eid1ropid2E.place:=newtemp;emit(ifid1.placeropid2.placegotonextstat+3);emit(E.place,:=0);emit(gotonextstat+2);emit(E.place,:=1);其中nextstat给出了在输出序列中下一四元式序号。调用emit过程，每次加1。,用数值表示布尔值的翻译方案,EtrueE.place:=newtemp;emit(E.place,:=1);EfalseE.place:=newtemp;emit(E.place,:=0);,8.5.2控制语句中布尔表达式的翻译,三种控制语句的语法为：SifEthenS1|ifEthenS1elseS2|WhileEdoS1,控制语句的代码结构,把条件转移的布尔表达式E翻译成仅含：条件真转和无条件转的四元式。E：aropbifaropbgotoE.truegotoE.false,控制语句中布尔表达式的翻译,控制语句中布尔表达式的翻译,例：af可翻译成如下四元式：ifafgotoE.truegotoE.false,例：语句ifafthenS1elseS2的四元式序列为ifafgoto(7)转移至(E.true)(6)goto(p+1)转移至(E.false),控制语句中布尔表达式的翻译,(7)S1的四元式(E.true)入口(p)goto(q)(E.false)入口(p+1)(S2的四元式)(q),控制语句中布尔表达式的翻译,控制语句中布尔表达式的翻译,四元式(1)(5)(4)(6)中的转移地址，在整个布尔表达式的四元式产生完毕之后回填。采用“拉链”方式，记录回填地址的四元式。真链：需回填E.true的四元式拉成的链假链：需回填E.false的四元式拉成的链,若有四元式序列(10)gotoE.true(20)gotoE.true(30)gotoE.true把地址(30)称作“真”链链首，0为链尾标志，即地址(10)为“真”链链尾。,控制语句中布尔表达式的翻译,则链成goto(0)goto(10)(30)goto(20),控制语句中布尔表达式的翻译,nextstat指向下一四元式的地址emit输出四元式merge(p1,p2)把p1和p2为链首的两条链合并为一条。返回合并后的链首值。将p2的链尾第四区段改为p1，合并后的链首为p2。backpatch(p,t)把链接的每个四元式的第四区段都填为t。codebegin与非终结符E相连，表示表达式E的第一个四元式语句序号。,自下而上分析中的一种翻译方案,(1)EE1orE2backpatch(E1.false,E2.Codebegin);E.Codebegin:=E1.codebeginE.true:=merge(E1.true,E2.true)E.false:=E2.false(2)EE1andE2backpatch(E1.true,E2.codebegin);E.Codebegin:=E1.codebegin;E.true:=E2.true;E.false:=merge(E1.false,E2.false);(3)EnotEE.true:=E1.false;E.Codebegin:=E1.codebegin;E.false:=E1.true,自下而上分析中的一种翻译方案,(4)E(E1)E.true:=E1.codebeginE.Codebegin:=E1.codebegin;E.false:=E1.false(5)Eid1ropid2E.true:=nextstat;E.Codebegin:=nextstat;E.false:=nextstat+1;emit(ifid1.placeropid2.placegoto);emit(goto),自下而上分析中的一种翻译方案,(6)EtrueE.true:=nextstat;E.codebegin:=nextstat;emit(goto)(7)EfalseE.false:=nextstat;E.codebegin:=nextstat;emit(goto),布尔表达式的翻译,表达式aborcdandef在归约ab到E时，产生2个四元式：100：ifabgoto101：goto,nextstat初值为100E.codebegin为100E.true的值为100E.false的值为101,布尔表达式的翻译,由cd归约到E时产生：102：ifcdgoto103：goto由ef归约到E时产生：104：ifefgoto105：goto,E.codebegin为104E.true的值为102E.false的值为103,布尔表达式的翻译,用EE1andE2归约，完成的语义动作是backpatch(102,104)和merge(103,105)合并E1和E2的假链102：ifcdgoto104105：goto103,布尔表达式的翻译,用EE1orE2归约，完成的语义动作是backpatch(101,102)和merge(100,104)合并E1和E2的真链101：goto102104：ifefgoto100真链首E.true为104假链首E.false为105,布尔表达式的翻译,最后形成：100：ifabgoto101：goto102102：ifcdgoto104103：goto104：ifefgoto100105：goto103一旦真假出口确定，则可沿真假链回填。,8.6控制结构的翻译,控制结构的语句包括：条件控制转移语句：if-then、if-then-else、while-do等开关语句：case、swith(C语言)循环语句：for跳转出口语句：C语言的exit和break无条件转移：goto,8.6.1条件转移,文法GS定义：SifEthenS|ifEthenSelseS|whileEdoS|beginLend|A|LL：S|S,其中：S语句L语句串A赋值语句E布尔表达式,条件转移语句的转移目标,对于语句：ifEthenS1elseS2在扫描到then时确定E的“真”出口，扫描到else时确定E的“假”出口。在完成S1的翻译之后，goto，但在完成S2的翻译之前，无法确定其转移地址。对非终结符S和L，给定语义值S.chain和L.chain，需回填的四元式形成一条链，在转移目标的四元式形成后回填。,条件转移语句的翻译,语句while(AB)doif(CD)thenX:=Y+Z100ifABgoto102101goto107102ifCDgoto104103goto100104T:=Y+Z105X:=T106goto100107,8.6.2开关语句,假定case语句或switch语句形式为：switchEofcaseV1:S1caseV2:S2caseVn-1:Sn-1default:Snend,计算表达式E，测试符合哪一个case，相当于多个条件转移语句。,开关语句的翻译,扫描到switch时，产生标号test、next和临时变量t。计算E的结果代码值，存放到t中。分析到of时则产生四元式gototestLi：Si的中间代码test：ift=VigotoLinext：,Li为与caseVi对应的语句序列Si的标号,开关语句的翻译,将(ift=VigotoLi)改写成(case,Vi,Li,)的四元式形式：(case,V1,L1,)(case,V2,L2,)(case,Vn-1,Ln-1,)(case,t,Ln,)(Lable,next,),8.6.3for循环语句,fori:=E1stepE2untilE3doS1对应的产生式如下：F1fori:=E1F2F1stepE2F3F2untilE3SF3doS1,for循环语句,forI:=1step1untilNdoM:=M+I翻译成如下的四元式序列：I:=1goto103I:=I+1ifI=ngoto105goto108,105T:=M+I106M:=T107goto102108,C语言的for循环语句,for(i=1;i=n;i+)s=s+i;,对应的产生式如下：F1E1F2F1;E2F3F2;E3F4for(F3)SF4S1,四元式序列：100i=1101ifi=ngoto103102goto107103t=s+i104s=t105i=i+1106goto101107,8.6.4出口语句,exit语句和break语句无条件转移到结构的出口终止本层循环、switch语句等。转移的目标在分析break或exit语句所在的循环后面的语句时确定。一遍扫描使用回填技术给出转移目标,出口语句,对每个循环可使用“循环描述符”记录循环的有关信息：指向外层循环的指针、循环的名字、在符号表中的位置、转移的目标等。多层循环是用堆栈方式进行处理的使用currentloop作为指向直接外层循环描述符的指针。,8.6.5goto语句,通过标号和goto语句实现标号L在程序中定义两种情况：gotoL向上转移标号已处理：登记地址向下转移标号未处理：未定义,符号表及未定义标号的引用链,符号表：nametypedefaddLlabelnotr,四元式：(p)goto0(q)gotop(r)gotoq,建链的方法,若gotoL中的标号L尚未在符号表中出现，则把L填入表中，置L的“定义否”标志为“未”，把nextstat填进L的地址栏中作为新链首，然后，产生四元式(goto0)，其中0为链尾标志。若L已在符号表中出现(但“定义否”标志为“未”)，则把它的地址栏中的编号(记为q)取出，把nextstat填进该栏作新链首，然后，产生四元式(gotoq)。,定义标号语句的产生式,SSi：那么，当用i:进行归约时，应做如下的语义动作：1.若i所指的标识符(假定为L)不在符号表中，则把它填入，置“类型”为“标号”，“定义否”为“已”，“地址”为nextstat。,定义标号语句的产生式,2.若L已在符号表中，但“类型”不为“标号”或“定义否”为“已”，则报告出错。3.若L已在符号表中，则把标志“未”改为“已”，然后，把地址栏中的链首(设为q)取出，同时把nextstat填在其中，最后，执行backpatch(q，nextstat)。,goto语句的翻译,翻译goto语句时，还有两点必须注意：第一：相同名字的标号可以在不同名字作用域中定义。如：(1)begin(2)L：begin(3)gotoL；延迟使用(4)(5)L：(6)end(7)end,goto语句的翻译,第二，转移标号是非法的(1)fori:=1to10do(2)begingotoL;(3)forj:=1to20do(4)begingotoL;(n)L:endforjendfori,处理到第(n)行后，第(4)行的goto目标得以解决。而第(2)行的gotoL是非法的，但只有当循环关闭时才能确定。,8.6.6过程调用的四元式产生,过程调用转子程序过程调用包括两项工作参数的处理：传递实在参数地址。如果实在参数是变量或数组元素，直接传地址；如果是表达式，先计算并在临时单元T中保存，然后传T的地址。返回地址,过程调用的四元式产生,例如：过程调用CALLS(A+B,Z)翻译成：T:=A+B计算A+B赋值给TparT第一个实参地址parZ第二个实参地址callS转子指令把实参的地址排列在转子指令的前面统计par的个数记录实在参数个数,描述过程调用语句的语法及语义描述,设定非终结符arglist的一项语义值，称为数据队列QUEUE，在处理实参的过程中记录每个实参的地址。SCalli()FOR队列arglist.每一项pDOGEN(par,-,-,p);GEN(call,-,-,ENTRY(i),描述过程调用语句的语法及语义描述,(2)1,E把E.place排在1.QUEUE的末端；.QUEUE:=1.QUEUE(3)E建立一个.QUEUE，仅包含一项E.place,8.7说明语句的翻译,说明语句定义各种形式的有名字的实体：常量、变量、数组、记录、过程、子程序等。说明语句的种类：对象说明、变量说明、类型说明、过程说明等。说明语句不是可执行语句，不生成目标代码。编译程序把说明语句定义的名字和性质登记在符号表中。,8.7.1简单说明语句的翻译,说明语句的翻译是指在符号表中登录引入的名字及其性质。最简单的说明句的语法：Dinteger|real，id|idinteger和real为关键字，文法可改写为：DD1，id|integerid|realid,产生式所产生的语义动作,Dintegeridenter(id,int);D.ATT:=int(2)Drealidenter(id,real);D.ATT:=real(3)DD1,identer(id，D1.ATT);D.ATT:=D1.ATT给非终结符D一个语义变量D.ATT，记录引入的名字的性质是integer或real。,8.7.2过程中的说明,过程的翻译包括：处理说明和处理调用。过程中说明的局部名字：建立符号表项，记录名字和存储的相对地址。Drealident