第五章语法制导的翻译 赵建华 南京大学计算机系 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;