语义分析和中间代码产生(第九周).pptxVIP

第七章 语义分析和 中间代码产生;概述;中间语言（复杂性界于源语言和目标语言之间）的好处： 便于进行与机器无关的代码优化工作 易于移植 使编译程序的结构在逻辑上更为简单明确 ;内容线索;中间语言;后缀式;逆波兰表示法不用括号。只要知道每个算符的目数，对于后缀式，不论从哪一端进行扫描，都能对它进行唯一分解。 后缀式的计算 用一个栈实现。 一般的计算过程是：自左至右扫描后缀式，每碰到运算量就把它推进栈。每碰到k目运算符就把它作用于栈顶的k个项，并用运算结果代替这k个项。;把表达式翻译成后缀式的语义规则描述;数组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;a+a*(b-c)+(b-c)*d的图表示法;抽象语法树;建立表达式的抽象语法树;建立抽象语法树的语义规则; a－4＋c的抽象语法树; a:=b*(-c)+b*(-c)的图表示法 ;产生赋值语句抽象语法树的属性文法 ;三地址代码;DAG对应的代码： T1:=-c T2:=b*T1 T5:=T2+T2 a:=T5 ;三地址语句的种类 ;x:=y 把y的地址赋给x，其中y是一个名字，或者是一个临时变量，代表一个具有左值的表达式 x:=*y 把y所指示的地址单元里存放的内容赋给x，其中y是一个指针或者是一个其右值为地址的临时变量。 *x:=y 把y的右值赋给x所指向的对象的右值 ;;从赋值语句生成三地址代码的S-属性文法;为赋值语句生成三地址代码的S-属性文法定义 ;三地址语句;三地址语句;三地址语句;三地址语句;例如，语句 X:=(A+B)*C; Y:=D↑(A+B) 的间接三元式表示如下表所示。;四元式、三元式和间接三元式比较; 三元式中使用了指向三元式的指针，优化时修改较难。 间接三元式优化只需要更改间接码表，并节省三元式表存储空间。 修改四元式表也较容易，只是临时变量要填入符号表，占据一定存储空间。; 1. 后缀式 后缀式表示法又称逆波兰表示法，是一种表示表达式的方法，它把运算量（操作数）写在前面，算符写在后面 例：中缀表示: a+b,a+b*c,m=1,(a+b)*c, (a+b)*(c-d) 后缀表示: ab+, abc*+, m1=,ab+c*, ab+cd-* 特点: 运算分量的个数与先后次序不变； 运算符的个数不变, 但其出现顺序即为执行顺序 无括号；;一个表达式E的后缀式可如下定义：; 二叉树遍历法即后序遍历二叉树 例如：((a+b) / (c-d)） e;后缀式的推广 [例] 条件算术表达式: if e then X else Y 三目运算 if - then - else : ￥ ;2、树: 也可以用树型结构表示表达式或语句。对表达式中的每个子表达式表式为一棵子树，即简单变量或常数的树就是该变量或常数自身。如果表示e1和e2的树为T1和T2，那么，e1+e2,e1*e2,-e1的树分别为：;3、三地址代码 一般形式：x:=y op z 如： x:=y op z 二元赋值 x:= op y 一元赋值 x:=y 复制赋值 goto L 无条件转移 if x relop y goto L 条件转移 if a goto L 条件转移 三地址代码在具体实现时常表示为记录结构，如四元式、三元式、间接三元式。;[例] a:= b*-c+b*-c 的四元式序列: op arg1 arg2 result (1) ( @ c _ T1 ) (2) ( * b T1 T2 ) (3) ( @ c _ T3 ) (4) ( * b T3 T4 ) (5) (+ T2 T4 T5) (6) (:= T5 _ a); 三元式 一个三元式有三个域 ( op, arg1, arg2 ),其中：arg1,arg2为指向符号表的指针（