《编译原理绪论》PPT课件.ppt

《《编译原理绪论》PPT课件.ppt》由会员分享，可在线阅读，更多相关《《编译原理绪论》PPT课件.ppt（34页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第第 1 1 讲讲西北农林科技大学本科教程西北农林科技大学本科教程 主讲教师：主讲教师：赵建邦赵建邦 办公地址：办公地址：信息学院信息学院403403联系电话：联系电话：电子邮箱：电子邮箱：联系方式联系方式教材和参考书教材和参考书u关于关于编译原理编译原理l1 1 编译原理理论概述编译原理理论概述l2 2 学习目标学习目标l3 3 学习方法学习方法u重点掌握重点掌握l1 1 翻译、解释、编译的区别和联系翻译、解释、编译的区别和联系l2 2 编译过程分为哪些步骤编译过程分为哪些步骤本讲目标本讲目标 第一章第一章 绪论绪论l1.1 1.1 程序设计语言和编译程序程序设计语言和编译程序l1.2 1.

2、2 编译程序的历史及发展编译程序的历史及发展(自学自学)l1.3 1.3 编译过程和编译程序结构编译过程和编译程序结构l1.4 1.4 编译程序的开发编译程序的开发l1.5 1.5 构造编译程序所应具备的知识内容构造编译程序所应具备的知识内容u计算机的指令系统计算机的指令系统计算机所能执行的计算机所能执行的每一种操作每一种操作称为一条称为一条指令指令，计算机能够，计算机能够执行的全部指令集合就是该计算机的执行的全部指令集合就是该计算机的指令系统指令系统。指令格式：指令格式：操作码操作码 操作地址码操作地址码PCPC的指令规模一般是的指令规模一般是300500300500条。条。可执行程序就是不

3、同指令的反复组合。可执行程序就是不同指令的反复组合。1.1 1.1 程序设计语言和编译程序程序设计语言和编译程序算术运算、逻辑运算、算术运算、逻辑运算、存数、取数、转移等。存数、取数、转移等。指出该条指令涉及的操指出该条指令涉及的操作数的地址。作数的地址。低级语言低级语言u机器语言机器语言 二进制形式的指令序列二进制形式的指令序列称为某计算机的称为某计算机的机器语言机器语言，也是计，也是计算机唯一能够直接识别并执行的语言。算机唯一能够直接识别并执行的语言。u汇编语言汇编语言用用助记符助记符代替机器语言的二进制指令，所生成的语言就是代替机器语言的二进制指令，所生成的语言就是汇编语言汇编语言。例如

4、用例如用“MOVMOV”代替代替“00010001”，用，用“ADDADD”代替代替“00110011”，1.1 1.1 程序设计语言和编译程序程序设计语言和编译程序低级语言低级语言u举例：计算举例：计算“b=a+2b=a+2”u显然，汇编语言比机器语言有了长足的进步。但仍存在以下显然，汇编语言比机器语言有了长足的进步。但仍存在以下缺点：缺点：严重依赖目标机器；严重依赖目标机器；不易开发、调试；不易开发、调试；和自然语言存在鸿沟，可读性差。和自然语言存在鸿沟，可读性差。1.1 1.1 程序设计语言和编译程序程序设计语言和编译程序MOV a，R1ADD#2，R1MOV R1，b0001 01 0

5、0 000000000011 01 10 000000100010 01 00 00000100汇编语言机器语言汇编程序高级语言的发展高级语言的发展1.1 1.1 程序设计语言和编译程序程序设计语言和编译程序高级语言高级语言高级语言已经从具体机器中抽象出来，摆脱了依赖具体机高级语言已经从具体机器中抽象出来，摆脱了依赖具体机器的问题。器的问题。高级语言虽然更符合人类的思维习惯，但高级语言程序也高级语言虽然更符合人类的思维习惯，但高级语言程序也必须必须翻译翻译(编译编译)成最终能够直接执行的机器语言程序。而成最终能够直接执行的机器语言程序。而且，这个难度比汇编过程大大增加。且，这个难度比汇编过程大

6、大增加。1.1 1.1 程序设计语言和编译程序程序设计语言和编译程序从从1966年至今，所有颁布的图灵奖中，有三分之一年至今，所有颁布的图灵奖中，有三分之一的奖项颁布给了对高级程序设计语言和编译理论有的奖项颁布给了对高级程序设计语言和编译理论有杰出贡献的科学家。杰出贡献的科学家。程序设计语言的转换程序设计语言的转换u翻译翻译是指将某种语言的源程序，在不改变语义的条件下，转换是指将某种语言的源程序，在不改变语义的条件下，转换成另一种语言程序成另一种语言程序目标语言程序目标语言程序l编译编译专指由高级语言程序一次性转换成低级语言程序，专指由高级语言程序一次性转换成低级语言程序，类似于类似于全文翻译

7、全文翻译l解释解释接受某高级语言的一个语句输入，进行解释并控制计算机接受某高级语言的一个语句输入，进行解释并控制计算机执行，得到这个语句的执行结果后，等待下一个语句的解执行，得到这个语句的执行结果后，等待下一个语句的解释执行，执行过程中并不产生目标程序。释执行，执行过程中并不产生目标程序。类似于口译类似于口译1.1 1.1 程序设计语言和编译程序程序设计语言和编译程序不同高级语言程序的执行类型不同高级语言程序的执行类型：u编译型（本课程只关注编译型）编译型（本课程只关注编译型）C C、C+C+、PascalPascal、DelphiDelphi等：生成目标程序。等：生成目标程序。u解释型解释型

8、BASICBASIC、UnixUnix的的shellshell、网络浏览器（将、网络浏览器（将HTMLHTML及及JavascriptJavascript等脚本程序解释执行）等；等脚本程序解释执行）等；u特殊型特殊型即时编译：即时编译：JavaJava：先翻译成较低级的字节码程序，然后编：先翻译成较低级的字节码程序，然后编译为机器语言程序。译为机器语言程序。1.1 1.1 程序设计语言和编译程序程序设计语言和编译程序在翻译的过程中，必须始终遵循的原则是：在逻辑上等价。在翻译的过程中，必须始终遵循的原则是：在逻辑上等价。编译型高级语言程序的阶段：编译型高级语言程序的阶段：高级语言程序的执行通常分

9、为高级语言程序的执行通常分为两个阶段两个阶段：编译阶段编译阶段和和运运行阶段行阶段。编译程序编译程序就是指这样一种程序，通过它能够将用高级语就是指这样一种程序，通过它能够将用高级语言编写的源程序转换成与之在逻辑上等价的低级语言形式的言编写的源程序转换成与之在逻辑上等价的低级语言形式的目标程序（如目标程序（如C C语言下的语言下的exeexe）u编译：编译：u运行：运行：初始数据初始数据 +目标程序目标程序 +运行系统运行系统 计算结果计算结果1.1 1.1 程序设计语言和编译程序程序设计语言和编译程序高级语言程序的执行分为高级语言程序的执行分为三个阶段三个阶段的情况：的情况：编译阶段编译阶段、

10、汇编阶段汇编阶段和和运行阶段运行阶段。1.1 1.1 程序设计语言和编译程序程序设计语言和编译程序源程序编译程序汇编语言汇编程序目标代码编译阶段汇编阶段目标代码运行系统初始数据计算结果运行阶段思考：解释和编译的主要区别是什么？思考：解释和编译的主要区别是什么？u机器语言的诞生机器语言的诞生例：例：C7 06 0000 0002 C7 06 0000 0002（将数字（将数字2 2移到地址移到地址0000)0000)u汇编语言和汇编程序的诞生汇编语言和汇编程序的诞生例：例：MOV X,2(MOV X,2(功能和上式类似功能和上式类似,其中其中X X的值赋值为的值赋值为0 0）u第一个高级语言第一

11、个高级语言FORTRANFORTRAN及其编译器的诞生（及其编译器的诞生（19571957，IBMIBM）uChomskyChomsky研究了语言和文法的数学理论研究了语言和文法的数学理论0 0型、型、1 1型、型、2 2型、型、3 3型型u编译程序的自动生成研究编译程序的自动生成研究YACCYACC、JavaCC:JavaCC:语法分析器自动生成工具语法分析器自动生成工具1.2 1.2 编译程序的历史及发展（里程碑意义的事件）编译程序的历史及发展（里程碑意义的事件）u联系实际，想想自然语言的翻译联系实际，想想自然语言的翻译Let me show you!Let me show you!翻译成

12、中文的五个阶段：翻译成中文的五个阶段：词法分析：识别出句子中的一个个单词词法分析：识别出句子中的一个个单词语法分析：分析句子的语法结构，是否符合英语语法语法分析：分析句子的语法结构，是否符合英语语法语义分析：对正确的英文句子分析其含义，并用汉语语义分析：对正确的英文句子分析其含义，并用汉语表示表示优化：根据上下文的关系以及汉语的表达习惯对中文优化：根据上下文的关系以及汉语的表达习惯对中文句子做修饰工作句子做修饰工作输出全部中文输出全部中文1.3 1.3 编译过程和编译程序结构编译过程和编译程序结构u高级语言程序的编译过程高级语言程序的编译过程输入：输入：源程序源程序，输出：，输出：目标程序目标

13、程序五个阶段：五个阶段：词法分析词法分析 语法分析语法分析 语义分析和中间代码生成语义分析和中间代码生成中间代码优化中间代码优化 目标代码生成目标代码生成1.3 1.3 编译过程和编译程序结构编译过程和编译程序结构u1.3.1 1.3.1 词法分析词法分析任务：任务：将源程序中的字符串变换成单词符号流将源程序中的字符串变换成单词符号流例如，如下的例如，如下的C C语言程序：语言程序：通过词法分析得到如下单词符号：通过词法分析得到如下单词符号：关键字：关键字：float标识符：标识符：position initial rate常数：常数：60运算符：运算符：+*界符：界符：,;=1.3 1.3

14、编译过程和编译程序结构编译过程和编译程序结构 float position,initial,rate;position=initial+rate*60;词法分析所遵循的是词法分析所遵循的是语语言的构词规则言的构词规则u1.3.2 1.3.2 语法分析语法分析任务：任务：根据语法规则，从单词符号串中识别出各种语法单根据语法规则，从单词符号串中识别出各种语法单位（如表达式、说明、程序段等），并检查语法结构的正位（如表达式、说明、程序段等），并检查语法结构的正确性。确性。“position=initial+rate*60;”包含哪些语法单位包含哪些语法单位？被定义为：被定义为：=被定义为：被定义为：

15、+被定义为：被定义为：*被定义为：被定义为：|1.3 1.3 编译过程和编译程序结构编译过程和编译程序结构语法分析遵循语法分析遵循语言的语法规则语言的语法规则，通常使用，通常使用上下文无关文法上下文无关文法u1.3.2 1.3.2 语法分析语法分析“position=initial+rate*60”的的语法树语法树：1.3 1.3 编译过程和编译程序结构编译过程和编译程序结构+表达式表达式标识符position*表达式表达式initial标识符rate常数60赋值语句=表达式标识符u1.3.3 1.3.3 语义分析和中间代码生成语义分析和中间代码生成任务：任务：1 1、对每种语法单位（范畴）进

16、行静态语义审查、对每种语法单位（范畴）进行静态语义审查 (验证语法结构合法的程序是否真正有意义验证语法结构合法的程序是否真正有意义)2 2、在语义检查正确的情况下进行中间代码的翻译、在语义检查正确的情况下进行中间代码的翻译中间代码是中间代码是介于高级语言语句和低级语言的指令之间的一介于高级语言语句和低级语言的指令之间的一种种独立于具体硬件的记号系统独立于具体硬件的记号系统，既有一定抽象，又与低级，既有一定抽象，又与低级语言指令十分接近，因此转换成目标代码比较容易语言指令十分接近，因此转换成目标代码比较容易中间代码的常用表示形式：中间代码的常用表示形式：四元式、三元式、间接三元式四元式、三元式、

17、间接三元式和逆波兰记号等（将在第四章介绍）和逆波兰记号等（将在第四章介绍）1.3 1.3 编译过程和编译程序结构编译过程和编译程序结构把语法单位翻译成中间代码遵循把语法单位翻译成中间代码遵循语言的语义规则语言的语义规则u1.3.3 1.3.3 语义分析和中间代码生成语义分析和中间代码生成“position=initial+rate*60”所转换的四元式：所转换的四元式：1.3 1.3 编译过程和编译程序结构编译过程和编译程序结构（*，rate,60,t1 rate,60,t1 ）（+，initial,t1,t2 initial,t1,t2 ）（=，t2,_,positiont2,_,posit

18、ion）（操作符，操作数（操作符，操作数1,1,操作数操作数2 ,2 ,执行结果执行结果 ）u1.3.4 1.3.4 中间代码优化中间代码优化任务：是对前阶段产生的中间代码进行任务：是对前阶段产生的中间代码进行等价等价变换或改造，变换或改造，以期获得更为高效以期获得更为高效(节省时间和空间节省时间和空间)的目标代码的目标代码优化遵循优化遵循等价变换规则等价变换规则手段：删除冗余运算、删除无用赋值、合并已知量、手段：删除冗余运算、删除无用赋值、合并已知量、循环优化等循环优化等“position=initial+rate*60”1.3 1.3 编译过程和编译程序结构编译过程和编译程序结构（*，ra

19、te,60,t1 ）（+，initial,t1,t2 ）（=，t2,_,position）（+，initial,t1,position）u1.3.5 1.3.5 目标代码生成目标代码生成任务：是把中间代码任务：是把中间代码(或经优化处理之后或经优化处理之后)变换成变换成特定机器特定机器上的机器语言程序或汇编语言程序上的机器语言程序或汇编语言程序，实现最终的翻译工作，实现最终的翻译工作因为目标语言的关系，该阶段的工作非常依赖硬件系统因为目标语言的关系，该阶段的工作非常依赖硬件系统本学期不作为教学要求本学期不作为教学要求1.3 1.3 编译过程和编译程序结构编译过程和编译程序结构u编译程序结构示意

20、图编译程序结构示意图1.3 1.3 编译过程和编译程序结构编译过程和编译程序结构注意：一个编译过程注意：一个编译过程可分为可分为一遍、两遍或一遍、两遍或多遍多遍完成，每一遍完完成，每一遍完成所规定的任务。成所规定的任务。例如，第一遍只完成例如，第一遍只完成词法分析的任务，第词法分析的任务，第二遍完成语法分析和二遍完成语法分析和语义加工工作并生成语义加工工作并生成中间代码，第三遍再中间代码，第三遍再实现代码优化和目标实现代码优化和目标代码生成。代码生成。但是多遍会导致编译但是多遍会导致编译效率的降低。效率的降低。u1.3.6 1.3.6 表格管理和出错处理表格管理和出错处理表格管理表格管理编译程

21、序过程中要记录变量名（存储分配、类型、作编译程序过程中要记录变量名（存储分配、类型、作用域等）用域等）如果是函数名（参数数量、类型，参数的传递方式、如果是函数名（参数数量、类型，参数的传递方式、返回值类型等）返回值类型等）常量表、分程序入口表以及中间代码表等常量表、分程序入口表以及中间代码表等编译程序的各个阶段需要编译程序的各个阶段需要构造构造、查找查找、更新更新变量和函变量和函数的信息数的信息,表格管理耗费了编译过程的绝大部分时间表格管理耗费了编译过程的绝大部分时间因此，编译程序中必须有一个管理各种表格的程序因此，编译程序中必须有一个管理各种表格的程序1.3 1.3 编译过程和编译程序结构编

22、译过程和编译程序结构u1.3.6 1.3.6 表格管理和出错处理表格管理和出错处理出错处理出错处理完整的编译程序应该能够定位和跟踪错误完整的编译程序应该能够定位和跟踪错误能够捕获到各种词法、语法、语义错误，并定位错误能够捕获到各种词法、语法、语义错误，并定位错误的类型及出错位置的类型及出错位置此外，为了尽可能多地发现错误，应在发现错误后还此外，为了尽可能多地发现错误，应在发现错误后还能继续编译下去，以便发现更多的错误能继续编译下去，以便发现更多的错误1.3 1.3 编译过程和编译程序结构编译过程和编译程序结构u1.4.1 1.4.1 开发编译程序的要求开发编译程序的要求开发人员要熟悉源程序语言

23、开发人员要熟悉源程序语言源程序语言的语法和语义有全面深入的理解源程序语言的语法和语义有全面深入的理解对目标机器的环境有深入的研究对目标机器的环境有深入的研究确定编译程序的开发方案及方法确定编译程序的开发方案及方法开发步骤（熟悉编译原理理论）开发步骤（熟悉编译原理理论）软件开发功底，保证编译程序的可读性与扩展性软件开发功底，保证编译程序的可读性与扩展性选择合适的编程语言选择合适的编程语言一般选择一般选择PascalPascal、C C、JavaJava和和AdaAda等高级语言等高级语言1.4 1.4 编译程序的开发编译程序的开发u1.4.2 1.4.2 编译程序的开发技术编译程序的开发技术自编

24、译自编译用某种高级语言书写自己的编译程序用某种高级语言书写自己的编译程序交叉编译交叉编译针对针对B B机器，在机器，在A A机上编写一个编译程序，使得机上编写一个编译程序，使得B B机器上机器上的源代码可以被编译成目标程序的源代码可以被编译成目标程序自展自展用机器语言或汇编语言实现简单的用机器语言或汇编语言实现简单的L0L0语言，用语言，用L0L0编写编写自身的扩充语言自身的扩充语言L1L1的编译程序，再用的编译程序，再用L1L1扩充扩充L2L2 移植移植修改基于修改基于A A机器的编译程序，使得能够在机器的编译程序，使得能够在B B机器上顺利机器上顺利执行执行1.4 1.4 编译程序的开发编

25、译程序的开发u1.4.3 1.4.3 编译程序的自动生成编译程序的自动生成有没有一种软件，可以自动生成高效的编译程序？有没有一种软件，可以自动生成高效的编译程序？输入：输入：源语言（如源语言（如C C语言）的语法：包括关键字、标识符的定语言）的语法：包括关键字、标识符的定义，各种语法结构等义，各种语法结构等输出：编译程序输出：编译程序当有一段源程序作为该编译程序的输入时，可以得到当有一段源程序作为该编译程序的输入时，可以得到目标代码目标代码现有的编译程序自动生成系统：现有的编译程序自动生成系统：JavaCCJavaCC,Lex,YACC,Lex,YACC等等我们需要做的是尽可能提供完备、正确的

26、语法描述和我们需要做的是尽可能提供完备、正确的语法描述和机器语言的描述机器语言的描述1.4 1.4 编译程序的开发编译程序的开发u要在一台机器上为某种源语言构造一个编译程序，需要掌握下要在一台机器上为某种源语言构造一个编译程序，需要掌握下述三方面的内容：述三方面的内容：深刻理解源语言的语法结构深刻理解源语言的语法结构(自学理解自学理解),),如：如：forfor循环的终值问题循环的终值问题参数传递的顺序问题参数传递的顺序问题对目标机器的硬件和指令系统有深刻的了解对目标机器的硬件和指令系统有深刻的了解主要针对于要产生目标代码的情况主要针对于要产生目标代码的情况熟练掌握编译方法熟练掌握编译方法编译

27、程序中各个环节相互联系编译程序中各个环节相互联系表达式表达式 条件表达式条件表达式 forfor、switchswitch、whilewhile的实现顺序的实现顺序1.5 1.5 构造编译程序所应具备的知识构造编译程序所应具备的知识l掌握编译的理论基础和形式化系统掌握编译的理论基础和形式化系统l词法分析词法分析l语法分析语法分析l语义分析和中间代码生成语义分析和中间代码生成l掌握编译程序的开发过程（掌握编译程序的开发过程（5 5次实验次实验）lJavaCCJavaCC：一种：一种eclipseeclipse插件。通过该插件，可以很方便插件。通过该插件，可以很方便地定义一种编程语言的文法，从而自

28、动生成编译程序。地定义一种编程语言的文法，从而自动生成编译程序。2 2 学习目标学习目标 l1 1、认真听课，理解基本概念、原理和算法、认真听课，理解基本概念、原理和算法l2 2、章节环环相扣，前面的理论是后面学习的基础，因此、章节环环相扣，前面的理论是后面学习的基础，因此做好复习，做好复习，切忌遗留问题切忌遗留问题l3 3、看懂书中的例题，、看懂书中的例题，多做课后习题多做课后习题(准备一个作业本准备一个作业本)l4 4、理论联系实践、理论联系实践3 3 学习方法学习方法 u本章小结本章小结掌握编译程序与高级程序设计语言的关系掌握编译程序与高级程序设计语言的关系掌握编译分为哪几个阶段掌握编译分为哪几个阶段了解各个阶段完成的主要功能了解各个阶段完成的主要功能