搜索
语义分析与中间代码生成授课：胡静语义分析的位置和作用紧跟在语法分析和语法分析之后，编译程序要做的工作就是进行静态语义检查和翻译。编译器必须要检查源程序是否符合源语言规定的语法和语义要求。这种检查称为静态检查，检查并报告程序中某些类型的错误。语法分析器记号流类型检查器语法树中间代码生成器语法树中间表示静态语义检查静态语义检查通常包括：类型检查：如果操作符作用于不相容的操作数，编译器应该报错控制流检查：引起控制流从某个结构中跳转出来的语句必须能够决定控制流转向的目标地址唯一性检查：有时，有的对象只能被定义一次。比如，同一case语句的标号不能相同，枚举类型的元素不能重复。与名字相关的检查：有时候要求同一名字在特定位置出现两次或多次（如，标识结构的开始和结尾）摘要：语义分析检查在词法分析和语法分析中发现不了的错误范围错误：变量没有定义多重定义类型错误给不同的类型进行赋值使用不同数目的参数或者错误类型的参数对函数进行调用返回语句的错误使用语义分析类型检查使用类型检查规则静态语义=用形式化的框架描述类型检查规则也有控制流错误必须保证break或者continue语句包含在while(或for)语句中可以通过遍历AST来轻松的发现控制流错误所处位置中间语言源语言的中间表示方法抽象语法树后缀式三地址代码（包括三元式、四元式、间接三元式）DAG图表示后缀式后缀式表示又称逆波兰表示法。这种表示法是：把运算量（操作数）写在前面，把算符写在后面（后缀）。一个表达式的后缀形式可以如下定义：如果E是一个变量或常量，则E的后缀式是E自身如果E是E1opE2形式的表达式，这里op是任何二元操作符，则E的后缀式为E1’E2’op。这里E1’和E2’分别是E1和E2的后缀式。如果E是(E1)形式的表达式，则E1的后缀式就是E的后缀式这种表示法用不着使用括号。只要知道每个算符的目数，对于后缀式，无论从那一端进行扫描，都能对它正确的进行唯一分解后缀式表达式翻译为后缀式的语义规则描述：其中E.code表示E的后缀式，op表示任何二元操作符，“||”表示后缀形式的连接产生式语义规则E→E1opE2E.code:=E1.code||E2.code||opE→(E1)E.code:=E1.codeE→idE.code:=id图表示法图表示法主要包括DAG(DirectedAcyclicGraph)与抽象语法树语法树描述了源程序的自然层次结构。DAG以更紧凑的形式给出了相同的信息。两者不同的是：在一个DAG中代表公共子表达式的结点具有多个父结点在一颗抽象语法树中公共子表达式被表示为重复的子树。assign+a**uminusbcuminusbca:=b*-c+b*-cassign+a*uminusbcabcuminus*bcnuminus*+assign抽象语法树语法树中的边不会显式的出现在后缀表达式中，可以根据结点出现的顺序及结点上的操作符所要求的操作数的个数来恢复。其恢复过程类似使用栈对后缀表达式求值。如果函数mknode(op,child)和mknode(op,left,right)尽可能返回一个指向一个存在的结点的指针以代替建立新的结点，那么就会生成DAG图。产生式语义规则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)抽象语法树的表示形式assign••ida+*••*••uminus•uminus•idbidbidcidc••0idb1idc2uminus13*024idb5idc6uminus57*468+379ida10assign9811…三地址代码三地址代码是下列一般形式的语句序列x:=yopz其中，x、y和z是名字，常量或编译器生成的临时变量op代表任何操作符（定点运算符、浮点运算符、逻辑运算符等）这里不允许组合的算术表达式，因为语句右边只有一个操作符。像x+y*z这样的表达式要翻译为如下；T1:=y*zT2:=x+T1其中T1，T2为编译时产生的临时变量。三地址代码这种复杂算术表达式和嵌套控制流语句的拆解使得三地址码适用于目标代码生成及优化。由程序计算出来的中间值的名字的使用使得三地址码容易被重排列——而不像后缀表达式那样三地址码可以看成是语法树或DAG的线性表示。三地址码的得名原因是每条语句通常包含三个地址，两个是操作数地址，一个是结果地址。在实际的实现中，有程序员定义的名字被一个指向改名字的符号表表项的指针所代替。三地址码assign+a**uminusbcuminusbcassign+a*uminusbct1:=-ct2:=b*t1t3:=-ct4:=b*t3t5:=t2+t4a:=t5t1:=-ct2:=b*t1t3:=t2+t2a:=t3三地址语句的类型三地址语句类似于汇编语言代码。语句可以由符号标号，而且存在各种控制流语句。符号标号代表存放中间代码的数组中三地址代码语句的下标。下面列出本书中使用的三地址语句的种类：形如x:=yopz的赋值语句，其中op为二元算术算符或逻辑算符形如x:=opy的赋值语句，其中op为一元算符。形如x:=y的复制语句，将y的值赋给x形如gotoL的无条件跳转语句，即下一条将被执行的语句是带有标号L的三地址语句三地址语句的类型下面列出本书中使用的三地址语句的种类：形如ifxrelopygotoL或ifagotoL的条件跳转语句。第一种形式使用关系运算符号relop（，等）第二种a为布尔变量或常量用于过程调用的语句paramx和callp,n，以及返回语句returny。源程序中的过程调用p(x1,x2,…,xn)：paramx1paramx2……paramxncallp,nn表示实参个数。returny中y为过程返回的一个值三地址语句的类型下面列出本书中使用的三地址语句的种类：形如x:=y[i]及x[i]:=y的索引赋值。形如x:=&y,x:=*y和*x:=y的地址和指针赋值。设计中间代码形式时，运算符的选择是非常重要的。算符种类应足以用来实现源语言中的运算。一个小型算符集合较易于在新的目标机器上实现。局限的指令集合会使某些源语言运算表示成中间形式时代码加长，需要在目标代码生成时做较多的优化工作。生成三地址码的S-属性文法S具有综合属性S.code，代表赋值语句S的三地址码非终结符E有如下性质：E.place表示存放E值的名字E.code表示对E求值的三地址语句序列函数newtemp的功能是每次调用它时，将返回一个不同临时变量的名字。如T1,T2,….用gen(x‘:=’y‘+’z)表示生成三地址语句x:=y+z。在实际实现中，三地址码可能被送到输出文件中，而不是生成code属性。生成三地址码的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.placeE.code:=E1.codeE→idE.place:=id.placeE.code:=‘’如何加入控制语句S→WhileEdoS1S→WhileEdoS1对应的语义规则是：S.begin:=newlabel;S.after:=newlabel;S.code:=gen(S.begin‘:’)||E.code||gen(‘if’E.place‘=’‘0’‘goto’S.after)||S1.code||gen(‘goto’S.begin)||gen(S.after‘:’)E.codeifE.place=0gotoS.afterS1.codegotoS.beginS.begin:S.after:三地址语句的实现三地址语句是中间代码的一种抽象形式。这些语句可以以带有操作符和操作数域的记录来实现。四元式、三元式及简介三元式是三种这样的表示。四元式一个四元式是带有四个域的记录结构，这四个域分别称为op,arg1,arg2及result。域op包含一个代表运算符的内部码三地址语句x:=yopz通过将y放入arg1，z放入arg2，并且将x放入result，:=为算符。像x:=y或x:=-y这样的一元操作符语句不使用arg2像param这样的运算符仅使用arg1域。条件和无条件语句将目标标号存入result域。临时变量也要填入符号表中。三元式为了避免把临时变量填入符号表，我们可以通过计算这个临时变量的语句的位置来引用这个临时变量。这样三地址代码的记录只需要三个域op,arg1和arg。对于一目运算符op,arg1和arg2只需用其一。我们可以随意选用一个。四元式举例oparg1arg2result(0)uminuscT1(1)*bT1T2(2)uminuscT3(3)*bT3T4(4)+T2T4T5(5)assignT5aoparg1arg2(0)uminusc(1)*b0(2)uminusc(3)*b2(4)+13(5)assigna4a:=b*-c+b*-c三元式举例oparg1arg2(0)[]=xi(1)assign(0)yoparg1arg2(0)=[]yi(1)assignx(0)x[i]:=yx:=y[i]间接三元式为了便于代码优化处理，有时不直接使用三元式表，而是另设一张指示器（称为间接码表），它将运算的先后顺序列出有关三元式在三元表中的位置。换句话说，我们用一张间接码表辅以三元式表的办法来表示中间代码。这种表示方法称为间接三元式。间接三元式举例X:=(A+B)*CY:=D^(A+B)oparg1arg2(11)+AB(12)*(11)C(13):=X(12)(14)^D(11)(15):=Y(14)间接代码(11)(12)(13)(11)(14)(15)当在代码优化过程中需要调整运算顺序时，只需重新安排间接码表，无需改动三元式表对于间接三元式表示，语义规则中应增添产生间接码表的动作，并且在向三元式表填进一个三元式之前，必须先查看一下此式是否已在其中，就无须填入。表示方法比较：间址的使用三元式与四元式的差异可以看作在表示中引入了多少间址。使用四元式表示，定义或使用临时变量的三地址语句可通过符号表直接访问该临时变量的地址使用四元式的一个更重要的好处体现在优化编译器中。在三元式中，如果要移动一条临时值的语句需要改变arg1和arg2数组中对该语句的引用。间接三元式没有上述问题。间接三元式看上去和四元式非常相似，他们都需要大约相同的存储空间，并且对代码重新排序的效率相同。对于普通三元式，必须将对那些临时变量的存储分配推迟到代码生成阶段。三地址代码三地址代码：a=bOPc最多有三个地址(可以少于三个)通常写成四元组：(a,b,c,OP)例子：例子怎么翻译对于有嵌套的语言结构：嵌套的if和while语句需要一个算法来进行翻译解决方案：从AST描述开始对AST中的每个结点定义翻译方法遍历AST中的每一个结点的翻译表达式的翻译二元操作符t=T[e1OPe2](数学运算符和关系比较符号)一元操作符:t=T[OPe]布尔表达式的翻译t=T[e1ORe2]对于最为选择的OR表达