【教学课件】第四章语法制导的翻译.ppt

第四章 语法制导的翻译,本章内容1、介绍语义描述的一种形式方法：语法制导的翻译，它包括两种具体形式语法制导的定义翻译方案2、介绍语法制导翻译的实现方法,4.1 语法制导的定义,例简单计算器的语法制导定义,4.1 语法制导的定义,4.1.1 语法制导定义的形式基础文法每个文法符号有一组属性每个文法产生式A 有一组形式为b=f(c1,c2,ck)的语义规则，其中b和c1,c2,ck 是该产生式文法符号的属性，f 是函数综合属性：如果b是A的属性，c1,c2,ck 是产生式右部文法符号的属性或A的其它属性继承属性：如果b是右部某文法符号X的属性,4.1 语法制导的定义,4.1.2 综合属性S属性定义：仅使用综合属性的语法制导定义,4.1 语法制导的定义,注释分析树:结点的属性值都标注出来的分析树8+5*2 n的注释分析树,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 语法制导的定义,继承属性int id,id,id,4.1 语法制导的定义,例int id1,id2,id3的标注了部分属性的分析树不可能像像综合属性那样自下而上标注属性,4.1 语法制导的定义,4.1.4 属性依赖图例int id1,id2,id3的分析树（虚线）的依赖图（实线）D TL L.in=T.type,4.1 语法制导的定义,4.1.4 属性依赖图例int id1,id2,id3的分析树（虚线）的依赖图（实线）L L1,id L1.in=L.in;addType(id.entry,L.in),4.1 语法制导的定义,4.1.4 属性依赖图例int id1,id2,id3的分析树（虚线）的依赖图（实线）L id addType(id.entry,L.in),4.1 语法制导的定义,4.1.5 属性计算次序1、拓扑排序：结点的一种排序，使得边只会从该次序中先出现的结点到后出现的结点例1，2，3，4，5，6，7，8，9，10,4.1 语法制导的定义,4.1.5 属性计算次序2、属性计算次序：构造输入的分析树,4.1 语法制导的定义,4.1.5 属性计算次序2、属性计算次序：构造输入的分析树，构造属性依赖图,4.1 语法制导的定义,4.1.5 属性计算次序2、属性计算次序：构造输入的分析树，构造属性依赖图，对结点进行拓扑排序,4.1 语法制导的定义,4.1.5 属性计算次序2、属性计算次序：构造输入的分析树，构造属性依赖图，对结点进行拓扑排序，按拓扑排序的次序计算属性,4.1 语法制导的定义,语义规则的计算方法分析树方法：刚才介绍的方法，动态确定计算次序，效率低概念上的一般方法基于规则的方法：（编译器实现者）静态确定（编译器设计者提供的）语义规则的计算次序 适用于手工构造的方法忽略规则的方法：（编译器实现者）事先确定属性的计算策略（如边分析边计算）,（编译器设计者提供的）语义规则必须符合所选分析方法的限制 适用于自动生成的方法,4.2 S属性定义的自下而上计算,语法树语法树是分析树的浓缩表示：算符和关键字是作为内部结点语法制导翻译可以基于分析树，也可以基于语法树语法树的例子：if B then S1 else S2 8+5 2,4.2 S属性定义的自下而上计算,构造语法树的语法制导定义,4.2 S属性定义的自下而上计算,a+5b的语法树的构造,4.2 S属性定义的自下而上计算,a+5b的语法树的构造,4.2 S属性定义的自下而上计算,a+5b的语法树的构造,4.2 S属性定义的自下而上计算,a+5b的语法树的构造,4.2 S属性定义的自下而上计算,a+5b的语法树的构造,4.2 S属性定义的自下而上计算,a+5b的语法树的构造,4.2 S属性定义的自下而上计算,a+5b的语法树的构造,4.2 S属性定义的自下而上计算,a+5b的语法树的构造,4.2 S属性定义的自下而上计算,a+5b的语法树的构造,4.2 S属性定义的自下而上计算,4.2.3 S属性的自下而上计算LR分析器的栈增加一个域来保存综合属性值,若产生式A XYZ的语义规则是A.a=f(X.x,Y.y,Z.z)，那么归约后：,top,栈 state val,top,4.2 S属性定义的自下而上计算,简单计算器的语法制导定义改成栈操作代码,栈 state val,top,4.2 S属性定义的自下而上计算,简单计算器的语法制导定义改成栈操作代码,栈 state val,top,4.2 S属性定义的自下而上计算,简单计算器的语法制导定义改成栈操作代码,栈 state val,top,4.2 S属性定义的自下而上计算,简单计算器的语法制导定义改成栈操作代码,栈 state val,top,4.2 S属性定义的自下而上计算,简单计算器的语法制导定义改成栈操作代码,栈 state val,top,4.2 S属性定义的自下而上计算,简单计算器的语法制导定义改成栈操作代码,栈 state val,top,4.2 S属性定义的自下而上计算,简单计算器的语法制导定义改成栈操作代码,栈 state val,top,4.2 S属性定义的自下而上计算,简单计算器的语法制导定义改成栈操作代码,栈 state val,top,4.2 S属性定义的自下而上计算,简单计算器的语法制导定义改成栈操作代码,栈 state val,top,4.3 L属性定义的自上而下计算,边分析边翻译的方式能否用于继承属性？属性的计算次序一定受分析方法所限定的分析树结点建立次序的限制分析树的结点是自左向右生成如果属性信息是自左向右流动，那么就有可能在分析的同时完成属性计算,4.3 L属性定义的自上而下计算,4.3.1 L属性定义如果每个产生式AX1Xj-1XjXn的每条语义规则计算的属性是A的综合属性；或者是Xj 的继承属性，但它仅依赖：该产生式中Xj左边符号X1,X2,Xj-1的属性；A的继承属性S属性定义属于L属性定义,4.3 L属性定义的自上而下计算,变量类型声明的语法制导定义是一个L属性定义,4.3 L属性定义的自上而下计算,4.3.2 翻译方案例把有加和减的中缀表达式翻译成后缀表达式如果输入是8+5 2，则输出是8 5+2 E T RR addop T print(addop.lexeme)R1|T num print(num.val)E T R num print(8)R numprint(8)addop Tprint(+)R numprint(8)addop numprint(5)print(+)R print(8)print(5)print(+)addop Tprint()R print(8)print(5)print(+)print(2)print(),4.3 L属性定义的自上而下计算,例数学排版语言EQN E sub 1.val S B B B1 B2 B B1 sub B2 B text,4.3 L属性定义的自上而下计算,例数学排版语言EQN（语法制导定义）E sub 1.val,4.3 L属性定义的自上而下计算,例数学排版语言EQN（翻译方案）S B.ps=10 B继承属性的计算BS.ht=B.ht 位于B的左边,4.3 L属性定义的自上而下计算,例数学排版语言EQN（翻译方案）S B.ps=10 B综合属性的计算BS.ht=B.ht 放在右部末端,4.3 L属性定义的自上而下计算,例数学排版语言EQN（翻译方案）S B.ps=10 BS.ht=B.ht B B1.ps=B.ps B1B2.ps=B.ps B2B.ht=max(B1.ht,B2.ht)B B1.ps=B.ps B1sub B2.ps=shrink(B.ps)B2B.ht=disp(B1.ht,B2.ht)B textB.ht=text.h B.ps,4.3 L属性定义的自上而下计算,例左递归的消除引起继承属性,4.3 L属性定义的自上而下计算,E T R.i=T.nptr T+T+T+RE.nptr=R.sR+TR1.i=mkNode(+,R.i,T.nptr)R1R.s=R1.sR R.s=R.i T F W.i=F.nptrWT.nptr=W.sW FW1.i=mkNode(,W.i,F.nptr)W1W.s=W1.sW W.s=W.i F 产生式部分不再给出,4.3 L属性定义的自上而下计算,略去了E TR T 部分,4.3 L属性定义的自上而下计算,略去了E TR T 部分,4.3 L属性定义的自上而下计算,略去了E TR T 部分,4.3 L属性定义的自上而下计算,略去了E TR T 部分,4.3 L属性定义的自上而下计算,略去了E TR T 部分,4.3 L属性定义的自上而下计算,略去了E TR T 部分,4.3 L属性定义的自上而下计算,略去了E TR T 部分,4.3 L属性定义的自上而下计算,略去了E TR T 部分,4.3 L属性定义的自上而下计算,4.3.3 预测翻译器的设计把预测分析器的构造方法推广到翻译方案的实现产生式R+TR|的分析过程void R()if(lookahead=+)match(+);T();R();else/什么也不做/,4.3 L属性定义的自上而下计算,syntaxTreeNode R(syntaxTreeNode i)syntaxTreeNode nptr,i1,s1,s;char addoplexeme;if(lookahead=+)/产生式 R+T R/addoplexeme=lexval;match(+);nptr=T();i1=mkNode(addoplexeme,i,nptr);s1=R(i1);s=s1;else s=i;/产生式 R/return s;,R:i,sT:nptr+:addoplexeme,4.3 L属性定义的自上而下计算,4.3.4 用综合属性代替继承属性Pascal的声明，如m,n:integerD L:T（非L属性定义）T integer|charL L,id|id信息从右向左流，归约从左向右，两者不一致,4.3 L属性定义的自上而下计算,4.3.4 用综合属性代替继承属性Pascal的声明，如m,n:integerD L:T（非L属性定义）T integer|charL L,id|id等所需信息获得后再归约改成从右向左归约D id LL,id L|:TT integer|char,4.3 L属性定义的自上而下计算,D id L addtype(id.entry,L.type)L,id L1 L.type=L1.Type;addtype(id.entry,L1.type)L:T L.type=T.typeT integer T.type=integerT real T.type=real,4.4 L属性的自下而上计算,在自下而上分析的框架中实现L属性定义的方法它能实现任何基于LL(1)文法的L属性定义也能实现许多（但不是所有的）基于LR(1)的L属性定义,4.4 L属性的自下而上计算,删除翻译方案中嵌入的动作E T RR+T print(+)R1|T print()R1|T num print(num.val)在文法中加入产生的标记非终结符，让每个嵌入动作由不同标记非终结符M代表，并把该动作放在产生式M 的右端E T RR+T M R1|T N R1|T num print(num.val)M print(+)N print(),这些动作的一个重要特点：没有引用原来产生式文法符号的属性,4.4 L属性的自下而上计算,4.4.2 分析栈上的继承属性例 int p,q,r D T L.in=T.type LT int T.type=integerT real T.type=realL L1.in=L.in L1,id addtype(id.entry,L.in)L id addtype(id.entry,L.in),4.4 L属性的自下而上计算,4.4.2 分析栈上的继承属性1、属性位置能预测例 int p,q,r D T L.in=T.type LT int T.type=integerT real T.type=realL L1.in=L.in L1,id addtype(id.entry,L.in)L id addtype(id.entry,L.in),4.4 L属性的自下而上计算,4.4.2 分析栈上的继承属性1、属性位置能预测例 int p,q,r D T L.in=T.type LT int T.type=integerT real T.type=realL L1.in=L.in L1,id addtype(id.entry,L.in)L id addtype(id.entry,L.in),继承属性的计算可以略去，引用继承属性的地方改成引用其他符号的综合属性,4.4 L属性的自下而上计算,4.4 L属性的自下而上计算,2、属性的位置不能预测S aACC.i=A.sS bABCC.i=A.sC cC.s=g(C.i)增加标记非终结符，使得位置可以预测S aACC.i=A.sS bABMCM.i=A.s;C.i=M.sC cC.s=g(C.i)M M.s=M.i,4.4 L属性的自下而上计算,2、属性的位置不能预测S aACC.i=A.sS bABCC.i=A.sC cC.s=g(C.i)增加标记非终结符，使得位置可以预测S aACC.i=A.sS bABMCM.i=A.s;C.i=M.sC cC.s=g(C.i)还得考虑M.sM M.s=M.i 计算的可预测,4.4 L属性的自下而上计算,模拟继承属性的计算继承属性是某个综合属性的一个函数S aACC.i=f(A.s)C cC.s=g(C.i)增加标记非终结符，把f(A.s)的计算移到对标记非终结符归约时进行S aANCN.i=A.s;C.i=N.sN N.s=f(N.i)C cC.s=g(C.i),4.4 L属性的自下而上计算,例 数学排版语言EQN S B.ps=10 BS.ht=B.ht B B1.ps=B.ps B1B2.ps=B.ps B2B.ht=max(B1.ht,B2.ht)B B1.ps=B.ps B1sub B2.ps=shrink(B.ps)B2B.ht=disp(B1.ht,B2.ht)B textB.ht=text.h B.ps,4.4 L属性的自下而上计算,4.4 L属性的自下而上计算,4.4 L属性的自下而上计算,4.4 L属性的自下而上计算,举例说明 在text归约成B时，B的ps属性 都在次栈顶位置,4.4 L属性的自下而上计算,4.4 L属性的自下而上计算,4.4 L属性的自下而上计算,4.4 L属性的自下而上计算,4.4 L属性的自下而上计算,4.4 L属性的自下而上计算,4.4 L属性的自下而上计算,4.4 L属性的自下而上计算,本 章 要 点,语义规则的两种描述方法：语法制导的定义和翻译方案设计简单问题的语法制导定义和翻译方案，这是本章的重点和难点语法制导定义和翻译方案的实现S属性的自下而上计算（边分析边计算）L属性的自上而下计算（边分析边计算）L属性的自下而上计算（边分析边计算）不再介绍先分析后计算的方法不能边分析边计算的情况是存在的，见5.6节,例 题 1,下面是产生字母表=0,1,2上数字串的一个文法：S D S D|2D 0|1写一个语法制导定义，判断它接受的句子是否为回文数 S Sprint(S.val)S D1 S1 D2S.val=(D1.val=D2.val)and S1.val S 2S.val=trueD 0D.val=0D 1D.val=1,例 题 2,为下面文法写一个语法制导的定义，用S的综合属性val给出下面文法中S产生的二进制数的值。例如，输入101.101时，S.val=5.625（可以修改文法）若按22+0+20+2-1+0+2-3来计算，该文法对小数点左边部分的计算不利，因为需要继承属性来确定每个B离开小数点的距离S L.L|LL L B|BB 0|1,例 题 2,为下面文法写一个语法制导的定义，用S的综合属性val给出下面文法中S产生的二进制数的值。例如，输入101.101时，S.val=5.625（可以修改文法）若小数点左边按(1 2+0)2+1计算。该办法不能直接用于小数点右边，需改成(1 2+0)2+1)/23，这时需要综合属性来统计B的个数S L.L|LL L B|BB 0|1,例 题 2,为下面文法写一个语法制导的定义，用S的综合属性val给出下面文法中S产生的二进制数的值。例如，输入101.101时，S.val=5.625（可以修改文法）更清楚的办法是将文法改成下面的形式S L.R|LL L B|BR B R|BB 0|1,例 题 2,S L.RS.val=L.val+R.valS LS.val=L.valL L1 BL.val=L1.val 2+B.valL BL.val=B.valR B R1R.val=R1.val/2+B.val/2R BR.val=B.val/2B 0B.val=0B 1B.val=1,例 题 3,给出把中缀表达式翻译成没有冗余括号的中缀表达式的语法制导定义。例如,因为和是左结合,(a(b+c)(d)可以重写成a(b+c)d两种方法：先把表达式的括号都去掉，然后在必要的地方再加括号去掉表达式中的冗余括号，保留必要的括号,例 题 3,第一种方法S E print(E.code)E E1+T if T.op=plus thenE.code=E1.code|“+”|“(”|T.code|“)”elseE.code=E1.code|“+”|T.code;E.op=plusE TE.code=T.code;E.op=T.op,例 题 3,T T1 Fif(F.op=plus)or(F.op=times)thenif T1.op=plus thenT.code=“(”|T1.code|“)”|“”|“(”|F.code|“)”elseT.code=T1.code|“”|“(”|F.code|“)”else if T1.op=plus thenT.code=“(”|T1.code|“)”|“”|F.codeelseT.code=T1.code|“”|F.code;T.op=times,例 题 3,T FT.code=F.code;T.op=F.opF idF.code=id.lexeme;F.op=idF(E)F.code=E.code;F.op=E.op,例 题 3,第二种方法给E，T和F两个继承属性left_op和right_op分别表示左右两侧算符的优先级给它们一个综合属性self_op表示自身主算符的优先级再给一个综合属性code表示没有冗余括号的代码分别用1和2表示加和乘的优先级，用3表示id和(E)的优先级，用0表示左侧或右侧没有运算对象的情况,例 题 3,S EE.left_op=0;E.right_op=0;print(E.code)E E1+TE1.left_op=E.left_op;E1.right_op=1;T.left_op=1;T.right_op=E.right_op;E.code=E1.code|“+”|T.code;E.self_op=1;E TT.left_op=E.left_op;T.right_op=E.right_op;E.code=T.code;E.self_op=T.self_op,例 题 3,T T1 F.T F.F idF.code=id.lexeme;F.self_op=3,例 题 3,F(E)E.left_op=0;E.right_op=0;F.self_op=if(F.left_op=F.right_op)thenE.self_op else 3F.code=if(F.left_op=F.right_op)thenE.code else“(”|E.code|“)”,习 题,第一次 4.1，4.3，4.5第二次4.7，4.9,4.10第三次 4.13，4.14,