编译原理电子教案第八章

第八章语法制导翻译法,语法制导翻译法，就是在语法分析的过程中，依随分析的过程，根据每个产生式添加的语义动作进行翻译的方法。本章介绍语法制导翻译法的基本原理及其在中间代码生成中的应用。,8.1一般原理和树变换,8.1.1一般原理语法制导翻译法（SDTS）由一个源语言、一个目标语言和一组翻译规则组成，这组规则可将任何源语言符号串翻译成对应的目标语言串。SDTS的翻译规则是文法中的产生式再添加上语义动作。什么叫SDTS？为每个产生式配一个语义子程序，在语义分析过程中，在选用某个产生式的同时，调用配备的语义子程序来完成相应的翻译工作的一种方法。,8.1一般原理和树变换,SDTS的形式定义为：SDTS是一个五元组T=(VT,VN,R,S)，其中，VT是一个有穷的输入字母表，包含源语言中的符号；VN是一个有穷的非终结符号集合；是一个有穷的输出字母表，包含出现在翻译串或输出串中的那些符号；R是形如Aw,y的规则的有穷集合，w是由终结符和（或）非终结符组成的串，y是由VN和（或）中的符号组成的串；SVN是一个开始符号，其含义和用法如同CFG中的开始符号。,8.1一般原理和树变换,翻译模式的定义如下：(S,S)是一个翻译模式，且这两个S是相关的（S是SDTS的开始符号）。(aAb,aAb)是一个翻译模式，且两个A是相关的；此外，若Ag,g是R中的一条规则，那么(agb,agb)也是一个翻译模式。规则中g和g的非终结符之间的相关性也必须带进这种翻译模式之中。,8.1一般原理和树变换,8.1.2树变换语法制导的翻译过程可用语法树来说明，可看做从一棵树到另一棵树的变换，其变换过程如下：从中剪掉终结符号结点；根据适当的翻译规则，重排每个中间结点的孩子；添加对应于输出符号集中的终结符结点。,8.2简单SDTS和自上而下翻译器,如果每一规则的翻译成分中，非终结符出现的次序与它们在源成分出现的次序相同，则称一个SDTS是简单的（simple）。定理8.1如果T=(VN,VT,R,S)是其基础源文法为LL(k)的简单SDTS，那么，存在一个自上而下的确定的下推翻译器PDT(PushDownTranslater)，它接收T的输入语言中的任何符号串并产生对应的输出串。,8.2简单SDTS和自上而下翻译器,PDTP的定义如下：P的一个构形是一个四元组（q,x,y,z），其中，q是它的有穷控制器的状态，x是尚待扫描的输入串，y是下推栈，z是此时被打印出的输出符号串。于是，在某次移动中，便有(q,ax,Yy,z)(r,x,gy,zz)其中，存在一条翻译器规则(q,a,Y)包含(r,g,z),8.2简单SDTS和自上而下翻译器,如果P满足下述两个条件，则称P是确定的：对所有的状态q，输入串a和栈符号Z,(q,a,Z)至多只包含一个元素。若(q,Z)非空，则不存在符号a(a)使得(q,a,Z)非空，即对于某个状态和栈符号，在空移动和非空移动之间不应存在冲突。如果SDTS的基础源文法是二义性的，那么就不存在确定的PDT。若SDTS的基础源文法是LL(1)，那么，它的PDT是确定的，而且对每一个可接收的输入串恰好存在一个翻译。,8.3简单后缀SDTS和自下而上翻译器,如果一个SDTS是简单的，而且它的每个翻译规则都有下述形式：Aa0B1a1B2a2Bkak，B1B2Bkw除了最右边的w之外，（输出）终结符不可能出现在翻译成分之中，那么，称这个SDTS为简单后缀的(SimplePostFix)。定理8.2对其基础源文法为LR(k)的每一简单后缀的SDTS，存在一确定的LR(k)PDT,它接收从该基础源文法可推导出的每一句子；它将这种句子的翻译作为输出。,8.3简单后缀SDTS和自下而上翻译器,8.3.1后缀翻译8.3.2IFTHENELSE控制语句将原来的单一产生式拆成三个产生式引进含“then”和“else”关键字的产生式使用空产生式来实现8.3.3函数调用,8.4抽象语法树的构造,抽象语法树AST（Abstract-SyntaxTree）是某个语言结构的一种简洁的树形表示形式，它只需包含该结构尚须转换或归约的信息。任何语法结构（例如表达式、控制结构和说明）都可以用AST表示。AST也可作为一个多遍编译程序的中间语言结构。采用AST表示法有助于代码的产生和优化。,8.4抽象语法树的构造,将语法树简化成一个AST的方式：去掉与单非产生式相关的子树，并上提相关分支上的终结符结点。如果第一棵语法子树也对应于某个单非产生式，则去掉根结点及其连线。对于直接包含运算符的多个子树，上提运算符并让它取代其父结点。去掉括号，并上提运算符，让它取代其结点。最后得到的语法树便是一个AST。,8.4抽象语法树的构造,8.4.1自下而上构造AST8.4.2AST的拓广AST也可表示数组元素、过程调用、控制结构和说明等,数组访问（或过程调用）的AST,8.4抽象语法树的构造,CASE语句的AST,8.5属性文法,属性文法（AttributeGrammar）也称为属性翻译文法。属性文法以上下文无关文法为基础，只不过为每个文法符号配备了一些属性。属性分为两种，一种称为继承属性(InheritedAttribute)，另一种称为综合属性(SynthesizedAttribute)。通常规定：每个文法符号的继承属性和综合属性之交集为空。,8.5属性文法,8.5.1L属性文法L属性文法也称为自上而下的属性翻译文法，适合于用来指导自上而下的分析过程。其定义如下：产生式右部任一文法符号V的继承属性仅依赖于下述两种属性值中的一种：i)产生式左部的继承属性；ii)产生式右部但位于V左边的符号的任何属性。产生式左部符号的综合属性仅依赖于下面的属性值中的一种：i)产生式左部符号的继承属性；ii)产生式右部符号（除自身外）的任意属性。,8.5属性文法,8.5.2S属性文法S属性文法也称为自下而上的属性翻译文法，它适用于指导自下而上的分析过程，其定义如下：全部非终结符的属性是综合属性；同一产生式中相同符号的各综合属性之间无相互依赖关系；如果q是某个产生式中文法符号V的继承属性，那么，属性q的值仅依赖于该产生式右部位于V左边的符号的属性。,8.6中间代码形式,中间代码形式是指用来表述源程序并与之等效的一种编码方式，可根据具体情况将它设计成各种形式。8.6.1逆波兰表示法特点：运算符直接写在其运算对象之后。不再有括号运算对象出现的次序未变，同一层中运算符则按其优先级出现求值过程简单,8.6中间代码形式,8.6.2逆波兰表示法的推广只要遵循将算符直接写在运算对象之后的原则，则可推广之。8.6.3四元式一般形式：运算符运算量1运算量2结果出现的次序是对应语法成分的计算次序可以随时引进临时工作变量，之间的联系通过临时变量进行的调整四元式的位置比较容易过多引进临时变量，导致存贮空间的浪费,8.6中间代码形式,8.6.4三元式一般形式：运算符运算量1运算量2出现的次序是对应语法成分的计算次序无需引进临时工作变量，用三元式的编号代替之，节省了存贮空间其中的编号代表某个三元式的位置编号和代表某个三元式的值之间的联系靠编号进行，因此，三元式的移动较困难，不便于优化,8.7属性翻译文法的应用,8.7.1综合属性与自下而上定值每个非终结符的属性值都是根据位于其下面那些符号的属性值来确定的，即按一种自下而上的方式来确定的。8.7.2继承属性和自上而下定值非终结符Vlist的属性值或者根据其上层非终结符的属性来确定或者根据产生式右部其它符号的属性来确定。这种属性值是根据自上而下方式确定的。,8.7属性翻译文法的应用,8.7.3布尔表达式到四元式的翻译作用：用做控制条件；计算逻辑值。文法：BBBBBB(B)idBropB其中，、为布尔（逻辑）运算符；rop为关系运算符（，=，）；id为布尔（逻辑）变量或布尔（逻辑）常数；BropB为关系表达式。布尔表达式的求值方法：通过逐步计算出各部分的值来计算整个表达式。利用布尔运算符的性质计算其值,8.7属性翻译文法的应用,8.7.4条件语句的翻译基本思路：先对定义它的文法进行改造，以便能在相应处添加上语义子程序；根据它的语义，设计出相应语义子程序的动作。,8.7属性翻译文法的应用,计算E若E之值为false，则转执行S1goto执行S2(后继语句),条件语句的语义,对应的抽象代码形成,8.7属性翻译文法的应用,由以上分析可将原文法改造成：,8.7属性翻译文法的应用,8.7.5迭代语句的翻译形式：SwhileEdoS用于翻译这类循环的属性翻译文法是WwhileWguad:=Nextguad;CWEdoCguad:=Wguad;Backpatch(Etrue,Nextguad);Cfalse:=EfalseSCS(1)Backpatch();Snext:=Cfals