语法制导翻译与属文法市公开课金奖市赛课一等奖课件.pptx

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,*,第六章 语法制导翻译与属性文法,School of Computer Science&Technology,Harbin Institute of Technology,重点：,语法制导翻译基本思想，语法制导定义，,翻译模式，自顶向下翻译，自底向上翻译。,难点：,属性意义，对综合属性，继承属性，,固有属性理解，属性计算，,怎么通过属性来表示翻译。,第1页,第1页,/10/10,2,第,6,章,语法制导翻译与属性文法,6.1,语法制导翻译概述,6.2,语法制导定义,6.3,属性计算,6.4,翻译模式6.5,本章小结,第2页,第2页,/10/10,3,为何进行词法和语法分析？,用,A,进行归约表示是什么意思？,看：,operand+term,E,E,1,+,T,E,1,值,+,T,值结果作为,E,值,即：取来,E,1,值和,T,值做加法运算，结果作为,E,值,E,.,val,=,E,1,.,val,+,T,.,val,问题,第3页,第3页,/10/10,4,6.1,语法制导翻译概述,为了提升编译程序可移植性，普通将编译程序划分为前端和后端。,前端通常包括词法分析、语法分析、语义分析、中间代码生成、符号表建立，以及与机器无关中间代码优化等，它们实现普通不依赖于详细目的机器。,后端通常包括与机器相关代码优化、目的代码生成、相关错误处理以及符号表访问等。,图,6.1,编译器前端逻辑结构,第4页,第4页,/10/10,5,6.1,语法制导翻译概述,语义分析器主要任务是检查各个语法结构静态语义，称为静态语义分析或静态检查,类型检查：操作数和操作符类型是否相容；,控制流检查：控制流转向目的地址是否合法；,惟一性检查：对象是否被重复定义；,关联名检查：同一名字多次特定出现是否一致。,将静态检查和中间代码生成结合到语法分析中进行技术称为,语法制导翻译,。,第5页,第5页,/10/10,6,6.1,语法制导翻译概述,语法制导翻译基本思想,在进行语法分析同时，完毕相应语义处理。也就是说，一旦语法分析器辨认出一个语法结构就要马上对其进行翻译，翻译是依据语言语义进行，并通过调用事先为该语法结构编写语义子程序来实现。,对文法中每个产生式附加一个,/,多个语义动作,(,或语义子程序,),，在语法分析过程中，每当需要使用一个产生式进行推导或归约时，语法分析程序除执行相应语法分析动作外，还要执行相应语义动作,(,或调用相应语义子程序,),。,第6页,第6页,/10/10,7,6.1,语法制导翻译概述,语义子程序功效,指明相应产生式中各个文法符号详细含义，并要求了使用该产生式进行分析时所应采用语义动作,(,如传送或处理语义信息、查填符号表、计算值、生成中间代码等,),。,语义信息获取和加工是和语法分析同时进行，并且这些语义信息是通过文法符号来携带和传递。,第7页,第7页,/10/10,8,6.1,语法制导翻译概述,一个文法符号,X,所携带语义信息称为,X,语义属性，简称为属性，它是依据翻译需要设置,(,相应分析树结点数据结构,),，主要用于描述语法结构语义。,一个变量属性有类型、层次、存储地址等,表示式属性有类型、值等。,第8页,第8页,/10/10,9,6.1,语法制导翻译概述,属性值计算和产生式相关联，伴随语法分析进行，执行属性值计算，完毕语义分析和翻译任务。,E,E,1,+,E,2,E,.,val,:=,E,1,.,val,+,E,2,.,val,语法结构含有要求语义,问题：如何依据被辨认出语法成份进行语义处理？,亦即如何,将属性值计算及翻译工作同产生式相关联？,第9页,第9页,/10/10,10,典型处理办法一,语法制导定义,通过将属性与文法符号关联、将语义规则与产生式关联来描述语言结构翻译方案,相应每一个产生式编写一个语义子程序，当一个产生式取得匹配时，就调用相应语义子程序来实现语义检查与翻译,E,E,1,+,T,E,.,val,:=,E,1,.,val,+,T,.,val,T,T,1,*,F,T,.,val,:=,T,1,.,val,*,F,.,val,F,digit,F,.,val,:=digit.,lexval,适宜在完毕归约时候进行,第10页,第10页,/10/10,11,典型处理办法二,翻译模式,通过将属性与文法符号关联，并将语义规则插入到产生式右部来描述语言结构翻译方案,在产生式右部适当位置，插入相应语义动作，按照分析进程，执行碰到语义动作,D,T,L,.,inh,:=,T,.,type,L,T,int,T,.,type,:=integer,T,real,T,.,type,:=real,L,L,1,.,inh,:=,L,.,inh,L,1,id,addtype,(id.,entry,L,.,inh,),L,id,addtype,(id.,entry,L,.,inh,),适宜在进行推导时完毕,第11页,第11页,/10/10,12,6.2,语法制导定义,语法制导定义是附带有属性和语义规则上下文无关文法,属性是与文法符号相关联语义信息,语义规则是与产生式相关联语义动作,语法制导定义是基于语言结构语义要求设计，类似于程序设计，语法制导定义中属性类似于程序中用到数据结构，用于描述语义信息，语义规则类似于计算，用于搜集、传递和计算语义信息。,属性通常被保留在分析树相关节点中,第12页,第12页,/10/10,13,概念术语,综合属性：节点属性值是通过度析树中该节点或其子节点属性值计算出来,继承属性：节点属性值是由该节点、该节点弟兄节点或父节点属性值计算出来,固有属性：通过词法分析直接得到属性,依赖图：描述属性之间依赖关系图，依据语义规则来结构,注释分析树：节点带有属性值分析树,第13页,第13页,/10/10,14,语法制导定义形式,在一个,语法制导定义,中，,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,第14页,第14页,/10/10,15,例,6.1,台式计算器语法制导定义,产生式 语义规则,L,En,print,(,E,val,)(,可看作是,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,第15页,第15页,/10/10,16,S,-,属性,定义,只含综合属性语法制导定义称为,S,-,属性定义,对于,S,-,属性定义，通常使用自底向上分析办法，在建立每一个结点处使用语义规则来计算综合属性值，即在用哪个产生式进行归约后，就执行那个产生式,S,-,属性定义计算属性值，从叶结点到根结点进行计算。,没有副作用语法制导定义有时又称为,属性文法,，属性文法语义规则单纯依据常数和其它属性值来定义某个属性值,第16页,第16页,/10/10,17,继承属性,当分析树结构同源代码抽象语法不“匹配”时，继承属性将非常有用。下面例子能够阐明如何用继承属性来处理这种不匹配问题，产生这种不匹配原因是由于文法通常是为语法分析而不是为翻译设计。,例,6.2,考虑如何在自顶向下分析过程中计算,3*5,和,4*8*9,这样表示式项,消除左递归之后算数表示式文法一个子集：,T,FT,T,*,FT,1,T,F,digit,第17页,第17页,/10/10,18,表,6.3,为适于自顶向下分析文法设计语法制导定义,产生式,语义规则,T,FT,T,.,inh,:=,F,.,val,T,.,val,:=,T,.,syn,T,*,FT,1,T,1,.,inh,:=,T,.,inh,F,.,val,T,.,syn,:=,T,1,.,syn,T,T,.,syn,:=,T,.,inh,F,digit,F,.,val,:=digit.,lexval,第18页,第18页,/10/10,19,4*8*9,注释分析树,第19页,第19页,/10/10,20,表,6.3,中语法制导定义相应翻译模式,假如对,4*8*9,进行自顶向下语法制导翻译，则,val,值计算顺序为,依据上述对,val,值计算顺序,，,能够将表,6.3,中语法制导定义转换成下列翻译模式,T,F,T,.,inh,:=,F,.,val,T,T,.,val,:=,T,.,syn,T,*,F,T,1,.,inh,:=,T,.,inh,F,.,val,T,1,T,.,syn,:=,T,1,.,syn,T,T,.,syn,:=,T,.,inh,F,digit,F,.,val,:=digit.,lexval,第20页,第20页,/10/10,21,6.3,属性计算,语义规则定义了属性之间依赖关系，这种依赖关系将影响属性计算顺序,为了拟定分析树中各个属性计算顺序，我们能够用图来表示属性之间依赖关系，并将其称为依赖图,假如依赖图中没有回路，则利用它能够很以便地求出属性计算顺序。,注释分析树只是给出了属性值，而依赖图则能够帮助我们拟定如何将这些属性值计算出来。,第21页,第21页,/10/10,22,6.3.1,依赖图,所谓依赖图其实就是一个有向图，用于描述分析树中节点属性和属性间互相依赖关系，称为分析树依赖图。,每个属性相应依赖图中一个节点，假如属性,b,依赖于属性,c,，则从属性,c,节点有一条有向边指向属性,b,节点。,属性间依赖关系是依据相应语义规则拟定。,第22页,第22页,/10/10,23,依赖图结构办法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,有向边；,第23页,第23页,/10/10,24,例,6.3,图,6.3,中注释分析树依赖图,第24页,第24页,/10/10,25,6.3.2,属性计算顺序,拓扑排序,一个无环有向图拓扑排序是图中结点任何顺序,m,1,，,m,2,，,，,m,k,，使得边必须是从序列中前面结点指向后面结点，也就是说，假如,m,i,m,j,是,m,i,到,m,j,一条边,那么在 序列中,m,i,必须出现在,m,j,前面。,若依赖图中无环，则存在一个拓扑排序，它就是属性值计算顺序。,例,6.4,图,6.4,拓扑排序为：,1,，,2,，,3,，,4,，,5,，,6,，,7,，,8,，,9,，,10,，,11,，,12,，,13,第25页,第25页,/10/10,26,6.3.2,属性计算顺序,依据拓扑排序得到翻译程序,a,4:=4,a,5:=,a,4,a,6:=8,a,7:=,a,5,a,6,a,8:=9,a,9:=,a,7,a,8,a,10:=,a,9,a,11:=,a,10,a,12:=,a,11,a,13:=,a,12,上述属性计算办法又称为,分析树法,，这种办法在编译时需要显式地结构分析树和依赖图，因此编译时空效率比较低，并且假如分析树依赖图中存在回路话，这种办法将会失效。,这种办法长处是能够多次遍历分析树，从而使得属性计算不依赖于所采用语法分析办法以及属性间严格依赖关系。,第26页,第26页,/10/10,27,计算语义规则其它办法,基于规则办法,在结构编译器时，用手工或专门工具来分析语义规则,拟定属性值计算顺序。,忽略语义规则办法,在分析过程中翻译，那么计算顺序由分析办法来拟定而表面上与语义规则无关。这种办法限制了能被实现语法制导定义种类。,这两种办法都不必显式结构依赖图，因此时空效率更高。,第27页,第27页,/10/10,28,S-,属性定义,定义,6.1,只含综合属性语法制导定义称为,S,-,属性定义，又称为,S,-,属性文法。,假如某个语法制导定义是,S,-,属性定义，则能够按照自下而上顺序来计算分析树中节点属性。,一个简朴属性计算办法是对分析树进行后根遍历，并在最后一次遍历节点,N,时计算与节点,N,相关联属性。,postorder,(,N,),for,N,每个子节点,M,(,从左到右,),postorder,(,M,);,计算与节点,N,相关联属性,;,第28页,第28页,/10/10,29,L-,属性定义,定义,6.2,一个语法制导定义被称为,L-,属性定义，当且仅当它每个属性或者是综合属性，或者是满足下列条件继承属性：设有产生式,A,X,1,X,2,X,n,，其右部符号,X,i,(1,i,n,),继承属性只依赖于下列属性：,A,继承属性；,产生式中,X,i,左边符号,X,1,、,X,2,、,、,X,i,-1,综合属性或继承属性；,X,i,本身综合属性或继承属性，但前提是,X,i,属性不能在依赖图中形成回路。,L,-,属性定义又称为,L,-,属性文法。,第29页,第29页,/10/10,30,表,6.3,L-,属性,定义示例,产生式,语义规则,T,FT,T,.,inh,:=,F,.,val,T,.,val,:=,T,.,syn,T,*,FT,1,T,1,.,inh,:=,T,.,inh,F,.,val,T,.,syn,:=,T,1,.,syn,T,T,.,syn,:=,T,.,inh,F,digit,F,.,val,:=digit.,lexval,第30页,第30页,/10/10,31,例,6.7,不是,L-,属性定义语法制导定义,产生式,语义规则,A,BC,A,.,syn,:=,B,.,b,B,.,inh,:=,f,(,C,.,c,A,.,syn,),语义规则,B,.,inh,:=,f,(,C,.,c,A,.,syn,),定义了一个继承属性，因此整个语法制导定义就不是,S,-,属性定义了。另外，即使这条语义规则是合法属性定义规则，但不满足,L,-,属性定义要求。这是由于：属性,B,.,inh,定义中用到了属性,C,.,c,，而,C,在产生式右部处于,B,右边。即使在,L,-,属性定义中能够使用弟兄节点属性来定义某个属性，但这些弟兄节点必须是左弟兄节点才行。因此，该语法制导定义也不是,L,-,属性定义。,第31页,第31页,/10/10,32,L-,属性定义中属性计算,visit,(,N,),for,N,每个子节点,M,(,从左到右,),计算节点,M,继承属性,;,visit,(,M,);,计算节点,N,综合属性,;,;,第32页,第32页,/10/10,33,抽象语法树,是表示程序层次结构树，它把分析树中对语义无关紧要成份去掉，是分析树抽象形式，也称作语法结构树，或结构树。,语法树是惯用一个,中间表示,形式。,把语法分析和翻译分开。语法分析过程中完毕翻译有许多长处，但也有一些不足：,1.,适于语法分析文法也许不完全反应语言成份自然层次结构；,2.,由于语法分析办法限制，对分析树结点访问顺序和翻译需要访问顺序不一致。,6.3.5,属性计算示例,抽象语法树结构,第33页,第33页,/10/10,34,产生式,S,if,B,then,S,1,else,S,2,语法树,if-then-else,|,B,S,1,S,2,赋值语句,语法树,assignment,variable,expression在语法树中，运算符号和关键字都不在叶结点，而是在内部结点中出现。,语法树,第34页,第34页,/10/10,35,结构表示式语法树使用函数,1.,mknode,(,op,left,right,),建立一个标识为,op,运算符结点，两个域,left,和,right,分别是指向左右运算对象指针。,2,mkleaf,(id,entry,),建立一个标识为,id,标识符结点，其域,entry,是指向该标识符在符号表中相应表项指针。,3.,mkleaf,(num,val,),建立一个标识为,num,数结点，其域,val,用于保留该数值。,结构表示式语法树,第35页,第35页,/10/10,36,结构表示式语法树语法制导定义,产生式,语义规则,T,T,1,*,F,T,.,node,:=,mknode,(*,T,1,.,node,F,.,node,),T,T,1,/,F,T,.,node,:=,mknode,(/,T,1,.,node,F,.,node,),T,F,T,.,node,:=,F,.,node,F,(,E,),F,.,node,:=,E,.,node,F,id,F,.,node,:=,mkleaf,(id,id.,entry,),F,num,F,.,node,:=,mkleaf,(num,num.,val,),第36页,第36页,/10/10,37,图,6.5 3*x/y,语法树结构,第37页,第37页,/10/10,38,3*x/y,抽象语法树结构环节,p,1,:=,mkleaf,(num,3),；,p,2,:=,mkleaf,(id,entry,-,x,),；,p,3,:=,mknode,(*,p,1,p,2,),；,p,4,:=,mkleaf,(id,entry,-,y,),；,p,5,:=,mknode,(/,p,3,p,4,),；,图,6.5,语法树是自底向上结构，对于那些为便于进行自顶向下分析而设计文法来说，使用同样环节照样能够建立图,6.5,中抽象语法树。当然，分析树结构也许大不相同，并且也许需要引入继承属性来传递语义信息。,第38页,第38页,/10/10,39,在自顶向下分析过程中结构语法树,产生式,语义规则,T,FT,T,.,node,:=,T,.,syn,T,.,inh,:=,F,.,node,T,*,FT,1,T,1,.,inh,:=,mknode,(*,T,.,inh,F,.,node,),T,.,syn,:=,T,1,.,syn,T,/,FT,1,T,1,.,inh,:=,mknode,(/,T,.,inh,F,.,node,),T,.,syn,:=,T,1,.,syn,T,T,.,syn,:=,T,.,inh,F,(,E,),F,.,node,:=,E,.,node,F,id,F,.,node,:=,mkleaf,(id,id.entry,),F,num,F,.,node,:=,mkleaf,(num,num.,val,),第39页,第39页,/10/10,40,依据表,6.6,语法制导定义结构,语法树,第40页,第40页,/10/10,41,定义,翻译模式,是语法制导定义一个便于实现书写形式。其中属性与文法符号相关联，语义规则或语义动作用花括号 括起来，并可被插入到产生式右部任何适当位置上。,这是一个语法分析和语义动作交错表示法，它表示在按深度优先遍历分析树过程中何时执行语义动作。,翻译模式给出了使用语义规则进行计算顺序。,可当作是分析过程中翻译注释。,6.4,翻译模式,第41页,第41页,/10/10,42,将中缀表示式翻译成后缀表示式：,E,TR,R,addop,T,print,(addop.,lexeme,),R,1,|,T,num,print,(num.,val,),把语义动作当作终止符号，输入,3+4-5,其分析树如图,6.8,，当按深度优先遍历它，执行遍历中访问语义动作，将输出,3 4+5-,它是输入表示式,3+4-5,后缀式。,例,6.10,一个简朴翻译模式,第42页,第42页,/10/10,43,图,6.8 3+4-5,带语义动作分析树,第43页,第43页,/10/10,44,前提,语法制导定义是,L,-,属性定义,确保语义动作不会引用还没计算出来属性值,1.,只需要综合属性情况,为每一个语义规则建立一个包括赋值动作，并把该动作放在相应产生式右部末尾。,比如：,T,T,1,*,F,T,val,:=,T,1,val,*,F,val,转换成：,T,T,1,*,F,T,val,:=,T,1,val,*,F,val,翻译模式设计,依据语法制导定义,第44页,第44页,/10/10,45,2.,既有综合属性又有继承属性,产生式右边符号继承属性必须在这个符号以前动作中计算出来。,一个动作不能引用这个动作右边符号综合属性。,产生式左边非终止符号综合属性只有在它所引用所有属性都计算出来以后才干计算。计算这种属性动作通常可放在产生式右端末尾。,翻译模式设计,依据语法制导定义,第45页,第45页,/10/10,46,下面翻译模式不满足要求：,S,A,1,A,2,A,1,in,:=1;,A,2,in,:=2,A,a,print,(,A,in,)/*,A,.,in,尚无定义,*,/,例,6.11,从,L,-,属性制导定义建立一个满足上面,要求,翻译模式。,使用文法产生语言是数学排版语言,EQN,E,sub 1,val,编排结果,第46页,第46页,/10/10,47,B,表示盒子,B,B,1,B,2,代表两个相邻盒子并列，且,B,1,位于,B,2,左边。,B,B,1,sub,B,2,代表盒子,B,1,后随下标盒子,B,2,，下标盒子,B,2,以较小字体和较低位置出现。,B,(,B,1,),代表一个由括号括起来盒子,B,1,，主要是为了对多个盒子或下标进行分组。在,EQN,中，使用花括号进行分组，此处使用圆括号是为了避免跟语义动作外面花括号产生冲突。,B,text,代表文本字符串，即任意字符构成串。,该文法是二义性文法，将“并列”和“下标”当作是左结合，并令“下标”优先级高于“并列”话，则能够对该文法所描述语言进行自底向上语法分析。,第47页,第47页,/10/10,48,属性设置,point size,用于表示盒子中文本尺寸,(,以点来计算，也就是字号,),。假如原则盒子尺寸为,p,，则下标盒子尺寸为,0.7,p,。属性,B,.,ps,表示盒子,B,尺寸，该属性是继承属性。每个盒子都有一个基线,(baseline),，用来表示每个文本底部垂直位置。,height,用来表示从盒子顶部到基线距离。属性,B,.,ht,表示盒子,B,高度,height,，该属性是综合属性。,depth,用来表示从基线到盒子底部距离。用属性,B,.,dp,表示盒子,B,深度,depth,，该属性也是综合属性。,第48页,第48页,/10/10,49,表,6.7,对盒子进行排版语法制导定义,产生式,语义规则,S,B,B,.,ps,:=10,S,.,ht,:=,B,.,ht,S,.,dp,:=,B,.,dp,B,B,1,B,2,B,1,.,ps,:=,B,.,ps,B,2,.,ps,:=,B,.,ps,B,.,ht,:=,max,(,B,1,.,ht,B,2,.,ht,),B,.,dp,:=,max,(,B,1,.,dp,B,2,.,dp,),B,B,1,sub,B,2,B,1,.,ps,:=,B,.,ps,B,2,.,ps,:=0.7,B,.,ps,B,.,ht,:=,max,(,B,1,.,ht,B,2,.,ht,-0.25,B,.,ps,),B,.,dp,:=,max,(,B,1,.,dp,B,2,.,dp,+0.25,B,.,ps,),B,(,B,1,),B,1,.,ps,:=,B,.,ps,B,.,ht,:=,B,1,.,ht,B,.,dp,:=,B,1,.,dp,Btext,B,.,ht,:=,getheight,(,B,.,ps,text.,lexval,),B,.,dp,:=,getdepth,(,B,.,ps,text.,lexval,),第49页,第49页,/10/10,50,S,B,.,ps,:=10,B,S,.,ht,:=,B,.,ht,;,S,.,dp,:=,B,.,dp,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,:=0.7,B,.,ps,B,2,B,.,ht,:=,max,(,B,1,.,ht,B,2,.,ht,-0.25,B,.,ps,);,B,.,dp,:=,max,(,B,1,.,dp,B,2,.,dp,+0.25,B,.,ps,);,B,(,B,1,.,ps,:=,B,.,ps,B,1,),B,.,ht,:=,B,1,.,ht,;,B,.,dp,:=,B,1,.,dp,;,B,text,B,.,ht,:=,getheight,(,B,.,ps,text.,lexval,);,B,.,dp,:=,getdepth,(,B,.,ps,text.,lexval,),从表,6.7,结构翻译模式,第50页,第50页,/10/1051,T,F,T,.,inh,:=,F,.,node,T,T,.,node,:=,T,.,syn,T,*,F,T,1,.,inh,:=,mknode,(*,T,.,inh,F,.,node,),T,1,T,.,syn,:=,T,1,.,syn,T,/,F,T,1,.,inh,:=,mknode,(/,T,.,inh,F,.,node,),T,1,T,.,syn,:=,T,1,.,syn,T,T,.,syn,:=,T,.,inh,F,(,E,),F,.,node,:=,E,.,node,F,id,F,.,node,:=,mkleaf,(id,id.,entry,),F,num,F,.,nodemkleaf,(num,num.,val,),从表,6.6,结构翻译模式,第51页,第51页,/10/10,52,在分析栈中使用一个附加域来存储综合属性值。下图为一个带有综合属性值域分析栈：,stack,val,.,X,X,.,x,Y,.,Y,.,y,.,.,Z,Z,.,z,top,6.4.2 S-,属性定义自底向上计算,第52页,第52页,/10/10,53,A,b,:=,f,(,c,1,c,2,c,k,),b,是,A,综合属性，,c,i,(1,i,k,),是,中符号属性。,综合属性值是在自底向上分析过程中，每次归约之迈进行计算。,A,XYZ,A,a,:=,f,(,X,x,Y,y,Zz,),A,a,X,x,Y,y,Z,z,第53页,第53页,/10/10,54,top,stack,val,.,.,X,X,.,x,Y,Y,.,y,Z,Z,.,z,stack,val,.,.,A,A,.,a,top,实现时，将定义式,A,.,a,:=,f,(,X,.,x,Y,.,y,Z,.,z,)(,抽象,),变成,stack,ntop,.,val,:=,f(stack,top,-2.,val,stack,top,-1.,val,stack,top,.,val,)(,详细可执行代码,),。,在执行代码段之前执行：,ntop,:=,top,-,r,+1 ,r,是句柄长度,执行代码段后执行：,top,:=,ntop,;,第54页,第54页,/10/10,55,例,6.14,用,LR,分析器实现,台式计算器,与表,6.2,对比,L,E,nprint(s,tack,top-,1.,val,);,top,:=,top-,1;,E,E,1,+,T,s,tack,top-,2.,val,:=s,tack,top-,2.,val,+s,tack,top,.,val,;,top,:=,top-,2;,E,T,T,T,1,*,F,s,tack,top-,2.,val,:=s,tack,top-,2.,val,s,tack,top,.,val,;,top,:=,top-,2;,T,F,F,(,E,)stack,top-,2.,val,:=s,tack,top-,1.,val,;,top,:=,top-,2;,F,digit,第55页,第55页,/10/10,56,表,6.8,翻译输入,6+7*8n,上移动序列,输入,state,val,使用产生式,6+7*8n -,+7*8,n,6 6,+7*8n F 6 F,digit,+7*8n T 6 T,F,+7*8n E 6 E,T,7*8n E+6+,*8n E+7 6+7,第56页,第56页,/10/10,57,*8,n,E+F 6+7 F,digit,*8n E+T 6+7 T,F,8n E+T*6+7*,n E+T*8 6+7*8,n E+T*F 6+7*8 F,digit,n E+T 6+56 T,T*,F,n E 62 E,E+T,En 62,L 62 L,En,第57页,第57页,/10/10,58,采用自底向上分析，比如,LR,分析，首先给出,S,-,属性定义，然后，把,S,-,属性定义变成可执行代码段，这就构成了翻译程序。象一座建筑，语法分析是构架，归约处有一个“挂钩”，,语义分析和翻译代码段（语义子程序）,就挂在这个钩子上。这样，伴随语法分析进行，归约前调用相应语义子程序,完毕翻译任务。,S-,属性定义小结,第58页,第58页,/10/10,59,用翻译模式结构自顶向下翻译。,1.,从翻译模式中消除左递归,对于一个翻译模式，若采用自顶向下分析，必须消除左递归和提取左公因子，在改写基础文法时考虑属性值计算。,对于自顶向下语法分析，假设语义动作是在与之处于同一位置文法非终止符被展开时执行，并且,不考虑继承属性处理（很简朴）,。,6.4.3 L-,属性定义自顶向下翻译,第59页,第59页,/10/10,60,例,6.15,考虑下列将中缀表示式翻译为后缀表示式翻译模式中两个产生式：,E,E,1,+,T,print(+);,E,T,E,TR,R,+,T,print(+);,R,R,只有简朴语义动作时左递归消除,第60页,第60页,/10/10,61,设有下列左递归翻译模式：,A,A,1,Y,A,.,a,:=,gA,1,.,a,Y,.,y,),A,X,A,.,a,:=,f,(,X,.,x,),假设每个非终止符都有一个综合属性，用相应小写字母表示，,g,和,f,是任意函数。,消除左递归后，文法转换成,A,X R,R,Y R,|,S-,属性定义左递归消除,第61页,第61页,/10/10,62,再考虑语义动作，翻译模式变为：,A,X,R,i,:=,f,(,X,x,),R,A,a,:=,R,s,R,Y,R,1,i,:=,g,(,R,i,Y,y,),R,1,R,s,:=,R,1,s,R,R,s,:=,R,i,通过转换翻译模式使用,R,继承属性,i,和综合属性,s,。,转换前后结果是同样,为何？,S-,属性定义左递归消除,A,A,1,Y,A,.,a,:=,g,(,A,1,.,a,Y,.,y,),A,X,A,.,a,:=,f,(,X,.,x,),引入继承属性,R,.,i,来搜集应用函数,g,计算结果。其初始值为,A,.,a,:=,f,(,X,.,x,）,引入综合属性,R,.,s,在,R,结束生成,Y,时复制,R,.,i,值。,第62页,第62页,/10/10,63,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,第63页,第63页,/10/10,64,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),第64页,第64页,/10/10,65,L,-,属性定义递归下降翻译器结构：,1,对每个非终止符,A,结构一个函数,A,，将非终止符,A,各个继承属性当作函数,A,形式参数，而将非终止符,A,综合属性集当作函数,A,返回值，为了便于讨论，假设每个非终止符只含有一个综合属性。,2,在函数,A,过程体中，不但要进行语法分析，并且要处理相应语义属性。函数,A,代码首先依据当前输入拟定用哪个产生式展开,A,，然后按照,3,中所给办法对各产生式进行编码。,2.,L,-,属性定义递归下降翻译法,第65页,第65页,/10/10,66,3,与每个产生式相应程序代码工作过程为：按照从左到右顺序，依次对产生式右部记号、非终止符和语义动作执行下列动作：,1),对带有综合属性,x,符号,X,，将,x,值保留在,X,.,x,中，并生成一个函数调用来匹配,X,，然后继续读入下一个输入符号；,2),对非终止符,B,，生成一个右部带有函数调用赋值语句,c,:=,B,(,b,1,b,2,bk,),，其中，,b,1,b,2,bk,是代表,B,继承属性变量，,c,是代表,B,综合属性变量；,3),对于语义动作，将其代码复制到语法分析器中，并将对属性引用改为对相应变量引用。,2.,L,-,属性定义递归下降翻译法,第66页,第66页,/10/10,67,例,6.16,function,T,:syntax_tree_node;,function,T,(,inh,:syntax_tree_node):syntax_tree_node;,function,F,:syntax_tree_node;,function,T,:syntax_tree_node;,var,node,syn,:syntax_tree_node;,begin,node,:=,F,;,syn,:=,T,(,node,);,return,syn,end;,第67页,第67页,/10/10,68,function,T,(,inh,:syntax_tree_node):syntax_tree_node;,var,node,inh,1,syn,1:syntax_tree_node;,oplexeme,:char;,beginif,lookahead,=*then begin,/*,匹配产生式,T,*,FT,*/,oplexeme,:=,lexval,;,match,(*);,node,:=,F,;,inh,1:=,mknode,(*,inh,node,);,syn,1:=,T,(,inh,1);,syn,:=,syn,1,end,else if,lookahead,=/then begin,/*,匹配产生式,T,/,FT,*/,oplexeme,:=,lexval,;,match,(/);,node,:=,F,;,inh,1:=,mknode,(/,inh,node,);,syn,1:=,T,(,inh,1);,syn,:=,syn,1,end else,syn,:=,inh,;return,syn,end;,第68页,第68页,/10/10,69,function,F,:syntax_tree_node;,var,node,:syntax_tree_node;,begin if,lookahead,=(then begin,/*,匹配产生式,F,(,E,)*/,match,();,node,:=,E,;,match,(),end,else if,lookahead,=id then begin,/*,匹配产生式,F,id*/,match,(id);,node,:=,mkleaf,(id,id.,entry,)end,else if,lookahead,=num then begin,/*,匹配产生式,F,num*/,match,(num);,node,:=,mkleaf,(num,num.,val,),end return,node,end;,第69页,第69页,/10/10,70,3.,L-,属