第七章 语义分析与中间代码产生(第十一周).ppt

第七章 语义分析和 中间代码产生 概述 静态语义检查 类型检查 控制流检查 一致性检查 相关名字检查 名字的作用域分析 中间语言（复杂性界于源语言和目标语言之间）的好处： 便于进行与机器无关的代码优化工作 易于移植 使编译程序的结构在逻辑上更为简单明确 内容线索 中间语言 说明语句 赋值语句的翻译 布尔表达式的翻译 控制语句的翻译 过程调用的处理 中间语言 常用的中间语言 后缀式，逆波兰表示 图表示 DAG 抽象语法树 三地址代码 三元式 四元式 间接三元式 后缀式 后缀式表示法：Lukasiewicz发明的一种表示表达式的方法，又称逆波兰表示法。 一个表达式E的后缀形式可以如下定义： 1. 如果E是一个变量或常量，则E的后缀式是E自身。 2. 如果E是E1 op E2形式的表达式，其中op是任何二元操作符，则E的后缀式为E1? E2? op，其中E1? 和E2? 分别为E1 和E2的后缀式。 3. 如果E是(E1)形式的表达式，则E1的后缀式就是E的后缀式。 逆波兰表示法不用括号。只要知道每个算符的目数，对于后缀式，不论从哪一端进行扫描，都能对它进行唯一分解。 后缀式的计算 用一个栈实现。 一般的计算过程是：自左至右扫描后缀式，每碰到运算量就把它推进栈。每碰到k目运算符就把它作用于栈顶的k个项，并用运算结果代替这k个项。 把表达式翻译成后缀式的语义规则描述 E.code表示E后缀形式 op表示任意二元操作符 “||”表示后缀形式的连接 数组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 图表示法 DAG 抽象语法树 DAG 有向无循环图(Directed Acyclic Graph，简称DAG) 对表达式中的每个子表达式，DAG中都有一个结点 一个内部结点代表一个操作符，它的孩子代表操作数 在一个DAG中代表公共子表达式的结点具有多个父结点 a+a*(b-c)+(b-c)*d的图表示法 抽象语法树 在语法树中去掉那些对翻译不必要的信息，从而获得更有效的源程序中间表示。这种经变换后的语法树称之为抽象语法树(Abstract Syntax Tree) 建立表达式的抽象语法树 mknode (op,left,right) 建立一个运算符号结点，标号是op，两个域left和right分别指向左子树和右子树。 mkleaf (id,entry) 建立一个标识符结点，标号为id，一个域entry指向标识符在符号表中的入口。 mkleaf (num,val) 建立一个数结点，标号为num，一个域val用于存放数的值。 建立抽象语法树的语义规则 产 生 式 语 义 规 则 E→E1+T E.nptr := mknode ( ‘+’, E1.nptr, T.nptr ) E→E1-T E.nptr := mknode ( ‘-’, E1.nptr, T.nptr ) E→T E.nptr := T.nptr T→ (E) T.nptr := E.nptr T→id T.nptr := mkleaf ( id, id.entry ) T→num T.nptr := mkleaf ( num, num.val ) a－4＋c的抽象语法树 a:=b*(-c)+b*(-c)的图表示法 产生赋值语句抽象语法树的属性文法 产 生 式 语义规则 S→id:=E S.nptr:=mknode(‘assign’, mkleaf(id,id.place),E.nptr) E→E1+E2 E.nptr:=mknode(‘+’,E1.nptr,E2.nptr) E→E1*E2 E.nptr:=mknode(‘*’,E1.nptr,E2.nptr) E→-E1 E.nptr:=mknode(‘uminus’,E1.nptr) E→ (E1) E.nptr:=E1.nptr E→id E.nptr:=mkleaf(id,id.place) 三地址代码 三地址代码 x:=y op z 三地址代码可以看成是抽象语法树或DAG的一种线性表示 a:=b*(-c)+b*(-c)的图表示法 DAG对应的代码： T1:=-c T2:=b*T1 T5:=T2+T2 a:=T5 三地址语句的种类 x:=y op z x:=op y x:=y goto L i