编译原理语法制导翻译课件市公开课一等奖省赛课微课金奖课件.pptx

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,2021/10/3,#,？为何进行词法和语法分析,？用,A,进行归约表示是什么意思,看：,operand+term,EE,1,+T,E,1,值+,T,值结果作为,E,值,即：取来,E,1,值和,T,值做加法运算，结果作为,E,值,E.val=E,1,.val+T.val,第1页,第五章 语法制导翻译,翻译任务,首先是语义分析和正确性检验，若正确，则翻译成中间代码或目标代码。,基本思想,依据翻译需要设置文法符号属性，以描述语法结构语义。,比如，一个变量属性有类型，层次，存放地址等。表示式属性有类型，值等。,属性值计算和产生式相联络。伴随语法分析进行，执行属性值计算，完成语义分析和翻译任务。,第2页,5.1,语法制导翻译概述,语法制导翻译概念描述,在进行语法分析同时，完成对应语义处理,EE,1,+E,2,E.val:=E,1,.val+E,2,.val,语法结构含有要求语义,问题：怎样依据被识别出语法成份进行语义处理？,第3页,1.语义分析任务,语义检验,例：类型、运算、维数、越界,语义处理,例：变量存放分配,例：表示式求值,例：语句翻译（中间代码生成）,总目标：生成等价中间代码,第4页,2.代码结构,计算学科：对信息（数据表示）描述和变换算法系统研究,变换：源、目标以及源与目标对应关系,语句代码结构,语句分类：,说明语句,符号表查填,可执行语句,指令代码,第5页,3.经典处理方法,对应每一个产生式编制一个语义子程序，当一个产生式取得匹配时，调用对应语义子程序实现语义检验与翻译,EE,1,+TE.val:=E,1,.val+T.val,TT,1,*FT.val:=T,1,.val*F.val,F idF.val:=id.val,适宜在完成归约时候进行,第6页,3.经典处理方法,在产生式右部适当位置，插入对应语义动作，按照分析进程，执行碰到语义动作,D T L.in:=T.type L,T int T.type:=integer,T real T.type:=real,L L,1,.in:=Lin L,1,id,语义,能够看成是对应文法符号属性,适宜在进行推导时完成,第7页,语义翻译流程,输,入,符,号,串,分,析,树,依,赖,图,语,义,规,则,计,算,实际上，编译中语义翻译实现并不是按图中流程处理；而是随语法分析进展，识别出一个语法结构，就对它语义进行分析和翻译。,第8页,语法制导定义是对上下文无关文法推广,每个,文法,符号都有一个相关属性集。,综合属性,:,经过分析树中其子节点属性值计算出来；,继承属性,:,由该节点弟兄节点及父节点属性值计算出来；,依赖图,语义规则,建立了属性之间依赖关系，这些关系能够用图来表示，这么图称为,依赖图。,属性,5.1,语法制导定义,(Syntax-directed definitions),第9页,在一个,语法制导定义,中，,A,P,都有与,之相关联一套语义规则，规则形式为,b,：,=f,（,c,1,，,c,2,，,，,c,k,），,f,是一个函数，而且或者,1,b,是,A,一个综合属性而且,c,1,，,c,2,，,，,c,k,是,中,符号属性，或者,2,b,是,中,符号一个继承属性而且,c,1,，,c,2,，,，,c,k,是,A,或,中,任何文法符号属性。,在两种情况下，都说属性,b,依赖于属性,c,1,，,c,2,，,，,c,k,。,5.1.1,语法制导定义形式,第10页,例,5.1,台式计算器程序语法制导定义（图,5,2),产生式 语义规则,L,En print(Eval,)(,可看作是,L,虚属性,),E E,1,+T E val:=E,1,val+T val,E T E val:=T val,T T,1,*F T val:=T,1,val*F val,T F T val:=F val,F(E)F val:=E val,F,digit,F val:=,digit,lexval,第11页,S-,属性定义,仅仅使用综合属性,语法制导定义,。,结点属性值计算恰好和自底向上分析建立分析树结点同时进行。,例,5.2,输入：,3*5+4n,5.1.2,综合属性,第12页,digit,lexval:=3,F,val:=3,Tval:=3,digit,lexval:=5,F,val:=5,T,val:=15,*,E,val:=15,+,digit,lexval:=4,F,val:=4,T,val:=4,E,val:=19,L,n,第13页,综合属性值计算方法,对于,s-,属性定义，通常使用自底向上分析方法，在建立每一个结点处使用语义规则来计算综合属性值，即在用哪个产生式进行归约后，就执行那个产生式,s-,属性定义计算属性值，从叶结点到根结点进行计算。,5.1.3,继承属性,继承属性,值是由此结点父结点和或弟兄结点一些属性值来决定。,例,5.3,变量说明属性定义,int a,b,c,第14页,表,5.2,带有继承属性,L.in,语法制导定义,产生式 语义规则,D,TL,L,in:=T,type,T,int,T,type:=,integer,T,real,T,type:=,real,L,L,1,id,L,1,in:=L,in,addtype(,id,entry,L,in),L,id,addtype(,id,entry,L,in),第15页,T,L,L,id3,L,id2,D,id1,real,1 entry,2 entry,3 entry,4,type,in 5,6,in 7,8,in 9,10,第16页,依赖图结构方法,for,分析树中每个结点,n do,for,与结点,n,对应文法符号每个属性,a do,在依赖图中为,a,结构一个结点；,for,分析树每个结点,n do,for,结点,n,所用产生式对应每条,语义规则,b:,f,（,c,1,，,c,2,，,，,c,k,)do,for i:=1 to k do,从结点,c,i,到结点,b,结构一条有向边；,5.1.4,依赖图,_,取得语义规则计算次序,第17页,例,5-5,图,5,5,分析树依赖图,第18页,拓扑排序,一个无环有向图拓扑排序是图中,结点任何次序,m,1,，,m,2,，,，,m,k,，使得,边必须是从序列中前面结点指向后面,结点，也就是说，假如,m,i,m,j,是,m,i,到,m,j,一条边,那么在 序列中,m,i,必须出现在,m,j,前面。,若依赖图中无环，则存在一个拓扑排序，它就是属性值计算次序。,5.1.5,计算次序,第19页,1,，,2,，,3,，,4,，,5,，,6,，,7,，,8,，,9,，,10,a,4,:=real;,a,5,:=a,4,;,addtype(id,3,entry,a,5,);,a,7,:=a,5,;,addtype(id,2,entry,a,7,);,a,9,:=a,7,;,addtype(id,1,entry,a,9,);,例,5.6,图,5.7,拓扑排序是：,第20页,分析树法,:,输入串分析树依赖图计算次序,基于规则方法,：在结构编译器时，用手工或专门工具来分析语义规则,确定属性值计算次序。,忽略语义规则方法,：在分析过程中翻译，那么计算次序由分析方法来确定而表面上与语义规则无关。这种方法限制了能被实现语法制导定义种类。,后两种方法无须显式结构依赖图，所以时空效率更高。,计算语义规则方法,第21页,抽象语法,（,abstract syntax,）,从详细语法中,抽象出,语言结构本质性东西，而不考虑语言详细符号表示，从而可简化语义形式描述。,在不一样语言中赋值语句有不一样写法：,x=y;,x:=y;,yx,等等，能够用抽象形式,assignment(variable,expression),把前面各种详细形式统一起来。,5.2,语法树（,syntax tree,）结构,第22页,表示程序层次结构树，它把分析树中对语义无关紧要成份去掉，是分析树抽象形式，也称作语法结构树，或结构树。,语法树是惯用一个中间表示形式。,把,语法,分析和翻译分开。,语法,分析过程中完成翻译有许多优点，但也有一些不足：,1.,适于语法分析文法可能不完全反应语言成份自然层次结构；,2.,因为语法分析方法限制，对分析树结点访问次序和翻译需要访问次序不一致。,语法树,第23页,产生式,sif B then S1 else S2,语法树,if-then-else,|,B S1 S2,赋值语句,语法树,assignment,variable expression,在语法树中，运算符号和关键字都不在叶结点，而是在内部结点中出现。,5.2.1,语法树,第24页,结构表示式语法树使用函数,1.mknode(op,left,right),建立一个标识为,op,运算符结点，两个域,left,和,right,是指向左右运算对象指针。,2,mkleaf(id,entry),建立一个标识为,id,标识符结点,其域,entry,是指向该标识符在符号表中对应表项指针。,3.mkleaf(num,val),建立一个标识为,num,数结点，域,val,用于保留该数值。返回指向新建立结点指针。,5.2.2,结构表示式语法树,第25页,id,to entry a,num 4,id,to entry c,+,图,5-8 a-4+c,语法树,第26页,5.2.3,结构语法树语法制导定义,产生式,语义规则,E,E,1,+T E.nptr:=mknode(+,E,1,.nptr,T.nptr),E,E,1,-T E.nptr:=mknode(-,E,1,.nptr,T.nptr),E,T E.nptr:=T.nptr,T,(E)T.nptr:=E.nptr,T,id T.nptr:=mkleaf(id,id.entry),T,num T.nptr:=mkleaf(num,num.val),第27页,图,5-10 a-4+c,语法树结构,第28页,无环有向图,（,Directed Acyclic Graph,简称,dag),用途：提取表示式中公共子表示式，以取得目标程序局部优化。,方法：执行,mknode,和,mkleaf,时，检验是否已经有相同结点，若有，则返回对应结点指针。,5.2.4,表示式无环有向图,第29页,例,5.9,表示式,a,a*(b-c)+(b-c)*d,dag,+,*,d,+,*,a,c,b,第30页,在分析栈中使用一个附加域来存放综合属性值。下列图为一个带有综合属性值域分析栈：,state,val,.,X,X.x,Y,.,Y.y,.,.,Z,Z.z,top,5.3 S-,属性定义及其自底向上计算,第31页,A,b:=f(c,1,c,2,c,k,),b,是,A,综合属性，,ci,(1,i,k),是,中符号属性。,综合属性值是在自底向上分析过程中，每次归约之前进行计算。,A,XYZ Aa:=f(X x,Y y,Z z),A,a,X x Y y Z z,第32页,top,state,val,.,.,X,X.x,Y,Y.y,Z,Z.z,state,val,.,.,A,A.a,top,定义式,A.a:=f(X.x,Y.y,Z.z),（抽象）变成,valntop:=f(valtop-2,valtop-1,valtop),（详细可执行代码）。在执行代码段之前执行：,ntop:=top-r+1 r,是句柄长度,执行代码段后执行：,top:=ntop;,第33页,产生式 代码段和图,5,2,对比）,L,En printf(valntop),E E+T valntop:=valtop-2+valtop,E T,T T*F valntop:=valtop-2*valtop,T F,F(E)valntop:=valtop-1,F digit,例,5.10,用,LR,分析器实现,台式计算器,(,图,5,16,）,第34页,表,5.5,翻译输入,3*5+4n,所做移动,输入,state val,使用产生式,3*5+4n -,*,5+4n 3 3,*,5+4n F 3 F,digit,*,5+4n T 3 T,F,5+4n T*3-,+4n T*5 3-5,+4n T*F 3-5 F,digit,第35页,+4n T 15 T,T*F,+4n E 15 E,T,4n E+15-,n E+4 15-4,n E+F 15-4 F,digit,n E+T 15-4 T,F,n E 19 E,E+T,En 19-,L 19 L,En,第36页,采取自底向上分析，比如,LR,分析，首先给出,S-,属性定义，然后，把,S-,属性定义变成可执行代码段，这就组成了翻译程序。象一座建筑，语法分析是构架，归约处有一个“挂钩”，语义分析和翻译代码段（语义子程序）就挂在这个钩子上。这么，伴随语法分析进行，归约前调用对应语义子程序,完成翻译任务。,总结,第37页,在语法分析过程中进行语义分析和翻译，属 性计算次序受到语法分析建立分析树结点次序限制。,一个自然计算属性次序是按深度优先访问分析树结点次序，它适应各种自底向上和自顶向下翻译方法。,L-,属性定义 可用于按深度优先次序计算属性值。,5.4 L-,属性定义,第38页,procedure,dfvisit,(n:node);,begin,for n,每个子结点,m(,从左至右,)do,begin,计算,m,继承属性；,dfvisit,(m),end;,计算,n,综合属性,end;,深度优先次序计算属性,第39页,定义,一个语法制导定义是,L-,属性定义,，假如,AX,1,X,2,X,n,P,其每一个语义规则中每一个属性都是一个综合属性，或是,X,j,(1,j,n),一个继承属性，这个继承属性仅依赖于,1.,产生式中,X,j,左边符号,X,1,，,X,2,，,X,j-1,属性；,2,A,继承属性。,每一个,S-,属性定义都是,L-,属性定义。,5.4.1 L-,属性定义,第40页,图,5,19,非,L-,属性语法制导定义,产生式,语义规则,A,LM,A,QR,L.i:=l(A.i),M.i:=m(L.s),A.s:=f(M.s),R.i:=r(A.i),Q.i:=q(R.s),A.s:=f(Q.s),图,5,19,语法制导定义不是,L-,属性定义,文法符号,Q,继承属性依赖于它右边文法符号,R,属性,第41页,定义,翻译模式是语法制导定义一个便于翻译书写形式。其中属性与文法符号相对应，语义规则或语义动作用花括号 括起来，可被插入到产生式右部任何适当位置上。,这是一个语法分析和语义动作交织表示法，它表示在按深度优先遍历分析树过程中何时执行语义动作。,翻译模式给出了使用语义规则进行计算次序。可看成是分析过程中翻译注释。,5.4.2,翻译模式,第42页,将带有,+,号和,-,号中缀表示式翻译成后缀表示式：,ETR,Raddop T print(addop.lexeme)R,1,|,Tnumprint(num.val),把语义动作看成终止符号，输入,9-5+2,其分析树如图,5,20,，当按深度优先遍历它，执行遍历中访问语义动作，将输出,9 5-2+,它是输入表示式,9-5+2,后缀式。,例,5.12,一个简单翻译模式,第43页,图,5.10 9-5+2,带语义动作分析树,第44页,条件：语法制导定义是,L-,属性定义,确保语义动作不会引用还没有计算属性值。,1.,只需要综合属性情况,：,为每一个语义规则建立一个包含赋值动作，并把这个动作放在对应产生式右边末尾。,比如：,T,T,1,*F Tval:=T,1,val*F val,T,T,1,*F Tval:=T,1,val*F val,设计翻译模式（依据语法制导定义）,第45页,2.,现有综合属性又有继承属性,产生式右边符号继承属性必须在这个符号以前动作中计算出来。,一个动作不能引用这个动作右边符号综合属性。,产生式左边非终止符号综合属性只有在它所引用全部属性都计算出来以后才能计算。计算这种属性动作通常可放在产生式右端末尾。,设计翻译模式（依据语法制导定义）,第46页,下面翻译模式不满足要求：,S,A,1,A,2,A,1,in:=1;A,2,in:=2,A a print(A in),例,5.13,从,L-,属性制导定义建立一个满足上面,要求,翻译模式。,使用文法产生语言是数学排版语言,EQN,E sub 1,val,编排结果,E,1,val,第47页,B.,ps,:=10,S.,ht,:=B.,ht,B,1,.,ps,:=B.,ps,B,2,.,ps,:=B.,ps,B.,ht,:=,max,(B,1,.,ht,B,2,.,ht,),B,1,.,ps,:=B.,ps,B,2,.,ps,:=,shrink,(B.,ps,),B.,ht,:=,disp,(B,1,.,ht,B,2,.,ht,),B.,ht,:=text.,h,*B.,ps,S,B,B,B,1,B,2,B,B,1,sub B,2,B,text,产生式,语义规则,图,5-22,盒子大小和高度语法制导定义,第48页,B,是盒子；,B,BB,表示两个盒子并置；,B,B sub B,表示第二个盒子是第一个盒子下标；,ps,是继承属性,，影响公式高度；正文实际高度 等于正文标准高度乘以,B.,ps,；,B,高度由,综合属性,ht,表示；,text,h,可依据,text,性质查表得到；,shrink,把,B,2,尺寸缩小,30%,；,disp,把,B,2,向下偏置。,第49页,S,B.,ps,:=10,B,S.,ht,:=B.,ht,B B,1,.,ps,:=B.,ps,B,1,B,2,.,ps,:=B.,ps,B,2,B.,ht,:=max(B,1,.,ht,B,2,.,ht,),B B,1,.,ps,:=B.,ps,B,1,sub B,2,.,ps,:=,shrink,(B.,ps,),B,2,B.,ht,:=,disp,(B,1,.,ht,B,2,.,ht),Btext,B.,ht,:=text.,h,*B,.,ps,从图,5-22,结构翻译模式,第50页,用翻译模式结构自顶向下翻译。,5.5.1,从翻译模式中消除左递归,对于一个翻译模式，若采取自顶向下分析，必须消除左递归和提取左公因子，在改写基本文法时考虑属性值计算。,例,5.14,图,5,24,带左递归文法翻译模式被转换成图,5,25,带右递归文法翻译模式。,5.5,自顶向下翻译,第51页,E,E,1,+T,E,val:=E,1,val+T,val,E,E,1,-T,E,val:=E,1,val-T,val,E,T E.val:=T,val,T,(E),T,val:=E,val,T,num,T,val:=num,val,带左递归文法翻译模式,第52页,ET R,i:=T,val,R,E,val:=R,s,R,T,R,1,i:=R.i+T.,val,R,1,R.,s:=R,1,s,R-,T,R,1,i:=R,i-T,val,R,1,R,s:=R,1,s,R,R,s:=R,i,T,（,E,）,T,val:=E.,val,Tnum T,val:=num,val,经过转换带有右递归文法翻译模式,第53页,E,val=6,T,val=9,R,i=9;R s=,6,9,T,val=5,5,R,i=4;R s=,6,+,T,val=2,R,i=6;,R s=,6,2,图,5,26,表示式,9-5+2,计算,第54页,左递归翻译模式,AA,1,Y,A.a:=g(A,1,.a,Y.y),AX,A.a:=f(X.x),（,5.2,）,每一个文法符号都有一个综合属性，用对应小写字母表示，,g,和,f,是任意函数。,消除左递归，文法转换成,AX R,RY R|,（,5.3,）,关于左递归翻译模式更普通化讨论,第55页,再考虑语义动作，翻译模式变为：,AX,R,i:=f(X,x),R,A.,a:=R.,s,RY,R,1,i:=g,（,R,i,Y,y,）,R,1,R,s:=R,1,s,R,R,s:=R,i,（,5.4,）,经过转换翻译模式与图,5,25,中一样,使用,R,继承属性,i,和综合属性,s,。,（,5.2,）和（,5.4,）结果是一样,为何？,关于左递归翻译模式更普通化讨论,第56页,A,a=g(g(f(X,x),Y,1,y),Y,2,y),A,a=g(f(X,x),Y,1,y),A,a=f(X,x),Y,2,Y,1,X,(a),输入：,XY,1,Y,2,第57页,A,R,i=f(X,x),R,i=g(f(X,x),Y,1,y),R,i=g(g(f(X,x),Y,1,y),Y,2,y),Y,2,Y,1,X,(b),第58页,E,E,1,+T,Enptr:=mknode(+,E,1,nptr,T nptr),E,E,1,-T,Enptr:=mknode(-,E,1,nptr,T nptr),E,T Enptr:=T nptr,从,翻译模式中消除左递归，变成图,5,28,翻译模式。,例,5.15,表示式建立语法树翻译模式,第59页,ET R,i:=T,nptr,R,E,nptr:=R,s,R,T,R,1,i:=mknode(+,R,i,T,nptr),R,1,R,s:=R,1,s,R-,T,R,1,i:=mknode(-,R,i,T,nptr),R,1,R,s:=R,1,s,R,R,s:=R,i,T(E )T,nptr:=E,nptr,Tid T,nptr:=mkleaf(id,id,entry),Tnum,T,nptr:=mkleaf(num,num,val)第60页,使用继承属性结构语法树,E,i,R,s,T,id,R,-,T,num,i,R,T,+,id,id,num 4,id,-,+,to entry for a,to entry for c,nptr,nptr,nptr,第61页,算法,5.1,预测语法制导翻译器建立,输入：一个带有适合预测分析基础文法 语法制导翻译模式。,输出：一个语法制导翻译器代码。,方法：在预测分析器中加入语义动作代码。,1,A,V,N,建立一个可递归调用函数过程,A,。为,A,每一个继承属性都设置一个形式参数，函数返回值是,A,综合属性值。,2.,函数过程,A,代码（指用符号形式表示数据和程序）要依据当前输入符号来决定使用哪一个产生式。,5.5.2,预测翻译器设计,第62页,3,与每一个产生式相关代码，从左到右根椐产生式右部是单词符号、非终止符号还是语义动作，分别是：,（,a,）对于带有综合属性,x,单词符号,X,，,x,存放在,X.x,中，,Match(X),。,（,b,）对于,B,V,N,，编写一个赋值语句,c,：,=B,（,b,1,b,2,，,b,k,),其中,，,b,1,b,2,，,b,k,是继承,属性，,c,是,综合属性。,（,c,）对于每个动作，动作代码抄进翻译器中，用代表属性变量来代替对属性每一次引用。,5.5.2,预测翻译器设计,第63页,例,5.16,：,Raddop,T,R,1,i:mknode,（,addop,lexeme,，,R,i,，,T,nptr,）,R,1,R.s:=R,1,.s,R,R.s:=R.i,（,5,5,）,递归下降结构语法树,function R,（,in:,syntax-tree-node,）：,syntaX-tree-node,；,var nptr,i1,s1,s,：,syntax-tree-node;,addoplexeme:char,；,第64页,IF lookahead=addop,THEN /*,产生式,Raddop T R*/,addoplexeme:=lexval;,match(addop);,nptr:=T;,i1:=mknodeaddoplexeme,in,nptr);,s1:=R(i1);,s:=s1;,ELSE s:=in;/*,产生式,R,*/,return(s);,第65页,5.6 L,属性自底向上计算,在自底向上分析框架中实现,L,属性定义方法,它能实现任何基于,LL(1),文法,L,属性定义,也能实现许多（但不是全部）基于,LR(1),L,属性定义,第66页,5.6 L,属性自底向上计算,5.6.1,删除翻译方案中嵌入动作,E,T R,R,+T print(,+,)R1|,T print(,)R1|,T,num print(num.val),第67页,5.6 L,属性自底向上计算,5.6.1,删除翻译方案中嵌入动作,E,T R,R,+T print(,+,)R1|,T print(,)R1|,T,num print(num.val),在文法中加入产生,标识非终止符，让每个嵌入动作由不一样标识非终止符,M,代表，并把该动作放在产生式,M,右端,第68页,5.6 L,属性自底向上计算,5.6.1,删除翻译方案中嵌入动作,E,T R,R,+T print(,+,)R1|,T print(,)R1|,T,num print(num.val),在文法中加入产生,标识非终止符，让每个嵌入动作由不一样标识非终止符,M,代表，并把该动作放在产生式,M,右端,E,T R,R,+T M R1|,T N R1|,T,num print(num.val),M,print(,+,),N,print(,),第69页,5.6 L,属性自底向上计算,5.6.2,分析栈上继承属性,属性位置能预测,例,int p,q,r,D,T L.in=T.type,L,T,int T.type=integer,T,real T.type=real,L,L1.in=L.in,L1,id addtype(id.entry,L.in),L,id addtype(id.entry,L.in),D,T,L,L,r,L,q,p,int,type,in,in,in,第70页,5.6 L,属性自底向上计算,D,T,L,L,r,L,q,p,int,type,in,in,in,产 生 式,代 码 段,D,TL,T,int,val,top,=,integer,T,real,val,top,=,real,L,L,1,id,addType,(,val,top,val,top,3),L,id,addType,(,val,top,val,top,1),第71页,5.6 L,属性自底向上计算,属性位置不能预测,S,aACC.i=A.s,S,bABCC.i=A.s,C,cC.s=g(C.i),第72页,5.6 L,属性自底向上计算,属性位置不能预测,S,aACC.i=A.s,S,bABCC.i=A.s,C,cC.s=g(C.i),增加标识非终止符,S,aACC.i=A.s,S,bABMCM.i=A.s;C.i=M.s,C,cC.s=g(C.i),M,M.s=M.i,第73页,5.6 L,属性自底向上计算,5.6.3,模拟继承属性计算,继承属性是某个综合属性一个函数,S,aACC.i=f(A.s),C,cC.s=g(C.i),增加标识非终止符，把,f(A.s),计算移到对标识非终止符归约时进行,S,aANCN.i=A.s;C.i=N.s,N,N.s=f(N.i),C,cC.s=g(C.i),第74页,5.6 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,B1,sub B2.ps=shrink(B.ps),B2B.ht=disp(B1.ht,B2.ht),B,textB.ht=text.h,B.ps,第75页,5.6 L,属性自底向上计算,产,生,式,语 义 规 则,S,LB,B,.,ps,=,L,.,s,;,S,.,ht,=,B,.,ht,L,L,.,s,=10,B,B,1,MB,2,B,1,.,ps,=,B,.,ps,;,M,.,i,=,B,.,ps,;,B,2,.,ps,=,M,.,s,;,B,.,ht,=,max,(,B,1,.,ht,B,2,.,ht,),M,M,.,s,=,M,.,i,B,B,1,sub,NB,2,B,1,.,ps,=,B,.,ps,;,N,.,i,=,B,.,ps,;,B,2,.,ps,=,N,.,s,;,B.ht,=,disp,(,B,1,.,ht,B,2,.,ht,),N,N,.,s,=,shrink,(,N,.,i,),B,text,B,.,ht,=text.,h,B,.,ps,第76页,5.6 L,属性自底向上计算,S,M,s,B,L,s,B,B,text,B,sub,N,s,B,text,text,第77页,5.6 L,属性自底向上计算,产,生,式,代 码 段,S,LB,B,.,ps,=,L,.,s,;,S,.ht,=,B,.,ht,L,L,.,s,=10,B,B,1,MB,2,B,1,.,ps,=,B,.,ps,;,M,.,i,=,B,.,ps,;,B,2,.,ps,=,M,.,s,;,B,.,ht,=,max,(,B,1,.,ht,B,2,.,ht,),M,M,.,s,=,M,.,i,B,B,1,sub,NB,2,B,1,.,ps,=,B,.,ps,;,N,.,i,=,B,.,ps,;,B,2,.,ps,=,N,.,s,;,B.ht,=,disp,(,B,1,.,ht,B,2,.,ht,),N,N,.,s,=,shrink,(,N,.,i,),B,text,B,.,ht,=text.,h,B,ps,第78页,5.6 L,属性自底向上计算,产 生 式,代 码 段,S,LB,valtop,1=valtop,L,L.s=10,B,B1 MB2,B1.ps=B.ps;M.i=B.ps;,B2.ps=M.s;B.ht=max(B1.ht,B2.ht),M,M.s=M.i,B,B1 sub NB2,B1.ps=B.ps;N.i=B.ps;,B2.ps=N.s;B.ht=disp(B1.ht,B2.ht),N,N.s=shrink(N.i),B,text,B.ht=text.h,B.ps,第79页,5.6 L,属性自底向上计算,产 生 式,代 码 段,S,LB,valtop,1=valtopL,valtop+1=10,B,B1 MB2,B1.ps=B.ps;M.i=B.ps;,B2.ps=M.s;B.ht=max(B1.ht,B2.ht),M,M.s=M.i,B,B1 sub NB2,B1.ps=B.ps;N.i=B.ps;,B2.ps=N.s;B.ht=disp(B1.ht,B2.ht),N,N.s=shrink(N.i),B,text,B.ht=text.h,B.ps,第80页,5.6 L,属性自底向上计算,产 生 式,代 码 段,S,LB,valtop,1=valtop,L,valtop+1=10,B,B1 MB2,valtop,2=max(valtop,2,valtop),M,M.s=M.i,B,B1 sub NB2,B1.ps=B.ps;N.i=B.ps;,B2.ps=N.s;B.ht=disp(B1.ht,B2.ht),N,N.s=shrink(N.i),B,text,B.ht=text.h,B.ps,第81页,5.6 L,属性自底向上计算,产 生 式,代 码 段,S,LB,valtop,1=valtop,L,valtop+1=10,B,B1 MB2,valtop,2=max(valtop,2,valtop),M,valtop+1=valtop,1,B,B1 sub NB2,B1.ps=B.ps;N.i=B.ps;,B2.ps=N.s;B.ht=dispB1.ht,B2.ht),N,N.s=shrink(N.i),B,text,B.ht=text.h,B.ps,第82页,5.6 L,属性自底向上计算,产 生 式,代 码 段,S,LB,valtop,1=valtop,L,valtop+1=10,B,B1 MB2,valtop,2=max(valtop,2,valtop),M,valtop+1=valtop,1,B,B1 sub NB2,valtop,3=disp(valtop,3,valtop),N,N.s=shrink(N.i),B,text,B.ht=text.h,B.ps,第83页,5.6 L,属性自底向上计算,产,生,式,代 码 段,S,LB,val,top,1=,val,top,L,val,top,+1,=10,B,B,1,MB,2,val,top,2=,max,(,val,top,2,val,top,),M,val,top,+1,=,val,top,1,B,B,1,sub,NB,2,val,top,3=,disp,(,val,top,3,val,top,),N,val,top,+1,=,shrink,(,val,top,2),B,text,B,.,ht,=text.,h,B,.,ps,第84页,5.6 L,属性自底向上计算,产,生,式,代 码 段,S,LB,val,top,1=,val,top,L,val,top,+110,B,B,1,MB,2,val,top,2=,max,(,val,top,2,val,top,),M,val,top,+1,=,val,top,1,B,B,1,sub,NB,2,val,top,3=,disp,(,val,top,3,val,top,),N,val,top,+1,=,shrink,(,val,top,2),B,text,val,top,=,val,top,val,top,1,第85页,5.7,递归计算,回顾：语法制导定义实现,分析树方法,边分析边进行属性计算，只能完成,L,属性计算（忽略规则方法）,本节介绍先分析后计算方法，不局限于,L,属性计算（基于规则方法）,为每个非终止符结构一个属性计算函数，不过该函数不含语法分析部分,为非终止符不一样综合属性结构不一样函数,第86页,5.7,递归计算,5.7.1,自左向右遍历,为,B,结构一个属性计算函数,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,B1,sub B2.ps=shrink(B.ps),B2B.ht=disp(B1.ht,B2.ht),B,textB.ht=text.h,B.ps,第87页,5.7,递归计算,function B(n,ps);,var ps1,ps2,ht1,ht2begin,case,在结点,n,产生式,of,B,B1 B2:,ps1=ps;,ht1=B(child(n,1),ps1);,ps2=ps;,ht2=B(child(n,2),ps2);,return max(ht1,ht2);,B,B,1,.,ps,=,B,.,ps,B,1,B,2,.,ps,=,B,.,ps,B,2,B,.,ht,=,max,(,B,1,.,ht,B,2,.,ht,),第88页,5.7,递归计算,function B(n,ps);,var ps1,ps2,ht1,ht2;,begin,case,在结点,n,产生式,of,B,B1 sub B2:,ps1=ps;,ht1B(child(n,1),ps1);,ps2=shrink(ps);,ht2=B(child(n,3),ps2);,return disp(ht1,ht2);,B,B,1,.,ps,=,B,.,ps,B,1,sub,B,2,.,ps,=,shrink,(,B,.,ps,),B,2,B.ht,=,disp,(,B,1,.,ht,B,2,.,ht,),第89页,5.7,递归计算,function,B,(,n,ps,);,var,ps,1,ps,2,ht,1,ht,2;,begin,case,在结点,n,产生式,of,B,text:,return,ps,text.,h,;,default:,err