编译原理及实践-第1章 概论

1 编译原理 任课教师 肖少拥邮箱 xiaoshaoyong 教学资料 ftp 210 26 184 65电话2 讲述程序设计语言转换成可执行代码时使用的技术 数据结构和算法 3 教材 编译原理及实践机械工业出版社冯博琴冯岚等译 有英文版 内容简介 介绍了经典的编译理论和技术 提供了较完整的适用于教学实践的Tiny语言的编译器源码 是一本理论和实践内容相结合的书 有中文版电子书有英文版电子书 4 参考书 1 虚拟机的设计与实现 C C 机械工业出版社 美 Blunden著 杨涛等译2 编译原理西北工业大学出版社蒋立源康慕宁主编西北工业大学网络精品课程 编译原理网址 5 授课方式 本课程主要采用课堂讲授和上机实践相结合的形式 在教学过程中 编译器设计的理论和原理的实际应用部分以TINY语言的编译器设计为案例来讲解 6 课程内容第一章概论第二章词法分析第三章上下文无关文法及分析第四章自上而下的语法分析第五章自下而上的语法分析第六章语义分析第七章运行时环境第八章代码生成 7 第一章概论 1 1编译原理的重要性1 2编译器的发展1 3与编译器相关的程序1 4编译器逻辑阶段的划分1 5编译阶段的组合1 6交叉编译1 7考核方式 8 1 1编译原理的重要性 用户 人 应用软件 支撑软件 接口软件 工具软件 数据库 系统软件 操作系统 编译程序 硬件系统 计算机系统组成 9 编译器是将一种语言翻译为另一种语言的计算机程序 编译器是一种相当复杂的程序 其代码的长度可从10000行到1000000行不等 在计算机科学的课程中 编译原理占有非常重要的位置 学习该课程有助于理解程序设计语言 迅速掌握新的语言工具 如果软件 工程师 掌握一定的编译原理知识 他就懂得程序是如何运作的 写出更高效的程序 同时可以迅速掌握新的语言工具 10 包含许多软件技术对于从事软件设计很有价值 建立词法分析器的串匹配技术已用于文本编辑器 信息检索系统 模式识别器 软件的建模和测试领域 上下文无关文法和语法制导定义等概念已用于诸如书的排版 绘图等软件系统中 计算机应用程序中经常遇到的一个任务就是命令解释程序和界面程序的开发 例如 手机微浏览器的开发 这比编译器要小 但使用的却是相同的技术 代码优化器已用于程序验证器和从非结构化程序产生结构化程序的程序验证器中 11 蕴含着计算机学科中解决问题的思路 抽象问题和解决问题的方法 编写编译器的过程 实际上就是对程序进行全局抽象的过程 可以使我们对编程有一个全面和高层次的理解 计算机理论的三个传统的核心领域 自动机 可计算性和复杂性 计算机安全 在目前只有少数人涉及编译器的构造和维护的情况下 学习编译技术仍然具有重要的意义和价值 12 第一章概论 1 1编译原理的重要性1 2编译器的发展1 3与编译器相关的程序1 4编译器逻辑阶段的划分1 5编译阶段的组合1 6交叉编译1 7考核方式 13 1 2编译器 compiler 的发展 第一代编程语言 在20世纪40年代 冯 诺伊曼存储 程序计算机 编写一串代码或程序成为必要 开始用机器语言编写程序 例如 c70600000002 16进制 上述机器码表示 在IBMPC上使用Intel8x86处理器将数字2存入地址为0000的位置 14 第一代编程语言是二进制机器码 即0 1的二进制序列 机器可以直接执行和处理用机器语言编写的程序 15 翻译程序 汇编程序 第二代编程语言 机器语言很快被汇编语言代替 例如 movx 2 汇编程序将汇编语言程序的符号代码和存储地址翻译成与之等价的机器码 汇编器 MASM MS AS Linux 16 汇编语言以符号的形式给出指令及存储地址 大大简化了编程过程 直到现在 在一些实时性要求较高及希望使用计算机特定硬件结构特性的场合仍用汇编语言编程 汇编语言也有许多缺点 编写 阅读和理解都比较困难 而且严格依赖于特定的机器 为一台计算机编写的代码在应用于另一台计算机时必须完全重写 我们把严格依赖于特定机器的机器语言 汇编语言称为低级语言 17 第三代编程语言的出现 发展编程技术的下一个步骤 高级语言 类似于数学定义或自然语言的简洁形式来编写程序 与机器无关 例如 x 2 18 编译器的出现 编译器 汇编语言程序 movx 2 机器语言程序 c70600000002 高级语言程序 x 2 注 用高级语言编写的一条指令对应于5到10条机器码指令 面向对象的编程语言也可被认为是第三代编程语言 19 按照传统的观念 把相应的计算机源语言 高级语言 翻译成该计算机的目标语言 汇编语言或机器语言 的计算机程序称为编译器 简单地说 编译器是一个程序 它读入用某种 源语言 编写的程序并将其翻译成一个与之等价的以另一种语言 目标语言 编写的程序 编译器 20 作为编译过程的一个重要组成部分 编译器能够向用户报告被编译的源程序中出现的错误 1 2编译器 compiler 的发展 续 编译器 21 1954年至1957年期间IBM的JohnBackus带领的一个研究小组开发了FORTRAN语言及其编译器 同时 NoamChomsky开始了他的自然语言结构的研究 他提出了一种用来描述语言的数学系统 并以此定义了四类性质不同的语言 称为语言 文法 的Chomsky分类 0 1 2 3型 1 2编译器 compiler 的发展 续 编译器的发展 22 编译器的自动构造 词法分析程序生成器的工具 Lex20世纪70年代MikeLesk为Unix系统开发的 语法分析器的自动生成工具 Yacc它的第一版于20世纪70年代初发表 是美国贝尔实验室的软件产品 作者为S C Johnson 20世纪70年代后期和80年代早期 大量项目关注编译器其它部分的生成自动化 但未取得成功 1 2编译器 compiler 的发展 续 23 编译器设计最近的发展 1 2编译器 compiler 的发展 续 1 编译器越来越成为基于窗口的交互开发环境的一部分 它包括了编辑器 连接程序 调试程序及项目管理程序 2 编译器包括了更为复杂的算法的应用程序 它用于推断或简化程序中的信息 但是基本编译器设计技术在近20多年中都没有多大的改变 2000 2013年又十多年过去 情况依旧 Java 24 21世纪的智能编译器 图灵奖获得者霍普克罗夫特博士 1986年获奖智能编译器主要包含 程序分析工具 和 测试环境 两大部分 其主要作用是把程序员从大部分Debug工作中解放出来 例如程序分析工具可以在不运行目标程序的情况下就能对程序所有的可执行分支进行检测 并将那些可能造成系统安全漏洞的分支标出 以提醒程序员 21世纪的并行编译技术 25 第一章概论 1 1编译原理的重要性1 2编译器的发展1 3与编译器相关的程序1 4编译器逻辑阶段的划分1 5编译阶段的组合1 6交叉编译1 7考核方式 26 解释程序是如同编译器的一种语言翻译程序 与编译器不同之处在于 它以源程序为输入 在执行过程中不产生目标程序 代码 而是边解释边执行 即直接执行源程序中蕴含的操作 1 3与编译器相关的程序 续 解释程序 interpreter 27 如 b 2 a b 2 writea 28 边解释边执行的方式工作效率很低 但它比编译程序简单 且占用内存少 适合一些规模较小的语言 如BASIC 它经常用于执行命令语言 有时将编译和解释结合起来解决问题 如Java语言 29 解释程序虽然不产生目标程序 但它可能产生中间代码 尽管编译程序和解释程序在功能上有明显的区别 但从结构上看 好的解释程序和编译程序并没有很大的差别 它们都有词法分析 语法分析 语义分析和中间代码生成等工作 30 1 3与编译器相关的程序 续 汇编程序 assembler 汇编程序是用于特定计算机上的汇编语言的翻译程序 有时 编译器会生成汇编语言作为其目标语言 然后再有一个汇编程序将它翻译成特定计算机上的目标代码 31 源程序 连接程序和装入程序 linker 32 1 3与编译器相关的程序 续 预处理器 preprocessor 预处理器是在真正的翻译开始之前由编译器调用的独立程序 编辑器 editor 编译器通常接受由任何生成标准文件 如ASCII文件 的编辑器编写的源程序 调试程序 debugger 调试程序是可在被编译了的程序中判定执行错误的程序 它经常与编译器一起放在IDE中 33 第一章概论 1 1编译原理的重要性1 2编译器的发展1 3与编译器相关的程序1 4编译器逻辑阶段的划分1 5编译阶段的组合1 6交叉编译1 7考核方式 34 1 4编译器逻辑阶段的划分 翻译外文书刊与编译工作比较 35 编译器的编译过程包括了许多步骤或称为阶段 它们执行不同的逻辑操作 下图是编译器中的阶段和与以下阶段或其中一部分交互的3个辅助部件 36 编译器逻辑结构的组成 词法分析程序 语法分析程序 语义分析程序 中间代码生成 代码优化程序 目标代码生成 源代码 目标代码 常数表 符号表 错误处理器 37 词法分析程序 词法分析器 Thebigelephantatethepeanut 一个逻辑单位 单词 也称扫描程序 scanner 38 词法分析程序 词法分析器scanner 任务 逐个读入源程序字符并按照构词规则切分成一系列单词 单词是语言中具有独立意义的最小单位 包括保留字 标识符 运算符 标点符号和常量等 识别源程序中的单词 删除无用的空白字符 空格 回车等 进行词法检查 能够检测出输入中不能形成源语言任何单词的错误字符串 39 a标示符 左括号 Index标示符 右括号 赋值 4数字 加号 2数字 分析语句a index 4 2的单词 token 序列 40 编译器逻辑结构的组成 词法分析程序 语法分析程序 语义分析程序 中间代码生成 代码优化程序 目标代码生成 源代码 目标代码 常数表 符号表 错误处理器 41 语法分析程序 parser Thebigelephantatethepeanut 42 语法分析程序 parser 语法分析以词法分析程序输出的单词序列为输入 分析源程序的语法结构 判断它是否为相应程序设计语言的合法程序 通常我们将语法分析的结果表示为分析树 parsetree 或语法树 syntaxtree 语法分析阶段可以确定单词流中违反源语言语法结构规则的错误 43 句子a index 4 2的分析树 parsetree 44 句子a index 4 2的语法树 syntaxtree 语法分析程序更趋向于生成语法树 语法树是分析树中所含信息的浓缩 这种树是源代码单词序列的抽象表示 45 编译器逻辑结构的组成 词法分析程序 语法分析程序 语义分析程序 中间代码生成 代码优化程序 目标代码生成 源代码 目标代码 常数表 符号表 错误处理器 46 语义分析程序 semanticanalyzer 程序设计语言具有语法和语义两个特征 语法特征描述各语法成份的形式或结构 语义特征描述各语法成份的含义与功能 语义分析是在语法分析程序确定出语法短语后 审查有无语义错误 并为代码生成阶段收集类型信息 语义分析阶段能检测出具有正确的语法结构但对操作无意义的部分 47 语义分析程序分析的是程序的静态语义 一般的程序设计语言的典型静态语义包括变量的声明 计算表达式的值和类型检查等 语义分析程序计算的额外信息 例如变量的数据类型 表达式的值等 被称为属性 它们可以作为注释增加到语法树上 48 49 编译器逻辑结构的组成 词法分析程序 语法分析程序 语义分析程序 中间代码生成 代码优化程序 目标代码生成 源代码 目标代码 常数表 符号表 错误处理器 50 中间代码生成 为了处理方便和便于代码优化 通常在语义分析后并不直接产生目标代码 而是生成介于源代码和目标代码二者之间的中间代码 51 采用中间代码的具体优点有 使编译程序的算法清晰 便于分工 修改 维护和移植等 中间代码使编译器更容易重定向 不同机器上的编译器可以在已有前端的基础上附加一个适合这台新机器的后端来生成 可以在中间代码上进行与机器无关的代码优化 52 三地址码形式如下 x yopz句子a index 4 2的生成的相应的三地址码 three addresscode 如下图所示 例如三地址码 中间代码的普遍形式有两个 三地址码和P 代码 53 a index 4 2的语法树 t1 4 2t2 index 2t3 a t2 t3 t1 生成的三地址码 54 编译器逻辑结构的组成 词法分析程序 语法分析程序 语义分析程序 中间代码生成 代码优化程序 目标代码生成 源代码 目标代码 常数表 符号表 错误处理器 55 代码优化程序 代码优化工作可以在不同的编译阶段进行 其中对中间代码的优化尤其重要 为了使生成的目标代码更为高效 可以对产生的中间代码进行等价变换或进行改造 这就是代码的优化 56 代码优化程序将其优化为如下代码 t2 index 2t3 a t2 t3 6 上述中间代码t1 4 2t2 index 2t3 a t2 t3 t1 57 编译器逻辑结构的组成 词法分析程序 语法分析程序 语义分析程序 中间代码生成 代码优化程序 目标代码生成 源代码 目标代码 常数表 符号表 错误处理器 58 目标代码生成 任务 将中间代码翻译成为目标程序 通常目标代码可采用如下三种形式之一 具有绝对地址的机器指令代码 汇编语言形式的目标程序 模块结构的机器指令 59 优化后的中间代码 t2 index 2t3 a t2 t3 6 生成的目标代码 MOVR0 indexMULR0 2MOVR1 aADDR1 R0MOV R1 6 60 编译器逻辑结构的组成 词法分析程序 语法分析程序 语义分析程序 中间代码生成 代码优化程序 目标代码生成 源代码 目标代码 常数表 符号表 错误处理器 61 常数表 常数表的功能是存放在编译过程中用到的常量和字符串 快速插入和查找操作在常数表中十分重要 由于常数表的数据在整个编译过程中都被用到 所以无需在常数表中进行删除操作 62 符号表 符号表存储函数 变量 常量以及数据类型等标识符相关的信息 符号表用于以下情况 在词法分析 语法分析和语义分析的过程中收集有关标识符的属性 并存于符号表中 作为进行语法和语义的合法性检查的依据 同一个标识符可能在程序的不同地方出现 需要检查标识符在上下文中的一致性和合法性 而符号表正是进行这种检查的依据 63 作为目标代码生成阶段地址分配的依据 每个变量在目标代码生成时都需要确定其对应的存储地址 编译程序在完成了对变量的地址分配后 将其存于符号表中 可以通过符号表获取每个变量对应的存储地址 64 符号表 65 错误处理器 编译器的一个最为重要的功能是其对源程序中错误的反应 几乎在编译的每一个阶段都可以诊察出错误来 在编译阶段 编译器能够生成有意义的出错信息并在每一个错误之后恢复编译 使得编译器能继续运行 以检测出源程序中的更多错误 发现错误即停止的编译器不是一个好的编译器 66 编译器逻辑结构的组成 词法分析程序 语法分析程序 语义分析程序 中间代码生成 代码优化程序 目标代码生成 源代码 目标代码 常数表 符号表 错误处理器 67 举例 SunHostpotj2SE使用的javac编译器GJC 68 第一章概论 1 1编译原理的重要性1 2编译器的发展1 3与编译器相关的程序1 4编译器逻辑阶段的划分1 5编译阶段的组合1 6交叉编译1 7考核方式 69 1 5编译阶段的组合 前端和后端 前端 Front End 与目标机无关的部分包括分析部分 词法 语法 语义分析 中间代码生成与优化以及这部分的符号表管理错误处理 后端 Back End 的与目标机有关部分包括代码生成 与目标机有关的优化以及这部分的符号表管理和错误处理工作 70 前端和不同的后端相互配合可以得到不同的编译器 Machinecode2 Back End2 Compiler2 71 Front End2 Sourcepr