[第五章++语法制导翻译..ppt

第五章 语法制导翻译 5.4 ~ 5.5 5.4 语法制导的翻译模式(Translation Scheme) 语法制导翻译模式（SDT）是拓广的CFG， 在文法中嵌入语义动作，语义动作写在花括号“{}”里，可以出现在产生式右部适当位置。 当归约出产生式右部的某个非终结符号后，就执行紧接在该非终结符号右边的语义动作。 我们希望SDT能够在语法分析的同时进行，无需构造好分析树。这里讨论两类： 基础文法是LR，SDD是S-attributed； 基础文法是LL，SDD是L-attributed。 5.4.2 后缀SDT的语法分析实现 A ? X Y Z 例5.15 显式操作语法分析栈 5.4.3 产生式内部带语义动作的SDT B ? X {a} Y LR:归约出X之后立即执行{a} LL: Y之前执行{a} 例，翻译为后缀表达式(第2章的例子) L ? E n E ? E1+ T {print(‘+’)} E ? T T ? T1* F {print(‘*’)} T ? F F ? (E) F ? digit {print(digit.lexval)} 例5.16 翻译为前缀表达式 L ? E n E ? {print(‘+’)} E1+ T E ? T T ? {print(‘*’)} T1* F T ? F F ? (E) F ? digit {print(digit.lexval)} 嵌入动作的分析树：3*5+4 例5.12 中缀表达式翻译成为后缀形式 修改后的翻译模式 5.4.4 从SDT中删除左递归 例5.17 带左递归的文法的翻译模式。 E ? E1 + T { print(‘+’); } E ? T 转换为： E ? TR R ? + { print(‘+’); } R R ? ? 例：一个一般化的例子 5.4.5 L属性定义的SDT 如何将语义动作嵌入产生式右部的适当位置？ 2. 同时存在综合属性和继承属性，建立翻译模式的必要条件： 产生式右部符号的继承属性必须在这个符号以前的动作中计算出来； 一个动作不能引用该动作右边符号的综合属性； 产生式左边非终结符号的综合属性只有在它所引用的所有属性都计算出来以后才能计算。计算这种属性的动作通常可以放在产生式右端的末尾。 例5.18数学排版语言的翻译模式片断。 图5.22 盒子的大小和高度的语法制导定义 关于属性说明 继承属性ps, point size is used to set the text within a box. Assume ps = 10, and the subscript box has the smaller point size shrink 综合属性： ht ： height dp ： depth E sub 1.val 的推导过程(忽略二义性问题) 翻译模式 如何消除二义性? 5.5 自顶向下的翻译实现L属性定义 建立注释语法分析树 构造语法分析树，加入动作，按照前序顺序执行 使用递归下降的语法分析器，在预测分析的过程中实现L属性定义。 5.5.1 从翻译模式中消除左递归 经过转换的带有右递归文法的翻译模式 表达式9-5+2的计算 例5.15 转换后的构造语法树的翻译模式 5.5.2 预测翻译器的设计算法5.1 预测语法制导翻译器的构造 算法5.1 预测语法制导翻译器的构造 例5.16 图5.28中的文法是LL(1)文法，适于自顶向下的分析。 从文法中非终结符号的属性，可以得到函数E，R和T的参数和返回值的类型。由于E和T没有继承属性，所以它们不含有参数。 R的翻译器代码基于产生式 R ? addop T R |?的语法分析过程： 5.6 自底向上计算继承属性 与自顶向下的翻译不同 综合属性——在归约时执行计算动作 继承属性——关键问题 5.6.1 删除嵌入在翻译模式中的动作 语义动作如何执行 希望在归约时执行 所有的动作都出现在产生式的末尾 可以采用在翻译模式中插入标记非终结符号的方法。 例：引入标记非终结符号M,N，改写翻译模式： 5.6.2 分析栈中的继承属性 继承属性的值无非有两种来源 一开始就存在 来自综合属性 继承属性来自综合属性，其值由复写规则决定，且继承属性的位置固定的情形。 翻译模式 图5.33 当L的右边符号被归约时，T正好在其右边的符号的下面 图5.34 T.type的值在L.in处被使用 5.6.3 模拟继承属性的计算 这两种情况如何处理？ 继承属性的存放位置不能事先预知 继承属性需要通过计算得到 例5.18　一个不能预知属性值在栈中所放位置的例子 通过标记非终结符M复写属性的值 标记非终结符也可以用来模拟不是复写规则的语义规则 例5.19 使用三个标记非