《编译程序介绍》PPT课件.ppt

第1章 编译程序概述,张晶 2011.3,问卷,对编译程序的了解程度? 有没有接触过编译器？ 可不可以不用编译器？ 编译器可以帮助我们做什么？ 编程过程中遇到过哪些编译错误? 出现非法字符； 标识符未声明的错误; 标识符未定义的错误; 标识符使用和声明不匹配的错误; 单词拼写错误; 符号使用错误; ,第1章 编译程序概述,1.1 程序设计语言 1.2 程序设计语言的实现方式 1.3 编译程序的伙伴程序 1.4 编译程序的功能结构分解 1.5 编译程序的设计与实现,1.1 程序设计语言,1.1 程序设计语言,历史 1800，第一个程序：Jacquard loom 第一个程序员：Analytical engine,Ada Lovelace; Grace Hopper;董铁宝张绮霞 1950，第一个程序设计语言 (FORTRAN; COBOL; Algol60; LISP) 1960，涌现了上百种程序设计语言 (特殊目的语言; 通用语言) 1970，简化, 抽象 (PASCAL; C; ) 1980，面向对象语言 (Ada; Modular; Smalltalk; C+ ) 1990，网络语言 (Java), Libraries, 脚本语言 (Perl; Javascript) 2000，说明语言(XML,UML,Z),1.1 程序设计语言,分类（几千种程序设计语言） 功能 科学计算(Fortran); 商业数据处理(Cobol); 表处理(Lisp); 格式处理(Latex); 数据库语言(SQL); 抽象级别 低级 机器语言 & 汇编语言 高级 (不同范例paradigms) 划代(ith-Generation Language，iGL) 1GL：机器语言 2GL：汇编语言 3GL：高级程序设计语言，如FORTRAN，ALGOL，BASIC，LISP等； 4GL：为特定应用设计的语言，如数据库查询语言SQL,文本排版Postscript等； 5GL：指基于逻辑和约束的语言，如Prolog，OPS5,1.1 程序设计语言,高级程序语言 (不同范例paradigms) 过程式(Procedural programming languages-imperative) 程序中指明如何完成一个计算任务 FORTRAN, PASCAL, C, C+, C#, Java 函数式(Functional programming languages-declarative) 程序中指明要进行哪些计算 LISP, HASKELL, ML 逻辑式(Logical programming languages-declarative) 事实+推理规则 PROLOG 对象式(Object-oriented programming languages) 支持面向对象编程 Smalltalk, Java, C+,机器语言和汇编语言的例子,机器语言语句： 汇编语言语句：,C7 06 0000 0002,MOV X,2,表示在IBM PC上使用的Intel 8x86处理器将数字2移至地址0000(16进制),假设X的存储地址是0000,过程式和函数式程序设计语言,过程式语言(C语言)： #define TYPE int void square(TYPE x, int n) for(int i=0; in; i+) *(x+i)*=*(x+i); ,求n个数的平方。,函数式语言(Haskell)： fun square()= | square(a:x)= a*a : square(x),逻辑式程序设计语言,domains person, another = symbol predicates likes(person, another). clauses likes(jack, sussan). likes(john, marry). likes(tom, cathy). likes(mark, ellen). likes(bob, tom). likes(richard, ellen). likes(tom, ellen). likes(jack, X) if likes(tom, X).,【事实】 Jack 喜欢 Sussan John 喜欢 Marry Tom 喜欢 Cathy Mark 喜欢 Ellen Tom 喜欢 Ellen 【规则】 如果Tom喜欢X，那么Jack喜欢X,likes(jack, ellen)?,1.1 程序设计语言,不同的程序设计语言机制(函数式、过程式、逻辑式、对象式)，需要采用不同的技术编写编译程序 过程式语言的编译是对象式语言编译的基础 本课程重点关注过程式程序设计语言编译程序的构造原理和技术,第1章 编译程序概述,1.1 程序设计语言 1.2 程序设计语言的实现方式 1.3 编译程序的伙伴程序 1.4 编译程序的功能结构分解 1.5 编译程序的设计与实现,1.2 程序设计语言的实现方式,1.2 程序设计语言的实现方式,编译器(Compiler)：编译器将某种语言(源语言)编写的程序翻译成 语义等价的另一种语言(目标语言)编写的程序。 目标程序若是可执行的机器语言程序，则可以被用户调用，处理输入并产生输出。 目标程序若是汇编语言的程序，则须经汇编器汇编后方可执行。 编译器的重要任务之一是报告它在翻译过程中发现的源程序中的错误。,编译器,输入,源程序,目标程序,目标程序,输出(结果),错误,1.2 程序设计语言的实现方式,解释器(Interpreter)：解释器直接利用用户提供的输入执行源程序中指定的操作。 解释过程中若发现错误，则返回修改源程序，修改后重新解释执行。,解释器,输入,程序,输出（结果）,1.2 程序设计语言的实现方式,编译器和解释器的比较 相同点 使用相同的实现技术 区别 实现机制: 翻译 (程序 to 程序)vs. 解释(指令 to 指令序列) 执行效率: 高 vs. 低 存储代价: 少 vs. 多 错误诊断：差 vs. 好 解释器相对于编译器的优势 可移植性好: Java 支持交互式程序设计，更具通用性 错误诊断效果好 编译器的优势在于：目标程序的执行速度比解释器快很多,最大区别/根本区别：目标程序,1.2 程序设计语言的实现方式,程序设计语言的实现方式 编译方式 解释方式 转换方式：编译器的开发代价是非常昂贵的，在可能的情况下，可以将一种语言的程序转换成另一种语言的程序，利用另一种语言的编译器进行编译 前提条件：两种语言在语法和语义上很近似，或者一种语言是另一种语言的扩展 实例：C+ C,L源程序,转换器,L源程序,L编译器,目标程序,第1章 编译程序概述,1.1 程序设计语言 1.2 程序设计语言的实现方式 1.3 编译程序的伙伴程序 1.4 编译程序的功能结构分解 1.5 编译程序的设计与实现,1.3 编译程序的伙伴程序,1.3 编译程序的伙伴程序,Editor Preprocessor Compiler Assembler Linker Loader,Skeletal Source Program,Preprocessor,Compiler,Target Assembly Program,Assembler,Relocatable Machine Code,Loader/Linker,Absolute Machine Code,Editor,Source Program,编辑器 (editor) 除一般的文本编辑功能外，还可以对正在编辑的文本进行分析、提示、自动提供关键字匹配等功能； 预处理器(preprocessor) 删除源程序中的注释、执行宏替换以及包含文件的嵌入等； 汇编程序(assembler) 将编译程序生成的汇编代码汇编成机器代码； 连接程序(linker) 将不同的目标文件连接到一个可执行的文件中； 装入程序(loader) 将程序加载到内存中以便执行；,1.3 编译程序的伙伴程序,第1章 编译程序概述,1.1 程序设计语言 1.2 程序设计语言的实现方式 1.3 编译程序的伙伴程序 1.4 编译程序的功能结构分解 1.5 编译程序的设计与实现,1.4 编译程序的功能结构分解,1.4 编译程序的功能结构分解,编程问题 为高级程序设计语言开发编译器就是一个编程问题,How?,需要弄清 已知情况：源语言、目标语言和实现语言的词法、语法、语义规则 需要解决的问题 Input ：源语言的程序 = 字符序列 Output：目标语言的程序 = 目标指令序列 Data structure + algorithm,1.4 编译程序的功能结构分解,考虑 “自然语言翻译”过程：从英文到中文,You can put your dream into reality through your efforts! 你 能够 通过你的努力 实现你的梦想！,翻译的一般过程:,识别单词,语法检查,意义检查,翻译,分析,1.4 编译程序的功能结构分解,自然语言翻译过程总结 掌握源语言和目标语言：词法、语法和语义 翻译过程包括： 分析源句子是否正确 拼写，包括识别单词及其属性 依据源语言的语法建立语法结构 检查句子是否有意义 将句子翻译成目标语言 翻译每个语法部分 将其组合成有意义的目标语言句子,I eat sky in dog.,1.4 编译程序的功能结构分解,如何将一种程序设计语言的程序,翻译成,另一种程序设计语言的程序,1.4 编译程序的功能结构分解,表 处 理,错 误 处 理,目 标 代 码 生 成,中 间 代 码 优 化,中 间 代 码 生 成,语 义 分 析,语 法 分 析,词 法 分 析,目 标 程 序,源 程 序,分析,综合,1.4 编译程序的功能结构分解,词法分析 扫描源程序的字符流； 整理成有意义的单词(token)序列; 识别并报告词法错误 语法分析 扫描token序列； 确定程序的语法结构； 将分析结果表示成分析树或语法树; 识别并报告语法错误 语义分析 建立符号表，标识符的属性表 静态语义检查，如类型检查 识别并报告语义错误,if (x=j) z=0; else z=1;,E,Ass,Ass,If-stmt,x: int,z: int,j: int,z=0,z=1,if,(,id,ass,id,),id,ass,0,;,else,id,ass,1,;,1.4 编译程序的功能结构分解,代码生成 中间代码生成：为优化和移植考虑，不是必要的 目标代码生成：通常生成汇编代码 代码优化 目的是提高目标程序的执行效率 中间代码优化 目标代码优化 表处理 符号表、常量表等管理 错误处理 词法错误、语法错误、语义错误的处理,if (x=j) z=0; else z=1;,(=,x,j,t1) (JMP0,t1,-,elseL) (=,0,-,z) (JMP,-,-,outL) (Label, -,-,elseL) (=,1,-,z) (Label,-,-,outL),x=y*0,x=0,几个相关术语,前端(front end)：编译程序中与源语言有关，与目标程序无关的部分，称为前端。 通常包括词法分析、语法分析、语义分析、中间代码生成，与目标机无关的中间代码优化部分。 后端(back end)：编译程序中与源语言无关，与目标程序有关的部分，称为后端。 通常包括与目标机有关的中间代码优化、目标代码生成等部分。 遍/趟(pass)：所谓“遍”就是对源程序或源程序的中间表示形式从头到尾扫描一次，并作加工处理，生成新的中间结果或目标程序。 可以词法分析、语法分析、语义分析等阶段各作为单独一遍； 也可以词法分析作为语法分析的子程序； 还可以整个编译程序一遍扫描完成,第1章 编译程序概述,1.1 程序设计语言 1.2 程序设计语言的实现方式 1.3 编译程序的伙伴程序 1.4 编译程序的功能结构分解 1.5 编译程序的设计与实现,1.5 编译程序的设计与实现,1.5 编译程序的设计与实现,Where do compilers come from? T型图(T-diagram):与编译程序相关的语言有3个，源语言S,目标语言T,实现语言I，T型图表示如下： 第一个编译器是用机器语言或汇编语言写的。 机器语言/汇编语言不方便，效率低，不易维护。,1.5 编译程序的设计与实现-自展法,自展法：先用目标机的机器语言或汇编语言书写源语言的一个子集的编译程序，然后再用这个子集语言书写源语言的编译程序，当源语言很复杂，上述过程可能会分成若干步，就像滚雪球一样，直至生成源语言的编译程序为止，这样的实现方式称为自展技术。 第1步：用A机器的机器语言或汇编语言A书写L1语言的编译程序C1, 第2步：用L1语言书写L语言的编译程序C2, 第3步：在A机器上运行C2,即在A机器上实现了L语言的编译。,1.5 编译程序的设计与实现-自展法,自展法：如果把L分成L1,L2,L，即L2是L1的扩充，L是L2的扩充，则自展法可用下图表示：,1.5 编译程序的设计与实现-移植法,但是一个高级语言往往需要在不同的目标机上实现，这就提出了如何把已在某机器上实现的一个高级语言的编译程序能否移植到另一个目标机上。 利用自展技术也可实现 。我们希望能利用