第7章语法制导的语义计算.ppt

第八章语法制导翻译法,指出：按照编译程序的逻辑工作过程，语法分析后，接下来就要进行语义分析了，语义分析后，再生成中间代码。实际应用中，往往在语法分析的同时，进行语义分析并生成中间代码，这就是语法制导翻译法。语法制导翻译过程中，需要借助于属性文法进行语义描述和语义处理。,本章主要内容,属性内容语法制导翻译的基本思想中间代码的形式,属性文法,对于某个压缩了的文法，当把每个文法符号和一组属性相关联，并把产生式附加以语义规则的时候，就得到属性文法。语法制导的翻译过程：由于属性文法的规则和产生式是一一对应的关系。所以，由属性文法确定的语义分析可以在语法分析的过程中进行。这个过程成为语法制导的翻译。,属性文法,属性文法(attributegrammar):A=(G,V,F),其中G:一个CFG,属性文法的基础。V:有穷的属性集每个属性与一个文法符号相关联这些属性代表与文法符号相关的语义信息如类型、地址、值、代码、符号表内容等等属性与变量一样，可以进行计算和传递属性加工的过程即是语义处理的过程属性加工与语法分析同时进行属性的表示：标始符（或数），写在相应文法的下边点记法：E.Val,E.Place,E.TypeF:关于属性的属性断言或一组属性的计算规则(称为语义规则).断言或语义规则与一个产生式相联,只引用该产生式左端或右端的终结符或非终结符相联的属性.,继承属性和综合属性,两类属性：综合属性(SynthesizedAttribute)：归约型属性用于“自下而上”传递信息继承属性(InheritedAttribute)：推导型属性用于“自上而下”传递信息。属性的计算：AX1X2XnA的综合属性,计算S(A):=f(I(X1),I(Xn)Xj的继承属性,计算T(Xj):=f(I(A),.I(Xn)文法符号属性的说明：非终结符既可有综合属性也可有继承属性，但文法开始符号没有继承属性.终结符只有综合属性.通常规定：文法符号的综合属性与继承属性无交。,综合属性的例子,非终结符E、T及F都有一个综合属性val,符号digit有一个综合属性，它的值由词法分析器提供。与产生式LE对应的语义规则仅仅是打印由E产生的算术表达式的值的一个过程，我们可认为这条规则定义了L的一个虚属性。某些非终结符加上标是为了区分一个产生式中同一非终结符多次出现,综合属性的自下而上定值,.,L,E.val=19,E.val=15,T.val=4,T.val=15,F.val=4,T.val=3,F.val=3,F.val=5,digit.lexval=4,digit.lexval=5,digit.lexval=3,+,*,3*5+4的带注释的分析树,设表达式为35+4，则语义动作打印数值19,继承属性的例子,继承属性L.in,产生式,语义规则,DTL,Tint,Treal,LL1,id,Lid,L.in:=T.type,T.type=integer,T.type:=real,L1.in:=L.in,addtype(id.entry,L.in),addtype(id.entry,L.in),继承属性的自上而下定值,D,L.in=real,L.in=real,L.in=real,T.type=real,real,id2,id1,id3,.,Realid1,id2,id3,，,，,L属性文法,适合于指导自上而下的分析。一个属性文法称为L属性文法，如果对于每个产生式AX1X2Xn，满足：（1）Xj（1jn）的继承属性仅依赖于下述属性值中的一种：A的继承属性；产生式右部位于Xj左边的符号X1，X2，Xj-1的属性。（2）A的综合属性，仅依赖于下述属性值中的一种：A的继承属性；产生式右部符号Xj（除自身外）的任意属性。,L属性文法的自上而下计算,L属性文法的翻译器通常可借助于LL分析器实现。在L属性文法的基础上，LL分析器可以改造为一个翻译器，在对输入串进行语法分析的同时对属性进行计算。需要对LL分析器增加语义栈,以保存与栈中文法符号有关的继承属性值。每当进行推导时，新的属性值就由栈中正在推导的产生式左边符号的属性值来计算。,S属性文法,适用于指导自下而上的分析一个属性文法称为S属性文法,当且仅当满足如下条件：（1）所有非终结符的属性是综合属性；（2）同一产生式中相同符号的各综合属性之间无相互依赖关系；（3）如果q是某个产生式中文法符号V的继承属性，则属性q的值仅仅依赖于该产生式右部位于V左边的符号的属性。,S属性文法的自下而上计算,S属性文法的翻译器通常可借助于LR分析器实现。在S属性文法的基础上，LR分析器可以改造为一个翻译器，在对输入串进行语法分析的同时对属性进行计算。需要对LR分析器增加语义栈,以保存与栈中文法符号有关的综合属性值。每当进行归约时，新的属性值就由栈中正在归约的产生式右边符号的属性值来计算。,LR分析器改造为翻译器,LR分析器增加语义栈产生式语义规则）（.）1.1.）.l）1*.1.）F.F.）（）.）ii.:.,LR分析器改造为翻译器,*的分析和计值过程步骤动作状态栈语义栈(值栈)符号栈余留输入串）3*）3*）*）*）*）*）*）*）*）*）*）（）*#）（）（）接受,语法制导翻译的基本思想,为每条产生式配上一个翻译子程序（称为语义动作或语义子程序）；语义动作的工作指明符号串的意义；按照这种意义规定了对应的动作：查添各种表格改变变量之值诊察与报告源程序错误产生中间代码在语法分析的同时，当一个产生式获得匹配（对于自上而下分析）或用于归约（对于自下而上分析）时，就执行相应产生式的语义子程序。,语法制导翻译法的一般原理,直观地说，语法制导翻译法（SDTS）组成如下：一个源语言；一个目标语言；一组翻译规则为文法中的产生式添加上语义动作作用：将任何源语言符号串翻译成对应的目标语言串。,语法制导翻译法的形式化定义,SDTS是一个CFG,是一个五元组T=(VT,VN,R,S),其中(1)VT是有穷的输入字母表（包含源语言中的符号）；(2)VN是有穷的非终结符集；(3)是有穷的输出字母表（包含出现在输出串中的符号）；(4)R是形如Aw,y的规则的有穷集合；R中规则形式：Aw,yAVN,w(VTVN)*,y(VN)*且y中那组非终结符是w中那组非终结符的置换。W：规则的源成分y：规则的翻译成分(5)SVN，是文法的开始符号。,基础源文法和基础目标文法,SDTS的基础源文法(输入文法)一个CFG：(VT,VN,P,S),其中P=Aw|Aw,y属于R)SDTS的基础目标文法(输出文法)一个CFG：(VN,P,S),其中P=Ay|Aw,y属于R),一个例子,翻译模式,翻译模式可递归定义为：(S,S)是一个翻译模式，且这两个S是相关的(aAb,aAb)是一个翻译模式，且两个A是相关的；此外，若A-g,g是R中的一条规则，则(agb,agb)也是一个翻译模式。规则中g和g的非终结符之间的相关性也必须带进这种翻译模式中。显然，翻译模式是一个形如(u,v)的串对，其中u是基础源文法的一个句型,u(VTVN)*,v是与u对应的翻译，v(VN)*,翻译模式的变换,若(aAb,aAb)是一个翻译模式，A-g,g是R中的一条规则，则(aAb,aAb)=(agb,agb)是一个翻译模式到另一个翻译模式的变换。与推导过程类似。,SDTS定义的翻译,一个SDTS定义的翻译是如下对偶集：(x,y)|(S,S)=*(x,y),xVT*,y*比较：CFG中语言的定义。,翻译的例子,a+a*a的翻译过程：(E,E)(E+T,ET+)(T+T,TT+)(F+T,FT+)(a+T,aT+)(a+TF,aFF+)(a+FF,aFF+)(a+aF,aaF+)(a+aa,aaa+),树变换,语法制导的翻译过程可以看成是将输入文法Gi中的推导树变换成输出文法G0中的推导树。给了输入句子x，可以按如下方式得到x的一个翻译：先为推导x构造一棵推导树，再变换该树到输出文法中的一棵树，然后取此输出树的边缘作为x的一个翻译。具体变换过程如下：从中剪去终结符号结点；根据适当的翻译规则，重排每个中间结点的孩子；添加对应于输出符号集中的终结符结点。,中间代码,中间代码（Intermediatecode）：源程序的一种内部表示，不依赖目标机的结构，易于机械生成目标代码的中间表示。中间代码的几种形式逆波兰四元式三元式间接三元式树,逆波兰表示方法,表达式的一种表示形式运算符直接跟在运算量后面又称为后缀(postfix)表示法定义：设E是表达式，那么如果E是变量或者常量，E的逆波兰表示为EE1OPE2=E1E2OP，其中E1,E2为E1,E2的逆波兰表示。(E)=E,其中E为E的逆波兰表示。,后缀表达式的计值,自左向右扫描表达式，每遇到运算量就把它推进栈，每遇到k目算符就把它作用于栈顶的k个项，并把运算结果来代替这k个项,逆波兰表示的例子,A+bab+A+b*cabc*+(a+b)*cab+c*A+B*(C-D)+E/(C-D)NABCD-*+ECDN/+a+b*c/(d+e)abc*de+/+,逆波兰表示方法的扩充,赋值语句：V:=eVe:=例子：t=(a+b)*c/(d-e)tab+c*de-/=转向语句：gotojump条件语句：Ifthenelsejumpfjump数组说明：arrayAl1.u1,.,ln.unL1u1lnunAADEC下标变量：AASUBS,四元式,一般形式：例子：a+b*c*bct1+at1t2单目运算符的处理：为空。一般来讲，四元式的运算符都有对应的机器指令，或者对应的子程序，因此从四元式生成指令代码是容易的。四元式之间的联系是通过临时变量实现的，便于进行代码优化。,四元式表示的例子,A+B*(C-D)+E/(C-D)N（1）(-CDT1)（2）(*BT1T2)（3）(+AT2T3)（4）(-CDT4)（5）(T4NT5)（6）(/ET5T6)（7）(+T3T6T7),三元式,如果我们不明显给出四元式的结果部分，而是用四元式的编号来表示结果，那么我们可以得到三元式。形式如下：例子：a+b*c=*bc+a三元式的出现顺序与表达式的计值顺序一致。和四元式的比较：无须临时变量；占用存储空间少；相互引用太多，使得难以进行代码优化。,三元式表示的例子,A+B*(C-D)+E/(C-D)N(1)(-CD)(2)(*B(1)(3)(+A(2)(4)(-CD)(5)(4)N)(6)(/E(5)(7)(+(3)(6),间接三元式,间接三元式：为了便于代码优化处理，用一张间接码表辅以三元式表的办法来表示中间代码。间接码表是一张指示器表，它将按运算的先后顺序列出有关三元式在三元式表中的位置。当在代码优化过程中需要调整运算顺序时，只需重新安排间接码表即可。例子：X:=(A+B)*CY:=D(A+B),间接三元式表示的例子,A+B*(C-D)+E/(C-D)N间接三元式序列间接码表(-CD)(1)(*B(1)(2)(+A(2)(3)(4)(1)N)(1)(/E(4)(4)(6)(+(3)(5)(5)(6),树形表示（抽象语法树AST）,采用树形表示作为一种中间代码形式，有助于代码的产生和优化。树形表示的定义：简单变量或常数的树就是该变量或常数自身；如果表示e1和e2的树为T1和T2，那么，e1+e2,e1*e2,-e1的树分别是：显然，树形表示是三元式表示的翻版。抽象语法树（AbstractSyntaxTree）在语法树中去掉那些对翻译不必要的信息，获得更有效的源程序中间表示AST可以拓广，用来表示数组元素、过程调用、控制结构、说明等。,简单算术表达式和赋值句的翻译,文法：Ai:=EEE+E|E*E|-E|(E)|I引入的语义属性：E.PLACE与非终结符E相联系，表示存放E值的变量名在符号表的入口或整数码（对临时变量）语义过程：NEWTEMP:函数过程。每次调用，回送一个代表新临时变量名的整数码作为函数值。ENTRY(i):函数过程。对i所代表标识符查找符号表以获知它在符号表中位置（入口）。GEN(OP,ARG1,ARG2,RESULT):语义过程。把四元式(OP,ARG1,ARG2,RESULT)填入四元式表中。,产生式的语义描述,(1)Ai:=EGEN(:=,E.PLACE,_,ENTRY(i)(2)EE1+E2E.PLACE:=NEWTEMP;GEN(+,E1.PLACE,E2.PLACE,E.PLACE)(3)EE1*E2E.PLACE:=NEWTEMP;GEN(*,E1.PLACE,E2.PLACE,E.PLACE)(4)E-E1E.PLACE:=NEWTEMP;GEN(,E1.PLACE,_,E.PLACE)(5)E(E1)E.PLACE:=NEWTEMP(6)EiE.PLACE:=ENTRY(i),布尔表达式的翻译,布尔表达式基本作用：用作计算逻辑值；用作控制条件。布尔表达式文法：EEE|EE|E|(E)|idropid|id结合性和优先级：rop；左结合。,布尔表达式的翻译,计算布尔表达式的值：逐步计算；利用布尔表达式的性质采取优化措施：ABifAthentrueelseBABifAthenBelsefalseBifBthenfalseelsetrue,布尔表达式的翻译,逐步计算的例子:ABC=D(=,C,D,T1)(,B,T1,T2)(,A,T2,T3),如,ifBthenS1elseS,2,B,的,代,码,条,件,假转