搜索
编译原理第七章语义分析和中间代码生成编译原理第2页语义分析和中间代码产生紧接在词法分析和语法分析之后，编译程序要做的工作就是进行静态语义检查和翻译。静态语义检查(1)类型检查。如果操作符作用于不相容的操作数，编译程序必须报告出错信息。(2)控制流检查。控制流语句必须使控制转移到合法的地方。(3)一致性检查。在很多场合要求对象只能被定义一次。(4)相关名字检查。其它如名字的作用域分析等。编译原理第3页语义分析和中间代码产生使用中间语言的好处(1)便于进行与机器无关的代码优化工作；(2)使编译程序改变目标机更容易；(3)使编译程序的结构在逻辑上更为简单明确。以中间语言为界面，编译前端和后端的接口更清晰。编译原理第4页语义分析和中间代码产生编译原理第5页语义分析和中间代码产生本章内容目录中间语言后缀式图表示法三地址代码说明语句过程中的说明谙旬保留作用域信息记录中的域名赋值语句的翻译简单算术表达式及赋值语句数组元素的引用布尔表达式的翻译数值表示法作为条件控制的布尔式翻译控制语句的翻译编译原理第6页语义分析和中间代码产生中间语言几种常见的中间语言形式后缀式三地址代码（包括三元式、四元式、间接三元式）DAG图表示编译原理第7页语义分析和中间代码产生后缀式后缀式表示法又称逆波兰表示法。这种表示法是把运算量（操作数）写在前面，把算符写在后面（后缀）。例如，把a十b写成ab＋，把a*b写成ab*。编译原理第8页语义分析和中间代码产生一个表达式E的后缀形式(1)如果E是一个变量或常量，则E的后缀式是E自身。(2)如果E是E1opE2形式的表达式，这里op是任何二元操作符，则E的后缀式为E1′E2′op，这里E1′和E2′分别为E1和E2的后缀式。(3)如果E是（E1）形式的表达式，则E1的后缀式就是E的后缀式。后缀式表示法用不着使用括号。根据运算量和算符出现的先后位置，以及每个算符的目数，就完全决定了一个表达式的分解。编译原理第9页语义分析和中间代码产生只要知道每个算符的目数，对于后缀式，不论从哪一端进行扫描，都能对它正确进行唯一分解。编译原理第10页语义分析和中间代码产生图表示法包括DAG与抽象语法树无循环有向图（DirectedAcycliGraph简称DAG）。与抽象语法树一样，对表达式中的每个子表达式，DAG中都有一个结点。一个内部结点代表一个操作符，它的孩子代表操作数。与抽象语法树不同的是，在一个DAG中代公共子表达式的结点具有多个父结点，而在一棵抽象语法树中公共子表达式被表示为重复的子树。编译原理第11页语义分析和中间代码产生例如，表达式a+a*(b-c)+(b-c)*d编译原理第12页语义分析和中间代码产生例如，表达式a+a*(b-c)+(b-c)*d编译原理第13页语义分析和中间代码产生编译原理第14页语义分析和中间代码产生编译原理第15页语义分析和中间代码产生后缀式即是对抽象语法树的后续遍历序列例：上图中的抽象语法树的后缀式是：abcuminus*bcuminu*+assign抽象语法树的边没有显式地出现在后缀式中，这些边可以根据结点出现的次序及表示操作符的结点要求操作数的个数还原出来。编译原理第16页语义分析和中间代码产生编译原理第17页语义分析和中间代码产生编译原理第18页语义分析和中间代码产生三地址代码三地址代码是由下面一般形式的语句构成的序列：x：=yopz其中,x,y,z为名字、常数或编译时产生的临时变量；op代表运算符号如定点运算符、浮点运算符、逻辑运算符等等。每个语句的右边只能有一个运算符。例如，源语言表达式x＋y*z可以被翻译为如下语句序列：T1：＝y*zT2：＝x＋T1其中，Tl，T2为编译时产生的临时变量。编译原理第19页语义分析和中间代码产生三地址代码可以看成是抽象语法树或DAG的一种线性表示。编译原理第20页语义分析和中间代码产生三地址语句类似于汇编语言代码。语句可以带有符号标号，而且存在各种控制流语句。符号标号代表存放中间代码的数组中三地址代码语句的下标。下面列出所使用的三地址语句的种类。（1)形如x:＝yopz的赋值语句，其中op为二元算术算符或逻辑算符。(2)形如x:＝opy的赎值语句，其中op为一元算符，如一元减ununus,逻辑非not,移位算符及转换算符（如将定点数转换成浮点数）。(3)形如x:=y的复制语句，它将y的值赋给x。(4)形如gotoL的无条件转移语句，即下一条将被执行的语句是带标号L的三地址语句。编译原理第21页语义分析和中间代码产生(5)形如ifxrelopygotoL或ifagotoL的条件转移语句。第一种形式语句施用关系运算符号relop（如＜，＝，＞，=等等）于x和y,若x与y满足关系relop,那么下面就执行带标号L的语句，否则下面就继续执行if语句之后的语句。第二种形式的语句中，a为布尔变量或常量，若a为真，则执行带标号L的语句，否则执行后一条语句。(6)用于过程调用的语句paramx和callp,n,以及返回语句returny.源程序中的过程调用语句P(xl，x2，…，xn）通常产生如下的三地址代码：paramx1paramx2……paramxncallp,n其中n表示实参个数。过程返回语句retumy中y为过程返回的一个值。编译原理第22页语义分析和中间代码产生(7)形如x:=y[i]及x[i]:=y的索引赋值。前者把相对于地址y的后面第i个单元里的值赋给x。后者把y的值赋给相对于地址x后面的第i个单元。（8）形如x:=&y,x:=*y和*x:=y的地址和指针赋值。其中第一个赋值语句把y的地址赋给x。假定y是个名字，或者是一个临时变量，代表一个具有左值的表达式，例如A[i,j]；并且x是一个指针名字或临时变量。也就是说,x的右值将被赋予对象y的左值。第二个赋值语句x:=*y，假定y是一个指针或者是一个其右值为地址的临时变量。此语句执行的结果是把y所指示的地址单元里存放的内容赋给x.第三个赋值语句*x:=y,将把x所指向的对象的右值赋给y的右值。编译原理第23页语义分析和中间代码产生在设计中间代码形式时，运算符的选择是非常重要的。显然，算符种类应足以用来实现源语言中的运算。一个小型算符集合较易于在新的目标机器上实现。然而，用局限的指令集合会使某些源语言运算表示成中间形式时代码加长，从而需要在目标代码生成时做较多的工作以获得高效的代码。编译原理第24页语义分析和中间代码产生生成三地址代码时，临时变量的名字对应抽象语法树的内部结点。对于产生式E→E1＋E2的左端的非终结符号E而言，它的经过计算得出的值往往放到一个新的临时变量T中。一般说来，赋值语句id:=E的三地址代码包括：对表达式E求值并置于变量T中，然后进行赋值id.place:=T.如果一个表达式仅有一单个标识符，例如Y,则由Y自身保留表达式的值。编译原理第25页语义分析和中间代码产生下表是为赋值语句生成三地址代码的S-属性文法定义。如给定输入a:=b*-c+b*-c。非终结符号S有综合属性S.code,它代表赋值语句S的三地址代码。非终结符号E有如下两个属性：（1)E.place表示存放E值的名字；(2)E.code表示对E求值的三地址语句序列。函数newtemp的功能是，每次调用它时，将返回一个不同临时变量名字，如T1，T2，…。为了方便，我们在表使用gen(x‘：＝’y‘+’z)表示生成三地址语句x:=y十z.代替x,y或z出现的表达式在传递给gen时求值，用单引号括起来的运算符或操作数将保留引号里字面的符号。编译原理第26页语义分析和中间代码产生编译原理第27页语义分析和中间代码产生三地址语句可看成中间代码的一种抽象形式。编译程序中，三地址代码语句的具体实现可以用记录表示，记录中包含表示运算符和操作数的域。通常有三种表示方法：四元式、三元式、间接三元式。编译原理第28页语义分析和中间代码产生四元式一个四元式是一个带有四个域的记录结构，这四个域分别称为op、arg1,arg2及result.域op包含一个代表运算符的内部码。三地址语句x:＝yopz可表示为：将y置于argl域，置于arg2域，x置于result域，：＝为算符。带有一元运算符的语句如：x:=-y或者x:=y的表示中不用arg2.而像param这样的运算符仅使用argl域。条件和无条件转移语句将目标标号置于result域中。编译原理第29页语义分析和中间代码产生三元式为了避免把临时变量填入到符号表，可以通过计算这个临时变量值的语句的位置来引用这个临时变量。这样表示三地址代码的记录只需三个域：op、argl和arg2编译原理第30页语义分析和中间代码产生编译原理第31页语义分析和中间代码产生间接三元式为了便于代码优化处理，有时不直接使用三元式表，而是另设一张指示器（称为间接码表），它将按运算的先后顺序列出有关三元式在三元表中的位置。换句话说就是，用一张间接码表辅以三元式表的办法来表示中间代码。这种表示法称为间接三元式。编译原理第32页语义分析和中间代码产生例如，语句X:=（A＋B）*C；Y:=D↑（A＋B)的间接三元式表示如表所示。编译原理第33页语义分析和中间代码产生四元式与三元式和间接三元式作一些比较四元式之间的联系是通过临时变量实现的。这一点和三元式不同。要更动一张三元表是很困难的，它意味着必须改变其中一系列指示器的值。但要更动四元式表是很容易的，因为调整四元式之间的相对位置并不意味着必须改变其中一系列指示器的值。因此，当需要对中间代码进行优化处理时，四元式比三元式要方便得多。对优化这一点而言，四元式和间接三元式同样方便。编译原理第34页语义分析和中间代码产生说明语句当考查一个过程或分程序的一系列说明语句时，便可为局部于该过程的名字分配存储空间。对每个局部名字，我们都将在符号表中建立相应的表项，并填入有关的信息如类型、在存储器中的相对地址等。相对地址是指对静态数据区基址或活动记录中局部数据区基址的一个偏移量。编译原理第35页语义分析和中间代码产生当产生中间代码地址时，对目标机一些情况做到心中有数是有好处的。例如，假定在一个以字节编址的目标机上，整数必须存放在4的倍数的地址单元，那么，计算地址时就应以4的倍数增加。编译原理第36页语义分析和中间代码产生过程中的说明语句在C,Pascal及FORTRAN等语言的语法中，允许在一个过程中的所有说明语句作为一个组来处理，把它们安排在一所数据区中。从而需要一个全程变量如offset来跟踪下一个可用的相对地址的位置。编译原理第37页语义分析和中间代码产生在下图关于说明语句的翻译模式中，非终结符号P产生一系列形如id：T的说明语句。在处理第一条说明语句之前，先置offset为0，以后每次遇到一个新的名字，便将该名字填入符号表中并置相对地址为当前offset之值，然后使offset加上该名字所表示的数据对象的域宽。编译原理第38页语义分析和中间代码产生编译原理第39页语义分析和中间代码产生过程enter(name,type,offset）用来把名字name填入到符号表中，并给出此名字的类型type及在过程数据区中的相对地址offset。非终结符号T有两个综合属性T.type和T.width，分别表示名字的类型和名字的域宽（即该类型名字所占用的存储单元个数）。在图中,假定整数类型域宽为4；实数域宽为8;一个数组的域宽可以通过把数组元素数目与一个元素的域宽相乘获得；每个指针类型的域宽假定为4.编译原理第40页语义分析和中间代码产生如果把图中的第一条产生式及其语义动作写在一行，则对offset赋初值更明显，如下式所示：P→｛offset:=0｝D（7．1）前面曾谈到产生ε的标记非终结符号，可以用它来重新改写上述产生式以便语义动作均出现在整个产生式的右边。我们可采用标记非终结符号M来重写式（7.1）：P→MDM→ε{offset:=0}编译原理第41页语义分析和中间代码产生保留作用域信息允许嵌套过程的语言，对于每一个过程，其中局部名字的相对地址计算可以采用图7.6的方法。而当遇到一个嵌入的过程说明