编译概述精品课件

1、编译概述第1页，共54页，2022年，5月20日，20点35分，星期二编译原理-课前思考为什么有些语言规定标识符不能超过8个字符？而有些语言对标识符的长度无限制？ 为什么有些语言能实现递归，而有些语言不能？ C语言规定数组下界为0，上界为声明的数减1，为什么？ 嵌套的IF语句规定ELSE与上面最近的IF配对，为什么？为什么有些程序运行一段时间后会导致内存溢出？为什么Java实现了“一次编写，到处运行”？ 第2页，共54页，2022年，5月20日，20点35分，星期二学习目的 了解和掌握设计和构造编译程序的基本原理、基本技术及其实现方法，加深对计算机系统的了解，培养和提高计算（机）思维能力。第3

2、页，共54页，2022年，5月20日，20点35分，星期二各章节内容第1章 编译概述（2课时）第2章 文法和语言（6课时）第3章 词法分析（6+4课时）第4章 语法分析-自顶向下分析（6+4课时）第5章 语法分析-自底向上分析（6课时）第6章 语法制导翻译技术（6课时）第7章 符号表管理技术 （2课时）第8章 程序运行时的存储组织及管理 （2课时）第9章 语义分析和代码生成（6+4课时）第10章 代码优化（2课时）第4页，共54页，2022年，5月20日，20点35分，星期二学习要求认真听课积极练习课后复习编译原理好难！第5页，共54页，2022年，5月20日，20点35分，星期二参考书目张幸

3、儿编，计算机编译原理编译程序构造实践(第二版)，科学出版社，2009年刘磊等编，编译程序的设计与实现，高等教育出版社，2004年赵克佳等译，现代编译原理C语言描述，人民邮电出版社，2006年张素琴，吕映芝等编，编译原理（第2版），清华大学出版社，2005年赵建华等译，编译原理(第2版)，机械工业出版社，2009年第6页，共54页，2022年，5月20日，20点35分，星期二编译原理(原书第2版)作者： (美)Alfred V.Aho Monica S.Lam Ravi Sethi Jeffrey D.Ullman 译者： 赵建华 郑滔 戴新宇 出版社：机械工业出版社 编译领域里程碑式的经典著作

4、龙书原版封面中文版封面第7页，共54页，2022年，5月20日，20点35分，星期二课程学习网站清华大学北京航空航天大学武汉大学第8页，共54页，2022年，5月20日，20点35分，星期二题 外 话基本：完成课程学习，通过考试，获得学分。提高：能够将所学知识和内容用于解决实际问题。飞跃：通过编译原理的学习，改进思维方式，为将来的工作打好基础，终身受益。第9页，共54页，2022年，5月20日，20点35分，星期二考试成绩评定方法平时（30%） 作业、课堂练习和出勤(25%) 上机编程(15%)期考（70%） 考试方式：笔试（闭卷） 考试题型：填空题 判断题 选择题 综合应用题第10页，共54

5、页，2022年，5月20日，20点35分，星期二No man is born wise or learned. 没有生而知之者第1章 编译概述第11页，共54页，2022年，5月20日，20点35分，星期二学习内容：1.1 程序设计语言1.2 翻译程序1.3 编译程序的组成1.4 编译程序的结构1.5 编译程序的前后处理器1.6 TEST语言与编译器第12页，共54页，2022年，5月20日，20点35分，星期二第1章 编译概述学习重点：1、编译程序2、编译程序与解释程序的根本区别3、典型的编译程序模型及其各组成 部分的功能第13页，共54页，2022年，5月20日，20点35分，星期二回顾：

6、程序与程序设计语言程序：为实现特定目标或解决特定问题而用计算机语言编写的指令序列的集合。常见的程序设计语言： C+, Java, C, FORTRAN, Pascal, Lisp, Basic, ML等程序输入程序输出高级语言机器语言第14页，共54页，2022年，5月20日，20点35分，星期二1.1 程序设计语言(p1) 1、机器语言（最低形式，属低级语言） 特点：程序中的每条指令都是用二进制代码直接表示的，由它构成机器的指令系统，机器能直接识别和直接执行，但机器语言程序难写、难读、难修改，编程的工作量大，对程序员的要求高。 机器语言程序示例： 00111110 00011010 1111

7、1110 00100100 11010011 00101111 01110110 第15页，共54页，2022年，5月20日，20点35分，星期二2、汇编语言（属低级语言） 特点：它是机器语言的符号表示，例如用ADD表示加法，可读性等方面较机器语言有一定的改进，但还依赖于具体的机器，机器不能直接识别和直接执行。汇编语言程序示例：LD A，26 /把26送到变量AADD A，36 /加上36 OUT (48)，A /输出到48号端口 HALT /暂停第16页，共54页，2022年，5月20日，20点35分，星期二 3、高级语言 特点：它独立于机器，比较接近自然语言，因而容易学习和掌握，且编写程序

8、效率高，编写出的程序易读、易理解、易修改、易移植，但机器不能直接识别和直接执行。C语言程序示例：int a,c=2; a=16+c*2; printf(a=%d,a); 第17页，共54页，2022年，5月20日，20点35分，星期二高 汇级 编语 语言 言程 程序 序翻译程序第18页，共54页，2022年，5月20日，20点35分，星期二1.2 翻译程序(p2)1、除机器语言程序外，用其它语言编写的程序都必须翻译才能被计算机识别和执行。2、翻译程序的定义： 翻译程序是这样的一种程序，它能将用甲语言（源语言）编写的程序（源程序）翻译成与之等价的乙语言（目标语言）编写的程序（目标程序）。第19页

9、，共54页，2022年，5月20日，20点35分，星期二3、翻译程序在计算机系统中的所在层翻译程序属于系统软件 ! 第20页，共54页，2022年，5月20日，20点35分，星期二4、翻译方式（1）解释方式（相当口译） 特点：源程序的翻译到执行只有一个阶段解释执行阶段，即：解释程序将按源程序中语句的动态顺序，逐句地进行分析解释，并立即予以执行。在这种翻译方式下，不生成目标代码。第21页，共54页，2022年，5月20日，20点35分，星期二（2）编译方式（相当笔译） 特点：源程序的翻译和目标程序的运行是分阶段进行的，它先将高级语言编写的源程序翻译成汇编语言程序或机器语言程序，然后再运行目标程序

10、。 第22页，共54页，2022年，5月20日，20点35分，星期二编译程序 vs. 解释程序编译解释第23页，共54页，2022年，5月20日，20点35分，星期二a.当目标程序是机器语言程序时，源程序从编译到被执行的过程分为两个阶段： 第24页，共54页，2022年，5月20日，20点35分，星期二b.当目标程序是汇编语言程序时，源程序从编译到被执行的过程分为三个阶段：第25页，共54页，2022年，5月20日，20点35分，星期二看起来，编译器似乎完全能代替汇编啊！回答是No。Why?高级语言通过编译器转化成的机器语言，受限于高级语言，其效率和功能上都有限制。比如不能过分操作内存。但通过

11、汇编器转化过来的机器语言，效率高，且用汇编语言，可直接和CPU对话！ 汇编可以反汇编（逆向编译），即： 程序（二进制机器语言）通过反汇编器（compiler），可转化为汇编代码（文本） 但永远不能转化为高级语言的源代码！ 第26页，共54页，2022年，5月20日，20点35分，星期二预处理器源程序标准源程序 可重定位机器代码可重定位目标文件库文件编译程序汇编程序目标汇编程序连接加载程序绝对机器代码C语言编译系统（见p9）宏处理文件包含条件编译第27页，共54页，2022年，5月20日，20点35分，星期二5、两种翻译方式的比较编译方式与解释方式的根本区别在于是否生成目标代码。 在解释方式下执

12、行源程序，易于查错，在程序执行中可以修改程序(代表有BASIC语言) 。但和编译方式相比，执行效率太低。现在有些语言的集成开发环境提供了两种方式，如Visual Basic，调试期间可解释执行源程序，而调好的程序可以编译生成目标程序。 第28页，共54页，2022年，5月20日，20点35分，星期二编译过程自然语言的翻译（如把英文翻译为中文 ）识别出句子中的一个个单词；分析句子的语法结构；根据句子的含义进行初步翻译；对译文进行修饰；写出最后的译文。 词法分析语法分析中间代码产生优化目标代码产生例 The monkey ate the banana.例 A compiler is a compu

13、ter program that transforms source code written in a programming language into another computer language. 第29页，共54页，2022年，5月20日，20点35分，星期二一个平滑的字符流变成一个单词序列得到语法成分更接近机器语言更高的效率达到目标走向目标1走向目标2走向目标3走向目标4走向目标51.3 编译程序的组成(p3)第30页，共54页，2022年，5月20日，20点35分，星期二第31页，共54页，2022年，5月20日，20点35分，星期二1、词法分析程序（又称扫描器） 词法分析

14、依次读入源程序中的每个字符，依据语言的构词规则，识别出一个个具有独立意义的最小语法单位，即“单词”，并用整数码或有意义的记号来表示每个单词的词性是保留字、标识符、分界符、运算符或常数。例如，表达式a=10+c*20的词法分析结果如右表所示。整数码记号单词100IDa21=200NUM1022+100IDc25*200NUM20第32页，共54页，2022年，5月20日，20点35分，星期二2、语法分析程序 依据语言的语法规则，逐一地分析词法分析时得到的单词，以确定它们是怎样组成说明和语句的，以及说明和语句是怎样组成程序的。 分析时如发现有不合语法规则的地方，则报告出错位置和性质；如无语法错误，

15、则以另一种内部表示（如语法分析树或其它中间表示）给出正确的语法结构，供下一阶段分析使用。“猴子吃香蕉”的语法分析树第33页，共54页，2022年，5月20日，20点35分，星期二a=10+c*20的语法分析树第34页，共54页，2022年，5月20日，20点35分，星期二3、语义分析程序 依据语言的语义规则对语法分析得到的语法结构进行静态语义检查（即确定类型、类型和运算合法性检查、识别含义与相应的语义处理及其它一些静态语义检查），并用另一种内部形式表示出来，供下一阶段使用。4、中间代码生成程序（可有可无） 根据语法成分的语义对其进行翻译，用另一种接近于计算机的指令形式（中间代码）表示出来，供下

16、一阶段使用。第35页，共54页，2022年，5月20日，20点35分，星期二语义分析及中间代码生成示例第36页，共54页，2022年，5月20日，20点35分，星期二5、中间代码优化程序(可有可无)第37页，共54页，2022年，5月20日，20点35分，星期二6、目标代码生成程序 将中间代码或优化之后的中间代码转换为等价的目标代码。 目标代码的形式可以是绝对指令代码、可重定位的机器指令代码或汇编指令代码。目标代码依赖于具体的计算机的硬件系统结构和指令系统。第38页，共54页，2022年，5月20日，20点35分，星期二7、符号表处理程序 编译过程中要记录源程序中出现的标识符，并收集每个标识符

17、的各种属性信息。符号表是由若干记录组成的数据结构，每个标识符在表中有一条记录。 标识符的各种属性是在编译的不同阶段填入符号表的。词法分析阶段只能分析出标识符名，语法分析阶段只能判断标识符在语句中出现是否合法，语义分析阶段将标识符的各种属性填入符号表并使用这些属性生成中间代码。 标识符名标识符类型 类型 地址 aaa1（表示变量） 1（表示整型） 0001 第39页，共54页，2022年，5月20日，20点35分，星期二8、出错处理程序 编译的各个阶段都可能发现源程序中的错误。任意时刻发现错误，都应该报告错误信息，包括错误出现的位置、错误性质等，为程序员调试程序提供方便，从而使编译能继续进行。

18、词法分析可以检测出源程序中的非法符号。语法分析能够发现程序语句中的各种语法错误，如括号不匹配等等。语义分析能判断运算对象的类型是否匹配、变量是否重复声明或没声明就使用等错误。 例 int a,b; a= 2*)12+b);第40页，共54页，2022年，5月20日，20点35分，星期二C编译器不同的编译器，其结构也不一定相同！FORTRAN 编译器第41页，共54页，2022年，5月20日，20点35分，星期二1.4 编译程序的结构(p7)1、遍（趟，趟程） 所谓一遍是指一个编译程序在编译时把源程序或其中间代码从头到尾扫描一遍并完成相应工作的全过程。在一遍处理中，可完成编译程序六个任务中的一个

19、或几个。2、单遍与多遍编译程序 根据编译程序在完成翻译任务的过程中需要对源程序或其中间代码扫描的遍数，可以把编译程序分为单遍编译程序(只需扫描一遍)和多遍编译程序（需扫描多遍）。第42页，共54页，2022年，5月20日，20点35分，星期二（1）单遍编译程序举例 编译程序对源程序只进行一遍扫描，就完成编译的各项任务，其典型结构是：以语法分析程序为主程序，词法分析程序作为语法分析的一个子程序，当语法分析需要一个新单词时，便调用词法分析程序，当它识别出一个语法成分时，就调用语义分析程序。第43页，共54页，2022年，5月20日，20点35分，星期二 具体做法：将整个编译程序划分为若干个相继执行

20、的模块，每一模块都对它前一模块的输出扫描一遍，并完成相应工作，然后将工作结果送给下一模块加工。 （2）多遍编译程序举例 例如，三遍编译程序：把词法分析作为第一遍，语法分析和语义分析作为第二遍，代码生成作为第三遍。有：第44页，共54页，2022年，5月20日，20点35分，星期二3、遍的划分依据源语言的繁简宿主机的存储容量的大小编译程序功能的强弱目标程序优化的程度实现工具的先进程度设计人员的素质和数量 当源语言较繁、编译程序功能很强、目标程序优化程度较高且宿主机存储容量较小时，宜采用多遍扫描方式。第45页，共54页，2022年，5月20日，20点35分，星期二4、前端和后端(p8)第46页，共

21、54页，2022年，5月20日，20点35分，星期二 把编译程序分为前端和后端的优点是便于编译程序的构造和移植。 例如，有K种高级语言、L种目标机器，如果不分前端和后端，就需要建立K*L套编译程序，而分成前端和后端，只需要建立K（前端）+L（后端）套编译程序。CPBAB中间语言第47页，共54页，2022年，5月20日，20点35分，星期二1.6 TEST语言与编译器（p10）一、TEST语言 TEST语言程序是由一对花括号括起来的语句序列，它在语法上相当于C语言的函数体。 声明语句：只能是简单的整型变量 控制语句：if、while和for语句 表达式语句：布尔表达式和算术表达式 算术运算符： +、*、/ 比较运算符： 、=、=和!= 输入语句：read语句 输出语句：write语句 注释语句：用“/*”和“*/”括起来，但注释不能嵌套。 第48页，共54页，2022年，5月20日，20点35分，星期二一个TEST语言程序 int i; int n; int j; j=1; read n; /*输入语句*/ for (i=1;i=n;i=i+1) j=j*i; write j; /*输出语句*/第49页，共54页，2022年，5月20日，20点35分，星期二二、TEST编译器TEST编译器包括以下3个C文件：1、TESTmain.c：主程序，先后调用词法分析、语法分析及语义分