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

编译原理(第三版) 陈火旺等编著 （2012年9月-12月） 主讲：朱世松 计算机学院 二、语义分析的范围 1.确定类型：确定标识符所关联的数据类型。 2.类型检查：按语言的类型规则，检查运算的合法性与运算分量类型的一致性，必要时作类型转换。 3.识别含义：根据语言的语义定义（形式或非形式），识别程序中各构造成分组合到一起的含义，并作相应的语义处理（生成中间代码或目标代码） 4.控制流检查：控制流语句必须转移到合法的地方。 如：C中，break语句规定跳出最内层的循环或switch语句. 5.一致性检查：在很多场合要求对象只能被说明一次(避免重复定义)。 6.相关名字检查：如：Ada，循环或块可以有一个名字，它出现在这些结构的开头或结尾。编译程序必须检查这两个地方用的名字是否相同。 三、语义描述工具和语义分析方法 语义描述工具 目前流行：用属性文法作为描述语义的工具。 语义分析方法 根据描述属性文法的语义规则的方式不同，语义分析方法分为： 语法制导定义方法 翻译方案 7.1 中 间 语 言 1 中间语言 中间语言：它介于源程序到目标语言程序中间程序的语言 中间语言程序：用中间语言表示的程序。 作用：用于编译程序，将源程序翻译成等价的中间语言程序，再将中间语言程序转化成目标程序（即将语义分析和目标代码生成分开处理） 源程序 中间语言程序 目标程序 中间语言是表示语法制导翻译的结果。 好处： 中间语言与机器无关，使采用中间语言进行翻译的编译程序系统易于移植。 易于优化翻译后的代码。 使编译程序的结构在逻辑上更简单明确。 2 中间语言的表示 常见：逆波兰表示 四元式表示和三地址代码、三元式 图表示： DAG和树形表示 7.1.1 逆波兰表示 由波兰逻辑学家J.Lukasiewicz(卢卡西维兹)首先提出用来表示表达式的方法，后来推广到表示程序设计语言中的其它语法成分。 表达式的逆波兰表示 表达式的表示： 中缀表示： 运算符居中，运算对象在左右两边:a+b 波兰表示： 前缀表示：运算符在前，运算对象在后：+ab 后缀表示：运算对象在前，运算符在后：ab+… (逆波兰表示) 例：逆波兰表示的例子 把表达式翻译成后缀式的语义规则描述 (2)逆波兰表示的特点 a.标识符(运算对象)出现的顺序（从左到右）和原有顺序相同。 b. 运算符是按实际计算顺序（从左到右）出现的。 c. 运算符紧跟在运算对象的后面出现，并且没有括号。 (3) 好处：易于对表达式的计算处理 对于一般表达式的计算，系统需要用两个工作栈分别处理运算对象和运算符。 对于逆波兰表示的表达式计算处理只用一个工作栈。 一般的计算过程是：自左至右扫描后缀式，每碰到运算量就把它推进栈。每碰到k目运算符就把它作用于栈顶的k个项，并用运算结果代替这k个项。 例：逆波兰式ab+c*的计算处理过程 2. 形成逆波兰表示 怎样将一般表达式转换成逆波兰表示？ 基本思想:从左到右扫描表达式，每遇到： 1o 表达式中的运算对象则往左去。 2o 表达式中的运算符，则与运算符栈顶元素比较优先数： 例：画出形成表达式a*(b+c/d)的逆波兰表示过程 形成逆波兰表示的过程，实质上是表达式的翻译过程。（算法不难写出） 例：a/b/c+d = ab/c/d+ (a+b)*(c-d/e) = ab+cde/-* 数组POST存放后缀式：k为下标，初值为1 上述语义动作可实现为： 产生式 程序段 E→E(1)op E(2) {POST[k]:=op;k:=k+1} E→ (E(1)) {} E→i {POST[k]:=i;k:=k+1} 例：输入串a+b+c的分析和翻译 POST： 1 2 3 4 5 7.1.2 图表示法 图表示法 DAG 抽象语法树 7.1.2 图表示法 无循环有向图(Directed Acyclic Graph，简称DAG) 对表达式中的每个子表达式，DAG中都有一个结点 一个内部结点代表一个操作符，它的孩子代表操作数 在一个DAG中代表公共子表达式的结点具有多个父结点 a:=b*(-c)+b*(-c)的图表示法 抽象语法树对应的代码： T1:=-c T2:=b*T1 T3:=-c T4:=b*T3 T5:=T2+T4 a:=T5 DAG对应的代码： T1:=-c T2:=b*T1 T5:=T2+T2 a:=T5 产生赋值语句抽象语法树的属性文法 产 生 式 语义规则 S→id:=E S.nptr:=mknode(‘assign’, mkleaf(id,id