编译7语义分析和中间代码产生1(zss).ppt

编译原理 第三版 陈火旺等编著 2012年9月 12月 主讲 朱世松计算机学院 2 2020 2 4 概述 一 语义分析的任务审查每一个语法结构的静态语义 即验证语法正确的结构是否有意义 如 赋值语句 x x y 左边变量类型与右边变量类型是否一致 在语义正确的基础上生成一种中间代码或目标代码 3 2020 2 4 二 语义分析的范围1 确定类型 确定标识符所关联的数据类型 2 类型检查 按语言的类型规则 检查运算的合法性与运算分量类型的一致性 必要时作类型转换 3 识别含义 根据语言的语义定义 形式或非形式 识别程序中各构造成分组合到一起的含义 并作相应的语义处理 生成中间代码或目标代码 4 控制流检查 控制流语句必须转移到合法的地方 如 C中 break语句规定跳出最内层的循环或switch语句 4 2020 2 4 5 一致性检查 在很多场合要求对象只能被说明一次 避免重复定义 6 相关名字检查 如 Ada 循环或块可以有一个名字 它出现在这些结构的开头或结尾 编译程序必须检查这两个地方用的名字是否相同 5 2020 2 4 三 语义描述工具和语义分析方法语义描述工具目前流行 用属性文法作为描述语义的工具 语义分析方法根据描述属性文法的语义规则的方式不同 语义分析方法分为 语法制导定义方法翻译方案 6 2020 2 4 1中间语言中间语言 它介于源程序到目标语言程序中间程序的语言中间语言程序 用中间语言表示的程序 作用 用于编译程序 将源程序翻译成等价的中间语言程序 再将中间语言程序转化成目标程序 即将语义分析和目标代码生成分开处理 源程序中间语言程序目标程序中间语言是表示语法制导翻译的结果 等价变换 转化 7 1中间语言 7 2020 2 4 好处 中间语言与机器无关 使采用中间语言进行翻译的编译程序系统易于移植 易于优化翻译后的代码 使编译程序的结构在逻辑上更简单明确 2中间语言的表示常见 逆波兰表示四元式表示和三地址代码 三元式图表示 DAG和树形表示 8 2020 2 4 7 1 1逆波兰表示由波兰逻辑学家J Lukasiewicz 卢卡西维兹 首先提出用来表示表达式的方法 后来推广到表示程序设计语言中的其它语法成分 表达式的逆波兰表示表达式的表示 中缀表示 运算符居中 运算对象在左右两边 a b波兰表示 前缀表示 运算符在前 运算对象在后 ab后缀表示 运算对象在前 运算符在后 ab 逆波兰表示 9 2020 2 4 例 逆波兰表示的例子 10 2020 2 4 1 表达式逆波兰表示的定义 设E是一般表达式 则 一般表达式逆波兰表达式若E为变量或常量E E E的逆波兰式E 1 opE 2 二目运算 E 1 的逆波兰式E 2 的逆波兰式opopE 单目运算 E的逆波兰式op 11 2020 2 4 把表达式翻译成后缀式的语义规则描述 产生式E E 1 opE 2 E E 1 E id 语义动作E code E 1 code E 2 code opE code E 1 codeE code id E code表示E后缀形式op表示任意二元操作符 表示后缀形式的连接 12 2020 2 4 2 逆波兰表示的特点a 标识符 运算对象 出现的顺序 从左到右 和原有顺序相同 b 运算符是按实际计算顺序 从左到右 出现的 c 运算符紧跟在运算对象的后面出现 并且没有括号 13 2020 2 4 3 好处 易于对表达式的计算处理对于一般表达式的计算 系统需要用两个工作栈分别处理运算对象和运算符 对于逆波兰表示的表达式计算处理只用一个工作栈 一般的计算过程是 自左至右扫描后缀式 每碰到运算量就把它推进栈 每碰到k目运算符就把它作用于栈顶的k个项 并用运算结果代替这k个项 14 2020 2 4 例 逆波兰式ab c 的计算处理过程 遇运算对象a b入栈 扫描ab c 栈 遇二目运算符 c 取出a b 运算结果T入栈 取出c T作运算 设结果T1 遇运算符 c 遇运算对象c入栈 15 2020 2 4 2 形成逆波兰表示怎样将一般表达式转换成逆波兰表示 基本思想 从左到右扫描表达式 每遇到 1o表达式中的运算对象则往左去 2o表达式中的运算符 则与运算符栈顶元素比较优先数 16 2020 2 4 逆波兰表示 表达式 运算对象 运算符 进栈 出栈 运算符栈 如果运算符栈顶元素的优先数大于或等于表达式中当前的运算符优先数 则栈顶元素退栈向左去 然后当前运算符继续与栈顶的新元素比较优先数 直到栈顶元素的优先数小于表达式中当前运算符为止 此时 才将表达式中当前运算符进栈 17 2020 2 4 例 画出形成表达式a b c d 的逆波兰表示过程 18 2020 2 4 19 2020 2 4 形成逆波兰表示的过程 实质上是表达式的翻译过程 算法不难写出 例 a b c d ab c d a b c d e ab cde 20 2020 2 4 数组POST存放后缀式 k为下标 初值为1上述语义动作可实现为 产生式程序段E E 1 opE 2 POST k op k k 1 E E 1 E i POST k i k k 1 例 输入串a b c的分析和翻译POST 12345 E E 1 opE 2 E code E 1 code E 2 code opE E 1 E code E 1 codeE idE code id a b c 21 2020 2 4 7 1 2图表示法 图表示法DAG抽象语法树 22 2020 2 4 7 1 2图表示法 无循环有向图 DirectedAcyclicGraph 简称DAG 对表达式中的每个子表达式 DAG中都有一个结点一个内部结点代表一个操作符 它的孩子代表操作数在一个DAG中代表公共子表达式的结点具有多个父结点 23 2020 2 4 a b c b c 的图表示法 24 2020 2 4 抽象语法树对应的代码 T1 cT2 b T1T3 cT4 b T3T5 T2 T4a T5 25 2020 2 4 DAG对应的代码 T1 cT2 b T1T5 T2 T2a T5 抽象语法树对应的代码 T1 cT2 b T1T3 cT4 b T3T5 T2 T4a T5 26 2020 2 4 产生赋值语句抽象语法树的属性文法 产生式语义规则S id ES nptr mknode assign mkleaf id id place E nptr E E1 E2E nptr mknode E1 nptr E2 nptr E E1 E2E nptr mknode E1 nptr E2 nptr E E1E nptr mknode uminus E1 nptr E E1 E nptr E1 nptrE idE nptr mkleaf id id place 27 2020 2 4 7 1 3三地址代码 三地址代码x yopz三地址代码可以看成是抽象语法树或DAG的一种线性表示 28 2020 2 4 a b c b c 的图表示法 29 2020 2 4 T1 cT1 cT2 b T1T2 b T1T3 cT5 T2 T2T4 b T3a T5T5 T2 T4a T5对于抽象语法树的代码对于DAG的代码 30 2020 2 4 三地址语句的种类 x yopzx opyx ygotoLifxrelopygotoL或ifagotoLparamx和callp n 以及返回语句returnyx y i 及x i y的索引赋值x y x y和 x y的地址和指针赋值 31 2020 2 4 生成三地址代码时 临时变量的名字对应抽象语法树的内部结点id E对表达式E求值并置于变量T中值id place T 32 2020 2 4 从赋值语句生成三地址代码的S 属性文法 非终结符号S有综合属性S code 它代表赋值语句S的三地址代码 非终结符号E有如下两个属性 E place表示存放E值的名字 E code表示对E求值的三地址语句序列 函数newtemp的功能是 每次调用它时 将返回一个不同临时变量名字 如T1 T2 33 2020 2 4 为赋值语句生成三地址代码的S 属性文法定义 产生式语义规则S id ES code E code gen id place E place E E1 E2E place newtemp E code E1 code E2 code gen E place E1 place E2 place E E1 E2E place newtemp E code E1 code E2 code gen E place E1 place E2 place E E1E place newtemp E code E1 code gen E place uminus E1 place E E1 E place E1 place E code E1 codeE idE place id place E code 34 2020 2 4 三地址语句 四元式一个带有四个域的记录结构 这四个域分别称为op arg1 arg2及resultoparg1arg2result 0 uminuscT1 1 bT1T2 2 uminuscT3 3 bT3T4 4 T2T4T5 5 T5a 35 2020 2 4 三地址语句 三元式通过计算临时变量值的语句的位置来引用这个临时变量三个域 op arg1和arg2oparg1arg2 0 uminusc 1 b 0 2 uminusc 3 b 2 4 1 3 5 assigna 4 36 2020 2 4 三地址语句 x i yoparg1arg2 0 xi 1 yx y i