《编译原理第7章》由会员分享，可在线阅读，更多相关《编译原理第7章（85页珍藏版）》请在金锄头文库上搜索。
1、编译原理第七章 语义分析和中间代码生成编译原理第2页语义分析和中间代码产生l紧接在词法分析和语法分析之后，编译程序要做的工作就是 进行静态语义检查和翻译。 l静态语义检查(1)类型检查。如果操作符作用于不相容的操作数，编译程序必 须报告出错信息。(2)控制流检查。控制流语句必须使控制转移到合法的地方。 (3)一致性检查。在很多场合要求对象只能被定义一次。(4)相关名字检查。其它如名字的作用域分析等。编译原理第3页语义分析和中间代码产生l使用中间语言的好处(1)便于进行与机器无关的代码优化工作；(2)使编译程序改变目标机更容易；(3)使编译程序的结构在逻辑上更为简单明确。以中 间语言为界面，编译
2、前端和后端的接口更清晰。编译原理第4页语义分析和中间代码产生编译原理第5页语义分析和中间代码产生本章内容目录l中间语言 l后缀式 l图表示法l三地址代码l说明语句 l过程中的说明谙旬l保留作用域信息 l记录中的域名l赋值语句的翻译l简单算术表达式及赋值语句l数组元素的引用l布尔表达式的翻译l数值表示法l作为条件控制的布尔式翻译l控制语句的翻译编译原理第6页语义分析和中间代码产生中间语言 l几种常见的中间语言形式后缀式三地址代码（包括三元式、四元式、间接三元式）DAG图表示编译原理第7页语义分析和中间代码产生后缀式 l后缀式表示法又称逆波兰表示法。l这种表示法是把运算量（操作数）写在前面，把算符
3、写在后 面（后缀）。例如，把a十b写成ab，把a*b写成ab*。编译原理第8页语义分析和中间代码产生一个表达式E的后缀形式 l(1)如果E是一个变量或常量，则E的后缀式是E自身。 l(2)如果E是E1 op E2 形式的表达式，这里op是任何二元操作 符，则E的后缀式为E1E2op，这里E1和E2分别为E1和E2 的后缀式。l(3)如果E是（E1）形式的表达式，则E1的后缀式就是E的后缀 式。后缀式表示法用不着使用括号。根据运算量和算符出现的 先后位置，以及每个算符的目数，就完全决定了一个表达式的 分解。编译原理第9页语义分析和中间代码产生l只要知道每个算符的目数，对于后缀式，不论从哪一端进行
4、 扫描，都能对它正确进行唯一分解。编译原理第10页语义分析和中间代码产生图表示法 l包括DAG与抽象语法树 l无循环有向图（Directed Acycli Graph简称DAG）。 与抽象语法树一样，对表达式中的每个子表达式，DAG 中都有一个结点。一个内部结点代表一个操作符，它的孩子 代表操作数。 与抽象语法树不同的是，在一个DAG中代公共子表达式 的结点具有多个父结点，而在一棵抽象语法树中公共子表达 式被表示为重复的子树。 编译原理第11页语义分析和中间代码产生 l例如，表达式 a+a*(b-c)+(b-c)*d 编译原理第12页语义分析和中间代码产生 l例如，表达式 a+a*(b-c)+
5、(b-c)*d 编译原理第13页语义分析和中间代码产生编译原理第14页语义分析和中间代码产生编译原理第15页语义分析和中间代码产生l后缀式即是对抽象语法树的后续遍历序列例：上图中的抽象语法树的后缀式是：a b c uminus * b c uminu *+ assign l抽象语法树的边没有显式地出现在后缀式中，这些 边可以根据结点出现的次序及表示操作符的结点要 求操作数的个数还原出来。编译原理第16页语义分析和中间代码产生编译原理第17页语义分析和中间代码产生编译原理第18页语义分析和中间代码产生三地址代码 l三地址代码是由下面一般形式的语句构成的序列：x ：= y op z l其中,x,y
6、,z为名字、常数或编译时产生的临时变量；op代表 运算符号如定点运算符、浮点运算符、逻辑运算符等等。 每个语句的右边只能有一个运算符。l例如，源语言表达式xy*z 可以被翻译为如下语句序列：T1：y*zT2：xT1 l其中，Tl，T2为编译时产生的临时变量。编译原理第19页语义分析和中间代码产生l三地址代码可以看成是抽象语法树或DAG的一种线性表示。 编译原理第20页语义分析和中间代码产生l三地址语句类似于汇编语言代码。语句可以带有符号标号， 而且存在各种控制流语句。符号标号代表存放中间代码的数 组中三地址代码语句的下标。 l下面列出所使用的三地址语句的种类。 （1)形如 x:y op z 的
7、赋值语句，其中 op 为二元算术算符或 逻辑算符。(2)形如 x: op y 的赎值语句，其中 op 为一元算符，如一元 减ununus,逻辑非not, 移位算符及转换算符（如将定点数转 换成浮点数）。(3)形如 x:=y 的复制语句，它将y的值赋给x。(4)形如 goto L 的无条件转移语句，即下一条将被执行的语 句是带标号L的三地址语句。编译原理第21页语义分析和中间代码产生(5)形如 if x relop y goto L 或 if a goto L的条件转移语句。第一种形式语句施用关系运算符号relop（如，=等等）于x 和y,若x与y满足关系relop,那么下面就执行带标号L的语句
8、，否则下面就 继续执行if语句之后的语句。第二种形式的语句中，a为布尔变量或常量，若a为真，则执行带标号L 的语句，否则执行后一条语句。(6)用于过程调用的语句 param x 和 call p, n,以及返回语句return y.源程序中的过程调用语句 P(xl，x2，xn）通常产生如下的三地址代 码：param x1param x2param xncall p,nl其中n表示实参个数。过程返回语句retum y中y为过程返回的一个值。编译原理第22页语义分析和中间代码产生(7)形如x:= yi 及 xi:=y 的索引赋值。前者把相对于地址y 的后面第i个单元里的值赋给x。后者把y的值赋给相
9、对于地 址x后面的第i个单元。 （8）形如 x:=一个数组的域 宽可以通过把数组元素数目与一个元素的域宽相乘获得；每 个指针类型的域宽假定为4.编译原理第40页语义分析和中间代码产生l如果把图中的第一条产生式及其语义动作写在一行，则对 offset赋初值更明显，如下式所示：Poffset:=0D （7 1） l前面曾谈到产生的标记非终结符号，可以用它来重新改写 上述产生式以便语义动作均出现在整个产生式的右边。l我们可采用标记非终结符号M来重写式（7.1）：P M DM offset:=0编译原理第41页语义分析和中间代码产生保留作用域信息 l允许嵌套过程的语言，对于每一个过程，其中局部名字的相
10、 对地址计算可以采用图7.6的方法。 l而当遇到一个嵌入的过程说明时，则应当暂停包围此过程的 外围过程说明语句的处理。这种方法可以通过加入到如下的 语言把有关语义动作来说明。PDDD; D | id：T | proc id：D；S (72) l由于我们当前的目标是考虑说明语句，因而对其中产生语句 的非终结符号S及产生类型的非终结符号T的产生式我们没有 给出。与图7.6中相同T有两个综合属性type和width。编译原理第42页语义分析和中间代码产生l假定对于式(72)的语言的每一个过程都有一张独立的符号 表。这种符号表可用链表实现。当碰到过程说明Dproc id ；D,；S时，便创建一张新的符
11、号表，并且把在D，中的所 有说明项都填入此符号表内。 l新表有一个指针指向刚好包围该嵌入过程的外围过程的符号 表，由id表示的过程名字作为该外围过程的局部名字。 l对图7.6处理变量说明的唯一修改是，要告诉enter在哪个符 号表填入一项。 编译原理第43页语义分析和中间代码产生 l在下面的语义规则中用到如下操作。(1) mktable(previous)创建一张新符号表，并返回指向新表的 一个指针。参数previous指向一张先前创建的符号表，譬如 刚好包围嵌入过程的外围过程符号表。指针previous之值放 在新符号表表头，表头中还可存放一些其它信息如过程嵌套 深度等等。我们也可以按过程被
12、说明的顺序对过程编号，并 把这一编号填入表头。(2) enter(table，name，type, offset）在指针table指示的符 号表中为名字name建立一个新项，并把类型type、相对地 址offset填入到该项中。(3) addwidth(table,width)在指针table指示的符号表表头中记 录下该表中所有名字占用的总宽度。(4) enterpcoc(table，name，newtable）在指针table指示的 符号表中为名字为name的过程建立一个新项。参数 newtable指向过程name的符号表。编译原理第44页语义分析和中间代码产生l在下图中的翻译模式给出了如何
13、在一遍扫描中对数据进行处 理，它使用了一个栈tblptr保存各外层过程的符号表指针。 l当处理过程partition中的说明语句时，栈tblprt中将包括指向 sort, quicksort R partition的符号表的指针。指向当前符号 表的指针在栈顶。l另一个栈offset存放各嵌套过程的当前相对地址。offset的栈 顶元素为当前被处理过程的下一个局部名字的相对地址。编译原理第45页语义分析和中间代码产生编译原理第46页语义分析和中间代码产生编译原理第47页语义分析和中间代码产生编译原理第48页语义分析和中间代码产生记录中的域名 l除了基本类型、指针和数组外，下述产生式使非终结符号T
14、产 生记录类型：Trecord D end l当遇到保留字record时，与标记非终结符号L相应的语义动 作为记录中的各域名创建一张新的记录符号表。把指向该表 的指针压人栈tblptr中，并把相对地址。压入栈offset中。 编译原理第49页语义分析和中间代码产生编译原理第50页语义分析和中间代码产生赋值语句的翻译 l赋值语句中的表达式的类型可以是整型、实型、数组 和记录。 l作为翻译赋值语句为三地址代码的一个部分，将讨论 如何在符号表中查找名字及如何存取数组和记录的元 素。编译原理第51页语义分析和中间代码产生简单算术表达式及赋值语句 l属性id. name表示id所代表的名字本身。 l过程
15、lookup(id.nam）检查是否在符号表中存在相应此名 字的入口。如果有，则返回一个指向该表项的指针，否 则，返回nil表示没有找到。 l在语义动作中，调用过程emit将生成的三地址语句发送 到输出文件中 编译原理第52页语义分析和中间代码产生l假定赋值语句出现在如下文法形成的上下文环境中：PMDMDD;D | id:T | proc id; N D;SN l如果把这些产生式加到下面文法中，非终结符P就变为开始 符号。 编译原理第53页语义分析和中间代码产生编译原理第54页语义分析和中间代码产生数组元素的引用 l现在讨论包含数组元素的表达式和赋值句的翻译问题。 l数组在存储器中的存放方式决
16、定了数组元素的地址计算法， 从而也决定了应该产生什么样的中间代码。编译原理第55页语义分析和中间代码产生l若数组A的元素存放在一片连续单元里，则可以较容易地访 问数组的每个元素。假设数组A每个元素宽度为w，则Ai 这个元素的起始地址为base+(i-low)*w其中: low 为数组下标的下界,base是分配给数组的相对地址，即base为A的第一个 元素Alow的相对地址。 l 变形整理得：i*w（base一low * w) l其中子表达式C=base-low * w可以在处理数组说明时计算 出来。l我们假定C值存放在符号表中数组A的对应项中，则Ai相对 地址可由i*w十C计算出来 .编译原理第56页语义分析和中间代码产生l二维数组可以按行或按列存放。l若二维数组A按行存放，则可用如下公式计算A il，i2 的相 对地址：base（i1-low1）*n2i1-low
