第五章语法制导翻译.

1第五章语法制导翻译5.4~5.5编译原理25.4语法制导的翻译模式(TranslationScheme)语法制导翻译（SDT）是SDD的实现。语法制导翻译模式（SDT）是拓广的CFG，在文法中嵌入语义动作，语义动作写在花括号“{}”里，可以出现在产生式右部适当位置。当归约出产生式右部的某个非终结符号后，就执行紧接在该非终结符号右边的语义动作。编译原理3任何SDT可以通过先建立语法分析树，然后前序遍历执行语义动作。但是，我们希望SDT能够在语法分析的同时进行，无需构造好分析树。这里讨论两类：1.基础文法是LR，SDD是S-attributed；2.基础文法是LL，SDD是L-attributed。编译原理4SDDvs.SDT语义规则语义动作产生式语义规则EE1+TE.val:=E1.val+T.valEE1+T{E.val:=E1.val+T.val}编译原理5SDDvs.SDT语义规则语义动作产生式语义规则EE1+TE.code:=E1.code||T.code||‘+’EE1+T{print(‘+’);}编译原理65.4.1后缀SDT自底向上分析S属性文法。AXYZ{语义动作}编译原理7LEn{print(E.val);}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:=digit.lexval;}编译原理85.4.2后缀SDT的语法分析实现AXYZXYZX.xY.yZ.ztop文法符号综合属性编译原理9例5.15显式操作语法分析栈LEn{print(stack[top-1].val);top=top-1;}EE1+T{stack[top-2].val=stack[top-2].val+stack[top].val;top=top-2;}ETTT1*F{stack[top-2].val=stack[top-2].valstack[top].val;top=top-2;}TFF(E){stack[top-2].val=stack[top-1].val；top=top-2;}Fdigit编译原理103*5n的分析计算过程digit3top编译原理113*5n的分析计算过程F3top编译原理123*5n的分析计算过程T3*digit5top编译原理133*5n的分析计算过程T3*F5top编译原理143*5n的分析计算过程T15top编译原理153*5n的分析计算过程E15top编译原理163*5n的分析计算过程E15ntop编译原理173*5n的分析计算过程L15top编译原理185.4.3产生式内部带语义动作的SDTBX{a}YLR：归约出X之后立即执行动作{a}LL：试图展开Y之前执行动作{a}编译原理19例，中缀到后缀转换的SDDProductionSemanticRuleexprexpr1+termexpr.t:=expr1.t||term.t||‘+’exprexpr1–termexpr.t:=expr1.t||term.t||’-’exprtermexpr.t:=term.tterm0term.t:=‘0’term1term.t:=‘1’….….term9term.t:=‘9’编译原理20例，中缀到后缀转换的SDTLEnEE1+T{print(‘+’)}ETTT1*F{print(‘*’)}TFF(E)Fdigit{print(digit.lexval)}编译原理21例5.16翻译为前缀表达式LEnE{print(‘+’)}E1+TETT{print(‘*’)}T1*FTFF(E)Fdigit{print(digit.lexval)}NotallSDT’scanbeimplementedduringparsing:NotaLRGrammar?编译原理22嵌入动作的分析树：3*5+4编译原理235.4.4从SDT中删除左递归例5.17带左递归的文法的翻译模式。EE1+T{print(‘+’);}ET转换为：ETRR+{print(‘+’);}RR编译原理24AA1Y{A.a:=g(A1.a,Y.y)}AX{A.a:=f(X.x)}消除左递归后：AX{R.i:=f(X.x)}R{A.a:=R.s}RY{R1.i:=g(R.i,Y.y)}R1{R.s:=R1.s}R{R.s:=R.i}例：一个一般化的例子编译原理25AA1Y{A.a:=g(A1.a,Y.y)}AX{A.a:=f(X.x)}Y1XY2AAA.a=g(g(f(X.x),Y1.y),Y2.y).a=g(f(X.x),Y1.y).a=f(X.x).y.y.x编译原理26AX{R.i:=f(X.x)}R{A.a:=R.s}RY{R1.i:=g(R.i,Y.y)}R1{R.s:=R1.s}R{R.s:=R.i}AXRY1RY2R.i=g(g(f(X.x),Y1.y),Y2.y).i=g(f(X.x),Y1.y).y.i=f(X.x).y.xasss编译原理275.4.5L属性定义的SDT确定语义动作的执行时机如何将语义动作嵌入产生式右部的适当位置？编译原理281.只有综合属性的情况：将计算综合属性的语义规则作为产生式右边末尾的动作。例如：原则：产生式语义规则TT1*FT.val:=T1.val*F.val产生式语义动作TT1*F{T.val:=T1.val*F.val}编译原理292.同时存在综合属性和继承属性，建立翻译模式的必要条件：产生式右部符号的继承属性必须在这个符号以前的动作中计算出来；一个动作不能引用该动作右边符号的综合属性；产生式左边非终结符号的综合属性只有在它所引用的所有属性都计算出来以后才能计算。计算这种属性的动作通常可以放在产生式右端的末尾。编译原理30例：翻译模式SA1A2{A1.in:=1;A2.in:=2}Aa{print(A.in)}不符合条件(1)。若改写成S{A1.in:=1;A2.in:=2}A1A2Aa{print(A.in)}则就符合条件(1)。编译原理31E1.val上图可以用命令：Esub1.val描述。例5.18数学排版语言的翻译模式片断。ai上图可以用命令：asubisubj描述。j编译原理32例5.18数学排版语言的翻译模式。综合属性：ht：描述heightdp：描述depth继承属性ps：pointsize，设定字体大小。Assumeps=10。下标的大小按比例缩小，位置下降。编译原理33产生式语义规则SBBB1B2BB1subB2B(B1)BtextB.ps:=10B1.ps:=B.psB2.ps:=B.psB.ht:=max(B1.ht,B2.ht)B.dp:=max(B1.dp,B2.dp)B1.ps:=B.psB2.ps:=0.7*B.psB.ht:=max(B1.ht,B2.ht–0.25*B.ps)B.dp:=max(B1.dp,B2.dp+0.25*B.ps)B1.ps:=B.psB.ht:=B1.htB.dp:=B1.dpB.ht:=getHt(B.ps,text.lexval)B.dp:=getDp(B.ps,text.lexval)图5-25盒子的大小和高度的语法制导定义编译原理34SBBBBsubBBsub1Esub1E1B1.htmax(B1.ht,B2.ht–0.25*B.ps)Esub1的推导过程(忽略二义性问题)max(B1.dp,B2.dp+0.25*B.ps)非终结符号B(表示Box)代表一个公式。产生式BB1B2代表两个方框的并置。BB1subB2代表一个布局，其中B2是比B1小一号的方框，B2是B1的下标。编译原理35翻译模式编译原理36如何消除二义性?SBBB1B2BB1subB2B(B)|text1.结合性：右结合2.优先级：sub高于并置SBBTB1|TTFsubT1|FF(B)|text编译原理37例5.19Swhile(C)S1C.codeS1.codegotoL1...C.true:C.false:toC.truetoC.falsewhile语句L1:L2:编译原理38产生式语义规则Swhile(C)S1L1=newlabel();L2=newlabel();S1.next=L1;C.false=S.next;C.true=L2;S.code=label||L1||C.code||label||L2||S1.codeSwhile({L1=newlabel();L2=newlabel();C.false=S.next;C.true=L2;}C){S1.next=L1;}S1{S.code=label||L1||C.code||label||L2||S1.code}编译原理395.5实现L属性定义的翻译建立注释语法分析树构造语法分析树，加入动作，按照前序顺序执行使用递归下降的语法分析器，在预测分析的过程中实现L属性定义。编译原理40例5.20编译原理41例5.22编译原理42编译原理435.5.1从翻译模式中消除左递归例5.14带左递归的文法的翻译模式。S-属性定义EE1+T{E.val:=E1.val+T.val}EE1-T{E.val:=E1.val-T.val}ET{E.val:=T.val}T(E){T.val:=E.val}Tnum{T.val:=num.val}编译原理44经过转换的带有右递归文法的翻译模式ET{R.i:=T.val}R{E.val:=R.s}R+T{R1.i:=R.i+T.val}R1{R.s:=R1.s}R{R.s:=R.i}T(E){T.val:=E.val}Tnum{T.val:=num.val}编译原理45表达式9-5+2的计算EvalT.val=9num.val=9i=9Rs-T.val=5num.val=5i=4Rs+T.val=2i=6Rsnum.val=2编译原理46例5.15转换后的构造语法树的翻译模式ET{R.i:=T.nptr}R{E.nptr:=R.s}R+T{R1.i:=mknode(‘+’,R.i,T.nptr)}R1{R.s:=R1.s}R-T{R1.i:=mknode(‘-’,R.i,T.nptr)}R1{R.s:=R1.s}R{R.s:=R.i}T(E){T.nptr:=E.nptr}Tid{T.nptr:=mkleaf(id,id.entry)}Tnum{T.nptr:=mkleaf(num,num.val)}编译原理47+-idtoentryforanum4idtoentryforc图5.29使用继承属性构造a-4+c的语法树idiRsTnptr+iRsnumTnptr-iRsE.nptrTnptrid编译原理485.5.2预测翻译器的设计算法5.1预测语法制导翻译器的构造输入:语法制导翻译模式,其基础文法适于预测分析输出:语法制导翻译器方法:修改预测分析器的结构。1.为每个非终结符号A构造一个函数，A的每个继承属性对应函数的一个参数，A的综合属性对应函数的返回值(假定A只有一个综合属性)，并为出现在A的产生式中的文法符号的每个属性定义一个局部变量；2.A函数的代码根据当前的输入决定使用哪一个产生式；编译原理493.与每个产生式有关的代码如下：1)对于带有综合属性x的单词符号X，把x的值保存在为X.x声明的变量中，产生匹配X的调用，并继续输入；2)对于非终结符号B，产生一个赋值语句c:=B(b1,b2,…,bk),b1,b2,…,bk是代表B的继承属性的变量，c是代表B的综合属性的变量；3)对于每个动作，将其代码拷贝到分析器，把对属