Part2.ppt

编译原理引论 编译原理引论 授课：于瑞国 内容提要 编译器构造法的研究目的（什么是编译程序） 编译器的结构 编译的基本原则 编译器应有的性质 编译器的应用模型 编译过程综述 编译技术展望 编译器构造法的研究目的 什么是编译程序 编译器构造法的研究目的 编译程序与其他软件的关系 软件：计算机系统中的程序及其文档 系统软件（操作系统）：居于计算机系统中最靠近硬件的一层，其他软件一般都通过系统软件发挥作用。他和具体的应用领域无关，如编译系统和操作系统等。 语言处理系统（编译系统）：把软件语言书写的各种程序处理成可在计算机上执行的程序。 软件语言：用于书写软件的语言。它主要包括需求定义语言，功能性语言，设计性语言，程序设计语言以及文档语言。 编译器构造法的研究目的 编译器和解释器的比较 相同点（执行相同的任务）: 检查输入程序并确定这个程序是否一个有效程序 建立一个内部模型来刻画输入程序的结构和含义 决定在执行期间值的存放位置 不同点（执行的行为不同）： 编译器以一个可执行程序的描述作为输入，以另一个等价的可执行程序的描述作为输出。 解释器以一个可执行程序的描述作为输入，以执行这一可执行程序描述的结果作为输出。 编译器构造法的研究目的 好的编译器是计算机科学的缩影 包含大量的技术：贪婪算法（寄存器分配）、启发式有哪些信誉好的足球投注网站技术（列表调度）、图形算法（死码消除）、动态规划（指令筛选）、有穷自动机和下推自动机（扫描和语法分析）、不动点算法（数据流分析） 处理复杂的问题：动态分配、同步、命名、局部化、存储器分层管理、管道调度 提供完整的解决方案：有机的结合算法、软件体系结构和软件工程的各种理论，对棘手问题给出综合性的解答方案。 编译器构造法的研究目的 一个语言处理系统（编译系统）举例 编译器构造法的研究目的 预处理器—产生编译器的输入 宏处理：宏的定义和引用 文件包含：把头文件包含到程序的正文中。 “理性”预处理器：把现代控制流和数据结构化机制添加到比较老式的语言中。 语言扩充：通过大量的内部宏定义来增强语言的能力 汇编器—对编译器的输出进行后期加工 装配连接编辑器—完成程序的装入和连接编辑两项功能 装入过程包括读入可重定位及其代码，修改可重定位地址，并将修改后的指令和数据放到内存中适当的位置 连接编辑器允许我们将多个可重定位代码的文件组成一个程序。 内容提要 编译器构造法的研究目的 编译器的结构 编译的基本原则 编译器应有的性质 编译器的应用模型 编译过程综述 编译技术展望 编译器的基本原则 编译器是工程对象，是具有独特目标的大型软件系统，两个设计原则必须遵守 不违背原义 编译器必须保持被编译程序的含义不变 这一原则是编译器设计者与编译器用户之间的契约的核心 实用性原则 编译器必须用某种明确的方式改进输入程序 例如代码优化等对输入程序的改进 编译器应有的性质 速度（Speed） 空间（Space） 反馈（Feedback） 调试（Debugging） 编译时效率（Compile-Time Efficiency） 编译器的应用模型 分析-综合模型 分析部分将源程序切分成一些基本块并形成源程序的中间表示 词法分析 语法分析 语义分析 综合部分把源程序的中间表示转化为所需的目标程序，需要一些特定的技术 符号表管理 错误检测与报告 中间代码生成 代码优化 代码生成 编译器的应用模型 内容提要 编译器构造法的研究目的 编译器的结构 编译的基本原则 编译器应有的性质 编译器的应用模型 编译过程综述 概括和展望 词法分析 词法分析也叫线性分析和扫描。 从左到右的读构成源程序的字符流，分组为多个记号。 语法分析 词法分析也叫层次分析，把源程序的记号进一步分组，产生被编译器用于生成代码的语法短语。 程序的语法结构常常需要递归 上下文无关文法是递归规则的一种形式化，可以指导语法分析 由于词法分析不要求递归，因此我们通常不明确的界定词法分析和语法分析的界限。也就是说，我们将词法分析程序当成语法分析程序调用的一个子程序。 语法分析（续） 语义分析 语义分析阶段检测程序的语义错误，收集代码生成阶段要用到的类型信息 利用语法分析阶段确定的层次结构来识别表达式和语句中的操作符和操作数 语义分析的一个重要组成部分是类型检查 语义分析只是一些简单的，可以用一定规则描述的语义信息，而无法判断程序表达的含义是否符合要求的 语义分析（续） 中间代码生成 某些编译器的中间代码生成器产生源程序的一个显式中间表示 中间表示应该具有两个重要性质，一是易于产生，二是易于翻译成目标程序 中间表示可以看成某种抽象机的程序 中间表示不仅仅计算表达式，还必须处理控制流结构和过程调用等其他任务 中间代码生成（续） 代码优化 试图改进中间代码，以产生执行速度较快的机器代码，有些编译器几乎没有进