编译语言语法制导的翻译 4.ppt

第四章 语法制导的翻译,本章内容介绍一种形式化的语义描述方法：语法制导的翻译，包括它的两种具体形式：语法制导的定义和翻译方案 介绍语法制导翻译的实现方法,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*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 语法制导的定义,4.1.3 继承属性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.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.2 S属性定义的自下而上计算,4.2.1 语法树语法树是分析树的浓缩表示：算符和关键字是作为内部结点语法制导翻译可以基于分析树，也可以基于语法树语法树的例子：,4.2 S属性定义的自下而上计算,4.2.2 构造语法树的语法制导定义,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分析器增加一个域来保存综合属性值,栈 state val,top,4.2 S属性定义的自下而上计算,4.2.3 S属性的自下而上计算将LR分析器增加一个域来保存综合属性值,栈 state val,top,若产生式A XYZ的语义规则是A.a=f(X.x,Y.y,Z.z),4.2 S属性定义的自下而上计算,4.2.3 S属性的自下而上计算将LR分析器增加一个域来保存综合属性值,栈 state val,top,若产生式A XYZ的语义规则是A.a=f(X.x,Y.y,Z.z)，那么归约后：,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 L属性定义的自上而下计算,边分析边翻译的方式能否用于继承属性？属性的计算次序一定受分析方法所限定的分析树结点建立次序的限制分析树的结点是自左向右生成如果属性信息是自左向右流动，那么就有可能在分析的同时完成属性计算,4.3 L属性定义的自上而下计算,4.3.1 L属性定义如果每个产生式A X1 X2 Xn 的每条语义规则计算的属性是A的综合属性；或者是Xj 的继承属性，1 j n,但它仅依赖：该产生式中Xj左边符号X1,X2,Xj-1的属性；A的继承属性,4.3 L属性定义的自上而下计算,4.3.1 L属性定义如果每个产生式A X1 X2 Xn 的每条语义规则计算的属性是A的综合属性；或者是Xj 的继承属性，1 j n,但它仅依赖：该产生式中Xj左边符号X1,X2,Xj-1的属性；A的继承属性S属性定义属于L属性定义,4.3 L属性定义的自上而下计算,变量类型声明的语法制导定义是一个L属性定义,4.3 L属性定义的自上而下计算,4.3.2 翻译方案例 把有加和减的中缀表达式翻译成后缀表达式如果输入是8+5 2，则输出是8 5+2,4.3 L属性定义的自上而下计算,4.3.2 翻译方案例 把有加和减的中缀表达式翻译成后缀表达式如果输入是8+5 2，则输出是8 5+2 E T RT+T+T+R addop T print(addop.lexeme)R1|T num print(num.val),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 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.nptrRE.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,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,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:TT integer|charL L,id|id,4.3 L属性定义的自上而下计算,4.3.4 用综合属性代替继承属性Pascal的声明，如m,n:integerD L:TT integer|charL L,id|id改成从右向左归约D id LL,id L|:TT integer|char,4.3 L属性定义的自上而下计算,4.3.4 用综合属性代替继承属性Pascal的声明，如m,n:integerD L:TT 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属性的自下而上计算,4.4.1 删除翻译方案中嵌入的动作E T RR+T print(+)R1|T print()R1|T num print(num.val),4.4 L属性的自下而上计算,4.4.1 删除翻译方案中嵌入的动作E T RR+T print(+)R1|T print()R1|T num print(num.val)在文法中加入产生的标记非终结符，让每个嵌入动作由不同标记非终结符M代表，并把该动作放在产生式M 的右端,4.4 L属性的自下而上计算,4.4.1 删除翻译方案中嵌入的动作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 分析栈上的继承属性属性位置能预测例 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属性的自下而上计算,属性的位置不能预测S aACC.i=A.sS bABCC.i=A.sC cC.s=g(C.i),4.4 L属性的自下而上计算,属性的位置不能预测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属性的自下而上计算,4.4.3 模拟继承属性的计算继承属性是某个综合属性的一个函数S aACC.i=f(A.s)C cC.s=g(C.i),4.4 L属性的自下而上计算,4.4.3 模拟继承属性的计算继承属性是某个综合属性的一个函数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属性的自下而上计算,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。不得修改文法，但属性使用没有限制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,