第五章语法制导的翻译 赵建华 南京大学计算机系 2010年3月
第五章 语法制导的翻译 赵建华 南京大学计算机系 2010年3月
介绍 使用上下文元关文法引导语言的翻译 CFG的非终结符号代表了语言的某个构造 程序设计语言的构造由更小的构造组合而成 一个构造的语义可以由小构造的含义综合而來 比如:表达式x+y的类型由X、y的类型和运算待+决 定。 也可以从附近的构造继承而来 °比如:声明ntx;中x的类型由它左边的类型表达式 决定
介绍 • 使用上下文无关文法引导语言的翻译 – CFG的非终结符号代表了语言的某个构造 – 程序设计语言的构造由更小的构造组合而成 – 一个构造的语义可以由小构造的含义综合而来 • 比如：表达式x+y的类型由x、y的类型和运算符+决 定。 – 也可以从附近的构造继承而来 • 比如：声明int x;中x的类型由它左边的类型表达式 决定
语法制导定义和语法制导翻译 ·语法制导定义: 将文法符号和某些属性相关联 并通过语义规则來描述如何计算属性的值 E→E1+T E code=E. codelL code 一属性code代表中缀表达式的逆波兰表示,规则说刂 加法表达式的逆波兰表示由两个分量的逆波兰表示 并置,然后加上“得到。 ·语法制导翻译 在产生式体中加入语义动作,并在适当的时候执行 这些语义动作 E→E1+T{ prnt“+
语法制导定义和语法制导翻译 • 语法制导定义： – 将文法符号和某些属性相关联， – 并通过语义规则来描述如何计算属性的值 – E→E1+T E.code=E1 .code||T.code || ‘+’ – 属性code代表中缀表达式的逆波兰表示，规则说明 加法表达式的逆波兰表示由两个分量的逆波兰表示 并置，然后加上‘+’得到。 • 语法制导翻译： – 在产生式体中加入语义动作，并在适当的时候执行 这些语义动作 – E→E1+T {print ‘+’;}
语法制导的定义(SDD) SDD是上下文无关文法和属性/规则的结合; 属性和文法符号相关联。按照需要来确定各个 文法符号需要哪些属性 规则和产生式相关联 ·对于丈法符号Ⅹ和属性a.我们用Ⅹa表示分 析树中的某个标号为Ⅹ的结点的值。 一个分析树结点和它的分支对应于一个产 生式规则,而对应的语义规则确定了这些 结点上的属性的取值
语法制导的定义（SDD） • SDD是上下文无关文法和属性/规则的结合； – 属性和文法符号相关联，按照需要来确定各个 文法符号需要哪些属性 – 规则和产生式相关联 • 对于文法符号X和属性a，我们用X.a表示分 析树中的某个标号为X的结点的值。 • 一个分析树结点和它的分支对应于一个产 生式规则，而对应的语义规则确定了这些 结点上的属性的取值
分析树和属性值() 假设我们需要知道一个表达式的类型。以及对 应代码将它的值存放在何处,我们就需要两个 属性;type, place; 产生式规则:E→>E1+T 语义规则:(假设只有 int/float类型) E type = if(El. type=--=T type) T type else float E place= new Tempplaceo;/回一个新的内存位置; 产生式规则:F→id F type= lookup Table(id lex value)->type F place lookupldTable(id lex value)->address
分析树和属性值(1) • 假设我们需要知道一个表达式的类型，以及对 应代码将它的值存放在何处，我们就需要两个 属性：type，place； • 产生式规则：E→E1+T • 语义规则：(假设只有int/float类型） – E.type = if (E1 .type==T.type) T.type else float – E.place = newTempPlace(); //返回一个新的内存位置； • 产生式规则：F→id – F.type = lookupIDTable(id.lexValue)->type; – F.place = lookupIDTable(id.lexValue)->address;
分析树和属性值(2) EType= FLoat E EPlace=&tmp2 EType= FLOAT TType= INT E Place= &a E T Place =&tmp TType= FLOAT T F FType=INT T Place= &a E Place =&c 假设abc是已经声明的 FType= FLOAT F idid. evalue=c全局变量,a的类型为 E Place= &a FLOAT.bc的类型为 d lexvalue=a id INT id idlexvalue=b 中间未标明的T和F的 type和 address都是NT和 ·a+bc的语法分析树以及属性值 &b
分析树和属性值(2) • a+b*c的语法分析树以及属性值 E E + T T F id T * F F id id.lexValue=a id F.Type = FLOAT F.Place = &a T.Type = FLOAT T.Place = &a E.Type = FLOAT E.Place = &a T.Type = INT T.Place = &tmp F.Type = INT F.Place = &c id.lexValue=c id.lexValue=b 假设a,b,c是已经声明的 全局变量，a的类型为 FLOAT，b,c的类型为 INT 中间未标明的T和F的 type和address都是INT和 &b; E.Type = FLOAT E.Place = &tmp2
继承属性和综合属性 ·综合属性( synthesized attribute):在分析树结点N上 的非终结符号A的属性值由N对应的产生式所关联的 语义规则来定义。 通过N的子结点或N本身的属性值来定义 继承属性( inherited attribute):结点N的属性值由N的 父结点所关联的语义规则来定义。 依赖于N的父结点、N本身和N的兄弟结点上的属性值。 不允许N的继承属性通过N的子结点上的属性來定义, 但是允许N的综合属性依赖于N本身的继承属性。 终结符号有综合属性(由词法分析获得),但是没 有继承属性
继承属性和综合属性 • 综合属性(synthesized attribute)：在分析树结点N上 的非终结符号A的属性值由N对应的产生式所关联的 语义规则来定义。 – 通过N的子结点或N本身的属性值来定义 • 继承属性(inherited attribute)：结点N的属性值由N的 父结点所关联的语义规则来定义。 – 依赖于N的父结点、N本身和N的兄弟结点上的属性值。 • 不允许N的继承属性通过N的子结点上的属性来定义， 但是允许N的综合属性依赖于N本身的继承属性。 • 终结符号有综合属性（由词法分析获得），但是没 有继承属性
SDD的例子 产生式 语义规则 1)L→En L. val= e.val 2)E+E1 +T E.val=E1. al+ Tval 3)E→T E.val=Tval 4)T→T1*F|Tal=Ti,al×Fal 5)T→F Tval= F. val )F→(E) F.val= E. val 7)F→ digit F.val= digit.lexval 目标:计算表达式行的值(属性val) ·计算L的va值需要E的va值 E的va值又依赖于E和T的val值 终结号dgi有综合属性 clexval o
SDD的例子 • 目标：计算表达式行L的值（属性val） • 计算L的val值需要E的val值 • E的val值又依赖于E和T的val值 • … • 终结符号digit有综合属性lexval
S属性的SDD 只包含综合属性的SDD称为S属性的SDD。 每个语义规则都根据产生式体中的属性值来计算头 部非终结符号的属性值。 S属性的SDD可以和R语法分析器一起实现 栈中的状态可以附加相应的属性值 在进行归约时,按照语义规则计算归约得到的符号 的属性值。 语义规则不应该有复条的副作用 要求副作用不影响其它属性的求值 没有副作用的SDD称为属性文法
S属性的SDD • 只包含综合属性的SDD称为S属性的SDD。 – 每个语义规则都根据产生式体中的属性值来计算头 部非终结符号的属性值。 • S属性的SDD可以和LR语法分析器一起实现 – 栈中的状态可以附加相应的属性值 – 在进行归约时，按照语义规则计算归约得到的符号 的属性值。 • 语义规则不应该有复杂的副作用 – 要求副作用不影响其它属性的求值 – 没有副作用的SDD称为属性文法
语法分析树上的SDD求值(1) ·实践中很少先构造语法分析树再进行SDD求值 ·但在分析树上求值有助于翻译方案的可视化 便于理解。 注释语法分析树 包含了各个结点的各属性值的语法分析树 步驟 对于任意的输入串,首先构造出相应的分析树。 给各个结点(根据其文法符号)加上相应的属性值 按照语义规则讣算这些属性值即可
语法分析树上的SDD求值（1） • 实践中很少先构造语法分析树再进行SDD求值 • 但在分析树上求值有助于翻译方案的可视化， 便于理解。 • 注释语法分析树 – 包含了各个结点的各属性值的语法分析树 • 步骤： – 对于任意的输入串，首先构造出相应的分析树。 – 给各个结点（根据其文法符号）加上相应的属性值 – 按照语义规则计算这些属性值即可