编译原理语义分析和中间代码产生

语义分析和中间代码产生静态语义检查类型检查控制流检查一致性检查相关名字检查名字的作用域分析语法分析器中间代码产生器静态检查器中间代码优化器中间语言(复杂性界于源语言和目标语言之间)的好处：便于进行与机器无关的代码优化工作易于移植使编译程序的结构在逻辑上更为简单明确源语言程序目标语言程序中间语言程序CompilerFrontEndCompilerBackEnd常用的中间语言：后缀式，逆波兰表示三地址代码三元式四元式间接三元式DAG图表示7.1中间语言7.1.1后缀式后缀式表示法：Lukasiewicz发明的一种表示表达式的方法，又称逆波兰表示法。一个表达式E的后缀形式可以如下定义：1.如果E是一个变量或常量，则E的后缀式是E自身。2.如果E是E1opE2形式的表达式，其中op是任何二元操作符，则E的后缀式为E1E2op，其中E1和E2分别为E1和E2的后缀式。3.如果E是(E1)形式的表达式，则E1的后缀式就是E的后缀式。逆波兰表示法不用括号。只要知道每个算符的目数，对于后缀式，不论从哪一端进行扫描，都能对它进行唯一分解。后缀式的计算用一个栈实现。一般的计算过程是：自左至右扫描后缀式，每碰到运算量就把它推进栈。每碰到k目运算符就把它作用于栈顶的k个项，并用运算结果代替这k个项。•把表达式翻译成后缀式的语义规则描述产生式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表示任意二元操作符•“||”表示后缀形式的连接。数组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：12345ab+c+…7.1.2图表示法图表示法DAG抽象语法树7.1.2图表示法无循环有向图(DirectedAcyclicGraph，简称DAG)对表达式中的每个子表达式，DAG中都有一个结点一个内部结点代表一个操作符，它的孩子代表操作数在一个DAG中代表公共子表达式的结点具有多个父结点a:=b*(-c)+b*(-c)的图表示法assigna+*buminuscDAGassigna+*buminusc抽象语法树*buminusc产生赋值语句抽象语法树的属性文法产生式语义规则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)7.1.3三地址代码三地址代码x:=yopz表达式x+yz翻译成的三地址语句序列是t1:=yzt2:=x+t1出于语句的右边只有一个算符的考虑三地址代码可以看成是抽象语法树或DAG的一种线性表示三地址代码是语法树或dag的一种线性表示a:=(b+cd)+cd语法树的代码dag的代码t1:=bt2:=cdt3:=t1+t2t4:=cdt5:=t3+t4a:=t5新增加的名字对应树/图中的内部结点assigna++bcdcduminus语法树三地址代码是语法树或dag的一种线性表示a:=(b+cd)+cd语法树的代码dag的代码t1:=bt2:=cdt3:=t1+t2t4:=t3+t2a:=t4新增加的名字对应树/图中的内部结点assigna++bcduminus(b)dag三地址语句的种类本书常用的三地址语句赋值语句x:=yopz;x:=opy;x:=y无条件转移gotoL条件转移ifxrelopygotoL过程调用paramx和callp,n过程返回returny索引赋值x:=y[i]和x[i]:=y地址和指针赋值x:=&y，x:=y和x:=y生成三地址代码时，临时变量的名字对应抽象语法树的内部结点id:=E对表达式E求值并置于变量T中值id.place:=T从赋值语句生成三地址代码的S-属性文法非终结符号S有综合属性S.code，它代表赋值语句S的三地址代码。非终结符号E有如下两个属性：E.place表示存放E值的名字。E.code表示对E求值的三地址语句序列。函数newtemp的功能是，每次调用它时，将返回一个不同临时变量名字,如T1,T2,…。为赋值语句生成三地址代码的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=‘’三地址语句三地址语句可看成中间代码的一种抽象形式.编译程序中,三地址代码语句的具体实现可用记录表示.通常有三种表示方法:四元式、三元式、间接三元式。四元式一个带有四个域的记录结构，这四个域分别称为op,arg1,arg2及resultoparg1arg2result(0)uminuscT1(1)*bT1T2(2)uminuscT3(3)*bT3T4(4)+T2T4T5(5):=T5a三地址语句三元式通过计算临时变量值的语句的位置来引用这个临时变量三个域：op、arg1和arg2oparg1arg2(0)uminusc(1)*b(0)(2)uminusc(3)*b(2)(4)+(1)(3)(5)assigna(4)三地址语句x[i]:=yoparg1arg2(0)[]=xi(1)assign（0）yx:=y[i]oparg1arg2(0)=[]yi(1)assignx(0)三地址语句间接三元式为了便于优化，用三元式表+间接码表表示中间代码间接码表:一张指示器表，按运算的先后次序列出有关三元式在三元式表中的位置。优点:方便优化，节省空间例如，语句X:=(A+B)*C;Y:=D↑(A+B)的间接三元式表示如下表所示。间接代码(1)(2)(3)(1)(4)(5)三元式表OPARG1ARG2(1)+AB(2)*(1)C(3):=X(2)(4)↑D(1)(5):=Y(4)7.2声明语句声明的语法制导定义产生式语义规则DTLL.in:=T.typeTintT.type:=integerTrealT.type:=realLL1,idL1.in:=L.in;addtype(id.entry,L.in)Lidaddtype(id.entry,L.in)7.2声明语句DidL{addtype(id.entry,L.type)}L,idL1{L.type:=L1.Type;addtype(id.entry,L1.type)}L:T{L.type:=T.type}Tinteger{T.type:=integer}Treal{T.type:=real}以上没有继承属性的翻译方案D:L,idLidintegerT7.2声明语句为局部名字建立符号表条目为它分配存储单元符号表中包含名字的类型和分配给它的存储单元的相对地址等信息7.2声明语句7.2.1过程中的声明PDSDD;DDid:TTintegerTrealTarray[num]ofT1TT17.2声明语句计算被声明名字的类型和相对地址P{offset:=0}DSDD;DDid:T{enter(id.name,T.type,offset);offset:=offset+T.width}Tinteger{T.type:=integer;T.width:=4}Treal{T.type:=real;T.width:=8}Tarray[num]ofT1{T.type:=array(num.val,T1.type);T.width:=num.valT1.width}TT1{T.type:=pointer(T1.type);T.width:=4}offset:用于跟踪可用的相对地址的位置。enter(name,type,offset):用于填充符号表。7.2声明语句7.2.2作用域信息的保存所讨论语言的文法PDSDD;D|id:T|procid;D;S语义动作用到的函数mktable(previous)enter(table,name,type,offset)addwidth(table,width)enterproc(table,name,newtable)7.2声明语句处理嵌套过程中的说明语句PMDS{addwidth(top(tblptr),top(offset));pop(tblptr);pop(offset)}M{t:=mktable(nil);push(t,tblprt);push(0,offset)}DD1;D2Dprocid;ND1;S{t:=top(tblptr);addwidth(t,top(offset));pop(tblptr);pop(offset);enterproc(top(tblptr),id.name,t)}Did:T{enter(top(tblptr),id.name,T.type,top(offset));top(offset):=top(offset)+T.width}N{t:=mktable(top(tblptr));push(t,tblptr);push(0,offset)}tblptr与offset是两个栈名，tblptr为主过程的符号表头，offset为存放各嵌套过程的当前相对地址。7.2声明语句exchangereadarrayxa表头空sortquicksort指向readarraypartitionvk表头quicksortreadarraryi表头exchange表头指向exchangepartition7.3赋值语句的翻译7.3.1简单算术表达式及赋值语句为赋值语句生成三地址代码的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=‘’产生赋值语句三地址代码的翻译模式S→id:=E{