第六章-中间代码生成PPT课件

.,1,第六章中间代码生成,.,2,第六章：中间代码生成,编译器分析综合模型前端：源程序=中间代码（和源语言相关细节）后端：中间代码=目标代码（和目标语言相关细节）本章内容中间代码表示静态类型检查中间代码生成如何实现？描述用SDD、实现用SDT所有翻译方案都可以通过生成并遍历抽象语法树来实现大部分翻译方案可以基于自顶向下或自底向上语法分析实现,.,3,第六章：中间代码生成,静态检查类型检查：保证运算符被应用到兼容的运算分量语法分析之后进行的所有语法检查，例如C语言中的一条break指令位于一个for/while/switch语句之内中间表示抽象语法树高层：源语言层次化结构三地址码可高可低（通过选择不同的运算符）高级语言，如C语言C语言灵活通用、可编译成高效机器代码,.,4,6.1抽象语法树的变体：有向无环图（6.1）,表达式的无环有向图DAG作用：识别表达式中的公共子表达式比较：DAGvs抽象语法树DAG中，代表公共子表达式的节点具有多个父节点在抽象语法树中，公共子表达式由重复的子树表示，只有一个父节点例6.1：图6.3表达式a+a*(b-c)+(b-c)*d的DAG,.,5,6.1抽象语法树的变体：有向无环图,表达式的无环有向图DAG如何构建DAG？与构造抽象语法树相似，只要在构造节点之前先检查是否存在相同节点不存在：构建一个新节点存在：返回一个指向先前已构造好了的节点的指针图6-4构建图6-3的DAG的SDD图6-5图6-3所示的DAG的构造过程,.,6,6.1抽象语法树的变体：有向无环图,表达式的无环有向图DAGDAG的存放数组图6-6节点的整数索引：值编号算法6.3：构造DAG节点的值编号方法列表图6-6HASH表图6-7,.,7,6.2三地址代码（6.2）,三地址代码的一般形式x=yopz三地址代码是抽象语法树或DAG的线性表示图6-8：一个DAG及其对应的三地址代码,.,8,6.2三地址代码,三地址语句的类型（通用）x=yopzx=opyx=ygotoLifxgotoLifxrelopygotoLx=yi，xi=yx=&y，x=*y，*x:=yp(x1,x2xn)paramx1；paramx2；paramxn；y=callp,n；returny；,.,9,6.2三地址代码,三地址语句的实现抽象形式：三地址语句具体实现：通过带有操作符和操作数的记录结构来实现四元式三元式间接三元式,.,10,6.2三地址代码,三地址语句的实现四元式带有四个域的记录结构：op,arg1,arg2,resultarg1,arg2,result域的内容正常情况下指向这些域所代表的名字在符号表表项的指针临时名字在生成时一定要被写入符号表图6-10：三地址代码及其四元式表示,.,11,6.2三地址代码,三地址语句的实现三元式为了避免临时名字在生成时被写入符号表中，可以通过计算临时值的语句的位置来引用它带有三个域的记录结构：op,arg1,arg2arg1,arg2指向符号表（对于程序员定义的名字或常量）的指针或者三元组结构（对于临时变量）的指针带有括号的数字表示指向相应三元式结构的指针图6-11：三地址语句的抽象语法树及三元式表示对于表达式，抽象语法树和DAG等价,.,12,6.2三地址代码,三地址语句的实现间接三元式列出指向三元式的指针，而不是列出三元式本身优化编译器可以通过对instruction列表的重新排序来移动指令的位置。图6-12：三地址语句的间接三元式表示,.,13,6.2三地址代码,三地址语句的实现静态单赋值形式：有利于某些代码优化（了解一下即可）所有赋值针对不同名字变量(一个变量在不同地方使用不同名字)；函数将不同名字的相同变量合并起来表示方法比较：间址的使用使用四元式表示，定义或使用临时变量的三地址语句可以通过符号表直接访问临时变量的地址使用四元式表示，符号表在值的计算及使用之间提供了一次额外间址，有利于优化。使用三元式表示，移动一条定义临时值的语句需要我们改变在arg1及arg2数组中所有对该语句的引用，难以优化。使用间接三元式表示，可以通过statement列表的重新排序来移动语句。,.,14,6.3类型和类型检查（6.3、6.5）,类型应用类型检查：利用一组逻辑规则来推理一个程序在运行时刻的行为，即保证运算分量的类型和运算符的预期类型相匹配翻译时的应用：根据一个名字的类型，编译器可以确定这个名字在运行时刻需要多大的存储空间、插入显式的类型转换、选择正确版本的算术运算符、计算一个数值引用所指示的地址等等方面。,.,15,6.3类型和类型检查,类型表达式基本类型是类型表达式布尔型、字符型、整型、实数型、void（没有值）子界类型、枚举类型（PASCAL）类型名是类型表达式（可以为类型表达式命名）作用于类型表达式的类型构造算子是类型表达式，包括：数组：类型构造算子array作用于一个数字和一个类型表达式记录：类型构造算子record作用于字段名和相应的类型表达式指针：类型构造算子&作用于一个类型表达式函数：使用类型构造算子-构造得到函数类型的类型表达式笛卡儿积：如果s和t是类型表达式，那么sxt是类型表达式类型表达式可以包含其值为类型表达式的变量,.,16,6.3类型和类型检查,类型表达式表示：图方法：语法制导为类型表达式构造一颗抽象语法树或DAG内节点：类型操作算子叶节点：基本类型、类型名、类型变量例6.8：图6-14int23的类型表达式,.,17,6.3类型和类型检查,类型等价,.,18,6.3类型和类型检查,类型检查：静态vs动态静态类型检查：由编译器完成健全的类型系统能静态地确定程序在运行时不发生错误，因此不需要动态检查。如果某一语言能保证它所接受的程序不会在运行时发生类型错误，则称该语言是强类型语言动态类型检查：目标程序运行时完成有些检查只能动态完成,.,19,6.3类型和类型检查,类型检查：表达式E-literalE.type=charE-numE.type=integerE-idE.type=lookup(id.entry)E-E1modE2E.type=ifE1.type=integerandE2.type=integerthenintegerelsetype_errorE-E1E2E.type=ifE2.type=integerandE1.type=array(s,t)thentelsetype_errorE-E1E.type=ifE1.type=pointer(t)thentelsetype_error,.,20,6.3类型和类型检查,函数的类型检查产生一个函数的产生式E-E（E）函数类型的定义T-T1-T2T.type=T1.type-T2.type函数类型的检查E-E1（E2）E.type=ifE2.type=sandE1.type=s-tthentelsetype_error函数有多个参数时：s可以是函数的多个参数的乘积T1xT2xxTn,.,21,6.4声明的翻译（6.3）,声明的翻译一个简化的声明文法：一次只声明一个名字,.,22,6.4声明的翻译,声明的翻译一个简化的声明文法：一次只声明一个名字单个过程中所有的声明语句作为一个组来处理：使用一个全局变量offset跟踪下一个可用的相对地址,变换使之适合LR语法分析,.,23,6.5表达式的翻译（6.4）,表达式中的运算,.,24,6.5表达式的翻译,表达式中的运算,.,25,6.6控制流的翻译（6.6-6.7）,布尔表达式计算逻辑值从左到右按与算术表达式相似的方式完全计算布尔运算符vs算术运算符改变控制流,.