编译第一章08本.ppt

编译原理,软件学院 郭伟 guow9966@,Compiler,课 程 简 介（课程地位）,,课程简介(课程间的拓扑图）,开课目的,预备知识：两门以上的高级程序设计语言,源程序,,目标程序,,可执行程序,编译 程序,连接,形式语言与自动机 汇编语言 数据结构等,课 程 简 介,学习的意义 对编程语言的设计和实现有深刻的理解，对和编程语言有关的理论有所了解，对宏观上把握编程语言来说，起一个奠基的作用. 从软件工程看，编译器是一个很好的实例，所介绍的概念和技术能应用到一般的软件设计之中. 大多数程序员同时是简单语言的设计者，有助于提高对这些语言的设计水平. 它的理论基础扎实，其形式化系统不仅应用于编译技术，还大量应用于人工智能,多媒体技术及数据库等领域.,课 程 简 介,[教材和参考书] 肖军模，程序设计语言编译方法，大连理工大学出版社 陈火旺等,程序设计语言编译原理,国防工业出版社,2000 陈意云、张昱，编译原理和技术，高等教育出版社， 2003 吕映芝等，编译原理，清华大学出版社,课 程 简 介,课程要求: 课时:48学时 分为两部分:(分别计分) 理论基础(48学时):课堂教学 实践部分(0学时):上机实践目的:掌握编译的理论基础和形式化系统，了解编译的全过程及其具体实现方法。

能运用所学技术解决实际问题，能独立编写一个小型编译系统课 程 简 介,要求: 提前预习,认真听课,理解基本概念,基本原理与基本算法 在看书时或理解例题及习题时,一定要划出相应的细节变化过程,通过画图来加深理解 作业要求独立、按时完成 地点：耘慧楼 421 E-mail：guow9966@ 答疑时间： 学期总评 = 考试成绩占80%，平时占20%,内容简介,•第一章 引论 •第二章 编译基础 •第三章 词法分析 •第四章 自上而下语法分析 •第五章 自下而上语法分析 •第六章 语法制导翻译技术和中间代码生成 •第七章 运行时的存贮空间组织 •第八章 优化 •第九章 目标代码生成 •第十章 面向对象语言编译,,Compiler,第一章 引论,Compiler,第二章 编译基础,Compiler,第三章 词法分析,Compiler,Compiler,Compiler,Compiler,Compiler,Compiler,第一章 引 论,（介绍名词术语、了解编译系统的结构和编译过程）,编译的起源：程序设计语言的发展,基本概念,编译过程和编译程序构造,编译程序的生成,1.1 什么叫编译程序？,Compiler,C7 06 0000 0002,MOV x, 2,x = 2,程序设计语言的发展,,Compiler,•低级语言（Low level Language) --字位码、机器语言、汇编语言特点：与特定的机器有关，功效高，但使用复杂、繁琐、费时、易出错,•高级语言 -- Fortran、Pascal、C语言等 特点：不依赖具体机器，移植性好、对用户要求低、易使用、易维护等。

用高级语言编制的程序，计算机不能立即执行， 必须通过一个“翻译程序”加工，转化为与其等价的 机器语言程序，机器才能执行 这种翻译程序，称之为“编译程序”编译程序的种类,诊断编译程序 优化编译程序 交叉编译程序 可变目标编译程序,,高级语言处理过程图,,,Compiler,基本概念,• 源程序用汇编语言或高级语言编写的程序称为源程序• 目标程序---用目标语言所表示的程序 目标语言：可以是介于源语言和机器语言之间的 “中间语言”，可以是某种机器的机器语言,也可以是某机器的汇编语言• 翻译程序将源程序转换为目标程序的程序称为翻译程序 它是指各种语言的翻译器，包括汇编程序和编译程序， 是汇编程序、编译程序以及各种变换程序的总称Compiler,源程序、翻译程序、目标程序 三者关系：,源程序,翻译程序,目标程序,,SOURCE PROGRAM,,,TRANSLATER,,OBJECT PROGRAM,即源程序是翻译程序的输入，目标程序是翻译程序的输出,Compiler,• 汇编程序 若源程序用汇编语言书写，经过翻译程序得到用机器语言 表示的程序，这时的翻译程序就称之为汇编程序，这种翻译过 程称为“汇编”(Assemble）,• 编译程序若源程序是用高级语言书写，经加工后得到目标程序， 这种翻译过程称“编译”（Compile),汇编程序与编译程序都是翻译程序，主要区别是加工对象的 不同。

由于汇编语言格式简单，常与机器语言之间有一一对 应的关系，汇编程序所要做的翻译工作比编译程序简单得多源程序,汇编语言,高级语言,翻译程序,汇编程序,编译程序,,,目标程序,机器语言,目标程序,,,,,Compiler,源程序的编译和运行,编译或汇编阶段,运行阶段,1.2 编译过程概述 一段英文翻译成中文 需经下列步骤: 识别出句子中的单词分析句子的语法结构根据句子的含义进行初步分析 对译文进行修饰写出最后的译文,编译程序,语法分析,词法分析,语义分析及中间代码生成,代码优化,目标代码生成,,,,,,编译程序的各个阶段,Compiler,,Compiler,编译过程是指将高级语言程序翻译为等价的目标程 序的过程习惯上是将编译过程划分为5个基本阶段：,词法分析,语法分析,语义分析、生成中间代码,代码优化,生成目标程序,第一阶段 词法分析,Compiler,任务：分析和识别单词源程序是由字符序列构成的，词法分析扫描源程序(字符串),根据语言的词法规则分析并识别单词，并以某种编码形式输出•单词：是语言的基本语法单位，一般语言有五大类单词 语言定义的关键字或保留字（如BEGIN、END、IF） 标识符常数分界符（如;、（、） ……）运算符 （如+、-、*、/……）,对于如下的字符串,词法分析程序将分析和识别出9个单词： X1 := ( 2.0 + 0.8 ) * C11 2 3 4 5 6 7 8 9,举例说明 Void jisuan( ){ int y,c,d;float x,a,b;x=a+b*50;y=c+)d*(x+b;},Compiler,一、词法分析,识别右边程序中的单词 基本字：Void,int,float 标识符：a,b,c,d,x,y,jisuan 常数：50 运算符：*,+,=,- 界限符：{ } ; , ( ),一.词法分析,词法分析依照词法规则，识别出正确的单词，转换成统一规格备用 转换—对基本字，运算符，界符的转换—标识符的转换—常数的转换—转换完成后的格式（类号，内码） 描述词法规则的有效工具是正规式和有限自动机,Compiler,１．词法分析 完成的任务：,读入源程序,识别出单词：,position、=、initial 、 + 、 rate、 *、 60,关键字、标识符、常数、算符和界符,并用记号表示识别出的单词,例：id1、id2、id3表示position、 initial、 rate,记号表示逻辑上相关的字符序列，常用整数来表示,形成一个记号的字符序列称为该记号的单词,上述语句表示为：id1=id2+id3*60,以position = initial + rate * 60为例,Compiler,第一章 引 论,二、语法分析,Compiler,任务：根据语法规则（即语言的文法），分析并识别出 各种语法成分，如表达式、各种说明、各种语句、 过程、函数等，并进行语法正确性检查。

语法规则—语言的规则，又称为文法 语法规则的表示： ——BNF：A::=B|C,X1:= ( 2.0 + 0.8 ) * C1,赋值语句的文法： → → →:= → ……,赋值语句的语法规则： A::=V=E E::=T|E+T T::=F|T*F F::=V|(E)|C V::=标识符 C::=常数,语法分析的方法： ——推导（derive)和归约（reduce) 推导——最左推导，最右推导 最右推导 最左归约 （x=a+b*50),赋值语句的语法规则： A::=V=E E::=T|E+T T::=F|T*F F::=V|(E)|C V::=标识符 C::=常数,举例说明 Void jisuan( ){int y,c,d;float x,a,b;x=a+b*50;y=c+)d*(x+b;},A V=E,,V=E+T,,V=E+T*F,,,V=E+T*C,V=E+T*50,,V=E+F*50,,V=E+V*50,,V=E+b*50,,V=T+b*50,,V=F+b*50,,V=V+b*50,,V=a+b*50,,x=a+b*50,,举例说明 Void jisuan( ){int y,c,d;float x,a,b;x=a+b*50;y=c+)d*(x+b;},赋值语句的语法规则： A::=V=E E::=T|E+T T::=F|T*F F::=V|(E)|C V::=标识符 C::=常数,最右推导,归约—最右归约，最左归约 A V=E x=E x=E+T x=T+Tx=V+T x=a+T x=a+T*F x=a+F*F x=a+V*F x=a+b*F x=a+b*C x=a+b*50 最左推导 最右归约,,,,,,,,,,,,,赋值语句的语法规则： A::=V=E E::=T|E+T T::=F|T*F F::=V|(E)|C V::=标识符 C::=常数,C语言语句 y=c+)d*(x+b 分析过程: A V=E V=E+T V=E+F V=E+V V=E+b V=T+b V=T*F+b V=T*V+b V=T*x+b 无法得到该句故，该C语言语句是错误的,,,,,,,,,,赋值语句的语法规则： A::=V=E E::=T|E+T T::=F|T*F F::=V|(E)|C V::=标识符 C::=常数,举例说明 Void jisuan( ){int y,c,d;float x,a,b;x=a+b*50;y=c+)d*(x+b;},具体地说，语法分析是在记号流的基础上建立一个层次结构——建立语法树 语法分析过程也可以用一棵倒着的树来表示 这棵树叫语法树，比如上述程序段中的单词序列：id1=id2+id3*60经语法分析得知其是PASCAL语言的“赋值语句”，表示成如下所示形式。

二、语法分析,Compiler,,＝,id1,id2,id3,+,*,60,,,,,,,=,,+,,,*,id1,id2,id3,Num,,,1,2,3,,,,,,,,60,a.语法树,b.数据结构,二、语法分析,Compiler,第一章 引 论,三、语义分析与生成中间代码,任务：对识别出的各种语法成分进行语义分析， 并产生相应的中间代码• 中间代码：一种介于源语言和目标语言之间的中间语言形式,• 生成中间代码的目的： 便于做优化处理； 便于编译程序的移植• 中间代码的形式：编译程序设计者可以自己设计，常用的有 四元式、三元式、逆波兰表示等Compiler,例： X1:= ( 2.0 + 0.8 ) * C1,由语法分析识别出为赋值语句，语义分析首先要分析语义上的正确性，例如要检查表达式中和赋值号两边的类型是否一致• 根据赋值语句的语义，生成中间代码即用一种语言形式来代替另一种语言形式，这是翻译的关键步骤翻译的实质：语义的等价性）,三、语义分析与生成中间代码,position = initial + rate * 60,总结一下语义分析主要的任务： 完成静态语义审查和处理 上下文相关性审查 类型匹配审查 类型转换,三、语义分析与生成中间代码,Compiler,★四元式（三地址指令）,X1:= ( 2.0 + 0.8 ) * C1,。