编译原理-陈意云-23963chapter4

第四章语法制导的翻译,本章内容介绍一种形式化的语义描述方法：语法制导的翻译，包括它的两种具体形式：语法制导的定义和翻译方案介绍语法制导翻译的实现方法,4.1语法制导的定义,例简单台式计算器的语法制导定义,4.1语法制导的定义,4.1.1语法制导定义的形式基础文法每个文法符号有一组属性每个文法产生式A有一组形式为b:=f(c1,c2,ck)的语义规则，其中f是函数，b和c1,c2,ck是该产生式文法符号的属性综合属性：如果b是A的属性，c1,c2,ck是产生式右部文法符号的属性或A的其它属性继承属性：如果b是产生式右部某个文法符号X的属性,4.1语法制导的定义,4.1.2综合属性S属性定义：仅仅使用综合属性的语法制导定义,4.1语法制导的定义,8+5*2n的注释分析树,4.1语法制导的定义,分析树各结点属性的计算可以自下而上地完成,4.1语法制导的定义,分析树各结点属性的计算可以自下而上地完成,4.1语法制导的定义,分析树各结点属性的计算可以自下而上地完成,4.1语法制导的定义,分析树各结点属性的计算可以自下而上地完成,4.1语法制导的定义,分析树各结点属性的计算可以自下而上地完成,4.1语法制导的定义,分析树各结点属性的计算可以自下而上地完成,4.1语法制导的定义,分析树各结点属性的计算可以自下而上地完成,4.1语法制导的定义,分析树各结点属性的计算可以自下而上地完成,4.1语法制导的定义,分析树各结点属性的计算可以自下而上地完成,4.1语法制导的定义,分析树各结点属性的计算可以自下而上地完成,4.1语法制导的定义,分析树各结点属性的计算可以自下而上地完成,4.1语法制导的定义,注释分析树:结点的属性值都标注出来的分析树,4.1语法制导的定义,4.1.3继承属性intid,id,id,4.1语法制导的定义,intid1,id2,id3的注释分析树,4.1语法制导的定义,4.1.4属性依赖图intid1,id2,id3的分析树的依赖图DTLL.in:=T.type,4.1语法制导的定义,4.1.4属性依赖图intid1,id2,id3的分析树的依赖图LL1,idL1.in:=L.in;addtype(id.entry,L.in),4.1语法制导的定义,4.1.5属性计算次序拓扑排序：结点的一种排序，使得边只会从该次序中先出现的结点到后出现的结点例：1，2，3，4，5，6，7，8，9，10,4.1语法制导的定义,属性计算次序构造输入的分析树,4.1语法制导的定义,属性计算次序构造输入的分析树，构造属性依赖图,4.1语法制导的定义,属性计算次序构造输入的分析树，构造属性依赖图，对结点进行拓扑排序,4.1语法制导的定义,属性计算次序构造输入的分析树，构造属性依赖图，对结点进行拓扑排序，按拓扑排序的次序计算属性,4.1语法制导的定义,语义规则的计算方法分析树方法：前面介绍的方法,4.1语法制导的定义,语义规则的计算方法分析树方法：前面介绍的方法基于规则的方法：静态确定语义规则的计算次序,4.1语法制导的定义,语义规则的计算方法分析树方法：前面介绍的方法基于规则的方法：静态确定语义规则的计算次序忽略规则的方法：事先确定属性的计算策略（如边分析边计算），那么语义规则的设计必须符合所选分析方法的限制,4.2S属性定义的自下而上计算,4.2.1语法树语法树是分析树的浓缩表示：算符和关键字是作为内部结点语法制导翻译可以基于分析树，也可以基于语法树语法树的例子：,4.2S属性定义的自下而上计算,4.2.2构造语法树的语法制导定义,4.2S属性定义的自下而上计算,a+5*b的语法树的构造,4.2S属性定义的自下而上计算,a+5*b的语法树的构造,4.2S属性定义的自下而上计算,a+5*b的语法树的构造,4.2S属性定义的自下而上计算,a+5*b的语法树的构造,4.2S属性定义的自下而上计算,a+5*b的语法树的构造,4.2S属性定义的自下而上计算,a+5*b的语法树的构造,4.2S属性定义的自下而上计算,a+5*b的语法树的构造,4.2S属性定义的自下而上计算,a+5*b的语法树的构造,4.2S属性定义的自下而上计算,a+5*b的语法树的构造,4.2S属性定义的自下而上计算,4.2.3S属性的自下而上计算将LR分析器增加一个域来保存综合属性值,栈stateval,top,4.2S属性定义的自下而上计算,4.2.3S属性的自下而上计算将LR分析器增加一个域来保存综合属性值,栈stateval,top,若产生式AXYZ的语义规则是A.a:=f(X.x,Y.y,Z.z),4.2S属性定义的自下而上计算,4.2.3S属性的自下而上计算将LR分析器增加一个域来保存综合属性值,栈stateval,top,若产生式AXYZ的语义规则是A.a:=f(X.x,Y.y,Z.z)，那么归约后：,top,4.2S属性定义的自下而上计算,台式计算器的语法制导定义改成栈操作代码,栈stateval,top,4.2S属性定义的自下而上计算,台式计算器的语法制导定义改成栈操作代码,栈stateval,top,4.2S属性定义的自下而上计算,台式计算器的语法制导定义改成栈操作代码,栈stateval,top,4.2S属性定义的自下而上计算,台式计算器的语法制导定义改成栈操作代码,栈stateval,top,4.2S属性定义的自下而上计算,台式计算器的语法制导定义改成栈操作代码,栈stateval,top,4.2S属性定义的自下而上计算,台式计算器的语法制导定义改成栈操作代码,栈stateval,top,4.2S属性定义的自下而上计算,台式计算器的语法制导定义改成栈操作代码,栈stateval,top,4.2S属性定义的自下而上计算,台式计算器的语法制导定义改成栈操作代码,栈stateval,top,4.2S属性定义的自下而上计算,台式计算器的语法制导定义改成栈操作代码,栈stateval,top,4.3L属性定义的自上而下计算,边分析边翻译的方式能否用于继承属性？属性的计算次序一定受分析方法所限定的分析树结点建立次序的限制,4.3L属性定义的自上而下计算,边分析边翻译的方式能否用于继承属性？属性的计算次序一定受分析方法所限定的分析树结点建立次序的限制分析树的结点是自左向右生成,4.3L属性定义的自上而下计算,边分析边翻译的方式能否用于继承属性？属性的计算次序一定受分析方法所限定的分析树结点建立次序的限制分析树的结点是自左向右生成如果属性信息是自左向右流动，那么就有可能在分析的同时完成属性计算,4.3L属性定义的自上而下计算,4.3.1L属性定义如果每个产生式AX1X2Xn的每条语义规则计算的属性是A的综合属性；或者是Xj的继承属性，1jn,但它仅依赖：该产生式中Xj左边符号X1,X2,Xj-1的属性；A的继承属性,4.3L属性定义的自上而下计算,4.3.1L属性定义如果每个产生式AX1X2Xn的每条语义规则计算的属性是A的综合属性；或者是Xj的继承属性，1jn,但它仅依赖：该产生式中Xj左边符号X1,X2,Xj-1的属性；A的继承属性S属性定义属于L属性定义,4.3L属性定义的自上而下计算,变量类型声明的语法制导定义是一个L属性定义,4.3L属性定义的自上而下计算,4.3.2翻译方案例把有加和减的中缀表达式翻译成后缀表达式如果输入是8+52，则输出是85+2,4.3L属性定义的自上而下计算,4.3.2翻译方案例把有加和减的中缀表达式翻译成后缀表达式如果输入是8+52，则输出是85+2ETRT+T+T+RaddopTprint(addop.lexeme)R1|Tnumprint(num.val),4.3L属性定义的自上而下计算,4.3.2翻译方案例把有加和减的中缀表达式翻译成后缀表达式如果输入是8+52，则输出是85+2ETRRaddopTprint(addop.lexeme)R1|Tnumprint(num.val)ETRnumprint(8)Rnumprint(8)addopTprint(+)Rnumprint(8)addopnumprint(5)print(+)Rprint(8)print(5)print(+)addopTprint()Rprint(8)print(5)print(+)print(2)print(),4.3L属性定义的自上而下计算,例数学排版语言EQNEsub1.valSBBB1B2BB1subB2Btext,4.3L属性定义的自上而下计算,例数学排版语言EQNEsub1.val,4.3L属性定义的自上而下计算,例数学排版语言EQNSB.ps:=10BS.ht:=B.htBB1.ps:=B.psB1B2.ps:=B.psB2B.ht:=max(B1.ht,B2.ht)BB1.ps:=B.psB1subB2.ps:=shrink(B.ps)B2B.ht:=disp(B1.ht,B2.ht)BtextB.ht:=text.hB.ps,4.3L属性定义的自上而下计算,例左递归的消除引起继承属性,4.3L属性定义的自上而下计算,ETR.i:=T.nptrRE.nptr:=R.sR+TR1.i:=mknode(+,R.i,T.nptr)R1R.s:=R1.sRR.s:=R.iTFW.i:=F.nptrWT.nptr:=W.sW*FW1.i:=mknode(*,W.i,F.nptr)W1W.s:=W1.sWW.s:=W.i,4.3L属性定义的自上而下计算,ETR.i:=T.nptrT+T+T+RE.nptr:=R.sR+TR1.i:=mknode(+,R.i,T.nptr)R1R.s:=R1.sRR.s:=R.iTFW.i:=F.nptrWT.nptr:=W.sW*FW1.i:=mknode(*,W.i,F.nptr)W1W.s:=W1.sWW.s:=W.i,4.3L属性定义的自上而下计算,略去了ETRT部分,4.3L属性定义的自上而下计算,4.3.3预测翻译器的设计把预测分析器的构造方法推广到翻译方案的实现产生式R+TR|的分析过程procedureR;beginiflookahead=+thenbeginmatch(+);T;Rendelsebegin/*什么也不做*/endend,4.3L属性定义的自上而下计算,functionR(i:syntax_tree_node):syntax_tree_node;varnptr,i1,s1,s:syntax_tree_node;addoplexeme:char;beginiflookahead=+thenbegin/*产生式R+TR*/addoplexeme:=lexval;match(+);nptr:=T;i1:=mknode(addoplexme,i,nptr);s1:=R(i1);s:=s1endelses:=i;/*产生式R*/returnsend;,R:i,sT:nptr+:addoplexeme,4.3L属性定义的自上而下计算,4.3.4用综合属性代替继承属性Pascal的声明，如m,n:integerDL:TTinteger|charLL,id|id,4.3L属性定义的自上而下计算,4.3.4用综合属性代替继承属性Pascal的声明，如m,n:integerDL:TTinteger|charLL,id|id改成从右向左归约DidLL,idL|:TTinteger|char,4.3L属性定义的自上而下计算,4.3.4用综合属性代替继承属性Pascal的声明，如m,n:integerDL:TTinteger|charLL,id|id改成从右向左归约DidLL,idL|:TTinteger|char,4.3L属性定义的自上而下计算,DidLaddtype(id.entry,L.type)L,idL1L.type:=L1.Type;addtype(id.entry,L1.type)L:TL.type:=T.typeTintegerT.type:=integerTrealT.type:=real,4.4L属性的自下而上计算,在自下而上分析的框架中实现L属性定义的方法它能实现任何基于LL(1)文法的L属性定义也能实现许多（但不是所有的）基于LR(1)的L属性定义,4.4L属性的自下而上计算,4.4.1删除翻译方案中嵌入的动作ETRR+Tprint(+)R1|Tprint()R1|Tnumprint(num.val),4.4L属性的自下而上计算,4.4.1删除翻译方案中嵌入的动作ETRR+Tprint(+)R1|Tprint()R1|Tnumprint(num.val)在文法中加入产生的标记非终结符，让每个嵌入动作由不同标记非终结符M代表，并把该动作放在产生式M的右端,4.4L属性的自下而上计算,4.4.1删除翻译方案中嵌入的动作ETRR+Tprint(+)R1|Tprint()R1|Tnumprint(num.val)在文法中加入产生的标记非终结符，让每个嵌入动作由不同标记非终结符M代表，并把该动作放在产生式M的右端ETRR+TMR1|TNR1|Tnumprint(num.val)Mprint(+)Nprint(),4.4L属性的自下而上计算,4.4.2分析栈上的继承属性例intp,q,rDTL.in:=T.typeLTintT.type:=integerTrealT.type:=realLL1.in:=L.inL1,idaddtype(id.entry,L.in)Lidaddtype(id.entry,L.in),4.4L属性的自下而上计算,4.4.2分析栈上的继承属性属性位置能预测例intp,q,rDTL.in:=T.typeLTintT.type:=integerTrealT.type:=realLL1.in:=L.inL1,idaddtype(id.entry,L.in)Lidaddtype(id.entry,L.in),4.4L属性的自下而上计算,4.4L属性的自下而上计算,属性的位置不能预测SaACC.i:=A.sSbABCC.i:=A.sCcC.s:=g(C.i),4.4L属性的自下而上计算,属性的位置不能预测SaACC.i:=A.sSbABCC.i:=A.sCcC.s:=g(C.i)增加标记非终结符SaACC.i:=A.sSbABMCM.i:=A.s;C.i:=M.sCcC.s:=g(C.i)MM.s:=M.i,4.4L属性的自下而上计算,4.4.3模拟继承属性的计算继承属性是某个综合属性的一个函数SaACC.i:=f(A.s)CcC.s:=g(C.i),4.4L属性的自下而上计算,4.4.3模拟继承属性的计算继承属性是某个综合属性的一个函数SaACC.i:=f(A.s)CcC.s:=g(C.i)增加标记非终结符，把f(A.s)的计算移到对标记非终结符归约时进行SaANCN.i:=A.s;C.i:=N.sNN.s:=f(N.i)CcC.s:=g(C.i),4.4L属性的自下而上计算,例数学排版语言EQNSB.ps:=10BS.ht:=B.htBB1.ps:=B.psB1B2.ps:=B.psB2B.ht:=max(B1.ht,B2.ht)BB1.ps:=B.psB1subB2.ps:=shrink(B.ps)B2B.ht:=disp(B1.ht,B2.ht)BtextB.ht:=text.hB.ps,4.4L属性的自下而上计算,4.4L属性的自下而上计算,举例说明,4.4L属性的自下而上计算,4.4L属性的自下而上计算,4.4L属性的自下而上计算,4.4L属性的自下而上计算,4.4L属性的自下而上计算,4.4L属性的自下而上计算,4.4L属性的自下而上计算,4.4L属性的自下而上计算,4.5递归计算,回顾：语法制导定义的实现分析树方法,4.5递归计算,回顾：语法制导定义的实现分析树方法边分析边进行属性计算，只能完成L属性计算（忽略规则的方法）,4.5递归计算,回顾：语法制导定义的实现分析树方法边分析边进行属性计算，只能完成L属性计算（忽略规则的方法）本节介绍先分析后计算的方法，不局限于L属性计算（基于规则的方法）,4.5递归计算,回顾：语法制导定义的实现分析树方法边分析边进行属性计算，只能完成L属性计算（忽略规则的方法）本节介绍先分析后计算的方法，不局限于L属性计算（基于规则的方法）为每个非终结符构造一个属性计算函数，但是该函数不含语法分析部分,4.5递归计算,回顾：语法制导定义的实现分析树方法边分析边进行属性计算，只能完成L属性计算（忽略规则的方法）本节介绍先分析后计算的方法，不局限于L属性计算（基于规则的方法）为每个非终结符构造一个属性计算函数，但是该函数不含语法分析部分为非终结符的不同综合属性构造不同的函数,4.5递归计算,4.5.1自左向右遍历为B构造一个属性计算函数SB.ps:=10BS.ht:=B.htBB1.ps:=B.psB1B2.ps:=B.psB2B.ht:=max(B1.ht,B2.ht)BB1.ps:=B.psB1subB2.ps:=shrink(B.ps)B2B.ht:=disp(B1.ht,B2.ht)BtextB.ht:=text.hB.ps,4.5递归计算,functionB(n,ps);varps1,ps2,ht1,ht2;begincase在结点n的产生式ofBB1B2:ps1:=ps;ht1:=B(child(n,1),ps1);ps2:=ps;ht2:=B(child(n,2),ps2);returnmax(ht1,ht2);,BB1.ps:=B.psB1B2.ps:=B.psB2B.ht:=max(B1.ht,B2.ht),4.5递归计算,functionB(n,ps);varps1,ps2,ht1,ht2;begincase在结点n的产生式ofBB1subB2:ps1:=ps;ht1:=B(child(n,1),ps1);ps2:=shrink(ps);ht2:=B(child(n,3),ps2);returndisp(ht1,ht2);,BB1.ps:=B.psB1subB2.ps:=shrink(B.ps)B2B.ht:=disp(B1.ht,B2.ht),4.5递归计算,functionB(n,ps);varps1,ps2,ht1,ht2;begincase在结点n的产生式ofBtext:returnpstext.h;default:errorend,BtextB.ht:=text.hB.ps,4.5递归计算,4.5.2其它遍历方法按所需次序访问结点的子结点，可用于非L属性定义ALML.i:=l(A.i);M.i:=m(L.s);A.s:=f(M.s)AQRR.i:=r(A.i);Q.i:=q(R.s);A.s:=f(Q.s),4.5递归计算,ALM:/*从左到右的次序*/li:=l(ai);ls:=L(child(n,1),li);mi:=m(ls);ms:=M(child(n,2),mi);returnf(ms);,4.5递归计算,AQR:/*从右到左的次序*/ri:=r(ai);rs:=R(child(n,2),ri);qi:=q(rs);qs:=Q(child(n,1),qi);returnf(qs);,4.5递归计算,4.5.3多次遍历SEE.i:=g(E.s);S.r:=E.tEE1E2E.s:=fs(E1.s,E2.s);E1.i:=fi1(E.i);E2.i:=fi2(E.i);E.t:=ft(E1.t,E2.t)EidE.s:=id.s;E.t:=h(E.i),4.5递归计算,综合属性t不可能和s在同一遍扫描中完成计算,4.5递归计算,functionSr(n);begins:=Es(child(n,1);i:=g(s);t:=Et(child(n,1),i);returntend;,4.5递归计算,functionEs(n);|functionEt(n,i);begin|begincase在结点n的产生式of|case在结点n的产生式ofEE1E2:|EE1E2:s1:=Es(child(n,1);|i1:=fi1(i);s2:=Es(child(n,2);|t1:=Et(child(n,1),i1);returnfs(s1,s2);|i2:=fi2(i);Eid:|t2:=Et(child(n,2),i2);returnid.s;|returnft(t1,t2);default:|Eid:error|returnh(i);end|default:end;|error|end|end;,本章要点,语义规则的两种描述方法：语法制导的定义和翻译方案设计简单问题的语法制导定义和翻译方案，这是本章的重点和难点语义规则的三种计算方法：分析树方法、基于规则的方法和忽略规则的方法S属性的自下而上计算（边分析边计算）L属性的自上而下计算（边分析边计算）L属性的自下而上计算（边分析边计算）递归计算（先分析后计算）,例题1,下面是产生字母表=0,1,2上数字串的一个文法：SDSD|2D0|1写一个语法制导定义，判断它接受的句子是否为回文数SSprint(S.val)SD1S1D2S.val=(D1.val=D2.val)andS1.valS2S.val=trueD0D.val=0D1D.val=1,例题2,为下面文法写一个语法制导的定义，用S的综合属性val给出下面文法中S产生的二进制数的值。例如，输入101.101时，S.val:=5.625。不得修改文法，但属性使用没有限制SL.R|LLLB|BRBR|BB0|1,例题2,SL.RS.val:=L.val+R.valSLS.val:=L.valLL1BL.val:=L1.val2+B.valLBL.val:=B.valRBR1R.val:=R1.val/2+B.val/2RBR.val:=B.val/2B0B.val:=0B1B.val:=1,例题3,给出把中缀表达式翻译成没有冗余括号的中缀表达式的语法制导定义。例如,因为和是左结合,(a(b+c)(d)可以重写成a(b+c)d先把表达式的括号都去掉，然后在必要的地方再加括号去掉表达式中的冗余括号，保留必要的括号,例题3,第一种方法SEprint(E.code)EE1+TifT.op=plusthenE.code:=E1.code|“+”|“(”|T.code|“)