南京大学：《编译原理 Principles and Techniques of Compilers》课程教学电子教案（课件讲义）第五章 语法制导的翻译

第五章语法制导的翻译 许畅 南京大学计算机系 2022年春季 版权所有南京大学计算机科学与技术系许畅2022春季版

许畅 南京大学计算机系 2022年春季 第五章 语法制导的翻译 版权所有 南京大学计算机科学与技术系 许畅 2022春季版 南大编译许畅

介绍 。使用上下文无关文法引导语言的翻译 CFG的非终结符号代表了语言的某个构造 程序设计语言的构造由更小的构造组合而成 一个构造的语义可以由小构造的含义综合而来 比如：表达式x+y的类型由x、y的类型和运算符+决定 也可以从附近的构造继承而来 比如：声明ntx中x的类型由它左边的类型表达式决定 2

介绍 • 使用上下文无关文法引导语言的翻译 – CFG的非终结符号代表了语言的某个构造 – 程序设计语言的构造由更小的构造组合而成 – 一个构造的语义可以由小构造的含义综合而来 • 比如：表达式x + y的类型由x、y的类型和运算符+决定 – 也可以从附近的构造继承而来 • 比如：声明int x中x的类型由它左边的类型表达式决定 2 南大编译许畅

语法制导定义和语法制导翻译 语法制导定义 将文法符号和某些属性相关联，并通过语义规则来描 述如何计算属性的值 。E今E1+T E.code E.code I T.code I+ 属性cod代表表达式的逆波兰表示，规则说明加法表达 式的逆波兰表示由两个分量的逆波兰表示并置，然后 加上'+'得到 ·语法制导翻译 在产生式体中加入语义动作，并在适当时候执行动作 ·E→E1+T print '+' 3

语法制导定义和语法制导翻译 • 语法制导定义 – 将文法符号和某些属性相关联，并通过语义规则来描 述如何计算属性的值 • E → E1 + T E.code = E1 .code || T.code || '+' – 属性code代表表达式的逆波兰表示，规则说明加法表达 式的逆波兰表示由两个分量的逆波兰表示并置，然后 加上'+'得到 • 语法制导翻译 – 在产生式体中加入语义动作，并在适当时候执行动作 • E → E1 + T { print '+'; } 3 南大编译许畅

语法制导的定义(SDD) Syntax-Directed Definition(SDD)是上下文无 关文法和属性/规则的结合 属性和文法符号相关联，按照需要来确定各个文法符 号需要哪些属性 规则和产生式相关联 对于文法符号X和属性a,我们用X.表示分析树中 某个标号为X的结点的值 一个分析树结点和它的分支对应一个产生式规则，而 对应的语义规则确定了这些结点上属性的取值和计算 4

语法制导的定义 (SDD) • Syntax-Directed Definition (SDD) 是上下文无 关文法和属性/规则的结合 – 属性和文法符号相关联，按照需要来确定各个文法符 号需要哪些属性 – 规则和产生式相关联 • 对于文法符号X和属性a，我们用X.a表示分析树中 某个标号为X的结点的值 – 一个分析树结点和它的分支对应一个产生式规则，而 对应的语义规则确定了这些结点上属性的取值和计算 4 南大编译许畅

分析树和属性值(1) 假设需要知道一个表达式的类型，以及对应代码 将它的值存放的内存地址 我们需要两个属性：type,place 产生式规则：E→E1+T 假设只有int/loat类型 E.type=if (E.type ==T.type)T.type else float; E.place=newTempPlace().;/∥返回一个新的内存位置 产生式规则：F→d F.type =lookupIDTable(id.lexValue)->type; F.place lookupIDTable(id.lexValue)->address; 5

分析树和属性值 (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; 5 南大编译许畅

分析树和属性值(2) ,输入a+b*c的语法分析树以及属性值 E.type=float EE.place=&tmp2 (1)假设a,b,c是已声 E.type float T.type=int 明的全局变量，a E.place=&a E T T.place &tmp1 的类型为float, T.type float T T 米 F.type=int b和c的类型为int T.place &a F.place =&c (2)中间未标明的T F.type=float F id 和F的type和place F.place=&a id.lexValue c 是int和&b id id id.lexValue a id.lex Value =b 6

分析树和属性值 (2) • 输入a + b * c的语法分析树以及属性值 6 (1) 假设a, b, c是已声 明的全局变量，a 的类型为float， b和c的类型为int (2) 中间未标明的T 和F的type和place 是int和&b E E + T T F id T * F F id id id.lexValue = a F.type = float F.place = &a T.type = float T.place = &a E.type = float E.place = &a T.type = int T.place = &tmp1 F.type = int F.place = &c id.lexValue = c id.lexValue = b E.type = float E.place = &tmp2 南大编译许畅

综合属性和继承属性 综合属性(Synthesized Attribute) 结点N的属性值由W的产生式所关联的语义规则来定义 通过N的子结点或N本身的属性值来定义 继承属性(Inherited Attribute) 结点N的属性值由N的父结点所关联的语义规则来定义 依赖于N的父结点、N本身和N的兄弟结点上的属性值 。几条约束 不允许N的继承属性通过N的子结点上的属性来定义， 但允许N的综合属性依赖于N本身的继承属性 终结符号有综合属性（来自词法分析），但无继承属性 7

综合属性和继承属性 • 综合属性 (Synthesized Attribute) – 结点N的属性值由N的产生式所关联的语义规则来定义 – 通过N的子结点或N本身的属性值来定义 • 继承属性 (Inherited Attribute) – 结点N的属性值由N的父结点所关联的语义规则来定义 – 依赖于N的父结点、N本身和N的兄弟结点上的属性值 • 几条约束 – 不允许N的继承属性通过N的子结点上的属性来定义， 但允许N的综合属性依赖于N本身的继承属性 – 终结符号有综合属性 (来自词法分析)，但无继承属性 7 南大编译许畅

SDD的例子 计算表达式行L的值（属性val) 。 计算L的val值需要E的val值，E的val值又依赖于E1 和T的val值.. ·终结符号digit有综合属性lexval 产生式 语义规则 1) L→En L.val E.val 2) E→E1+T E.val E1.val+T.val 3) E→T E.val=T.val 4) T→T1*F T.val=T1.val×F.val 5) T→F T.val F.val 6) F→(E) F.val E.val 7) F→digit F.val digit.lexval 8

SDD的例子 • 计算表达式行L的值 (属性val) • 计算L的val值需要E的val值，E的val值又依赖于E1 和T的val值… • 终结符号digit有综合属性lexval 8 南大编译许畅

S属性的SDD ·只包含综合属性的SDD称为S属性的SDD 每个语义规则都根据产生式体中的属性值来计算头部 非终结符号的属性值 ·S属性的SDD可以和LR语法分析器一起实现 栈中的状态/文法符号可以附加相应的属性值 归约时，按照语义规则计算归约得到的符号的属性值 。语义规则不应该有复杂的副作用 要求副作用不影响其它属性的求值 没有副作用的SDD称为属性文法 9

S属性的SDD • 只包含综合属性的SDD称为S属性的SDD – 每个语义规则都根据产生式体中的属性值来计算头部 非终结符号的属性值 • S属性的SDD可以和LR语法分析器一起实现 – 栈中的状态/文法符号可以附加相应的属性值 – 归约时，按照语义规则计算归约得到的符号的属性值 • 语义规则不应该有复杂的副作用 – 要求副作用不影响其它属性的求值 – 没有副作用的SDD称为属性文法 9 南大编译许畅

语法分析树上的SDD求值(1) 实践中很少先构造语法分析树再进行SDD求值， 但在分析树上求值有助于翻译方案的可视化，便 于理解 注释语法分析树 包含了各个结点的各属性值的语法分析树 步骤 对于任意的输入串，首先构造出相应的分析树 给各个结点（根据其文法符号）加上相应的属性 按照语义规则计算这些属性的值 10

语法分析树上的SDD求值 (1) • 实践中很少先构造语法分析树再进行SDD求值， 但在分析树上求值有助于翻译方案的可视化，便 于理解 • 注释语法分析树 – 包含了各个结点的各属性值的语法分析树 • 步骤 – 对于任意的输入串，首先构造出相应的分析树 – 给各个结点 (根据其文法符号) 加上相应的属性 – 按照语义规则计算这些属性的值 10 南大编译许畅