编译程序原理与实现：第1章 编译程序介绍

1、第1章 编译程序概述问卷对编译程序的了解程度?有没有接触过编译器？可不可以不用编译器？编译器可以帮助我们做什么？编程过程中遇到过哪些编译错误? 出现非法字符；标识符未声明的错误;标识符未定义的错误;标识符使用和声明不匹配的错误;单词拼写错误;符号使用错误;第1章 编译程序概述1.1 程序设计语言1.2 程序设计语言的实现方式1.3 编译程序的伙伴程序1.4 编译程序的功能结构分解1.5 编译程序的设计与实现1.1 程序设计语言1.1 程序设计语言历史1800，第一个程序：Jacquard loom 第一个程序员：Analytical engine,Ada Lovelace; Grace Hop

2、per;董铁宝张绮霞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); 格式处理(La

3、tex); 数据库语言(SQL); 抽象级别低级机器语言 & 汇编语言高级 (不同范例paradigms)划代(ith-Generation Language，iGL)1GL：机器语言2GL：汇编语言3GL：高级程序设计语言，如FORTRAN，ALGOL，BASIC，LISP等； 4GL：为特定应用设计的语言，如数据库查询语言SQL,文本排版Postscript等； 5GL：指基于逻辑和约束的语言，如Prolog，OPS51.1 程序设计语言高级程序语言 (不同范例paradigms)过程式(Procedural programming languages-imperative)程序中指明如何

4、完成一个计算任务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 0002MOV X,2表示在IB

5、M PC上使用的Intel 8x86处理器将数字2移至地址0000(16进制)假设X的存储地址是0000过程式和函数式程序设计语言过程式语言(C语言)：#define TYPE intvoid 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 = symbolpredicates likes(person, another). cl

6、auses 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喜欢Xlikes(jack, ellen)?1.1 程序设计

7、语言不同的程序设计语言机制(函数式、过程式、逻辑式、对象式)，需要采用不同的技术编写编译程序过程式语言的编译是对象式语言编译的基础本课程重点关注过程式程序设计语言编译程序的构造原理和技术第1章 编译程序概述1.1 程序设计语言1.2 程序设计语言的实现方式1.3 编译程序的伙伴程序1.4 编译程序的功能结构分解1.5 编译程序的设计与实现1.2 程序设计语言的实现方式1.2 程序设计语言的实现方式编译器(Compiler)：编译器将某种语言(源语言)编写的程序翻译成 语义等价的另一种语言(目标语言)编写的程序。目标程序若是可执行的机器语言程序，则可以被用户调用，处理输入并产生输出。目标程序若是

8、汇编语言的程序，则须经汇编器汇编后方可执行。编译器的重要任务之一是报告它在翻译过程中发现的源程序中的错误。编译器输入源程序目标程序目标程序输出(结果)错误1.2 程序设计语言的实现方式解释器(Interpreter)：解释器直接利用用户提供的输入执行源程序中指定的操作。解释过程中若发现错误，则返回修改源程序，修改后重新解释执行。解释器输入程序输出（结果）1.2 程序设计语言的实现方式编译器和解释器的比较相同点使用相同的实现技术区别实现机制: 翻译 (程序 to 程序)vs. 解释(指令 to 指令序列)执行效率: 高 vs. 低存储代价: 少 vs. 多错误诊断：差 vs. 好 解释器相对于编

9、译器的优势可移植性好: Java支持交互式程序设计错误诊断效果好编译器的优势在于：目标程序的执行速度比解释器快很多最大区别/根本区别：目标程序1.2 程序设计语言的实现方式程序设计语言的实现方式编译方式解释方式转换方式：编译器的开发代价是非常昂贵的，在可能的情况下，可以将一种语言的程序转换成另一种语言的程序，利用另一种语言的编译器进行编译前提条件：两种语言在语法和语义上很近似，或者一种语言是另一种语言的扩展实例：C+ CL源程序转换器L源程序L编译器目标程序第1章 编译程序概述1.1 程序设计语言1.2 程序设计语言的实现方式1.3 编译程序的伙伴程序1.4 编译程序的功能结构分解1.5 编译

10、程序的设计与实现1.3 编译程序的伙伴程序1.3 编译程序的伙伴程序EditorPreprocessorCompilerAssemblerLinkerLoader Skeletal Source ProgramPreprocessorCompilerTarget Assembly ProgramAssemblerRelocatable Machine Code Loader/LinkerAbsolute Machine CodeEditorSource Program 编辑器 (editor) 除一般的文本编辑功能外，还可以对正在编辑的文本进行分析、提示、自动提供关键字匹配等功能；预处理器(p

11、reprocessor) 删除源程序中的注释、执行宏替换以及包含文件的嵌入等；汇编程序(assembler) 将编译程序生成的汇编代码汇编成机器代码；连接程序(linker) 将不同的目标文件连接到一个可执行的文件中；装入程序(loader) 将程序加载到内存中以便执行；1.3 编译程序的伙伴程序第1章 编译程序概述1.1 程序设计语言1.2 程序设计语言的实现方式1.3 编译程序的伙伴程序1.4 编译程序的功能结构分解1.5 编译程序的设计与实现1.4 编译程序的功能结构分解1.4 编译程序的功能结构分解编程问题为高级程序设计语言开发编译器就是一个编程问题How?需要弄清已知情况：源语言、目

12、标语言和实现语言的词法、语法、语义规则需要解决的问题Input ：源语言的程序 = 字符序列Output：目标语言的程序 = 目标指令序列Data structure + algorithm考虑 “自然语言翻译”过程：从中文到英文翻译的一般过程:你能够通过自己的努力实现你的梦想!识别单词检查语法检查语义翻译你能够通过自己的努力实现你的梦想!Youcanput your dreams into realitythrough your efforts!1.4 编译程序的功能结构分解自然语言翻译过程总结掌握源语言和目标语言：词法、语法和语义翻译过程包括：分析源句子是否正确拼写，包括识别单词及其属性依

13、据源语言的语法建立语法结构检查句子是否有意义将句子翻译成目标语言翻译每个语法部分将其组合成有意义的目标语言句子I eat sky in dog.1.4 编译程序的功能结构分解如何将一种程序设计语言的程序翻译成另一种程序设计语言的程序1.4 编译程序的功能结构分解表 处 理 错 误 处 理 目标代码生成中间代码优化中间代码生成语义分析语法分析词法分析目标程序源程序分析综合1.4 编译程序的功能结构分解词法分析扫描源程序的字符流；整理成有意义的单词(token)序列;识别并报告词法错误语法分析扫描token序列；确定程序的语法结构；将分析结果表示成分析树或语法树;识别并报告语法错误语义分析建立符号

14、表，标识符的属性表静态语义检查，如类型检查识别并报告语义错误if (x=j) z=0; else z=1;EAssAssIf-stmtx: intz: intj: intz=0z=1if(idassid)idass0;elseidass1;1.4 编译程序的功能结构分解代码生成中间代码生成：为优化和移植考虑，不是必要的目标代码生成：通常生成汇编代码代码优化目的是提高目标程序的执行效率中间代码优化目标代码优化表处理符号表、常量表等管理错误处理词法错误、语法错误、语义错误的处理if (x=j) z=0; else z=1;(=,x,j,t1)(JMP0,t1,-,elseL)(=,0,-,z)(J

15、MP,-,-,outL)(Label, -,-,elseL)(=,1,-,z)(Label,-,-,outL)x=y*0 x=0 几个相关术语前端(front end)：编译程序中与源语言有关，与目标程序无关的部分，称为前端。通常包括词法分析、语法分析、语义分析、中间代码生成，与目标机无关的中间代码优化部分。后端(back end)：编译程序中与源语言无关，与目标程序有关的部分，称为后端。通常包括与目标机有关的中间代码优化、目标代码生成等部分。遍/趟(pass)：所谓“遍”就是对源程序或源程序的中间表示形式从头到尾扫描一次，并作加工处理，生成新的中间结果或目标程序。可以词法分析、语法分析、语义

16、分析等阶段各作为单独一遍；也可以词法分析作为语法分析的子程序；还可以整个编译程序一遍扫描完成 第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型图表示如下：第一个编译器是用机器语言或汇编语言写的。机器语言/汇编语言不方便，效率低，不易维护。STISAA1.5 编译程序的设计与实现-自展

17、法自展法：先用目标机的机器语言或汇编语言书写源语言的一个子集的编译程序，然后再用这个子集语言书写源语言的编译程序，当源语言很复杂，上述过程可能会分成若干步，就像滚雪球一样，直至生成源语言的编译程序为止，这样的实现方式称为自展技术。第1步：用A机器的机器语言或汇编语言A书写L1语言的编译程序C1, 第2步：用L1语言书写L语言的编译程序C2,第3步：在A机器上运行C2,即在A机器上实现了L语言的编译。1.5 编译程序的设计与实现-自展法自展法：如果把L分成L1,L2,L，即L2是L1的扩充，L是L2的扩充，则自展法可用下图表示：AA1.5 编译程序的设计与实现-移植法但是一个高级语言往往需要在不

18、同的目标机上实现，这就提出了如何把已在某机器上实现的一个高级语言的编译程序能否移植到另一个目标机上。利用自展技术也可实现 。我们希望能利用A机器上已有的L语言的编译程序，实现B机器上的编译程序以缩短开发时间。移植的实现：(1) 开发一个A代码到B代码的翻译程序(2) 重建L在A机器上的编译器的后端，使之生成B机器上的代码(3)交叉编译：LLBB1.5 编译程序的设计与实现-交叉编译利用A机器上已有的L语言的编译程序使其在B机器上也能实现 第1步： 我们用L语言书写L语言的编译程序C1, 产生B机器上的汇编语言或机器语言； 第2步：用A机器上已有的L语言的编译程序编 译器C1,得到用A语言书写的L语言 在B机器上的编译器C2(交叉编译器)。第3步：用C2编译C1,得到C3.经过以上3步得到L语言在B机器上的编译器。1.5 编译