第五章 语法制导的翻译.ppt

《第五章 语法制导的翻译.ppt》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。

1、第五章语法制导的翻译赵建华南京大学计算机系2010年3月介绍使用上下文无关文法引导语言的翻译CFG的非终结符号代表了语言的某个构造程序设计语言的构造由更小的构造组合而成一个构造的语义可以由小构造的含义综合而来比如：表达式x+y的类型由x、y的类型和运算符+决定。也可以从附近的构造继承而来比如：声明intx;中x的类型由它左边的类型表达式决定。语法制导定义和语法制导翻译语法制导定义：将文法符号和某些属性相关联，并通过语义规则来描述如何计算属性的值EE1+TE.code=E1.code

2、

3、T.code

4、

5、‘+’属性code代表中缀表达式的逆波兰表示，规则说明加法表达式的逆波兰表示由

6、两个分量的逆波兰表示并置，然后加上‘+’得到。语法制导翻译：在产生式体中加入语义动作，并在适当的时候执行这些语义动作EE1+T{print‘+’;}语法制导的定义（SDD）SDD是上下文无关文法和属性/规则的结合；属性和文法符号相关联，按照需要来确定各个文法符号需要哪些属性规则和产生式相关联对于文法符号X和属性a，我们用X.a表示分析树中的某个标号为X的结点的值。一个分析树结点和它的分支对应于一个产生式规则，而对应的语义规则确定了这些结点上的属性的取值。分析树和属性值(1)假设我们需要知道一个表达式的类型，以及对应代码将它的值存放在何处，我们就需要两个属性：type，place

7、；产生式规则：EE1+T语义规则：(假设只有int/float类型）E.type=if(E1.type==T.type)T.typeelsefloatE.place=newTempPlace();//返回一个新的内存位置；产生式规则：FidF.type=lookupIDTable(id.lexValue)->type;F.place=lookupIDTable(id.lexValue)->address;分析树和属性值(2)a+b*c的语法分析树以及属性值EET+TFidTF*Fididid.lexValue=aF.Type=FLOATF.Place=&aT.Type=FLO

8、ATT.Place=&aE.Type=FLOATE.Place=&aT.Type=INTT.Place=&tmpF.Type=INTF.Place=&cid.lexValue=cid.lexValue=b假设a,b,c是已经声明的全局变量，a的类型为FLOAT，b,c的类型为INT中间未标明的T和F的type和address都是INT和&b;E.Type=FLOATE.Place=&tmp2继承属性和综合属性综合属性(synthesizedattribute)：在分析树结点N上的非终结符号A的属性值由N对应的产生式所关联的语义规则来定义。通过N的子结点或N本身的属性值来定义继承属

9、性(inheritedattribute)：结点N的属性值由N的父结点所关联的语义规则来定义。依赖于N的父结点、N本身和N的兄弟结点上的属性值。不允许N的继承属性通过N的子结点上的属性来定义，但是允许N的综合属性依赖于N本身的继承属性。终结符号有综合属性（由词法分析获得），但是没有继承属性。SDD的例子目标：计算表达式行L的值（属性val）计算L的val值需要E的val值E的val值又依赖于E和T的val值…终结符号digit有综合属性lexval。S属性的SDD只包含综合属性的SDD称为S属性的SDD。每个语义规则都根据产生式体中的属性值来计算头部非终结符号的属性值。S属性的S

10、DD可以和LR语法分析器一起实现栈中的状态可以附加相应的属性值在进行归约时，按照语义规则计算归约得到的符号的属性值。语义规则不应该有复杂的副作用要求副作用不影响其它属性的求值没有副作用的SDD称为属性文法。语法分析树上的SDD求值（1）实践中很少先构造语法分析树再进行SDD求值但在分析树上求值有助于翻译方案的可视化，便于理解。注释语法分析树包含了各个结点的各属性值的语法分析树步骤：对于任意的输入串，首先构造出相应的分析树。给各个结点（根据其文法符号）加上相应的属性值按照语义规则计算这些属性值即可语法分析树上的SDD求值（2）按照分析树中的分支对应的文法产生式，应用相应的语义规则计

11、算属性值计算顺序问题：如果某个结点N的属性a为f(N1.b1,N2.b2,…,Nk.bk)，那么我们需要先算出N1.b1,N2.b2,…,Nk.bk的值。如果我们可以给各个属性值排出计算顺序，那么这个注释分析树就可以计算得到。S属性的SDD一定可以按照自底向上的方式求值。下面的SDD不能计算ABA.s=B.i；B.i=A.s+1；注释分析树的例子适用于自顶向下分析的SDD前面的表达式文法存在直接左递归，因此无法直接用自顶向下方法处理。消除左递归之后，我们无法直接使用属性val进