第01章、编译程序概论-3.ppt

1,编译原理,Email:mali电话核：平时考勤、表现：10%平时作业：20%期末考试（闭卷）：70%,2,前言,课程内容课程特点教学安排学习章节考试安排,3,课程内容,主要阐述编译程序的基本结构、编译技术的一般理论和常用的有效方法与技术。包括:文法和形式语言自动机理论词法分析语法分析语义分析中间语言代码生成,4,理论与实践的结合理论：编译基础理论实践：自己编写编译器（专门课程设计课）涉及的知识面广形式语言自动机理论离散数学数据结构算法,课程特点,有,点,难,?,5,教学安排,教学:48课时主要采用幻灯片辅导教学课后作业：从第3章起一般每章交1次，大约5-6次课终复习、串讲一次要求：课前预习、课后认真作业,6,学习章节,第一章编译程序概论(一般了解)第二章PL/0编译程序的实现(一般了解)第三章文法和语言第四章词法分析第五章自顶向下语法分析-LL（1）文法第六章自底向上语法分析-优先分析法第七章自底向上语法分析-LR分析法第八章语法制导翻译及代码生成,7,考试安排,考核范围:重点考察编译原理中的基本概念，编译基础理论以及编译过程的各个阶段的功能和实现方法。考核方式：期末考核与平时成绩相结合的方式。1）期末考核：笔试、闭卷，答题时限120分钟，占70%；2）平时成绩：视平时考勤、表现、课堂提问、作业完成情况等给分，占30%。以上成绩累计60分以上（包括60分）算考核通过。,8,参考书,1编译原理（第二版），张素琴、吕映芝、蒋维杜、戴桂兰编著，清华大学出版社，2011年(教材)2程序设计语言编译原理（第三版），陈火旺、刘春林等编著，国防工业出版社，2000年3编译原理与编译程序构造，高仲仪等编著，北京航空航天大学出版社，2001年4编译原理，胡伦骏、徐兰芳、刘建农编，电子工业出版社，2002年,9,5、龙书（Dragonbook）英文名：Compilers:Principles,Techniques,andTools作者：AlfredV.Aho,RaviSethi,JeffreyD.Ullman中文名：编译原理技术和工具6、虎书（Tigerbook）英文名：ModernCompilerImplementationinC作者：AndrewW.Appel,withJensPalsberg中文名：现代编译原理-C语言描述7、鲸书（Whalebook）英文名：AdvancedCompilerDesignandImplementation作者：StevenS.Muchnick中文名：高级编译器设计与实现,10,第一章编译程序概论,1.1什么是编译程序1.2编译过程概述1.3编译程序的结构1.4编译技术的发展和应用,11,1.1什么是编译程序(compiler),一、基本概念1.编译程序编译程序是现代计算机系统的基本组成部分。从功能上看，一个编译程序就是一个语言翻译程序，它把一种语言(称作源语言)书写的程序翻译成另一种语言(称作目标语言)的等价的程序。,12,程序设计语言,低级语言,高级语言,汇编语言,机器语言,翻译程序,翻译程序,2.程序设计语言及其翻译,源程序,目标程序,翻译程序,13,翻译程序Translator,汇编程序Assembler,编译程序Compiler,解释程序Interpreter,高级语言,3.翻译程序,14,4.高级语言程序处理的两种方法,(1)编译途径方法一：,源程序,运行程序,目标程序,编译程序,结果,初始数据,编译阶段,运行阶段,15,4.高级语言程序处理的两种方法,(1)编译途径方法二：,源程序,运行程序,目标代码,编译程序,结果,初始数据,编译阶段,运行阶段,汇编语言,汇编程序,汇编阶段,16,(2)解释途径,源程序,结果,解释程序,初始数据,直接解释执行、中间代码,与编译的主要区别：解释程序不产生目标代码,4.高级语言程序处理的两种方法,17,编译程序vs.解释程序,编译,解释,18,二、编译程序的功能,功能,术语编译程序的源语言(源程序S)编译程序的目标语言(目标程序O、T)编译程序的实现语言(I),高级语言书写的程序,编译程序,低级语言程序,19,三、编译程序在软件中的地位,软件系统软件语言处理系统,1.属于系统软件类,20,2.计算机软件相关概念(1)软件：计算机系统中的程序及其文档(2)系统软件：居于计算机系统中最靠近硬件的一层，其他软件一般都通过系统软件发挥作用。他和具体的应用领域无关，如编译系统和操作系统等。(3)语言处理系统：把软件语言书写的各种程序处理成可在计算机上执行的程序。(4)软件语言：用于书写软件的语言。它主要包括需求定义语言，功能性语言，设计性语言，程序设计语言以及文档语言。,21,预处理器,编译器,汇编器,装配连接编辑,骨架程序,源程序,目标汇编程序,可重定位机器代码,绝对机器码,可重定位目标文件库,3.语言处理过程,22,编译工作重要贡献者,GraceHopper，计算机软件的第一夫人Hopper“全美技术奖。1952年，世界上第一个将高级符号语言转变为机器语言的编译，COBOL语言和编译器。JohnCocke，“IBM小子”1987图灵奖，高性能计算机的体系结构方面（RISC），编译器的优化方面的贡献。A.J.Perlis1966图灵奖，获奖原因：在先进编程技术和编译架构方面的贡献。,23,1.2编译过程概述,24,把英文翻译为中文识别出句子中的一个个单词；分析句子的语法结构；根据句子的含义进行初步翻译；对译文进行修饰；写出最后的译文。,词法分析,语法分析（含语义）,中间代码生成,优化,目标代码产生,举例,25,编译逻辑过程:词法分析语法分析语义分析中间代码生成代码优化目标代码生成编译辅助工作:表格管理出错处理,26,1.词法分析,扫描源程序的ASCII码序列,拼出每一个单词,并把每个单词的ASCII码序列替换为所谓的机内表示TOKEN形式，这时还检查词法错误。但词法分析阶段不依靠语法关系。简单地说，就是从左至右读字符流的源程序、识别(拼)单词。例：position=initial+rate*60;,27,词法分析position=initial+rate*60;,单词类型单词值标识符1(id1)position算符(赋值)=标识符2(id2)initial算符(加)+标识符3(id3)rate算符(乘)*整数60分号；,28,又如一个C源程序片断：inta;a=a+2;词法分析后可能返回:单词类型单词值保留字int标识符(变量名)a界符;标识符(变量名)a算符(赋值)=标识符(变量名)a算符(加)+整数2界符；,29,2.语法分析,功能：层次分析。依据源程序的语法规则把源程序的单词序列组成语法短语(表示成语法树).扫描对象可能是源程序的ASCII码序列，也可能是词法分析后的TOKEN序列。主要任务是检查源程序的形式语法错误,每当发现错误时将输出有关信息。position=initial+rate*60;规则:=“=”:=“+”:=“*”:=“(”“)”:=:=:=,30,赋值语句,标识符,表达式,表达式,+,表达式,表达式,标识符,整数,标识符,=,表达式,*,31,id1=id2+id3*N,32,3.语义分析,语义审查(静态语义)上下文相关性类型匹配类型转换,例:mainp();floatrate;voidinitial;position=initial+rate*60;/*error*/*error*/*warning*/;,33,又如:intarr2,abc;abc=arr*10;mainp();floatrate;floatinitial;floatposition;position=initial+rate*60;,34,语义分析例：,35,4.中间代码生成,扫描对象通常是语法分析后的结果，这部分把源程序的TOKEN序列转换成更接近目标代码的中间代码三元式或四元式的序列。源程序的内部(中间)表示：后缀式、三元式、四元式、树、波兰式、逆波兰式等例如：后缀式：ab+c*表示(a+b)*c三元式：(*，id3，t1)四元式：(*，id3，t1，t2),36,中间代码生成例：,id1=id2+id3*60(1)(inttoreal,60-t1)(2)(*,id3t1t2)(3)(+,id2t2t3)(4)(=,t3-id1),37,5.代码优化,按代码级别，可分成源代码优化、中间代码优化和目标代码优化三种。其中：中间代码优化扫描对象是中间代码,任务是把优化前的中间代码转换成可产生高质量目标代码的中间代码。优化工作包括表达式优化、公共子表达式优化、不便表达式外提和削减运算强度等。,38,代码优化例：,t1=b*ct1=b*ct2=t1+0优化后：a=t1+t1t3=b*ct4=t2+t3a=t4,39,6.目标代码生成,(*,id3，60.0，t1)(+,id2，t1，id1),movfid3,R2mulf#60.0,R2movfid2,R1addfR2,R1movfR1,id1,扫描对象是中间代码，任务是从中间代码产生目标代码，这一部分的工作与目标机紧密相关，其它部分的工作几乎与目标机无关。,40,7.表格管理,较大的编译程序用到很多表格，甚至可达几十种表。不少编译程序都设立一些专门子程序（称为表格管理程序），它们专门负责管理表格。记录源程序中使用的名字收集每个名字的各种属性信息，包括：类型、作用域、分配存储信息，例如：Const1常量值：35Var1变量类型：实,41,8.出错处理,出错处理包括词法错误、语法错误、静态语义错误、动态语义错误等；出错处理模块的作用是：检查错误、报告出错信息、排错、恢复编译工作。,42,1.3编译程序的结构(components),词法分析程序语法分析程序语义分析程序中间代码生成程序代码优化程序目标代码生成程序符号表管理程序出错处理程序,43,出错处理,表格管理,44,1.4编译技术的发展和应用,一、实现方式手工机器语言汇编系统程序设计语言自动构造工具lexyacc分类：命令行集成环境,45,二、程序设计语言范型,1.命令式（过程式）：程序特点：语句1；语句2；语句3；与冯诺曼机的体系结构一致,46,2.应用式（函数式）程序特点：Functionn(funetion2(funetion1(data)程序执行：执行一个个函数施用在数据上的变换最终得到的结果编译：语法分析容易；语义处理复杂。,二、程序设计语言范型,47,3.基于规则的语言（prolog,yacc)：程序特点：使能条件1动作1使能条件2动作2使能条件3动作34.面向对象语言：抽象数据类型，继承机制编译：动态绑定；,二、程序设计语言范型,48,三、执行环境,批处理环境：将源程序作为整体处理排除程序错误不能依靠用户的外部帮助交互环境：解释增量式编译嵌入式系统环境：交叉编译分布并行环境：并行编译程序创建和测试环境：独立编译编译和调试同时设计考虑,49,高级语言的实现高级编程语言易于编程，但程序运行较慢低级语言编程时可实施更有效的控制方式，得到更有效的代码，但难编写、易出错、难维护流行编程语言的大多数演变都是朝着提高抽象级别的方向每一轮编程语言新特征的出现都刺激编译器优化的新研究,四、编译技术的应用,50,高级语言的实现每一轮编程语言新特征的出现都刺激编译器优化的新研究支持用户定义的聚合数据类型和高级控制流，如数组和记录、循环和过程调用：C、Fortran面向对象的主要概念是数据抽象和性质继承，使得程序更加模块化并易于维护：Smalltalk、C+、C#、Java类型安全的语言：Java没有指针，也不允许指针算术。它用无用单元收集机制来自动地释放那些不再使用的变量占据的内存Java设计来支持代码移植和代码移动,四、编译技术的应用,51,针对计算机体系结构的优化计算机体系结构的迅速演化引起对新的编译器技术一种不知足的需要并行化编译器重新整理指令，使得指令级并行更有效编译器从传统的串行程序自动生成并行代码，使之运行于多处理器上内存分层编译器优化历来集中在优化处理器的执行上，但是现在更强调要使内存分层更有效,四、编译技术的应用,52,新计算机体系结构的设计现在计算机系统的性能不仅仅取决于它的原始速度，还取决于编译器是否能生成充分利用其特征的代码在现代计算机体系结构的研究中，在处理器的设计阶段就开发编译器，并将编译生成的代码在模拟器上运行，以评价拟采用体系结构的特征编译器技术影响计算机体系结构设计的一个著名例子是精简指令集计算机（RISC）的发明,四、编译技术的应用,53,程序翻译二进制翻译编译器技术可用于把一种机器的二进制代码翻译成另一种机器的代码，以运行原先为别的指令集编译的代码数据库查询解释器数据库查询由一些谓词组成，这些谓词由包含关系运算的布尔表达式组成，可以被解释执行,也可以被编译成搜索数据库的命令,四、编译技术的应用,54,提高软件开发效率的工具源于编译器中代