第1章引论 58zz.ppt

第一章 编译程序及其设计概述 编译程序总体结构 编译程序的实现方法 1.1 解释系统的功能分析 程序的解释执行 如：BASIC、Prolog，问题：效率低下 1.1 编译系统的功能分析 程序的编译执行 1.1 编译系统的功能分析 程序分析 词法、语法、语义 分析综合 语句的翻译、代码生成 标识符： 1. 词法分析 例： main( ) { printf(“hello”); } 结果 IDN main ‘(’ ‘)’ ‘{’ IDN printf ‘(’ STR hello ‘)’ ‘;’ ‘}’ 1、词法分析 词法分析由词法分析器完成(Lexical Analyzer)，词法分析器又叫做扫描器(Scanner) 词法分析器从左（前）到右（后）扫描源程序——一个字符串，并将该字符串转换成单词(符号—Token)串；同时要：查词法错误，进行标识符登记——符号表管理。 输入：字符串 输出：(种别码，属性值)——序对 属性值——token的机内表示 2、语法分析 语法分析由语法分析器(Syntax Analyzer)完成，语法分析器又叫Parser。 功能：Parser实现“组词成句”，构造分析树，指出语法错误，指导翻译 输入：Token序列 输出：语法成分 2. 语法分析 语句 printf(“hello”)； 表达式 ； 函数调用 标识符 （ 表达式 ） 常数 字符串 3. 语义分析 功能：分析由语法分析器给出的语法单位的语义 获取标识符的属性：类型、作用域等 语义检查：运算的合法性、取值范围等 子程序的静态绑定：代码的相对地址 变量的静态绑定：数据的相对地址 4. 生成中间代码 中间代码(intermediate Code) ： 波兰表示(Polish Notation)、逆(Anti-)波兰表示、三元式、三元组、四元组(三地址码)、语法树 例:id1+id2*id3 4. 生成中间代码 中间代码的特点 简单规范 机器无关 易于优化与转换 例（三地址代码） x := s （赋值） param x （参数） call f （函数调用） 注释 s 是 hello 的地址 f 是函数 printf 的地址 5. 代码优化 对中间代码的优化处理:对代码进行等价变换以求提高执行效率——提高运行速度和节省存储空间 与机器无关的优化 与机器有关的优化 与机器无关的优化 局部优化 常数运算在编译期间完成：8+9*4 公共子表达式的提取:基本块内 循环优化 强度削减 代码外提 与机器有关的优化 寄存器的利用 将常用量放入寄存器，以减少访问内存的次数 存储策略 根据算法访存的要求安排：Cache、并行存储体系——减少访问冲突 任务划分 按运行的算法即体系结构，划分子任务(MPMD) 6. 目标代码生成 将中间代码转换成目标机上的机器指令代码或汇编代码 7、表格管理 管理各种符号表（常数、标号、变量、过程、结构……），查、填（登记、查找）源程序中出现的符号和编译程序生成的符号，为编译的各个阶段提供信息。 辅助语法检查、语义检查 完成静态绑定、管理编译过程 Hash表、链表等各种查、填表技术 8、错误处理 进行各种错误的检查、报告、纠正，以及相应的续编译处理（如：错误的定位与局部化） 词法：拼写…… 语法：语句结构、表达式结构…… 语义：类型不匹配…… 模块分类 分析：词法分析、语法分析、语义分析 综合：中间代码生成、代码优化、目标代码生成 辅助：符号表管理、出错处理 8项功能对应8个模块 编译的遍（Pass） 根据系统资源的状况、运行目标的要求……等，可以将一个编译程序设计成多遍扫描的形式，在每一遍扫描中，完成不同的任务。 1.3 编译技术的应用 把复杂数据看作一条语句 数据格式的分析 利用词法分析、语法分析方法 数据处理的框架 基于语法制导的语义处理框架 编译技术可以用于各种复杂数据的分析处理 例1-1（1/1） DOS 命令 date 的输出格式 例：9-2-1993、09-03-1993、9-03-93 语法 date → month - day - year 词法 month → DIGIT DIGIT | DIGIT day → DIGIT DIGIT | DIGIT year → DIGIT DIGIT | DIGII DIGIT DIGIT DIGIT 例1-1 语义 year(年)、month(月)、day(日) 语义约束条件 0 month.value 13 0 day.value 32，31，30 0 year.value 10000 1.4 编译程序的实现方法 设计目标 目标程序小，执行