第五章语法制导翻译和中间代码第4章主要内容回顾.ppt

2020/5/16,第五章：语法制导翻译和中间代码,1,第4章主要内容回顾,自顶向下语法分析思想自顶向下语法分析方法：LL（1）分析方法递归下降分析方法自底向上语法分析思想自底向上语法分析方法：算符优先分析方法LR分析方法,2020/5/16,第五章：语法制导翻译和中间代码,2,第五章语法制导翻译和中间代码生成,语法分析概述属性文法中间代码赋值语句的翻译布尔表达式的翻译控制流语句的翻译,本章主要内容：,2020/5/16,第五章：语法制导翻译和中间代码,3,5.1语义分析概述,语义分析的任务：语义分析的输入是语法分析的输出（分析树），输出是中间代码，但同时它还完成了很多语义处理工作。语义检查：如，类型、运算、维数、越界等。语义处理：如，变量的存储分配、表达式的求值、语句的翻译（中间代码的生成）等。总目标：生成等价的中间代码。语义分析的主流技术：语法制导翻译技术。语法分析的处理方法：对应每一个产生式编制一个语义子程序，当一个产生式获得匹配时，调用相应的语义子程序实现语义检查与翻译。（语法制导翻译）在产生式的右部的适当位置，插入相应的语义动作，按照分析的进程，执行遇到的语义动作。（翻译方案）,2020/5/16,第五章：语法制导翻译和中间代码,4,5.2属性文法,属性：对文法的每一个符号，引进一些属性，这些属性代表与文法符号相关的信息，例如它的类型、值、代码序列、符号表内容等。与这些属性相关的信息，即属性值，可以在语法分析过程中计算和传递。属性加工的过程即语义的处理过程。属性分为综合属性和继承属性。N.t综合属性：从语法分析树的角度来看，如果一个结点的某一属性，其值由子结点的属性值来计算，则称该属性为综合属性。其形式定义为：设AX1X2Xn为一个产生式，则A的综合属性A.s可描述为：A.s=f(c1,c2,ck)，这里c1,c2,ck是X1，X2，Xn的属性。适合自底向上分析（即归约分析）。,2020/5/16,第五章：语法制导翻译和中间代码,5,5.2属性文法,继承属性：在语法树分析中，若一个结点的某个属性值由该结点的兄弟和或父结点的属性的值来计算，则此结点的属性称为继承属性。其形式定义可描述为：设AX1X2Xn为一个产生式，则Xi继承属性B.in可定义为：B.in=f(c1,c2,ck)，这里，c1,c2,ck是A,X1，X2，Xi-1的属性。适合自顶向下的分析。注意：终结符号只有综合属性，他们由词法分析器提供。非终结符号既有综合属性也可有继承属性，文法的开始符号没有继承属性，除非另外加以说明。,2020/5/16,第五章：语法制导翻译和中间代码,6,5.2属性文法,属性文法：属性文法的特点：是一种接近形式化的语义描述方法；长于描述静态语义、短于描述动态语义；每个语法符号有相应的属性符号；每个产生式有相应的计算属性的规则（即语义规则）属性文法举例：例5-1产生式属性（计算）规则/语义规则EE1+E2E.val:=E1.val+E2.valEE1*E2E.val:=E1.val*E2.valE(E1)E.val:=E1.valEidE.val:=id.val,2020/5/16,第五章：语法制导翻译和中间代码,7,5.2属性文法,属性文法的定义：一个属性文法包含着一个上下文无关文法和一系列语义规则，这些语义规则附在文法的每一个产生式上，在语法分析过程中，完成附加在所使用的产生式上的语义规则描述的动作，从而实现语义处理。属性文法的形式定义为：三元组（，），其中，是上下文无关文法，是属性的有穷集，是关于属性的计算规则。属性文法的用法：根据文法符号的语义，为文法符号设置属性（终结符使用单词的属性）为每个产生式设置语义规则描述各属性的关系计算规则两种形式：语法制导定义和翻译模式。,2020/5/16,第五章：语法制导翻译和中间代码,8,5.2属性文法,语法制导定义：语法制导定义的概念：构造属性文法时，不指明翻译时语义规则的计算顺序，这样的属性文法称为语法制导定义。其形式如P210。S-属性定义：唯独只使用综合属性的语法制导定义称为S-属性定义。S-属性定义中属性的计算：在S-属性定义的分析树中，通常可以使用自底向上的方法在每一个归约处使用语义规则来计算结点的综合属性值，即从叶结点到根结点进行计算。举例：例5-2，简单算术表达式求值的属性文法以及简单算术表达式3*5+4的语义分析过程如下。,2020/5/16,第五章：语法制导翻译和中间代码,9,5.2属性文法,例5-2简单算术表达式求值的语法制导定义（属性文法）：LEprint(E.val)（虚属性）EE1+TE.val:=E1.val+T.valETE.val:=T.valTT1*FT.val:=T1.val*F.valTFT.val:=F.valF(E)F.val:=E.valFdigitF.val:=digit.lexvallexval是单词digit的属性,3*5+4的语义分析过程：,2020/5/16,第五章：语法制导翻译和中间代码,10,5.2属性文法,L-属性定义：包含综合属性和继承属性的语法制导定义称为L-属性定义。P230给出了L-属性的形式定义。P230的表5.6给出了非L-属性的语法制导定义。L-属性定义中属性的计算：其属性可用深度优先的顺序从左至右计算。即对于所有12n，i属性计算仅使用1、2、i-1的属性和的继承属性。举例：例5-3，类型说明语句的语法制导定义（属性文法）以及说明语句realid1,id2,id3的语义分析过程如下：,2020/5/16,第五章：语法制导翻译和中间代码,11,5.2属性文法,例5-3，类型说明语句的语法制导定义（属性文法）：DTLL.in:=T.typeTintT.type:=integerTrealT.type:=realLL1,idL1.in:=L.inaddtype(id.entry,L.in)Lidaddtype(id.entry,L.in)entry：单词id的属性addtype：在符号表中为变量填加类型信息,注意：要解决的问题：记录标识符的类型以及类型信息传递方法：将类型信息作为类型描述T的属性type和变量表L的属性in。目的：分析说明语句D，为变量指定类型。,2020/5/16,第五章：语法制导翻译和中间代码,12,5.2属性文法,说明语句realid1,id2,id3的语义分析过程：,addtype,addtype,addtype,2020/5/16,第五章：语法制导翻译和中间代码,13,5.2属性文法,语法制导翻译的实现：语法制导翻译：在语法分析过程中，随着分析的步步进展，根据每个产生式所对应的语义子程序（或语义规则描述的语义动作）进行翻译的办法称为语法制导翻译。语法制导翻译的具体实现：假定有一个LR分析器，现在把它的分析栈扩充，使得每个文法符号都跟有语义值，即把栈的结构看成如下所示：状态栈语义栈符号栈Smy.valySm-1x.valx:S0#,5.2属性文法,例5-4，对表达式2+3*5#的语义处理过程：,分析表：,r4,r2,S6,3,S5,r6,3,r4,S7,S5,10,r6,r3,9,S5,r6,0)1)+2)3)*4)5)()6)id,2,1,9,r1,1,acc,2020/5/16,第五章：语法制导翻译和中间代码,15,5.2属性文法,翻译模式（翻译方案）：翻译模式：如果在构造属性文法时把语义规则用括起来，插入到规则右部的合适位置上指明语义规则的计算次序，则称这种属性文法的书写形式为翻译模式（或翻译方案）。这是一种动作与分析交错的表示方法，以表达动作在分析过程中的执行时刻。其特征是保证当动作使用某属性时，该属性必须是可用的。S-属性定义的翻译方案：由于S-属性定义中只含有综合属性，所以在构造其翻译方案时只需将每个语义规则写成由赋值语句组成的语义动作，并把该语义动作放在相应规则右部之末端，便得到其翻译方案。,2020/5/16,第五章：语法制导翻译和中间代码,16,5.2属性文法,L-属性定义的翻译方案：由于L-属性定义中既有文法符号的综合属性，又有文法符号的继承属性，那么进行翻译方案设计时，要满足下列三个要求：规则右部符号的继承属性必须在先于这个符号的语义动作中计算；一个语义动作不能引用该语义动作右边符号的综合属性；规则左部非终结符号的综合属性只能在它所引用的所有属性都计算完后再计算。计算该属性的语义动作通常放在规则右部的末端。举例：例5-5，建立说明语句的翻译方案。,2020/5/16,第五章：语法制导翻译和中间代码,17,5.2属性文法,说明语句的翻译模式：（将语义动作中继承属性的计算前移，使它出现在其相应文法符号之前）DTL.in:=T.typeLTintT.type:=integerTrealT.type:=realLL1.in:=L.inL1,idaddtype(id.entry,L.in)Lidaddtype(id.entry,L.in),说明语句的语法制导定义：DTLL.in:=T.typeTintT.type:=integerTrealT.type:=realLL1,idL1.in:=L.inaddtype(id.entry,L.in)Lidaddtype(id.entry,L.in),2020/5/16,第五章：语法制导翻译和中间代码,18,5.2属性文法,说明语句realid1,id2的处理过程：DTL.in:=T.typeLrealT.type:=realL.in:=T.typeLrealL.in=realLrealL.in=realL1.in:=L.inL1,id2addtype(id2.entry,L.in)realL1.in=realL1,id2addtype(id2.entry,real)realL1.in=realid1addtype(id1.entry,L1.in),id2addtype(id.entry,real)realid1(id1.entry,real),id2(id.entry,real),DTL.in:=T.typeLTintT.type:=integerTrealT.type:=realLL1.in:=L.inL1,idaddtype(id.entry,L.in)Lidaddtype(id.entry,L.in),2020/5/16,第五章：语法制导翻译和中间代码,19,5.3中间代码的形式,中间表示：是语法分析以后到目标代码生成之间的源程序表现形式；中间表示的生成可以按语法制导定义来完成；中间表示是语法分析和语义分析相结合的产物。中间表示形式：编译程序所使用的中间代码有多种形式，常见的有逆波兰式、三元式、四元式和树形表示。在这里，以a:=b*e+b*d为例。逆波兰式：也称后缀式，是将运算对象写在前面，运算符号写在后面的中间代码表示形式。如abe*bd*+:=三元式：把表达式及各种语句表示成一组三元式。每个三元式三个组成部分为：算符op、第一运算对象ARG1、第二运算对象ARG2。与后缀式不同，三元式中含有对中间计算结果的显式引用。对于一目算符op只需使用ARG1，此时ARG2为空；对于多目算符，则可用若干相继的三元式表示。,2020/5/16,第五章：语法制导翻译和中间代码,20,5.3中间代码的形式,如（1）(*，b，c)（2）(*，b，d)（3）(+，（1），（2）（4）(:=，（3），a)树形表示：是三元式的另一种表示。简单变量或常数的树就是该变量或常数自身，如果表达式e1和e2的树分别为T1和T2，那么，e1+e2、e1*e2、-e1的树分别为；,2020/5/16,第五章：语法制导翻译和中间代码,21,5.3中间代码的形式,四元式：比较普遍采用的中间代码形式。四个组成成分为算符op、第一和第二运算对象及运算结果。如：（1）(*，b，c，t1)（2）(*，b，d,t2)（3）(+，t1，t2,t3）（4）(:=，t3，-,a),为了更直观，通常写成赋值形式,t1:=b*ct2:=b*dt3:=t1+t2a:=t3,一般形式x:=yopz其中x,y,z为变量名、常数或编译产生的临时变量,对应的四元式（op,y,z,x）,2020/5/16,第五章：语法制导翻译和中间代码,22,5.3中间代码的形式,三元式种类：x:=yopz双目运算（P328）x:=opy单目运算x:=y复制语句ifxrelopygotol条件转移语句gotol无条件转移paramx实在参数callp,n过程调用returnx过程返回x:=yi数组运算xi:=yx:=ifpnilthenemit(p:=E.place)elseerrorEE1+E2E.place:=newtemp;emit(E.place:=E1.place+E2.place)EE1*E2E.place:=newtemp;emit(E.place:=E1.place*E2.place)E-E1E.place:=newtemp;emit(E.place:=0-E1.place)E(E1)E.place:=E1.placeEidp:=lookup();ifpnilthenE.place:=pelseerrorEnumE.place:=num.val,2020/5/16,第五章：语法制导翻译和中间代码,29,5.4赋值语句的翻译,举例：例5-7，参照上面给定的赋值语句的翻译模式，采用自底向上的分析方法将a:=-c+b*34翻译成中间代码。其分析树为：,自底向上的翻译过程：,id.p=a,id.p=c,E.p=c,E.p=t1,t1:=-c,id.p=b,E.p=b,num.v=34,E.p=34,E.p=t2,t2:=b*34,E.p=t3,t3:=t1+t2,a:=t3,2020/5/16,第五章：语法制导翻译和中间代码,30,5.5布尔表达式的翻译,布尔表达式：是用布尔运算符号and、or、not作用到布尔变量或关系表达式上而组成。对于运算符号and、or满足左结合，优先级从高到低的顺序为：notandor。布尔表达式的数值表示时的翻译：将布尔表达式的值数字化，即用1表示真（true)，用0表示假（false).此时布尔表达式从左到右按算术表达式的求值方法来计算。这样其翻译方法也类似于算术表达式的翻译，如：aorbandnotc可翻译为：t1:=notct2:=bandt1t3:=aort2,2020/5/16,第五章：语法制导翻译和中间代码,31,5.5布尔表达式的翻译,而形如ab的关系式可等价为ifabthen1else0,其对应的三地址代码序列为：（假设代码从100开始存放）100ifabgoto103101t1=:=0102goto104103t1:=1104据此，将算术表达式进行扩展，并加进产生式Eid1relopid2最终形成了P351图7.11的关于布尔表达式的数值表示法的翻译模式。,举例：例5-8，参照P351图7.11给出的关于布尔表达式的数值表示法的翻译模式，采用自底向上的分析方法将aborcdandef翻译成中间代码。其分析树为：,2020/5/16,第五章：语法制导翻译和中间代码,32,5.5布尔表达式的翻译,自底向上的翻译过程：(假设中间代码从100开始）,E.p=t1,E.p=t2,104ifcdgoto107105t2:=0106goto108107t2:=1108,E.p=t3,108ifefgoto111109t3:=0110goto112111t3:=1112,E.p=t4,112t4:=t2andt3113,E.p=t5,113t5:=t1ort4114,2020/5/16,第五章：语法制导翻译和中间代码,33,5.5布尔表达式的翻译,控制流语句中布尔表达式的翻译：在这种方法中，用程序中控制转移到达的位置来表示布尔表达式的值。如在ifE1orE2thenS1elseS2中，如果E1或E2为真，则整个表达式为真，即可用S1所在的位置来表示整个布尔表达式的真（记为E.truelist=merge(E1.truelist,E2.truelist）；若E1为假，则还需计算E2，只有E2也为假，整个布尔表达式的值才为假。（即E.falselist=E2.falselist）。另外，这里由于E1orE2中若E1为假则要计算E2，所以要转到E2的开始处，即E2表达式所在的标号处。故在E2前加进M，使它引进一个语义动作，以便在适当的时刻获得四元式的标号（在这里就是E2所对应的四元式的标号）。同理在E1andE2的E2前也做同样的处理，这就形成了P361的图7.14控制流语句中的布尔表达式的翻译模式。,2020/5/16,第五章：语法制导翻译和中间代码,34,5.5布尔表达式的翻译,举例：例5-9，用此翻译模式对例5-8中的布尔表达式进行自底向上的翻译过程如下：(假设中间代码从100开始）,E.t=100E.f=101,99100ifabgoto101goto102,M.q=102,E.t=102E.f=103,102ifcdgoto103goto104,M.q=104,E.t=104E.f=105,104ifefgoto105goto106,104,E.t=104E.f=103,105,102,E.t=100,104E.f=103,105,如果用L1和L2分别表示整个表达式E的真、假出口，则如下：,L1,L1,L2,L2,2020/5/16,第五章：语法制导翻译和中间代码,35,5.5布尔表达式的翻译,上例也可这样分析：aborMcdandMef,99100ifabgoto101goto102,104,M.q=102,102ifccandnot(ac)（注：假设标号从100开始，L1、L2分别为布尔表达式的真、假出口。,99100ifabgotoL1101goto102102ifbcgoto104103gotoL2104ifacgotoL2105gotoL1,E.t=100E.f=101,99100ifabgoto101goto102,M.q=102,E.t=102E.f=103,102ifbcgoto103goto104,M.q=104,104,E.t=105E.f=103,104,102,E.t=100,105E.f=103,104,L1,L2,E.t=104E.f=105,104ifacgoto105goto106,E.t=104E.f=105,E.t=105E.f=104,L1,L2,2020/5/16,第五章：语法制导翻译和中间代码,37,5.6控制流语句的翻译,高级语言的控制结构顺序begin语句;语句；end条件if_then_elseif_thenswitchcase循环while_dodo_whileforrepeat_utilSifCthenS1elseS2的翻译：代码序列：C、S1、S2属性关系：S1.begin=C.trueS2.begin=C.falseS1.next=S2.next=S.next,2020/5/16,第五章：语法制导翻译和中间代码,38,5.6控制流语句的翻译,SwhileCdoS1的翻译：属性设置（继承）布尔式C：代码段真出口true代码段假出口false语句S：代码段的入口begin后续段入口next根据以上思想，形成了P365的控制流语句的翻译模式。,2020/5/16,第五章：语法制导翻译和中间代码,39,5.6控制流语句的翻译,举例，例5-10，按照P365给出的关于控制流语句的翻译模式，将下面给出的控制流语句翻译成中间代码:,ifaborcdandefthenA1elseA2;whileabdoA3,2020/5/16,第五章：语法制导翻译和中间代码,40,5.6控制流语句的翻译,ifaborcdandefthenA1elseA2;whileafdoa:=a+1elsea:+a+2,2020/5/16,第五章：语法制导翻译和中间代码,42,5.6控制流语句的翻译,控制流语句的自顶向下的翻译：将P356的表7.5和P354的表7.4修改成翻译模式，即将语义规则中的文法符号的继承属性用括起来并放在产生式中的此文法符号的左部。如：EE1.true:=E.true,E1.false:=newlabel;E1orE2.true:=E.true,E2.false:=E.false;E2E.code:=E1.code|gen(E1.false:)|E2.code其它也类似。举例，例5-11，利用以上修改后的翻译模式，将例5-8中给出的布尔表达式翻译成四元式代码。,2020/5/16,第五章：语法制导翻译和中间代码,43,5.6控制流语句的翻译,其带语义动作的分析树为：,2020/5/16,第五章：语法制导翻译和中间代码,44,5.6控制流语句的翻译,其分析结果为：（假定整个表达式的真假出口分别为Ltrue和Lfalse,在翻译时已由外