ch1编译原理引论全解.ppt

编译原理 计算机科学技术系李薇livaye 为什么要学习编译原理 必修主干课程 操作系统和编译系统构成程序设计者与计算机之间的基本界面 通过学习该课程 掌握编译的基本理论 常用的编译技术 了解编译过程及编译系统结构和机理 能运用所学技术解决实际问题 能独立编写一个小型编译系统 此外 通过学习编译原理可以更好地理解程序语言的内部机制 从而更好地理解和运用程序设计语言 能运用编译程序构造的原理和技术完成相关软件工具的设计和开发工作 课程内容介绍编译器构造的一般原理和基本实现方法介绍的理论知识 形式语言和自动机理论 语法制导的定义和属性文法 类型论等强调形式描述技术和自动生成技术 课程简介 先行课程高等数学 离散数学 汇编语言 数据结构 参考资料 国外编译原理领域内的3本权威书籍 当代编译技术三大圣经 1 龙书 Dragonbook 2 鲸书 Whalebook 3 虎书 Tigerbook 国内编译原理领域内的权威书籍 1 陈意云 编译原理 高等教育出版社 2 吕映芝 编译原理 清华大学教育出版社 3 陈英 编译原理 清华工大学出版社 4 蒋宗礼 编译原理 高等教育出版社 5 刘磊 编译原理及实现 机械工业出版社 要求及学习方法 课程特点 理论性强 算法复杂平时 20 无故旷课 5一本教材 认真听课 以讲义为主 做适当的笔记认真完成课堂和课后作业期末 80 闭卷笔试 第一章编译概述 掌握编译程序中所涉及的有关名词术语2 理解编译程序总的框架 明确编译程序工作的基本过程及各阶段的基本任务 教学目标 1 1 程序的翻译1 2 编译的过程1 3 编译程序的逻辑结构1 4 编译程序的生成1 5 编译技术的应用及发展 教学内容 1 1程序的翻译 语言和翻译 语言是人类交流思想和信息的工具 如自然语言 世界上存在着许多种语言 各国之间要交流信息 就要有各种语言之间的翻译 计算机语言同样是丰富多彩的 2020年3月24日星期二 第16页 机器语言 machinelanguage C70600000002汇编语言 assemblerlanguage MOVX 2高级语言 high levellanguage X 2 为什么要使用编译程序 程序语言的分类 低级语言 LowlevelLanguage 机器语言 汇编语言特点 与特定的机器有关 功效高 但使用复杂 繁琐 费时 易出错 高级语言 Fortran Pascal C语言等特点 不依赖具体机器 移植性好 对用户要求低 易使用 易维护等 计算机硬件只懂自己的指令系统 那么它是如何识别除机器语言以外的另一种语言呢 解决这一问题的方法 翻译程序 翻译程序 翻译程序 能够把某一种语言程序 称为源语言程序 转换成另一种语言程序 称为目标语言程序 的一个程序 而后者与前者在逻辑上是等价的 程序翻译的方式通常有两种 一种是编译方式 另一种是解释方式 编译程序 编译程序 如果一个翻译程序的源语言是某种高级语言 其目标语言是相对于某一计算机的汇编语言或机器语言 则称这种翻译程序为编译程序 或称为编译器 若编译生成的目标程序不是机器代码 而是汇编语言程序 则还要增加一个会变程序将其会变为机器代码 汇编程序 如果一个翻译程序的源语言是某种汇编语言 其目标语言是某一计算机的机器语言 则称这种翻译程序为汇编程序 解释程序 解释程序 是一种语言处理程序 它以源程序作为输入 但不产生目标代码 它将源程序中的语句按动态顺序 逐句翻译成课执行代码 一旦具备执行条件 则立即执行这一阶段代码得到部分结果 特点 与编译系统比较 解释系统较简单 可移植性好 易于查错 但速度慢 编译和解释程序编译程序的工作相当于载翻译一本原著 计算机运行编译后的目标程序 相当于阅读一本译著 而解释程序的工作相当于在进行同声翻译 计算机运行解释程序 相当于我们直接通过翻译听外宾讲话 程序的编译执行 编译程序 运行系统 目标程序 程序的解释执行 如 BASIC Prolog 问题 效率低下 为什么解释运行的工作效率低于编译方式 编译程序与解释程序的差别 根本区别 是否生成目标代码 编译 解释执行 系统 例如Java语言 编译程序在计算机系统中的位置 编译程序是一种软件 是系统软件 通常认为系统软件是居于计算机系统中最靠近硬件的一层 其他软件一般都通过系统软件发挥作用 翻译程序所处的层次 几个概念 宿主机 运行编译程序的计算机目标机 运行编译程序所产生的目标代码的计算机交叉编译程序 一个编译程序产生不同于其宿主机的机器代码可变目标编译程序 不需要重写编译程序中与机器无关的部分就能改变目标机 对编译程序的一些说明 编译程序实质上是一个翻译程序 要注意等价变换本课程的任务就是讲解在这个转换过程中所涉及到的一些理论和方法 最后 使用这些理论和方法 自己编写一个小的编译器转换是一个总体的功能 要抓住总体结构 逐层细分 写编译器时要体现软件工程中软件设计的原则 自顶向下 逐层分解 编译器要完成的转换任务相当复杂 实现编译器时必须分步骤分阶段实现 分阶段实现的好处是能够简化程序的设计 当然也可以不分阶段实现 编译原理是讨论编译程序设计的基本理论 基本概念 基本方法 什么是编译原理 2020 3 24 34 编译器和集成开发环境 编译器 即编译程序 把高级语言经分析翻译为低级语言 集成开发环境 简称IDE IntegratedDevelopEnvironment 是用于提供程序开发环境的应用程序 一般包括代码编辑器 编译器 调试器和图形用户界面工具 背景 早期程序设计的各个阶段都要用不同的软件来进行处理 如先用字处理软件编辑源程序 再用编译程序进行编译 然后用链接程序进行函数 模块连接 开发者必须在几种软件间来回切换操作 人们习惯上经常把IDE称为编译器 编译原理引论 35 常见语言及其IDE 1 2编译的过程 1 编译程序的工作过程2 编译器各阶段的工作 1 编译程序的工作过程 编译过程本身是一种语言的翻译过程 类似于外文的翻译 将英文句子 Iwishyousuccess翻译成中文 两阶段完成翻译分析 分析单词 I wish you success分析语法 主语 谓语 宾语 宾补分析语义 我希望你成功综合 综合英语的意思 上下文环境和汉语的表达习惯 完成翻译 祝你成功 1 编译程序的工作过程 翻译外文资料 1 能识别出句子中的一个单词 2 分析句子的语法结构 3 根据句子的含义进行初步翻译 4 对译文进行修饰 5 写出最后的译文 翻译外文资料与编译源程序进行类比 将编译过程划分为5个基本阶段 词法分析 语法分析 语义分析及中间代码生成 代码优化 目标代码生成 从概念上来讲 一个编译程序的整个工作过程是划分成阶段进行的 每个阶段将源程序的一种表示形式转换成另一种表示形式 各个阶段进行的操作在逻辑上是紧密连接在一起的 事实上 某些阶段可能组合在一起 这些阶段间的源程序的中间表示形式就没必要构造出来了 1 2编译的过程 1 编译程序的工作过程2 编译器各阶段的工作 2 编译器各阶段的工作 1 词法分析词法分析阶段是编译过程的第一个阶段 这个阶段的任务是从左到右一个字符一个字符地读入源程序 对构成源程序的字符流进行扫描和分解 根据语言的词法规则识别出一个个具有独立意义的最小语法单位 即单词 2 编译器各阶段的工作 根据词法规则分析和识别单词 把需要存放的单词放到符号表中 如变量名 标号 常量等 工作依据 源语言的构词规则 即词法 也称为模式 pattern 标识符的模式是 以字母开头的字母数字序列 例 sum 10 20 num square 结果 标识符 sum 赋值号 左括号 整常数 10 加号 整常数 20 右括号 乘号 左括号 标识符 num 加号 标识符 square 右括号 分号 词法分析的功能如下 识别出源程序中意义独立的最小词法单位 单词 删除无用的空格 回车和其他与输入介质有关的符号删除程序员为了提高程序可读性所加的注释如果发现错误则报告出错 2 语法分析根据语法规则 即语言的文法 分析并识别出各种语法成分 如表达式 语句 函数等 并进行语法正确性检查 通常将语法分析的结果表示为语法树 sum 10 20 num square 语法分析的功能是进行层次分析 把源程序的单词序列组成语法短语 表示成语法树 依据的是语法规则 C语言的赋值语句的规则为 单词序列sum 10 20 num square 之所以能表示成上图的语法树 依据的是赋值语句和表达式的语法规则 3 语义分析及中间代码生成语义分析阶段的任务是审查源程序有无语义错误 工作依据 源语言的语义规则一个重要任务 类型检查根据规则检查每个运算符及其运算对象是否符合要求 数组的下标是否合法 过程调用时 形参与实参个数 类型是否匹配等 3 语义分析及中间代码生成源程序中有些语法成分 按照语法规则去判断 它是正确的 但它不符合语义规则 比如使用了没有声明的变量 或者给一个过程名赋值 或者调用函数时参数类型不合适或者参加运算的两个变量类型不匹配等等 比如下边的程序片段 intarr 2 c c arr1 10 其中的赋值语句是符合语法规则的 但是因为没有声明变量arr1 而存在语义错 中间代码生成 可选 所谓 中间代码 是一种结构简单 含义明确的记号系统 这种记号系统可以设计为多种多样的形式 重要的设计原则为两点 一是容易生成 二是容易将它翻译成目标代码 中间代码的形式 四元式 三元式 逆波兰表示 中间代码 intermediateCode 例 sum 10 20 num square 后缀表示 逆波兰Anti PolishNotation sum1020 numsquare 前缀表示 波兰PolishNotation sum 1020 numsquare 四元式表示 三地址码 10 20 T1 num square T2 T1 T2 T3 T3 sum 三元式表示 10 20 num square sum 语法树 4 中间代码优化 可选 代码优化阶段的任务是对前阶段产生的中间代码进行变换或进行改造 目的是使生成的目标代码更为高效 即省时间和省空间 例 sum 10 20 num square 得到的四元式T1 10 20T2 num squareT3 T1 T2sum T3优化后T1 num squareSum 30 T1 这只是优化工作的两个方面 此外诸如公共子表达式的删除 强度削弱 循环优化等优化工作将在后面的章节详细介绍 代码优化工作会降低编译程序的编译速度 因此编译优化阶段常常作为可选择阶段 编译程序具有控制机制以允许用户在编译速度和目标代码的质量间进行权衡 思考 代码优化能提高编译程序的运行效率吗 5 目标代码生成目标代码生成阶段的任务是把中间代码变换成特定机器上的绝对指令代码或可重定位的指令代码或汇编指令代码 这是编译的最后阶段 它的工作与硬件系统结构和指令含义有关 这个阶段的工作很复杂 涉及到硬件系统功能部件的运用 机器指令的选择 各种数据类型变量的存储空间分配以及寄存器和后缓寄存器的调度等 涉及到的两个重要问题 对程序中使用的每个变量要指定存储单元对变量进行寄存器分配 例 sum 10 20 num square 得到的优化后四元式T1 num squareSum 30 T1生成如下指令序列 MOVnum R1MOVsquare R2ADDR2 R1MUL30 R1MOVR1 sum 目标代码可采用如下三种形式之一 1 具有绝对地址的机器指令代码 2 汇编语言形式的目标程序 需要经过汇编程序汇编 以产生机器代码 3 可重定位的指令代码 多数编译程序所产生的目标代码都是这种类型 语句sum 10 20 num square 的翻译过程 编译过程小结 上述编译过程的阶段划分是一种典型的处理模式 事实上并非所有的编译程序都包括这样几个阶段 有些编译程序并不要中间代码 即不存在中间代码生成阶段 有些编译程序不进行优化 优化阶段即可省去 有些最简单的编译程序只有词法分析 语法分析 语义分析和目标代码生成 1 3编译程序的逻辑结构 按逻辑功能不同 可将编译过程划分为五个基本阶段 与此相对应 我们将实现整个编译过程的编译程序划分为五个逻辑阶段 即五个逻辑子过程 每个阶段中都要有 符号表管理和错误处理 典型的编译程序具有7个逻辑部分 S P O P 词法分析 识别单词 至少分以下几大类 关键字 保留字 标识符 字面量 特殊符号 语法分析 得到语言结构并以树的形式表示语义分析 考察结构正确的句子是否语义合法 可修改树结构 中间代码生成 可选 生成一种既接近目标语言 又与具体机器无关的表示 便于优化与代码生成 到目前为止 编译器与解释器可以一致 中间代码优化 可选 局部优化 循环优化 全局优化等 优化实际上是一个等价变换 变换前后的指令序列完成同样的功能 但是 在占用的空间上和程序执行的时间上都更省 更有效 目标代码生成 不同形式的目标代码 汇编 可重定位 绝对机器指令 符号表管理 合理组织符号 便于各阶段查找 填写等 出错处理 错误的种类 词法错 语法错 静态语义错 动态语义错 符号表管理 编译程序的一项重要工作 记录源程序中使用的标识符收集每个标识符的各种属性信息符号表是由若干记录组成的数据结构每个标识符在表中有一条记录记录的域是标识符的属性对符号表结构的要求 应允许快速地找到标识符的记录可在其中存取数据标识符的各种属性是在编译的各个不同阶段填入符号表的 声明语句 floattotal rate 词法分析器 float是关键字total rate是标识符在符号表中创建这两个标识符的记录语义分析器 total rate都表示变量float表示这两个变量的类型可以把这两种属性及存储分配信息填入符号表 在语义分析和生成中间代码时 还要在符号表中填入对这个float型变量进行存储分配的信息 错误处理 在编译的每个阶段都可能检测到源程序中存在的错误词法分析程序可以检测出非法字符错误 语法分析程序能够发现记号流不符合语法规则的错误 语义分析程序试图检测出具有正确的语法结构 但对所涉及的操作无意义的结构 代码生成程序可能发现目标程序区超出了允许范围的错误 处理与恢复判断位置和性质适当的恢复出错处理能力的优劣是衡量编译程序质量好坏的一个重要指标 编译有关的其他概念 遍 前端和后端 编译器扫描的遍数 遍 趟 是对源程序或源程序的中间结果从头到尾扫描一遍 并作有关加工处理 生成新的中间结果或目标程序 例如 词法分析器对输入源程序进行第一遍扫描 语法分析进行第二遍扫描但一个阶段对应一遍扫描的工作方式是逻辑上的 由于多次扫描的方式需要大量的存储空间存放中间表示 并且会增加一些不必要的输入输出操作 因此编译器往往把若干个阶段的工作结合起来 对应一遍扫描 从而减少对程序的扫描遍数 一个编译程序应分成几遍 如何划分 是与源程序 设计要求 硬件设备等诸因素有关的 因地难于统一划定 在主存可能的前提下 一般遍数尽可能少一点为好 但并不是每种语言都可以用单遍编译程序实现 一遍扫描的编译程序 语法分析器 词法分析器 语义分析及代码生成 控制流信息流 开始 结束 整理目标程序 多遍编译程序 编译阶段的组合 在前面所讨论的编译过程中阶段的划分是编译程序的逻辑组织 有时 常常把编译的过程分为前端 frontend 和后端 backend 前端的工作主要依赖于源语言而与目标机无关 后端工作依赖于目标机而一般不依赖源语言 根据编译程序各部分功能 将编译程序分成前端和后端 前端 通常将与源程序有关的编译部分称为前端 词法分析 语法分析 语义分析 中间代码生成 分析部分特点 与源语言有关后端 与目标机有关的部分称为后端 代码优化 代码生成 综合部分特点 与目标机有关 编译程序的前端和后端 编译阶段的组合 为什么生成中间代码 同一前端 不同后端 不同机器构成同一语言的编译程序 例如Java语言 不同前端 同一后端 同一机器生成几个语言的编译程序 例如GCC编译程序集合 编译程序中的主要数据结构 续 2020年3月24日星期二 第83页 1 4编译程序的设计 构造编译程序要掌握以下几方面的内容 源语言 理解其结构和含义目标语言 必须清楚硬件的系统结构和指令的格式等编译方法 2020年3月24日星期二 第84页 1 4编译程序的设计 一般实现编译程序的方法有 1 直接用机器语言编写编译程序2 用汇编语言编写编译程序注 编译程序核心部分常用汇编语言编写3 用高级语言编写编译程序注 这是普遍采用的方法4 自编译5 用编译工具自动生成 LEX 词法分析 与YACC 用于自动产生LALR分析表 6 移植 同种语言的编译程序在不同类型的机器之间移植 1 4编译程序的生成 早期人们用汇编语言编写编译程序 但其效率低 实现困难 比如FORTRAN语言编译器18年才完成 专门的编译编译工具 可以支持编译程序某些部分的自动生成 比如 LEX和YACC等 说到一个编译程序 一定要知道它的源语言是什麽 目标语言是什麽 还有它的实现语言是什麽 常使用T型图来表示一个编译程序所涉及的三个语言 S 源语言O 目标语言T 编译程序实现语言 SO T 开发编译程序的途径 自展法工具法自动生成法移植法 自展法 利用A机器上已有的用A代码编写的L1语言的编译程序 把用L1语言编写的L2语言的编译程序进行编译 得到A机器代码实现的L2语言的编译程序 表示为 或者表示为 问题一 如何直接在一个机器上实现C语言编译器 解决 用汇编语言实现一个 子集的编译程序 P0 人 用汇编程序处理该程序 得到 P2 可直接运行 用 子集编制 语言的编译程序 P3 人 用P2编译P3 得到P4 自展 4 用P2编译P3 得到P4 语言 机器语言 机器语言 P4 子集 机器语言 机器语言 P2 获得一个工具 子集 汇编语言 机器语言 P0 1 用汇编语言实现一个 子集的编译程序 P0 人 汇编语言 机器语言 机器语言 子集 机器语言 机器语言 P1 P2 2 用汇编程序 P1 处理该程序 得到 P2 可直接运行 语言 子集 机器语言 P3 3 用 子集编制 语言的编译程序 P3 人 移植 问题二 A机上有一个C语言编译器 是否可利用此编译器实现B机上的C语言编译器 条件 机有 语言的编译程序目的 实现 机的 语言的编译 语言 A机器 A机器 语言 B机器 机器 要完成的任务 语言 语言 机器 语言 机器 机器 语言 机器 机器 语言 语言 机器 语言 机器 A机器 语言 A机器 机器 需要编写的程序 1 问题的分析 1 人 用 语言编制B机的 编译程序P0 C B 机的C编译P1 编译P0 得到在A机上可运行的P2 C B 获得一个工具 2 问题的解决办法 3 机的P2 编译P0 得到在B机上可运行的P3 C B P2 语言 语言 机器 语言 机器 机器 语言 机器 机器 P0 P3 语言 语言 机器 语言 机器 A机器 语言 A机器 机器 P0 P1 P2 获得的工具 编译程序移植 用A机器上的L语言编写能在机器B上运行的L语言的编译程序先用L语言编写出在A机器上运行的产生B机器代码的L编译程序源程序 然后把该程序经过A机器上的L编译程序编译后得到能在A机器上运行的产生B机器代码的编译程序 用这个编译程序再一次编译上述源程序 本机编译器的利用 问题三 A机上有一个C语言编译器 现要实现一个新语言NEW的编译器 能利用交叉编