[工学]第08章中间代码生成.ppt

第08章 中间代码生成 中间代码 表达式的中间代码生成 原子语句的中间代码生成 结构语句的中间代码生成 8.1 中 间 代 码 中间代码的好处：便于移植、便于修改、便于优化、便于掌握。 中间代码的种类： [1] 后缀式中间代码（逆波兰式） [2] 三地址中间代码（三元式、四元式） [3] 抽象语法树中间代码（AST) [4] 无环有向图（ DAG ） 8.1.2 后缀式中间代码 特点：将运算对象写在前面，把运算符号写在后面，适合于栈式机。 优点：遇到操作符即可处理，不需要括弧。 缺点：不利于优化和代码生成。 后缀式结构：表达式后缀式的形式定义如下： Suffix(x)=x Suffix(c)=c Suffix((E))= Suffix(E) Suffix(E1 ? E2)= Suffix(E1) Suffix(E2) ? Suffix(f(E1,E2,?En)= Suffix(E1) ? Suffix(En) f Suffix(x:=E)= x Suffix(E) := 计算方法：自左向右扫描逆波兰式，遇到运算对象则入栈，遇到算符则将相应数目的运算对象出栈计算后结果入栈。 栈式机上的目标代码：栈式机主要由一个栈和一些命令组成。 8.1.3 三地址中间代码 三地址代码：一个操作码、两个操作数、一个结果值，可抽象表示为： Result := Operand1 Op Operand2 例：语句x:=b*c+b*d可表示为： t1 := b*c ; t2 := b*d ; t3 := t1*t2 ; x := t3; 三元式： (p):(op,arg1, arg2) 四元式：（op,arg1,arg2，Result) 例：语句x:=b*c+b*d可表示为： 间接三元式： 是三元式编号序列，每个间接三元式指向三元式表中的一个三元式，，是三元式表是由不同的三元式组成的表。 例：语句a*b+c+a*b可表示为： 三元式和四元式的比较：三元式比四元式占用的空间小，但四元式比三元式更易于生成目标代码和优化。 更详细的三地址中间代码：考虑类型等信息，如：语句x:=b*c+b*d可表示为： 8.1.4 抽象语法树(AGT)和无环有向图(DAG) AGT：中间代码的一种树形描述方式。 DAG：如果有向图中的任一通路都不是环路，则称为无环路有向图，简称DAG。 例：c:=a?b+a?b 的AGT和DAG表示。 *将四元式(?,A,B,T)变为DAG的算法： [1] 用A和B查Pairs表：若没有A或B项 ，则新建标记为A或B的叶结点，并将对偶（A,addrA)或（B,addrB)填入Pairs表；若有，则查出其相应的addrA/addrB。 [2] 查已造的DAG中是否有：以?为运算符，左右儿子为A和B的结点；若没有，则新建标记为?的结点(设其地址为addrT)，并将对偶（T,addrT) 填入Pairs表；若有，则不建新结点，而是将对偶（T,addrT?) 填入Pairs 表中。 8.1.5 多元式中间代码 多元式：允许具有不同个数分量的中间代码。 例1：写出 a:=b?c+b?d 的多元表示，设a和d为实型，b和c为整型。 (1) (MULTI , addr(b) ,addr(c) ,t1) (2) (FLOAT , addr(b) , t2) (3) (MULTF , t2 ,addr(d) ,t3) (4) (FLOAT , t1 ,t4) (5) (ADDF , t4 ,t3 , t5) (6) ( := , t5 , addr(a)) 多元式可用于其它语句的表示，见下例： 例2：写出 read(A);read(B);if AB then C:=A+5 else C:=B+5;write(2*(C-1)) 的多元表示。 8.1.6 中间代码分量ARG结构 两种方案：多元式中的分量有变量、整数、实数、标号等，变量的ARG的表示形式一般有两种方案：1）采用变量名在符号表中的地址，称为符号表地址法；2）把生成地址时所需要的信息封装后直接存储在一个ARG中，称为逻辑地址法。 ARG结构：符号表地址法和逻辑地址法的ARG结构见下图所示： ARG逻辑结构的C语言描述： [1] enum kind{ LabelKind,IntKind,RealKind, VarKind,FuncKind,ProcKind}; [2] stru