【精品】【考研计算机专业课】天津大学 编译原理ppt课件 part7语义分析与中间代码生成（可编辑.ppt

【考研计算机专业课】天津大学 编译原理PPT课件 Part7语义分析与中间代码生成语义分析的位置和作用语义分析的位置和作用紧跟在语法分析和语法分析之后，编译程序要做的工紧跟在语法分析和语法分析之后，编译程序要做的工作就是进行静态语义检查和翻译。作就是进行静态语义检查和翻译。编译器必须要检查源程序是否符合源语言规定的语法编译器必须要检查源程序是否符合源语言规定的语法和语义要求。这种检查称为静态检查，检查并报告程和语义要求。这种检查称为静态检查，检查并报告程序中某些类型的错误。序中某些类型的错误。语法分析器语法分析器记号流记号流类型检查器类型检查器语法树语法树中间代码中间代码生成器生成器语法树语法树中间表示中间表示静态语义检查静态语义检查静态语义检查通常包括：静态语义检查通常包括：类型检查：如果操作符作用于不相容的操作数，编译类型检查：如果操作符作用于不相容的操作数，编译器应该报错器应该报错控制流检查：引起控制流从某个结构中跳转出来的语控制流检查：引起控制流从某个结构中跳转出来的语句必须能够决定控制流转向的目标地址句必须能够决定控制流转向的目标地址唯一性检查：有时，有的对象只能被定义一次。比如，唯一性检查：有时，有的对象只能被定义一次。比如，同一同一case语句的标号不能相同，枚举类型的元素不能重语句的标号不能相同，枚举类型的元素不能重复。复。与名字相关的检查：有时候要求同一名字在特定位置与名字相关的检查：有时候要求同一名字在特定位置出现两次或多次（如，标识结构的开始和结尾）出现两次或多次（如，标识结构的开始和结尾）中间语言中间语言源语言的中间表示方法源语言的中间表示方法抽象语法树抽象语法树后缀式后缀式三地址代码（包括三元式、四元式、间接三元式）三地址代码（包括三元式、四元式、间接三元式）DAG图表示图表示图表示法图表示法图表示法主要包括图表示法主要包括DAG(Directed Acyclic Graph)与抽象语法树与抽象语法树语法树描述了源程序的自然层次结构。语法树描述了源程序的自然层次结构。DAG以更紧凑的形式给出了相同的以更紧凑的形式给出了相同的信息。两者不同的是：信息。两者不同的是：在一个在一个DAG中代表公共子表达式的结点具有多个父结点中代表公共子表达式的结点具有多个父结点在一颗抽象语法树中公共子表达式被表示为重复的子树。在一颗抽象语法树中公共子表达式被表示为重复的子树。assign+a*uminusbcuminusbca:=b*-c+b*-cassign+a*uminusbcabc uminus*bc numinus*+assign抽象语法树抽象语法树语法树中的边不会显式的出现在后缀表达式中，可以根据结点出现的顺序语法树中的边不会显式的出现在后缀表达式中，可以根据结点出现的顺序及结点上的操作符所要求的操作数的个数来恢复。其恢复过程类似使用栈及结点上的操作符所要求的操作数的个数来恢复。其恢复过程类似使用栈对后缀表达式求值。对后缀表达式求值。如果函数如果函数mknode(op,child)和和mknode(op,left,right)尽可能返回一个指向一尽可能返回一个指向一个存在的结点的指针以代替建立新的结点，那么就会生成个存在的结点的指针以代替建立新的结点，那么就会生成DAG图。图。产生式产生式语义规则语义规则Sid:=ES.nptr:=mknode(assign,mkleaf(id,id.place),E.nptr)EE1+E2E.nptr:=mknode(+,E1.nptr,E2.nptr)EE1*E2E.nptr:=mknode(*,E1.nptr,E2.nptr)E-E1E.nptr:=mknode(uminus,E1.nptr)E(E1)E.nptr:=E1.nptr EidE.nptr:=mkleaf(id ,id.place)抽象语法树的表示形式抽象语法树的表示形式assignida+*uminusuminusidbidbidcidc0idb1idc2uminus13*024idb5idc6uminus57*468+379ida10assign9811三地址代码三地址代码三地址代码是下列一般形式的语句序列三地址代码是下列一般形式的语句序列x:=y op z其中，其中，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:=y op z的赋值语句，其中的赋值语句，其中op为二元算术算符或为二元算术算符或逻辑算符逻辑算符形如形如x:=op y的赋值语句，其中的赋值语句，其中op为一元算符。为一元算符。形如形如x:=y的复制语句，将的复制语句，将y的值赋给的值赋给x形如形如goto L的无条件跳转语句，即下一条将被执行的语的无条件跳转语句，即下一条将被执行的语句是带有标号句是带有标号L的三地址语句的三地址语句三地址语句的类型三地址语句的类型下面列出本书中使用的三地址语句的种类：下面列出本书中使用的三地址语句的种类：形如形如if x relop y goto L或或 if a goto L的条件跳转语句。的条件跳转语句。第一种形式使用关系运算符号第一种形式使用关系运算符号relop（等）等）第二种第二种a为布尔变量或常量为布尔变量或常量用于过程调用的语句用于过程调用的语句param x和和call p,n，以及返回语句，以及返回语句return y。源程序中的过程调用源程序中的过程调用p(x1,x2,xn)：param x1param x2param x2call p,n n表示实参个数。表示实参个数。return y中中y为过程返回的一个值为过程返回的一个值三地址语句的类型三地址语句的类型下面列出本书中使用的三地址语句的种类：下面列出本书中使用的三地址语句的种类：形如形如x:=yi及及xi:=y的索引赋值。的索引赋值。形如形如x:=&y,x:=*y和和*x:=y的地址和指针赋值。的地址和指针赋值。设计中间代码形式时，运算符的选择是非常重要的。设计中间代码形式时，运算符的选择是非常重要的。算符种类应足以用来实现源语言中的运算。算符种类应足以用来实现源语言中的运算。一个小型算符集合较易于在新的目标机器上实现。一个小型算符集合较易于在新的目标机器上实现。局限的指令集合会使某些源语言运算表示成中间形式局限的指令集合会使某些源语言运算表示成中间形式时代码加长，需要在目标代码生成时做较多的优化工时代码加长，需要在目标代码生成时做较多的优化工作。作。生成三地址码的生成三地址码的S-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-属性文法属性文法产生式产生式语义规则语义规则Sid:=ES.code:=E.code|gen(id.place :=E.place)EE1+E2E.place:=newtemp;E.code:=E1.code|E2.code|gen(E.place:=E1.place +E2.place)EE1*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.codeEidE.place:=id.place E.code:=如何加入控制语句如何加入控制语句SWhile E do S1SWhile E do S1对应的语义规则是：对应的语义规则是：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.codeif E.place=0 goto S.afterS1.codegoto S.beginS.begin:S.begin:三地址语句的实现三地址语句的实现三地址语句是中间代码的一种抽象形式。三地址语句是中间代码的一种抽象形式。这些语句可以以带有操作符和操作数域的记录来实现。这些语句可以以带有操作符和操作数域的记录来实现。四元式、三元式及简介三元式是三种这样的表示。四元式、三元式及简介三元式是三种这样的表示。四元式四元式一个四元式是带有四个域的记录结构，这四个域分别一个四元式是带有四个域的记录结构，这四个域分别称为称为op,arg1,arg2及及result。域域op包含一个代表运算符的内部码包含一个代表运算符的内部码三地址语句三地址语句x:=y op z通过将通过将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)xi:=yx:=yi间接三元式间接三元式为了便于代码优化处理，有时不直接使用三元式表，为了便于代码优化处理，有时不直接使用三元式表，而是另设一张指示器（称为间接码表），它将运算的而是另设一张指示器（称为间接码表），它将运算的先后顺序列出有关三元式在三元表中的位置。先后顺序列出有关三元式在三元表中的位置。换句话说，我们用一张间接码表辅以三元式表的办法换句话说，我们用一张间接码表辅以三元式表的办法来表示中间代码。这种表示方法称为间接三元式。来表示中间代码。这种表示方法称为间接三元式。间接三元式举例间接三元式举例X:=(A+B)*C Y:=D(A+B)oparg1arg2(1)+AB(2)*(1)C(3):=X(2)(4)D(1)(5):=Y(4)间接代码间接代码(1)(2)(3)(1)(4)(5)(1)(2)(3)(1)(4)(5)当在代码优化过程中需要调整运算顺序时，当在代码优化过程中需要调整运算顺序时，只需重新安排间接码表，无需改动三元式只需重新安排间接码表，无需改动三元式表表对于间接三元式表示，语义规则中应增添对于间接三元式表示，语义规则中应增添产生间接码表的动作，并且在向三元式表产生间接码表的动作，并且在向三元式表填进一个三元式之前，必须先查看一下此填进一个三元式之前，必须先查看一下此式是否已在其中，就无须填入。式是否已在其中，就无须填入。表示方法比较：间址的使用表示方法比较：间址的使用三元式与四元式的差异可以看作在表示中引入了多少间址。三元式与四元式的差异可以看作在表示中引入了多少间址。使用四元式表示，定义或使用临时变量的三地址语句可通过符号使用四元式表示，定义或使用临时变量的三地址语句可通过符号表直接访问该临时变量的地址表直接访问该临时变量的地址使用四元式的一个更重要的好处体现在优化编译器中。在三元式使用四元式的一个更重要的好处体现在优化编译器中。在三元式中，如果要移动一条临时值的语句需要改变中，如果要移动一条临时值的语句需要改变arg1和和arg2数组中对数组中对该语句的引用。该语句的引用。间接三元式没有上述问题。间接三元式没有上述问题。间接三元式看上去和四元式非常相似，他们都需要大约相同的间接三元式看上去和四元式非常相似，他们都需要大约相同的存储空间，并且对代码重新排序的效率相同。存储空间，并且对代码重新排序的效率相同。对于普通三元式，必须将对那些临时变量的存储分配推迟到代对于普通三元式，必须将对那些临时变量的存储分配推迟到代码生成阶段。码生成阶段。说明语句说明语句声明语句引起的翻译动作声明语句引起的翻译动作当过程或程序块内部的声明语句被考察的时候，我们当过程或程序块内部的声明语句被考察的时候，我们需要为需要为局部局部于该过程的名字分配存储空间。于该过程的名字分配存储空间。对每个局部名字，都将在符号表中创建一个表项，对每个局部名字，都将在符号表中创建一个表项，填写类型、相对存储地址等相关信息填写类型、相对存储地址等相关信息相对地址指相对于静态数据区基址或活动记录基址的偏相对地址指相对于静态数据区基址或活动记录基址的偏移量移量单个过程中的声明语句单个过程中的声明语句允许嵌套过程中的声明语句允许嵌套过程中的声明语句单个过程中的声明语句单个过程中的声明语句变量和过程设计变量和过程设计设置全局变量：设置全局变量：offset，跟踪下一个可用的相对地址，跟踪下一个可用的相对地址过程过程enter(name,type,offset)为名字建立符号表表项为名字建立符号表表项综合属性综合属性type和和width说明非终结符说明非终结符T的类型及宽度（或该类型的对象所占用的类型及宽度（或该类型的对象所占用的内存数。的内存数。Poffset:=0 DDD;DDid:Tenter(id.name,T.type,offset);offset:=offset+T.width TintegerT.type:=integer;T.width:=4 TrealT.type:=real;T.width:=8Tarraynumof T1T.type:=array(num.val,T1.type);T.width:=num.val*T1.widthTT1T.type:=pointer(T1.type);T.width:=4Poffset:=0 DPMDD offset:=0允许嵌套过程中的声明语句允许嵌套过程中的声明语句PMDaddwidth(top(tblptr),top(offset);pop(tblptr);pop(offset)Mt=mktable(nil);push(t,tblptr);push(0,offset)DD1;D2Dproc id;N D1;S t:=top(tblptr);addwidth(t,top(offset);pop(tblptr);pop(offset);enterproc(top(tblptr),id.name,t)Did:Tenter(top(tblptr),id.name,T.type,top(offset);top(offset:=top(offset)+T.widthN t:=mktable(top(tblptr);push(t,tblptr),push(0,offset)M的动作用于初始化栈的动作用于初始化栈tblptr，将，将相对地址相对地址0压入栈压入栈offset当出现一个过程声明时，当出现一个过程声明时，N的动作的动作和和M的动作基本相同的动作基本相同对每个变量声明，不改变对每个变量声明，不改变tblptr，但是要改变但是要改变offset的栈顶指针。的栈顶指针。记录中的域名记录中的域名当看到关键字当看到关键字record之后，与标记之后，与标记L相关联的动作为相关联的动作为域名创建一个新的符号表。指向该符号表的指针被压域名创建一个新的符号表。指向该符号表的指针被压入栈入栈tblptr，相对地址，相对地址0被压入栈被压入栈offset。Trecord D endTrecord L D endT.type:=record(top(tblptr);T.width:=top(offset);pop(tblptr);pop(offset)Lt=mktable(nil);push(t,tblptr);push(0,offset)赋值语句赋值语句赋值语句赋值语句赋值语句中表达式的类型赋值语句中表达式的类型整型整型实型实型数组数组记录记录将赋值语句转换为三地址码要做的工作将赋值语句转换为三地址码要做的工作在符号表中查找名字在符号表中查找名字存取数组及记录中的元素存取数组及记录中的元素符号表中的名字符号表中的名字lookup 操作支持最近嵌套原操作支持最近嵌套原则。则。其上下文是由前面定义的过其上下文是由前面定义的过程，当作用于程，当作用于name时，需要时，需要先检查先检查name是否已经在符号是否已经在符号表中定义过了。表中定义过了。PMDMDD1;D2|Dproc id;N D1;S|Did:TN Sid:=Ep:=lookup(id.name);if p nuil then emit(p:=E.place)else errorEE1+E2E.place:=newtemp;emit(E.place:=E1.place+E2.place E E1*E2E.place:=newtemp;emit(E.place:=E1.place*E2.place E-E1 E.place:=newtemp;emit(E.place:=uminus E1.place E(E1)emit(E.place:=E1.place Eidp:=lookup(id.name);if p nil then E.place:=p;else error寻址数组元素寻址数组元素如果数组元素存放在连续的存储块中，数组元素可以如果数组元素存放在连续的存储块中，数组元素可以迅速的访问。每个数组元素的宽度是迅速的访问。每个数组元素的宽度是w，则，则一维数组一维数组Ai的地址：的地址：base+(i-low)*w二维数组二维数组Ai1,i2的地址：的地址：base+(i1-low1)*n2+i2-low2)*w，可以改写为可以改写为(i1*n2)+i2)*w+(base-(low1*n2)+low2)*w)多维数组多维数组Ai1,i2,ik的地址：的地址：(i1n2+i2)*n3+i3)nk+ik)*w+base-(low1n2+low2)*n3+low3)nk+lowk)*w将数组名与最左边的下标表达式连在一起。使得产生式允许将将数组名与最左边的下标表达式连在一起。使得产生式允许将符号表中指向数组名表项的指针作为符号表中指向数组名表项的指针作为Elist的综合属性的综合属性array进进行传递。行传递。(i1n2+i2)n3+i3)nm+im)使用如下递归公式计算：使用如下递归公式计算：e1=i1em=em-1*nm+imL有两个属性，有两个属性，L.place和和L.offset，当，当L是简单名字时，是简单名字时，L.place是指向符号表中该名字表项的指针，而是指向符号表中该名字表项的指针，而L.offset是是nullLidElist|idElistElist,E|ELElist|idElistElist,E|idE数组元素寻址的翻译模式数组元素寻址的翻译模式如果如果L是简单名字，则生成一般的赋值，否则生成对是简单名字，则生成一般的赋值，否则生成对L所指位置的索引赋值。所指位置的索引赋值。(1)SL:=E if L.offset=null thenemit(L.place:=E.place);else emit(L.place L.offset :=E.place)(2)EE1+E2E.place:=newtemp;emit(E.place:=E1.place+E2.place)(3)E(E1)E.place:=E1.place(4)ELif L.offset=null thenE.place:=L.place else beginE.place:=newtemp;emit(E.place:=L.place L.offset 0 end(1)SL:=E(2)EE+E(3)E(E)(4)EL(5)LElist(6)Lid(7)ElistElist,E(8)Elist idE数组元素寻址的翻译模式数组元素寻址的翻译模式(5)LElist L.place:=newtemp;L.offset:=newtemp;emit(L.place:=c(Elist.array)emit(L.offset:=Elist.place*width(Elist.array)(6)LidL.place:=id.place;L.offset:=null(7)ElistElist1,E)t:=E.place:=E1.place m:=Elist1.ndim+1;emit(t:=Elist1.place*limit(Elist1.arry,m);emit(t:=t+E.place);Elist.array:=Elist1.array;Elist.place:=t;Elist.ndim:=m(8)ElistidEElist.arry:=id.place;Elist.place:=E.place;Elist.ndim:=1(1)SL:=E(2)EE+E(3)E(E)(4)EL(5)LElist(6)Lid(7)ElistElist,E(8)Elist idE赋值语句中的类型转换赋值语句中的类型转换变量和常量有许多不同的类型，因而编译器或者拒绝变量和常量有许多不同的类型，因而编译器或者拒绝某种混合类型的操作，或者生成适当的强制（类型转某种混合类型的操作，或者生成适当的强制（类型转换）指令。换）指令。假设有两种类型：假设有两种类型：EE1+E2E.type:=if E1.type=integer and E2.type=integer then integer else real赋值语句中的类型转换赋值语句中的类型转换(1)SL:=E(2)EE+E(3)E(E)(4)EL(5)LElist(6)Lid(7)ElistElist,E(8)Elist idEE.Place:=newtemp;if E1.type=integer and E2.type=integer then begin emit(E.place:=E1.place int+E2.place);E.type:=integerendelse if E1.type=real and E2.type=real then begin emit(E.place:=E1.place real+E2.place);E.type:=realendelse if E1.type=integer and E2.type=real then begin u:=newtemp;emit(u:=inttoreal E1.place;emit(E.place:=u real+E2.place);E.type:=realendelse if E1.type=real and E2.type=integer then begin u:=newtemp;emit(u:=inttoreal E2.place;emit(E.place:=E1.place real+u);E.type:=realendelse E.type:=type_error;布尔表达式的翻译布尔表达式的翻译布尔表达式的作用布尔表达式的作用用作计算逻辑值用作计算逻辑值用作控制语句（如用作控制语句（如if语句，语句，while语句等）语句等）布尔表达式和关系表达式布尔表达式和关系表达式布尔表达式是用布尔运算符作用到布尔变量或关系表布尔表达式是用布尔运算符作用到布尔变量或关系表达式上而组成的。（达式上而组成的。（not、and、or）关系表达式是有关系运算符连接的算术表达式关系表达式是有关系运算符连接的算术表达式布尔表达式值的计算布尔表达式值的计算如同计算算术表达式一样，一步不差的从表达式各部如同计算算术表达式一样，一步不差的从表达式各部分的值计算出整个表达式的值分的值计算出整个表达式的值采用优化措施计算布尔表达式的值采用优化措施计算布尔表达式的值计算计算A or B时，如果时，如果A为真，则不用计算为真，则不用计算B，结果为真，结果为真计算计算A and B时，如果时，如果A为假，不用计算为假，不用计算B，结果为假，结果为假一般的计算公式如下：一般的计算公式如下：A or B：if A then true else BA and B：if A then B else falsenot A：if A then false else true用上述两种方法把布尔表达式翻译成地址代码用上述两种方法把布尔表达式翻译成地址代码EE1 or E2E.place:=newtemp;emit(E.place:=E1.place or E2.place E E1 and E2E.place:=newtemp;emit(E.place:=E1.place and E2.place Enot E1E.place:=newtemp;emit(E.place:=not E1.place E(E1)E.place:=E1.place Eid1 relop id2E.place:=newtemp;emit(if id1.place relop.op id2.place goto nextstat+3);emit(E.place:=0);emit(goto nextstat+2);emit(E.place:=1)EidE.plece:=id.placeab or cd and ef100:if ab goto 103107:T2:=1101:T1:=0108:if ef goto 111102:goto 104109:T3:=0103:T1:=1110:goto 112104:if cc or bc goto L2goto L1L1:if bd goto L2goto L3L2:(S1的三地址码序列的三地址码序列)goto LnestL3:(S2的三地址码序列的三地址码序列)Lnext:产生布尔表达式三地址代码的语义规则产生布尔表达式三地址代码的语义规则函数函数newlabel产生新的符号标号产生新的符号标号if E then S1 else S2。假定假定E形如形如ab，则将生成如下，则将生成如下E的代码：的代码：if ab goto E.truegoto E.false对于上述翻译的讨论：对于上述翻译的讨论：如果如果E为为E1 or E2，如果，如果E1为真，则立即可知为真，则立即可知E为真，于为真，于是是E1.true与与E.true是相同的；若是相同的；若E1为假，则必须对为假，则必须对E2求求值，因此我们置值，因此我们置E1.false为为E2的代码的第一条指令的标的代码的第一条指令的标号，而号，而E2的真假出口可以分别与的真假出口可以分别与E的真假出口相同。的真假出口相同。产生式产生式语义规则语义规则EE1 or E2E1.true:=E.true;E1.false:=newlabel;E2.true:=E.true;E2.false:=E.false;E.code:=E1.code|gen(E1.false:)|E2.codeEE1 and E2E1.true:=newlabel;E1.false:=E.false;E2.true:=E.true;E2.false:=E.false;E.code:=E1.code|gen(E1.true:)|E2.codeEnot E1E1.true:=E.false;E1.false:=E.true;E.code:=E1.codeE(E1)E1.true:=E.true;E1.false:=E.false;E.code:=E1.codeEid1 relop id2E.code:=gen(if id1.place relop.op id2.place goto E.true)|gen(goto E.false)EtrueE.code:=gen(goto E.true)EfalseE.code:=gen(goto E.false)类型检查类型检查类型检查概述类型检查概述编译器必须要检查源程序是否符合源语言规定的语法编译器必须要检查源程序是否符合源语言规定的语法和语义要求。这种检查称为静态检查，检查并报告程和语义要求。这种检查称为静态检查，检查并报告程序中某些类型的错误，包括：序中某些类型的错误，包括：类型检查：如果操作符作用于不相容的操作数，编译类型检查：如果操作符作用于不相容的操作数，编译器应该报错器应该报错控制流检查：引起控制流从某个结构中跳转出来的语控制流检查：引起控制流从某个结构中跳转出来的语句必须能够决定控制流转向的目标地址句必须能够决定控制流转向的目标地址唯一性检查：有时，有的对象只能被定义一次。唯一性检查：有时，有的对象只能被定义一次。与名字相关的检查：有时候要求同一名字在特定位置与名字相关的检查：有时候要求同一名字在特定位置出现两次或多次出现两次或多次类型检查概述类型检查概述前面描述的一些工作可以并入其他活动中。前面描述的一些工作可以并入其他活动中。唯一性检查可以在将名字信息填入符号表时进行。唯一性检查可以在将名字信息填入符号表时进行。一些静态检查和中间代码生成同语法分析结合在一起一些静态检查和中间代码生成同语法分析结合在一起代码生成器需要类型检查器所收集的信息代码生成器需要类型检查器所收集的信息重载，可能伴随有强制类型转换，以便编译器把操作重载，可能伴随有强制类型转换，以便编译器把操作数转化为上下文所期望的类型数转化为上下文所期望的类型多态，函数体可以用不同类型的参数来执行。多态，函数体可以用不同类型的参数来执行。类型系统类型系统类型检查器的设计基于如下规则类型检查器的设计基于如下规则语言中语法结构的信息语言中语法结构的信息类型的概念类型的概念语言结构的类型指派规则语言结构的类型指派规则C语言中类型分为基本类型和构造类型语言中类型分为基本类型和构造类型基本类型和其它构造类型可以用来构造新类型基本类型和其它构造类型可以用来构造新类型指针和函数也可以看成构造类型指针和函数也可以看成构造类型类型表达式类型表达式类型表达式的构成类型表达式的构成基本类型基本类型类型构造符类型构造符类型表达式的构造方法类型表达式的构造方法基本类型是类型表达式，基本类型包括基本类型是类型表达式，基本类型包括boolean、char、integer和和real；特殊的基本类型；特殊的基本类型type_error，以及，以及void。因为可以为类型表达式命名，所以类型名也是类型表达式。因为可以为类型表达式命名，所以类型名也是类型表达式。由类型构造符作用于类型表达式而形成的表达式也是类型表达式。由类型构造符作用于类型表达式而形成的表达式也是类型表达式。基本类型集和构造符依赖于被检查的语言基本类型集和构造符依赖于被检查的语言类型表达式类型表达式类型构造器包括类型构造器包括数组。如果数组。如果T是表达式类型，那么是表达式类型，那么array(I,T)就是表示元素类型为就是表示元素类型为T，下标集合为，下标集合为I的数组类型的类型表达式。其中的数组类型的类型表达式。其中I通常是一个整通常是一个整数区间数区间乘积。如果乘积。如果T1和和T2是类型表达式，则其笛卡尔积是类型表达式，则其笛卡尔积T1T2 也是类型也是类型表达式。假设表达式。假设是左结合的是左结合的记录。记录和乘积的区别是记录中的域有名字。类型构造符记录。记录和乘积的区别是记录中的域有名字。类型构造符record将作用于由域名和域类型组成的元组。将作用于由域名和域类型组成的元组。指针。如果指针。如果T是类型表达式，那么是类型表达式，那么pointer(T)也是类型表达式。也是类型表达式。函数。从定义域类型函数。从定义域类型D到值域类型到值域类型R的映射。可以用类型表达式的映射。可以用类型表达式DR来表示。来表示。类型表达式可以包含其值为类型表达式的变量。类型表达式可以包含其值为类型表达式的变量。类型系统类型系统类型系统是将类型表达式指派到程序各部分的一组规则。类型类型系统是将类型表达式指派到程序各部分的一组规则。类型检查器用来实现类型系统检查器用来实现类型系统由编译器完成的检查成为静态检查，而在目标程序运行时完成由编译器完成的检查成为静态检查，而在目标程序运行时完成的检查则称为动态检查。只要目标代码中含有足够的类型信息，的检查则称为动态检查。只要目标代码中含有足够的类型信息，类型检查总可以动态进行。类型检查总可以动态进行。健全的类型系统健全的类型系统能静态的确定在目标程序运行时不会发生错误，因此不需要动态能静态的确定在目标程序运行时不会发生错误，因此不需要动态检查。检查。一个健全的类型系统将一个不是一个健全的类型系统将一个不是