国防科技大学计算机系602教研室,第七章 语义分析和中间代码产生,静态语义检查 类型检查 控制流检查 一致性检查 相关名字检查 名字的作用域分析,语法分 析器,中间代码 产生器,静态检 查器,中间代码,优化器,国防科技大学计算机系602教研室,中间语言(复杂性界于源语言和目标语言之间)的好处： 便于进行与机器无关的代码优化工作 易于移植 使编译程序的结构在逻辑上更为简单明确,源语言 程序,目标语 言程序,中间语 言程序,国防科技大学计算机系602教研室,常用的中间语言： 后缀式，逆波兰表示 图表示： DAG、抽象语法树 三地址代码 三元式 四元式 间接三元式,7.1 中间语言,国防科技大学计算机系602教研室,7.1.1 后缀式,后缀式表示法：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的后缀式。,国防科技大学计算机系602教研室,逆波兰表示法不用括号。只要知道每个算符的目数，对于后缀式，不论从哪一端进行扫描，都能对它进行唯一分解。 后缀式的计算 用一个栈实现。 一般的计算过程是：自左至右扫描后缀式，每碰到运算量就把它推进栈。每碰到k目运算符就把它作用于栈顶的k个项，并用运算结果代替这k个项。,国防科技大学计算机系602教研室,把表达式翻译成后缀式的语义规则描述,产生式 EE(1)op E(2) E (E(1) Eid,语义动作 E.code:= E(1).code | E(2).code |op E.code:= E(1).code E.code:=id,E.code表示E后缀形式 op表示任意二元操作符 “|”表示后缀形式的连接。,国防科技大学计算机系602教研室,数组POST存放后缀式：k为下标，初值为1 上述语义动作可实现为： 产生式 程序段 EE(1)op E(2) POSTk:=op;k:=k+1 E (E(1) Ei POSTk:=i;k:=k+1 例：输入串a+b+c的分析和翻译 POST： 1 2 3 4 5,EE(1)op E(2) E.code:= E(1).code | E(2).code |op E (E(1) E.code:= E(1).code Eid E.code:=id,a,b,+,c,+,国防科技大学计算机系602教研室,7.1.2 图表示法,图表示法 DAG 抽象语法树,国防科技大学计算机系602教研室,7.1.2 图表示法,无循环有向图(Directed Acyclic Graph，简称DAG) 对表达式中的每个子表达式，DAG中都有一个结点 一个内部结点代表一个操作符，它的孩子代表操作数 在一个DAG中代表公共子表达式的结点具有多个父结点,国防科技大学计算机系602教研室,a:=b*(-c)+b*(-c)的图表示法,国防科技大学计算机系602教研室,抽象语法树对应的代码： T1:=-c T2:=b*T1 T3:=-c T4:=b*T3 T5:=T2+T4 a:=T5,国防科技大学计算机系602教研室,DAG对应的代码： T1:=-c T2:=b*T1 T5:=T2+T2 a:=T5,抽象语法树对应的代码： T1:=-c T2:=b*T1 T3:=-c T4:=b*T3 T5:=T2+T4 a:=T5,国防科技大学计算机系602教研室,产生赋值语句抽象语法树的属性文法,产 生 式 语义规则 Sid:=E S.nptr:=mknode(assign, mkleaf(id,id.place),E.nptr) EE1+E2 E.nptr:=mknode(+,E1.nptr,E2.nptr) EE1*E2 E.nptr:=mknode(*,E1.nptr,E2.nptr) E-E1 E.nptr:=mknode(uminus,E1.nptr) E (E1) E.nptr:=E1.nptr Eid E.nptr:=mkleaf(id,id.place),国防科技大学计算机系602教研室,7.1.3 三地址代码,三地址代码 x:=y op z 三地址代码可以看成是抽象语法树或DAG的一种线性表示,国防科技大学计算机系602教研室,a:=b*(-c)+b*(-c)的图表示法,国防科技大学计算机系602教研室,T1:=-c T1:=-c T2:=b*T1 T2:=b*T1 T3:=-c T5:=T2+T2 T4:=b*T3 a:=T5 T5:=T2+T4 a:=T5 对于抽象语法树的代码 对于DAG的代码,国防科技大学计算机系602教研室,三地址语句的种类,x:=y op z x:=op y x:=y goto L if x relop y goto L或if a goto L param x和call p,n，以及返回语句return y x:=yi及xi:=y的索引赋值 x:=&y, x:=*y和*x:=y的地址和指针赋值,国防科技大学计算机系602教研室,生成三地址代码时，临时变量的名字对应抽象语法树的内部结点 id:=E 对表达式E求值并置于变量T中值 id.place:=T,国防科技大学计算机系602教研室,从赋值语句生成三地址代码的S-属性文法,非终结符号S有综合属性S.code，它代表赋值语句S的三地址代码。 非终结符号E有如下两个属性： E.place表示存放E值的名字。 E.code表示对E求值的三地址语句序列。 函数newtemp的功能是，每次调用它时，将返回一个不同临时变量名字,如T1,T2,。,国防科技大学计算机系602教研室,为赋值语句生成三地址代码的S-属性文法定义,产生式 语义规则 Sid:=E S.code:=E.code | gen(id.place := E.place) EE1+E2 E.place:=newtemp; E.code:=E1.code | E2.code | gen(E.place := E1.place + E2.place) EE1*E2 E.place:=newtemp; E.code:=E1.code | E2.code | gen(E.place := E1.place * E2.place) E-E1 E.place:=newtemp; E.code:=E1.code | gen(E.place := uminus E1.place) E (E1) E.place:=E1.place; E.code:=E1.code Eid E.place:=id.place; E.code= ,国防科技大学计算机系602教研室,三地址语句,四元式 一个带有四个域的记录结构，这四个域分别称为op, arg1, arg2及result op arg1 arg2 result (0) uminus c T1 (1) * b T1 T2 (2) uminus c T3 (3) * b T3 T4 (4) + T2 T4 T5 (5) := T5 a,国防科技大学计算机系602教研室,三地址语句,三元式 通过计算临时变量值的语句的位置来引用这个临时变量 三个域：op、arg1和arg2 op arg1 arg2 (0) uminus c (1) * b (0) (2) uminus c (3) * b (2) (4) + (1) (3) (5) assign a (4),国防科技大学计算机系602教研室,三地址语句,xi:=y op arg1 arg2 (0) = x i (1) y x:=yi op arg1 arg2 (0) = y i (1) assign x (0),国防科技大学计算机系602教研室,三地址语句,间接三元式 为了便于优化，用 三元式表+间接码表 表示中间代码 间接码表:一张指示器表，按运算的先后次序列出有关三元式在三元式表中的位置。 优点: 方便优化，节省空间,国防科技大学计算机系602教研室,例如，语句 X:=(A+B)*C; Y:=D(A+B) 的间接三元式表示如下表所示。,国防科技大学计算机系602教研室,7.2 说明语句,国防科技大学计算机系602教研室,7.3 赋值语句的翻译,7.3.1 简单算术表达式及赋值语句,国防科技大学计算机系602教研室,为赋值语句生成三地址代码的S-属性文法定义,产生式 语义规则 Sid:=E S.code:=E.code | gen(id.place := E.place) EE1+E2 E.place:=newtemp; E.code:=E1.code | E2.code | gen(E.place := E1.place + E2.place) EE1*E2 E.place:=newtemp; E.code:=E1.code | E2.code | gen(E.place := E1.place * E2.place) E-E1 E.place:=newtemp; E.code:=E1.code | gen(E.place := uminus E1.place) E (E1) E.place:=E1.place; E.code:=E1.code Eid E.place:=id.place; E.code= ,国防科技大学计算机系602教研室,产生赋值语句三地址代码的翻译模式,Sid:=E p:=lookup(id.name); if pnil then emit(p := E.place) else error EE1+E2 E.place:=newtemp; emit(E.place := E1.place + E2.place) EE1*E2 E.place:=newtemp; emit(E.place := E 1.place * E 2.place),Sid:=E S.code:=E.code | gen(id.place := E.place) EE1+E2 E.place:=newtemp; E.code:=E1.code | E2.code |gen(E.place := E1.place + E2.place) EE1*E2 E.place:=newtemp; E.code:=E1.code | E2.code | gen(E.place := E1.place * E2.place),国防科技大学计算机系602教研室,产生赋值语句三地址代码的翻译模式,E-E1 E.place:=newtemp; emit(E.place:= uminusE 1.place) E(E1) E.place:=E1.place Eid p:=lookup(id.name); if pnil then E.place:=p else error ,E-E1 E.place:=newtemp; E.code:=E1.code | gen(E.place := uminus E1.place) E (E1) E.place:=E1.place; E.code:=E1.code Eid