北京航空航天大学《编译原理》第9章 语法制导翻译技术.pdf

第九章 语法制导翻译技术 • 翻译文法(TG)和语法制导翻译 • 属性翻译文法(ATG) • 自顶向下语法制导翻译 • 翻译文法的自顶向下语法制导翻译 • 属性文法的自顶向下语法制导翻译 • 自底向上的语法制导翻译（自学） 北京航空航天大学计算机学院 11 9.0 本章导言 词法分析，语法分析：解决单词和语言成分的识别 及词法和语法结构的检查。语法结构可形式化地用 一组产生式来描述。给定一组产生式，能够很容易 地将其分析器构造出来。 本章要介绍的是语义分析和代码生成技术。 程序语言的语义形式化描述目前有三种基本描述方 法，即： • 操作语义 • 指称语义 • 公理语义 北京航空航天大学计算机学院 22 9.1 翻译文法和语法制导翻译 有上下无关文法G[E]: 1. E →E+T 4. T →F 2. E →T 5. F →(E) 3. T →T*F 6. F →i 此文法是一个中缀算术表达式文法 翻译的任务是: 中缀表达式 逆波兰表示 a+b*c abc*+ 假如翻译任务是要将中缀表达式简单变换为波兰后 缀表示，只需在上述文法中插入相应的动作符号。 北京航空航天大学计算机学院 33 1. E →E+T 4. T →F 2. E →T 5. F →(E) 3. T →T*F 6. F →i 1. E →E+T@+ 4. T →F 2. E →T 5. F →(E) 3. T →T*F @* 6. F →i@i 其中： @+,@*,@i 为动作符号。@为动作符号标记，后面为字符串。 在本例中，其对应语义子程序的功能是要输出打印动作 符号标记后面的字符串。 所以，产生式1：E →E+T@+ 的语义是分析E, + 和T ，输出+ 产生式6：F →i @ i的语义是分析i ，输出i 北京航空航天大学计算机学院 44 下面给出输入文法和翻译文法的概念： 输入文法：未插入动作符号时的文法。 由输入文法可以通过推导产生输入序列。 翻译文法：插入动作符号的文法。 由翻译文法可以通过推导产生活动序列。 输入序列 动作序列 北京航空航天大学计算机学院