第七章语义分析与中间代码生成.ppt

第七章 语义分析和中间代码产生 紧接在词法分析和语法分析之后，编译程序要做的工作就是进行静态语义检查和翻译。 静态语义检查通常包括： 1）类型检查 2）控制流检查 3）一致性检查 4）相关名字检查 其它如名字的作用域分析等也都是静态语义分析的工作。 虽然源程序可以直接翻译为目标语言代码，但是许多编译程序却采用了独立于机器的、复杂性介于源语言和机器语言之间的中间语言。这样的好处是： 1）便于进行与机器无关的代码优化工作； 2）使编译程序改变目标机更容易； 3）使编译程序的结构在逻辑上更为简单明确。以中间语言为界面，编译前端和后端的接口更清晰。 静态语义检查和中间代码产生在编译程序中的地位如图7.1 7.1中间语言 在6.2.4节中介绍了抽象语法树，它是源程序的中间表示方法之一。在此将介绍其它几种常见的中间语言形式。 常见的中间语言有：后缀式（逆波兰表示法），树型表示，三元式和四元式等。 7.1.1逆波兰表示法 逆波兰表示法是把运算量（操作数）写在前面，把算符写在后面（后缀），也称后缀表示法。 例如：a+b写成ab+, a*b写成ab* .用这种办法表示的表达式称为后缀式。 一个表达式E的后缀形式定义： 1）如果E是一个变量或常量，则E的后缀式是E自身。 2）如果E是E1 op E2形式的表达式，这里op是任何二元操作符，则E的后缀式为E1’E2’op ，这里E’和E2’分别为E1和E2的后缀式。 3）如果E是（E1）形式的表达式，则E1的后缀式就是E的后缀式。 逆波兰表示法用不着使用括号，根据运算量和算符出现的先后位置，以及每个算符的目数就完全决定一个表达式的分解。 例如： (a+b)*c将被表示成 ab+c* abc+* 所代表的表达式是a*(b+c) Ab+cd+* 所代表的表达式是(a+b)*(c+d) 把一般表达式翻译为后缀式是很容易的。表7.1给出了把表达式翻译为后缀式的语义规则描述，其中E.code表示E后缀形式，op表示任意二元操作符，“||”表示后缀形式的连接。 逆波兰表示法中栈的使用 后缀式的计值用栈实现非常方便，一般的计值过程是：自左至右扫描后缀式,每碰到运算量就把它推进栈，每碰到K目算符就把它作用于栈顶部的k个项，并用运算的结果来代替这k个项（运算的结果仅有一项）。 7.1.2图表示法 图表示法包括DAG与抽象语法树 无循环有向图DAG：与抽象语法树一样，对表达式中的每个子表达式，DAG中都有一个结点。一个内部结点代表一个操作符，它的孩子代表操作数。 不同点：在DAG中代表公共子表达式的结点具有多个父结点，而在一棵抽象语法树中公共子表达式被表示为重复的子树。 可见P167 7.1.3三地址代码 一般形式 x := y op z 其中 x, y, z 为变量名、常数或编译产生的临时变量； Op代表运算符号如定点运算符、浮点运算符、逻辑运算符等等。 每个语句的右边只能有一个运算符。例如，源语言表达式x+y*z可被翻译为如下语句序列： T1:=y*z T2:=x+T1 其中T1，T2为编译时产生的临时变量。 之所以称为三地址代码是因为每条语句通常包含三个地址，两个用来表示操作数，一个用来存放结果。对于后面给出的三地址代码中，用户定义的名字在实际实现时将由指乡符号表中的相应名字入口的指针所代替。 常用的三地址语句种类 1）x := y op z 双目运算 2）x := op y 单目运算 3）x := y 赋值 4）if x relop y goto l 条件转移 其他三地址种类 goto l 无条件转移 param x 实在参数 call p, n (n是参数个数) 过程调用 return x 过程返回 x := y[i] 数组运算 x[i] := y x := y 指针运算 x := *y *x = y 生成三地址代码时，临时变量的名字对应抽象语法树的内部结点。对于产生式E →E1+E2的左端的非终结符号E而言，它的经过计算得出的值往往放到一个新的临时变量T中。 赋值语句id:=E的三地址代码包括：对表达式E求值并置于变量T中，然后进行赋值id.place:=T。如果一个表达式仅有一个单个标示符，例如y,则由y自身保留表达式的值。 表7.3是为赋值语句生成三地址代码的S-属性文法定义。如给定输入a:=b*-c+b*-c。非终结符号S有综合属性S.code，它代表赋值语句S的三地址代码。非终结符号E有如下两个属性：