编译原理与技术讲义-第1章.ppt

青岛大学信息工程学院 编译原理与技术 第1章概论 编译原理与技术 2 主要内容 为什么学习编译什么叫编译程序编译过程概述编译程序的构成与编译有关的概念和技术如何开发编译程序编译系统以及其它相关程序 编译原理与技术 3 1 1为什么学习编译 编译程序构造的原理和技术一直属于计算机科学必备的专业基础知识 是计算机科学中一个非常成功的分支 也是最早获得成功的分支之一 它所建立的理论 技术和方法值得深入研究和学习 编译构造正确地建立了研究的问题领域和研究方式 编译原理与技术 4 1 1为什么学习编译 针对编译程序构造的某些部分已经开发了标准的形式化技术 包括有限自动机理论 上下文无关文法 正规表达式 属性文法 机器代码描述 数据流分析方程式等 编译程序包含许多普遍使用的数据结构和算法 例如散列法 哈希算法 栈机制 堆机制 垃圾收集 集合算法 表驱动算法 编译程序的许多构造技术已经得到了广泛的应用 学习编译原理和技术还有助于我们理解程序设计语言 编写优秀的软件 编译原理与技术 5 1 2什么叫编译程序 概念翻译程序或翻译器是把一种语言 源语言 转换成等价的另外一种语言 目标语言 的程序 如果源语言是高级编程语言 目标语言是机器代码和汇编语言这样的低级语言 这类翻译程序就叫做编译程序或编译器 编译原理与技术 6 1 2什么叫编译程序 编译执行方式 把源程序用编译程序翻译成机器可以执行的目标程序或目标代码 然后才能接受输入数据运行 编译程序 源程序 输入数据 目标程序 计算机系统 目标程序 运行结果 编译原理与技术 7 1 2什么叫编译程序 解释程序 解释程序不产生源程序的目标代码 而是对源程序逐条语句的分析 根据每个语句的含义执行产生结果 解释程序 输入数据 源程序 计算机系统 运行结果 编译原理与技术 8 1 3编译过程概述 词法分析词法分析的任务是逐步地扫描和分解构成源程序的字符串 识别出一个一个的单词符号或符号 编译程序的词法分析也叫词法扫描或线性扫描 计算机高级语言的单词符号通常包括 标识符 关键字或基本字 标点符号 常数 运算符 分隔符等类型 编译原理与技术 9 1 3编译过程概述 例子1 1 while i 100 sum sum i词法分析的结果识别出的单词 编译原理与技术 10 1 3编译过程概述 语法分析语法分析的任务是在词法分析基础上 根据语言的语法规则把单词符号串分解成各类语法单元 语法范畴 语法短语 例如 短语 子句 语句 程序段 函数 和 程序 等 语法分析是把线形序列的单词符号 根据语言的语法规则 按照层次分解 结果通常表示成语法分析树 编译原理与技术 11 1 3编译过程概述 例子1 1while i 100 sum sum i语法分析树 编译原理与技术 12 1 3编译过程概述 语义分析和中间代码生成语义分析的任务是检查程序语义的正确性 解释程序结构的含义 检查变量是否有定义 变量在使用前是否具有值 数值是否溢出等 其中的一个重要部分是进行类型的检查和转换 语义分析完成之后 编译程序通常就依据语言的语义规则 利用语法制导技术把源程序翻译成某种中间代码 编译原理与技术 13 1 3编译过程概述 中间代码是一种定义明确 便于处理 独立于计算机硬件的记号系统 可以认为是一种抽象机的程序 其中一类是三地址代码 很象机器的汇编语言 Lbegin ifi 100gotoLbodygotoLendLbody t1 sum isum t1t2 i 1i t2gotoLbeginLend 编译原理与技术 14 1 3编译过程概述 中间代码优化主要任务是对前一阶段产生的中间代码进行等价变换 以便产生速度快 空间小的目标代码 Lbegin ifi 100gotoLbodygotoLendLbody sum sum ii i 1gotoLbeginLend 编译原理与技术 15 1 3编译过程概述 目标代码生成目标代码生成的主要任务是把 经过优化处理的 中间代码翻译成特定的机器指令或汇编程序 这个阶段的工作依赖于计算机的硬件结构和指令系统 主要涉及到机器指令的选择 各种类型变量存储空间的分配 以及寄存器的分配和调度 等等 编译原理与技术 16 1 3编译过程概述 目标代码生成 MOV 100 R0 把常数100存入寄存器R0MOVi R1 把变量i的值存入寄存器R1MOVsum R2 把变量m的值存入寄存器R2Lbegin CMPR1 R0 比较R1和R0的值 结果存入状态寄存器CTJ Lend 状态寄存器CT 1或2 即R1 R0 程序转入单元LendADDR1 R2 把寄存器R1加R2 结果送入R2INCR1 寄存器R1的值加1JLbegin 无条件转移到地址LbeginLend 编译原理与技术 17 1 4编译程序的构成 符号表管理 错误处理 词法分析器 语法分析器 语义分析与中间代码生器 代码优化器 目标代码生成器 目标代码 单词符号 源程序 语法单元 中间代码 中间代码 编译原理与技术 18 1 4编译程序的构成 基本功能 词法分析器 又叫扫描器 对输入的源程序执行词法分析工作 输出单词符号序列 语法分析器 又叫分析器 对单词符号序列进行语法分析 识别出各类语法单元 判断输入的符号串是否构成语法正确的 程序 语义分析与中间代码生成器 对语法正确的各类程序单元进行语义分析 并把它们翻译成一定形式的中间代码 代码优化器 执行对中间代码的优化处理 以提高代码的执行效率 目标代码生成器 根据特定的机器把中间代码翻译成目标代码 并进行优化处理 编译原理与技术 19 1 4编译程序的构成 辅助功能 符号表管理 把编译程序中的各种符号合理地组织和管理 方便符号信息的添加 查询 更新和删除 错误诊断和报告 有效地识别 诊断 分析和报告程序中的各种错误 分类 语法错误 词法错误和句法错误 和语义错误这两类 编译原理与技术 20 1 5其它与编译有关的概念和技术 遍 趟 在编译的具体实现时 往往根据不同的源语言 设计要求 使用对象以及编译程序所在宿主机的内存等硬件条件 将编译过程组织为若干遍 趟 一个编译程序最终经过几遍完成 就称为几遍编译 编译原理与技术 21 1 5其它与编译有关的概念和技术 编译的前端和后端编译前端只依赖于源程序 独立于目标计算机 编译前端的工作包括词法分析 语法分析 语义分析 中间代码生成及其优化 文法错误的处理和符号表的组织也在编译前端完成 编译后端的工作主要是目标代码的生成和优化 独立于源程序 完全依赖于目标机器和中间代码 把编译程序分成前端和后端已经成为目前编译程序的设计实践 其显著优点是 可以优化配置不同的编译程序组合 实现编译的重用 保持语言与机器的独立性 编译原理与技术 22 1 5其它与编译有关的概念和技术 编译程序的分类诊断型编译程序 专门用于帮助程序的开发和调试 它们系统地分析程序 发现程序中的错误 智能地校正一些错误 优化型编译程序 这类编译程序着重于提高目标代码的时空效率 使得产生的目标代码既占用较少的存储空间 又运行的快 编译原理与技术 23 1 5其它与编译有关的概念和技术 交叉型编译程序 运行目标程序的计算机和运行编译程序的计算机的型号不相同 利用编译前端和后端的技术 可以设计与目标机无关的编译程序 利用编译后端就可以改变目标计算机 这样编译方便移植 称为可变目标型编译程序 编译原理与技术 24 1 6编译技术和软件工具 语法制导编辑器这类工具运用程序语言的语法知识 在用户编写程序的时候按照词法和语法分析的信息提供智能的帮助 包括自动地提供关键字及其匹配的关键字 左右括号的配对 对象的属性和操作 等等 程序调试工具调试的目的是根据程序的异常 追踪和确定错误在程序中的具体位置 并且修改程序 消除错误 编译原理与技术 25 1 6编译技术和软件工具 程序测试工具程序测试是为了发现错误而执行程序的过程 基于编译技术的测试辅助工具可以分为静态分析器和动态测试工具 程序理解工具在软件测试 软件维护以及软件的再向工程和逆向工程等工作中 需要人们理解和分析程序 得到需要的软件信息 这类工具称为程序理解工具 编译原理与技术 26 1 7如何开发编译程序 手工编写编译程序编译程序的自动生成技术编译程序的自展技术 编译原理与技术 27 1 7如何开发编译程序 编译程序的移植技术用宿主计算机上的高级语言编写一个能在另外类型目标机上运行的编译程序 AB H HK M AB K 图1 7把机器H上的编译移植到机器K上 编译原理与技术 28 1 7编译系统以及其它相关程序 编译系统 预处理器 源程序 编辑器 修改后的源程序 汇编程序 可重定位的目标程序 可执行的目标程序 函数库 可重定位的目标文件 连接器与加载器 特性器 调试器 解释器 配置与版本控制器 源程序 汇编器 编译器 源程序 编译原理与技术 29 1 7编译系统以及其它相关程序 编辑器 程序员借助编辑器编写源程序 由编辑器产生出标准的正文文件 如ASCII文件 作为编译程序的输入 预处理器 它是在编译程序真正开始翻译源程序之前调用的一个独立的程序 以便加快和简化翻译工作 汇编器 汇编器把汇编语言代码翻译成一个特定的机器指令序列 连接器 搜集和组织程序所需要的不同代码和数据 把它们连接成可以执行的