第四章-语法制导的翻译-复习+习题

14.3L属性定义的自上而下计算•L属性定义•翻译方案–消除左递归•预测翻译器的设计•用综合属性代替继承属性24.3L属性定义的自上而下计算•关于算术表达式的左递归文法相应的翻译模式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}E→TRR→+TR1R→-TR1R→T→(E)T→num3E→T{R.i:=T.val}R{E.val:=R.s}R→+T{R1.i:=R.i+T.val}R1{R.s:=R1.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}E→TRR→+TR1R→-TR1R→T→(E)T→numR.i:R前面子表达式的值R.s:分析完R时子表达式的值消除左递归，构造新的翻译模式4ETRnumnum.val=9T.val=9R.i=9-TRnumnum.val=5T.val=5R.i=4+TRnumnum.val=2T.val=2R.i=6R.s=6R.s=6R.s=6E.val=6E→T{R.i:=T.val}R{E.val:=R.s}R→+T{R1.i:=R.i+T.val}R1{R.s:=R1.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}计算表达式9－5＋25构造抽象语法树的属性文法定义转化成翻译模式E→E1+T{E.nptr:=mknode(‘+’,E1.nptr,T.nptr)}E→E1-T{E.nptr:=mknode(‘-’,E1.nptr,T.nptr)}E→T{E.nptr:=T.nptr}6E→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:=R.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)}构造抽象语法树的属性文法定义转化成翻译模式7使用继承属性构造a－4＋c的抽象语法树ETRidToentryforaidT.nptr-Tnumnum4T.nptrR.i-R+TRidToentryforcidT.nptrR.i+R.iR.sR.sR.sE.nptrE→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:=R.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)}8本章使用的两类方法•分析树方法构造分析树属性依赖图确定属性的计算次序•边分析边进行属性计算的方法–S属性的自下而上计算（边分析边计算）。–L属性的自上而下计算（边分析边计算）。–L属性的自下而上计算（边分析边计算）。优点：效率高缺点：结点访问次序受分析方法限制。9•语义规则的两种描述方法：语法制导的定义和翻译方案。•设计简单问题的语法制导定义和翻译方案，这是本章的重点和难点。•S属性的自下而上计算（边分析边计算）。•L属性的自上而下计算（边分析边计算）。•L属性的自下而上计算（边分析边计算）。语法制导翻译要点10例题1•为文法S(L)|aLL,S|S写一个语法制导定义，它输出括号的对数。首先，分析问题（1）需要定义哪些属性值属性num，表示相应符号中括号的对数（2）属性值为哪些符号定义？L,S（3）num属性属于综合属性还是继承属性？综合属性！因为产生式左部符号的num值要依赖于产生式右部每个符号的属性值11例题1•为文法S(L)|aLL,S|S写一个语法制导定义，它输出括号的对数。SSprint(S.num)S(L)S.num:=L.num+1SaS.num:=0LL1,SL.num:=L1.num+S.numLSL.num:=S.num12•为文法S(L)|aLL,S|S写一个语法制导定义，它输出括号的对数。构建翻译方案对应的代码段：SSprint(val[top])S(L)S.num:=L.num+1SaS.num:=0LL1,SL.num:=L1.num+S.numLSL.num:=S.num栈stateval例题1......SS.num......top13•为文法S(L)|aLL,S|S写一个语法制导定义，它输出括号的对数。SSprint(val[top])S(L)val[top-2]:=val[top-1]SaS.num:=0LL1,SL.num:=L1.num+S.numLSL.num:=S.num栈stateval例题1)LL.num(......top14•为文法S(L)|aLL,S|S写一个语法制导定义，它输出括号的对数。SSprint(val[top])S(L)val[top-2]:=val[top-1]Saval[top]:=0LL1,SL.num:=L1.num+S.numLSL.num:=S.num栈stateval例题1a......top15•为文法S(L)|aLL,S|S写一个语法制导定义，它输出括号的对数。SSprint(val[top])S(L)val[top-2]:=val[top-1]Saval[top]:=0LL1,Sval[top-2]:=val[top-2]+val[top]LSL.num:=S.num栈stateval例题1SS.num,L1L1.num......top16•为文法S(L)|aLL,S|S写一个语法制导定义，它输出括号的对数。SSprint(val[top])S(L)val[top-2]:=val[top-1]Saval[top]:=0LL1,Sval[top-2]:=val[top-2]+val[top]LS-例题1SS.num......栈statevaltop17•为文法S(L)|aLL,S|S写一个翻译方案，它输出每个a的嵌套深度。例如，对于(a,(a,a))，输出的结果是122。S{S.depth:=0}SS{L.depth:=S.depth+1}(L)Sa{print(S.depth)}L{L1.depth:=L.depth}L1,{S.depth:=L.depth}SL{S.depth:=L.depth}S外层括号数目例题218•为文法S(L)|aLL,S|S写一个翻译方案，它打印出每个a在句子中是第几个字符。例如，当句子是(a,(a,(a,a),(a)))时，打印的结果是2581014。S{S.in:=0}SS({L.in:=S.in+1}L){S.num:=L.num+2}Sa{S.num:=1;print(S.in+1)}L{L1.in:=L.in}L1,{S.in:=L1.in+L1.num+1}S{L.num:=L1.num+S.num+1}L{S.in:=L.in}S{L.num:=S.num}例题319•4.5给出对表达式求导数的语法制导定义，表达式由+和*作用于变量x和常数组成，如x*(3*x+x*x)，并假定没有任何化简，例如将3*x翻译成3*1+0*x。•经分析可知对每个文法符号需要有两个属性•.exp用来记录原表达式•.s用来记录该表达式求导的结果20•E′→Enprint(E.s)•E→E1+TE.exp=E1.exp+T.expE.s=E1.s+T.s•E→TE.exp=T.expE.s=T.s•T→T1*FT.exp=T1.exp*F.expT.s=(T1.s)*F.exp+T1.exp*F.s•T→FT.exp=F.expT.s=F.s•F→(E)F.exp=(E.exp)F.s=(E.s)•F→numF.exp=num.lexmeF.s=0•F→xF.exp=xF.s=1214.7令综合属性val表示S产生的二进制数的值。SL.L|LLLB|BB0|1(a)试用各有关综合属性决定S.val.如果只有整数部分，很显然，可以定义如下：SLS.val=L.val;LL1BL.val=L1.val*2+B.val;LBL.val=B.val;L.b=2;B0B.val=0;B1B.val=1;22为了求小数部分的值，引入L的综合属性b记录2的L的位数次幂值(2lengthofL)SL1.L2S.val=L1.val+L2.val/L2.b;SLS.val=L.val;LL1BL.val=L1.val*2+B.val;L.b=L.b*2;LBL.val=B.val;L.b=2;B0B.val=0;B1B.val=1;23SvalLv.LbvLvBvLbvBvBv0LbvBv11Bv0124SvalLv.LbvLvBvLbvBvBv0LbvBv11Bv01=1=1=0=2=1=1=0=1=2=5=2=4=8=2+5/8=2.62525(b)试用一个语法制导定义来决定S.val，在这个定义中B仅有综合属性c，给出由B生成的位对于最后的数值的分担额.引入B的继承属性i,综合属性cSL1.L2{L1.i=20;L2.i=2-1;S.val=L1.val+L2.val}SL{L.i=20;S.val=L.val;}LL1B{ifL.i=20thenbeginL1.i=L.i*2;B.i=L.iendelsebeginL1.i=L.i;L.s=L1.s/2;B.i=L1.sendL.val=L1.val+B.c}LB{B.i=L.i;L.s=L.i/2;L.val=B.c}B0{B.c=B.i*0}B1{B.c=B.i*1}26SvalLv.LsvLvBcLsvBcBc0LsvBc11Bc01=2=0*1=0.5=0*0.25=0.125=2.62527SvaliLv.iLsviLviBciLsviBciBc0iLsviBc11iBc0128SvaliLv.iLsviLviBciLsviBciBc0iLsviBc11iBc01=20=2-1=21=20=21=2-1=2-1=2-1=2-2=2-2=2-3=2-3=2-4=2-1=0.5=0.5=2-2*0=0=2-3*1=0.125=0.5=0.5+0.125=0.625=2.625