sun编译原理第5章语法制导翻译技术和中间代码生成(第19.ppt

2020 3 11 信息学院孙丽云 1 5 1概述 语义分析的任务 首先编译程序审查每个语法结构的静态语义 如果静态语义正确 再生成中间代码 词法分析 分析的预备阶段 输出是单词符号序列 语法分析 分析的主要阶段 输出是语法树 但这样还不能完全确定源程序的正确性 也没有获得翻译时所需的所有信息 注意 有的编译程序不生成中间代码而直接生成实际的目标代码 2020 3 11 信息学院孙丽云 2 5 2属性文法 词法规则的描述工具 语法规则的描述工具 语义规则的常用描述工具 属性文法 正规文法或正规式 上下文无关文法 属性是编程语言结构的任意特性 如 变量的数据类型表达式的值存储器中变量的位置程序的目标代码数的有效位数 基本概念 X a是与X关联的a的值 X是一个文法符号 a是X的一个属性 如 X type X的类型 X place X的存储位置 X val X的值 2020 3 11 信息学院孙丽云 3 属性文法 即 以语法分析为基础 对应文法的每个产生式 确定相应的语义规则 属性文法是在上下文无关文法的基础上 允许每个文法符号X 终结符或非终结符 根据处理的需要 定义与X相关联的属性 一个属性文法形式上定义为一个三元组AG AG G V E 其中G表示一个上下文无关文法 V表示属性的有穷集 E表示属性的断言或谓词的有穷集 其中每个断言与文法某产生式相关联 例 E m n 则与该产生式相关联的断言为 E val m val n val 2020 3 11 信息学院孙丽云 4 属性文法 一般地 将属性文法写成表格形式 每个文法规则用属性等式的集合或相应规则的语义规则列出 注意 文法规则中同一产生式中某符号出现多次必须使用下标进行区分 例 number1 number2digit 1 已知无符号数文法如下 请改写成值属性文法 number numberdigit digitdigit 0 1 2 3 4 5 6 7 8 9 例如 2020 3 11 信息学院孙丽云 6 grammarrulesemanticrulesexp1 exp2 termexp1 val exp2 val term valexp1 exp2 termexp1 val exp2 val erm valexp termexp val term valterm1 term2 factorterm1 val term2 val factor valterm factorterm val factor valfactor exp factor val exp valfactor numberfactor val number val 2 简单的整数算术表达式文法如下 请改写成值属性文法 exp exp term exp term termterm term factor factorfactor exp number 解 2020 3 11 信息学院孙丽云 7 1 简单的整数算术表达式文法如下 请改写成值属性文法 E E T TT T F FF E I2 已知无符号数文法如下 请改写成值属性文法 N ND DD 0 1 2 3 4 5 6 7 8 9 练习 2020 3 11 信息学院孙丽云 8 使用属性文法来计算属性值 即把属性等式转化成计算规则 可用依赖图 或称相关图 来决定属性值的计算顺序 属性的计算 关键 如何决定属性值的计算顺序 2020 3 11 信息学院孙丽云 9 例 已知无符号数属性文法 请画出属性等式及345的依赖图 grammarrulesemanticrulesnumber1 number2digitnumber1 val number2 val 10 digit valnumber digitnumber val digit val 解 1 属性等式number1 val number2 val 10 digit val文法规则number1 number2digit的依赖图 2 属性等式number val digit val文法规则number digit的依赖图 2020 3 11 信息学院孙丽云 10 依赖图以属性等式为最小结构单位 一个文法的依赖图就是全部属性等式依赖图的总和 2020 3 11 信息学院孙丽云 11 例2 已知无符号数属性文法 请画出属性等式及floatx y的依赖图 grammarrulesemanticrulesdecl typevar listvar list dtype type dtypetype inttype dtype integertype floattype dtype realvar list1 id var list2id dtype var list1 dtypevar list2 dtype var list1 dtypevar list idid dtype var list dtype 属性等式id dtype var list dtype文法规则var list id的依赖图 id dtype var list dtype 2020 3 11 信息学院孙丽云 13 依据依赖图 利用拓扑排序算法 可按顺序计算出字符串floatx y中各属性的值 字符串floatx y的依赖图 2020 3 11 信息学院孙丽云 14 属性分为两类 1 合成属性 或称综合属性 2 继承属性 属性的分类 1 一个属性是合成的 如果在语法树中它所有的相关都从子节点指向父节点 例 2020 3 11 信息学院孙丽云 15 2 一个属性如果不是合成的 则称作继承属性 属性的分类 例 2020 3 11 信息学院孙丽云 16 5 3语法制导翻译概述 语义分析阶段的2个主要任务 1 分析语言的含义 2 用一种中间代码将这种含义描述出来 目前常用过的语义分析方法 语法制导翻译法 所谓语法制导翻译法就是在语法分析过程中 随着分析的逐步进展 根据相应文法的每一规则所对应的语义子程序进行翻译的方法 语法制导翻译法可分为自下向上语法制导翻译和自上向下语法制导翻译 2020 3 11 信息学院孙丽云 17 语法分析时属性的计算 每步归约时 计算相应的属性值 在分析栈中使用一个附加的域来存放综合属性值 例 对3 4 5进行LR分析的过程进行属性值的计算 E E E E E E E E number 语法规则语义规则E1 E2 E3E1 val E2 val E3 valE1 E2 E3E1 val E2 val E3 valE1 E2 E3E1 val E2 val E3 valE1 E2 E1 val E2 valE numberE val number val 解 例 对3 4 5进行LR分析并进行属性值的计算 E E E E E E E E number 解 Parsingstackinputparsingactionvaluestacksemanticaction1 3 4 5 Shift 2 n 4 5 ReduceE n nE val n val3 E 4 5 Shift 34 E 4 5 Shift 3 5 E n 5 ReduceE n 3 nE val n val6 E E 5 ReduceE E E 3 4E1 val E2 val E3 val7 E 5 Shift 128 E 5 Shift 12 9 E n ReduceE n 12 nE val n val10 E E ReduceE E E 12 5E1 val E2 val E3 val11 E 17 2020 3 11 信息学院孙丽云 19 例 已知无符号数文法如下 请改写成值属性文法 并对345进行语义分析 number numberdigit digitdigit 0 1 2 3 4 5 6 7 8 9 文法规则语义规则number1 number2digitnumber digitdigit 0digit 1 digit 8digit 9 number1 val number2 val 10 digit val number val digit val digit val 0 digit val 1 digit val 8 digit val 9 2020 3 11 信息学院孙丽云 20 number val 3 10 4 34 number val 3 digit val 4 number val 34 10 5 345 digit val 5 digit val 3 3 4 5 语法树表示345的属性等式的计算 采用自底向上的语法分析 2020 3 11 信息学院孙丽云 21 例 已知简单的整数算术表达式文法如下 请改写成值属性文法 并对 34 3 42进行语义分析 exp exp term exp term termterm term factor factorfactor exp number 2020 3 11 信息学院孙丽云 22 term val 31 factor val 31 term val 31 42 1302 factor val 42 exp val 34 3 31 number val 42 theparsetree 34 3 42 exp val 1302 exp val 34 term val 34 factor val 34 term val 3 factor val 3 number val 3 number val 34 2020 3 11 信息学院孙丽云 23 语法制导翻译举例 1 有一属性文法为 1 P bQb print 1 2 Q cR print 2 3 Q a print 3 4 R Qad print 4 输入串为bccaadadb 且采用自底向上语法分析方法时 则输出序列是 2 试给出下列文法的适合自下而上翻译的语义动作 使得当输入串是aacbb时 其输出串是12020 1 A aB 2 A c 3 B Ab 342421 print 1 print 2 print 0 2020 3 11 信息学院孙丽云 24 词法规则的描述工具 语法规则的描述工具 语义规则的常用描述工具 属性文法 正规文法或正规式 上下文无关文法 小结 属性文法是在上下文无关文法的基础上 允许每个文法符号X 终结符或非终结符 根据处理的需要 定义与X相关联的属性 一般地 将属性文法写成表格形式 每个文法规则用属性等式的集合或相应规则的语义规则列出 2020 3 11 信息学院孙丽云 25 例 简单表达式文法 E E E E E E E E number 语法规则语义规则E1 E2 E3E1 val E2 val E3 valE1 E2 E3E1 val E2 val E3 valE1 E2 E3E1 val E2 val E3 valE1 E2 E1 val E2 valE numberE val number val 该文法对应的属性文法为 2020 3 11 信息学院孙丽云 26 小结 属性分为两类 1 合成属性 或称综合属性 2 继承属性 目前常用过的语义分析方法 语法制导翻译法 在语法分析过程中 随着分析的逐步进展 根据相应文法的每一规则所对应的语义子程序进行翻译的方法 2020 3 11 信息学院孙丽云 27 语法制导翻译举例 有一属性文法为 1 P bQb print 1 2 Q cR print 2 3 Q a print 3 4 R Qad print 4 输入串为bab 且采用自底向上语法分析方法时 则输出序列是 31 2020 3 11 信息学院孙丽云 28 例 利用下列属性文法对 3 6 9进行语义分析 语法规则语义规则E1 E2 E3E1 val E2 val E3 valE1 E2 E3E1 val E2 val E3 valE1 E2 E3E1 val E2 val E3 valE1 E2 E1 val E2 valE numberE val number valnumber 0number val 0 number 9number val 9 语法制导翻译举例 2020 3 11 信息学院孙丽云 29 综合练习 给出文法G S S SaA AA AbB BB cSd e 1 试证实AacAd是文法G S 的一个句型 2 请写出该句型的所有短语 直接短语以及句柄 3 为文法G S 的相应产生式写出语义动作 使句型AacAd经该翻译方案后 输出为11435 2020 3 11 信息学院孙丽云 30 5 4中间语言 所谓中间代码形式是指用来描述源程序并与之等效的一种编码方式 可根据具体情况将它设计成各种形式 一般来说 对于一个多遍扫描的编译程序 越到后面的阶段 所产生的中间代码越接近于机器代码 常用的中间代码有逆波兰式表示 后缀式 三元式 树形 抽象的语法树 四元式 三地址码表示等 2020 3 11 信息学院孙丽云 31 逆波兰式 逆波兰表示法是把运算量 操作数 写在前面 把运算符写在后面 又称为后缀表示法 特征 操作符在前 操作数紧随其后 无需用括号限制运算的优先级和结合性 且求表达式值较中缀表达式方便 例 将 a b a c d x y 翻译成逆波兰表示 并求出当a 3 b 7 c 1 d 2 x 4 y 6时该表达式的值 程序语句也可用逆波兰式表示 练习 求 b c e b c f的逆波兰式 2020 3 11 信息学院孙丽云 32 三元式由3个域和一个序号组成 i op arg1 arg2 其中op为运算符 arg1 arg2是2个运算对象 例 算术表达式的三地址码x yopz的三元式为 1 op y z 2 x 1 三元式 三元式的运算结果由每一个三元式前的序号指示 2020 3 11 信息学院孙丽云 33 例 赋值语句a c d c d 相应的三元式代码为 1 c d 2 c d 3 1 2 3 a 3 三元式举例 三元式出现的先后顺序和表达式各部分的计值顺序是一致的 2020 3 11 信息学院孙丽云 34 在三元式代码表的基础上另设一张表 该表按运算的次序列出相应三元式在表中的位置 这张表称为间接码表 三元式表只记录不同的三元式语句 间接码表表示由这些语句组成的运算次序 间接三元式 例 赋值语句a c d c d 三元式代码为 相应的间接三元式代码由三元式表和间接码表组成 三元式表 1 c d 2 1 1 3 a 2 间接码表 1 1 2 3 1 c d 2 c d 3 1 2 4 a 3 2020 3 11 信息学院孙丽云 35 树形表示 树形表示法可以很方便的表示一个表达式或语句 其中 一个表达式中的简单变量或常数的树形表示就是该变量或常数自身 简单表达式的树形表示见课本P109图5 8树形结构一般表示成二叉树的形式 练习 求a b c e b c f的树形表示 2020 3 11 信息学院孙丽云 36 四元式 四元式是具有四个域的记录结构 这四个域为 op arg1 arg2 result 其中op为运算符 arg1 arg2为运算对象 result为编译程序为存放中间运算结果引进的临时变量 例 赋值语句a b c d 相应的四元式代码为 1 c d t1 2 b t1 t2 3 t2 a 四元式出现的顺序与表达式计算的顺序一致 四元式之间的联系是通过临时变量实现的 2020 3 11 信息学院孙丽云 37 三地址码 三地址码的形式定义为 X aopb其中 X a和b为变量名 常量或编译时产生的临时变量 op为运算符 注意 三地址语句中等号右边只含有一个运算符 因此多个运算符组成的表达式必须用三地址语句序列来表示 如 x y z的三地址码序列为 1 t1 y z 2 t2 x t1其中t1和t2是编译时产生的临时变量 三地址码是语法树的一种线性表示 2020 3 11 信息学院孙丽云 38 综合练习 求a b c e的各种中间语言表示形式 1 逆波兰式2 三元式3 间接三元式4 树形表示5 四元式6 三地址代码 2020 3 11 信息学院孙丽云 39 练习 1 四元式之间的联系是通过 实现的 2 间接三元式表示法的优点为 A 采用间接码表 便于优化处理B 节省存储空间 不便于表的修改C 便于优化处理 节省存储空间D 节省存储空间 不便于优化处理 临时变量 A 2020 3 11 信息学院孙丽云 40 5 5自下而上语法制导翻译 自下而上语法制导翻译方法是在自下而上的语法分析过程中逐步实现语义规则的方法 自下而上翻译的特点 1 当栈顶形成句柄执行归约时 调用相应的语义动作 2 语法分析栈与语义分析栈同步操作 2020 3 11 信息学院孙丽云 41 表达式中间代码生成 1 逆波兰式的生成 算术表达式的逆波兰式的生成只需对其抽象语法树进行后序遍历即可 例 求 b c e的逆波兰式可利用语法分析结果的抽象语法树获得 考虑若求a b c e b c f的逆波兰式 2020 3 11 信息学院孙丽云 42 表达式中间代码生成 Tn是编译过程中的临时变量 用以存储中间结果 2 表达式的四元式变换如下 例 求a b c e b c f的四元式 2020 3 11 信息学院孙丽云 43 1 表达式 A B C D 的逆波兰表示为 2 写出赋值语句x a b c d的四元式序列 课后练习 2020 3 11 信息学院孙丽云 44 一 中间代码有如下形式 表达式中间代码生成小结 1 逆波兰式2 三元式3 间接三元式4 树形表示5 四元式6 三地址代码 二 表达式 b c e b c f的中间代码 2020 3 11 信息学院孙丽云 45 if语句中间代码生成 if语句的形式 if E S1elseS2 这里的表达式E一般是布尔表达式 或逻辑表达式 if语句的核心操作不是计算 而是转移 包括条件转移与无条件转移 因此if语句翻译成中间代码时 变成对布尔表达式的判断与转移组合 所生成的四元式中间代码由两条基本语句组成 表示如果a非零则转移到地址L1 表示无条件转移到地址L2 if语句中间代码生成 if语句有两种形式 形式1 if E S 计算E的四元式值并存入T jnz T L jp next L S的四元式 next 后续程序四元式 中间代码生成过程 例 求if a b x x 1 y y 1 的四元式序列 流程图 N Y 形式2 if E S1elseS2 if语句中间代码生成 E的四元式 值存入T next 后续程序四元式 中间代码生成过程 例 求if a b x x 1 elsex x 1 y 1 的四元式序列 N Y 2020 3 11 信息学院孙丽云 48 if语句中间代码生成 if语句四元式生成过程中 有一个关键技术问题 如何填写转移地址的问题 因为在生成四元式转移语句时 转移的目标地址还不确定 这需要用到转移地址回填技术 例 求if c d x x 1 y y x elsex x 1 y x 1 的四元式序列 练习 求y a 1 if x y x x 1 y y 1 y x x 的四元式序列 2020 3 11 信息学院孙丽云 49 布尔表达式代码生成 在语句if E S1elseS2中 表达式E的作用是提供选择执行语句S1还是S2的判断 因此不必保留E的值 而是将计算结果表示为程序执行流程的转移 此时E的值只需有两个即可 所以E被视为布尔表达式 E的真值被转换为一个条件转移 称为 真出口 E的假值被转换为一个无条件转移 称为 假出口 最简单的情况E是一个布尔变量a 那么有 真出口 假出口 2020 3 11 信息学院孙丽云 50 布尔量间的运算除了一般的布尔代数运算外 还有一种运算方法 称为 短路布尔操作 它的意义是 对于一个二元布尔操作 如果根据第1个布尔量的值就可以判断这个布尔结果 那么就不必计算第2个布尔量了 就是说 在某种情况下第2个布尔量被短路了 布尔表达式代码生成 如 对于二元操作aandb 如果a是假 不管b是什么 aandb的结果都是假 所以b被短路掉 就不用计算了 这种短路的操作对代码来说是很重要的 有些时候 没被短路的操作会引起错误 例如 这是C语言中常见的语句 但如果出现p NULL时还要对p val求值将引起内存错误 2020 3 11 信息学院孙丽云 51 短路的布尔操作类似于if语句 它们经常用if表达式定义 例如 将E1的真出口与全句的真出口并联 E1的假出口转移至E2的第1个四元式 E2的真出口是全句的真出口 E2的假出口是全句的假出口 布尔表达式代码生成 将E1的真出口转移至E2的第1个四元式 E1的假出口与全句假出口并联 相同 E2的真出口就是全句的真出口 E2的假出口也是全句的假出口 2020 3 11 信息学院孙丽云 52 举例 1 a b 求其短路布尔操作四元式序列 1 jnz a 3 2 jp false 3 jnz b true 4 jp false 依据布尔表达式的四元式定义可将其四元式代码写成 例 求表达式a b c d e f的短路布尔操作四元式序列 true表示布尔表达式的真出口 false表示布尔表达式的假出口 注意 优先级高于 a b 练习 求表达式x y z的短路布尔操作四元式序